Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


An analog of the prime number theorem for finite fields via truncated polylogarithm expansions

Authors: Niko Rebenich, T. Aaron Gulliver, Stephen Neville and Ulrich Speidel
Journal: Math. Comp. 87 (2018), 855-877
MSC (2010): Primary 05A16, 11T06; Secondary 11G55, 11M35, 11Y35, 40A05
Published electronically: May 5, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An exponentially accurate asymptotic expansion of the truncated polylogarithm function is derived that leads to an asymptotic formula for enumerating monic irreducible polynomials over finite fields. This formula is analogous to the asymptotic expansion formula of the classical prime counting function. Results are presented which show that it is more accurate than previous results in the literature while requiring very little computational effort. Asymptotic expansions of the Lerch transcendent, Eulerian polynomials, and polylogarithms of negative integer order are also given. The accuracy of the proposed approach is verified via numerical results.

References [Enhancements On Off] (What's this?)

  • [1] Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York-Heidelberg, 1976. Undergraduate Texts in Mathematics. MR 0434929
  • [2] Carl M. Bender and Steven A. Orszag, Advanced Mathematical Methods for Scientists and Engineers, McGraw-Hill Book Co., New York, 1978. International Series in Pure and Applied Mathematics. MR 538168
  • [3] Elwyn R. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
  • [4] John P. Boyd, The devil's invention: asymptotic, superasymptotic and hyperasymptotic series, Acta Appl. Math. 56 (1999), no. 1, 1-98. MR 1698036,
  • [5] Daniel Bump, Algebraic Geometry, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. MR 1669884
  • [6] L. Carlitz, D. C. Kurtz, R. Scoville, and O. P. Stackelberg, Asymptotic properties of Eulerian numbers, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 23 (1972), 47-54. MR 0309856
  • [7] L. Carlitz, D. P. Roselle, and R. A. Scoville, Permutations and sequences with repetitions by number of increases, J. Combinatorial Theory 1 (1966), 350-374. MR 0200178
  • [8] Charalambos A. Charalambides, Enumerative Combinatorics, CRC Press Series on Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, FL, 2002. MR 1937238
  • [9] M. Aslam Chaudhry and Syed M. Zubair, On a Class of Incomplete Gamma Functions with Applications, Chapman & Hall/CRC, Boca Raton, FL, 2002. MR 1887130
  • [10] Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. MR 0460128
  • [11] A. Erdélyi, W. Magnus, F. Oberhettinger and F. G. Tricomi, Higher Transcendental Functions, Vol. 1. New York, NY: McGraw-Hill, 1953.
  • [12] Chelo Ferreira and José L. López, Asymptotic expansions of the Hurwitz-Lerch zeta function, J. Math. Anal. Appl. 298 (2004), no. 1, 210-224. MR 2086542,
  • [13] Dominique Foata, Eulerian polynomials: from Euler's time to the present, The Legacy of Alladi Ramakrishnan in the Mathematical Sciences, Springer, New York, 2010, pp. 253-273. MR 2744266,
  • [14] Theodore W. Gamelin, Complex Analysis, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 2001. MR 1830078
  • [15] Eldar Giladi and Joseph B. Keller, Eulerian number asymptotics, Proc. Roy. Soc. London Ser. A 445 (1994), no. 1924, 291-303. MR 1276912,
  • [16] Solomon W. Golomb, Obtaining specified irreducible polynomials over finite fields, SIAM J. Algebraic Discrete Methods 1 (1980), no. 4, 411-418. MR 593851,
  • [17] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1397498
  • [18] Henryk Iwaniec and Emmanuel Kowalski, Analytic Number Theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214
  • [19] A. Jonquière, Note sur la série $ \sum _{n=1}^{\infty } \frac {x^n}{n^s}$, Bull. Soc. Math. France 17 (1889), 142-152 (French). MR 1504064
  • [20] Helge von Koch, Sur la distribution des nombres premiers, Acta Math. 24 (1901), no. 1, 159-182 (French). MR 1554926,
  • [21] Margret Kruse and Henning Stichtenoth, Ein Analogon zum Primzahlsatz für algebraische Funktionenkörper, Manuscripta Math. 69 (1990), no. 3, 219-221. MR 1078353,
  • [22] Jeffrey C. Lagarias and Wen-Ching Winnie Li, The Lerch zeta function III. Polylogarithms and special values, Res. Math. Sci. 3 (2016), Paper No. 2, 54. MR 3465529,
  • [23] N. N. Lebedev, Special Functions and Their Applications, Revised English edition. Translated and edited by Richard A. Silverman, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1965. MR 0174795
  • [24] Rudolf Lidl and Harald Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, 1986. MR 860948
  • [25] M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. MR 675953
  • [26] Alexander Lubotzky and Dan Segal, Subgroup Growth, Progress in Mathematics, vol. 212, Birkhäuser Verlag, Basel, 2003. MR 1978431
  • [27] N. Metropolis and Gian-Carlo Rota, Witt vectors and the algebra of necklaces, Adv. in Math. 50 (1983), no. 2, 95-125. MR 723197,
  • [28] F. W. J. Olver, Asymptotics and Special Functions, Computer Science and Applied Mathematics, Academic Press, New York-London, 1974. MR 0435697
  • [29] R. B. Paris, Hadamard Expansions and Hyperasymptotic Evaluation: An Extension of the Method of Steepest Descents, Encyclopedia of Mathematics and its Applications, vol. 141, Cambridge University Press, Cambridge, 2011. MR 2796952
  • [30] T. Kyle Petersen, Eulerian Numbers, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser/Springer, New York, 2015. MR 3408615
  • [31] Paul Pollack, Revisiting Gauss's analogue of the prime number theorem for polynomials over a finite field, Finite Fields Appl. 16 (2010), no. 4, 290-299. MR 2646339,
  • [32] Michael Rosen, Number Theory in Function Fields, Graduate Texts in Mathematics, vol. 210, Springer-Verlag, New York, 2002. MR 1876657
  • [33] H. M. Srivastava and Junesang Choi, Series Associated with the Zeta and Related Functions, Kluwer Academic Publishers, Dordrecht, 2001. MR 1849375
  • [34] H. M. Srivastava and Junesang Choi, Zeta and $ q$-Zeta Functions and Associated Series and Integrals, Elsevier, Inc., Amsterdam, 2012. MR 3294573
  • [35] Henning Stichtenoth, Algebraic Function Fields and Codes, 2nd ed., Graduate Texts in Mathematics, vol. 254, Springer-Verlag, Berlin, 2009. MR 2464941
  • [36] S. Tanny, A probabilistic interpretation of Eulerian numbers, Duke Math. J. 40 (1973), 717-722. MR 0340045
  • [37] C. Truesdell, On a function which occurs in the theory of the structure of polymers, Ann. of Math. (2) 46 (1945), 144-157. MR 0011344
  • [38] F. J. Ursell, Integrals with a large parameter. A strong form of Watson's lemma, in Ship Hydrodynamics, Water Waves and Asymptotics, vol. 2, pp. 848-852, Singapore: World Sci. Pub., 1991.
  • [39] Qichun Wang and Haibin Kan, Counting irreducible polynomials over finite fields, Czechoslovak Math. J. 60(135) (2010), no. 3, 881-886. MR 2672421,
  • [40] G. N. Watson, The harmonic functions associated with the parabolic cylinder, Proc. London Math. Soc. S2-17 (1918), no. 1, 116. MR 1575566,
  • [41] H. S. Wilf, Generatingfunctionology. San Diego, CA: Acad. Press Inc. 1990.
  • [42] W. Wirtinger, Über eine besondere Dirchletsche Reihe, J. Reine Angew. Math. 129 (1905), 214-219 (German). MR 1580667,

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05A16, 11T06, 11G55, 11M35, 11Y35, 40A05

Retrieve articles in all journals with MSC (2010): 05A16, 11T06, 11G55, 11M35, 11Y35, 40A05

Additional Information

Niko Rebenich
Affiliation: Department of Electrical and Computer Engineering, University of Victoria, P.O. Box 1700, STN CSC Victoria, British Columbia V8W 2Y2, Canada

T. Aaron Gulliver
Affiliation: Department of Electrical and Computer Engineering, University of Victoria, P.O. Box 1700, STN CSC Victoria, British Columbia V8W 2Y2, Canada

Stephen Neville
Affiliation: Department of Electrical and Computer Engineering, University of Victoria, P.O. Box 1700, STN CSC Victoria, British Columbia V8W 2Y2, Canada

Ulrich Speidel
Affiliation: Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand

Keywords: Lerch transcendent, polylogarithm, Eulerian polynomials, divergent series, superasymptotic expansion, prime polynomial counting function, irreducible polynomials, aperiodic necklaces.
Received by editor(s): March 31, 2016
Received by editor(s) in revised form: June 3, 2016, and September 7, 2016
Published electronically: May 5, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society