cnrs   Université de Toulouse

Table of contents for this issue | Previous article | Next article
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 Sér. 6, 26 no. 2 (2017), p. 263-288, doi: 10.5802/afst.1533
Article PDF

Résumé - Abstract

Let $H(n)$ 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] Georgios K. Alexopoulos, “Random walks on discrete groups of polynomial volume growth”, Ann. Probab. 30 (2002) no. 2, p. 723-801 Article
[2] Sami Assaf, Persi Diaconis & K. Soundararajan, “A rule of thumb for riffle shuffling”, Ann. Appl. Probab. 21 (2011) no. 3, p. 843-875 Article
[3] Louis Auslander & Richard Tolimieri, “Is computing with the finite Fourier transform pure or applied mathematics?”, Bull. Am. Math. Soc. 1 (1979), p. 847-897 Article
[4] Artur Avila & Svetlana Jitomirskaya, “The Ten Martini Problem”, Ann. Math. 170 (2009) no. 1, p. 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. 21 (1997) no. 4, p. 337-356 Article
[6] Florin P. Boca & Alexandru Zaharescu, “Norm estimates of almost Mathieu operators”, J. Funct. Anal. 220 (2005) no. 1, p. 76-96 Article
[7] Emmanuel Breuillard, Random Walks on Lie Groups, Ph. D. Thesis, Yale University (USA), Chapter 2, 2004
[8] Emmanuel Breuillard, “Local limit theorems and equidistribution of random walks on the Heisenberg group”, Geom. Funct. Anal. 15 (2005) no. 1, p. 35-82 Article
[9] Daniel Bump, Automorphic forms and representations, Cambridge Studies in Advanced Mathematics 55, Cambridge University Press, 1997
[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”, to appear in Operator Theory: Advances and Applications, 2016
[12] Pierre Cartier, Quantum mechanical commutation relations and theta functions, Algebraic Groups and Discontinuous Subgroups, Proc. Sympos. Pure Math. 9, American Mathematical Society, 1966, p. 361–383  MR 216825
[13] Persi Diaconis, Group representations in probability and statistics, IMS Lecture Notes-Monograph Series 11, Institute of Mathematical Statistics, 1988
[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 524, American Mathematical Society, 2010, p. 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. 24 (2015) no. 4, p. 973-1016 Article
[17] Persi Diaconis & Laurent Saloff-Coste, “Comparison theorems for reversible Markov chains”, Ann. Appl. Probab. 3 (1993) no. 3, p. 696-730 Article
[18] Persi Diaconis & Laurent Saloff-Coste, “Moderate growth and random walk on finite groups”, Geom. Funct. Anal. 4 (1994) no. 1, p. 1-36 Article
[19] Persi Diaconis & Laurent Saloff-Coste, “An application of Harnack inequalities to random walk on nilpotent quotients”, J. Fourier Anal. Appl. Special Issue (1995), p. 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. 9 (1996) no. 2, p. 459-510 Article
[21] Bradley W. Dickinson & Kenneth Steiglitz, “Eigenvectors and functions of the discrete Fourier transform”, IEEE Trans. Acoust. Speech Signal Process. 30 (1982), p. 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. 4 (2001) no. 2, p. 91-100, electronic only
[23] David J. Griffiths, Introduction to Quantum Mechanics, Pearson Prentice Hall, 2004
[24] Peter Gavin Hall & Christopher Charles Heyde, Martingale limit theory and its application, Probability and Mathematical Statistics, Academic Press, 19870
[25] William L. Harkness & M. L. Harkness, “Generalized hyperbolic secant distributions”, J. Am. Stat. Assoc. 63 (1968), p. 329-337
[26] Roger Howe, “On the role of the Heisenberg group in harmonic analysis”, Bull. Am. Math. Soc. 3 (1980), p. 821-843 Article
[27] Bertram Huppert, Endliche Gruppen. I, Grundlehren der Mathematischen Wissenschaften 184, Springer, 1967
[28] Jun-ichi Igusa, Theta functions, Grundlehren der Mathematischen Wissenschaften 194, Springer, 1972
[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, p. 99–120
[30] Gregory F. Lawler & Vlada Limic, Random walk : a modern introduction, Cambridge Studies in Advanced Mathematics 123, Cambridge University Press, 2010  MR 2677157
[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, 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 6, Birkhäuser, 1980
[34] Madan Lal Mehta, “Eigenvalues and eigenvectors of the finite Fourier transform”, J. Math. Phys. 28 (1987), p. 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. 82, American Mathematical Society, 1989, p. 89–96
[36] Yuval Peres & Allan Sly, “Mixing of the upper triangular matrix walk”, Probab. Theory Relat. Fields 156 (2013) no. 3-4, p. 581-591 Article
[37] L. A. Ponomarenko & , “Cloning of Dirac fermions in graphene superlattices”, Nature 497 (2013), p. 594-597 Article
[38] Laurent Saloff-Coste, “Probability on groups: random walks and invariant diffusions”, Notices Am. Math. Soc. 48 (2001) no. 9, p. 968-977
[39] Laurent Saloff-Coste, Random walks on finite groups, Probability on discrete structures, Encycl. Math. Sci. 110, Springer, 2004, p. 263–346
[40] Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics 42, Springer, 1977, 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. 23 (1995) no. 4, p. 1961-1981 Article
[43] Richard Stong, “Eigenvalues of the natural random walk on the Burnside group $B(3,n)$”, Ann. Probab. 23 (1995) no. 4, p. 1950-1960 Article
[44] Michio Suzuki, Group theory. II, Grundlehren der Mathematischen Wissenschaften 248, Springer, 1986, 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 57, North-Holland, Amsterdam, 1990, p. 537–544
[46] Yi Zhang, Akash V. Maharaj & Steven A. Kivelson, “Are there quantum oscillations in an incommensurate charge density wave?”,, 2014
Search for an article
Search within the site