RANDOM WALK ON UNIPOTENT MATRIX GROUPS

arXiv:1512.06304v2 [math.PR] 25 Nov 2017

PERSI DIACONIS AND BOB HOUGH
Abstract. We introduce a new method for proving central limit
theorems for random walk on nilpotent groups. The method is
illustrated in a local central limit theorem on the Heisenberg group,
weakening the necessary conditions on the driving measure. As
a second illustration, the method is used to study walks on the
n ˆ n uni-upper triangular group with entries taken modulo p.
The method allows sharp answers to the behavior of individual
coordinates: coordinates immediately above the diagonal require
order p2 steps for randomness, coordinates on the second diagonal
require order p steps; coordinates on the kth diagonal require order
2
p k steps.

1. Introduction
Let HpRq denote the real Heisenberg group
$¨
,
˛
& 1 x z
.
(1)
HpRq “ ˝ 0 1 y ‚ : x, y, z P R .
% 0 0 1
¨
˛
1 x z
Abbreviate ˝ 0 1 y ‚ with rx, y, zs, identified with a vector in R3 .
0 0 1
Consider simple random walk on G “ HpRq driven by Borel probability
measure µ. For N ě 1, the law of this walk is the convolution power
µ˚N where, for Borel measures µ, ν on G, and for f P Cc pGq,
ż
(2)
xf, µ ˚ νy “
f pghq dµpgq dνphq.
g,hPG

Say that measure µ is non-lattice (aperiodic) if its support is not
contained in a proper closed subgroup of G. For general non-lattice
µ of compact support Breuillard [6] uses the representation theory of
G to prove a local limit theorem for the law of µ˚N , asymptotically
evaluating its density in translates of bounded Borel sets. However,
in evaluating µ˚N on Borel sets translated on both the left and the

2010 Mathematics Subject Classification. Primary 60F05, 60B15, 20B25, 22E25,
60J10, 60E10, 60F25, 60G42.
Key words and phrases. Random walk on a group, Heisenberg group, local limit
theorem, unipotent group.
We are grateful to Laurent Saloff-Coste, who provided us a detailed account of
previous work.
1

2

PERSI DIACONIS AND BOB HOUGH

right he makes a decay assumption on the Fourier transform of the
abelianization of the measure µ, and raises the question of whether
this is needed. We show that this condition is unnecessary. In doing so
we give an alternative approach to the local limit theorem on G treating
it as an extension of the classical local limit theorem on Rn . We also
obtain the best possible rate. The method of argument is analogous to
(though simpler than) the analysis of quantitative equidistribution of
polynomial orbits on G from [19].
Recall that the abelianization Gab “ G{rG, Gs of G is isomorphic to
2
R with projection p : G Ñ Gab given by pprx, y, zsq “ rx, ys. Assume
that the probability measure µ satisfies the following conditions.
i. Compact support.
ii. Centered. The projection p satisfies
ż
(3)
ppgqdµpgq “ 0.
G

iii. Full dimension. Let Γ “ xsupp µy be the closure of the subgroup of G generated by the support of µ. The quotient G{Γ is
compact.
Section 2 gives a characterization of closed subgroups Γ of G of full
dimension.
Under the above conditions, the central limit theorem for µ is known.
Let pdt qtą0 denote the semigroup of dilations given by
dt prx, y, zsq “ rtx, ty, t2 zs

(4)

and denote the Gaussian semigroup pνt qtą0 defined by its generator (see
[6], [10])
ˇ ż
d ˇˇ
(5)
f pgqdνt pgq
Af “ ˇ
dt
t“0

gPG

1
1
2
“ zBz f pidq ` xyBxy
f pidq ` x2 Bx2 f pidq ` y 2 By2 f pidq
2
2
ş
2
2
2
2
“ xy, z.
where σx “ x2 “ g“rx,y,zsPG x dµpgq and similarly σy “ y 2, σxy
With ν “ ν1 , the central limit theorem for µ states that for f P Cc pGq,
A
E
(6)
f, d ?1 µ˚N Ñ xf, νy.
N

For g P G define the left and right translation operators Lg , Rg :
L2 pGq Ñ L2 pGq,
(7)

Lg f phq “ f pghq,

Rg f phq “ f phgq.

Our local limit theorem in the non-lattice case is as follows.
Theorem 1. Let µ be a Borel probability measure of compact support
on G “ HpRq, which is centered and full dimension. Assume that
the projection to the abelianization µab is non-lattice. Let ν be the

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

3

limiting Gaussian measure of d ?1 µ˚N . Uniformly for g, h P G and for
N
f P Cc pGq, as N Ñ 8,
D
`
˘
@
D @
(8)
Lg Rh f, µ˚N “ Lg Rh f, d?N ν ` oµ }f }1 N ´2 .
If the Cramér condition holds:
ˇż
ˇ
(9)
sup ˇˇ
x2 , |λ|ą1
λPR

g“rx,y,zsPG

´iλ¨px,yq

e

ˇ
ˇ
dµpgqˇˇ ă 1

then uniformly for g, h P G and Lipschitz f P Cc pGq, as N Ñ 8
¯
´
@
D @
D
5
(10)
Lg Rh f, µ˚N “ Lg Rh f, d?N ν ` Of,µ N ´ 2 .

Remark. The rate is best possible as may be seen by projecting to the
abelianization. A variety of other statements of the local theorem are
also derived, see eqn. (74) in Section 3.
Remark. For non-lattice µ, [6] obtains (8) with h “ id and for general
h subject to Cramér’s condition. A condition somewhat weaker than
Cramér’s would suffice to obtain (10).
Remark. In the case that µ is supported on a closed discrete subgroup
or has
with respect to Haar measure, [1, 2] obtains an error
´ a density
¯
5
of O N ´ 2 in approximating µ˚N pgq, g P Γ.

Our proof of Theorem 1 applies equally well in the case when µab
has a lattice component, and gives a treatment which is more explicit
than the argument in [1]. To illustrate this, we determine the leading
constant in the probability of return to 0 in simple random walk on
HpZq.
Theorem 2. Let µ0 be the measure on HpZq which assigns equal probability 15 to each element of the generating set
$ ¨
˛ ¨
˛,
1 ˘1 0
1 0 0 .
&
(11)
id, ˝ 0 1 0 ‚, ˝ 0 1 ˘1 ‚ .
%
0 0 1
0 0 1
¯
´
25
´ 25
As N Ñ 8, µ˚N
pidq
“
.
`
O
N
0
16N 2
The basic idea which drives the proof is that permuting segments
of generators in a typical word of the walk generates smoothness in
the central coordinate of the product, while leaving the abelianized
coordinates unchanged. This observation permits passing from a limit
theorem to a local limit theorem by smoothing at a decreasing sequence
of scales. When studying µ˚N near the scale of its distribution, we use
a Lindeberg replacement scheme in which one copy at a time of µ is
replaced with a Gaussian measure in the abelianization. To handle uniformity in the translation in Theorem 1 in the case where the Cramér

4

PERSI DIACONIS AND BOB HOUGH

condition is not assumed we are forced to treat frequencies α which are
unbounded, and thus must consider the large spectrum
(
(12)
Specϑ pµab q “ α P R2 : |µ̂ab pαq| ą 1 ´ ϑ
where ϑ Ñ 0 as a function of N. In treating this, we use an approximate
lattice structure of Specϑ pµab q, see Section 2.1.
As a further application of the word rearrangement technique, answering a question of [13] we determine the mixing time of the central
coordinate in a natural class of random walks on the group Nn pZ{pZq
of n ˆ n uni-upper triangular matrices with entries in Z{pZ.

Theorem 3. Let n ě 2 and let µ be a probability measure on Zn´1
which satisfies the following conditions.
i.
ii.
iii.
iv.
v.
(13)

Bounded support.
Full support. xsupp µy “ Zn´1
Lazy. µp0q ąř0
Mean zero. xPZn´1 xµpxq “ 0
Trivial covariance.
¸n´1
˜
ÿ
xpiq xpjq µpxq
“ In´1 .
xPZn´1

i,j“1

Push forward µ to a probability measure µ̃ on Nn pZq via, for all x P
Zn´1 ,
¨
˛
1 xp1q 0 ¨ ¨ ¨
0
..
.
˚
‹
.
˚ 0 1 xp2q . .
‹
˚ . .
‹
.
.
(14)
µ̃ ˚ ..
‹ “ µpxq.
..
..
..
0
˚
‹
˝
pn´1q ‚
0
1 x
0 ¨¨¨
0
1

Write Z : Nn pZq Ñ Z for the upper right corner entry of a matrix of
Nn pZq. There exists C ą 0 such that, for all primes p, for N ě 1,
˜
¸
ˇ
ÿ ˇˇ
ˇ
N
1
ˇµ̃˚N pZ ” x mod pq ´ ˇ ! exp ´C 2
(15)
.
ˇ
pˇ
p n´1
x mod p
´

Remark. Informally, the top right corner entry mixes in time O p

2
n´1

1

¯

.

This is tight, since archimedean considerations show that the L dis2
tance to uniform is " 1 if the number of steps of the walk is ! p n´1 .
Remark. Although we have considered only the top right corner entry
in Un pZ{pZq, this result determines the mixing time of each entry above
the diagonal by iteratively projecting to the subgroups determined by
the top left or bottom right m ˆ m sub-matrices.

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

5

Remark. Our argument permits treating measures not supported on the
first super-diagonal essentially without change. We treat the simplified
case stated in order to ease the notation.
History
Random walk on groups is a mature subject with myriad projections
into probability, analysis and applications. Useful overviews with extensive references are in [5], [25]. Central limit theorems for random
walk on Lie groups were first proved by [29] with [28] carrying out the
details for the Heisenberg group. Best possible results under a second
moment condition for nilpotent Lie groups are in [24].
A general local limit theorem for the Heisenberg group appears in
[6], which contains a useful historical review. There similar conditions
to those of our Theorem 1 are made, but the argument treats only the
non-lattice case and needs a stronger condition on the characteristic
function of the measure projected to the abelianization. Remarkable
local limit theorems are in [1, 2]. The setting is groups of polynomial growth, and so “essentially” nilpotent Lie groups via Gromov’s
Theorem. The first paper gives quite complete results assuming that
the generating measure has a density. The second paper gives results
for measures supported on a lattice. The arguments in [2] have been
adapted in [7] to give a local limit theorem for non-lattice measures
supported on finitely many points.
Just as for the classical abelian case, many variations have been studied. Central limit theorems for walks satisfying a Lindeberg condition
on general Lie groups are proved in [26], see also references therein.
Large deviations for walks on nilpotent groups are proved in [3]. Central limit theorems on covering graphs with nilpotent automorphism
groups are treated in [21, 22]. This allows walks on Cayley graphs with
some edges and vertices added and deleted. Brownian motion and heat
kernel estimates are also relevant, see [20, 17].
Random walk on finite nilpotent groups are a more recent object
of study. Diaconis and Saloff-Coste [15, 14, 13] show that for simple
symmetric random walk on Z{nZ, order n2 steps are necessary and
sufficient for convergence to uniform. The first paper uses Nash inequalities, the second lifts to random walk on the free nilpotent group
and applies central limit theorems of Hebisch, Saloff-Coste and finally
Harnack inequalities to transfer back to the finite setting. The third
paper uses geometric ideas of moderate growth to show that for groups
of polynomial growth, diameter-squared steps are necessary and sufficient to reach uniformity. This paper raises the question of the behavior
of the individual coordinates on Un pZ{pZq which is finally answered in
Theorem 3. A direct non-commuting Fourier approach to HpZ{pZq is
carried out in [8], where it is shown that order p log p steps suffice to
make the central coordinate random, improved here to order p steps,

6

PERSI DIACONIS AND BOB HOUGH

which is best possible. For a review of the HpZq results, see [12]. Finally there have been quite a number of papers studying the walk on
Un pZ{pZq when both p and n grow. We refer to [23], which contains a
careful review and definitive results.

Notation and conventions
Vectors from Rd , d ě 1 are written in plain text w, their coordinates
with superscripts w piq , and sequences of vectors with an underline w.
The sum of a sequence of vectors w is indicated w. w t denotes the
transpose of w. We have been cavalier in our use of transpose; interpretation of vectors as rows or columns should be clear from the
context. We frequently identify matrix elements in the group Un with
vectors from Euclidean space, and have attempted to indicate the way
in which the vectors should be interpreted. As a rule of thumb, when
the group law is written multiplicatively, the product is in the group
Un , and when additively, in Euclidean space.
The arguments presented use permutation group actions on sequences
of vectors. Given integer N ě 1, denote SN the symmetric group on
rNs “ Z X r1, Ns, which acts on length N sequence of vectors by permuting the indices:
(16)

SN Q σ : pw1 , ..., wN q ÞÑ pwσp1q , ..., wσpN q q.

C2 is the two-element group. For d ě 1, identify C2d with the ddimensional hypercube t0, 1ud . 1d is the element of C2d corresponding
to the sequence of all 1’s on the hypercube. C2d acts on sequences of
vectors of length 2d with the jth factor determining the relative order
of the first and second blocks of 2j´1 elements. To illustrate the action
of C22 on x “ x1 x2 x3 x4 :
(17)

p0, 0q ¨ x “ x1 x2 x3 x4
p1, 0q ¨ x “ x2 x1 x3 x4
p0, 1q ¨ x “ x3 x4 x1 x2

p1, 1q ¨ x “ x3 x4 x2 x1 .
The 2-norm on Rd is indicated } ¨ } and } ¨ }pR{Zqd denotes distance
to the nearest integer lattice point. Given ξ P Rd , eξ p¨q denotes the
character of Rd , eξ pxq “ e2πiξ¨x .
Use δx to indicate the Dirac delta measure at x P Rd . Given f P
Cc pRd q and measure µ, xf, µy denotes the bilinear pairing
ż
(18)
xf, µy “
f pxqdµpxq.
Rd

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

7

Denote the Fourier transform of function f , resp. the characteristic
function of measure µ by, for ξ P Rd ,
ż
ż
(19)
fˆpξq “
e´ξ pxqf pxqdx,
µ̂pξq “
e´ξ pxqdµpxq.
Rd

Rd

For x P Rd , Tx f denotes function f translated by x,

(20)

ˆ
Ty
x f pξq “ e´ξ pxqf pξq

Tx f pyq “ f py ´ xq,

and for real t ą 0, ft denotes f dilated by t,
(21)

ft pxq “ t f ptxq ,

For smooth f ,
(22)

ˆ ˙
ξ
p
ˆ
ft pξq “ f
.
t

d

f pxq “

ż

Rd

fˆpξqeξ pxqdξ.

By a bump function ρ on Rn we mean a smooth non-negative function
of compact support and integral 1. The Fourier transform of ρ satisfies,
for each A ą 0 there is a constant CpA, ρq ą 0 such that
(23)

|ρ̂pξq| ď

CpA, ρq
.
p1 ` }ξ}qA

