Search Results

Documents authored by Gao, Zhicheng

Document
DOI: 10.4230/LIPIcs.AofA.2022.9
Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field

Authors: Zhicheng Gao

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
A polynomial is called self-reciprocal (or palindromic) if the sequence of its coefficients is palindromic. In this paper we obtain improved error bounds for the number of irreducible polynomials and self-reciprocal irreducible monic polynomials with prescribed coefficients over a finite field. The improved bounds imply that self-reciprocal irreducible monic polynomials with degree 2d and prescribed 𝓁 leading coefficients always exist provided that 𝓁 is slightly less than d/2.
Cite as

Zhicheng Gao. Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gao:LIPIcs.AofA.2022.9,
  author =	{Gao, Zhicheng},
  title =	{{Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.9},
  URN =		{urn:nbn:de:0030-drops-160958},
  doi =		{10.4230/LIPIcs.AofA.2022.9},
  annote =	{Keywords: finite fields, irreducible polynomials, prescribed coefficients, generating functions, Weil bounds, self-reciprocal}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.13
Counting Cubic Maps with Large Genus

Authors: Zhicheng Gao and Mihyun Kang

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We derive an asymptotic expression for the number of cubic maps on orientable surfaces when the genus is proportional to the number of vertices. Let Σ_g denote the orientable surface of genus g and θ=g/n∈ (0,1/2). Given g,n∈ ℕ with g→ ∞ and n/2-g→ ∞ as n→ ∞, the number C_{n,g} of cubic maps on Σ_g with 2n vertices satisfies C_{n,g} ∼ (g!)² α(θ) β(θ)ⁿ γ(θ)^{2g}, as g→ ∞, where α(θ),β(θ),γ(θ) are differentiable functions in (0,1/2). This also leads to the asymptotic number of triangulations (as the dual of cubic maps) with large genus. When g/n lies in a closed subinterval of (0,1/2), the asymptotic formula can be obtained using a local limit theorem. The saddle-point method is applied when g/n→ 0 or g/n→ 1/2.
Cite as

Zhicheng Gao and Mihyun Kang. Counting Cubic Maps with Large Genus. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.AofA.2020.13,
  author =	{Gao, Zhicheng and Kang, Mihyun},
  title =	{{Counting Cubic Maps with Large Genus}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.13},
  URN =		{urn:nbn:de:0030-drops-120437},
  doi =		{10.4230/LIPIcs.AofA.2020.13},
  annote =	{Keywords: cubic maps, triangulations, cubic graphs on surfaces, generating functions, asymptotic enumeration, local limit theorem, saddle-point method}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact