Geodesic
A New Proof of the Hansen—Mullen Irreducibility Conjecture
Canadian journal of mathematics, Tome 70 (2018) no. 6, pp. 1373-1389

Voir la notice de l'article provenant de la source Cambridge University Press

We give a new proof of the Hansen–Mullen irreducibility conjecture. The proof relies on an application of a (seemingly new) sufficient condition for the existence of elements of degree $n$ in the support of functions on finite fields. This connection to irreducible polynomials is made via the least period of the discrete Fourier transform $\left( \text{DFT} \right)$ of functions with values in finite fields. We exploit this relation and prove, in an elementary fashion, that a relevant function related to the $\text{DFT}$ of characteristic elementary symmetric functions (that produce the coefficients of characteristic polynomials) satisfies a simple requirement on the least period. This bears a sharp contrast to previous techniques employed in the literature to tackle the existence of irreducible polynomials with prescribed coefficients.
DOI : 10.4153/CJM-2017-022-1
Mots-clés : 11T06, irreducible polynomial, primitive polynomial, Hansen–Mullen conjecture, symmetric function, q-symmetric, discrete Fourier transform, finite field 
Tuxanidy, Aleksandr; Wang, Qiang. A New Proof of the Hansen—Mullen Irreducibility Conjecture. Canadian journal of mathematics, Tome 70 (2018) no. 6, pp. 1373-1389. doi: 10.4153/CJM-2017-022-1
@article{10_4153_CJM_2017_022_1,
     author = {Tuxanidy, Aleksandr and Wang, Qiang},
     title = {A {New} {Proof} of the {Hansen{\textemdash}Mullen} {Irreducibility} {Conjecture}},
     journal = {Canadian journal of mathematics},
     pages = {1373--1389},
     year = {2018},
     volume = {70},
     number = {6},
     doi = {10.4153/CJM-2017-022-1},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-022-1/}
}
TY  - JOUR
AU  - Tuxanidy, Aleksandr
AU  - Wang, Qiang
TI  - A New Proof of the Hansen—Mullen Irreducibility Conjecture
JO  - Canadian journal of mathematics
PY  - 2018
SP  - 1373
EP  - 1389
VL  - 70
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-022-1/
DO  - 10.4153/CJM-2017-022-1
ID  - 10_4153_CJM_2017_022_1
ER  - 
%0 Journal Article
%A Tuxanidy, Aleksandr
%A Wang, Qiang
%T A New Proof of the Hansen—Mullen Irreducibility Conjecture
%J Canadian journal of mathematics
%D 2018
%P 1373-1389
%V 70
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-022-1/
%R 10.4153/CJM-2017-022-1
%F 10_4153_CJM_2017_022_1

[1] [1] Aigner, M. and Ziegler, G. M., Proofs from the book. 4th éd., Springer-Verlag, Berlin, 2010. Google Scholar

[2] [2] Barvinok, A., Matrices with prescribed row and column sums. Linear Algebra Appl. 436 (2012), no. 4, 820–844. http://dx.doi.Org/10.1016/j.laa.2O10.11.019 Google Scholar

[3] [3] Bourgain, J., Prescribing the binary digits of primes, II. Israel J. Math. 206 (2015), no. 1, 165-182. http://dx.doi.org/10.1007/s11856-014-1129-5 Google Scholar

[4] [4] Canteaut, A. and Videau, M., Symmetric boolean functions. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers 51 (2005), no. 8, 2791–2811. http://dx.doi.org/10.1109/TIT.2005.851743 Google Scholar

[5] [5] Carlitz, L., A theorem of Dickson on irreducible polynomials. Proc. Amer. Math. Soc. 3 (1952), 693–700. http://dx.doi.org/10.1090/S0002-9939-1952-0049940-6 Google Scholar

[6] [6] Castro, F. N. and Medina, L. A., Linear recurrences and asymptotic behaviour of exponential sums of symmetric boolean functions. Electr. J. Comb. 18 (2011), no. 2, paper #P9. Google Scholar

[7] [7] Cohen, S. D., Primitive polynomials over small fields. In: Finite fields and applications. Lecture Notes in Comput. Sci., 2948. Springer, Berlin, 2004, pp. 197–214. Google Scholar

[8] [8] Cohen, S. D., Primitive polynomials with a prescribed coefficient. Finite Fields Appl. 12 (2006), no. 3, 425–491. http://dx.doi.Org/10.1016/j.ffa.2005.08.001 Google Scholar

[9] [9] Cohen, S. D. and Presern, M., Primitive polynomials with prescribed second coefficient. Glasgow Math. J. 48 (2006), 281–307. http://dx.doi.org/10.1017/S0017089506003077 Google Scholar

