Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field

Author Zhicheng Gao



PDF
Thumbnail PDF

File

LIPIcs.AofA.2022.9.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Author Details

Zhicheng Gao
  • School of Mathematics and Statistics, Carleton University, Canada

Acknowledgements

I would like to thank the referees for their helpful comments which improve the presentation of the paper.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.AofA.2022.9

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing β†’ Generating functions
  • Mathematics of computing β†’ Enumeration
Keywords
  • finite fields
  • irreducible polynomials
  • prescribed coefficients
  • generating functions
  • Weil bounds
  • self-reciprocal

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. L. Carlitz. Some theorems on irreducible reciprocal polynomials over a finite field. J. Reine Angew. Math., 227:212-220, 1967. Google Scholar
  2. S. D. Cohen. On irreducible polynomials of certain types in finite fields. Proc. Camb. Phil. Soc., 66:335-344, 1969. Google Scholar
  3. S. D. Cohen. Explicit theorems on generator polynomials. Finite Fields Appl., 11:337-357, 2005. Google Scholar
  4. Z.C. Gao. Counting self-reciprocal irreducible monic polynomials with prescribed coefficients over a finite field. URL: http://arxiv.org/abs/2109.09006.
  5. T. Garefalakis and G. Kapetanakis. On the hansen-mullen conjecture for self-reciprocal irreducible polynomials. Finite Fields Appl., 69:832-841, 2012. Google Scholar
  6. J Ha. Irreducible polynomials with several prescribed coefficients. Finite Fields Appl., 40:10-25, 2016. Google Scholar
  7. K.H. Ham and G.L. Mullen. Distribution of irreducible polynomials of small degrees over finite fields. Math. Comp., 67(221):337-341, 1998. Google Scholar
  8. D. R. Hayes. The distribution of irreducibles in GF[q, x]. Trans. Amer. Math. Soc., 117:101-127, 1965. Google Scholar
  9. C.N. Hsu. The distribution of irreducible polynomials in 𝔽_q[t]. J. Number Theory, 61(1):85-96, 1996. Google Scholar
  10. D. Panario. Open problems for polynomials over finite fields and applications. In Chapter 5 of Proceedings on the Open Problems in Mathematics and Computer Science Conference, pages 111-126. Springer, 2015. Google Scholar
  11. D. Panario and G. Tzanakis. A generalization of the hansen-mullen conjecture on irreducible polynomials over finite fields. Finite Fields Appl., 18:303-315, 2012. Google Scholar
  12. P. Pollack. Irreducible polynomials with several prescribed coefficients. Finite Fields Appl., 22:70-78, 2013. Google Scholar
  13. D. Bossen S. Hong. On some properties of self-reciprocal polynomials. IEEE Trans. Inform. Theory, 21(4):462-464, 1975. Google Scholar
  14. D. Wan. Generators and irreducible polynomials over finite fields. Math. Comp., 219:1195-1212, 1997. Google Scholar
  15. S. Kuttner Z. Gao and Q. Wang. Counting irreducible polynomials with prescribed coefficients over a finite field. Finite Fields Appl., 80(102023), 2022. URL: https://doi.org/10.1016/j.ffa.2022.102023.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail