×

On the degrees of polynomial divisors over finite fields. (English) Zbl 1371.12002

Summary: We show that the proportion of polynomials of degree \(n\) over the finite field with \(q\) elements, which have a divisor of every degree below \(n\), is given by \(c_qn^{-1} + O(n^{-2})\). More generally, we give an asymptotic formula for the proportion of polynomials, whose set of degrees of divisors has no gaps of size greater than \(m\). To that end, we first derive an improved estimate for the proportion of polynomials of degree \(n\), all of whose non-constant divisors have degree greater than \(m\). In the limit as \(q\to\infty\), these results coincide with corresponding estimates related to the cycle structure of permutations.

MSC:

12E05 Polynomials in general fields (irreducibility, etc.)
11T06 Polynomials over finite fields
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] [1]R.Arratia, A. D.Barbour and S.TavaréRandom combinatorial structures and prime factorizations. Not. Amer. Math. Soc.44 (1997), 903-910. · Zbl 0915.60011
[2] [2]A. Y.Cheer and D. A.GoldstonA differential delay equation arising from the sieve of Eratosthenes. Math. Comp.55 (1990), 129-141.10.1090/S0025-5718-1990-1023043-8 · Zbl 0702.11059
[3] [3]J.Dixmier and J.-L.Nicolas. Partitions without small parts. Number Theory, Vol. I (Budapest, 1987), 9-33, Colloq. Math. Soc. János Bolyai, 51 (North-Holland, Amsterdam, 1990). · Zbl 0707.11072
[4] [4]P.Erdős and M.Szalay. On some problems of J. Dénes and P. Turán, Stud. Pure Math. (Birkhäuser, Basel, 1983), 187-212.10.1007/978-3-0348-5438-2_18 · Zbl 0523.10029
[5] [5]P.Flajolet and R.SedgewickAnalytic Combinatorics (Cambridge University Press, 2009).10.1017/CBO9780511801655 · Zbl 1165.05001
[6] [6]S.Gao and D.PanarioTests and constructions of irreducible polynomials over finite fields. Foundations of Computational Mathematics (Rio de Janeiro, 1997), (Springer, Berlin, 1997), 346-361.10.1007/978-3-642-60539-0_27 · Zbl 0882.11065
[7] [7]A.Granville The anatomy of integers and permutations, http://www.dms.umontreal.ca/ andrew/PDF/Anatomy.pdf · Zbl 1423.00004
[8] [8]R.Lidl and H.NiederreiterFinite Fields. Encyclopedia Math. Appli. Vol. 20 (Cambridge University Press, 1997).
[9] [9]E.ManstavičiusOn permutations missing short cycles. Lietuvos matem. rink., spec. issue, 42 (2002), 1-6.
[10] [10]E.Manstavičius and R.Petuchovas. Local probabilities and total variation distance for random permutations, to appear in Ramanujan J. · Zbl 1373.05014
[11] [11]D.Panario and B.RichmondAnalysis of Ben-Or’s polynomial irreducibility test. Random Structures Algorithms13 (1998), 439-456.10.1002/(SICI)1098-2418(199810/12)13:3/4<439::AID-RSA13>3.0.CO;2-U · Zbl 0960.11052
[12] [12]P.Pollack and L.ThompsonOn the degrees of divisors of T^n - 1. New York J. Math.19 (2013), 91-116.3028137 · Zbl 1282.11125
[13] [13]C.Pomerance, L.Thompson and A.Weingartner On integers n for which X^n - 1 has a divisor of every degree, arXiv:1511:03357. · Zbl 1364.11143
[14] [14]Z.Rudnick Some problems in analytic number theory for polynomials over a finite field, arXiv:1501.01769. · Zbl 1373.11082
[15] [15]E.SaiasEntiers à diviseurs denses 1. J. Number Theory62 (1997), 163-191.10.1006/jnth.1997.2057 · Zbl 0872.11039 · doi:10.1006/jnth.1997.2057
[16] [16]G.TenenbaumSur un problème de crible et ses applications. Ann. Sci. École Norm. Sup.(4)19 (1986), 1-30. · Zbl 0599.10037
[17] [17]G.TenenbaumSur un problème de crible et ses applications, 2. Corrigendum et étude du graphe divisoriel. Ann. Sci. École Norm. Sup.(4)28 (1995), 115-127. · Zbl 0852.11048
[18] [18]G.TenenbaumIntroduction to Analytic and Probabilistic Number Theory. Camb. Stud. Adv. Math., Vol. 46 (Cambridge University Press, 1995). · Zbl 0788.11001
[19] [19]L.ThompsonPolynomials with divisors of every degree. J. Number Theory132 (2012), 1038-1053.10.1016/j.jnt.2011.10.0052890525 · Zbl 1287.11113 · doi:10.1016/j.jnt.2011.10.005
[20] [20]L.ThompsonOn the divisors of x^n−1 in F_p[x]. Int. J. Number Theory9 (2013), 421-430.10.1142/S1793042112501412 · Zbl 1271.11094 · doi:10.1142/S1793042112501412
[21] [21]R.WarlimontArithmetical semigroups II: sieving by large and small prime elements. Sets of multiples. Manuscripta Math.71 (1991), 197-221.10.1007/BF025684021101269 · Zbl 0735.11046 · doi:10.1007/BF02568402
[22] [22]A.WeingartnerIntegers with dense divisors 3. J. Number Theory142 (2014), 211-222.10.1016/j.jnt.2014.02.0213208399 · Zbl 1295.11104 · doi:10.1016/j.jnt.2014.02.021
[23] [23]A.WeingartnerPractical numbers and the distribution of divisors. Q. J. Math.66 (2015), 743-758.10.1093/qmath/hav0063356847 · Zbl 1338.11087 · doi:10.1093/qmath/hav006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.