[10] [10] Cohen, S. D. and Presern, M., The Hansen-Mullen primitivity conjecture: completion of proof. In: Number theory and polynomials. London Math. Soc. Lecture Note Ser., 352. Cambridge University Press, Cambridge, 2008, pp. 89–120. Google Scholar

[11] [11] Dorsey, T. and Hales, A. W., Irreducible coefficient relations. Sequences and their applications-SETA. 2012, Lecture Notes in Comput. Sci., 7280. Springer, Heidelberg, 2012 , pp. 117–125. Google Scholar

[12] [12] Fan, S. Q. and Han, W. B., p-Adic formal series and primitive polynomials over finite fields. Proc. Amer. Math. Soc. 132 (2004), 15–31. http://dx.doi.org/10.1090/S0002-9939-03-07040-0 Google Scholar

[13] [13] Fitzgerald, R. W. and Yucas, J. L., Irreducible polynomials over GF(2) with three prescribed coefficients. Finite Fields Appl. 9 (2003), 286–299. http://dx.doi.Org/10.1016/S1071-5797(03)00005-4 Google Scholar

[14] [14] Garefalakis, T., Irreducible polynomials with consecutive zero coefficients. Finite Fields Appl. 14 (2008), no. 1, 201–208. http://dx.doi.Org/10.1016/j.ffa.2006.11.002 Google Scholar

[15] [15] Ha, J., Irreducible polynomials with several prescribed coefficients. Finite Fields Appl. 40 (2016), 10–25. http://dx.doi.0rg/IO.IOI6/j.ffa.2016.O2.OO6 Google Scholar

[16] [16] Ham, K. H. and Mullen, G. L., Distribution of irreducible polynomials of small degrees over finite fields.Math. Comp. 67 (1998), no. 221, 337–341. http://dx.doi.org/10.1090/S0025-5718-98-00904-1 Google Scholar

[17] [17] Han, W. B., On Cohen's problem. Chinacrypt ‘96, Academic Press (China) (1996) 231-235 (Chinese). Google Scholar

[18] [18] Hansen, T. and Mullen, G. L., Primitive polynomials over finite fields. Math. Comp. 59 (1992), 639–643. http://dx.doi.org/10.1090/S0025-5718-1992-1134730-7 Google Scholar

[19] [19] Koç, Ç. K., Open problems in mathematics and computational science. Springer International Publishing, 2014. Google Scholar

[20] [20] Kononen, K., Moisio, M., Rinta-aho, M., and Vâânânen, K., Irreducible polynomials with prescribed trace and restricted norm. JP J. Algebra Number Theory Appl. 11 (2009), 223–248. Google Scholar

[21] [21] van Lint, J. H. and Wilson, R. M., A course in combinatorics. 2nd éd., Cambridge University Press, Cambridge, 2001. Google Scholar

[22] [22] Koma, B. Omidi, Panario, D., and Wang, Q., The number of irreducible polynomials of degree n over ¥ with given trace and constant terms. Discrete Math. 310 (2010), 1282–1292. http://dx.doi.Org/10.1016/j.disc.2009.12.006 Google Scholar

[23] [23] Panario, D. and Tzanakis, G., A generalization of the Hansen-Mullen conjecture on irreducible polynomials over finite fields. Finite Fields Appl. 18 (2012), no. 2, 303–315. http://dx.doi.Org/10.1016/j.ffa.2O11.09.003 Google Scholar

[24] [24] Tuxanidy, A. and Wang, Q., On the number of N -free elements with prescribed trace. J. Number Theory 160 (2016), 536–565. http://dx.doi.Org/10.1016/j.jnt.2015.09.008 Google Scholar

[25] [25] Pollack, P., Irreducible polynomials with several prescribed coefficients. Finite Fields Appl. 22 (2013), 70–78. http://dx.doi.Org/10.1016/j.ffa.2013.03.001 Google Scholar

[26] [26] Ren, D.-B., On the coefficients of primitive polynomials over finite fields. Sichuan Daxue Xuebao 38 (2001), 33–36. Google Scholar

[27] [27] Shparlinski, I. E., On primitive polynomials. Prob. Peredachi Inform. 23 (1988), 100–103 (Russian). Google Scholar

[28] [28] Tzanakis, G., On the existence of irreducible polynomials with prescribed coefficients over finite fields. Master's thesis, Carleton University, 2010. //www.math.carleton.ca/∼gtzanaki/mscthesis.pdf Google Scholar

[29] [29] Wan, D., Generators and irreducible polynomials over finite fields. Math. Comp. 66 (1997), no. 219, 1195–1212. http://dx.doi.org/10.1090/S0025-5718-97-00835-1 Google Scholar

Cité par Sources :