This follows from integration by parts.
For r P R and σ ą 0, ηpr, σq denotes the one-dimensional Gaussian
distribution with mean r and variance σ 2 , with density and characteristic function
(24)
´
¯
2
exp ´ px´rq
2
`
˘
2σ
{
?
,
ηpr,
σqpξq “ e´ξ prq exp ´2π 2 σ 2 ξ 2 .
ηpr, σqpxq “
2πσ
A centered (mean zero) normal distribution η in dimension d is specified
by its covariance matrix
ˆż
˙d
2
pmq pnq
(25)
σ “
x x ηpxq
Rd

m,n“1

and has density and characteristic function
(26)
´ t 2 ´1 ¯
exp ´ x pσ 2q x
`
˘
{
ηp0, σqpxq “
ηp0,
σqpξq “ exp ´2π 2 ξ t σ 2 ξ .
1 ,
d
p2πq 2 pdet σ 2 q 2

All of our arguments concern the repeated convolution µ˚N of a fixed
measure µ on the upper triangular matrices. The product measure µbN
is abbreviated UN . Asymptotic statements are with respect to N as
the large parameter. The Vinogradov notation A ! B, resp. A " B,
means A “ OpBq, resp. B “ OpAq. A — B means A ! B and B ! A.

8

PERSI DIACONIS AND BOB HOUGH

2. Background to Theorems 1 and 2
This section collects together several background statements regarding the Heisenberg group, its Gaussian semigroups of probability measures and statements of elementary probability which are needed in the
course of the argument.
Write A “ r1, 0, 0s, B “ r0, 1, 0s, C “ r0, 0, 1s. The following commutators are useful,
(27)

rA, Bs “ ABA´1 B ´1 “ r0, 0, 1s “ C,

rA´1 , B ´1 s “ A´1 B ´1 AB “ r0, 0, 1s “ C,

rA, B ´1 s “ AB ´1 A´1 B “ r0, 0, ´1s “ C ´1 ,

rA´1 , Bs “ A´1 BAB ´1 “ r0, 0, ´1s “ C ´1 .

A convenient representation for rx, y, zs P HpRq is C z B y Ax . Using
the commutator rules above, the multiplication rule for w P HpRqN
becomes
N ”
ı “
ź
‰
p2q
p3q
p1q
(28)
wi , wi , wi “ w p1q , wp2q , w p3q ` Hpwq
i“1

where ¨ and H act on sequences of vectors from R3 via
ÿ
ÿ p1q p2q
(29)
w“
wi
Hpwq “
wi wj .
i

iăj

It is also convenient to define

N
1 p1q p2q 1 ÿ p1q p2q
(30)
w w
H pwq “ Hpwq ´ w w `
2
2 i“1 i i
¯
1 ÿ ´ p1q p2q
p2q p1q
“
wi wj ´ wi wj ,
2 1ďiăjďN
‰
“
and for w “ rx, y, zs, w̃ “ x, y, z ´ 21 xy , so that the multiplication
rule may be written
„

N
ź
1 p1q p2q
˚
(31)
wi “ w̃ ` 0, 0, w w ` H pwq .
2
i“1
˚

Let S “ supp µ. Recall that Γ “ xSy is the closure of the group
generated by S. Its abelianization, Γab “ Γ{rΓ, Γs is equal to ppΓq
where p is the projection p : G Ñ Gab . Let Γ0 be the semigroup
generated by S. We record the following descriptions of Γ and Γ0 .
Proposition 4. Let Γ ď HpRq be a closed subgroup of full dimension.
The structure of the abelianization Γab “ Γ{rΓ, Γs and of Γ falls into
one of the following cases.
i.
(32)

Γab “ R2 ,

Γ “ trγ, rs : γ P Γab , r P Ru

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

(33)

9

ii. There exist non-zero orthogonal v1 , v2 P R2 , such that
Γab “ tnv1 ` rv2 : n P Z, r P Ru,

Γ “ trγ, rs : γ P Γab , r P Ru

iii. There exist non-zero v1 , v2 P R2 , linearly independent over R,
such that
(34)

(35)

Γab “ tn1 v1 ` n2 v2 : n1 , n2 P Zu.

In this case, Γ falls into one of two further cases
iv. Γ “ trγ, rs : γ P Γab , r P Ru
v. There exists λ P Rą0 and f : Γab Ñ R such that
Γ “ trγ, λpf pγq ` nqs : γ P Γab , n P Zu .

Proof of Proposition 4. The full dimension condition guarantees that
Γab is a two dimensional closed subgroup of R2 , and the three possibilities given are all such closed subgroups. Likewise, the center of Γ
is a non-trivial subgroup of R, hence either R or λ ¨ Z for some real
λ ą 0. It follows that the fiber over γ P Γab is a translate of the
center. Let v1 , v2 be two linearly independent elements of the abelianization, and choose g1 “ rv1 , z1 s, g2 “ rv2 , z2 s in Γ. The commutator
rg1 , g2 s “ g1 g2 g1´1 g2´1 is bilinear in v1 , v2 , is non-zero, and lies in the
center. It follows that if one of v1 , v2 may be scaled by a continuous
parameter in the abelianization then the center is R.

Lemma 5. The closure of the semigroup Γ0 is Γ0 “ Γ.
Proof. Write Γ0,ab “ ppΓ0 q where p denotes projection to the abelianization Gab . That Γ0,ab “ Γab follows from the local limit theorem on
R2 . To treat the central fiber, in the case Γab “ R2 let 0 ă ǫ ă 41 be a
fixed small parameter and choose x, x1 , y, y 1 in Γ0 such that
(36)

ppxq, ppx1 q, ppyq, ppy 1q « e1 , ´e1 , e2 , ´e2

where the approximation means to within distance ǫ. Take a word
w in T “ tid, x, x1 , y, y 1u of length 4n with product approximating
the identity in Γab to within ǫ, which is such that each of x, x1 , y, y 1
appear ą p1 ´ Opǫqqn times in w. The abelianization of the product is
independent of the ordering of w, but if the letters in w appear in order
y, x, y 1, x1 then the central element is ă ´p1 ` Opǫqqn2 , while if they
appear in order y 1 , x, y, x1 then the central element is ą p1 ` Opǫqqn2 .
Moving from an ordering of the first type to an ordering of the second
by swapping generators one at a time changes the central element by
Op1q at each step. Let ǫ Ó 0 to deduce that Γ0 contains positive and
negative central elements, and hence that Γ0 is a group, equal to Γ. In
the case Γab has a one or two dimensional lattice component, replace
either e1 or both e1 , e2 above with a basis for the lattice component
and repeat the argument.


10

PERSI DIACONIS AND BOB HOUGH

More quantitative structural statements are as follows.
Lemma 6. Let µ be a measure on HpRq, with abelianization µab not
supported on a lattice of R2 . If the Cramér condition holds for the
measure µab then it holds also for the measure on µ1 on R obtained by
pushing forward µab b µab by H ˚ pw1 , w2 q.
Proof. Let ξ P R, |ξ| ě 1 and fix w2 P supppµab q, bounded away from
w1 ^w2
˚
“ 21 w1 ¨ ŵ2 . The claim follows since
ˇ0.ş Write˚ H pw1 , w2 q “ ˇ2
ˇ e´ξ pH pw1 , w2 qq dµab pw1 qˇ is bounded away from 1 uniformly in ξ
and w2 .


Lemma 7. Let µ be a measure on R2 of compact support, with support
generating a subgroup of R2 of full dimension. If µ is lattice supported,
assume that the co-volume of the lattice is at least 1. There is a constant
Y ]
1
c “ cpµq ą 0 such that, uniformly in 0 ă ξ ď 2 , for N “ Npξq “ 2ξ1 ,
(37)

ˇż
ˇ
ˇ
ˇ

R2 ˆR2

˚

e´ξ pH pw1 , w2 qq dµ

˚N

pw1 qdµ

˚N

ˇ
ˇ
pw2 qˇˇ ď 1 ´ cpµq.

Proof. When µ is lattice with lattice of covolume V , the measure
H ˚ pw1 , w2 qdµpw1qdµpw2q is lattice distributed with step size V . Hence
the bound on |ξ| suffices to guarantee the claim for N bounded.
For N growing, a standard application of the functional central limit
theorem implies that N1 H ˚ pw1 , w2 qdµ˚N pw1 qdµ˚N pw2 q converges to a
non-zero density on R as N Ñ 8.

Normalize Haar measure on HpRq to be given in coordinates by
dg “ dxdydz. The density of a Gaussian measure ν on HpRq can
be understood as the rescaled limit of the density of a random walk
with independent Gaussian inputs in the abelianization. Consider the
distribution on the Heisenberg group given by ν2,σ “ rηp0, σq, 0s, which
has projection to the abelianization given by a two dimensional normal distribution of covariance σ, and with trivial central fiber. Write
ν2 “ ν2,I2 for the measure in which σ is the two dimensional identity
matrix. The rescaled distribution d ?1 ν2˚N converges to a Gaussian
N
measure ν0 on HpRq as N Ñ 8. Note that we have not included a
covariance term, which can be accommodated with a linear change of
coordinates. Also, we do not consider
? randomness in the central coordinate as it would scale only as N, whereas the central coordinate
has distribution at scale N.
Let α P R2 and ξ P R. Write the modified characteristic function of
)
ν0 as (recall z̃ “ z ´ xy
2
ż
(38)
Ipα, ξq “
e´α pgab qe´ξ pz̃qdν0 pgq
g“rx,y,zsPG

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

and
(39)

Ipα, ξ; Nq “

ż

pR2 qN

e´α

ˆ

x
?
N

˙

e´ξ

ˆ

H ˚ pxq
N

˙

11

bN
dν2,ab
pxq .

Lemma 8. Let α P R2 , ξ P R and let σ 2 be the covariance matrix of
a non-degenerate two dimensional normal distribution of determinant
δ 2 “ det σ 2 , δ ą 0. Then
ˆ
˙
ˆ ˚ ˙
ż
x
H pxq
e´α ?
e´ξ
dηp0, σqbN pxq “ Ipσα, δξ; Nq.
(40)
N
N
pR2 qN
Proof. Making ´the change
¯ of variables, for each i, σyi “ xi in the
xti σ´2 xi
1
changes x “ σy and H ˚ pxq “ det σ ¨ H ˚ pyq.
density 2πδ exp ´ 2

In view of the multiplication rule (31), for }α}, |ξ| “ Op1q
(41)

lim Ipα, ξ; Nq Ñ Ipα, ξq.

N Ñ8

The following rate of convergence is given in Appendix A.
Theorem 9. For all α P R2 , ξ P R such that p1 ` }α}2qp1 ` ξ 2 q ă N,
´
¯
2
2
1 ` O p1`}α}Nqp1`ξ q
¯
´
.
(42)
I pα, ξ; Nq “
2π}α}2
exp ξ coth πξ cosh πξ
In particular,
(43)

Ipα, ξq “

´
¯
2
exp ´ ξ2π}α}
coth πξ
cosh πξ

.

Remark. While Ipα, ξq characterizes the Gaussian measure, it does not
behave well under convolution.
Along with the above characteristic function calculation the following
moment calculation is used.
Lemma 10. Let η be a two dimensional Gaussian with identity covariance. For each k ě 1, and N ě 2,
(44)

“
‰
N 2k
EηbN H ˚ pwq2k ď µ22k 2k
2

where µ2k “ p2kq!
is the 2kth moment of a standard one dimensional
2k k!
Gaussian.
For any compactly supported probability measure µ of mean zero on
2
R , for any k ě 1, as N Ñ 8,
‰
`
˘
“
(45)
EµbN H ˚ pwq2k ď Ok,µ N 2k .

12

PERSI DIACONIS AND BOB HOUGH

Proof. Write
H ˚ pwq “

(46)

1 ÿ
p1q p2q
p´1q1piąjq wi wj
2 1ďi‰jďN

and expand the moment to find
“
‰
(47) EηbN H ˚ pwq2k
ﬀ
«
ÿ
1
p1q
p1q
wm
¨ ¨ ¨ wm
wnp2q1 ¨ ¨ ¨ wnp2q2k
ď 2k EηbN
1
2k
2
1ďm1 ,...,m2k ,n1 ,...,n2k ďN
ﬀﬀ2
«
«
ÿ
1
p1q
p1q
wm
¨ ¨ ¨ wm
“ 2k EηbN
1
2k
2
1ďm ,...,m ďN
1

2k

2k

N
.
22k
When treating general µ of compact support,
(48)
‰
“
EµbN H ˚ pwq2k
ﬀ
«
ÿ
1
p1q
p1q
“ 2k EµbN
¨ ¨ ¨ wm
wnp2q1 ¨ ¨ ¨ wnp2q2k .
εm,n wm
1
2k
2
1ďm ,...,m ,n ,...,n ďN
“ µ22k

1

2k

1

2k

with εm,n P t´1, 0, 1u. The expectation vanishes unless each index in
rNs which appears among m1 , ..., m2k , n1 , ..., n2k appears at least twice.
There are OpN 2k q ways to choose which indices appear and Ok p1q ways
to assign m1 , ..., n2k to the indices which appear. For those assignments
which don’t vanish, the expectation is Ok,µp1q by the compact support.

We make the following convention regarding rare events. Say that
a sequence of measurable events tAN uN ě1 such that AN Ă S N occurs
with high probability (w.h.p.) if the complements satisfy the decay
estimate,
`
˘
(49)
@ C ě 0,
µbN pAcN q “ OC N ´C

as N Ñ 8. The sequence of complements is said to be negligible. A
sequence of events tAN u which is negligible for µbN is also negligible
when µbN is conditioned on a non-negligible sequence of events tBN u.

2.1. The large spectrum. Let µ be a mean 0, compactly supported
probability measure on R2 . For 0 ă ϑ ă 1, define the large spectrum
of µ̂ to be
(
(50)
Specϑ pµq “ α P R2 : |µ̂pαq| ą 1 ´ ϑ

and let
(51)

Mϑ pµq “ tα P Specϑ pµq : |µ̂pαq| is a local maximumu.

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

13

Let
µ̌pAq “ µptx´1 : x P Auq

(52)

and set µ2 “ µ˚ µ̌. The measure µ2 is still mean 0, compactly supported
and satisfies
ż
(53)
µ̂2 pαq “
cosp2πα ¨ xqdµ2 pxq “ |µ̂pαq|2 ,
R2

so Specϑ pµq “ Spec2ϑ´ϑ2 pµ2 q and Mϑ pµq “ M2θ´θ2 pµ2 q.
For a differential operator Dβ “ Di1 Di2 ¨ ¨ ¨ Diℓ , set |β| “ ℓ.

Lemma 11. Let 0 ď ϑ ď 1, let α P Specϑ pµ2 q and let Dβ be a differential operator. Then
#
´ 1¯
Oβ ϑ 2
|β| odd
(54)
Dβ µ̂2 pαq “
.
Dβ µ̂2 p0q ` Oβ pϑq
|β| even
Proof. Let Dβ “ Di1 ¨ ¨ ¨ Diℓ . Differentiating under the integral, if ℓ is
odd then
ż
1pℓ”1 mod 4q
ℓ
xi1 ¨ ¨ ¨ xiℓ sinp2πα ¨ xqdµ2 pxq
(55) Dβ µ̂2 pαq “ p´1q
p2πq
R2

so that, using the compact support of µ2 and then Cauchy-Schwarz,
ż
(56)
|Dβ µ̂2 pαq| !ℓ
| sinp2πα ¨ xq|dµ2 pxq
2
ż Ra
“
1 ´ cos2 p2πα ¨ xqdµ2 pxq
R2

ď
If ℓ is even, then

ˆż
ℓ
2

2

R2

1 ´ cos p2πα ¨ xqdµ2 pxq

(57) Dβ µ̂2 pαq “ p´1q p2πq

ℓ

ż

˙ 21

1

ď p2ϑq 2 .

xi1 ¨ ¨ ¨ xiℓ cosp2πα ¨ xqdµ2 pxq
ż
ℓ
ℓ
xi1 ¨ ¨ ¨ xiℓ p1 ´ cosp2πα ¨ xqqdµ2 pxq.
“ Dβ µ̂2 p0q ´ p´1q 2 p2πq
R2

R2

Again using the compact support, the integral in the last line is Opϑq.

The previous lemma has the following consequences.
Lemma 12. There is a constant C1 “ C1 pµq, 0 ă C1 ă 1 such that if
0 ă ϑ ă C1 then the following hold:
i. There are constants C2 pµq, C3 pµq ą 0 such that if α0 P Mϑ pµ2 q
and }α ´ α0 } ă C2 then
(58)

µ̂2 pαq ď µ̂2 pα0 q ´ C3 }α ´ α0 }2 .

14

PERSI DIACONIS AND BOB HOUGH

ii. There is a constant C4 pµq ą 0 such that if α P Specϑ pµ2 q then
there exists α0 P Mϑ pµ2 q with
?
(59)
}α ´ α0 } ď C4 ϑ.

Furthermore, if µ does not have a lattice component, then there is a
growth function F pϑq tending to infinity as ϑ Ó 0 such that, if α0 ‰ α1
are distinct elements of Mϑ pµ2 q then
}α0 ´ α1 } ą F pϑq.

(60)

Proof. To prove i., Taylor expand about α0 using that the first derivatives vanish and that the third derivatives of µ̂2 are uniformly bounded.
The term from the second degree Taylor expansion may be replaced
with the corresponding term at α0 “ 0, making an error which is Opϑq.
This may be absorbed into the constant C3 by making C1 sufficiently
small.
To prove ii., first reduce C1 pµq to guarantee that there is a ball
Bδ pαq, 0 ă δ ă 1 a fixed constant, such that the maximum of µ̂2 does
not occur on the boundary of the ball. This may be achieved by Taylor
1
expanding about α, which now includes a linear term, which is Opϑ 2 q.
Let α0 be the global maximum in the interior, and now
? apply part i.
and µ̂2 pα0 q ´ µ̂2 pαq ď ϑ to conclude that }α ´ α0 } ! ϑ.
To prove the final statement, note that for 0 ď ϑ ď 14 , if α0 , α1 P
Specϑ pµ2 q then α0 ´ α1 P Spec4ϑ pµ2 q, see [27], p. 183. An easier proof
is possible here since the spectrum is positive, indeed,
ż
(61)
1 ´ µ̂2 pα0 ´ α1 q “
1 ´ cosp2πα0 ¨ xq cosp2πα1 ¨ xqdµ2
R2
ż
´
sinp2πα0 ¨ xq sinp2πα1 ¨ xqdµ2 .
R2

Bound the first integral by
(62)
ż
ż
1 ´ cosp2πα0 ¨ xqdµ2 `
R2

R2

cosp2πα0 ¨ xqp1 ´ cosp2πα1 ¨ xqqdµ2 ď 2ϑ.

By Cauchy-Schwarz, the second integral is bounded in size by
ˆż
˙ 21
ż
2
2
(63)
1 ´ cos p2πα0 ¨ xqdµ2
1 ´ cos p2πα1 ¨ xqdµ2
ď 2ϑ.
R2

0.

R2

The claim now follows on considering µ̂2 pαq in growing balls about


The following lemma gives information about variation of the phase
of µ̂pαq in the large spectrum.
Lemma 13. Let µ be a measure of mean 0 and compact support on
R2 , let 0 ď ϑ ď 21 and let α0 P Mϑ pµq. The following hold.
i. Im Di log µ̂pα0 q “ Oµ pϑq

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

15

?
ii. Im Di Dj log µ̂pα0 q “ Oµ p ϑq.
iii. For all α P Spec 1 pµq,
2

Im Di1 Di2 Di3 log µ̂pαq “ Op1q.

(64)

Proof. Let µ̂pα0 q “ eα0 pφ0 q|µ̂pα0 q|.
For i.
ż
Di µ̂pα0 q
2πi
(65)
Di log µ̂pα0 q “
xi eα0 px ´ φ0 qdµpxq.
“
µ̂pα0 q
|µ̂pα0 q| R2
Since µ is mean 0,
ż
2π
(66) Im Di log µ̂pα0 q “
xi pcosp2πα0 ¨ px ´ φ0 qq ´ 1qdµpxq.
|µ̂pα0 q| R2
By the compact support,
ż
(67)
| Im Di log µ̂pα0 q| !
1 ´ cosp2πα0 ¨ px ´ φ0 qqdµpxq
R2

“ 1 ´ |µ̂pα0 q| ď ϑ.

For ii., write
(68)

Di Dj log µ̂pα0 q “

Di Dj µ̂pα0 q Di µ̂pα0 qDj µ̂pα0 q
´
.
µ̂pα0 q
µ̂pα0 q2

i µ̂pα0 q
The subtracted term is real since Dµ̂pα
is imaginary (α0 is a maximum
0q
for |µ̂pα0 q|). Hence, again using the compact support and CauchySchwarz,

(69)

ż
´4π 2
xi xj sinp2πα0 ¨ px ´ φ0 qqdµpxq
Im Di Dj log µ̂pα0 q “
|µ̂pα0 q| R2
ż a
!
1 ´ cos2 p2πα0 ¨ px ´ φ0 qqdµpxq
R2

!

ˆż

R2

1 ´ cosp2πα0 ¨ px ´ φ0 qqdµpxq

˙ 21

1

ď ϑ2.

To obtain iii., note that the first three derivatives of µ̂ are bounded
due to the compact support.

The results of this section are collected into the following lemma
which permits approximating µ̂pαq in neighborhoods of a local maximum for |µ̂pαq|.

Lemma 14. Let µ be a probability measure on Rn of covariance matrix
σ 2 . There is a constant C “ Cpµq ą 0 such that for all 0 ď ϑ ď C and
for all α0 P Mϑ pµq we have
`
˘
(70)
µ̂pα0 ` αq “ µ̂pα0 qEreα pXqs ` O ϑ}α} ` }α}3
with X distributed as ηp0, σq.

16

PERSI DIACONIS AND BOB HOUGH

0 `αq
in a ball of constant radius about
Proof. Taylor expand log µ̂pα
µ̂pα0 q
α “ 0 to find
¯
´
1
µ̂pα0 ` αq
1 t
2
3
2
(71)
log
“ α H0 α ` O ϑ}α} ` ϑ }α} ` }α} ,
µ̂pα0 q
2

with H0 the Hessian of log µ̂pαq at 0. In making this expansion, we’ve
used the estimates for derivatives of µ̂2 pα0 ` αq in Lemma 11 together
with
(72)

Re log

µ̂pα0 ` αq
1
µ̂2 pα0 ` αq
“ log
µ̂pα0 q
2
µ̂2 pα0 q

and the estimates for derivatives of Im log µ̂pα0 ` αq in Lemma 13.
1
Then (we’ve absorbed the ϑ 2 }α}2 error term into the others)
`
˘
(73)
µ̂pα0 ` αq “ µ̂pα0 qEreα pXqs ` O ϑ}α} ` }α}3 .

Since µ̂ is bounded, this formula holds for all α by adjusting the constants appropriately.

3. Proof of Theorem 2

We first treat Theorem 2 which is illustrative of the main idea, before proving Theorem 1. Identify n “ pn1 , n2 , n3 qt P Z3 , with gn “
rn1 , n2 , n3 s P HpZq and let ν be the limiting Gaussian measure under
convolution by µ.
Proposition 15. For each n “ pn1 , n2 , n3 qt P Z3 ,
¯
´
¯
5
1 dν ´
d ?1 gn ` O N ´ 2 .
(74) PN pn1 , n2 , n3 q :“ µ˚N ptgn uq “ 2 ¨
N
N dg
Recalling the multiplication rule

N ”
ı „
ź
p1q
p2q
p1q
p2q 1 p1q p2q
˚
(75)
wi , wi , 0 “ w , w , w w ` H pwq ,
2
i“1

which is valid for wi “ r˘1, 0, 0s or r0, ˘1, 0s, it suffices to calculate,
with UN standing for the product measure µbN and expectation with
respect to UN ,
(76)

ˆ
˙
1
t
˚
UN w ab “ pn1 , n2 q , H pwq “ n3 ´ n1 n2 “
2
ż
ı
¯
”
´
`
˘
n1 n2
E eα pw ab qeξ pH ˚pwqq dξdα.
eα pn1 , n2 qt eξ n3 ´
2
pR{Zq3

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

17

3.1. Reduction to a central limit theorem. The following two lemmas reduce to a quantitative central limit theorem by truncating frequency space to the scale of the distribution.
Lemma 16. For any A ą 0 there is C “ CpAq ą 0 such that if
N
}ξ}R{Z ě C log
, for all α P R2 ,
N
|EUN reα pwab q eξ pH ˚ pwqqs| ď N ´A .

(77)

Proof. Choose k “ kpξq according to the rule
#
1
,
|ξ| ą 10
Y1, ]
.
(78)
kpξq “
1
1
,
|ξ| ď 10
2|ξ|

XN \
1
Let N 1 “ 2k
. The group Gk “ C2N acts on strings of length N with
jth factor exchanging the order of the substrings of length k ending at
p2j ´ 1qk and 2jk.
Given string w, write ŵ for the string of length 2N 1 with jth entry
given by
ŵj “

(79)
Write
(80)

˚

H pwq “

Hk1 pwq

`

k
ÿ

i“1

Hk2 pwq,

wpj´1qk`i .

Hk2 pwq

“

N1
ÿ

j“1

H ˚ pŵ2j´1, ŵ2j q .

Both w ab and Hk1 are invariant under Gk . Exchanging the order of the
expectations, which is justfied because the group action is finite,
(81)
EUN reα pw ab q eξ pH ˚ pwqqs “ Eτ PGk rEUN reα pw ab q eξ pH ˚ pτ ¨ wqqss
“
`
“ `
˘
˘‰‰
“ EUN eα pw ab qeξ Hk1 pwq Eτ PGk eξ Hk2 pτ ¨ wq ,

and, therefore,
(82)

