Let be the group of uni-uppertriangular matrices with entries in , the integers mod . We show that the simple random walk converges to the uniform distribution in order steps. The argument uses Fourier analysis and is surprisingly challenging. It introduces novel techniques for bounding the spectrum which are useful for a variety of walks on a variety of groups.
Soit le groupe des matrices supérieures ne contenant que des 1 sur la diagonale et dont les entrées appartiennent à , l’anneau des entiers modulo . On montre que la marche aléatoire simple y converge vers la probabilité uniforme en un temps d’ordre . La preuve utilise l’analyse de Fourier et, curieusement, n’est pas immédiate. De nouvelles techniques sont introduites pour borner le spectre, qui sont utiles pour d’autres exemples de marches aléatoires sur des groupes.
Daniel Bump 1; Persi Diaconis 2; Angela Hicks 2; Laurent Miclo 3; Harold Widom 4
@article{AFST_2017_6_26_2_263_0, author = {Daniel Bump and Persi Diaconis and Angela Hicks and Laurent Miclo and Harold Widom}, title = {An {Exercise(?)} in {Fourier} {Analysis} on the {Heisenberg} {Group}}, journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques}, pages = {263--288}, publisher = {Universit\'e Paul Sabatier, Toulouse}, volume = {Ser. 6, 26}, number = {2}, year = {2017}, doi = {10.5802/afst.1533}, language = {en}, url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1533/} }
TY - JOUR AU - Daniel Bump AU - Persi Diaconis AU - Angela Hicks AU - Laurent Miclo AU - Harold Widom TI - An Exercise(?) in Fourier Analysis on the Heisenberg Group JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2017 SP - 263 EP - 288 VL - 26 IS - 2 PB - Université Paul Sabatier, Toulouse UR - https://afst.centre-mersenne.org/articles/10.5802/afst.1533/ DO - 10.5802/afst.1533 LA - en ID - AFST_2017_6_26_2_263_0 ER -
%0 Journal Article %A Daniel Bump %A Persi Diaconis %A Angela Hicks %A Laurent Miclo %A Harold Widom %T An Exercise(?) in Fourier Analysis on the Heisenberg Group %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2017 %P 263-288 %V 26 %N 2 %I Université Paul Sabatier, Toulouse %U https://afst.centre-mersenne.org/articles/10.5802/afst.1533/ %R 10.5802/afst.1533 %G en %F AFST_2017_6_26_2_263_0
Daniel Bump; Persi Diaconis; Angela Hicks; Laurent Miclo; Harold Widom. An Exercise(?) in Fourier Analysis on the Heisenberg Group. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 26 (2017) no. 2, pp. 263-288. doi : 10.5802/afst.1533. https://afst.centre-mersenne.org/articles/10.5802/afst.1533/
[1] Random walks on discrete groups of polynomial volume growth, Ann. Probab., Volume 30 (2002) no. 2, pp. 723-801 | DOI
[2] A rule of thumb for riffle shuffling, Ann. Appl. Probab., Volume 21 (2011) no. 3, pp. 843-875 | DOI
[3] Is computing with the finite Fourier transform pure or applied mathematics?, Bull. Am. Math. Soc., Volume 1 (1979), pp. 847-897 | DOI
[4] The Ten Martini Problem, Ann. Math., Volume 170 (2009) no. 1, pp. 303-342 | DOI
[5] On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper’s operator, J. Geom. Phys., Volume 21 (1997) no. 4, pp. 337-356 | DOI
[6] Norm estimates of almost Mathieu operators, J. Funct. Anal., Volume 220 (2005) no. 1, pp. 76-96 | DOI
[7] Random Walks on Lie Groups, Yale University (USA) (2004) (Ph. D. Thesis)
[8] Local limit theorems and equidistribution of random walks on the Heisenberg group, Geom. Funct. Anal., Volume 15 (2005) no. 1, pp. 35-82 | DOI
[9] Automorphic forms and representations, Cambridge Studies in Advanced Mathematics, 55, Cambridge University Press, 1997, xiv+574 pages
[10] Characters and super characters for step two nilpotent groups with applications to random walks (to appear)
[11] Useful bounds on the extreme eigenvalues and vectors of matrices for Harper’s operators (2016) (to appear in Operator Theory: Advances and Applications)
[12] Quantum mechanical commutation relations and theta functions, Algebraic Groups and Discontinuous Subgroups (Proc. Sympos. Pure Math.), Volume 9, American Mathematical Society, 1966, pp. 361-383 (Boulder, Colo., 1965)
[13] Group representations in probability and statistics, IMS Lecture Notes-Monograph Series, 11, Institute of Mathematical Statistics, 1988, vi+198 pages
[14] Threads through group theory, Character theory of finite groups. Conference in honor of I. Martin Isaacs, València, Spain, June 3–5, 2009 (Contemporary Mathematics), Volume 524, American Mathematical Society, 2010, pp. 33-47
[15] Random walk on unipotent matrix groups (to appear)
[16] On Quantitative Convergence to Quasi-Stationarity, Ann. Fac. Sci. Toulouse, Math., Volume 24 (2015) no. 4, pp. 973-1016 | DOI
[17] Comparison theorems for reversible Markov chains, Ann. Appl. Probab., Volume 3 (1993) no. 3, pp. 696-730 | DOI
[18] Moderate growth and random walk on finite groups, Geom. Funct. Anal., Volume 4 (1994) no. 1, pp. 1-36 | DOI
[19] An application of Harnack inequalities to random walk on nilpotent quotients, J. Fourier Anal. Appl., Volume Special Issue (1995), pp. 189-207 Proceedings of the Conference in Honor of Jean-Pierre Kahane (Orsay, 1993)
[20] Nash inequalities for finite Markov chains, J. Theor. Probab., Volume 9 (1996) no. 2, pp. 459-510 | DOI
[21] Eigenvectors and functions of the discrete Fourier transform, IEEE Trans. Acoust. Speech Signal Process., Volume 30 (1982), pp. 25-31 | DOI
[22] A note on representations of the finite Heisenberg group and sums of greatest common divisors, Discrete Math. Theor. Comput. Sci., Volume 4 (2001) no. 2, pp. 91-100 (electronic only)
[23] Introduction to Quantum Mechanics, Pearson Prentice Hall, 2004, xi+468 pages
[24] Martingale limit theory and its application, Probability and Mathematical Statistics, Academic Press, 19870, xii+308 pages
[25] Generalized hyperbolic secant distributions, J. Am. Stat. Assoc., Volume 63 (1968), pp. 329-337
[26] On the role of the Heisenberg group in harmonic analysis, Bull. Am. Math. Soc., Volume 3 (1980), pp. 821-843 | DOI
[27] Endliche Gruppen. I, Grundlehren der Mathematischen Wissenschaften, 184, Springer, 1967, xii+793 pages
[28] Theta functions, Grundlehren der Mathematischen Wissenschaften, 194, Springer, 1972, x+232 pages
[29] Spectral theory of Sturm-Liouville operators on infinite intervals: a review of recent developments, Sturm-Liouville theory. Past and present. Selected survey articles based on lectures presented at a colloquium and workshop in Geneva, Italy, September 15–19, 2003 to commemorate the 200th anniversary of the birth of Charles François Sturm, Birkhäuser, 2005, pp. 99-120
[30] Random walk : a modern introduction, Cambridge Studies in Advanced Mathematics, 123, Cambridge University Press, 2010, xii+364 pages
[31] metrics on the Heisenberg group and the Goemans-Linial conjecture (submitted, an extended abstract appeared in FOCS 2006)
[32] Markov chains and mixing times, American Mathematical Society, 2009, xvii+371 pages (With a chapter by James G. Propp and David B. Wilson)
[33] The Weil representation, Maslov index and theta series, Progress in Mathematics, 6, Birkhäuser, 1980, viii+337 pages
[34] Eigenvalues and eigenvectors of the finite Fourier transform, J. Math. Phys., Volume 28 (1987), pp. 781-785 | DOI
[35] Simple representations of the integral Heisenberg group, Classical groups and related topics, Proc. Conf., Beijing/China 1987 (Contemp. Math.), Volume 82, American Mathematical Society, 1989, pp. 89-96
[36] Mixing of the upper triangular matrix walk, Probab. Theory Relat. Fields, Volume 156 (2013) no. 3-4, pp. 581-591 | DOI
[37] Cloning of Dirac fermions in graphene superlattices, Nature, Volume 497 (2013), pp. 594-597 | DOI
[38] Probability on groups: random walks and invariant diffusions, Notices Am. Math. Soc., Volume 48 (2001) no. 9, pp. 968-977
[39] Random walks on finite groups, Probability on discrete structures (Encycl. Math. Sci.), Volume 110, Springer, 2004, pp. 263-346
[40] Linear representations of finite groups, Graduate Texts in Mathematics, 42, Springer, 1977, x+170 pages (Translated from the French by Leonard L. Scott)
[41] Random walks on the two extra special groups, 1994 Department of Mathematics, Rice University (USA)
[42] Eigenvalues of random walks on groups, Ann. Probab., Volume 23 (1995) no. 4, pp. 1961-1981 | DOI
[43] Eigenvalues of the natural random walk on the Burnside group , Ann. Probab., Volume 23 (1995) no. 4, pp. 1950-1960 | DOI
[44] Group theory. II, Grundlehren der Mathematischen Wissenschaften, 248, Springer, 1986, x+621 pages (Translated from the Japanese)
[45] Measuring randomness and evaluating random number generators using the finite Heisenberg group, Limit theorems in probability and statistics (Pécs, 1989) (Colloq. Math. Soc. János Bolyai), Volume 57, North-Holland, Amsterdam, 1990, pp. 537-544
[46] Are there quantum oscillations in an incommensurate charge density wave? (2014) (https://arxiv.org/abs/1410.5108v1)
Cited by Sources: