ON RANDOM WALKS IN LARGE COMPACT LIE GROUPS 5 1 JEANBOURGAIN 0 2 y a M 1. Introduction 5 In order to put the problem considered in this Note in perspective, we 1 first recall some other relatively recent results around spectral gaps and ] generation in Lie groups. R P It was shown in [B-G1] (resp. [B-G2]) that if Λ is a symmetric finite h. subset of SU(2) resp. SU(d) consisting of algebraic elements, such that at thecountablegro(cid:0)upΓ = Λ ge(cid:1)neratedbyΛisdense,thenthecorresponding h i m averaging operators [ 1 Tf = f g (1.1) 2 Λ ◦ X v | | g∈Λ 7 acting on L2(G), has a uniform spectral gap (only depending on Λ). This 9 5 result was generalized in [dS B] to simple compact Lie groups. 1 − 0 It is not known if the assumption for Λ to be algebraic is needed, and . 1 one may conjecture that it is not. Short of providing uniform spectral gaps, 0 Varju[V]establishedthefollowingpropertywhichisthemostrelevantstate- 5 1 ment for what follows. : v i Proposition 1. Let G be a compact Lie group with semisimple connected X component. Let µ be a probability measure on G such that supp(µ˜ µ), µ˜ r ∗ a defined by f(x)dµ˜(x) = f(x−1)dµ(x), generates a dense subgroup of G. Then thereRis a constant cR> 0 depending only on µ such that the following holds. Let ϕ Lip(G), ϕ = 1 and ϕ= 0. Then ∈ k k2 G R ϕ(h−1g)dµ(h) < 1 c log−A(1+ ϕ ) (1.2) (cid:13)Z (cid:13)2 − k kLip (cid:13) (cid:13) (cid:13) (cid:13) with A depending on G. Date:May18,2015. ThisworkwaspartiallysupportedbyNSFgrantsDMS-1301619. 1 2 JEANBOURGAIN Using (1.2) and decomposition of the regular representation of G in irre- ducibles (though this may be avoided), one deduces easily from (1.2) that it takes time at most O(logA 1) as ε 0 for the random walk governed by ε → µ to produce an ε-approximation of uniform measure on G. Note that for G = SU(d), this statement corresponds to the Solovay-Kitaev estimates on generation, cf. [D-N], which in fact turns out to be equivalent. Let us focus on G = SO(d) or SU(d). While the exponent A in (1.2) is a constant, the prefactor c depends on µ, hence on G, and seems to have received little attention. Basically our aim is to prove a lower bound on c which is powerlike in 1 and without the need for uniform spectral d gaps (which may not be always available). We focus on the following model problembroughttotheauthor’sattentionbyT.Spencer(whowasmotivated by issues in random matrix theory that will not be pursued here). The general setting is as follows (we consider the SU(d)-version). Fix some probability measure η on SU(2) such that its support generates a dense group, i.e. supp η = SU(2). This measure η may be Haar but could be h i taken discrete as well. Identify 0,1,...,d 1 with the cyclic group Z/dZ { − } anddenote ν themeasureη on SU(2) acting on thespace [e ,e ]. Consider ij i j the random walk on SU(d) given by d−1 1 Tf(x)= f(gx)ν (dg). (1.3) d Z i,i+1 X i=0 Howlongdoesittakeforthisrandomwalktobecomeanε-approximation of uniform measure on G, with special emphasis on large d? Thus this is a particular instance of the more general issue formulated in the title. While we are unable to address the broader problem, specific cases such as (1.3) may be analyzed in a satisfactory way (based partly on arguments that are also relevant to the general setting). We prove Proposition 2. In the above setting, ε-approximation of the uniform mea- sure is achieved in time C(dlog 1)C, with C a constant independent of d. ε Comment IfηistakentobeauniformmeasureonSU(2),betterresultsareavailable, exploiting Hurwitz’construction of Haar measure(see [D-SC], section 2). In this situation, the operator T displays in fact a uniform spectral gap and ON RANDOM WALKS IN LARGE COMPACT LIE GROUPS 3 the power of log 1 can be taken to be one (cf. [D-SC], Theorem 1). Our ε interest in this presentation is a more robust approach however. Basically, one could expect a more general phenomenon (though some additional assumptions are clearly needed). In some sense, it would give a continuous version of the conjecture of Babai and Seress [B-S] predict- ing poly-logarithmic diameter for the family of non-Abelian finite simple groups (independently of the choice of generators). Important progress in this direction for the symmetric group appears in [H-S]. Independently of Spencer’s question, related spectral gap and mixing time issues for specific random walks in large (not necessarily compact) linear groups appear in the theory of Anderson localization for ‘quasi-one- dimensional’ methods in Math Phys. Consider the strip Z Z/dZ and a random Schro¨dinger operator ∆+λV × with ∆ the usual lattice Laplacian on Z Z/dZ, V a random potential and × λ > 0 the disorder. This model is wellknown to exhibit purepoint spectrum with so-called Anderson localization for the eigenfunctions. The issue here is how the localization length (or equivalently, the Lyapounov exponents in the transfer matrix approach) depend on d when d . → ∞ The classical approach based on Furstenberg’s random matrix product theory (acting on extension powers of Rd), cf. [B-L], is not quantitative and sheds no light on the role of d. In fact, the first explicit lower bound on Lyapounov exponents seems to appear in [B] (using different techniques based on Green’s function analysis), with, roughly speaking exponential dependence on d (while the ‘true’ behaviour is believed to be rather of the form d−C). Clearly understanding the mixing time for the random walk in the symplectic group Sp(2d) associated to the transfer matrix is crucial. Note that this group is non-compact, which is an added difficulty (for very small λ, depending on d, [B-S] provides the precise asymptotic of theexponents,basedonamulti-dimensionalextensionoftheFigotin-Pastur approach). 2. Some preliminary comments The proof of Proposition 1 in [V] exploits the close relation between ‘gen- eration’ and ‘restricted spectral gaps’. This point of view is also the key idea here in establishing 4 JEANBOURGAIN Proposition 1′ Let T be defined by (1.3). Then there is the following estimate Tf < 1 (cd)−C log(1+ f )−A (2.1) 2 Lip k k − k k (cid:0) (cid:1) for f Lip(G). f = 1, f = 0. ∈ k k2 G R HereC andAareconstants (denoteddifferently, becauseoftheirdifferent appearance in the argument). Unlike in [V], we tried to avoid the use of representation theory. The reason for this is the following. If one relies on decomposition of the reg- ular representation of G in irreducibles and the Peter-Weyl theorem, one is faced in the absence of a uniform spectral gap with convergence issues of the generalized Fourier expansion of functions on G of given regularity. Conversely, we also need to understand the regularity of matrix coefficients of the representations of increasing dimension. While these are classical is- sues, understanding the role of the dimension d does not seem to have been addressed explicitly. 3. Proof of proposition 1′ For simplicity, we take η to be a uniform measure on SU(2) and indicate the required modifications for the general case in 5. § According to (1.3), denote d−1 1 ν = ν (3.1) i,i+1 d X i=0 Thus ν = ν˜ and T is the corresponding averaging operator. Let f Lip(G), f = 1 and f = 0. Assuming ∈ k k2 G R 2 τ fν(dg) = Tf 2 > 1 ε (3.2) (cid:13)Z g (cid:13)2 k k2 − (cid:13) (cid:13) (cid:13) (cid:13) (denoting τ f(x)= f(gx) our aim is to obtain a lower bound on ε. g (cid:1) Clearly (3.2) implies that f, τ f(ν ν)(dg) > 1 ε g D Z ∗ E − and f τ f 2(ν ν)(dg) < 2ε. (3.3) Z k − g k2 ∗ ON RANDOM WALKS IN LARGE COMPACT LIE GROUPS 5 Fix ε > 0 to be specified later and denote B an ε -neighborhood (for 1 ε1 1 the operator norm) of Id in SU(d). It is clear from (3.1) that ν(B ) & ε4 ε1 1 and hence (3.3) implies Z kf −τg′gfk22ν(dg) . ε−14ε (3.4) for some g′ B . Next, partitioning SU(2) in ε -cells Ω and denoting ∈ ε1 1 α Ω = g SU(d);g(e ) = e for j i,i+1 and g Ω α,i { ∈ j j 6∈ { } |[ei,ei+1] ∈ α} observe that ν(Ω ) 1ε4 so that by (3.4) α,i ≥ d 1 Z(cid:30) kf −τg′gfk22ν(dg) . dε−18ε ≪ 1. (3.5) Ωα,i Exploiting (3.5), it is clear that we may introduce a collection SU(d) G ⊂ with the following properties f τ f . √dε−4√ε for g . (3.6) k − g k2 1 ∈ G and Given an element γ SU(2) and 1 i < j d, denote γ in SU(d) the ij ∈ ≤ ≤ element defined by γ (e ) = e for k i,j ij k k  6∈ { } (3.7)  γ = γ. ij [ei,ej] (cid:12)  (cid:12) Then, for each γ SU(2) and 1 i d, there is g s.t. ∈ ≤ ≤ ∈ G g γ < ε . (3.8) i,i+1 2 1 k − k At this point, we will invoke generation. Since f = 0, G R f τ f 2dg = 2 Z k − g k2 SU(d) and we take some h SU(d) s.t. 0 ∈ f τ f √2. k − h0 k2 ≥ If h h < δ 1 , then k 0− 1k ∼ kfkLip 1 1 kτh0f −τh1fk2 ≤ (kfkLipδ)2 < 2 and consequently f τ f > 1 if h h < δ. (3.9) k − h1 k2 k 0− 1k 6 JEANBOURGAIN Inordertogetacontradiction,weneedtoproduceawordh = g g ;g ,...,g 1 1 ℓ 1 ℓ ··· ∈ such that G h g g < δ (3.10) 0 1 ℓ k − ··· k and ε4 ℓ < 1 . (3.11) √ε√d Indeed, (3.6) implies then that f τ f f τ f + + f τ f < 1. k − h1 k2 ≤ k − g1 k2 ··· k − gℓ k2 For 1 i < d, let σ Sym(d) be the transposition of i and i+1. i,i+1 ≤ ∈ Denote σ˜ the corresponding unitary operator. Since i,i+1 σ ;i = 1,...,d 1 i,i+1 { − } is a generating set for Sym(d) consisting of cycles of bounded length, it followsfromaresultin[D-F]thatthecorrespondingCayleygraphonSym(d) has diameter at most Cd2. In particular, given i,j Z/dZ,i = j,σ˜ may i,j 6∈ 6 be realized as a composition of a string of elements σ˜ of length at most i,i+1 Cd2. In view of (3.7), this implies that if γ SU(2) and 1 i < j d, ∈ ≤ ≤ then γ g < cd2ε (3.12) ij 1 k − k for some g ,ℓ < cd2 ( = words of size ℓ written in g). ∈ Gℓ1 1 Gℓ Let κ > 0, κ2 > cd2ε . (3.13) 1 Adopting the Lie-algebra point of view, the preceding implies that given s,t R, s , t < 1 and z C, z < 1, then ∈ | | | | ∈ | | dist Id+κ is(e e )+it(e e )+z(e e )+z¯(e e ) , < κ2 (3.14) i⊗ i j⊗ j i⊗ j j⊗ i Gℓ1 (cid:0) (cid:0) (cid:1) (cid:1) and therefore dist(I +κA, ) < d2κ2 (3.15) Gd2ℓ1 for skew symmetric A, A 2π. k k ≤ Let h SU(d),h = eA with A as above. Taking κ = 1, we have ∈ r eA = (e1rA)r = 1+ 1A r +O 1 (cid:16) r (cid:17) (cid:16)r(cid:17) and therefore, by (3.15) d2 dist(h , ) rd2κ2 = . (3.16) 0 Grd2ℓ1 ≤ r ON RANDOM WALKS IN LARGE COMPACT LIE GROUPS 7 Taking κ= 1 = d−C and ε = d−2C−2, (3.16) ensure that r 1 dist(h, c ) < d−C for all h SU(d). (3.17) d 1 G ∈ Next, we rely on the Solovay-Kitaev commutator technique to produce approximations at smaller scale. This procedure is in fact dimensional free (see the comment in [D-N] following Lemma 2 in order to eliminate a poly- nomial prefactor in d - which actually would be harmless if we start from scales ε = d−C). The conclusion is that 0 dist(h, )< τ for all h SU(d) ℓ G ∈ may be achieved with 1 A ℓ < dC1 log . (cid:16) τ(cid:17) Returning to (3.10), (3.11), we obtain the condition ε4 dC0logA(1+ f Lip) < 1 = d−C2ε−12 (3.19) k k √ε√d and Proposition 1′ follows. 4. Proof of Proposition 2 The disadvantage of our approach is that T is not restricted to finite dimensional invariant subspaces of L2(G) so that strictly speaking, one can not rely on a spectral gap argument to control the norm of iterates of T. But Proposition 1′ nevertheless permit to derive easily the following Proposition 3. Assume f Lip(G), f = 1, f = 0. Let 0 < ρ < 1. ∈ k k2 G 2 Then R Tℓf < ρ (4.1) 2 k k provided 1 A+1 ℓ > cdC.logA(1+ f ). log . (4.2) Lip k k (cid:16) ρ(cid:17) Proof. Let B = f . Clearly Tℓf B also. Lip Lip k k k k ≤ Fix some ℓ and let f = Tℓf . Hence f B . 1 kTℓfk2 k 1kLip ≤ kTℓfk2 Applying Proposition 1′, it follows that Tℓ+1f Tℓf (1 ε ) 2 2 ℓ k k ≤ k k − 8 JEANBOURGAIN with B −A 1 −A ε = cd−C log 1+ > cd−C log(1+B) −A log 1+ . ℓ (cid:16) (cid:16) kTℓfk2(cid:17)(cid:17) (cid:0) (cid:1) (cid:16) (cid:16) kTℓfk2(cid:17)(cid:17) Hence, assuming Tℓf > ρ, we obtain 2 k k ρ < (1 cd−C log(1+B) −A log 1 −A ℓ − (cid:16) ρ(cid:17) (cid:17) (cid:0) (cid:1) implying (4.2). (cid:3) Proof of Proposition 2. Apply Proposition 3 with logB log 1 and log 1 d2log 1. ∼ ε ρ ∼ ε 5. Variants Thepreviousargumentisclearlyveryflexibleandmaybeappliedinother situations. Returningto 3, assumemoregenerally η aprobabilitymeasureonSU(2) § satisfying supp η = SU(2). Note that by Proposition 1, η(ℓ) with ℓ h i ∼ (log 1 )c (logd)c providesanε -approximationofHaarmeasureonSU(2). ε1 ∼ 1 It follows from (1.3), (3.3) that f τ f 2(ν ν )(dg) < 2d2ε Z k − g k2 i,i+1∗ i,i+1 and hence f τ f 2ν(ℓ) (dg) < ℓd2ε Z k − g k2 i,i+1 (cid:30) f τ f 2 ν(ℓ) (dg) .ℓd2ε−4ε. Z k − g k2 i,i+1 1 Ωa,i The collection may then be introduced similarly. Proposition 2 remains G valid. Let us point out that it is unknown if in general the density assumption supp η = SU(2) implies a uniform spectral gap (see the discussion on 1). h i § Instead of (1.3), one may introduce at time k = Z the discrete average + T = 1(τ +τ ) where we first pick some i Z/dZ and then choose a k 2 g g−1 ··· ∈ random element g SU(2) acting on [e ,e ] according to η. In this situa- i i+1 ∈ tion,oneobtainsrandomwalksonSU(d)indexedbyanadditionalprobabil- ity space Z/dZ SU(2) ⊗ ⊗ (cid:0) (cid:1) Tω = T T T (5.1) k k−1 1 ··· ··· and may ask for the typical mixing time of a realization. ON RANDOM WALKS IN LARGE COMPACT LIE GROUPS 9 Rather straightforward adjustments of the arguments appearing in the proof of Proposition 1′ combined with some Markovian considerations per- mit us to establish the analogue of Proposition 2 for Tω. Thus Proposition 4. Let Tω be defined by (5.1). Then, with large probability in ω, ε-approximation of uniform measure on SU(d) may be achieved in time C(dlog 1)C. ε Acknowledgement. The author is grateful to P. Varju for his comments and also for pointing out various references. P.VarjualsoreportedthefollowingsomewhatrelatedquestionofA.Lubotzky: Does SU(d) admit a finite set of generators with a spectral gap that is uni- form in d? References [B] J. Bourgain, A lower bound for the Lyapounov exponents of the random Schro¨dinger operator on a strip,J.Stat.Phys.153(2013), no1,1–9. [B-G1] J.Bourgain,A.Gamburd,OnthespectralgapforfinitelygeneratedsubgroupsofSU(2), Inventiones MathA1(2008), 201,83–121. [B-G2] J. Bourgain, A. Gamburd, A spectral gap theorem in SU(d), JEMS 14 (2012), no5, 1455–1511. [B-L] A. Bougerol. J. Lacroix, Product of random matrices with applications to Schr¨odinger operators, Birkh¨auser(1985). [B-S] L. Babai, A. Seress: On the diameter of permutation groups, European J. Combin. 13 (1992), 231–243. [D-N] C. Dawson, M Nielsen, The Solovay-Kitaev algorithm, Quantum Inf. & Comp., Vol. 6, No1(2006) 81–95. [D-SC] P.Diaconis,L.Saloff-Coste,BoundsontheKac’sMasterEquation,CMP,209(3): 729– 755(2000). [D-F] J. Driscoll, M. Furst, Computing short generator sequences, Inf. and Comp., Vol. 72, 1987,117–132. [dS-B] Y.Benoist,N.deSaxc´e: Aspectral gaptheoreminsimple Liegroups,arXiv.1405.1808. [H-S] H. Helfgott, A. Seress, On the diameter of permutation groups, Annals Math. (2) 179 (2014), no2,611–658. [S-B] H. Schulz-Baldes, Perturbation theory for the Lyapounov exponents of an Anderson model on a strip,GAFA14,1029-1117 (2004). [V] P.Varju,Random walks in compact groups, Doc.Math.18(2013), 1137–1175. (J.Bourgain)Institute forAdvancedStudy,Princeton, NJ 08540 E-mail address: [email protected]