“ `
˘‰ˇ‰
“ˇ
|EUN reα pwab qeξ pH ˚ pwqqs| ď EUN ˇEτ PGk eξ Hk2 pτ ¨ wq ˇ .

By Cauchy-Schwarz,
(83)
”ˇ
“ `
“ `
˘‰ˇ‰2
˘‰ˇ2 ı
“ˇ
EUN ˇEτ PGk eξ Hk2 pτ ¨ wq ˇ ď EUN ˇEτ PGk eξ Hk2 pτ ¨ wq ˇ .

One checks, using the product group structure,
˙
N1 ˆ
ˇ
“ ` 2
˘‰ˇ2 ź
1 ` cos p2πξH ˚pŵ2j´1, ŵ2j qq
ˇ
ˇ
,
(84) Eτ PGk eξ Hk pτ ¨ wq
“
2
j“1

18

PERSI DIACONIS AND BOB HOUGH

and hence, since the coordinates in w are i.i.d.,
”ˇ
“ `
˘‰ˇ2 ı
(85)
EUN ˇEτ PGk eξ Hk2 pτ ¨ wq ˇ
ˆ
˙N 1
1 ` EUN rcos p2πξH ˚pŵ1 , ŵ2 qqs
“
.
2

By Lemma 7 the expectation in the cosine is uniformly bounded in size
by 1 ´ cpµq for some cpµq ą 0. The claim is completed by using the
1
1

estimate p1 ´ xqN ď e´N x , which is valid for 0 ď x ď 1.
The following lemma obtains cancellation in α.
N
Lemma 17. Let A, ǫ ą 0 and 0 ď }ξ}R{Z ď C log
where C is as in
N
1
Lemma 16. For all N sufficiently large, if }α}R2{Z2 ě N ǫ´ 2 , then

EUN reα pwab q eξ pH ˚pwqqs ď N ´A .

(86)

Proof. Let N 1 “ tN 1´ǫ u. Let w0 be w truncated at N 1 and let wt be
the remainder of w so that w is the concatenation w0 ‘ wt . Write
(87)

to bound
(88)

H ˚ pwq “ H ˚pw 0 q ` H ˚ pw0 , wt q ` H ˚pw t q

|EUN reα pw ab q eξ pH ˚ pwqqs|
”ˇ
‰ˇˇı
“
ˇ
ď Ewt „µbpN´N 1 q ˇEw0 „µbN 1 eα pw 0,ab qeξ pH ˚ pw0 q ` H ˚ pw0 , wt qq ˇ .
?
Truncate the outer integral to }wt } ď N log N, which holds w.h.p.
Let Ek pxq denote the degree k Taylor expansion of e1 pxq about 0, and
recall that the integral form of Taylor’s theorem gives
ˇ
ˇ
ż1
k
ˇ p2π|x|qk`1
ˇ
p1
´
tq
k`1
(89) |e1 pxq ´ Ek pxq| “ ˇˇp2πxq
e1 pxtqdtˇˇ ď
.
k!
pk ` 1q!
0

Use Lemma 10 to choose k “ kpA, ǫq be odd and sufficiently large so
that
(90)

Ew0 „µbN 1 r|Ek pξH ˚ pw0 qq ´ eξ pH ˚ pw0 qq|s

‰
“
p2π|ξ|qk`1
Ew0 „µbN 1 |H ˚ pw 0 q|k`1
pk ` 1q!
1
ď Ok,µ p|ξ|Nqk`1 ď
.
2N A
It thus suffices to estimate
ﬀ
«
˘
`
(91)
EUN 1 eα w0,ab eξ pH ˚ pw0 , wt qq Ek pξH ˚pw0 qq .
ď

Expand Ek into PolypNq terms, each depending on boundedly many
indices from w 0 . Expectation over the remaining terms factors as a

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

19

product which is exponentially small in a power of N, hence negligible.

3.2. Quantitative Gaussian approximation. In the range }α} ď
1
N ǫ´ 2 , |ξ| ! logNN , expectation with respect to µ is replaced with expectation taken over a measure with projection to the abelianization
given by a Gaussian of the same covariance matrix as µab . The modified characteristic function in the Gaussian case is evaluated precisely
in Theorem 9, which finishes the proof.
Let σ 2 be the covariance matrix of µab and let ηp0, σq be a centered
Gaussian of the same covariance. Set δ “ det σ. Taylor expand log µ̂pβq
about β “ 0 to find a cubic map T pβq such that
`
˘
(92)
µ̂ab pβq “ η̂pβq p1 ` T pβqq ` O }β}4 .
In the phase eα pwab q eξ pH ˚pwqq let
«
ﬀt
ÿ
ξ ÿ
p2q
p1q
p´1q1piăjqwi , p´1q1piąjqwi
(93)
αj pwq “ α `
2 i‰j
i‰j

so that αj pwq ¨ wj is the part which depends on wj . The Gaussian
replacement scheme is as follows.
Lemma 18. Let 0 ă ǫ ă
N
,
and |ξ| ď C log
N

1
2

1

and C ą 0 be constants. For }α} ď N ǫ´ 2

´?
¯
`
˘
(94) EUN reα pw ab q eξ pH pwqqs “ I
N σ ¨ α, Nδξ ` O N ´1`Opǫq
«
˜
¸ﬀ
ÿ
` EηbN eα pwab q eξ pH ˚ pwqq
.
T pαj pwqq
˚

j

¯
Proof. Since EηbN reα pwab qeξ pH pwqqs “ I N σα, Nδξ; N , and since
in the stated range of α, ξ,
´ 1
¯
´ 1
¯
`
˘
2
2
(95)
I N σα, Nδξ; N “ I N σα, Nδξ ` O N ´1`Opǫq
˚

´

1
2

by Theorem 9, it suffices to prove
(96)

`
˘
EUN reα pwab q eξ pH ˚ pwqqs ` O N ´1`Opǫq
«
˜
¸ﬀ
ÿ
“ EηbN eα pwab q eξ pH ˚ pwqq 1 `
T pαj pwqq
.
j

For convenience, write
(97)
and, for k ‰ j,
(98)

Tj pα, ξ, wq “ T pαj pwqq
Tj pα, ξ, wq “ Tjk pα, ξ, wq ` T̂jk pα, ξ, wq

20

PERSI DIACONIS AND BOB HOUGH

in which Tjk collects monomials in Tj which depend on wk , and T̂jk
collects monomials which don’t depend on wk .
Since the expectation does not depend upon the third coordinate,
write µbN
ab in place of UN . For 0 ď j ď N consider the measure
bpN ´jq
µj “ µbj
in which the first j coordinates are i.i.d. with
ab b η
measure µab and last N ´ j coordinates are independent of the first j
and are i.i.d. η.
We prove (96) iteratively by showing that, for each k ě 1,
(99)

«

˜

Sk :“ Eµk eα pwab qeξ pH ˚ pwqq 1 `

ÿ

jąk

Tj pα, ξ, wq

¸ﬀ

˜
¸ﬀ
ÿ
` ´2`Opǫq ˘
Tj pα, ξ, wq
“O N
` Eµk´1 eα pw ab qeξ pH ˚ pwqq 1 `

`
˘
“ O N ´2`Opǫq ` Sk´1 ,

«

jąk´1

`
˘
which suffices since (96) may be written as |SN ´ S0 | “ O N ´1`Opǫq .
By the triangle inequality, and setting apart expectation in the kth
variable as the inner integral,
(100)
|Sk ´ Sk´1 |

ˇż
ˇ
ˇ
ˇ
ď Eµbpk´1q bηbpN´kq ˇˇ
eαk pwq pwk qpdµab ´ p1 ` Tk pα, ξ, wqq dηqˇˇ
ab
ˇż wk
ˇ
¸
˜
ˇ
ˇ
ÿ
ˇ
ˇ
` Eµbpk´1q bηbpN´kq ˇ
eαk pwq pwk q
Tj pα, ξ, wq pdµab ´ dηqˇ .
ab
ˇ wk
ˇ
jąk

In the first line of the right hand side, note that Tk pα, ξ, wq does not
depend on wk , so that Taylor expanding the exponential obtains a
bound of Op}αk pwq}4 q, which suffices since
“
‰
`
˘
(101)
Eµbpk´1q bηbpN´kq }αk pwq}4 “ O N ´2`4ǫ .
ab

In the second line, write Tj “ Tjk ` T̂jk . Since T̂jk does not depend on
wk , matching the first two moments of µab and η gives

(102)

ˇ
ˇż
˜
¸
ˇ
ˇ
ÿ
ˇ
ˇ
k
T̂j pα, ξ, wq pdµab ´ dηqˇ
Eµbpk´1q bηbpN´kq ˇ
epαk pwq ¨ wk q
ab
ˇ
ˇ wk
jąk
ˇ
ˇﬀ
«
ˇÿ
ˇ
ˇ
ˇ
! Eµbpk´1q bηbpN´kq }αk pwq}3 ˇ T̂jk pα, ξ, wqˇ ! N ´2`6ǫ .
ab
ˇjąk
ˇ

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

21

Finally, to bound the terms from Tjk , Taylor expand epαk pwq ¨ wk q to
degree 2 to bound
(103)

ˇż
ˇ
˜
¸
ˇ
ˇ
ÿ
ˇ
ˇ
epαk pwq ¨ wk q
Eµbpk´1q bηbpN´kq ˇ
Tjk pα, ξ, wq pdµab ´ dηqˇ
ab
ˇ wk
ˇ
jąk
ˇ
ˇż
ˇ
ˇ
ÿ
ˇ
ˇ
k
p1 ` 2πiαk pwq ¨ wk q
Tj pα, ξ, wqpdµab ´ dηqˇ
! Eµbpk´1q bηbpN´kq ˇ
ab
ˇ
ˇ wk
jąk
ˇ
ˇ
ż
ˇÿ
ˇ
ˇ
ˇ
}αk pwq}2 |wk |2 ˇ Tjk pα, ξ, wqˇ pdµab ` dηq.
` Eµbpk´1q bηbpN´kq
ab
ˇjąk
ˇ
wk

Since the first two moments of µab and η match, the only terms which
survive the first line here are degree 3 in wk , and these contribute
OpN ´2`3ǫ q. In the second line here, keeping in mind that Tjk contains
p1q
p2q
only monomials that have a factor of ξwk or ξwk , one obtains a bound
of OpN ´2`5ǫ q by applying Cauchy-Schwarz to separate the integrands.
This completes the iterative estimate (99).

We give two estimates for the error term
«
˜

(104)

T “ EηbN eα pw ab qeξ pH ˚ pwqq

ÿ
j

T pαj pwqq

¸ﬀ

depending on the relative sizes of α and ξ. In this part of the argument
we assume that ηp0, σq has identity covariance, which may be achieved
by rescaling α and ξ by constant factors.
1

Lemma 19. There exists c ą 0 such that, for }α} ď N ǫ´ 2 and |ξ| !
log N
,
N
¯
´
5
3
3
2
(105)
T “ O N}α} ` N |ξ| exp p´cN|ξ|q .
Proof. Bound each term
(106)

EηbN reα pwab qeξ pH ˚pwqqT pαj pwqqs

individually by setting
(107)

k“

$ Y ]
1
’
,
& 2|ξ|
’
% XN \
2

,

|ξ|N ą 1
otherwise

and allowing Gk to act as in Lemma 16. Let G1k be the subgroup
omitting the factor that moves wj . Then G1k leaves T pαj pwqq invariant,
so that
‰
“
p106q “ EηbN eα pwab qEτ PG1k reξ pH ˚pτ ¨ wqqsT pαj pwqq .

22

PERSI DIACONIS AND BOB HOUGH

By Cauchy-Schwarz,

“
‰
|p106q|2 ď EηbN |Eτ PG1k reξ pH ˚pτ ¨ wqqs|2 EηbN r|T pαj pwqq|2 s.

Arguing as in Lemma 16 now obtains the estimate, for some c ą 0,
¯
´
5
(108)
|p104q| ! N}α}3 ` N 2 |ξ|3 exp p´c|ξ|Nq .



To ř
obtain decay in }α} instead of |ξ|, consider the degree 3 polynomial j T pαj pwqq which consists of monomials of which
i. Those constant in w and cubic in α have absolute sum of coefficients OpNq.
ii. Those linear in ξw and quadratic in α have absolute sum of
coefficients OpN 2 q.
iii. Those quadratic in ξw and linear in α have absolute sum of
coefficients OpN 3 q. Of these, those with a repeated factor from
w have absolute sum of coefficients OpN 2 q.
iv. Those that are cubic in ξw have absolute sum of coefficients
OpN 4 q. Of these, those with a repeated factor from w have
absolute sum of coefficients OpN 3 q.
Write M for the typical monic monomial, so that M is of form
(109)

pǫ q

pǫ q

pǫ q

pǫ q

pǫ q

pǫ q

1, wi1 1 , wi1 1 wi2 2 , wi1 1 wi2 2 wi3 3

with ǫj P t1, 2u, according as the case is i., ii., iii. or iv.. Given a
typical monomial M of T , write ωpMq for the number of variables
from w which are odd degree in M.
Lemma 20. There is a constant c ą 0 such that, for 0 ă |ξ| !
a
1
and |ξ| ď }α} ď N ǫ´ 2 ,
„
`
˘
(110)
T “ O }α}p1 ` N}α}2 qp1 ` N 3 |ξ|3 q
ˆ ˆ
ˆ
˙˙˙
1
2
ˆ exp ´c }α} min N,
.
N|ξ|2
Proof. Consider the expectation
(111)

log N
N

EM “ EηbN rMeα pwab q eξ pH ˚ pwqqs .

We show that, for some c ą 0,

ˆ ˆ
ˆ
2
exp ´c }α} min N,

˙˙˙
1
(112)
EM ! }α}
,
N|ξ|2
which suffices on summing over the monomials described in i. through
iv. above.
Let c1 ą 0 be a small constant, and let
# Y ]
c1
,
N|ξ| ą c1
|ξ|
(113)
N1 “
.
N,
otherwise
ωpM q

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

