logo AFST
An Exercise(?) in Fourier Analysis on the Heisenberg Group
Daniel Bump; Persi Diaconis; Angela Hicks; Laurent Miclo; Harold Widom
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 26 (2017) no. 2, p. 263-288

Let H(n) be the group of 3×3 uni-uppertriangular matrices with entries in /n, the integers mod n. We show that the simple random walk converges to the uniform distribution in order n 2 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 H(n) le groupe des matrices supérieures 3×3 ne contenant que des 1 sur la diagonale et dont les entrées appartiennent à /n, l’anneau des entiers modulo n. On montre que la marche aléatoire simple y converge vers la probabilité uniforme en un temps d’ordre n 2 . 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.

Published online : 2017-04-13
DOI : https://doi.org/10.5802/afst.1533
@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},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 26},
     number = {2},
     year = {2017},
     pages = {263-288},
     doi = {10.5802/afst.1533},
     language = {en},
     url = {https://afst.centre-mersenne.org/item/AFST_2017_6_26_2_263_0}
}
Bump, Daniel; Diaconis, Persi; Hicks, Angela; Miclo, Laurent; Widom, Harold. 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. afst.centre-mersenne.org/item/AFST_2017_6_26_2_263_0/

[1] Georgios K. Alexopoulos Random walks on discrete groups of polynomial volume growth, Ann. Probab., Tome 30 (2002) no. 2, pp. 723-801 | Article

[2] Sami Assaf; Persi Diaconis; K. Soundararajan A rule of thumb for riffle shuffling, Ann. Appl. Probab., Tome 21 (2011) no. 3, pp. 843-875 | Article

[3] Louis Auslander; Richard Tolimieri Is computing with the finite Fourier transform pure or applied mathematics?, Bull. Am. Math. Soc., Tome 1 (1979), pp. 847-897 | Article

[4] Artur Avila; Svetlana Jitomirskaya The Ten Martini Problem, Ann. Math., Tome 170 (2009) no. 1, pp. 303-342 | Article

[5] Cédric Béguin; Alain Valette; Andrzej Zuk On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper’s operator, J. Geom. Phys., Tome 21 (1997) no. 4, pp. 337-356 | Article

[6] Florin P. Boca; Alexandru Zaharescu Norm estimates of almost Mathieu operators, J. Funct. Anal., Tome 220 (2005) no. 1, pp. 76-96 | Article

[7] Emmanuel Breuillard Random Walks on Lie Groups (2004) (Ph. D. Thesis)

[8] Emmanuel Breuillard Local limit theorems and equidistribution of random walks on the Heisenberg group, Geom. Funct. Anal., Tome 15 (2005) no. 1, pp. 35-82 | Article

[9] Daniel Bump Automorphic forms and representations, Cambridge Studies in Advanced Mathematics, Tome 55, Cambridge University Press, 1997, xiv+574 pages

[10] Daniel Bump; Persi Diaconis; Angela Hicks; Laurent Miclo; Harold Widom Characters and super characters for step two nilpotent groups with applications to random walks (to appear)

[11] Daniel Bump; Persi Diaconis; Angela Hicks; Laurent Miclo; Harold Widom Useful bounds on the extreme eigenvalues and vectors of matrices for Harper’s operators (2016) (to appear in Operator Theory: Advances and Applications)

[12] Pierre Cartier Quantum mechanical commutation relations and theta functions, Algebraic Groups and Discontinuous Subgroups (Proc. Sympos. Pure Math.) Tome 9, American Mathematical Society, 1966, pp. 361-383 ((Boulder, Colo., 1965))

[13] Persi Diaconis Group representations in probability and statistics, IMS Lecture Notes-Monograph Series, Tome 11, Institute of Mathematical Statistics, 1988, vi+198 pages

[14] Persi Diaconis 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) Tome 524, American Mathematical Society, 2010, pp. 33-47

[15] Persi Diaconis; B. Hough Random walk on unipotent matrix groups (to appear)

[16] Persi Diaconis; Laurent Miclo On Quantitative Convergence to Quasi-Stationarity, Ann. Fac. Sci. Toulouse, Math., Tome 24 (2015) no. 4, pp. 973-1016 | Article

[17] Persi Diaconis; Laurent Saloff-Coste Comparison theorems for reversible Markov chains, Ann. Appl. Probab., Tome 3 (1993) no. 3, pp. 696-730 | Article

[18] Persi Diaconis; Laurent Saloff-Coste Moderate growth and random walk on finite groups, Geom. Funct. Anal., Tome 4 (1994) no. 1, pp. 1-36 | Article

[19] Persi Diaconis; Laurent Saloff-Coste An application of Harnack inequalities to random walk on nilpotent quotients, J. Fourier Anal. Appl., Tome Special Issue (1995), pp. 189-207 (Proceedings of the Conference in Honor of Jean-Pierre Kahane (Orsay, 1993))

