Daniel Bump

Persi Diaconis

Angela Hicks

Laurent Miclo

Harold Widom

USEFUL BOUNDS ON THE EXTREME EIGENVALUES AND VECTORS OF MATRICES FOR HARPER'S OPERATORS

Keywords: 1991 Mathematics Subject Classification. 60B15; 20P05 Heisenberg group, almost Mathieu operator, Fourier analysis, random walk. The first, second, third, and fifth

In analyzing a simple random walk on the Heisenberg group we encounter the problem of bounding the extreme eigenvalues of an n × n matrix of the form M = C + D where C is a circulant and D a diagonal matrix. The discrete Schrödinger operators are an interesting special case. The Weyl and Horn bounds are not useful here. This paper develops three different approaches to getting good bounds. The first uses the geometry of the eigenspaces of C and D, applying a discrete version of the uncertainty principle. The second shows that, in a useful limit, the matrix M tends to the harmonic oscillator on L 2 (R) and the known eigenstructure can be transferred back. The third approach is purely probabilistic, extending M to an absorbing Markov chain and using hitting time arguments to bound the Dirichlet eigenvalues. The approaches allow generalization to other walks on other groups.

M n = 1 4

2 1 1 1 1 1 1 1 1                     2 cos 2πj n , 0 ≤ j ≤ n -1
As explained in [START_REF] Bump | An Exercise (?) in Fourier Analysis on the Heisenberg Group[END_REF] and summarized in Section 2, this matrix arises as the Fourier transform of a simple random walk on the Heisenberg group, as a discrete approximation to Harper's operator in solid state physics and in understanding the Fast Fourier Transform. Write M = C + D with C a circulant, (having 1 4 on the diagonals just above and below the main diagonal and in the corners) and D a diagonal matrix (with diagonal entries 1 2 cos 2πj n for 0 ≤ j ≤ n -1). The Weyl bounds [START_REF] Horn | Matrix analysis[END_REF] and Horn's extensions [START_REF] Bhatia | Linear algebra to quantum cohomology: the story of Alfred Horn's inequalities[END_REF] yield that the largest eigenvalue λ 1 (M ) ≤ λ 1 (C) + λ 1 (D).

Here λ 1 (C) = λ 1 (D) = 1 2 giving λ 1 (M ) ≤ 1. This was not useful in our application; in particular, we need λ 1 (M ) ≤ 1 -const n . This paper presents three different approaches to proving such bounds. The first approach uses the geometry of the eigenvectors and a discrete version of the Heisenberg uncertainty principle. It works for general Hermitian circulants: Theorem 1. Let C be an n × n Hermitian circulant with eigenvalues λ 1 (C) ≥ • • • ≥ λ n (C). Let D be an n × n real diagonal matrix with eigenvalues

λ 1 (D) ≥ • • • ≥ λ n (D). If k, k satisfy 1 ≤ k, k ≤ n, kk < n, then λ 1 (C + D) ≤ λ 1 (C) + λ 1 (D) - 1 2 min{λ 1 (D) -λ k (D), λ 1 (C) -λ k (C)} 1 - kk n 2 .
Example 1. For the matrix M n in (1), the eigenvalues of C and D are real and equal to 1 2 cos 2πj n 0≤j≤n-1 . For simplicity, take n odd. Then, writing λ j = λ j (C) = λ j (D), λ 1 = 1 2 , λ 2 = λ 3 = 1 2 cos 2π n , and

λ 2j+1 = λ 2j = 1 2 cos 2πj n for 1 ≤ j ≤ n-1 2 . Choose k = k = c
√ n for a fixed 0 < c < 1. Then

λ k = 1 2 1 - 1 2 πc n 1/2 2 + O 1 n 3/2 , 1 - kk n 2 ≥ (1 -c) 2
and the bound in Theorem 1 becomes

λ 1 (M n ) ≤ 1 - π 2 8 c 2 (1 -c) 2 n + O 1 n 3/2 .
The choice c = 1 2 gives the best result. Very sharp inequalities for the largest and smallest eigenvalues of M n follow from [START_REF] Florin | Norm estimates of almost Mathieu operators[END_REF]. They get better constants than we have in this example. Their techniques make sustained careful use of the exact form of the matrix entries while the techniques in Theorem 1 work for general circulants.

The second approach passes to the large n limit, showing that the largest eigenvalues of M n from (1) tend to suitably scaled eigenvalues of the harmonic oscillator L = -1 4 d 2 dx 2 + π 2 x 2 . Theorem 2. For a fixed k ≥ 1, the kth largest eigenvalue of M n equals

1 - µ k n + o 1 n with µ k = (2k-1)π 2
, the kth smallest eigenvalue of L.

Theorem 2 gets higher eigenvalues with sharp constants for a restricted family of matrices. The argument also gives a useful approximation to the kth eigenvector. Similar results (with very different proofs) are in [START_REF] Strohmer | Almost Eigenvalues and Eigenvectors of Almost Mathieu Operators[END_REF].

There are many techniques available for bounding the eigenvalues of stochastic matrices ( [START_REF] Lawler | Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality[END_REF], [START_REF] Diaconis | Geometric bounds for eigenvalues of Markov chains[END_REF], and [START_REF] Diaconis | Logarithmic Sobolev inequalities for finite Markov chains[END_REF]). We initially thought that some of these would adapt to M n . However, M n is far from stochastic: the row sums of M n are not constant and the entries are sometimes negative. Our third approach is to let M n = 1 3 I + 2 3 M n . This is substochastic (having non-negative entries and row sums at most 1). If a i = 1j M n (i, j), consider the (n + 1) × (n + 1) stochastic matrix:

(2)

M n = 1 0 0 . . . 0 a 1 a 2

. . .

a n .                  

M n

This has the interpretation of an absorbing Markov chain (0 is the absorbing state) and the Dirichlet eigenvalues of M n (namely those whose eigenvalues vanish at 0) are the eigenvalues of M n . In [START_REF] Bump | An Exercise (?) in Fourier Analysis on the Heisenberg Group[END_REF] path and other geometric techniques are used to bound these Dirichlet eigenvalues. This results in bounds of the form 1-const.

n 4/3 for λ 1 (M n ). While sufficient for the application, it is natural to want an improvement that gets the right order. Our third approach introduces a purely probabilistic technique which works to give bounds of the right order for a variety of similar matrices.

Theorem 3. There is a c > 0 such that, for all n ≥ 1 and M n defined at (1), the largest eigenvalue satisfies λ 1 (M n ) ≤ 1 -c n . Section 2 gives background and motivation. Theorems 1, 2, and 3 are proved in Sections 3, 4, and 5. Section 6 treats a simple random walk on the affine group mod p. It uses the analytic bounds to show that order p 2 steps are necessary and sufficient for convergence. It may be consulted now for further motivation. The final section gives the limiting distribution of the bulk of the spectrum of M n (a) using the Kac-Murdock-Szegö theorem.

Background

Our work in this area starts with the finite Heisenberg group:

H 1 (n) =      1 x z 0 1 y 0 0 1   : x, y, z ∈ Z/nZ    .
Write such a matrix as (x, y, z), so (x, y, z)(x , y , z ) = (x + x , y + y , z + z + xy ).

Let S = {(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0)} and ( 3)

Q(g) = 1 4 g ∈ S 0 otherwise . ( 4
)
Thus S is a minimal symmetric generating set for H 1 (n) and Q is the probability measure associated with 'pick an element in S at random and multiply.' Repeated steps of this walk correspond to convolution. For (x, y, z) ∈ H 1 (n),

Q * k (x, y, z) = (x ,y ,z )∈H1(n) Q(x , y , z )Q * k-1 ((x, y, z)(x , y , z ) -1 ). When k is large, Q * k converges to the uniform distribution U (x, y, z) = 1 n 3
The rate of convergence of Q * k to U can be measured by the chi-squared distance:

(x,y,z)∈H |Q * k (x, y, z) -U (x, y, z)| 2 /(U (x, y, z)) = ρ∈ Ĥ1 ρ =1 d ρ Q(ρ) k 2 , (5)
On the right, the sum is over nontrivial irreducible representations of H 1 (n) with ρ of dimension d ρ and Q(ρ) k = (x,y,z) Q * k (x, y, z)ρ(x, y, z). For background on the Fourier analysis approach to bounded convergence see [START_REF] Diaconis | Group representations in probability and statistics[END_REF], Chapter 3.

For simplicity, (see [START_REF] Bump | An Exercise (?) in Fourier Analysis on the Heisenberg Group[END_REF] for the general case) take n = p a prime. Then

H 1 (p) has p 2 1-dimensional representations ρ a,b (x, y, z) = e 2πi p (ax+by) for a, b in Z p . It has p -1 p-dimensional representations. These act on V = {f : Z p → C} via ρ a (x, y, z)f (w) = e 2πia p (yw+z) f (x + w), 0 ≤ a ≤ p -1.
The Fourier transform of Q at ρ a is the matrix M n (a) as in (1) with cos 2πj p replaced by cos 2πaj p for 0 ≤ j ≤ p -1.

The chi-squared norm in [START_REF] Bump | An Exercise (?) in Fourier Analysis on the Heisenberg Group[END_REF] is the sum of the (2k)th power of the eigenvalues so proceeding needs bounds on these. The details are carried out in [START_REF] Bump | An Exercise (?) in Fourier Analysis on the Heisenberg Group[END_REF]. The main results show that k of order n 2 steps are necessary and sufficient for convergence. That paper also summarizes other appearances of the matrices M n (a). They occur in discrete approximations of the 'almost Mathieu' operator in solid state physics. In particular, see [START_REF] Wang | Quasiclassical approximations for almostmathieu equations[END_REF], [START_REF] Florin | Norm estimates of almost Mathieu operators[END_REF], and [START_REF] Béguin | On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper's operator[END_REF]. If F n is the discrete Fourier transform matrix

(F n ) jk = 1 √ n e 2πijk n
; it is easy to see that F n M n (1) = M n (1)F n . Diagonalizing F n has engineering applications and having a 'nice' commuting matrix should help. For this reason, there is engineering interest in the eigenvalues and vectors of M n (1). See [START_REF] Dickinson | Eigenvectors and functions of the discrete Fourier transform[END_REF] and [START_REF] Mehta | Eigenvalues and eigenvectors of the finite Fourier transform[END_REF].

Proof of Theorem 1

Throughout this section C is an n × n Hermitian circulant with eigenvalues

λ 1 (C) ≥ λ 2 (C) ≥ • • • ≥ λ n (C) and D is a real diagonal matrix with eigenvalues λ 1 (D) ≥ λ 2 (D) ≥ • • • ≥ λ n (D). Let x be an eigenvector of C + D corresponding to λ 1 (C + D). Recall that (F n ) jk = 1 √ n e 2πijk n
for j, k ∈ Z/nZ. This has rows or columns which simultaneously diagonalize all circulants. Write x = F n x and x h for the conjugate transpose. We use

x 2 = x h x.
Our aim is to prove that for kk < n,

λ 1 (C + D) ≤ λ 1 (C) + λ 1 (D) (6) - 1 2 min{λ 1 (D) -λ k+1 (D), λ 1 (C) -λ k +1 (C)} 1 - kk n 2 .
The first step is to write x h Cx in terms of a Fourier transform pair x = F n x.

A subtle point is that although F n diagonalizes C, the resulting diagonal matrix does not necessarily have entries in decreasing order, necessitating a permutation indexing in the following lemma.

Lemma 1. Define a permutation σ such that

e 2πi n σ -1 j b √ n , 0 ≤ b ≤ n -1
is the eigenvector corresponding to λ j (C). Then

x h Cx = xh D x (7) with D = diag(λ σ1 (C), . . . , λ σn (C)). Proof. Since C is diagonalized by F h n , F n CF h n = D . Thus x h Cx = x h F h n F n CF h n F n x = xh D x.
A key tool is the Donoho-Stark [START_REF] Donoho | Uncertainty principles and signal recovery[END_REF] version of the Heisenberg Uncertainty Principle. For this, call a vector y ' -concentrated on a set S ⊂

[n]' if |x i | < for i / ∈ S.
Theorem 4 (Donoho-Stark). Let y, ŷ be a unit norm Fourier Transform pair with y S -concentrated on S and ŷ T -concentrated on T . Then

(8) |S||T | ≥ n(1 -( S + T )) 2 .
Let (y) S be the projection onto the subspace vanishing off S:

((y) S ) i = y i i ∈ S 0 otherwise .
A simple consequence of the bound (8) is Corollary 1. If kk < n, z, ẑ a unit norm Fourier transform pair and S and T are sets of size k, k , then

(z) S c 2 + (ẑ) T c 2 ≥ 1 2 1 - kk n 2 .
Proof. Let S = (z) S c and T = (ẑ) T c . Then z -(z) S = (z) S c and ẑ -(ẑ) T = (ẑ) T c . Thus z is S concentrated on S and ẑ is T concentrated on T . Thus [START_REF] Diaconis | Group representations in probability and statistics[END_REF] gives

|S||T | n = kk n ≥ (1 -( S + t )) 2 or ( S + T ) ≥ 1 - kk n , so if kk ≤ n (z) S c 2 + (ẑ) T c 2 = ( 2 S + 2 T ) ≥ 1 2 ( s + T ) 2 ≥ 1 2 1 - kk n 2
Proof of Theorem 1. With notation as above,