23

Let w0 be the initial string of w of length N 1 and assume that this
includes any variables from M; the general case may be handled by a
straightforward modification. Write w “ w 0 ‘ wt so that wt contains
the remaining variables. Write
H ˚ pwq “ H ˚ pw0 q ` H ˚pw 0 , wt q ` H ˚ pwt q.
ıt
”
p2q
p1q
ξ
Write α̂ “ α ` 2 wt , ´wt . Bound
ˇı
”ˇ
ˇ
ˇ
˚
1
1
(115)
|EM | ď Ewt „ηbpN´N q ˇEw0 „ηbN rMeα̂ pw0 q eξ pH pw 0 qqsˇ .

(114)

Expand eξ pH ˚ pw 0 qq in Taylor series to degree L :“ tN 2ǫ u. The error
in doing so is bounded by
“
‰
p2π|ξ|qL`1
Ew0 „ηbN 1 |M||H ˚ pw0 q|L`1 .
(116)
pL ` 1q!
Apply Cauchy-Schwarz to remove the monomial M, then insert the
moment bound of Lemma 10 to estimate this by
“
‰1
p2π|ξ|qL`1
(117)
!
Ew0 „ηbN 1 H ˚ pw0 q2L`2 2
pL ` 1q!
p2π|ξ|qL`1 p2L ` 2q!
ď
pN 1 qL`1
2L`2
pL ` 1q! pL ` 1q!2
ď p2π|ξ|N 1 qL`1 ď p2πc1 qL`1 .
1
then this is bounded by, for some c ą 0, exp p´cN 2ǫ q .
If c1 ă 2π
In the Taylor expansion, expectation over w 0 is bounded by

(118)
L
ÿ
“
‰ˇ
p2π|ξ|qℓ ˇˇ
EηbN 1 Meα̂ pw 0 qH ˚ pw0 qℓ ˇ
ℓ!
ℓ“0
L
ÿ
p2π|ξ|qℓ
ď
2ℓ ℓ!
ℓ“0

ÿ

m,nPrN 1 sℓ

ˇ
‰ˇ
“
ˇE bN 1 Meα̂ pw 0 qw p1q ¨ ¨ ¨ w p1q w p2q ¨ ¨ ¨ w p2q ˇ .
m1
mℓ n1
nℓ
η

The expectation factors as a product. Those indices of rN 1 s which
do not have a monomial factor contribute, for some c2 ą 0,
`
˘
`
˘
(119)
ď exp ´2π 2 pN 1 ´ 2ℓ ´ 3q}α̂}2 ď exp ´c2 N 1 }α̂}2 .

Let E (resp. O) be those indices in rN 1 s which appear a positive even (resp. odd) number of times among the factors in M and
m1 , ¨ ¨ ¨ , mℓ , n1 , ¨ ¨ ¨ , nℓ .
For indices which appear a positive even hj number of times, bound
|eα̂ pwj q| ď 1, so that the expectation is bounded by the hj th moment
of a 1-dimensional Gaussian,
hj !
(120)
µhj “ hj ´ ¯ .
h
2 2 2j !

24

PERSI DIACONIS AND BOB HOUGH

At indices which appear an odd hj number of times, set eα̂ pwj q “
1 ` Op}α̂}}wj }q. Expectation against 1 vanishes. The remaining expectation is bounded by
! }α̂}µhj `1 .

(121)

The configurations in which no index outside M appears with multiplicity greater than 2, and no more than one of the mj , nj fall on an
odd degree index of M and none fall on an even degree index of M,
make a dominant contribution. Call these base configurations. The
type of a base configuration is described by a triple pp, ℓ1 , ℓ2 q where p
indicates whether an index from m, n falls on each odd degree index
present in M, where ℓ1 counts the number of indices which appear
once, and ℓ2 counts the number of indices which appear twice. Let |p|
be the number of indices which fall on M. Thus
2ℓ “ |p| ` ℓ1 ` 2ℓ2 .

(122)

Let N pp, ℓ1 , ℓ2 q be the number of base configurations that have a given
type. There are
p2ℓq!
|p|!ℓ1 !ℓ2 !2ℓ2

(123)

ways to allot the 2ℓ indices of m, n to belong to p, the ℓ1 singletons or
ℓ2 doubles, and ! pN 1 qℓ1 `ℓ2 ways to place the indices in rN 1 s once they
have been so arranged, so that
N pp, ℓ1 , ℓ2 q !

(124)

p2ℓq!
pN 1 qℓ1 `ℓ2 .
ℓ
2
|p|!ℓ1 !ℓ2 !2

Given m, n of type pp, ℓ1 , ℓ2 q,
“
‰
p1q
p1q p2q
p2q
EηbN 1 Meα̂ pw 0 qwm
(125)
¨ ¨ ¨ wm
w
¨
¨
¨
w
n
n
1
1
ℓ
ℓ

ď expp´c2 N 1 }α̂}2 qOp1qℓ1 `ℓ2 }α̂}ωpM q´|p|`ℓ1 .

Indicating restriction of m, n to base configurations with a 1,
(126)
L
ÿ
p2π|ξ|qℓ
2ℓ ℓ!

ℓ“0

ÿ

m,nPrN 1 sℓ

! expp´c2 N 1 }α̂}2 q

ˆ

ÿ
p

8
ÿ

ℓ1 ,ℓ2 “0
|p|`ℓ1 even

1

ˇ
‰ˇ
“
p1q
p1q p2q
ˇE bN 1 Meα̂ pw 0 qwm
¨ ¨ ¨ wm
wn1 ¨ ¨ ¨ wnp2qℓ ˇ
η
1
ℓ

pπ|ξ|q

|p|`ℓ1 `2ℓ2
2

´

}α̂}ωpM q´|p|`ℓ1 p|p| ` ℓ1 ` 2ℓ2 q!
¯
OpN 1 qℓ1 `ℓ2 .
|p|`ℓ1 `2ℓ2
!ℓ1 !ℓ2 !2ℓ2
2

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

25

Bound
(127)

p|p| ` ℓ1 ` 2ℓ2 q!
4|p|`ℓ1 `2ℓ2
ℓ2 !
|p|`ℓ1 `2ℓ2 ´
¯
¯ ď ´
¯ .
´
ď
4
|p|`ℓ1 `2ℓ2
|p|`ℓ1 `2ℓ2
|p|`ℓ1
!ℓ1 !ℓ2 !
!
!
|p|!
2
2
2

If the constant c1 in (113) is chosen sufficiently small, then the sum over
ℓ2 converges to a bounded quantity and the sum over ℓ1 is bounded by
`
˘
(128)
! exp Op1q}α̂}2 |ξ|pN 1 q2 .
Since |ξ|N 1 ď c1 , if c1 is sufficiently small this obtains a bound,

(129)

´ c
¯´
¯
a
ωpmq
2
! exp ´ N 1 }α̂}2 }α̂}ωpmq ` }α̂}ωpmq´1 |ξ| ` ¨ ¨ ¨ ` |ξ| 2 .
2

This bound with α in place of α̂ obtains (112) for the dominant
terms, and hence bounds the dominant terms unless |ξ| " N1 . In the
remaining case, the bound is acceptable unless }α̂} ă c3 }α} for a small
constant c3 ą 0. In this case one obtains }ξwt } " }α}. Since wt is a
Gaussian with variance of order N ´ N 1 ă N, the´event }ξw
¯ t } " }α}
}α}2
occurs with wt -probability, for some c4 ą 0, ! exp ´c4 N ξ2 , which is
again satisfactory.
To obtain a bound for all configurations from the bound for base
ones, configurations with |O| “ ℓ1 , |E | “ ℓ2 may be enumerated by
adding a number k of double indices to an existing base configuration.
There are OpLqk ways of choosing the indices where the new doubles
will be added, OpLq2k ways of inserting the indices into the list m, n,
and the new indices make a gain in the calculated moments of OpLqk .
Meanwhile, a factor of |ξ|k is saved in the outer sum. Recall L ď N 2ǫ .
If ǫ ă 81 then the sum over k is Op1q for all N sufficiently large.

Proof of Theorem 2. Combining Lemmas 16 and 17 obtains, for any
A ą 0, 0 ă ǫ ă 41 , for some c ą 0
PN pn1 , n2 , n3 q ` OA pN

´A

q“

ĳ

eα
1

}α}ďN ǫ´ 2
N
|ξ|ď log
N

(130)

`

´
n1 n2 ¯
pn1 , n2 q eξ n3 ´
2
t

˘

” ´?
¯
ı
ˆ I
N σα, Nδξ ` O pEq dαdξ,

where the error term E satisfies the estimates of Lemmas ´18, 19¯and
5
20. Over the range of integration the error integrates to O N ´ 2 .

26

PERSI DIACONIS AND BOB HOUGH

Making a change of variables and extending the integral to R3 obtains
„
ˆ
˙
ż
´
¯
t
1
´ 25
´1 pn1 , n2 q
?
PN pn1 , n2 , n3 q ` O N
eα σ
“ 2 2
δ N R3
N
ˆ ˆ
n1 n2 ˙˙
1 n3 ´ 2
(131)
ˆ eξ
I pα, ξq dαdξ.
δ
N
The right hand side is the Gaussian density of theş limit theorem. To
4
obtain the return probability to 0, use δ 2 “ 25
and R3 Ipα, ξqdαdξ “ 41
in
ż
¯
´
1
´ 25
(132)
Ipα, ξqdαdξ ` O N
PN p0, 0, 0q “ 2 2
δ N R3
¯
´
25
´ 52
.
“
`
O
N
16N 2

4. Proof of Theorem 1, Cramér case
Theorem 1 treats measures for which the abelianized walk is nonlattice. In this case the fibered distribution is also dense in R, and
when the abelianized distribution satisfies the Cramér condition, the
fibered distribution does, also. We assume the Cramér condition in
this section and treat the general case in the next section. In this case,
after making an arbitrary translation on the left and right, the test
functions may be taken to be of the form
´
¯
xy
(133)
f prx, y, zsq “ F x ´ x0 , y ´ y0 , z ´
´ Ax ´ By ´ z0
2
where F is a Lipschitz function of compact support and x0 , y0 , z0 , A, B
are real parameters.
Let ρ be a smooth, compactly supported bump function on R3 , for
t ą 0, ρt pxq “ t3 ρptxq and Ft “ F ˚ ρt the convolution on R3 . Since F
is Lipschitz, }F ´ Ft }8 ! 1t as t Ñ 8. Set
´
¯
xy
(134) ft prx, y, zsq “ Ft x ´ x0 , y ´ y0 , z ´
´ Ax ´ By ´ z0 .
2
5

Choosing t “ tpNq “ N 2 ,

(135)
˚N

´

´ 52

¯

ż

`
F̂t pα, ξq
xf, µ y “ O N
pα,ξqPR3
A `
E
¯
˘ ´
xy
ˆ eα px ´ x0 , y ´ y0 qt eξ z ´
´ Ax ´ By ´ z0 , µ˚N dαdξ.
2
Using the decay of the Fourier transform of the bump function ρt ,
truncate the integral to }α}, |ξ| “ OpN Op1q q with admissible error.

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

27

Apply the multiplication rule (31) to write the central coordinate of
a product of group elements w as
xy
p3q
(136)
z̃ “ z ´
“ H ˚ pwq ` w̃ .
2
p3q

p3q

p3q

The mean of w̃ is N z̃. Let w̃0 “ w̃ ´ N z̃. Let α̃ “ α ´ ξ ¨ pA, Bqt .
Thus
(137)
A `
E
¯
˘ ´
xy
eα px ´ x0 , y ´ y0 qt eξ z ´
´ Ax ´ By ´ z0 , µ˚N “
ż 2
´
¯
`
˘
`
˘
p3q
eα ´px0 , y0 qt eξ N z̃ ´ z0
eα̃ pwab q eξ H ˚ pwq ` w̃0 dµbN .
HpRqN

argument
of Lemma 16 applies as before to truncate to |ξ| “
`The
˘
log N
O N . This uses Lemma 7 in the case |ξ| “ Op1q and Lemma 6
in the case |ξ| " 1. The argument of Lemma 17 applies as before to
1
truncate to }α̃} ! N ´ 2 `ǫ .
A small modification is needed to the application of Lemma 18 which
we now describe. Here one can now include in the measure µab a
third dimension corresponding the z̃ ´ z̃, and make η a 3 dimensional
Gaussian with the same covariance matrix. The Gaussian replacement scheme goes through essentially unchanged, the addition of the
third coordinate evaluated at the small frequency ξ making a negligible change; these terms do not need to be included in Tj pα̃, ξ, wq. The
main term becomes
´
”
¯ı
p3q
(138)
EηbN eα̃ pwab qeξ pH ˚ pwqqeξ w̃0
.
After a linear change of coordinates, the third coordinate is independent of the first two and α̃ is mapped to α1 “ α̃ ` Opξq. Hence
”
¯ı
´
p3q
(139)
EηbN eα̃ pwab qeξ pH ˚pwqqeξ w̃0
`
˘
“ 1 ` Opξ 2Nq EηbN reα1 pw ab qeξ pH ˚ pwqqs .

Note that, since }α1 }2 “ }α̃}2 ` Op}α̃}|ξ|q ` Op|ξ|2 q,
´
¯
1 }2
´ 1
¯ exp ´ δξ 2π}α
coth N δπξ
I N 2 σα1 , Nδξ “
(140)
cosh Nδπξ
´ 1
¯
“ I N 2 σ α̃, Nδξ p1 ` Op}α̃} ` |ξ|qq .
In the error term,
«

(141)

EηbN
´

ﬀ
´
¯ÿ
p3q
Tj pα̃, ξ, wq ,
eα̃ pw ab qeξ pH ˚ pwqqeξ w̃ 0

p3q

¯

j

the factor of eξ w̃0
may be removed by Taylor expanding to degree
1, so that this part of the argument is unchanged.

28

PERSI DIACONIS AND BOB HOUGH

To complete the argument, integrate as before
ż
@
D
˚N
t
(142)
f, µ
“
1 `ǫ F̂t pα, ξqeα p´px0 , y0 q qeξ pN z̃ ´ z0 q
´2
}α̃}!N
N
|ξ|! log
N

