LIPIcs.AofA.2022.9.pdf
- Filesize: 0.58 MB
- 13 pages
Document
Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field
Author
-
Part of:
Volume:
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-08
File
Document Identifiers
Acknowledgements
I would like to thank the referees for their helpful comments which improve the presentation of the paper.
Cite As Get 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)
0PDF Downloads
References
-
L. Carlitz. Some theorems on irreducible reciprocal polynomials over a finite field. J. Reine Angew. Math., 227:212-220, 1967.
-
S. D. Cohen. On irreducible polynomials of certain types in finite fields. Proc. Camb. Phil. Soc., 66:335-344, 1969.
-
S. D. Cohen. Explicit theorems on generator polynomials. Finite Fields Appl., 11:337-357, 2005.
- Z.C. Gao. Counting self-reciprocal irreducible monic polynomials with prescribed coefficients over a finite field. URL: http://arxiv.org/abs/2109.09006.
-
T. Garefalakis and G. Kapetanakis. On the hansen-mullen conjecture for self-reciprocal irreducible polynomials. Finite Fields Appl., 69:832-841, 2012.
-
J Ha. Irreducible polynomials with several prescribed coefficients. Finite Fields Appl., 40:10-25, 2016.
-
K.H. Ham and G.L. Mullen. Distribution of irreducible polynomials of small degrees over finite fields. Math. Comp., 67(221):337-341, 1998.
-
D. R. Hayes. The distribution of irreducibles in GF[q, x]. Trans. Amer. Math. Soc., 117:101-127, 1965.
-
C.N. Hsu. The distribution of irreducible polynomials in π½_q[t]. J. Number Theory, 61(1):85-96, 1996.
-
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.
-
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.
-
P. Pollack. Irreducible polynomials with several prescribed coefficients. Finite Fields Appl., 22:70-78, 2013.
-
D. Bossen S. Hong. On some properties of self-reciprocal polynomials. IEEE Trans. Inform. Theory, 21(4):462-464, 1975.
-
D. Wan. Generators and irreducible polynomials over finite fields. Math. Comp., 219:1195-1212, 1997.
- 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.