λ 1 (C + D) = x h (C + D)x = x h Cx + x h Dx = xh D x + x h Dx =: * . Let D = D -λ 1 (D)I and D = D -λ 1 (C)I. Then * = xh λ 1 (C)I x + xh D x + x h λ 1 (D)Ix + x h Dx = λ 1 (C) + xh D x + λ 1 (D) + x h Dx
Now D and D have non-positive eigenvalues so our improvement over the Weyl bounds will follow by showing that x or x have support on suitably negative entries of D or D.

Let S and T correspond to the largest k, k entries of D, D , respectively. Then x = (x) S + (x) S c , x = (x) T + (x) T c . Each of those decomposition is into orthogonal pieces. Multiplying any of the four pieces by an arbitrary diagonal matrix preserves this orthogonality.

Thus * = λ 1 (C) + λ 1 (D) + (x) h T D (x) T + (x) h T c D (x) T c + (x) h S D(x) S + (x) h S c D(x) S c .
For the last four terms on the right, terms 1 and 3 are bounded above by zero and 2 and 4 contribute with the following bounds:

* ≤ λ 1 (C) + λ 1 (D) + (λ k+1 (D) -λ 1 (D)) (x) S c 2 + (λ k +1 (C) -λ 1 (C) (x) T c 2 ≤ λ 1 (C) + λ 1 (D) + min{(λ k+1 (D) -λ 1 (D)), (λ k +1 (C) -λ 1 (C)}   1 2 1 - kk n 2  
where the last line follows from the corollary.

Remarks.

(1) These arguments work to give the smallest eigenvalue as well, so in fact we also have for ll < n:

λ n (C + D) ≥ λ n (C) + λ n (D) (9) + 1 2 min{λ n-l (D) -λ n (D), λ n-l (C) -λ n (C)} 1 - ll n 2 .
(2) Our thanks to a thoughtful anonymous reviewer, who pointed out that Corollary 1 can be improved using Cauchy-Schwartz to show that for 0 < a, b ≤ 1,

1 - kk n 2 ≤ ( s + T ) 2 ≤ (a 2 S + b 2 T ) 1 a + 1 b .
Setting a = λ k+1 (D) -λ 1 (D) and b = λ k+1 (D) -λ 1 (D), one can improve the previous theorem:

λ 1 (C + D) ≤ λ 1 (C) + λ 1 (D) - (λ 1 (D) -λ k+1 (D))(λ 1 (C) -λ k +1 (C)) (λ 1 (D) -λ k+1 (D)) + (λ 1 (C) -λ k +1 (C)) 1 - kk n 2 .
In our case, the result is the same, since the eigenvalues of C and D are identical. (3) Donoho and Stark [START_REF] Donoho | Uncertainty principles and signal recovery[END_REF] give many variations on their uncertainty principle suitable for other transforms. The techniques above should generalize, at least to the G-circulants of [START_REF] Diaconis | Patterned matrices[END_REF]. (4) There should be similar theorems with C and D replaced by general Hermitian matrices and perhaps extensions to higher Weyl and Horn inequalities (see [START_REF] Bhatia | Linear algebra to quantum cohomology: the story of Alfred Horn's inequalities[END_REF] and [START_REF] Fulton | Eigenvalues, invariant factors, highest weights, and Schubert calculus[END_REF]). ( 5) Further applications/examples are in Section 6.

4. The Harmonic oscillator as a limit.

We prove Theorem 2, that for k ≥ 1 the kth largest eigenvalue of

M n is equal to 1 -µ k /n + o(1/n) and the kth smallest eigenvalue of M n is equal to -1 + µ k /n + o(1/n), where µ k is the kth smallest eigenvalue of L = - 1 4
d 2 dx 2 + π 2 x 2 on (-∞, ∞)
. By a classical computation (see [START_REF] Griffiths | Introduction to Quantum Mechanics[END_REF]), µ k = (2k -1)/(2π).

The

n × n matrix M n has j, k-entry 1 4 [δ(j -k -1) + δ(j -k + 1)] + 1 2 cos(2πk/n) δ(j -k), where j, k ∈ Z n = Z/nZ. We define Mn = n (I -M n ).
This has j, k entry m 1 (j, k) + m 2 (j, k), where

(10) m 1 (j, k) = n 2 δ(j -k) - 1 2 [δ(j -k -1) + δ(j -k + 1)] (11) m 2 (j, k) = n 2 (1 -cos(2πk/n)) δ(j -k).
We will show first that if µ is any limit of eigenvalues of Mn then µ is an eigenvalue of L; and, second, that any eigenvalue µ of L has a neighborhood that contains exactly one eigenvalue, counting multiplicity, of Mn for n sufficiently large. These imply the stated result.

These will be accomplished as follows. Give each point of Z n measure 1/ √ n, so the total measure equals √ n. We then define an isometry

T from L 2 (Z n ) to L 2 (- √ n/2, √ n/
2) (thought of as a subspace of L2 (R) with Lebesgue measure) for which the following hold:

Proposition 1. Suppose {u n } is a sequence of functions of norm one in L 2 (Z n ) such that the sequence {( Mn u n , u n )} of inner products is bounded. Then {T u n } has a strongly (i.e., in norm) convergent subsequence. Proposition 2. If φ is a Schwartz function on R then T Mn T * φ → Lφ strongly. 1
These will easily give the desired results. (See Propositions 3 and 4 near the end.) The final section 4.2 treats the smallest eigenvalues. 4.1. Proofs for the largest eigenvalues. We use two transforms (with, confusingly, the same notation). First, for φ in L 2 (-

√ n/2, √ n/2) we define φ( ) = √ n/2 - √ n/2 e -2πi x/ √ n φ(x) dx, ( ∈ Z),
and we have by Parseval (after making the substitution x → x √ n in the integral)

(12) φ = n 1/4 φ .
Here

φ 2 = ∈Z | φ( )| 2 .
For u ∈ L 2 (Z n ) we have its finite Fourier transform

u( ) = k e -2πi k/n u(k), ( ∈ Z n ),
and we compute below that (13) u = n 3/4 u .

Here

u 2 = | u( )| 2 ,
the sum over any integer interval of length n. To show (13), we have

| u( )| 2 = j,k e -2πi (j-k)/n u(j) u(k).
Since e -2πi(j-k)/n is an nth root of unity, equal to 1 only when j = k in Z n , we get

u 2 = | u( )| 2 = n k |u(k)| 2 = n 3/2 u 2 .
Now we define the operator T . Let J be an interval of integers of length n (which later will be specified further) and set

D n (x) = ∈J e 2πi x .
Then T is defined by

(T u)(x) = 1 n k D n x √ n - k n u(k).
Thus T has kernel

T (x, k) = 1 n D n x √ n - k n .
By the definition of the inner product on L 2 (Z n ) we find that

T * : L 2 (- √ n/2, √ n/2) → L 2 (Z n ) has kernel T * (k, x) = 1 √ n D n k n - x √ n .
In terms of the transforms we have the following:

Lemma 2. (a) For u ∈ L 2 (Z n ), T u( ) =    1 √ n u( ) if ∈ J, 0 if ∈ J. (b) For φ ∈ L 2 (- √ n/2, √ n/2), T * φ( ) = √ n φ( ) when ∈ J.
Proof. For (a), we have

T u( ) = 1 n k, ∈J e -2πi x/ √ n e 2πi (x/ √ n-k/n) u(k) dx = 1 n ∈J e 2πi( -)x/ √ n u( ) dx.
The result follows.

For (b), we have when ∈ J,

T * φ( ) = 1 √ n k, ∈J e -2πi k/n e 2πi (k/n-x/ √ n) φ(x) dx = √ n e -2πi x/ √ n φ(x) dx = √ n φ( ).
We show two things about T . For the second we shall assume now and hereafter that the end-points of J are ±n/2 + O(1), although this is a lot stronger than necessary.

Lemma 3. (a) T * T = I. (b) T T * → I strongly as n → ∞. Proof. By Lemma 2b, T * T u( ) = √ n T u( ),
where ∈ J and -∈ nZ. By Lemma 2a this in turn equals u( ), which equals u( ) since u is n-periodic. This gives (a). For (b) observe that T T * is self-adjoint. Since (T T * ) 2 = T T * T T * = T T * , it is a (nonzero) projection and so has norm one. Therefore it suffices to show that if φ is a Schwartz function then T T * φ → φ. We have from Lemma 2a that

T T * φ( ) = 1 √ n T * φ( ) if ∈ J and equals zero otherwise. If ∈ J then by Lemma 2b it equals φ( ). It follows that T T * φ -φ 2 = ∈J | φ( )| 2 .
Integrating by parts shows that

φ( ) = O( √ n/ ),
and so, by our assumption on J, the sum on the right side is O(1). Then by [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF] we get

T T * φ -φ = O(n -1/4 ).
Now the work begins. First, an identity. We introduce the notations

C(ξ) = 1 -cos(2πξ), S(ξ) = sin(πξ),
and observe that

C(ξ) = 2 S(ξ) 2 . Lemma 4. For u ∈ L 2 (Z n ), ( Mn u, u) = n -1/2 S( /n) u( ) 2 + n S(k/n) u(k) 2 .
Note. Here and below we display "k" as the variable in the ambient space Z n and " " as the variable in the space Z n of the Fourier transform. We abuse notation and, for example, the "u(k)" above denotes the function k → u(k).

Proof. We consider first the contribution of [START_REF] Diaconis | Threads through group theory[END_REF] to the inner product. If we define the operators

A ± by (A ± u)(k) = u(k ± 1),
we see that the contribution to the inner product is

n 2 (u -[A + u + A -u]/2, u). Now A ± u( ) = e ±2πi /n u( ),
so if we use [START_REF] Diaconis | Geometric bounds for eigenvalues of Markov chains[END_REF] we see that the above is equal to

1 2 n -1/2 (C( /n) u, u( )) = n -1/2 S( /n) u 2 .
To complete the proof of the lemma we note that the contribution to the inner product of [START_REF] Diaconis | Horseshoes in multidimensional scaling and local kernel methods[END_REF] Proof of (a). We have

is clearly n 2 (C(k/n) u(k), u(k)) = n S(k/n) u(k) 2 .
u n ( ) -u n ( + 1) = k e -2π k/n (1 -e -2πik/n ) u n (k),
the finite Fourier transform of (1 -e -2πik/n ) u n (k). We have,

|(1 -e -2πik/n ) u n (k)| = 2|S(k/n) u n (k)|.
Therefore from [START_REF] Diaconis | Geometric bounds for eigenvalues of Markov chains[END_REF] and

S(k/n) u n (k) = O(n -1/2 ),
which follows from Lemma 4, we get

u n ( ) -u n ( + 1) = O(n 1/4 ).
It follows from Lemma 2a that T u n ( ) = T u n ( + 1) = 0 if both , + 1 ∈ J and ( 14)

, +1∈J | T u n ( ) -T u n ( + 1)| 2 = O(n -1/2 ).
If ∈ J but + 1 ∈ J then T u n ( + 1) = 0 and is the right end-point of J and therefore n/2 + O(1). From ). So the bound in ( 14) holds when the sum is taken over all ∈ Z. Since

T u n ( ) -T u n ( + 1) = e -2πix / √ n (1 -e -2πix/ √ n ) T u n (x) dx, it follows from (12) that S(x/ √ n) T u n (x) = O(n -1/2 ).
In the interval of integration |x| <

√ n/2, so |S(x/ √ n)| is bounded below by a constant times |x|/ √ n.
This gives (a).

Proof of (b). We have

(T u n ) (x) = 2πi n 3/2 k, ∈J e 2πi (x/ √ n-k/n) u n (k) = 2πi n 3/2 ∈J e 2πi x/ √ n u n ( ).
Thus T u n ( ) = 2πi u n ( )/n for ∈ J, and it follows from ( 12) that

(T u n ) 2 = 4π 2 n 5/2 ∈J 2 | u n ( )| 2 . Now |S( /n)| is bounded below by a constant times | /n| for ∈ J, so (15) implies that ∈J 2 | u n ( )| 2 = O(n 5/2 ),
which gives the result.

Proof of Proposition 1. Since T is an isometry each T u n = 1, and by passing to a subsequence we may assume {T u n } converges weakly to some f ∈ L 2 (R). We use the fact that strong convergence will follow if we can show that f ≥ 1. (In general, if f n = 1 and f n → f weakly, then f ≥ 1 implies that f n → f strongly.

Here is the argument. We have that

f n -f 2 = f n 2 + f 2 -2 Re (f n , f ). By weak convergence, (f n , f ) → f 2 . Therefore f n -f 2 → 1 -f 2 ≤ 0, so f n -f → 0.)
The hypothesis of Lemma 5 is satisfied. It follows from Lemma 5a that for each ε > 0 there is a bounded interval A such that

(1 -χ A ) T u n ≤ ε for all n. So χ A T u n ≥ 1 -ε.
It follows from Lemma 5b that {T u n } is equicontinuous, and this combined with χ A T u n ≤ 1 shows that a subsequence of {T u n } converges uniformly on A (to χ A f ), and so

χ A f ≥ 1 -ε. Thus, f ≥ 1.
Proof of Proposition 2. Consider first the operator corresponding to m 1 in [START_REF] Diaconis | Threads through group theory[END_REF]. We call it n∆ 2 k . (The subscript indicates that it acts on functions of k.) We show first that

n T ∆ 2 k T * φ → -φ /4
in L 2 (R). We have

n (T ∆ 2 k T * φ)(x) = 1 2n 1/2 , ,k e 2πi ((x/ √ n-k/n) √ n/2 - √ n/2 ∆ 2 k e 2πi ((k/n-y/ √ n) φ(y) dy
The exponent in the integral is a function of k/ √ n -y. So taking the second difference ∆ 2 k in k is the same as taking the second difference ∆ 2 y in y as long as the differences in the y-variable are 1/ √ n. With this understanding, the above equals

1 2n 1/2 , ,k e 2πi ((x/ √ n-k/n) √ n/2 - √ n/2 ∆ 2 y e 2πi ((k/n-y/ √ n) φ(y) dy.
By changing variables in two of the three summands from ∆ 2 y we can put the ∆ 2 y in front of the φ(y). There is an error because of the little change of integration domains but (for φ a Schwartz function) this is a rapidly decreasing function of n, and so can be ignored. After this what we get is nT T * ∆ 2 φ. Taylor's theorem gives

n(∆ 2 x φ)(x) = -φ (x)/4 + O n -1/2 max |y-x|<1/ √ n |φ (y)| ,
from which it follows that n (∆ 2 x φ)(x) → -φ (x)/4 strongly. Since T T * → I strongly we deduce that n T ∆ 2 k T * φ → -φ /2 strongly. Lastly, consider the operator corresponding to [START_REF] Diaconis | Horseshoes in multidimensional scaling and local kernel methods[END_REF], which is multiplication by

n C(k/n)/2 = n(1 -cos(2πk/n))/2. For convenience we call this operator C n /2.
By Lemma 2b we know that T * φ( ) = √ n φ( ) when ∈ J. In general,

C n u( ) = n k (1 -cos(2πk/n)) e -2πik /n u(k) = n (∆ 2 u)( ),
where here (∆ 2 u)( ) = u( ) -[ u( -1) + u( + 1)]/2. Applying this to T * φ gives

C n T * φ( ) = n ∆ 2 T * φ( ) = n 3/2 ∆ 2 φ( )
as long as ± 1 are also in J. If is in J but one of ± 1 is not in J then is near an end-point of J and the error committed will be rapidly decreasing as n → ∞. For the right side is n 3/2 times a linear combination of integrals like

√ n/2 - √ n/2 e ±πix √ n φ(x) dx,
and integration by parts many time shows this is rapidly decreasing. For the left side, if for example + 1 ∈ J then it is the same as the value at + 1 -n ∈ J, which is rapidly decreasing. So we ignore this little error and use

∆ 2 φ( ) = √ n/2 - √ n/2 e -2πix / √ n C(x/ √ n) φ(x) dx.
We also have T * x 2 φ( ) = √ n x 2 φ( ) for ∈ J. Thus (ignoring the error),

C n T * φ( ) -2π 2 T * x 2 φ( ) = √ n √ n/2 - √ n/2 e -2πix / √ n (n C(x/ √ n) -2π 2 x 2 ) φ(x) dx.
From this we get

C n T * φ -2π 2 T * x 2 φ ≤ n 3/4 (n C(x/ √ n) -2π 2 x 2 ) φ(x) = O(n -1/4 ), since n C(x/ √ n) -2π 2 x 2 = O(x 4 /n) and x 4 φ(x) ∈ L 2 (R).
Then we get from ( 13)

C n T * φ -2π 2 T * x 2 φ = O(n -1 ). Equivalently, T C n T * φ -2π 2 T T * x 2 φ = O(n -1
). Since T T * → I strongly, this gives

T C n T * φ -2π 2 x 2 φ → 0.
Since the operator corresponding to [START_REF] Diaconis | Horseshoes in multidimensional scaling and local kernel methods[END_REF] is multiplication by C n /2, this completes the proof of Proposition 2. Now we go back to the eigenvalues of Mn and easy consequences of Propositions 1 and 2. Proof of (a). Suppose that u n is an eigenvector of Mn of norm one with eigenvalue λ n . In particular ( Mn u n , u n ) = λ n . By Proposition 1 there is a subsequence of {T u n } that converges strongly to some f ∈ L 2 (R). For a Schwartz function φ we have (µf, φ) = lim (λ n T u n , φ) = lim (T Mn u n , φ)

= lim (u n , Mn T * φ) = lim (T u n , T Mn T * φ), since T is an isometry. By Proposition 2, T Mn T * φ converges strongly to Lφ. Therefore 2 the limit equals (f, Lφ), and we have shown

µ(f, φ) = (f, Lφ).
It follows that f is an eigenfunction of L with corresponding eigenvalue µ. Here is why. The eigenfunctions of L are the harmonic oscillator wave functions φ i , and therefore Schwartz functions. If the corresponding eigenvalues are µ i , then

(µ -µ i ) (f, φ i ) = µ (f, φ i ) -(f, Lφ i ) = 0.
Since the φ i are complete and f = 0, some µ -µ k = 0. And f , being orthogonal to the φ i with i = k, must be a multiple of φ k and therefore a corresponding eigenfunction.

Proof of (b). Suppose the contrary were true. Then there would be sequences of eigenvalues {λ n } and {λ n } of Mn , both converging to µ, and corresponding orthogonal (since Mn is self-adjoint) eigenfunctions u n and u n . The strong (sub)limits f and f of T u n and T u n would be mutually orthogonal eigenfunctions of L corresponding to the same eigenvalue µ of L. Since the eigenvalues of L are simple, this cannot happen.

2 For this we need only weak convergence of one and strong convergence of the other. But we also need that f = 0, which is no easier to show than strong convergence of T un, and we shall need strong convergence of T MnT * φ for Proposition 4.

Proposition 4. For each eigenvalue µ of L there is a sequence of eigenvalues λ n of Mn that converges to µ.

Proof. With corresponding eigenfunction φ of L we have, by Proposition 2,

T Mn T * φ -µ φ = T Mn T * φ -L φ = o(1).
From this, and that φ -T T * φ = o(1) by Lemma 3b, we get

T ( Mn T * φ -µ T * φ) = o(1).
Since T is an isometry this is the same as Mn T * φ -µ T * φ = o(1).

Since T * φ = T T * φ → φ = 0, and the other eigenvalues of L are bounded away from µ, this implies that µ is within o(1) of an eigenvalue of Mn and T * φ within o(1) of an eigenvector. See [START_REF] Diaconis | Horseshoes in multidimensional scaling and local kernel methods[END_REF].

Combining Propositions 3 and 4 shows that the kth largest eigenvalue of M n equals 1 -µ k /n + o(1/n).

4.2.

The bottom eigenvalues of M n . We shall find a unitary operator U on L 2 (Z n ) such that the quadratic form for n(I +U n M n U * n ) is the same as for n(I -M n ) when n is even and close to it when n is odd. From that it will follow that the kth bottom eigenvalue of

M n equals -1 + µ k /n + o(1/n).
Recall that Lemma 4 says that

(n(I -M n ) u, u) = n -1/2 S( /n) u 2 + n S(k/n) u(k) 2 =: Q(u),
where S(ξ) = sin(πξ). For this we used the identity 1 -cos ξ = 2 sin 2 (ξ/2). For n(I + M n ) this gets replaced by 1 + cos ξ = 2 cos 2 (ξ/2). So now we define

C(ξ) = cos(πξ),
and get

(n(I + M n ) u, u) = n -1/2 C( /n) u 2 + n C(k/n) u(k) 2 .
We consider first the less straightforward case of n odd and define

v(k) = e 2πiαk u (k -(n + 1)/2) ,
where α (real) will be determined below. We have

C(k/n) u(k) = C(k/n + 1/2 + 1/2n) v(k) = S(k/n + 1/2n) v(k) . Next, v( ) = k e -2πik /n e 2πiαk u (k -(n + 1)/2)
= k e -2πi(k+(n+1)/2) /n e 2πiα(k+(n+1)/2) u(k) = (-1) e -πi /n e πiα(n+1) k e -2πik /n e 2πiαk u(k)

We choose α = -(n + 1)/2n. The factor outside the sum has absolute value 1 while the sum becomes u( + (n + 1)/2). Alternatively,

| u( )| = | v( -(n + 1)/2)|. Therefore C( /n) u( ) = C( /n + 1/2 + 1/2n) v( ) = S( /n + 1/2n) v( ) .
The map U : u → v is unitary and we have shown Lemma 6. For n odd we have,

(n(I + U M n U * ) v, v) = n -1/2 S( /n + 1/2n) v( ) 2 + n S(k/n + 1/2n) v(k) 2 .
Remark. . When n is even we replace the shift (n + 1)/2 by n/2 and α by -1/2, and the extra 1/2n's do not appear in the arguments of the S's. The quadratic form becomes Q(v) exactly, so

U n M n U * n = -M n . 3 Proposition 5. (n(I + U M n U * ) v, v) = (1 + O(n -1/2 )) Q(v) + O(n -1/2 v 2 ).
Proof. Since dS/dξ is bounded,

S(k/n + 1/2n) v(k) ≤ S(k/n) v(k) + O(n -1 v(k) ).
It follows from the arithmetic-geometric mean inequality that for any ε > 0

|a + b| 2 ≤ (1 + ε) |a| 2 + (1 + ε -1 ) |b| 2 .
We will take ε → 0 as n → ∞, so we obtain

S(k/n + 1/2n) v(k) 2 ≤ (1 + ε) S(k/n) v(k) 2 + O(ε -1 n -2 v(k) 2 ).
Similarly,

S( /n + 1/2n) v 2 ≤ (1 + ε) S( /n) v 2 + O(ε -1 n -2 v) 2 ) = (1 + ε) S( /n) v 2 + O(ε -1 n -1/2 v 2 ),
where we used v = n3/4 v . Thus, (n

(I + U M n U * ) v, v) ≤ (1 + ε) Q(v) + O(ε -1 n -1 v 2 ).
Similarly,

(n(I + U M n U * ) v, v) ≥ (1 + ε) -1 Q(v) -O(ε -1 n -1 v 2 ).
We set ε = n -1/2 and put the inequalities together to get the statement of the proposition.

Recall that

Q(v) = (n(I -M n ) v, v).
If in the statement of the proposition we take the minimum of both sides over all v with v = 1 we deduce that

n + nλ n = (1 + O(n -1/2 ))(n -nλ 1 ) + O(n -1/2 ),
where λ n is the bottom eigenvalue of M n and λ 1 the top eigenvalue. Since 1), and then n + nλ n = µ 1 + o(1), and then

λ 1 = 1 -µ 1 /n + o(1/n), we have n -nλ 1 = µ 1 + o(
λ n = -1 + µ 1 /n + o(1).
Using the minimax characterization of the eigenvalues we show similarly that λ n-k+1 = -1 + µ k /n + o(1) for each k.

A Stochastic Argument

This section gives a bound on the largest eigenvalue of the matrix M n using a probabilistic argument. By inspection,

M n = 1 3 I + 2 3
M n is a sub-stochastic matrix (with non-negative entries and row sums at most 1). Take M n as in ( 2), an (n + 1) × (n + 1) stochastic matrix corresponding to a Markov chain absorbing at 0. The first (Dirichlet) eigenvector has first entry 0 and its corresponding eigenvalue β * is the top eigenvalue of M n . Thus

β = β * -1 3 (2/3) = 3 2 β * - 1 2
is the top eigenvector of M n . We will work in continuous time, thus, for any transition matrix M ,

M t = ∞ j=0
e -t M j t j j! = e t(M -I) .

The matrix L = I -M , the opposite of the generator of the semigroup {M t } t≥0 , has row sums zero, and non-positive off diagonal entries. 4 If v is a right eigenvector of M with eigenvalue β, then v is an eigenvector of L with eigenvalue 1-β. A lower bound for the non trivial eigenvalues of L gives an upper bound for the eigenvalues of M . Throughout, we specialize to L = I -M n , let λ * be the lowest non-zero eigenvalue of L, and β the highest eigenvector of M n .

Standard theory for absorbing Markov chains with all non-absorbing states connected shows that if τ is the time to first absorption, for any non absorbing state ξ, as t tends to infinity, lim t→∞

-log P ξ (τ > t) t = λ * .
Thus an upper bound on β will follow from an upper bound on P ξ (τ > t). Here is an outline of the proof. Begin by coupling the absorbing chain of interest with a simple random walk on C n = Z/(nZ). For a fixed b, let τ b be the first time that the simple random walk travels ±b from its start. We derive the bound

P ξ (τ > τ b ) ≤ G b ,
P {τ > c 1 mµ b } ≤ G m b + e -c2m .
4 Since some of our readers (indeed some of our authors) may not be probabilists we insert the following note; given any matrix L(x, y) with row sums zero and non-positive off diagonal entries one may construct a continuous time Markov process W = (Wt) t≥0 as follows. Suppose W 0 = w 0 is fixed. The process stays at w 0 for an exponential time σ 0 with mean 1/|L(w 0 , w 0 )|. (Thus P {σ 0 ≥ t} = e -tL(w 0 ,w 0 ) .) Then, choose w 1 = w 0 with probability |L(w 0 , w 1 )|/L(w 0 , w 0 ). Stay at w 1 for an exponential time σ 1 (with mean 1/L(w 1 , w 1 )). Continue, choosing from L(w 1 , .)/L(w 1 , w 1 ).

In our problem, classical random walk estimates show µ b ∼ b 2 . We show, for b = √ n, G √ n is bounded away from one. Thus

P {τ > c 1 mµ b } ≤ 2 max(G m b , e -c2m ) and log P {τ > c 1 mµ b } mµ b ≤ c µ b = c
n for some c , c < 0. Backtracking gives the claimed bound in Theorem 3.

The argument is fairly robust-it works for a variety of diagonal entries. At the end of the proof, some additions are suggested which should give the right constant multiplying 1 n . We begin by constructing two processes. For as long as possible, general absorption rates will be used. Let X = (x t ) t≥0 be the standard continuous time random walk on Z with jump rates 1 between neighbors. Take x 0 = 0. Fix b ∈ Z + and let τ b be the first hitting time of {-b -1, b + 1}: ( 16)

τ b = inf{t ≥ 0 : |x t | = b + 1}
Let {u x } x∈Z be killing rates, e.g. arbitrary non-negative real numbers. Add a cemetery state ∞ to Z. An absorbed process x = (x t ) t≥0 , behaving as x until it is absorbed at ∞ with the rates {u x } x∈Z can be constructed as follows: Let E be an independent exponential random variable with mean 1. Define an absorption time

τ ∈ [0, ∞] by τ = inf t≥0 t 0 µ xs ds ≥ E .
As soon as {u x } x∈Z does not vanish identically, τ is characterized by [START_REF] Allen | The passage time distribution for a birth-and-death chain: strong stationary duality gives a first stochastic proof[END_REF] τ 0 u xs ds = E.

More simply,

x t = x t if t < τ ∞ otherwise for 0 ≤ t < ∞.
The two processes are defined on the same probability space as are τ and τ b . The first goal is to estimate the chance that τ > τ b in terms of the given rates. Our bounds are crude but suffice for Theorem 3. Proposition 6. With notation as above, for any b ≥ 1, ( 18)

P {τ > τ b } ≤ 1 1 + (b + 1) 2 v 0 /2 b k=1 1 1 + (b + 1)(b + 1 -k)v k 1 b+1 with v k = min(u -k , u k ).
Note that the bound is achievable; if all v y = 0 then both sides equal 1.

Proof. For any k ∈ Z, v k ≤ u k . Thus if τ is the stopping time defined in [START_REF] Allen | The passage time distribution for a birth-and-death chain: strong stationary duality gives a first stochastic proof[END_REF] with u k replaced by v k , τ ≥ τ . Therefore it is sufficient to bound P {τ > τ b } from above. Now, everything is symmetric about zero. Consider the process Y = (Y t ) t≥0 = (|x t |) t≥0 . This is Markov with jump rates:

J(y, y ) =      2 if y = 0, y = 1 1 if y = Z +
L y (t) = t 0 δ y (Y s )ds for y ∈ Z + , t ≥ 0,
where δ y is the indicator function of y. For any t ≥ 0,

t 0 v xsds = 0≤y≤b v y L y (t). This gives {τ > τ b } = { 0≤y≤b v y L y (τ b ) < E}.
Taking expectations of both sides with respect to E

P {τ > τ b } = E    exp   - 0≤y≤b v y L y (τ b )      (19)
≤ b y=1 E {exp (-(b + 1)v y L y (τ b ))} 1 b+1 . ( 20
)
The last bound follows from Hölder's inequality (with b + 1 functions). It is well known (see [START_REF] Kent | The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes[END_REF] or Claim 2.4 of [START_REF] Peres | Total variation cutoff in a tree[END_REF] for the discrete time version) that for any y, 1 ≤ y ≤ b, L y (τ b ) is distributed as an exponential random variable with mean (b + 1 -y) and L 0 (τ b ) is exponential with mean b+1

2 . (The process leaves zero twice as fast as it leaves other points.) Thus, for 1 ≤ y ≤ b,

E{exp(-(b + 1)v y L y (τ b )} = (b + 1 -y) -1 (b + 1 -y) -1 + (b + 1)v y . E{exp(-(b + 1)v 0 L 0 (τ b )} = 1 1 + (b + 1) 2 v 0 /2 .
This completes the proof of Proposition 6.

The bound of Proposition 6 suggests introducing functions F b , G b on R b+1 + . Given by

F b (v) = 1 1 + (b + 1) 2 v 0 /2 b l=1 1 1 + (b + 1)(b + 1 -i)v l 1 l+1 (21) G b (v) = b k=0 1 1 + (b + 1)(b + 1 -k)v k /2 1 (b+1) . ( 22
)
They have the following crucial monotonicity properties: say that v, v ∈ R b+1 satisfies v ≤ v if this is true coordinate-wise. For v ∈ R b+1 , let v be the nondecreasing rearrangement of v. Then

F b (v) ≤ G b (v) (23) v ≤ v ⇒ G b (v) ≥ G b (v ) (24) G b (v) ≤ G b (v) (25)
Return now to the process underlying Theorem 3 (still keeping the extinction rates general.) Let z = (z t ) t≥0 be defined on Z/nZ; it jumps to nearest neighbors at rate l and is killed with rates u = (u ξ ) ξ∈Z/nZ . Suppose z o = ξ. Let v p , 0 ≤ p ≤ n-1 denote the non-decreasing rearrangement of u. Let τ be the absorption time of z. Fix b, 0 ≤ b ≤ n/2 -1 and let

τ b = inf t>0 {z τ ∈ {ξ -b -1, ξ + b + 1}}.
Proposition 6 in conjunction with properties ( 23), [START_REF] Lawler | Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality[END_REF], and [START_REF] Mehta | Eigenvalues and eigenvectors of the finite Fourier transform[END_REF], imply that for any u, with G b (u) depending only on the first b coordinates of u,

(26) P ξ [τ > τ b ] ≤ G b (u).
Note that the upper bound is independent of ξ.

Introduce a sequence ξ i of further stopping times: ξ 1 = ξ b , and if ξ m has been constructed, [START_REF] Pham | Reliability of a standby system with beta-distributed component lives. Reliability[END_REF]

ξ m+1 = inf{t > ξ m : z t ∈ {z ξm -b -1, z ξm + b + 1}}
Informally speaking these stopping times end up being good. Because they cannot be larger than τ , as in the previous treatment of a random walk on Z/nZ coinciding with z t up to the absorption time, then ξ m are (almost surely) finite for all m and the strong law of large numbers gives:

lim m→α ξ m m → µ b = (b + 1) 2
where µ b = E{ξ 1 } = (b + 1) 2 from the Classical Gambler's Ruin (see Chapter 14 of [START_REF] Feller | An introduction to probability theory and its applications[END_REF]). This suggests that, for m large, the quantities

P ξ [τ > mµ b ] and P ξ [τ > ξ m ]
should behave similarly. Of course, care must be taken because τ and ξ m are not independent. To proceed, we use a large deviations bound for ξ m .

Proposition 7. For ξ m defined in [START_REF] Pham | Reliability of a standby system with beta-distributed component lives. Reliability[END_REF], there are positive constants, c 1 , c 2 , independent of b and n such that for all m ≥ 1,

P [ξ m > c 1 mµ b ] ≤ e -c2m .
Proof. Observe first that this is simply a large deviations bound for the first hitting time of the simple random walk ( 16) so that n does not enter. The law of ξ 1 is well known (see [START_REF] Keilson | Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes[END_REF], [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF], and [START_REF] Allen | The passage time distribution for a birth-and-death chain: strong stationary duality gives a first stochastic proof[END_REF]). It can be represented as a sum of b + 1 independent exponential variables with means a 1 , a 2 , . . . , a b+1 given by:

a -1 k = 2 1 -cos π(2k -1) 2(b + 1) .
Thus for θ ∈ (0, a 1 )

E[e θξ1 ] = b+1 k=1 a k a k -θ .
By simple calculus, there is c > 0 such that for all a ∈ (0, We can now set up a bound for the top eigenvalue. Working on Z/nZ but still with general absorption rates:

P ξ [τ > c 1 mµ b ] = P ξ [τ > c 1 mµ b ; ξ m ≤ c 1 mµ b ] + P ξ [τ > c 1 mµ d , ξ m > c 1 mµ b ] (28) ≤ P ξ [τ > ξ m ] + P ξ [ξ m > c 1 mµ b ] (29) ≤ G m b (v) + e -c2m . (30)
It follows that

λ * = -lim m→∞ 1 c 1 mτ b log(P ξ [τ > c 1 mτ b ]) ≥ 1 c 1 τ b min{c 2 , -log(G b (x))}.
Since µ b = (b+1) 2 , proving that with b of order √ n, -log(G b (x)) is bounded below by a positive constant, uniformly in n, will complete the proof.

Up to now, the kill rates u have been general. Specialize now to the rates for the matrix M with any scrambling of its diagonal. The vector v is given by the b + 1 entries of: Indeed,

0, 1 3 1 -cos 2π n , 1 3 1 -cos 2π n , 1 3 1 -cos 4π n , 1
-log(G b (v)) = 1 b + 1 b-1 y=0 log 1 + (b + 1)(b + 1 -y) 1 -cos 2π n y + 1 2 ∼ 2π 2 n 2 1 b b-1 y=0 (b + 1)(b + 1 -y) y + 1 2 2 ∼ π 2 b 4 2n 2 1 b b-1 y=0 1 - y b y b 2 ∼ π 2 b 4 2n 2 1 0 (1 -y)y 2 dy ∼ π 2 24 .
where σ : Z * p → Z p-1 is the group morphism such that σ(g) = 1. Then

Q(ρ α ) = 3 5 + 2 5 cos 2πα p -1 .
There is one (p -1) dimensional representation ρ. This may be realized on

V = {f : {1, 2, . . . , p -1} → C} with ρ(a, b)f (j) = e 2πijb p f (aj), 1 ≤ j ≤ p -1.
It is easy to check directly that ρ is a representation with character

χ(a, b) =      0 a = 1 -1 a = 1, b = 0 p -1 a = 1, b = 0 . A further simple check shows that χ|χ = 1 p(p-1)
a,b |χ(a, b)| 2 = 1 and that χ is orthogonal to the characters ρ α in [START_REF] Whittaker | infinite processes and of analytic functions[END_REF]. It follows that {ρ α } p-1 α=1 , ρ is a full set of irreducible representations. Choose a basis δ g a (•) for V , 0 ≤ a ≤ p -2. Then, for Q in [START_REF] Wang | Quasiclassical approximations for almostmathieu equations[END_REF],

Q(ρ) = 1 5 1 1 1 1 1 1 1 1                     1 + 2 cos 2πj p , 1 ≤ j ≤ p -1 .
Using any of the three techniques above, there is a constant c > 0 such that the largest and smallest eigenvalues of Q(ρ) (in absolute value) are bounded above by 1 -c p . Combining bounds . This shows that the walk is close to random after order p 2 log(p) steps. In the Heisenberg examples the Weyl bounds give a bound of 1 which is useless.

4 Q * k -U 2 T V ≤ p-1 j=1 3
The methods above can be applied to other walks on other groups. While we won't carry out the details here, we briefly describe two further examples and point to our companion paper [START_REF] Bump | Characters and super characters for step two nilpotent groups with applications to random walks[END_REF] for more.

Example 2 (Borel Subgroup of SL 2 (F p )). Let G be the 2 × 2 matrices of the form:

a b 0 a -1 a ∈ F * p , b ∈ F p ↔ (a, b).
A minimal generating set (with the identity) is S = {id, (g, 0), (g -1 , 0), (1, 1), (1, -1)}, g a generator of F * p . The group has order p(p -1) with p -1 1-dimensional representations and 4 representations of dimension (p -1)/2. They are explicitly described in [START_REF] Curtis | Representation theory of finite groups and associative algebras[END_REF] p. 67. The Fourier analysis of the measure Q supported on S is almost the same as the analysis for the affine group. The results are that order p 2 steps are necessary and sufficient for convergence to the uniform distribution.

Example 3 (M (p 3 )). There are two nonabelian groups of order p 3 : the Heisenberg group discussed above and M (p 3 ). See [START_REF] Suzuki | Group theory. II, volume 248 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF] Chapter 4 Section 4. One description of the latter is:

M (p 3 ) = {(a, b) : a ∈ Z p , b ∈ Z 2 p }, (a, b)(a , b ) = (a + a , a * b + b) with a * b = (1 + ap)b (mod p 2 )
. This group has the same character table as H 1 (p). It thus has p 2 1-dimensional representations and p -1 representations of dimension p. A minimal generating set (for odd p the identity is not needed to take care of parity problems) is S = {(1, 0)(-1, 0)(0, 1), (0, -1)}.

The Fourier transforms of the associated Q at the p dimensional representations have the same form as the matrices in (1) with diagonal elements 2 cos 2πc p 2 (1 + jp) , 0 ≤ j ≤ p -1 where 1 ≤ c ≤ p -1 is fixed (for the cth representation). We have not carried out the details, but, as shown in [START_REF] Diaconis | Threads through group theory[END_REF], it is known that order p 2 steps are necessary and sufficient for convergence.

Eigenvalues in the Bulk

Consider the matrix M n (a) as in (1) with cos 2πja m , 0 ≤ j ≤ n -1 as the diagonal elements. The sections above give bounds on the largest and smallest eigenvalues. It is natural to give bounds for the empirical measure of all the eigenvalues. This is straightforward, using a theorem of Kac-Murdock-Szegö from [START_REF] Kac | On the eigenvalues of certain Hermitian forms[END_REF]. We use the elegant form of Trotter [START_REF] Hale | Eigenvalue distributions of large Hermitian matrices; Wigner's semicircle law and a theorem of Kac, Murdock, and Szegő[END_REF]. If

). Note that the curve has a very extreme, but finite slope around -1 and 1. For example, although it is clear that f 2 (-1) = 0, the small point on the left of the picture corresponds to (-.99, f 2 (-.99)) ≈ .32

be the associated empirical measure. To describe the limit let

d 2 2 (Λ n , µ 2 ) = sup E|W -Z| 2 with W ∼ Λ n , Z ∼ µ 2 .
Theorem 6. Let Λ n be the empirical measure of the matrix M n (a) with 1 ≤ a ≤ n -1. Let µ 2 be defined by (33). Then, with a fixed, as n → ∞, d 2 (Λ n , µ 2 ) → 0.

See Figure 1 for an example.

Remark. We have not seen a way to use this kind of asymptotics to bound the rate of convergence of a random walk. Indeed our limit theorem shows that the distribution of the bulk does not depend on a while previous results show the extreme eigenvalues crucially depend on a. (34)

f (x) = 1 π √ 1-x 2 -1 ≤ x ≤ 1 0 else .
Trotter shows that the empirical measure is close to µ 2 , the distribution of σ.

It follows that the empirical measure of the eigenvalues has limiting distribution the law of (X + Y )/2 where X and Y are independent with density f (x). This convolution has density This is a complete elliptic integral and equals

π 2 F 2,1 1 2 , 1 2 ; 1, k 2 .
(See Section 22.301 of [START_REF] Whittaker | infinite processes and of analytic functions[END_REF].) For ease of notation, we will evaluate

f 3 (x) = min(1,x+1) max(-1,x-1)
dt This is an even function of x so it is enough to consider when x 0. Then we need to evaluate b -b dt h(t) .

(1 -t 2 )(1 -(x -t)

Lemma 5 .

 5 Suppose u n satisfy ( Mn u n , u n ) = O(1). Then (a) x T u n (x) = O(1), and (b) (T u n ) = O(1).

  [START_REF] Donoho | Uncertainty principles and signal recovery[END_REF] S( /n) u n ( ) = O(n 1/4 ), which also follows from Lemma 4, and that |S( /n)| is bounded below for = n/2 + O(1), we have in particular that u n ( ) = O(n 1/4 ), Therefore T u n ( ) = O(n -1/4

Proposition 3 .

 3 (a) If λ n are eigenvalues of Mn and λ n → µ, then µ is an eigenvalue of L. (b) Any eigenvalue µ of L has a neighborhood that contains at most one eigenvalue (counting multiplicity) of Mn for sufficiently large n.

1 b

 1 where G b < 1 is a particular constant described below. Define a sequence of stopping times τ i b as follows. τ 1 b = τ b , τ 2 b is the first time following τ that the walk travels ±b, similarly define τ m b . By the strong law of large numbers, τ m b /m → µ b = E(τ 1 b ) almost surely. Thus P {τ > mµ b } ∼ = P {τ > τ m b }. Using the Markov property, P {τ > τ m b } ≤ G m b . This implies there are positive c 1 , c 2 with

  and |y -y| = 1 0 otherwise. Clearly τ b = inf t≥0 {Y t = b + 1}. Define the family of local times associated to Y :

1 2 ]-c 1 a 1 mµ b 2 E

 22 , -log(1 -a) ≤ ca. Thus, for θ ∈ (0, a 1 /2], E(e θξ1 ) ≤ e cθ b+1 n=1 Note that a n is of order (n/b) 2 so the right side of the last inequality is bounded uniformly in b, say by k > 1. Now, ξ n is a sum of m i.i.d. random variables so for any c 1 > 0P [ξ m > c 1 mµ b ] ≤ e [e a1ξ1/2 ] m ≤ e -m(c1a1µ b )/2-log k . Since µ b = (b + 1) 2 ,a 1 µ b can be bounded below by a constant > 0, uniformly in b ∈ N. Thus if c 1 = 4 log k/ , the claimed bound holds with c 2 = log(k).

2 n

 2 From the definition of G b at (21) with b = √ n , a Riemann sum approximation gives lim n→∞ G b (v) = e -π 2 24 .

. 2 k p 2 + 2 5 cos 2πj p , 1 ≤

 221 Using cos(x) = 1 + x 2 2 + O(x 4 ), the sum is at most c 1 e -c for universal c 1 , c 2 . The final term is exponentially smaller proving the upper bound. The lower bound follows from the usual second moment method. (See[START_REF] Diaconis | Group representations in probability and statistics[END_REF] Chapter 3 Theorem 2 for details.) Further details are omitted. Remark. In this example, the matrix Q(ρ) is again the sum of a circulant and a diagonal matrix. Here, the circulant has eigenvalues 2 5 cos 2πj p-1 , 0 ≤ j ≤ p -2 and the diagonal matrix has entries3 5 j ≤ p -1. The Weyl bounds show that the largest and smallest eigenvalues are bounded in absolute value by 1 -θ p 2 for some fixed θ > 0. Using this to bound the final term in the upper bound gives (p -1) 2 1 -c p 2 2k

λ 1 ≥Figure 1 .

 11 Figure1. The curve shows the eigenvalues predicted by f 2 , while the histogram gives the distribution of the actual eigenvalues of M 10,000 (= M 10,000 (1)). Note that the curve has a very extreme, but finite slope around -1 and 1. For example, although it is clear that f 2 (-1) = 0, the small point on the left of the picture corresponds to (-.99, f 2 (-.99)) ≈ .32

F 2 , 1

 21 is the hypergeometric function. Let µ 2 be the associated measure. Distance between Λ n and µ 2 is measured in the d 2 Wasserstein distance:

Proof.

  Trotter's version of the Kac-Murdock-Szegö theorem applies to M n . If σ(x, y) = cos(2πax) + cos(2πy) 0 ≤ x, y ≤ 1, consider σ as a random variable on [0, 1] 2 , endowed with the Lebesgue measure. This has distribution cos(2πaU 1 ) + cos(2πU 2 ) where U 1 and U 2 are independent uniform on [0, 1]. An elementary calculation shows that cos(2πaU ) has an arc-sine density f (x) no matter what the integer a is.

1 ( 1 ( 1 -

 111 (2x-y) 2 -1)(y 2 -1) dy -1 ≤ x ≤ 1 0 else .The arguement below shows that this integral is in fact integral in (34) is in fact a well known integral in a different guise. Let 0 k t 2 )(1 -k 2 t 2 ) .

  2 ) for |x| 2 Making the variable change t → t + x 2 it becomes

		min(-x 2 +1, x 2 +1)	dt
		max(-x 2 -1, x 2 -1)	h(t)
	where	h(t) = (a 2 -t 2 )(b 2 -t 2 ),	a = 1 +	x 2	, b = 1 -	x 2	.

The operator T * acts on L

(-√ n/2, √ n/2), so φ is first to be restricted to (-√ n/2, √ n/2).

This is easy to see directly.

Acknowledgment. As this work progressed, we received useful comments from Florin Boca, Ben Bond, Bob Guralnick, Susan Holmes, Marty Isaacs, Evita Nestoridi, Jim Pitman, Laurent Saloff-Coste, and Thomas Strohmer. We offer thanks for the remarks of our very helpful reviewer.

authors would like to acknowledge partial support from NSF grants DMS 1001079, DMS 08-04324, DMS 1303761, and DMS 1400248 (respectively). The remaining author would like to acknowledge partial support from ANR grant number ANR-12-BS01-0019.

Combining the pieces, we use β for the highest eigenvalue of M n and thus β = 3 2 β * - 1 2 . Using this notation, we have shown that c n ≤ λ * = 1 -1 3 + 2 3 β . Thus β ≤ 1 -3c 2n . This completes the argument and ends the proof of Theorem 3. Remarks. The above argument can be modified to handle quite general diagonal elements (in particular cos 2πaj n , 0 ≤ j ≤ N -1, needed for the application to the Heisenberg random walk). Indeed, for a = o(n), the argument goes through with no essential change with b = n a to show that with diagonal entries cos 2πaj n , 0 ≤ j ≤ n -1, the eigenvalue bound 1 -ca n holds (with c > 0 independent of n and a).

The use of Hölder's inequality in [START_REF] Griffiths | Introduction to Quantum Mechanics[END_REF] is crude. The joint distribution of the local times of birth and death processes is accessible (see [START_REF] Kent | The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes[END_REF]). We hope this can be used to give sharp results for the constant. Finally we note that the approach to bound β via an associated absorbing Markov chain was used in [START_REF] Bump | An Exercise (?) in Fourier Analysis on the Heisenberg Group[END_REF]. There, a geometric path argument was used to complete the analysis. This gave cruder bounds (β ≤ 1-c n 4 3

) but the argument worked for diagonal entries cos 2πaξ n for any 1 ≤ a ≤ n 2 as well as negative eigenvalues.

A random walk on the affine group (mod p)

Let A p be the affine group (mod p). Here, p is prime and elements of A p can be represented as pairs (a, b),

All entries are taken mod p. Fix a generator g of the multiplicative group. Let S = {(1, 0), (1, 1), (1, -1), (g, 0), (g -1 , 0)}.

Set (31)

Convolution powers of Q converge to the uniform distribution U (h) = 1 p(p-1) . We use the representation theory of A p and the analytic results of previous sections to show that order p 2 steps are necessary and sufficient for convergence. Theorem 5. With definitions above, there are positive universal constants c 1 ,c 2 , and c 3 such that for all primes p and k ≥ 1

Proof. By the usual Upper Bound Lemma (see [START_REF] Diaconis | Group representations in probability and statistics[END_REF], Chapter 3):

Here, the sum is over nontrivial irreducible representations Make the variable change t → bt and the integral becomes

The factor of 2 comes from the fact that we are integrating an even function from -1 to 1, whereas in (37) the integral is from 0 to 1. Thus Remark. [START_REF] Pham | Reliability of a standby system with beta-distributed component lives. Reliability[END_REF] gives a similar expresson for the sum of two general beta variables.


Daniel Bump

Persi Diaconis

Angela Hicks

Laurent Miclo

Harold Widom

AN EXERCISE (?) IN FOURIER ANALYSIS ON THE HEISENBERG GROUP

Let H(n) be the group of 3 × 3 uni-uppertriangular matrices with entries in Z/nZ, 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.

Introduction

For a positive integer n, let H(n) be the "Heisenberg group mod n," the group of 3 × 3 uni-uppertriangular matrices with entries in Z/nZ:

  1 x z 0 1 y 0 0 1  
x, y, z ∈ Z/nZ.

Write such a matrix as (x, y, z), so (x, y, z)(x , y , z ) = (x + x , y + y , z + z + xy ).

A minimal symmetric generating set is S = {(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0)} (1) A random walk proceeds, starting at the identity (0, 0, 0), by repeatedly choosing an element from S with probability 1 4 and multiplying.

The first three authors can be contacted at: Department of Mathematics, Stanford University, 450 Serra Mall, Bldg. 380, Stanford, CA 94305-2125, USA.

The fourth author can be contacted at: Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118, route de Narbonne, F-31062 Toulouse Cedex 9, France.

The fifth author can be contacted at: UC Santa Cruz, Department of Mathematics, Santa Cruz, CA 95064, USA.

More formally, define

Q(g) = 1 4 g ∈ S 0 otherwise . (2) For g ∈ H(n), Q * Q(g) = h Q(h)Q(gh -1 ), Q * k (g) = h Q(h)Q * (k-1) (gh -1 ).
If n is odd, high convolution powers of Q converge to the uniform distribution U (g) = 1 n 3 , Q * k (g) → U (g). Measure the speed of convergence by the total variation distance

Q * k -U = max A⊆H |Q * k (A) -U (A)| = 1 2 g∈H |Q * k (g) -U (g)|.
One purpose of this paper is to give a new proof of the following theorem.

Theorem 1. For Q defined by [START_REF] Assaf | A rule of thumb for riffle shuffling[END_REF] on H(n), there are universal positive constants A and C such that

Ae -2π 2 k n 2 ≤ Q * k -U T V ≤ Ce -2π 2 k n 2
for all odd n and all k.

We say "order n 2 steps are necessary and sufficient for convergence." Theorem 1 is proved by Fourier analysis on H(n). This natural approach is known to be challenging. (See Section 2.) As explained in Section 3, the Fourier proof involves bounding the spectrum of the n×n matrices (where the unmarked entries are taken to be zero):

(3) M (ξ) = 1 4

2 1 1 1 1 1 1 1 1                     2 cos 2πξj m , 0 ≤ j ≤ m -1
These same matrices come up in a variety of solid state physics and ergodic theory problems as 'Harper's Operator,' 'Hofstader's Butterfly,' and the 'Ten Martini's Problem' discussed in Section 2. They further occur in the engineering literature on the fast Fourier transform and for other random walks on the meta-abelian groups. Section 2 is a literature review, including the parallel problem of a random walk on H(R) and H(Z). It describes the physics problems, the connections with the fast Fourier transform, and connections to Levy's area. Section 3 gives background on Fourier analysis on H(n). Theorem 1 is proved there assuming our eigenvalue bounds (which are proved later). It also gives a variety of other walks on other groups where matrices M (ξ) (and thus our bounds) appear.

Eigenvalue bounds are given in Section 4. Two new techniques are developed. The first uses geometric path methods, developed for Dirichlet eigenvalues of stochastic matrices to give upper bounds for the largest eigenvalue of M (ξ); note that some entries of M (ξ) are negative and the rows don't sum to a constant. The second is a new technique for lower bounds on smallest eigenvalues. The bounds are rough (but more than adequate for the task) and work generally.

Acknowledgment. We have benefited from useful comments and technical help from Laurent Saloff-Coste, Marty Isaacs, Je-Way Zhou, Steven Kivelson, Steve Evans, Mehrdad Shahshahani, Thomas Strohmer, Yi Zhang, Akash Maharaj, and Arun Ram. Also, the first, second, third, and fifth authors would like to acknowledge partial support from NSF grants DMS 1001079, DMS 08-04324, DMS 1303761, and DMS 1400248 (respectively). The remaining author would like to acknowledge partial support from ANR grant number ANR-12-BS01-0019.

Background and References

For background on Markov chains and random walks on groups, a good introduction is [START_REF] Levin | Markov chains and mixing times[END_REF]. The Fourier approach is developed in [START_REF] Diaconis | Group representations in probability and statistics[END_REF]. A variety of analytic approaches are described in [START_REF] Saloff-Coste | Probability on groups: random walks and invariant diffusions[END_REF] and [START_REF] Saloff-Coste | Random walks on finite groups[END_REF]. The Heisenberg group is ubiquitous in mathematics and physics through its connections to the quantum harmonic oscillator [START_REF] Cartier | Quantum mechanical commutation relations and theta functions[END_REF], Harmonic analysis [START_REF] Howe | On the role of the Heisenberg group in harmonic analysis[END_REF], theta functions ( [START_REF] Ichi Igusa | Theta functions[END_REF], [START_REF] Lion | The Weil representation, Maslov index and theta series[END_REF]), and number theory [START_REF] Bump | Automorphic forms and representations[END_REF]. Analysis and geometry on the Heisenberg group have recently been important in finding counterexamples to the Goemans-Linial conjecture in complexity theory [START_REF] Lee | l p metrics on the Heisenberg group and the Goemans-Linial conjecture[END_REF]. When p is prime, the groups H(p) are building blocks of the extra special p-groups (groups with center, commutator and derived group equal to Z/pZ). See [START_REF] Huppert | I. Die Grundlehren der Mathematischen Wissenschaften[END_REF] and [START_REF] Suzuki | Group theory. II, volume 248 of Grundlehren der Mathematischen Wissenschaften[END_REF].

The literature on random walks on the Heisenberg group is reviewed in 2.1, the connection to fast Fourier transform is treated in 2.2 the solid state connection is reviewed in 2.3, and the connection to Levy's area is given in 2.3. Section 2.5 describes two companion papers. The first generalizes to other groups; the second gives precise asymptotics for the top and bottom eigenvalues of M (ξ).

Random Walk on H(n).

The probabilistic study of a random walk on H(n) was started by Zack ([41]), who gave an interpretation of the walk in terms of random number generation. Theorem 1 was first proved in joint work with Saloff-Coste (see [START_REF] Diaconis | Moderate growth and random walk on finite groups[END_REF], [START_REF] Diaconis | An application of Harnack inequalities to random walk on nilpotent quotients[END_REF], [START_REF] Diaconis | Nash inequalities for finite Markov chains[END_REF]) using 'geometric theory.' The first proof used Nash inequalities, the second proof uses moderate growth, showing that a similar proof holds for any sequence of finite nilpotent groups with bounded class and number of generators: (diameter) 2 steps are necessary and sufficient for convergence. (The diameter of H(n) with generating set S is of order n.)

The third proof of Theorem 1 lifts to a random walk on a free nilpotent group (here H(Z)). Then results of Herbish-Saloff-Coste give bounds on the decay rate of convolution powers for the lifted walk. These are transferred down to the finite quotient using Harnack inequalities. The beautiful work of Alexopoulos ( [START_REF] Georgios | Random walks on discrete groups of polynomial volume growth[END_REF]) should allow similar results for less symmetric walks on quotients of groups with polynomial growth.

A fourth proof appears in [START_REF] Diaconis | Threads through group theory[END_REF]. This completes the generating set S to a union of conjugacy classes. Character theory is used to bound the conjugacy walk. Finally, comparison theory is used to go from the conjugacy walk to the walk based on S. Richard Stong ([37], [START_REF] Stong | Eigenvalues of random walks on groups[END_REF], [START_REF] Stong | Eigenvalues of the natural random walk on the Burnside group B(3, n)[END_REF]) has results which specialize to three yet different proofs. His approach, using 'twisted random walks' works for other classes of groups, such as the Burnside groups B(n, 3). It deserves to be developed further.

A further set of approaches/results is worth mentioning. A simple random walk on n × n uni-uppertriangular matrices with coefficients mod p has also been studied in a series of papers. In this work, the emphasis is on large n and fixed p behavior but some of the results specialize well to n = 3. We refer to the definitive paper by Peres and Sly [START_REF] Peres | Mixing of the upper triangular matrix walk[END_REF] which surveys earlier literature.

Curiously none of the papers cited above carries out the program attempted here-direct use of Fourier analysis. All we can say is, having pushed it through, we now see why.

There has also been work on a random walk on the Heisenberg group H(R). This can be developed as a special case of a random walk on Lie groups-see Breuillard [START_REF] Breuillard | Random Walks on Lie Groups[END_REF] for a useful survey. The paper [START_REF] Breuillard | Local limit theorems and equidistribution of random walks on the Heisenberg group[END_REF] focuses on H(R) and proves a local limit theorem using Fourier analysis. Of course, this is close in spirit to the present effort. Alexopoulos [START_REF] Georgios | Random walks on discrete groups of polynomial volume growth[END_REF] had remarkable decay rates for general discrete groups of polynomial growth.

A natural problem (open to our knowledge) interpolating between the finite and and infinite case would be to study the simple random walk on H(Z) with generating set S of (1). Although Breuillard allows discrete measures on H(R), he must rule out measures supported on subgroups. Indeed, as far as we know, the irreducible unitary representations of H(Z) have not been classified (and seem to give rise to a 'wild' problem).

If Q is the measure supported on S (considered on H(Z)), the associated random walk is transient. It is natural to study the decay rate of Q * k . In particular we conjecture that

Q * k (id) ∼ c k 2 with c = 4Γ 2 1 4 π 2 . ( 4
)
A justification for the conjectured constant appears in Section 2.4 below.

Notice that (4) could be studied by considering Q from (2) on H(n) for n >> k 2 (when there is no possibility of the walk wrapping around.) Indeed H(nZ) is a normal subgroup of H(Z) and all of the irreducible unitary representations of H(Z/nZ) described in 3.2 give rise to irreducible unitary representations of H(Z) via

H(Z) → H(Z)/H(nZ) = H(Z/nZ) → GL(V )
where V is the vector space underlying the representation of H(Z/nZ).

Those quotients are all of the finite dimensional simple representations of H(Z). (See [START_REF] Nunley | Simple representations of the integral Heisenberg group[END_REF].) The usual infinite dimensional irreducible unitary representations of H(R) restricted to H(Z) are also irreducible but alas there are others which do not seem to be known at this writing.

2.2.

The Discrete Fourier Connection. For f : Z/nZ → C, the discrete Fourier transform (DFT) takes f → f with

f (k) = 1 √ n n-1 ξ=0 f (ξ)e 2πiξk n .
This is a mainstay of scientific computing because of the fast algorithms (FFT). There is a close connection between the discrete Heisenberg groups H(n) and these transforms. This is charmingly exposited in Auslander and Tolimieri ( [START_REF] Auslander | Is computing with the finite Fourier transform pure or applied mathematics?[END_REF]). Let the matrix associated with the DFT be

F n , with (F n ) j,k = e 2πijk n √ n .
Recall the matrix of the Fourier transform M (1) at [START_REF] Auslander | Is computing with the finite Fourier transform pure or applied mathematics?[END_REF]. It is straightforward to see that F n commutes with M (1):

F -1 n M (1)F n = M (1)
. This implies that these Hermitian matrices can be simultaneously diagonalized. As explained in [START_REF] Dickinson | Eigenvectors and functions of the discrete Fourier transform[END_REF] and [START_REF] Mehta | Eigenvalues and eigenvectors of the finite Fourier transform[END_REF], there is engineering interest in diagonalizing F n . We are interested in diagonalizing M (1) and hoped information about F n would help.

Alas, F n 4 = id, so the eigenvalues are ±1, ±i. It is known that the associated eigenspaces have dimension (within one of) n 4 .( [START_REF] Dickinson | Eigenvectors and functions of the discrete Fourier transform[END_REF]) This does not give a useful reduction for our problem. Going the other way, Dickinson and Steiglitz [START_REF] Dickinson | Eigenvectors and functions of the discrete Fourier transform[END_REF] looked for matrices commuting with F n and suggested M (1)(!). Mehta [START_REF] Mehta | Eigenvalues and eigenvectors of the finite Fourier transform[END_REF] found a basis for eigenfunctions of F n as 'periodicized Hermite functions'. These are tantalizingly close to the approximate eigenfunctions for M (1) that we find in [START_REF] Bump | Sharp bounds on the extreme eigenvalues and vectors of matrices for Harper's operators[END_REF]. We are sure there is more to understand on this front.

Harpers Operator.

In trying to understand the band structure of the x-ray diffraction patterns of various solids (particularly metals),a variety of model problems involving Schrödinger operators with periodic potentials have been introduced and studied. Perhaps the most widely studied model is Harper's model on 2 (Z) with Hamiltonian

H θ,φ ξ(n) = ξ(n + 1) + ξ(n -1) + 2 cos(2π(nθ + φ))ξ(n), n ∈ Z, θ, φ ∈ [0, 1].
The spectrum of H θ,φ is pictured as "Hofstadter's Butterfly" with its own Wikipedia page. With 2 cos replaced by A cos, the operator is often called the almost Mathieu operator (with its own Wikipedia page). For θ irrational, the norm of H θ,φ is known not to depend on φ. Our operator M (ξ) is a discretized version of H ξ n ,0 which is often used to get numerical approximations to the spectrum. It has also been used to prove things, see the beautiful account in Section 3 of Béguin-Valette-Zuk [START_REF] Béguin | On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper's operator[END_REF]. They give bounds on the largest and smallest eigenvalues of M (ξ) which we are able to sharpen considerably in some cases.

Any periodic Schrödinger operator has band structure in its spectrum because of Bloch's Theorem [START_REF] Griffiths | Introduction to Quantum Mechanics[END_REF]. Determining the fine structure of the spectrum of H θ,ψ has generated a large literature well surveyed in [START_REF] Last | Spectral theory of Sturm-Liouville operators on infinite intervals: a review of recent developments[END_REF]. One of the signature problems here was dubbed the "Ten Martini's problem" by Barry Simon. It has recently been completely resolved by work of Last [START_REF] Last | Spectral theory of Sturm-Liouville operators on infinite intervals: a review of recent developments[END_REF], and Avila and Jitomirskaya ( [START_REF] Avila | The Ten Martini Problem[END_REF]).

There is considerable interest in a variety of similar operators, e.g. in M (ξ), replace cos 2πθj n with cos 2πθj n + cos 2πξj n . See Zhang et al [START_REF] Zhang | Are there quantum oscillations in an incommensurate charge density wave?[END_REF] and their references. We have tried to develop our bounds on the spectrum of M (ξ) (in Section 4) so that it applies to these generalizations.

2.4. Levy Area Heuristics. The random walk on H(Z) with generating set S = {(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0)} leads to interesting probability theory which gives a useful heuristic picture of the behavior on H(n) as well. This section gives the heuristics; mathematical details will appear in a later publication.

Let the successive steps of the walk be

( 1 , δ 1 , 0), ( 2 , δ 2 , 0), . . . , ( n , δ n , 0), • • • ∈ S.
By a simple direct computation, ( n , δ n , 0) . . .

( 1 , δ 1 , 0) = (X n , Y n , Z n ) with X n = 1 + . . . n , Y n = δ 1 + • • • + δ n , Z n = 2 δ 1 + 3 (δ 1 + δ 2 ) + • • • + n (δ 1 + • • • + δ n-1 ).
Thus the X n and Y n coordinates perform simple random walks on Z P ( i = 1) = P ( i = -1) = 1 4 and P ( i = 0) = 1 2 . The Local Central Limit Theorem shows

P {X n = j} ∼ e -1 2 j σ √ n 2 √ 2πσ 2 n with σ 2 = 1 2 .
The same result holds for Y n and indeed (X n , Y n ) have independent Gaussian approximations. In particular,

P {(X n , Y n ) = (0, 0)} ∼ 1 πn .
Next consider Z n . This is a martingale and a straightforward application of the martingale central limit theorem shows that

P Z n n ≤ ξ → F (ξ)
with F (ξ) the distribution function of

1 2 1 0 B 1 (s)dB 2 (s)
with B i standard Brownian motion. We note that

1 0 B 1 (t)dB 2 (t) - 1 0 B 2 (t)dB 1 (t) is
Levy's area integral, the distribution of the signed area between Brownian motion and its chord at time 1.

In turn,

1 0 B 1 (s)dB 2 (s)
can be shown to have the density

f (ξ) = 1 π 3 2 Γ 1 2 2 3 2 Γ 1 4 + iξ 2 Γ 1 4 - iξ 2 , -∞ < ξ < ∞
See Harkness and Harkness [START_REF] Harkness | Generalized hyperbolic secant distributions[END_REF] for background and details.

If Xn √ n , Yn √ n , Zn
√ n are asymptotically independent, this would suggest that

P {(X n , Y n , Z n ) = (0, 0, 0)} ∼ c n 2 , c = 4Γ 2 1 4 π 2 .
Note that Breuillard [START_REF] Breuillard | Local limit theorems and equidistribution of random walks on the Heisenberg group[END_REF] has a local limit theorem of a similar sort for a non-lattice walk on H(R) with a less well identified constant. We conjecture that this is our c. A further heuristic conclusion which this paper makes rigorous: the walk on H(Z) can be mapped to the walk on H(m) by considering the coordinates mod m. This familiar trick works, for example, for X n (mod m), showing that the simple random walk mod (m) requires order m 2 steps to get close to uniform. The same argument works for the joint distribution of (X n , Y n ). The proof for these cases requires something like the Berry-Esseen Theorem. See Diaconis [START_REF] Diaconis | Group representations in probability and statistics[END_REF] for details for X n (mod m) and [START_REF] Georgios | Random walks on discrete groups of polynomial volume growth[END_REF] for details on H(n).

The limit theorem for Zn n suggests that order m steps are necessary and sufficient. This suggest that order m 2 steps are necessary and sufficient for randomness on H(m). This is exactly what Theorem 1 proves.

This aspect of 'features' of a Markov chain getting to their stationary distribution at different rates is important in practice. A simulation is often run with just a few features of interest and the relaxation time for the whole state space may be deceptive. See [START_REF] Assaf | A rule of thumb for riffle shuffling[END_REF] for references to a handful of cases where this can be carefully proved. Generalizing, if U n (m) is the group of n × n uni-uppertriangular matrices with coefficients mod m, let a simple random walk be determined by picking one of the n -1 coordinates just above the diagonal and placing ±1 there (with the rest zero.) We conjecture that coordinates in the first diagonal require order m 2 step; in the second diagonal, order m steps; in the third diagonal, order m 2 3 steps; with order m 2/k steps for the kth diagonal. Here n is fixed, 1 ≤ k ≤ n -1 and m large are the cases of interest.

2.5. Future Developments. The present paper has two companion papers. The first [START_REF] Bump | Characters and super characters for step two nilpotent groups with applications to random walks[END_REF] abstracts the present results to a larger class of walks and groups. The second gets much more precise bounds on the extreme eigenvalues of the matrices M (ξ). Since essentially these matrices come up for the generalizations, present techniques and the refinements can be used to give satisfactory analyses of the generalizations.

Let G be a finite group with a normal abelian subgroup A and a subgroup B such that G = BA, B ∩ A = id . Thus G = B A is a semi-direct product. Let a 1 , . . . , a s be a symmetric generating set for A; b 1 , . . . , b t a symmetric generating set for B. Then {a i , b j } generate G. Consider the probability measure (with 0 < θ < 1 fixed):

Q(g) =      θ s if g ∈ {a 1 , . . . , a s } 1-θ t if g ∈ {b 1 , . . . , b t } 0 otherwise
.

The representation theory of semi-direct products is well known. See Serre Chapter 7 ( [START_REF] Serre | Linear representations of finite groups[END_REF]). The irreducible representations are determined by the representations of B and by inducing the characters of A up to

G. Let χ ∈ Â. If ρ χ (b, a) is the induced representation (a |B| × |B| matrix), Q(ρ χ ) = θP B + (1 -θ)D,
with P B the transition matrix of the B-walk (based on a uniform choice of b i ) and D a diagonal matrix with bth element

D(b, b) = 1 s s i=1 χ(b -1 a i b).
This is in sharp parallel with the present development and we have found that the techniques of the present Section 4 suffice for successful analyses. Examples from [START_REF] Bump | Characters and super characters for step two nilpotent groups with applications to random walks[END_REF] include:

• The random walk on H(n) generated by (x(i), 0, 0) and (0, y(j), 0) for (perhaps non symmetric) generating sets 1 ≤ i ≤ I, 1 ≤ j ≤ J chosen with some (perhaps non-uniform) probabilities.

• The d-dimensional Heisenberg groups G = (x , y , z), x , y ∈ (Z/nZ) d , z ∈ (Z/nZ). • The affine groups: G = (a, b), θ ∈ Z/nZ, a ∈ (Z/nZ) *
These and further examples are treated in [START_REF] Bump | Characters and super characters for step two nilpotent groups with applications to random walks[END_REF]. That paper also develops a useful supercharacter theory which allows the comparison approach [START_REF] Diaconis | Comparison theorems for reversible Markov chains[END_REF], [START_REF] Diaconis | Threads through group theory[END_REF] to be used for this class of examples. The second companion paper gives sharp bounds on the eigenvalues and eigenvectors of matrices M (ξ), for certian choices of ξ and dimension m. For ease of exposition, work with M (1). It is shown that the kth largest eigenvalue of M (1) is equal to 1 -µ k 2n + o 1 n where µ k is the kth smallest eigenvalue of the harmonic oscillator

L = - 1 2
d 2 dx 2 + 2π 2 x 2 .
on (-∞, ∞) (so µ k = (2k + 1)π), 0 ≤ k < ∞ fixed. The corresponding eigenfunctions of L are well known to be Hermite functions; with a = π,

φ 0 (x) = e -ax 2 φ 1 (x) = -4axe -ax 2 . . . φ n (x) = e ax 2 d n dx n (e -2ax 2 ) = e ax 2 d dx e -ax 2 φ n-1 (x)
It is also shown that wrapped versions of these are approximate eigenfunctions of M (1). Numerical comparisons, not reported here, show that these approximate eigenfunctions are very accurate for fixed k and large n.

The present technique gives cruder results which are all that we need and are available for all ξ.

Representation Theory

This section develops the tools needed for representation theory: Fourier inversion, the Plancherel Theorem, representations of H(n), and a formula for the distribution of central elements under convolution powers. Theorem 1 is proved when n is prime assuming the eigenvalue bounds in the following Section 4. For background, see [START_REF] Serre | Linear representations of finite groups[END_REF] and [START_REF] Diaconis | Group representations in probability and statistics[END_REF].

3.1. Basic Formulas. Let G be a finite group with Ĝ the irreducible unitary representations. For Q a probability on G and ρ ∈ Ĝ, define the Fourier Transform:

Q(ρ) = g Q(g)ρ(g).
As usual, Fourier transforms take convolution into products:

Q * Q(ρ) = ( Q(ρ)) 2 . For the uniform distribution U (g) = 1
|G| , Schur's lemma implies that Û (ρ) = 0 for all nontrivial ρ ∈ Ĝ. The Fourier Inversion Theorem shows how to reconstruct Q from Q(ρ):

Q(g) = 1 |G| ρ∈ Ĝ d ρ tr( Q(ρ)ρ(g) * ).
The basic Upper Bound Lemma ( see [START_REF] Diaconis | Threads through group theory[END_REF] page 24) gives a bound on the distance to stationary using the Fourier Transform:

4 Q * k -U 2 T V ≤ ρ∈ Ĝ ρ =1 d ρ Qk (ρ) 2 .
In these sums, d ρ is the dimension of ρ, M 2 = tr(M M * ) and ρ = 1 is the trivial representation.

Representation Theory of H(n).

A neat elementary description of the representations of H(n) appears in [START_REF] Grassberger | A note on representations of the finite Heisenberg group and sums of greatest common divisors[END_REF]. We find the following self contained derivation more useful for our application. Let q m = e 2πi/m , q n = e 2πi/n . Define ρ a,b,c (x, y, z) : V → V by ρ a,b,c (x, y, z)f (j) = q ax+by n q c(yj+z) m f (j + x).

In these formulas, regard Z/( n m Z) and Z/(mZ) as subgroups of Z/nZ by sending 1 to m (resp. n/m.) Using (x, y, z)(x y z ) = (x + x , y + y , z + z + xy ), it is easy to check that ρ a,b,c is a representation:

ρ a,b,c (x, y, z)ρ a,b,c (x , y , z )f (j) = ρ a,b,c (x, y, z)q ax +by n q c(y j+z ) m f (j + x ) = q a(x+x )+b(y+y ) n q c(y (j+x)+z +yj+z) m f (j + x + x ) = ρ a,b,c (x + x , y + y , z + z + xy )f (j).
To compute the character, note that the trace of ρ a,b,c (x, y, z) is zero unless m|x. In this case, the trace is q ax+by n q cz m m-1 j=0 q cyj m . This sum is zero unless m|y (when it is m). Thus: χ a,b,c (x, y, z) = 0 unless m|x and m|y q ax+by n q cz m m if m|x, y Distinctness and irreducibility can be determined by computing:

χ a,b,c |χ a ,b ,c = m 2 n 3 j 1 ,j 2 ,z q m(a-a )j 1 +m(b-b )j 2 n q (c-c )z m = δ abc,a b c .
In the sum, j 1 , j 2 run over 0, 1, . . . , n/m-1 and z runs over 0, 1, . . . , n-1. Since a, b can take any values in 0, 1, . . . , n m -1 and c runs over numbers relatively prime to m, this makes n m 2 φ(m) distinct irreducible characters of dimension m. Summing over divisors of n accounts for all of the characters.

Example 1. When m = 1, this gives the n 2 one dimensional characters χ a,b (x, y, z) = q ax+by n . Note that q 1 = 1 so that c doesn't occur.)

Example 2. When m = 2, set δ(x) = 1 if x is even 0 if x is odd., with δ(x) = 1 -δ(x). ρ a,b,1 (x, y, z) = q ax+by n q z m δ(x) δ(x) δ(x)q y m δ(x)q y m
Note that tr(ρ a,b,1 (x, y, z)) agrees with χ a,b,1 above.

Example 3. Consider Q(a, b, c) for Q(1, 0, 0) = Q(-1, 0, 0) = Q(0, 1, 0) = Q(0, -1, 0) = 1 4 . When m = 1, Q(a, b) = 1 2 cos 2πa n + 1 2 cos 2πb n for 0 ≤ a, b ≤ n -1. When m = 2 (so n is even) Q(a, b, 1) = 1 2 cos 2πb n cos 2πa n cos 2πa n -cos 2πb n .
In general, when m ≥ 3,

Q(a, b, c) = 1 4 q a n q -a n q -a n q -a n q a n q a n q a n q -a n                           q b n q jc m + q -b n q -jc m 0 ≤ j ≤ m -1
Note that conjugating Q(a, b, c) by a diagonal matrix with 1, q a n , q 2a n , . . . q (m-1)a n on the diagonal results in a matrix with ones on the super and subdiagonals (and q -ma n , q ma n in the two corners).

Example 4. When n is a prime p , there are p 2 one-dimensional representations and p -1 p-dimensional representations, with Q(0, 0, c) conjugate to M (c) of the introduction.

3.3. Proof of Theorem 1 when n = p is prime. From the Upper Bound Lemma stated in Section 3.1 and the formulas for Q(ρ) in Section 3.2,

4 Q * k -U 2 T V ≤ (a,b) =(0,0) 1 2 cos 2πa p + 1 2 cos 2πb p 2k + p-1 ξ=1 p M (ξ) k 2 = I + II
To understand I, first consider a = 0 and b = 1. This term is

1 2 + 1 2 cos 2π p 2k = 1 - π 2 p 2 + O 1 p 4 2k .
This term is of size e -Bη if k = ηp 2 with B = 2π 2 . A standard analysis, carried out in detail in [START_REF] Diaconis | Threads through group theory[END_REF] shows that the other terms in (I) can be similarly bounded and that the sum of these terms is at most Ce -4π 2 η for a universal constant C, independent of p and k. Consider the next sum (II ). The matrix M (ξ) is symmetric with real eigenvalues

1 > β 1 (ξ) ≥ • • • ≥ β p (ξ) > -1.
In Section 4 it is shown that for 0 < ξ < p log(p) ,

β * (ξ) = max(β 1 (ξ), -β p (ξ)) ≤ 1 - θ p 4/3
for a universal constant θ. Also, for p log(p) ≤ ξ < p 2 , it is shown that

β * (ξ) ≤ 1 - 3 4 ξ p 2 .
Furthermore note that

β * (ξ) = β * (p -ξ).
Indeed, as mentioned in Section 2.5, much sharper bounds are found. These are not relevant for this proof. Using these bounds with θ = min{θ, 3 4 },

II ≤ p 3 1 - θ p 4/3 2k + p 3 1 - θ log(p) 2k .
This is exponentially smaller than the bound for I, completing the proof of the upper bound.

A lower bound for the total variation follows from a lower bound for the total variation convergence of the (1, 2) coordinate X k to the uniform distribution on Z/pZ. As explained in Section 2.3, X k evolves as a simple random walk on Z/pZ and a lower bound showing that k = θp 2 steps is not sufficient for a fixed θ is well known. See [START_REF] Diaconis | Group representations in probability and statistics[END_REF] for several different proofs. This completes the proof.

We will not carry out the details of the proof of Theorem 1 in the case of general n. Bounds for the various transforms Q(a, b, c) are derived in Section 4. No new ideas are needed.

3.4.

A Formula for the Center. Let n = p be an odd prime. Let Z k be the value of the central element after k steps of the walk. A formula for P {Z k = z} can be derived from the Fourier Inversion Theorem. We do not see how to use this to derive useful estimates but record it here in case someone else does.

Proposition 1. For a simple random walk on H(p) with p an odd prime, all k ≥ 0, and z ∈ Z/pZ,

P {Z k = z} = 1 p + 1 p 2 p-1 ξ=1 e -2πiξz p p j=1 ( Q(ρ ξ ) k ) 1,j .
Proof. From the Fourier Inversion Theorem, for any (x, y, z)

P (X k = x, Y k = y, Z k = z) = 1 p 3 ρ∈ Ĝ d ρ Tr ( Q(ρ)) k ρ((x, y, z) -1
) . Sum over x, y and bring this sum inside the trace. The terms for the 1-dimensional representations are easily seen to vanish except of course for the trivial representation which contributes p 2 /p 3 = 1/p. For the p dimensional representations, writing ρ ξ for ρ 0,0,ξ , ρ ξ ((x, y, z) -1 ) = ρ ξ (-x, -y, -z + xy). In the basis of Section 2.3

ρ ξ (-x, -y, -z + xy)f (j) = e 2πiξ p (-yj-z+xy) f (j -x).
Fixing x and summing over y, y e -2πiξ p (j-x)y = pδ(j, x). Then,

y ρ ξ (-x, -y, -z + xy)f (j) = pe -2πiξz p f (0).

Summing over x gives

x,y

ρ ξ (-x, -y, -z + xy) = pe -2πiξz p   1 0 . . . 0 . . . . . . . . . 1 0 . . . 0   .
Multiplying by Q(ρ ξ ) k and taking the trace gives the result.

Remark. Of course, the elements in the first row of Qk (ρ ξ ) tend to zero, but it does not seem simple to get quantitative bounds.

Eigenvalue Bounds

This section gives upper and lower bounds for the eigenvalues of the matrices M (ξ) of (3). Recall that these are n × n, with 1 4 in the upper right and lower left corners and 1 2 cos( 2πξj n ) for 0 ≤ j ≤ n -1 on the main diagonal. These matrices have some symmetry properties, noted in Section 4.1, which simplifies the job. Section 4.2 gives upper bounds for the largest eigenvalue of the form 1 -θ ξ n 4 3 for θ an absolute positive constant and ξ << n. The argument makes novel use of bounds for Dirichlet eigenvalues using geometric path techniques. It is useful for more general diagonal entries and less structured matrices. A different variant bounds the largest eigenvalues for larger ξ. Section 4.3 gives lower bounds for the smallest eigenvalues. These use quite different ideas: Comparisons with matrices constructed to have 'nice' eigenvalues.

The following series of figures shows numerical examples. Figure 1 shows the top eigenvalues β 1 (ξ) of M (ξ) when n = 150. As ξ varies from 1, 2, . . . for small ξ, the top eigenvalues are close to 1 and fall off as ξ increases but they are not monotone. The evident symmetry β 1 (c) = β 1 (n -c) is proved in Section 4.1. Figure 2 shows the smallest eigenvalues of M (ξ). While these appear as a mirror image of Figure 1, a closer look at the numbers shows this is only an approximation and the same proof method does not work. Figure 3 shows all of the eigenvalues of M(1) for n = 150. 4.1. Symmetries and Inclusions. While many of the properties proved in this section are quite robust, the following more special properties are needed. For positive integers n, ξ and any real α, let D n,ξ,α denote the n × n diagonal matrix with diagonal entries:

D (j) n,ξ,α = cos 2πξ n (α + j) 0 ≤ j ≤ n -1.
Let M n,ξ,α = 1 2 (D n,ξ,α +P)) where P is the transition matrix of a simple random walk on Z/nZ ( 1 2 on the diagonals just above and below the main diagonal and 1 2 in the upper right and lower left corners.) Thus M n,ξ,0 = M (ξ). Let S(n, ξ, α) be the spectrum of M n,ξ,α . The highest eigenvalue of M(ξ) when n =150 The lowest eigenvalue of M(ξ) when n =150 Thus M (n, ξ, 0) = M (n, n -ξ, 0). For (b), if φ is an eigenvector of M n,ξ,α then juxtaposing it k times gives an eigenvector of M kn,kξ,α with the same eigenvalue because of periodicity. For (c), suppose ψ is an The eigenvalues of M(1) when n =150 eigenvector of M n,ξ,α with associated eigenvalue θ. Thus:

1 4 (ψ(j + 1) + ψ(j -1)) + 1/2 cos 2πξ n (α + j) ψ(j) = θψ(j)
Set φ(j) = (-1) j ψ(j). Then Remark. The operator with 1s above and below the diagonal (and in the corners) and V cos( 2πξ n (j + α)) with V > 0 a constant is a discrete version of the "almost Mathieu operator" of solid state physics. See [START_REF] Zhang | Are there quantum oscillations in an incommensurate charge density wave?[END_REF]. The discrete operator corresponds to 4M (n, ξ, α) when V = 2. This is well known to be the critical case in the theory. The ξ's of physical interest scale as O(n), which corresponds to the case when Z n is replaced by Z. When V > 2 the eigenfunctions are localized. For V < 2, they are spread out. The spectrum when V = 2 is called "Hofstadter's Butterfly." Its spectral properties have recently been observed in graphene [START_REF] La Ponomarenko | Cloning of Dirac fermions in graphene superlattices[END_REF]. All our ξ n ratios are rational. It is a fascinating question if the limit as ξ n tends to an irrational has limiting spectrum matching the spectrum of Harper's operator on 2 . See [START_REF] Zhang | Are there quantum oscillations in an incommensurate charge density wave?[END_REF] for further discussion.

4.2. Dirichlet Path Arguments. For general n, M (ξ) = Q(0, 0, ξ) is an n × n matrix with 1 2 cos 2πξj n on the main diagonal, 1 4 on the super and subdiagonals and in the upper right and lower left corners. Then 1 2 I + M (ξ) has non-negative entries with row sums in [ 1 2 , 3 2 ]. Finally, L ξ = 1 3 I + 2 3 M (ξ) is a substochastic matrix with 1 6 on the super and subdiagonals (and the corners) and 1 3 1 + cos 2πξj n on the main diagonal for 0 ≤ j ≤ n -1. The row sums are between 1 3 and 1. Form an (n + 1) × (n + 1) stochastic matrix K ξ by adding an absorbing state ∞, with transitions from j to ∞,

K ξ (j, ∞) = 1 3 1 -cos 2πξj n . Set K(∞, ∞) = 1.
Bounds on the eigenvalues of L ξ (and so M (ξ)) give bounds on the Dirichlet eigenvalues of K ξ . Use the notation of [START_REF] Diaconis | On Quantitative Convergence to Quasi-Stationarity[END_REF] Section 4.2 with S = {0, 1, . . . , n -1}, S = S ∪ {∞}. The Markov chain K ξ restricted to S is connected. Let U

(j) = 1/n, 0 ≤ j ≤ n -1 with 2 (U ) = {f : {0, 1, . . . , n -1} → R} having inner product f |g U = j∈S f (j)g(j)U (j).
As required, for all x, y ∈ S, U (x)K ξ (x, y) = U (y)K ξ (y, x). When needed, functions f on S are extended to S as f (∞) = 0. (Also set U (∞) = 0.) Define a Dirichlet form E on 2 (U ) by

E(f |f ) = 1 2 x,y∈S (f (x) -f (y)) 2 U (x)K ξ (x, y). Let β = β(ξ) be the largest eigenvalue of L ξ . From [12] Lemma 19, if there is a constant A > 0 such that f 2 U ≤ A E(f ) , for all f ∈ 2 (U ), then β ≤ 1 -1
A . This shows that the largest eigenvalue of M (ξ) is at most 1 -3 2A . Geometric arguments require a choice of paths γ x starting at x ∈ S to ∞, with steps which are possible with respect to K ξ . Thus γ

x = (x 0 = x, x 1 , x 2 , . . . , x d = ∞) with K ξ (x i , x i+1 ) > 0 for 0 ≤ i ≤ d -1. Let d = |γ x | denote the length of this path. From [12] Proposition 2c, β ≤ 1 - 1 A with A = max x∈S,y∈S 2 K ξ (x, y) z∈S, (x,y)∈γz |γ z |. (5)
The bounds are better if A is 'small.' From [START_REF] Béguin | On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper's operator[END_REF] this happens if both the paths are chosen so that no edge occurs too often and the (x, y) edges that appear don't have small value of K ξ (x, y). With these preliminaries we next prove:

1 2 x * l x * l + 1 ∞ Figure 5
. The chosen path from 1 to ∞ is given with solid lines, while the chosen path from 2 to ∞ is pictured with dashed lines.

infinity by horizontal paths r, r + 1, . . . , (r + x * l + 1) going directly from there to ∞. See Figure 5.

Do the symmetric thing with the rightmost x * -1 points at the right of group 1, (moving leftward.) Connect points from x * l to x * u directly to ∞ with paths of length 1. Treat each of the other groups in a parallel fashion.

Bounds for A in (5) follow from bounds from the edges in Group 1. For the edge (r -1, r), order x * paths use this edge and each such path has length x * . Since

2 K ξ (r-1,r) ≤ 2 K ξ (x * l -1,x * l ) = 12
, the contribution from this edge is at most of order (x * ) 2 . Next consider edges (j, ∞) with j between x * l and 2x * l or between x * u -x * and x * u . At most two paths use such an edge, one of length x * (and the other of length one.) The contribution here is of order n ξx * 2 x * . The exponent 2 3 in our choices of x * was chosen to make (x * ) 2 and n ξ 2 1

x * of the same order. The only other edges used are (j, ∞) with j from 2x * l to 2x * u . These are used once for paths of length 1 and 1 K(j,∞) is at most of order n ξ 2/3 . Combining bounds completes the proof of Proposition 3.

Proof of Proposition 4. Proceeding as above, break 0 ≤ j ≤ n -1 into groups of n ξ points (within 1). Again, the groups are treated identically and we focus on the first group. Let x * l = 1 4 n ξ and connect points of 0 ≤ j < x * l to points x * l +j and then to ∞. Since cos 2π n ξ(x * l + j) ≤ 0, 2 K ξ (x * l +j,∞) ≤ 6. For x * l to x * u , connect points directly to ∞. For j at the right of group 1, connect backward to x * u -j and then to ∞ in symmetric fashion. Now, 2 K(j,∞) ≤ 6. For all x * l ≤ j ≤ x * u that occur in this choice of paths, these edges (from j to ∞) have at most 3 paths through them, the longest path of length of order n 4ξ . This gives 5 n ξ as an upper bound for those edges. For edges (j, j + 1), 2 K(j,j+1) = 12. The maximizing such edge is (x * l -1, x * l ). This has x * l paths using it of

4.3.

Lower bounds on Negative Eigenvalues. We derive crude but useful lower bounds on the negative eigenvalues of M (ξ) by using the upper bounds from Section 4.2 together with the inclusion from Proposition 2. Suppose that n is odd (the case of interest for proving Theorem 1). From Proposition 2 (d), the following spectral inclusion holds:

S(n, ξ, 0) ⊆ -S(2n, 2ξ, n 2ξ ).

Thus bounds on the smallest eigenvalues of M (ξ) follow from bounds on the largest eigenvalues of 2n×2n matrices with diagonal cos 2πξj n + π , 0 ≤ j ≤ 2n -1. First consider the case of ξ = 1, the diagonal elements appear as in Figure 6. A cyclic shift of the diagonal doesn't change the spectrum so we may consider the 2n × 2n matrix with diagonal entries cos π(2j+1) n , 0 ≤ j < 2n -1, as in Figure 7. Now, the same paths and bounds used in Section 4.2 can be used to get upper bounds. We will not repeat the details but merely state the conclusions. Remark. The case of even n arises naturally as well. This may be treated in parallel fashion using Proposition 2 (c) to reduce things to bound the largest eigenvalues of slightly shifted matrices as above.

m 2 φ

 2 For every divisor m of n, 1 ≤ m ≤ n , there are n m 2 φ(m) distinct irreducible representations of degree m, where φ(m) is the Euler phi function. Since m|n n (m)m 2 = n 3 , this is a complete set. For the construction, fix m|n. Let V = {f : Z/mZ → C} . Now fix a, b ∈ Z/( n m Z) and c ∈ Z/mZ with (c, m) = 1.

Proposition 2 .

 2 (a) S(n, ξ, 0) = S(n, n -ξ, 0) (b) For all positive integer k, S(n, ξ, α) ⊆ S(kn, kξ, α)

Figure 1 .

 1 Figure 1. The top eigenvalues of M (ξ)

Figure 2 .Proof

 2 Figure 2. The lowest eigenvalues of M (ξ)

Figure 3 .

 3 Figure 3. All the eigenvalues of M (1)

  j) φ(j) = -θψ(j) but -cos( 2πξ n (α + j) = cos 2πξ n (α + j + n 2ξ . For (d), properties (b) and (c) imply that S(n, ξ, α) ⊆ S(2n, 2ξ, α) = -S 2n, 2ξ, α + n 2ξ .

Figure 6 . 4 n ξ 2 .

 642 Figure 6. Diagonal elements for ξ = 1

Proposition 5 .Figure 7 . 1 Proposition 6 .

 5716 Figure 7. A shift of the diagonal elements for ξ = 1

Proposition 3. There exists a positive constant θ such that for all n and 1 ≤ ξ ≤ n log n , the largest eigenvalue

. Break the ξ cycles of cos 2πξj n at n ξ , 2 n ξ , . . . into ξ groups, eg. when ξ = 3 breaking ties to the right. See Figure 4. Each group has n ξ + O(1) points. For each group, define a point x * l by counting x * points from the left and x * u by counting x * from the right of the groups. Each group is treated identically and we here focus on the first group. From the development above, for any j between x * l and 2x * l ,

(1 + o(1)) for an explicit constant θ, independent of ξ, j, n. For points r between 1 and x * l -1, connect r to