” ´ 1
¯
ı
´
¯
5
ˆ I N 2 σα1 , Nδξ ` OpEq dαdξ ` O N ´ 2 .

The argument is now completed essentially as before, to find
´
´
¯ @
¯
@
D @
D
D
5
5
(143) f, µ˚N “ ft , d?N ν ` O N ´ 2 “ f, d?N ν ` O N ´ 2 .
5. Proof of Theorem 1, general case

We now consider the case in which µab does not necessarily satisfy a
Cramér condition. In this section the test functions take the form
´
¯
xy
(144)
f prx, y, zsq “ F x ´ x0 , y ´ y0 , z ´
´ Ax ´ By ´ z0
2
with F continuous and of compact support. Since we ask only for an
asymptotic, it suffices by Selberg’s theory of band-limited majorants
and minorants [18] to assume that F takes the form
(145)

F prx, y, zsq “ φab px, yqφ3 pzq

with φab and φ3 functions with Fourier transform of compact support.
In this case, writing α̃ “ α ´ ξ ¨ pA, Bqt ,
ż
˘
@
D
`
˘ `
˚N
(146) f, µ
“
φ̂ab pαqφ̂3 pξqeα ´px0 , y0qt eξ N z̃ ´ z0
}α},|ξ|“Op1q
ż
´
¯
p3q
ˆ
eα̃ pwab q eξ H ˚ pwq ` w̃ 0 dµbN .
HpRqN

Argue as in Lemma 16 to truncate to |ξ| ! logNN . Since A and B are
unconstrained, a further difficulty is encountered in applying Lemma
17 to truncate α. Let ǫ ą 0. For |ξ| ! logNN and α̃ R SpecN ´1`ǫ pµab q,
Lemma 17 demonstrates that the integral over HpRqN is, for any A ą
0, OA pN ´A q. The following modification of Lemma 18 permits an
asymptotic evaluation of
”
´
¯ı
p3q
˚
(147)
EUN eα̃ pwab qeξ H pwq ` w̃ 0
at points α̃ in the large spectrum of µab , SpecN ´1`ǫ pµab q.

Lemma 21. Let µab have covariance matrix σ 2 and set δ “ detpσq.
P SpecN ´1`ǫ pµab q, |ξ| ! logNN , and let
Let 0 ă ǫ ă 41 , ϑ “ N ´1`ǫ , let α̃ ?
α0 P Mϑ pµab q satisfy }α̃ ´ α0 } ! ϑ. Then
´
”
¯ı
p3q
˚
EUN eα̃ pw ab qeξ H pwq ` w̃ 0
(148)
´
¯
´ 1
¯
1
“ O N ´ 2 `Opǫq ` µ̂ab pα0 qN I N 2 σpα̃ ´ α0 q, Nδξ .

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

29

´
¯
´
¯
p3q
p3q
Proof. Write eξ w̃0 “ 1 ` O |ξ|w̃0 . Since
ˇı
¯
´
” ˇ
ˇ p3q ˇ
´ 21 `ǫ
(149)
EUN |ξ| ˇw̃ 0 ˇ “ O N

it suffices to prove that
(150)

EUN reα̃ pw ab qeξ pH ˚ pwqqs
¯
´ 1
¯
´
N
´ 21 `Opǫq
2
.
“ µ̂ab pα0 q I N σpα̃ ´ α0 q, Nδξ ` O N

Let η “ ηp0, σq be a centered two dimensional Gaussian with covariance equal to that of µab . Let X be distributed according to η. Set
α “ α̃ ´ α0 . By Lemma 14,
(151)

µ̂ab pα0 ` αq “ µ̂ab pα0 qEη reα pXqs ` Opϑ}α} ` }α}3 q.

In analogy with Lemma 18, define
«
ﬀt
ÿ
ξ ÿ
p2q
p1q
(152)
αj pwq “ α `
p´1qδpiăjq wi , p´1qδpiąjq wi
.
2 i‰j
i‰j
bpN ´kq
Set, for 1 ď k ď N, µk “ µbk
. Also set w ab,k “
ab b η
and
‰
“
(153)
Sk “ Eµk eα pw ab qeα0 pwab,k qeξ pH ˚pwqq

řk

j“1 wj,ab

so that SN “ EUN reα̃ pwab qeξ pH ˚pwqqs and
´?
¯
´?
¯
`
˘
(154) S0 “ I
Nσα, Nδξ; N “ I
Nσα, Nδξ ` O N ´1`Opǫq .
Holding all but the kth variable fixed obtains
“
‰
(155) |Sk ´ µ̂ab pα0 qSk´1| ! Eµbpk´1q bηbpN´kq ϑ}αk pwq} ` }αk pwq}3
¯
´ab 3
“ O N ´ 2 `Opǫq .

The proof is now complete, since

´1
ˇ
ˇ
ˇ Nÿ
ˇ
ˇµ̂ab pα0 qk SN ´k ´ µ̂ab pα0 qk`1 SN ´k´1 ˇ
(156) ˇSN ´ µ̂ab pα0 qN S0 ˇ ď
k“0

ď

N
´1
ÿ
k“0

1

|SN ´k ´ µ̂ab pα0 qSN ´k´1 | ! N ´ 2 `Opǫq .


Proof of Theorem 1, general case. Let 0 ă ǫ ă 14 and let ϑ “ N ´1`ǫ .
By Lemma 12 there is a constant c1 “ c1 pµq such that
ď
Bc ϑ 21 pα0 q.
Specϑ pµab q Ă
α0 PMϑ

1

30

PERSI DIACONIS AND BOB HOUGH

Let supp φ̂ab Ă BR p0q. Define the set
+
#
ď
log N
(157) Ξgood “ ξ : |ξ| !
BR`c ϑ 21 pα0 q .
, ξ ¨ pA, Bqt P
1
N
α PM
0

ϑ

Assume that N is sufficiently large so that if α0 , α1 are distinct points
1
of Mϑ then }α0 ´ α1 } ě 2pR ` c1 ϑ 2 q. Given ξ P Ξgood let α0 pξq be the
nearest point to ξ ¨ pA, Bqt in Mϑ . Also, define
(
(158)
Aξ “ α P BR p0q : α̃ “ α ` ξ ¨ pA, Bqt P Specϑ pµab q .
By Lemma 12, |Aξ | ! N ´1`ǫ .
In the evaluation from above,
(159)
@

D
f, µ˚N ` OA pN ´A q
ż
ż
“

α:α̃PSpecϑ pµab q
reα̃ pwab qeξ pH ˚pwqqs dαdξ

ξPΞgood

ˆ EµbN

`
˘ `
˘
φ̂ab pαqφ̂3 pξqeα ´px0 , y0qt eξ N z̃ ´ z0

insert the asymptotic formula for the expectation from Lemma 21. The
error term here is bounded by
ż
ż
1
(160)
N ´ 2 `Opǫq dαdξ
N
ξ:|ξ|! log
N

ď

ż

ξPΞgood

αPBR p0q,
α̃PSpecϑ pµab q

¯
´
1
5
N ´ 2 `Opǫq |Aξ |dξ “ O N ´ 2 `Opǫq .

This leaves the main term
ż
ż
ξPΞgood

(161)

ˆI

´?

α:α̃PSpecϑ pµab q

`
˘ `
˘
φ̂ab pαqφ̂3 pξqeα ´px0 , y0 qt eξ N z̃ ´ z0

¯
Nσpα̃ ´ α0 pξqq, Nδξ dαdξ.

The contribution from the part of this integral where α0 pξq “ 0 contributes xf, d?N νy ` OpN ´A q, by extending the integral with the same
integrand to all of R3 , so it remains to bound the contribution from ξ
for which α0 pξq ‰ 0.
For a fixed ξ P Ξgood , the formula
¯
´
2
exp ´ ξ2π}α}
coth ξ
(162)
Ipα, ξq “
cosh πξ
gives that integration in α is bounded absolutely by
`
˘
ż ´?
¯
max N1 , |ξ|
.
(163)
I
N σpα̃ ´ α0 pξqq, Nδξ dα !
cosh Nπξ
α

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

31

The contribution of ξ P Ξgood for which α0 pξq ‰ 0 is bounded by
ż
maxp N1 , |ξ|q
(164)
dξ.
ξPΞgood ,α0 pξq‰0 cosh Nπξ
Since the integrand is decreasing, and since the α0 pξq are F pϑq spaced,
this is bounded by
˘
`
ˆ ˙
ż8
max N1 , |ξ|
1
1
dξ “ o
.
(165)
!
F pϑq 0 cosh Nπξ
N2



6. Random walk on Nn pZq, proof of Theorem 3
The case n “ 2 is classical so assume n ě 3.
Let M : Zn´1 Ñ Nn pZq be the map
¨
˛
¨
1 v p1q 0 ¨ ¨ ¨
0
p1q
v
..
˚
.
˚ 0 1 v p2q 0
˚ v p2q ‹
‹
˚ . .
˚
n´1
.
.
(166) M : Z
Q v “ ˚ .. ‹ ÞÑ ˚ ..
..
..
..
0
˝ . ‚ ˚
˝
pn´1q
0
0
1 v
v pn´1q
0 ¨¨¨
0
1

˛

‹
‹
‹
‹
‹
‚

Recall that, given m P Nn we write Zpmq for the upper right corner.
n´1 N
q the central coordinate
Given sequence of vectors v “ tvi uN
i“1 P pZ
satisfies the product rule
˜
¸
N
ź
ÿ
p1q p2q
pn´1q
(167)
Z
Mpvi q “
vi1 vi2 ¨ ¨ ¨ vin´1 .
i“1

Write
(168)

ZnN “

1ďi1 ăi2 ă...ăin´1 ďN

ÿ

p1q

1ďi1 ăi2 ă...ăin´1 ďN

pn´1q

ei1 b ¨ ¨ ¨ b ein´1

N
for the corresponding tensor. Zn,µ
denotes the measure on Z obtained
by pushing forward measure µ on Zn´1 via M to measure µ̃ on Nn pZq,
N
then obtaining xZ, µ̃˚N y. Equivalently, Zn,µ
is the distribution of ZnN
evaluated on N vectors vi drawn i.i.d. from µ.
Given a probability measure ν on Z and prime p, Cauchy-Schwarz
and Plancherel give
¸1
ˇ
ˇ ˜
ˇ
ÿ ˇ
ÿ ˇ ˆ ξ ˙ˇˇ2 2
ˇ
1
ˇνpx mod pq ´ ˇ ď
ˇν̂
ˇ
(169)
ˇ
ˇ
ˇ
ˇ
p
p
x mod p
0ıξ mod p

where
(170)

ν̂pαq “

ÿ

nPZ

e´α pnqνpnq.

32

PERSI DIACONIS AND BOB HOUGH

Theorem 3 thus reduces to the following estimate on the characteristic
N
function of Zn,µ
.
Proposition 22. Let n ě 3 and let µ be a measure on Zn´1 satisfying
the same conditions as in Theorem 3. There exists constant C ą 0
such that for all N ą 0 and all 0 ă |ξ| ď 12 ,
ˇ
ˇ
¯
´
2
ˇ N
ˇ
n´1
(171)
.
ˇẐn,µ pξqˇ ! exp ´CN|ξ|
2

Deduction of Theorem 3. Recall N “ cp n´1
upper bound of Proposition 22. By (169),
˜
ˇ¸2
ˇ
ÿ
ÿ ˇ
ˇ
1
N
ˇZn,µ pxq ´ ˇ ď
(172)
ˇ
pˇ
ξPZ
x mod p

and let c ě 1. Apply the

0ă|ξ|ă 2p

!

ÿ

0ă|ξ|ă p2

ˇ
ˆ ˙ˇ
ˇ N ξ ˇ2
ˇ
ˇẐn,µ
ˇ
p ˇ

´
¯
2
exp ´Cc|ξ| n´1

! exp p´Ccq .

6.1. Proof of Proposition 22. Let C2n´2 act on blocks of vectors of
length k2n´2 with the jth factor from C2n´2 , j ě 1 switching the relative
order of the first k2j´1 and second k2j´1 indices. Thus, for instance,
in case n “ 5, if each of x1 , ..., x8 represents a block of k consecutive
indices and x “ x1 x2 x3 x4 x5 x6 x7 x8 ,
τ2 x “ x3 x4 x1 x2 x5 x6 x7 x8

τ1 τ3 x “ τ3 τ1 x “ x5 x6 x7 x8 x2 x1 x3 x4
τ1 τ2 τ3 x “ x5 x6 x7 x8 x3 x4 x2 x1 .
X
\
1
For k ě 1 set N 1 “ k2Nn´2 and let Gk “ pC2n´2 qN . Gk acts on
sequences of length N with, for j ě 1, the jth factor of Gk acting on
the contiguous subsequence of indices of length k2n´2 ending at jk2n´2 .
For fixed k and fixed w P WN “ psupp µqN , let
‰
“
(174)
Zk pwq “ Eτ PGk δZnN pτ ¨wq .

(173)

Continue to abbreviate UN “ µbN . For any k,
N
Zn,µ
“ EUN rZk pwqs .

(175)

We introduce a second, dual action of Gk on a linear dual space. Let
(176)

IN “ ti “ pi1 , i2 , ..., in´1 q : 1 ď i1 ă i2 ă ... ă in´1 ď Nu .

