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.

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:
DOI: 10.5802/afst.1533

Daniel Bump 1; Persi Diaconis 2; Angela Hicks 2; Laurent Miclo 3; Harold Widom 4

1 Department of Mathematics, Stanford University, 450 Serra Mall, Bldg. 380, Stanford, CA 94305-2125, USA
2 same address
3 Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118, route de Narbonne, F-31062 Toulouse Cedex 9, France
4 UC Santa Cruz, Department of Mathematics, Santa Cruz, CA 95064, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     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 = {}
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  -
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
%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.

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

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

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

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

[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., Volume 21 (1997) no. 4, pp. 337-356 | DOI

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

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

[8] Emmanuel Breuillard 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] Daniel Bump Automorphic forms and representations, Cambridge Studies in Advanced Mathematics, 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.), Volume 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, 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), Volume 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., Volume 24 (2015) no. 4, pp. 973-1016 | DOI

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

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

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

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

[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., Volume 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., Volume 63 (1968), pp. 329-337

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

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

[28] Jun-ichi Igusa Theta functions, Grundlehren der Mathematischen Wissenschaften, 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, 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, 6, Birkhäuser, 1980, viii+337 pages

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

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

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

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

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

[40] Jean-Pierre Serre Linear representations of finite groups, Graduate Texts in Mathematics, 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., Volume 23 (1995) no. 4, pp. 1961-1981 | DOI

[43] Richard Stong 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] Michio Suzuki Group theory. II, Grundlehren der Mathematischen Wissenschaften, 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), Volume 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) (

Cited by Sources: