An Exercise(?) in Fourier Analysis on the Heisenberg Group

Bump, Daniel; Diaconis, Persi; Hicks, Angela; Miclo, Laurent; Widom, Harold

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 2, pp. 263-288.

Soit $H\left(n\right)$ le groupe des matrices supérieures $3\times 3$ ne contenant que des 1 sur la diagonale et dont les entrées appartiennent à $\mathbb{Z}/n\mathbb{Z}$, 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.

Let $H\left(n\right)$ be the group of $3\times 3$ uni-uppertriangular matrices with entries in $\mathbb{Z}/n\mathbb{Z}$, 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.

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

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

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

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

[5] Béguin, Cédric; Valette, Alain; Zuk, Andrzej 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] Boca, Florin P.; Zaharescu, Alexandru Norm estimates of almost Mathieu operators, J. Funct. Anal., Volume 220 (2005) no. 1, pp. 76-96 | DOI

[7] Breuillard, Emmanuel Random Walks on Lie Groups, Yale University (USA) (2004) (Ph. D. Thesis Chapter 2)

[8] Breuillard, Emmanuel 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] Bump, Daniel Automorphic forms and representations, Cambridge Studies in Advanced Mathematics, 55, Cambridge University Press, 1997, xiv+574 pages

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

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

[12] Cartier, Pierre 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] Diaconis, Persi Group representations in probability and statistics, IMS Lecture Notes-Monograph Series, 11, Institute of Mathematical Statistics, 1988, vi+198 pages

[14] Diaconis, Persi 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] Diaconis, Persi; Hough, B. Random walk on unipotent matrix groups (to appear)

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

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

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

[19] Diaconis, Persi; Saloff-Coste, Laurent 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] Diaconis, Persi; Saloff-Coste, Laurent Nash inequalities for finite Markov chains, J. Theor. Probab., Volume 9 (1996) no. 2, pp. 459-510 | DOI

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

[22] Grassberger, Johannes; Hörmann, Günther 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] Griffiths, David J. Introduction to Quantum Mechanics, Pearson Prentice Hall, 2004, xi+468 pages

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

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

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

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

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

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

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

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

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

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

[35] Nunley, Charles; Magid, Andy 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] Peres, Yuval; Sly, Allan Mixing of the upper triangular matrix walk, Probab. Theory Relat. Fields, Volume 156 (2013) no. 3-4, pp. 581-591 | DOI

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

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

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

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

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

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

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

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

[45] Zack, Maria 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] Zhang, Yi; Maharaj, Akash V.; Kivelson, Steven A. Are there quantum oscillations in an incommensurate charge density wave? (2014) (https://arxiv.org/abs/1410.5108v1)