Given i P IN and k ě 1, let Si,k Ă Sn´1 be the subset of permutations
Si,k “ tστ ,i : τ P Gk u where
(177) @1 ď j ď n ´ 1,

στ ,i pjq “ #t1 ď k ď n ´ 1 : τ pik q ď τ pij qu.

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

33

That is, στ ,i pjq is the relative position of τ ¨ ij when τ ¨ i is sorted to be
in increasing order. Put another way, suppose τ maps i1 ă ¨ ¨ ¨ ă in´1
to j1 ă ¨ ¨ ¨ ă jn´1 in some order (and vice versa, τ is an involution)
and calculate
p1q

pn´1q

p1q

pn´1q

ej1 b ¨ ¨ ¨ b ejn´1 pτ ¨ wq “ eτ ¨j1 b ¨ ¨ ¨ b eτ ¨jn´1 pwq
p1q

pn´1q

“ eiσ´1 p1q b ¨ ¨ ¨ b eiσ´1 pn´1q pwq

(178)

pσp1qq

“ ei1

pσpn´1qq

b ¨ ¨ ¨ b ein´1

pwq,

where στ ,i is abbreviated σ.
Let
)
!
pσp1qq
pσpn´1qq
(179)
XN,k “ ei1
b ¨ ¨ ¨ b ein´1
: i P IN , σ P Si,k .

The action of τ P Gk is defined on a representative set within XN,k by,
for each i P IN ,
¯
´
pσ p1qq
pστ ,i pn´1qq
p1q
pn´1q
(180)
τ ¨ ei1 b ¨ ¨ ¨ b ein´1 “ ei1 τ ,i b ¨ ¨ ¨ b ein´1
.
The following lemma justifies that this definition extends to a unique
group action of Gk on all of XN,k .

Lemma 23. Let τ , τ 1 P Gk and i P IN satisfy στ ,i “ στ 1 ,i . Then for
any τ 2 P Gk , στ `τ 2 ,i “ στ 1 `τ 2 ,i . In particular, (180) extends to a unique
group action on XN,k .
Proof. This follows, since, for any 1 ď i ă j ď N there is at most one
factor of G “ C2n´2 in Gk , and one index ℓ, 1 ď ℓ ď n ´ 2 of G which
exchanges the order of i and j. To define the group action in general,
given τ P Gk , i P IN and σ P Si,k choose any τ 0 such that σ “ στ 0 ,i .
Let σ 1 “ στ 0 `τ ,i . Then
(181)

pσp1qq

τ ¨ ei1

pσpn´1qq

b ¨ ¨ ¨ b ein´1

pσ1 p1qq

“ ei1

pσ1 pn´1qq

b ¨ ¨ ¨ b ein´1

The definition is clearly unique, since (180) surjects on XN,k .

.


The actions of Gk on WN and on XN,k , although not adjoint, are
compatible on ZnN , in the sense that for any τ ,
(182)
so that
(183)

pτ ¨ ZnN qpwq “ ZnN pτ ¨ wq
‰
“
Zk pwq “ Eτ PGk δpτ ¨ZnN qpwq .

Note that in general, although Gk is a product group, the separate
factors τi do not act independently in τ ¨ ZnN . For instance, when n “ 5
p1q
p2q
p3q
p4q
and k “ 1, the change in a tensor of type e1 b e2 b e2n´2 `1 b e2n´2 `2
under the first factor of Gk depends upon whether the second factor
has been applied. Thus the characteristic function
“
˘‰
`
(184)
χk pξ, wq “ Eτ PGk e´ξ ZnN pτ ¨ wq

34

PERSI DIACONIS AND BOB HOUGH

need not factor as a product.
A pleasant feature of the general case is that this difficulty is rectified
by estimating instead of χk pξ, wq, a function Fk pξ, wq which is the result
of applying the Gowers-Cauchy-Schwarz inequality to χk pξ, wq. To
1
1
describe this, write Gk “ pC2n´2 qN “ pC2N qn´2 , and thus
‰
“
(185)
Eτ PGk rf pτqs “ Eτ PC N 1 ¨ ¨ ¨ Eτ PC N 1 f pτ 1 , ..., τ n´2 q .
1

n´2

2

2

Then, setting apart one expectation at a time and applying CauchySchwarz,

(186)
n´2

|χk pξ, wq|2
ď Eτ

1
N1
1 ,τ 1 PC2

»

¨ ¨ ¨ Eτ
¨

“ Eτ ,τ 1 PGk –e´ξ ˝

“: Fk pξ, wq,

1
N1
n´2 ,τ n´2 PC2

ÿ

»

¨

–e´ξ ˝

ÿ

p´1qn´2´|S|τ S ¨ w‚ﬂ

SĂrn´2s

˛ﬁ

p´1qn´2´|S| τ S ¨ w ‚ﬂ

SĂrn´2s

where
(187)

˛ﬁ

τ S “ pτ S,1 , ..., τ S,n´2 q,

τ S,i “

"

τi
τ 1i

iPS
.
iRS

Lemma 24. Fk pξ, wq factors as the product
˙
N1 ˆ
ź
Fk,j pξ, wq
1
Fk pξ, wq “
(188)
1 ´ n´2 `
2
2n´2
j“1

where Fk,j pξ, wq is a function of wj,k “ pω1 , ..., ω2n´2 q with the
ÿ
wℓ
(189)
ωi “
p2n´2 pj´1q`i´1qkăℓďp2n´2 pj´1q`iqk

the sum of consecutive blocks
of length k in w. Identify C2n´2 with
ř
n´2
1pτi ‰ 0q. Then
t0, 1un´2 and write |τ | “ i“1
(190)
˛ﬁ
»
¨
ÿ
1
n´2
p´1q|τ | Zn2 ppτ ` τ 1 q ¨ wj,k q‚ﬂ
Fk,j pξ, wq “ Eτ PC2n´2 –e´ξ ˝
τ 1 PC2n´2

with the action of C2n´2 on blocks of size 1 in wj,k .

Proof. Consider for fixed τ , τ 1 P Gk the sum
ÿ
p´1qn´2´|S|τ S ¨ ZnN pwq.
(191)
ZnN pτ , τ 1 qpwq “
SĂrn´2s

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

35

After replacing w with τ 1 w and τ with τ ` τ 1 it suffices to consider
τ 1 “ id.
Consider the action of
ÿ
(192)
τ̂ “
p´1qn´2´|S| τS
SĂrn´2s

on a tensor

p1q

p2q

pn´1q

(193) e “ ei1 b ei2 b ¨ ¨ ¨ b ein´1 ,

1 ď i1 ă i2 ă ¨ ¨ ¨ ă in´1 ď N

appearing in ZnN . Let G “ C2n´2 identified with subsets S of rn ´ 2s,
let G0 “ stabpiq ď C2n´2 be the subgroup consisting of S for which
τ S ¨ e “ e, and let G1 “ C2n´2 {G0 . By the group action property, for all
x P G0 , for all y P G1 , τ x`y e “ τ y e so that when G0 ‰ t1u, τ̂ ¨ e “ 0.
A necessary and sufficient condition for G0 “ t1u is that, for some
1 ď j ď N 1,
(194)

@1 ă ℓ ď n ´ 1

2n´2 pj ´ 1qk ă i1 ď 2n´2 pj ´ 1qk ` k

2n´2 pj ´ 1qk ` 2ℓ´2 k ă iℓ ď 2n´2 pj ´ 1qk ` 2ℓ´1 k,

and τj “ 1n´2 P C2n´2 . In words, the indices must all belong to a
common block of length 2n´2k acted on by a single factor from Gk ,
within this block, the first 2ℓ´1k elements must contain iℓ and the
second 2ℓ´1 k must contain iℓ`1 for ℓ “ 1, 2, ..., n ´ 2, and the factor τj
acting on the block must be the element 1n´2 of the hypercube C2n´2 .
The product formula given summarizes this condition.

n´1

Proof of Proposition
without loss that |ξ| ě N ´ 2 . Let
´Y
] 22. Assume
¯
2
k “ max |ξ|´ n´1 , Mpµq , where Mpµq is a constant depending upon
µ. By the triangle inequality and Hölder’s inequality,
ˇ
ˇ
ˇ
ˇ N
(195)
ˇẐn,µ pξqˇ ď |EUN rχk pξ, wqs|
ď EUN r|χk pξ, wq|s
”
ı 1
2n´2 2n´2
ď EUN |χk pξ, wq|
1

ď EUN rFk pξ, wqs 2n´2 .

Since disjoint blocks are i.i.d., Lemma 24 implies that the expectation
of Fk pξ, wq factors as a product
ˆ
˙N 1
1
E rFk,1pξ, wqs
EUN rFk pξ, wqs “ 1 ´ n´2 `
(196)
.
2
2n´2
In the limit as |ξ| Ó 0,
ÿ
1
n´2
(197)
ξ
p´1q|τ | Zn2 ppτ ` τ 1 q ¨ wj,k q
τ 1 PC2n´2

36

PERSI DIACONIS AND BOB HOUGH

has a continuous limiting distribution, which is a polynomial of degree
n ´ 1 in independent normal random variables, and hence the characteristic function ErFk,1pξ, wqs has size bounded uniformly away from 1
for all |ξ| smaller than a fixed constant ǫpµq. It follows that
ˇ
ˇ
´
¯
2
ˇ
ˇ N
(198)
ˇẐn,µ pξqˇ ď expp´C 1 N 1 q ď exp ´C|ξ| n´1 N .

To handle the remaining range ǫpµq ď |ξ| ď 12 , choose N1 , N2 , ..., Nn´1
minimal such that µ˚Ni gives positive mass to the ith standard basis
vector in Rn´1 . Set k “ N1 ` ... ` Nn´1 and recall that µ assigns posin´2
tive probability to 0. Then with µb2 k -positive probability, for each
1 ď j ď n ´ 1, ω2j´1 is the jth standard basis vector and all other ωi
n´2
are 0. For this configuration, Zn2 pτ ¨ w1,k q “ 1 if τ is the identity,
and 0 otherwise. Again, this gives that the characteristic function is
uniformly bounded away from 1. We thus conclude, as before, that
ˇ
ˇ ˇ
ˇ
ˇ
ˇ ˇ N
ˇ N
(199)
ˇẐn,µ pξqˇ ď ˇẐn,µpξqˇ ď expp´CNq.


Appendix A. The characteristic function of a Gaussian
measure on the Heisenberg group
This section proves Theorem 9, which gives a rate of convergence
to the characteristic function of a Gaussian measure on the Heisenberg group when the steps in the walk are normally distributed in the
abelianization.
Recall that
ˆ
˙
ˆ ˚
˙
ż
x
H pxq
Ipα, ξ; Nq “
e´α ?
e´ξ
dν2bN pxq
(200)
N
2
N
N
pR q
¯
´
2
1
.
exp ´ }x}
where ν2 pxq “ 2π
2
First consider the case α “ 0. Integrate away xp1q to obtain,
ˆ
˙
ż
˘
˘
1
1 t ``
2
2
exp ´ y 1 ´ ξ0 IN ` ξ0 H y dy
(201) Ip0, ξ; Nq “
N
2
p2πq 2 RN
where
(202)

ξ0 “

πξ
,
N

Hi,j “ N ´ 2|i ´ j|;

ř
2 2
p1q p2q
this follows from H ˚pxq “ 21 iăj p´1qδpjăiq xi xj , η̂pξq “ e´2π ξ for a
standard one dimensional Gaussian, and
˜
¸2
N
ÿ
ÿ
(203)
y t pH ´ IN qy “
p´1qδpjăiq yj .
i“1

j‰i

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

37

Thus,
Ip0, ξ; Nq “ a

(204)

1
,
det pp1 ´ ξ02 q IN ` ξ02 Hq

as may be seen by using an orthogonal matrix to diagonalize the quadratic form.
We perform elementary row operatorations to simplify the computation of the determinant. Let
U´ “ IN ´

(205)
Thus

` t
˘
U´ U´ i,j

(206)

and
(207)

so that
(208)

`

U´t HU´

``

˘

i,j

N
´1
ÿ
i“1

$
1,
’
’
&
2,
“
´1,
’
’
% 0,

$
N,
’
’
&
´2,
“
4,
’
’
% 0,

ei b ei`1 .
i“j“1
i“ją1
|i ´ j| “ 1
otherwise

i“j“1
i “ 1, j ą 1 or j “ 1, i ą 1
,
i“ją1
otherwise

˘
˘
1 ´ ξ02 IN ` ξ02 H U´
«
N ´1
1 ´ ξ02 ÿ
2
pei b ei`1 ` ei`1 b ei q
“ p1 ` ξ0 q 2IN ´
1 ` ξ02 i“1

U´t

ﬀ
N
2ξ02 ÿ
pN ` 1qξ02 ´ 1
´
pe1 b ei ` ei b e1 q `
e1 b e1 .
1 ` ξ02 i“1
1 ` ξ02
1´ξ 2

Set ζ “ 1`ξ02 . We diagonalize the tridiagonal matrix with 2’s on the
0
diagonal and ´ζ on the first sub and super diagonal by working from
the lower right corner and adding up and to the left, and treat the
remainder of the matrix as a rank 2 perturbation.
Define sequences
(209)

ε1 “ 2,

@i ě 1, εi`1 “ 2 ´

π0 “ 1,

@i ě 1, πi “

δ1 “ 1,

@i ě 1, δi`1 “ 1 `

i
ź

ζ2
εi

εi

j“1

ζδi
.
εi

38

PERSI DIACONIS AND BOB HOUGH

