Traces of powers of matrices over finite fields
HTML articles powered by AMS MathViewer
- by Ofir Gorodetsky and Brad Rodgers PDF
- Trans. Amer. Math. Soc. 374 (2021), 4579-4638 Request permission
Abstract:
Let $M$ be a random matrix chosen according to Haar measure from the unitary group $\mathrm {U}(n,\mathbb {C})$. Diaconis and Shahshahani proved that the traces of $M,M^2,\ldots ,M^k$ converge in distribution to independent normal variables as $n \to \infty$, and Johansson proved that the rate of convergence is superexponential in $n$.
We prove a finite field analogue of these results. Fixing a prime power $q = p^r$, we choose a matrix $M$ uniformly from the finite unitary group $\mathrm {U}(n,q)\subseteq \mathrm {GL}(n,q^2)$ and show that the traces of $\{ M^i \}_{1 \le i \le k, p \nmid i}$ converge to independent uniform variables in $\mathbb {F}_{q^2}$ as $n \to \infty$. Moreover we show the rate of convergence is exponential in $n^2$. We also consider the closely related problem of the rate at which characteristic polynomial of $M$ equidistributes in ‘short intervals’ of $\mathbb {F}_{q^2}[T]$. Analogous results are also proved for the general linear, special linear, symplectic and orthogonal groups over a finite field. In the two latter families we restrict to odd characteristic.
The proofs depend upon applying techniques from analytic number theory over function fields to formulas due to Fulman and others for the probability that the characteristic polynomial of a random matrix equals a given polynomial.
References
- E. Artin, Geometric algebra, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1988. Reprint of the 1957 original; A Wiley-Interscience Publication. MR 1009557, DOI 10.1002/9781118164518
- Efrat Bank, Lior Bary-Soroker, and Lior Rosenzweig, Prime polynomials in short intervals and in arithmetic progressions, Duke Math. J. 164 (2015), no. 2, 277–295. MR 3306556, DOI 10.1215/00127094-2856728
- Daniel Bump and Persi Diaconis, Toeplitz minors, J. Combin. Theory Ser. A 97 (2002), no. 2, 252–271. MR 1883866, DOI 10.1006/jcta.2001.3214
- Daniel Bump and Alex Gamburd, On the averages of characteristic polynomials from classical groups, Comm. Math. Phys. 265 (2006), no. 1, 227–274. MR 2217304, DOI 10.1007/s00220-006-1503-1
- L. Carlitz, Some theorems on irreducible reciprocal polynomials over a finite field, J. Reine Angew. Math. 227 (1967), 212–220. MR 215815, DOI 10.1515/crll.1967.227.212
- Alina Carmen Cojocaru, Rachel Davis, Alice Silverberg, and Katherine E. Stange, Arithmetic properties of the Frobenius traces defined by a rational abelian variety (with two appendices by J-P. Serre), Int. Math. Res. Not. IMRN 12 (2017), 3557–3602. MR 3693659, DOI 10.1093/imrn/rnw058
- Wouter Castryck, Amanda Folsom, Hendrik Hubrechts, and Andrew V. Sutherland, The probability that the number of points on the Jacobian of a genus 2 curve is prime, Proc. Lond. Math. Soc. (3) 104 (2012), no. 6, 1235–1270. MR 2946086, DOI 10.1112/plms/pdr063
- Gilyoung Cheong and Yifeng Huang, Cohen-Lenstra distributions via random matrices over complete discrete valuation rings with finite residue fields, Preprint arXiv:1812.11728, 2018.
- Nick Chavdarov, The generic irreducibility of the numerator of the zeta function in a family of curves with large monodromy, Duke Math. J. 87 (1997), no. 1, 151–180. MR 1440067, DOI 10.1215/S0012-7094-97-08707-X
- Hi-joon Chae and Dae San Kim, $L$ functions of some exponential sums of finite classical groups, Math. Ann. 326 (2003), no. 3, 479–487. MR 1992273, DOI 10.1007/s00208-003-0431-z
- Hi-joon Chae and Dae San Kim, Identities arising from Gauss sums for finite classical groups, J. Number Theory 128 (2008), no. 7, 2010–2024. MR 2423746, DOI 10.1016/j.jnt.2008.01.001
- H. Cohen and H. W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33–62. MR 756082, DOI 10.1007/BFb0099440
- Keith Conrad, Irreducible values of polynomials: a non-analogy, Number fields and function fields—two parallel worlds, Progr. Math., vol. 239, Birkhäuser Boston, Boston, MA, 2005, pp. 71–85. MR 2176587, DOI 10.1007/0-8176-4447-4_{5}
- Charles W. Curtis and Ken-ichi Shinoda, Unitary Kloosterman sums and the Gelfand-Graev representation of $\textrm {GL}_2$, J. Algebra 216 (1999), no. 2, 431–447. MR 1693005, DOI 10.1006/jabr.1998.7807
- Leonard Eugene Dickson, Linear groups: With an exposition of the Galois field theory, Dover Publications, Inc., New York, 1958. With an introduction by W. Magnus. MR 0104735
- Jean A. Dieudonné, La géométrie des groupes classiques, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 5, Springer-Verlag, Berlin-New York, 1971 (French). Troisième édition. MR 0310083
- Maurice Duits and Kurt Johansson, Powers of large random unitary matrices and Toeplitz determinants, Trans. Amer. Math. Soc. 362 (2010), no. 3, 1169–1187. MR 2563725, DOI 10.1090/S0002-9947-09-04542-5
- Persi Diaconis and Mehrdad Shahshahani, On the eigenvalues of random matrices, J. Appl. Probab. 31A (1994), 49–62. Studies in applied probability. MR 1274717, DOI 10.2307/3214948
- Gove W. Effinger and David R. Hayes, Additive number theory of polynomials over a finite field, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR 1143282
- M. Eichler, Allgemeine Kongruenzklasseneinteilungen der Ideale einfacher Algebren über algebraischen Zahlkörper und ihre $L$-Reihen, J. Reine Angew. Math. 179 (1938), 227–251 (German). MR 1581595, DOI 10.1515/crll.1938.179.227
- Jason Fulman and Robert Guralnick, Conjugacy class properties of the extension of $\textrm {GL}(n,q)$ generated by the inverse transpose involution, J. Algebra 275 (2004), no. 1, 356–396. MR 2047453, DOI 10.1016/j.jalgebra.2003.07.004
- Jason Fulman and Dennis Stanton, On the distribution of the number of fixed vectors for the finite classical groups, Ann. Comb. 20 (2016), no. 4, 755–773. MR 3572385, DOI 10.1007/s00026-016-0336-7
- Jason Fulman, Jan Saxl, and Pham Huu Tiep, Cycle indices for finite orthogonal groups of even characteristic, Trans. Amer. Math. Soc. 364 (2012), no. 5, 2539–2566. MR 2888219, DOI 10.1090/S0002-9947-2012-05406-7
- Jason Fulman, Cycle indices for the finite classical groups, J. Group Theory 2 (1999), no. 3, 251–289. MR 1696313, DOI 10.1515/jgth.1999.017
- Eduardo Friedman and Lawrence C. Washington, On the distribution of divisor class groups of curves over a finite field, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 227–239. MR 1024565
- Murray Gerstenhaber, On the number of nilpotent matrices with coefficients in a finite field, Illinois J. Math. 5 (1961), 330–333. MR 130875
- Ofir Gorodetsky, Mean values of arithmetic functions in short intervals and in arithmetic progressions in the large-degree limit, Mathematika 66 (2020), no. 2, 373–394. MR 4130329, DOI 10.1112/mtk.12032
- George Gasper and Mizan Rahman, Basic hypergeometric series, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 96, Cambridge University Press, Cambridge, 2004. With a foreword by Richard Askey. MR 2128719, DOI 10.1017/CBO9780511526251
- Ofir Gorodetsky and Will Sawin, Correlation of arithmetic functions over $\Bbb {F}_q[T]$, Math. Ann. 376 (2020), no. 3-4, 1059–1106. MR 4081110, DOI 10.1007/s00208-019-01929-x
- David R. Hayes, The distribution of irreducibles in $\textrm {GF}[q,\,x]$, Trans. Amer. Math. Soc. 117 (1965), 101–127. MR 169838, DOI 10.1090/S0002-9947-1965-0169838-6
- Kurt Johansson and Gaultier Lambert, Multivariate normal approximation for traces of random unitary matrices, 2020.
- Kurt Johansson, On random matrices from the compact classical groups, Ann. of Math. (2) 145 (1997), no. 3, 519–545. MR 1454702, DOI 10.2307/2951843
- Dae San Kim, Gauss sums for general and special linear groups over a finite field, Arch. Math. (Basel) 69 (1997), no. 4, 297–304. MR 1466823, DOI 10.1007/s000130050124
- Dae San Kim, Gauss sums for $\textrm {O}^-(2n,q)$, Acta Arith. 80 (1997), no. 4, 343–365. MR 1450928, DOI 10.4064/aa-80-4-343-365
- Dae San Kim, Gauss sums for $\textrm {U}(2n+1,q^2)$, J. Korean Math. Soc. 34 (1997), no. 4, 871–894. MR 1485957
- Dae San Kim, Gauss sums for $\textrm {O}(2n+1,q)$, Finite Fields Appl. 4 (1998), no. 1, 62–86. MR 1612080, DOI 10.1006/ffta.1997.0202
- Dae San Kim, Gauss sums for symplectic groups over a finite field, Monatsh. Math. 126 (1998), no. 1, 55–71. MR 1633263, DOI 10.1007/BF01312455
- Dae San Kim, Gauss sums for $U(2n,q^2)$, Glasgow Math. J. 40 (1998), no. 1, 79–95. MR 1612161, DOI 10.1017/S0017089500032377
- Dae San Kim and In-Sok Lee, Gauss sums for $\textrm {O}^{+}(2n,q)$, Acta Arith. 78 (1996), no. 1, 75–89. MR 1425001, DOI 10.4064/aa-78-1-75-89
- Dae San Kim and Young Ho Park, Gauss sums for orthogonal groups over a finite field of characteristic two, Acta Arith. 82 (1997), no. 4, 331–357. MR 1483687, DOI 10.4064/aa-82-4-331-357
- Jonathan P. Keating and Zeév Rudnick, The variance of the number of prime polynomials in short intervals and in residue classes, Int. Math. Res. Not. IMRN 1 (2014), 259–288. MR 3158533, DOI 10.1093/imrn/rns220
- Erich Lamprecht, Struktur und Relationen allgemeiner Gausscher Summen in endlichen Ringen. I, II, J. Reine Angew. Math. 197 (1957), 1–26, 27–48 (German). MR 86801, DOI 10.1515/crll.1957.197.1
- Wen-Ch’ing Winnie Li, Character sums and abelian Ramanujan graphs, J. Number Theory 41 (1992), no. 2, 199–217. With an appendix by Ke Qin Feng and the author. MR 1164798, DOI 10.1016/0022-314X(92)90120-E
- Wen-Ching Winnie Li, Character sums over norm groups, Finite Fields Appl. 12 (2006), no. 1, 1–15. MR 2190183, DOI 10.1016/j.ffa.2004.06.006
- Corentin Perret-Gentil, Exponential sums over finite fields and the large sieve, Int. Math. Res. Not. IMRN 20 (2020), 7139–7174. MR 4172680, DOI 10.1093/imrn/rny202
- Corentin Perret-Gentil, Distribution questions for trace functions with values in cyclotomic integers and their reductions, Trans. Amer. Math. Soc. 371 (2019), no. 7, 4585–4629. MR 3934462, DOI 10.1090/tran/7333
- E. M. Rains, High powers of random elements of compact Lie groups, Probab. Theory Related Fields 107 (1997), no. 2, 219–241. MR 1431220, DOI 10.1007/s004400050084
- Irving Reiner, On the number of matrices with given characteristic polynomial, Illinois J. Math. 5 (1961), 324–329. MR 139621
- Georges Rhin, Répartition modulo $1$ dans un corps de séries formelles sur un corps fini, Dissertationes Math. (Rozprawy Mat.) 95 (1972), 75 (French). MR 349612
- A. Rudvalis and K. Shinoda, An enumeration in finite classical groups, U-Mass Amherst Department of Mathematics Technical Report, Amherst, MA, 1988.
- Richard Stong, Some asymptotic results on finite vector spaces, Adv. in Appl. Math. 9 (1988), no. 2, 167–199. MR 937520, DOI 10.1016/0196-8858(88)90012-7
- Donald E. Taylor, The geometry of the classical groups, Sigma Series in Pure Mathematics, vol. 9, Heldermann Verlag, Berlin, 1992. MR 1189139
- G. E. Wall, On the conjugacy classes in the unitary, symplectic and orthogonal groups, J. Austral. Math. Soc. 3 (1963), 1–62. MR 0150210
- André Weil, Basic number theory, 3rd ed., Die Grundlehren der mathematischen Wissenschaften, Band 144, Springer-Verlag, New York-Berlin, 1974. MR 0427267
- K. Wieand, Eigenvalue distributions of random unitary matrices, Probab. Theory Related Fields 123 (2002), no. 2, 202–224. MR 1900322, DOI 10.1007/s004400100186
- Melanie Matchett Wood, Random integral matrices and the Cohen-Lenstra heuristics, Amer. J. Math. 141 (2019), no. 2, 383–398. MR 3928040, DOI 10.1353/ajm.2019.0008
Additional Information
- Ofir Gorodetsky
- Affiliation: Mathematical Institute, University of Oxford, Oxford, OX2 6GG, United Kingdom
- MR Author ID: 1234845
- Email: ofir.goro@gmail.com
- Brad Rodgers
- Affiliation: Department of Mathematics and Statistics, Queen’s University, Kingston, Ontario K7L 3N6, Canada
- MR Author ID: 1049692
- Email: brad.rodgers@queensu.ca
- Received by editor(s): September 22, 2019
- Published electronically: April 28, 2021
- Additional Notes: The first author was supported by the European Research Council under the European Union’s Seventh Frame-work Programme (FP7/2007-2013)/ERC grant agreements n$^{\text {o}}$ 320755 and 786758. The second author was partly supported by the US NSF grant DMS-1701577 and an NSERC grant.
- © Copyright 2021 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 374 (2021), 4579-4638
- MSC (2020): Primary 60B15, 60B20, 20G40, 11T55
- DOI: https://doi.org/10.1090/tran/8337
- MathSciNet review: 4273172