[20] Persi Diaconis; Laurent Saloff-Coste Nash inequalities for finite Markov chains, J. Theor. Probab., Tome 9 (1996) no. 2, pp. 459-510 | Article

[21] Bradley W. Dickinson; Kenneth Steiglitz Eigenvectors and functions of the discrete Fourier transform, IEEE Trans. Acoust. Speech Signal Process., Tome 30 (1982), pp. 25-31 | Article

[22] Johannes Grassberger; Günther Hörmann A note on representations of the finite Heisenberg group and sums of greatest common divisors, Discrete Math. Theor. Comput. Sci., Tome 4 (2001) no. 2, pp. 91-100 (electronic only)

[23] David J. Griffiths Introduction to Quantum Mechanics, Pearson Prentice Hall, 2004, xi+468 pages

[24] Peter Gavin Hall; Christopher Charles Heyde Martingale limit theory and its application, Probability and Mathematical Statistics, Academic Press, 19870, xii+308 pages

[25] William L. Harkness; M. L. Harkness Generalized hyperbolic secant distributions, J. Am. Stat. Assoc., Tome 63 (1968), pp. 329-337

[26] Roger Howe On the role of the Heisenberg group in harmonic analysis, Bull. Am. Math. Soc., Tome 3 (1980), pp. 821-843 | Article

[27] Bertram Huppert Endliche Gruppen. I, Grundlehren der Mathematischen Wissenschaften, Tome 184, Springer, 1967, xii+793 pages

[28] Jun-ichi Igusa Theta functions, Grundlehren der Mathematischen Wissenschaften, Tome 194, Springer, 1972, x+232 pages

[29] Yoram Last 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] Gregory F. Lawler; Vlada Limic Random walk : a modern introduction, Cambridge Studies in Advanced Mathematics, Tome 123, Cambridge University Press, 2010, xii+364 pages

[31] James R. Lee; Assaf Naor l p metrics on the Heisenberg group and the Goemans-Linial conjecture (submitted, an extended abstract appeared in FOCS 2006)

[32] David A. Levin; Yuval Peres; Elizabeth L. Wilmer Markov chains and mixing times, American Mathematical Society, 2009, xvii+371 pages (With a chapter by James G. Propp and David B. Wilson)

[33] Gerard Lion; Michele Vergne The Weil representation, Maslov index and theta series, Progress in Mathematics, Tome 6, Birkhäuser, 1980, viii+337 pages

[34] Madan Lal Mehta Eigenvalues and eigenvectors of the finite Fourier transform, J. Math. Phys., Tome 28 (1987), pp. 781-785 | Article

[35] Charles Nunley; Andy Magid Simple representations of the integral Heisenberg group, Classical groups and related topics, Proc. Conf., Beijing/China 1987 (Contemp. Math.) Tome 82, American Mathematical Society, 1989, pp. 89-96

[36] Yuval Peres; Allan Sly Mixing of the upper triangular matrix walk, Probab. Theory Relat. Fields, Tome 156 (2013) no. 3-4, pp. 581-591 | Article

[37] L. A. Ponomarenko Cloning of Dirac fermions in graphene superlattices, Nature, Tome 497 (2013), pp. 594-597 | Article

[38] Laurent Saloff-Coste Probability on groups: random walks and invariant diffusions, Notices Am. Math. Soc., Tome 48 (2001) no. 9, pp. 968-977

[39] Laurent Saloff-Coste Random walks on finite groups, Probability on discrete structures (Encycl. Math. Sci.) Tome 110, Springer, 2004, pp. 263-346

[40] Jean-Pierre Serre Linear representations of finite groups, Graduate Texts in Mathematics, Tome 42, Springer, 1977, x+170 pages (Translated from the French by Leonard L. Scott)

[41] Richard Stong Random walks on the two extra special groups, 1994 (Department of Mathematics, Rice University (USA))

[42] Richard Stong Eigenvalues of random walks on groups, Ann. Probab., Tome 23 (1995) no. 4, pp. 1961-1981 | Article

[43] Richard Stong Eigenvalues of the natural random walk on the Burnside group B(3,n), Ann. Probab., Tome 23 (1995) no. 4, pp. 1950-1960 | Article

[44] Michio Suzuki Group theory. II, Grundlehren der Mathematischen Wissenschaften, Tome 248, Springer, 1986, x+621 pages (Translated from the Japanese)

[45] Maria Zack 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) Tome 57, North-Holland, Amsterdam, 1990, pp. 537-544

[46] Yi Zhang; Akash V. Maharaj; Steven A. Kivelson Are there quantum oscillations in an incommensurate charge density wave? (2014) (https://arxiv.org/abs/1410.5108v1)