These parameters have the following behavior with proof postponed
until the end of this section.
ı
´
1
Lemma 25. For ξ P 0, N 2 the following asymptotics hold
ˆ
ˆ
˙˙
sinhp2πξq
1 ` ξ2
πN “ N
1`O
2πξ
N
˙˙
ˆ
ˆ
2πξ
1 ` ξ2
εN “ 1 `
(210)
cothp2πξq 1 ` O
N
N
ˆ
ˆ
˙˙
2
1`ξ
N tanh πξ
1`O
δN “
2πξ
N
˙˙
ˆ
ˆ
N
´1 2
ÿ
δj
N3
1 ` ξ2
.
“ 3 3 r2πξ ´ 2 tanh πξs 1 ` O
ε
8π ξ
N
j“1 j
Set

(211)

Lε “ IN ` ζ

N
´1
ÿ
i“1

ei`1 b ei
,
εN ´i`1

N
ÿ
ei b ei
1
Dε “
.
2
p1 ` ξ0 q i“1 εN `1´i

The diagonalization process is summarized in the following matrix
1
equation, in which Dε2 is multiplied on left and right to obtain 1’s
on the diagonal
1
1
``
˘
˘
(212)
Dε2 Ltε U´t 1 ´ ξ02 IN ` ξ02 H U´ Lε Dε2 “ IN ` P

and where P is the rank two symmetric matrix which results from
applying the diagonalization operators to the second line on the right
hand side of (208),
(213)
N
´2ξ02 ÿ δN `1´i
pN ` 1qξ02 ´ 1
P “
pe
b
e
`
e
b
e
q
`
e1 b e1 .
?
1
i
i
1
1 ` ξ02 i“1 εN εN ´i`1
εN p1 ` ξ02 q
Then, for some orthogonal matrix O, and λ` ě λ´ ,

(214)

O t pIN ` P qO “ pλ` e1 b e1 ` λ´ e2 b e2 q ‘ IN ´2 .

By direct calculation, expanding by the top row, detpIN ` P q is equal
to the e1 b e1 entry plus the sum of the squares of the e1 b ei entries,
1 ă i ď N,
ˆ
˙
1
pN ` 1qξ02
`
(215) det pIN ` P q “ λ` λ´ “ 1 ´
εN p1 ` ξ02 q
εN p1 ` ξ02 q
N
´1 2
ÿ
4ξ04
δi
4ξ02 δN
´
´
2
2 2
1 ` ξ0 εN
p1 ` ξ0 q εN j“1 εi
ˆ
ˆ
˙˙
πξ coth πξ
1 ` ξ2
“
1`O
.
N
N

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

Since
(216)
(217)

39

˙˙
ˆ
ˆ
N sinh 2πξ
1 ` ξ2
,
det pDε q “ p1 `
“ 1`O
N
2πξ
ˆ
ˆ
˙˙
``
˘
˘
1 ` ξ2
2
2
2
det 1 ´ ξ0 IN ` ξ0 H “ pcosh πξq 1 ` O
.
N
´1

ξ02 qN πN

Now consider the general case in which α ‰ 0. Treat x as N vectors in R2 . When SO2 pRq acts diagonally on pR2 qN rotating each xi
simultaneously, H ˚ and the Gaussian density are preserved. Thus,
Ipα, ξ; Nq “ Ipp0, }α}qt, ξ; Nq. Calculate
1
e1
(218)
r1, 1, ¨ ¨ ¨ , 1sU´ Lε Dε2 “ a
.
ǫN p1 ` ξ02 q
1

It follows that after making the change of coordinates y 1 “: U1 Lε Dε2 y
the phase has magnitude ? 2π}α} 2 and is now in the e1 direction. Let
N εN p1`ξ0 q

v` , v´ be unit vectors generating the eigenspaces λ` , λ´ respectively.
Since e1 lies in the span of v` , v´ it follows
(219)
ˆ
˙˙
ˆ
xv` , e1 y2 xv´ , e1 y2
´2π 2 }α}2
Ip0, ξq.
`
Ipα, ξ; Nq “ exp
NεN p1 ` ξ02 q
λ`
λ´

Calculate

T “ λ` ` λ´ “ 2 `

(220)
so that
(221)
Also,

et1 P e1

ξ2
N

˙

ˆ
ˆ
˙˙ ˆ
˙
1 ` ξ2
πξ coth πξ
pλ` , λ´ q “ 1 ` O
1,
.
N
N
xv` , e1 y2 ` xv´ , e1 y2 “ 1

(222)

2

2

et1 P e1

,

2

λ` xv` , e1 y ` λ´ xv´ , e1 y “ 1 `
so that
(223)

“1`O

ˆ

2

xv` , e1 y “ O

ˆ

1 ` ξ2
N

˙

“O

ˆ

1 ` ξ2
N

xv´ , e1 y “ 1 ` O

ˆ

˙

1 ` ξ2
N

˙

.

It follows that
ˆ
ˆ
˙˙
N
1 ` ξ2
xv` , e1 y2 xv´ , e1 y2
1`O
.
`
“
(224)
λ`
λ´
πξ coth πξ
N
In particular

exp
(225)

Ipα, ξ; Nq “

´

´2π}α}2
ξ coth πξ

cosh πξ

¯

ˆ
ˆ
˙˙
p1 ` }α}2 qp1 ` ξ 2 q
1`O
N

40

PERSI DIACONIS AND BOB HOUGH
1´ξ02
.
1`ξ02

Proof of Lemma 25. Recall ζ “
(226)

πn “ 2πn´1 ´ ζ 2 πn´2 ,

πn satisfies the recurrence
π0 “ 1, π1 “ 2.

The following closed forms hold,
(227)

p1 ` ξ0 q2n`2 ´ p1 ´ ξ0 q2n`2
4ξ0 p1 ` ξ02 qn
2ξ0 p1 ` ξ0 q2n ` p1 ´ ξ0 q2n
εn “ 1 `
1 ` ξ02 p1 ` ξ0 q2n ´ p1 ´ ξ0 q2n
´
¯n ´
¯n
1`ξ0
1´ξ0
1 1´ξ0 ` 1`ξ0 ´ 2 1
´
¯n ´
¯n ` .
δn “
1`ξ0
1´ξ0
2ξ0
2
´

πn “

1´ξ0

1`ξ0

The formula for πn is immediate from the recurrence relation, since
(228)

p1 ` ξ0 q2
,
1 ` ξ02

p1 ´ ξ0 q2
1 ` ξ02

are the two roots of x2 ´ 2x ` ζ 2 “ 0. The formula for εn follows from
n
εn “ ππn´1
. The formula for δn is obtained on summing the geometric
series
(229)

δn “

n´1
ζ n´1 ÿ πj
,
πn´1 j“0 ζ j

and use
(230)

πn
p1 ` ξ0 q2n`2 ´ p1 ´ ξ0 q2n`2
“
ζn
4ξ0 p1 ´ ξ02 qn
«ˆ
˙n`1 ˆ
˙n`1 ﬀ
1 ` ξ0
1 ´ ξ02
1 ´ ξ0
.
“
´
4ξ0
1 ´ ξ0
1 ` ξ0

The claimed asymptotics for π, ε, δ are straightforward. For instance,
to obtain the correct relative error in πn , write
(231)

p1 ` ξ0 q2n`2 ´ p1 ´ ξ0 q2n`2
p1 ` ξ0 q2n`2 ´ p1 ´ ξ0 q2n`2
“
4ξ0
2 pp1 ` ξ0 q ´ p1 ´ ξ0 qq

as a geometric series of positive terms. In each term of the series,
approximate the power with an exponential with acceptable relative
error, then sum the sequence of exponentials. The correct relative
error may be obtained in the other cases similarly.
Using the exact formulae for ε and δ yields
ˆ
ˆ
˙˙
˙2
ˆ
δj2
1 ξ2
N2
jπξ
“ 1`O
`
tanh
(232)
.
εj
j N
4π 2 ξ 2
N

RANDOM WALK ON UNIPOTENT MATRIX GROUPS

41

Approximating with a Riemann sum,
˙˙
ˆ
ˆ
ż1
N
´1 2
ÿ
δj
N3
1 ` ξ2
(233)
“ 1`O
tanh ptπξq2 dt
2ξ 2
ε
N
4π
0
j“1 j
which gives the claimed estimate.



References
[1] Alexopoulos, G. K. “Centered densities on Lie groups of polynomial volume
growth.” Probab. Theory Related Fields 124 (2002), no. 1, 112–150.
[2] Alexopoulos, G. K. “Random walks on discrete groups of polynomial volume
growth.” Ann. Probab. 30 (2002), no. 2, 723–801.
[3] P. Baldi and L. Caramellino. “Large and moderate deviations for random walks
on nilpotent groups.” J. Theoret. Probab. 12 (1999), no. 3, 779–809.
[4] Balog, A. “On the distribution of integers having no large prime factors.”
Journées Arithmétiques, Besançon, Astérisque 147/148 (1985): 27–31.
[5] E. F. Breuillard, Equidistribution of random walks on nilpotent Lie groups and
homogeneous spaces, ProQuest LLC, Ann Arbor, MI, 2004.
[6] Breuillard, Emmanuel. “Local limit theorems and equidistribution of random walks on the Heisenberg group.” Geometric and functional analysis 15.1
(2005):35–82.
[7] Breuillard, Emmanuel. “Equidistribution of dense subgroups on nilpotent Lie
groups.” Ergodic Theory Dynam. Systems 30 (2010), no. 1, 131–150.
[8] Daniel Bump, Persi Diaconis, Angela Hicks, Laurent Miclo, and Harold
Widom. An exercise (?) in Fourier analysis on the Heisenberg group.
arXiv:1502.04160, 2015.
[9] P. Crépel and A. Raugi. “Théorème central limite sur les groupes nilpotents.”
Ann. Inst. H. Poincaré sec B, Prob. and Stat., vol XIV, 2. (1978): 145–164.
[10] Coulhon, Saloff-Coste, and Varopoulos. Analysis and geometry on groups.
Cambridge tracts on mathematics, Cambridge University Press, 1992.
[11] Chung, Fan and Linyuan Lu. “Concentration inequalities and martingale inequalities: a survey.” Internet mathematics 3.1 (2006): 79–127.
[12] P. Diaconis. “Threads through group theory.” In Character theory of finite
groups, 33–47, Contemp. Math., 524, Amer. Math. Soc., Providence, RI (2010).
[13] P. Diaconis and L. Saloff-Coste. “Moderate growth and random walk on finite
groups.” Geom. Funct. Anal. 4 (1994), no. 1, 1–36.
[14] P. Diaconis and L. Saloff-Coste. “An application of Harnack inequalities to
random walk on nilpotent quotients.” J. Fourier Anal. Appl. (1995), Special
Issue, 189–207.
[15] P. Diaconis and L. Saloff-Coste. “Nash inequalities for finite Markov chains.”
J. Theoret. Probab. 9 (1996), no. 2, 459–510.
[16] Lawler, Gregory F., and Vlada Limic. Random walk: a modern introduction.
Vol. 123. Cambridge University Press, 2010.
[17] Gaveau, Bernard. “Principe de moindre action, propagation de la chaleur et
estimées sous elliptiques sur certains groupes nilpotents.” Acta mathematica
139.1 (1977): 95-153.
[18] Gonalves, Felipe, Michael Kelly, and Jose Madrid. “One-sided band-limited approximations of some radial functions.” Bulletin of the Brazilian Mathematical
Society, New Series 46.4 (2015): 563-599.
[19] Green, Ben and Tao, Terence. “The quantitative behaviour of polynomial orbits on nilmanifolds.” Ann. of Math. (2) 175 (2012), no. 2, 465–540.

42

PERSI DIACONIS AND BOB HOUGH

[20] Hulanicki, Andrzej. “The distribution of energy in the Brownian motion in the
Gaussian field and analytic-hypoellipticity of certain subelliptic operators on
the Heisenberg group.” Studia Mathematica 2.56 (1976): 165-173.
[21] S. Ishiwata. “A central limit theorem on a covering graph with a transformation
group of polynomial growth.” J. Math. Soc. Japan 55 (2003), no. 3, 837–853.
[22] S. Ishiwata. “A central limit theorem on modified graphs of nilpotent covering
graphs.” In Spectral analysis in geometry and number theory, 59–72, Contemp.
Math., 484, Amer. Math. Soc., Providence, RI.
[23] Y. Peres and A. Sly. “Mixing of the upper triangular matrix walk.” Probab.
Theory Related Fields 156 (2013), no. 3-4, 581–591.
[24] Raugi, A. “Théorème de la limite centrale sur les groupes nilpotents.” Probability Theory and Related Fields 43.2 (1978): 149-172.
[25] L. Saloff-Coste, “Probability on groups: random walks and invariant diffusions.” Notices Amer. Math. Soc. 48 (2001), no. 9, 968–977.
[26] D. W. Stroock and S. R. S. Varadhan. “Limit theorems for random walks on
Lie groups.” Sankhyā Ser. A 35 (1973), no. 3, 277–294.
[27] Tao, T., and V. Vu. Additive combinatorics. Vol. 105. Cambridge University
Press, 2006.
[28] V.N. Tutubalin. “Compositions of measures on the simplest nilpotent group.”
(Russian) Teor. Verojatnost. i Primenen 9, (1964): 531–539.
[29] D. Wehn. “Probabilities on Lie groups.” Proc. Nat. Acad. Sci. U.S.A. 48
(1962): 791–795.
(Persi Diaconis) Department of Mathematics, Stanford University, 450
Serra Mall, Stanford, CA, 94305, USA
E-mail address: diaconis@math.stanford.edu
(Bob Hough) Department of Mathematics, Stanford University, 450
Serra Mall, Stanford, CA, 94305, USA
Current address: School of Mathematics, Institute of Advanced Study, 1 Einstein
Drive, Princeton, NJ, 08540
E-mail address: hough@math.ias.edu

