An analog of the prime number theorem for finite fields via truncated polylogarithm expansions
HTML articles powered by AMS MathViewer
- by Niko Rebenich, T. Aaron Gulliver, Stephen Neville and Ulrich Speidel PDF
- Math. Comp. 87 (2018), 855-877 Request permission
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
- Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR 0434929
- Carl M. Bender and Steven A. Orszag, Advanced mathematical methods for scientists and engineers, International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York, 1978. MR 538168
- Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
- John P. Boyd, The devil’s invention: asymptotic, superasymptotic and hyperasymptotic series, Acta Appl. Math. 56 (1999), no. 1, 1–98. MR 1698036, DOI 10.1023/A:1006145903624
- Daniel Bump, Algebraic geometry, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. MR 1669884, DOI 10.1142/3873
- 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 309856, DOI 10.1007/BF00536689
- 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 200178
- Charalambos A. Charalambides, Enumerative combinatorics, CRC Press Series on Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, FL, 2002. MR 1937238
- 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
- Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128
- A. Erdélyi, W. Magnus, F. Oberhettinger and F. G. Tricomi, Higher Transcendental Functions, Vol. 1. New York, NY: McGraw-Hill, 1953.
- 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, DOI 10.1016/j.jmaa.2004.05.040
- 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, DOI 10.1007/978-1-4419-6263-8_{1}5
- Theodore W. Gamelin, Complex analysis, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 2001. MR 1830078, DOI 10.1007/978-0-387-21607-2
- Eldar Giladi and Joseph B. Keller, Eulerian number asymptotics, Proc. Roy. Soc. London Ser. A 445 (1994), no. 1924, 291–303. MR 1276912, DOI 10.1098/rspa.1994.0062
- Solomon W. Golomb, Obtaining specified irreducible polynomials over finite fields, SIAM J. Algebraic Discrete Methods 1 (1980), no. 4, 411–418. MR 593851, DOI 10.1137/0601047
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
- Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214, DOI 10.1090/coll/053
- 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
- Helge von Koch, Sur la distribution des nombres premiers, Acta Math. 24 (1901), no. 1, 159–182 (French). MR 1554926, DOI 10.1007/BF02403071
- Margret Kruse and Henning Stichtenoth, Ein Analogon zum Primzahlsatz für algebraische Funktionenkörper, Manuscripta Math. 69 (1990), no. 3, 219–221 (German, with English summary). MR 1078353, DOI 10.1007/BF02567920
- 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, DOI 10.1186/s40687-015-0049-2
- N. N. Lebedev, Special functions and their applications, Revised English edition, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1965. Translated and edited by Richard A. Silverman. MR 0174795
- Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, 1986. MR 860948
- M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR 675953
- Alexander Lubotzky and Dan Segal, Subgroup growth, Progress in Mathematics, vol. 212, Birkhäuser Verlag, Basel, 2003. MR 1978431, DOI 10.1007/978-3-0348-8965-0
- N. Metropolis and Gian-Carlo Rota, Witt vectors and the algebra of necklaces, Adv. in Math. 50 (1983), no. 2, 95–125. MR 723197, DOI 10.1016/0001-8708(83)90035-X
- F. W. J. Olver, Asymptotics and special functions, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0435697
- R. B. Paris, Hadamard expansions and hyperasymptotic evaluation, Encyclopedia of Mathematics and its Applications, vol. 141, Cambridge University Press, Cambridge, 2011. An extension of the method of steepest descents. MR 2796952, DOI 10.1017/CBO9780511753626
- T. Kyle Petersen, Eulerian numbers, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser/Springer, New York, 2015. With a foreword by Richard Stanley. MR 3408615, DOI 10.1007/978-1-4939-3091-3
- 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, DOI 10.1016/j.ffa.2010.04.002
- Michael Rosen, Number theory in function fields, Graduate Texts in Mathematics, vol. 210, Springer-Verlag, New York, 2002. MR 1876657, DOI 10.1007/978-1-4757-6046-0
- H. M. Srivastava and Junesang Choi, Series associated with the zeta and related functions, Kluwer Academic Publishers, Dordrecht, 2001. MR 1849375, DOI 10.1007/978-94-015-9672-5
- H. M. Srivastava and Junesang Choi, Zeta and $q$-Zeta functions and associated series and integrals, Elsevier, Inc., Amsterdam, 2012. MR 3294573, DOI 10.1016/B978-0-12-385218-2.00001-3
- Henning Stichtenoth, Algebraic function fields and codes, 2nd ed., Graduate Texts in Mathematics, vol. 254, Springer-Verlag, Berlin, 2009. MR 2464941
- S. Tanny, A probabilistic interpretation of Eulerian numbers, Duke Math. J. 40 (1973), 717–722. MR 340045
- C. Truesdell, On a function which occurs in the theory of the structure of polymers, Ann. of Math. (2) 46 (1945), 144–157. MR 11344, DOI 10.2307/1969153
- 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.
- Qichun Wang and Haibin Kan, Counting irreducible polynomials over finite fields, Czechoslovak Math. J. 60(135) (2010), no. 3, 881–886. MR 2672421, DOI 10.1007/s10587-010-0055-x
- G. N. Watson, The Harmonic Functions Associated with the Parabolic Cylinder, Proc. London Math. Soc. (2) 17 (1918), 116–148. MR 1575566, DOI 10.1112/plms/s2-17.1.116
- H. S. Wilf, Generatingfunctionology. San Diego, CA: Acad. Press Inc. 1990.
- W. Wirtinger, Über eine besondere Dirchletsche Reihe, J. Reine Angew. Math. 129 (1905), 214–219 (German). MR 1580667, DOI 10.1515/crll.1905.129.214
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
- MR Author ID: 1079851
- Email: niko@ece.uvic.ca
- 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
- MR Author ID: 294190
- Email: agullive@ece.uvic.ca
- Stephen Neville
- Affiliation: Department of Electrical and Computer Engineering, University of Victoria, P.O. Box 1700, STN CSC Victoria, British Columbia V8W 2Y2, Canada
- Email: sneville@ece.uvic.ca
- Ulrich Speidel
- Affiliation: Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand
- MR Author ID: 821380
- Email: ulrich@cs.auckland.ac.nz
- 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
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 855-877
- MSC (2010): Primary 05A16, 11T06; Secondary 11G55, 11M35, 11Y35, 40A05
- DOI: https://doi.org/10.1090/mcom/3247
- MathSciNet review: 3739220