Quantum reflections, random walks and cut-off
Amaury Freslon



We study the cut-off phenomenon for random walks on free unitary quantum groups coming from quantum conjugacy classes of classical reflections. We obtain in particular a quantum analogue of the result of U. Porod concerning certain mixtures of reflections. We also study random walks on quantum reflection groups and more generally on free wreath products of finite groups by quantum permutation groups.


  
Tuning transport properties on graphene multi-terminal structures by mechanical deformations
    A. Latgé
    December 30, 2023
===============================================================================================





§ INTRODUCTION


Recently, J.P. McCarthy initiated in <cit.> the study of the cut-off phenomenon for random walks on compact quantum groups, focusing on the finite case. This led us to adress examples in the compact (infinite) case in <cit.>, where we were able to prove a cut-off for several examples inspired by classical random walks on orthogonal and symmetric groups. These examples include a quantum analogue of the uniform plane Kac walk on free orthogonal quantum groups as well as the uniform random walk on the set of quantum transpositions in free symmetric quantum groups. In the present paper, we continue this work by considering other compact quantum groups in connection with complex reflections.

Our first family of examples is free unitary quantum groups. In the classical case, the unitary group can be thought of as a complex version of the orthogonal group. The same analogy works in the quantum setting in a precise sense : the free unitary quantum group is the free complexification of the free orthogonal quantum group. This gives us a convenient way of producing central states (i.e. conjugation-invariant measures) on this quantum group using the free product construction. We analyse the behaviour of the associated random walk when the state is the uniform measure on the conjugacy class of a classical complex reflection. We then consider a "mixture" of these measures which was studied in the classical case by U. Porod in <cit.> and prove a cut-off with the same parameter, namely Nln(N)/2.

In <cit.>, we were not able to prove a cut-off for arbitrary mixtures of rotations because could not handle the behaviour of our approximations when the angle was close to 0. We therefore had to assume that the measure governing the mixture had a support bounded away from 0. Here, since we consider a specific measure, we can do explicit computations even though the support is not bounded away from 0 and directly prove the cut-off without reducing the problem to individual conjugacy classes of reflections.

Our second family of examples comes from reflection groups. More precisely, J. Bichon introduced in <cit.> a quantum version of the wreath product construction called the free wreath product of the dual of a discrete group Γ by the free symmetric quantum group S_N^+. When Γ = _s is cyclic, this object coincides with a quantum analogue of the complex reflection group H_N^s introduced by T. Banica and R. Vergnioux in <cit.>. It turns out that assuming Γ to be cyclic does not simplify the arguments of the proof of the cut-off phenomenon, so that we will consider in full generality the free wreath product of the dual of a finite group by S_N^+. Two problems arise in this context. First, constructing states on these compact quantum groups is not straightforward. It can nevertheless be done using a quantum group tool called monoidal equivalence and some earlier results on approximation properties for quantum SU(2) groups. Second, the computations are more involved than in the previous examples and we have to make an assumption on the state considered (more precisely on the parameter τ defining the state) so that we do not get a cut-off statement for all pure central states.

Let us conclude by an outline of the paper. Section <ref> contains some notations and essential results from <cit.>. In Section <ref> we introduce free unitary quantum groups and prove several cut-off statements. In particular, we obtain in Theorem <ref> a cut-off at Nln(N)/2 for a particular mixture of random reflections in perfect analogy with the classical result. In Section <ref> we turn to free wreath products and prove in Theorem <ref> a cut-off for pure central states satisfying a simple condition on the parameter τ defining the state.



§ PRELIMINARIES


We first briefly recall some facts concerning random walks on compact quantum groups, mainly to fix notations. The reader may refer to <cit.> for details and proofs. A compact quantum group  is given by a Hopf *-algebra Ø() together with an invariant state h, i.e. a positive linear map Ø()→ satisfying h(1) = 1 and

    (h⊗𝕀)∘(x) = h(x).1 = (𝕀⊗ h)∘(x)

for all x∈Ø(), where : Ø()→Ø()⊗Ø() is the coproduct. The state h is called the Haar state of . A unitary representation of dimension n of  is a unitary element u∈ M_n(Ø()) such that for all 1⩽ i, j⩽ n,

    (u_ij) = ∑_k=1^nu_ik⊗ u_kj.

A morphism between representations u and v of dimension n and m respectively is a linear map T : ^n→^m such that (T⊗𝕀)u = v(T⊗𝕀). Two representations are said to be equivalent if there is a bijective morphism between them. A representation u is said to be irreducible if the only morphisms between u and itself are the scalar multiples of the identity. A quantum analogue of the Peter-Weyl theory ensures that any unitary representation splits as a direct sum of irreducible finite-dimensional ones, so that the latter are enough to describe the representation theory. Denoting by () the set of equivalence classes of irreducible representations, we define for α∈() the corresponding character χ_α as

    χ_α = (u^α) = ∑_i=1^(u^α)u^α_ii

for any representative u^α of α.

In the present work, we are interested in the sequence (φ^∗ k)_k∈ of convolution powers of a state φ on the Hopf *-algebra Ø() of a compact quantum group , which is recursively defined by φ^∗ 1 = φ and

    φ^∗(k+1) = (φ^∗ k⊗φ)∘ = (φ⊗φ^∗ k)∘.

We will estimate how far states are from the Haar state with respect to the total variation distance. To define it requires the introduction of some topology. The state h induces a scalar product on Ø() through the formula ⟨ x, y⟩_h = h(xy^*) which, after separation and completion, yields a Hilbert space L^2(). The action by left multiplication induces an embedding Ø()↪ B(L^2()) yielding a norm  on Ø() denoted by ·_∞. The weak closure of Ø() is then a von Neumann algebra denoted by L^∞().


The total variation distance between two states φ and ψ on the von Neumann algebra L^∞() of  is defined by

    φ - ψ_TV = sup_p∈𝒫(L^∞())|φ(p) - ψ(p)|,

where 𝒫(L^∞()) = {p∈ L^∞() | p^2 = p = p^*}.


The main tool to study this distance is the Upper Bound Lemma of P. Diaconis and M. Shahshahani <cit.>. We will simply state its quantum version here and refer the reader to <cit.> for details and proofs. For a state φ on Ø() and an irreducible representation α∈() of dimension d_α, we denote by φ(α) the matrix (φ(u^α_ij))_1⩽ i, j⩽ d_α, where (u^α_ij)_1⩽ i, j⩽ d_α is a representative of α.


Let  be a compact quantum group of Kac type and let φ be a state on  which extends to L^∞(). Then,

    φ^∗ k - h_TV^2⩽1/4∑_α∈()∖{1_}d_α(φ(α)^* kφ(α)^k),

where 1_ = 1∈ M_1(Ø()) denotes the trivial representation.


As in <cit.> we will focus on central states, for which the matrices φ(α) are scalar and determined by the restriction of φ to the central algebra, i.e. the *-subalgebra of Ø() generated by characters. The states which we will study here are closely linked to the free product construction. Free probability theory gives tools to deal with such states. Moreover, because our states are central we only need to compute them on the central algebra, and it turns out that one of these states will be a *-homomorphism when restricted to characters. This considerably simplifies computations thanks to the following result :


Let C be a *-algebra together with a state φ and let A and B be *-subalgebras which are *-free with respect to φ. If moreover φ_| A is a *-homomorphism, then for any n∈ and any a_1, ⋯, a_n∈ A and b_0, ⋯, b_n∈ B,

    φ(b_0a_1b_1⋯ b_n-1a_nb_n) = φ(∏_i=1^na_i)φ(∏_i=0^n b_i).




The argument is almost the same as in the proof of <cit.> but we sketch it for completeness. Using the moment-cumulant formula (see for instance <cit.>), we can write

    φ(b_0a_1⋯ a_nb_n) = ∑_π∈ NC(2n+1)κ_π[b_0, a_1, b_1, ⋯, b_n-1, a_n, b_n].

Because A and B are *-free, mixed cumulants vanish (see <cit.>). Moreover, because φ is a *-homomorphism when restricted to A, cumulants of order at least two vanish by <cit.>, so that the term corresponding to a given π is 0 unless its restriction to the a_i's consists only in singletons. In that case, we have no constraint on the restriction of π to the b_i's, so that

    φ(b_0a_1b_1⋯ b_n-1a_nb_n) = φ(∏_i=1^na_i)∑_σ∈ NC(n+1)κ_σ[b_0, b_1, ⋯, b_n]

Using again the moment-cumulant formula, the sum in the right-hand side can be replaced by the corresponding moment and the proof is complete.


For any t > 2, set

    q(t) = t-√(t^2-4)/2.

This is the unique real number 0 < q(t) < 1 such that q(t) + q(t)^-1 = t, and the fundamental quantity for all our estimates. Note that

    q(t)^-1 = t+√(t^2-4)/2⩾t/2

so that q(t) ⩽ 2/t. Let us also define a sequence of functions u_n by

    u_n(t) = q(t)^-n-1 - q(t)^n+1/q(t)^-1 - q(t).

We will use repeatedly the following inequalities (see <cit.> for a proof) :


For all n⩾ 1 and t > 2,

    tq(t)^-(n-1)⩽ u_n(t)⩽q(t)^-n/1-q(t)^2.



Let us end this section with a simple lemma which will be useful for the study of lower bounds.


For a>0 and any N ⩾ 2a,

    N(1-a/N)^Nln(N)/a⩾e^-a/2e/√(2).




This is elementary and was used directly for instance in <cit.> to which we appealed for similar computations in <cit.>. Let us however give a proof for the sake of completeness. Estimates for alternate series yield

    ln(1-x)⩾ - x - x^2/21/1-x = - x - x^2/2(1-x)

so that

    (1-a/N)^N/a⩾exp(-1-a/2(N-a))

and

    N(1-a/N)^Nln(N)/a⩾exp(-aln(N)/2(N-a)).

The maximum of the function x↦ln(x)/x is e^-1, so that

    ln(N)/N-a = ln(N-a)/N-a + ln(N/(N-a))/N-a⩽ e^-1 + ln(2)/a

and the result follows.




§ FREE UNITARY QUANTUM GROUPS


The main part of this work is concerned with free unitary quantum groups, which were introduced by S. Wang in <cit.> and are in a sense the complex versions of the free orthogonal quantum groups studied in <cit.>. We define them through the associated Hopf *-algebra.


Let Ø(U_N^+) be the universal *-algebra generated by N^2 elements u_ij such that for all 1⩽ i, j⩽ N,

    ∑_k=1^Nu_iku_jk^* = δ_ij = ∑_i=1^N u_ik^*u_jk.

The formula 

    Δ(u_ij) = ∑_k=1^Nu_ik⊗ u_kj

extends to an algebra homomorphism Δ : Ø(U_N^+)→Ø(U_N^+)⊗Ø(U_N^+) and this can be completed into a compact quantum group structure.


This defines the free unitary quantum group U_N^+ and the abelianization of Ø(U_N^+) is the algebra of regular functions on the classical unitary group U_N. As mentionned above, U_N^+ can be seen as a "complex version" of O_N^+ and this provides a convenient description of its characters. Let  be the compact group of complex numbers of modulus one and consider the free product (over ) Ø(O_N^+)∗Ø(). It has a canonical compact quantum group structure by <cit.>. Moreover, denoting by v_ij the generators of Ø(O_N^+) and by z the identity function on , it was proven in <cit.> that the map u_ij↦ v_ijz for all 1⩽ i, j⩽ N extends to an isomorphism of compact quantum groups. It then follows from the description of the representation theory of free products in <cit.> that the characters of U_N^+ are products of characters of O_N^+ and powers of z. A more precise description was given in <cit.>, which we reproduce here :


Let (χ_n)_n∈ denote the characters of the irreducible representations of O_N^+. Then, the characters of the irreducible representations of U_N^+ are the elements

    z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+

where ϵ_0∈{-1, 1}, [ϵ]_- = min(ϵ, 0), [ϵ]_+ = max(ϵ, 0) and ϵ_i+1 = (-1)^n_i+1ϵ_i. Moreover, the dimension of the corresponding representation is given by applying the counit, yielding

    ε(z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+) = ∏_i=1^pd_n_i = ∏_i=1^pu_n_i(N).



We now need to build states on Ø(U_N^+) in order to study the associated random walk and this will be done using the free product picture above. Let us choose a state φ on Ø(O_N^+) and a probability measure ν on . Then, the free product state ψ = φ∗∫ν can be restricted to Ø(U_N^+) and yields a state which is central as soon as φ is. As shown in Lemma <ref>, free product states are easier to study when one of the states is a *-homomorphism on the central algebra so that we should choose φ carefully.

As a consequence of <cit.>, for any t∈ [0, N[ there is a state φ_t on Ø(O_N^+) given by φ_t(χ_n) = u_n(t)/d_n which is a *-homomorphism when restricted to the central algebra Ø(O_N^+)_0. We will therefore study the random walk associated to the state φ_t, ν = φ_t∗∫ν and our aim in the next two subsections is to prove that a cut-off phenomenon occurs. The proof will be split into two parts, first the upper bound and then the lower bound. Note that in view of Lemma <ref>, the important quantities are the numbers

    φ_t, ν(z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+)/ε(z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+) = m_ϵ(ν)^2k∏_i=1^pu_n_i(t)^2k/u_n_i(N)^2k-2

where ϵ = [ϵ_0]_- + ϵ_1 + ⋯ + ϵ_p-1 + [ϵ_p]_+ and m_ϵ(ν) is the ϵ-th moment of ν.



 §.§ Upper bound


We start with the upper bound. Since ν is a probability measure on , its moments all have modulus less than one so that the moments of the characters can be bounded by a quantity which only depends on t. This suggests to look for a cut-off parameter independent from ν. In the case of O_N^+, it was shown in <cit.> that writing t = N-τ, the cut-off parameter is exactly Nln(N)/τ. We will now see that the same formula holds for U_N^+.

Setting t = N-τ and k = Nln(N)/τ + cN, we want to prove that the total variation distance between φ^∗ k_t, ν and h is less that C_0e^-ct for some constant C_0. We will use estimates for O_N^+ obtained in <cit.> which are only valid if N is large enough. In particular, in <cit.> it is proven that setting

    C(τ) = 2/τ√(5)(2+√(2 + 9τ^2)),

we have

    Nq(N-τ)(1-q(N-τ)^2) ⩾ e^τ/N

as soon as N⩾τ + C(τ). With this in hand we can establish the upper bound.


For any N⩾τ + C(τ) and any c > ln(2)/2τ,

    φ_N-τ, ν^∗ Nln(N)/τ + cN - h_TV⩽1/√(2-4e^-2cτ)e^-cτ.




Lemma <ref> reduces the problem to the computation of a series where the sum runs over all irreducible representations of U_N^+. Noticing that in an irreducible character, the ϵ-sequence is completely determined by ϵ_0 as soon as the irreducible representations n_1, ⋯, n_p of O_N^+ are fixed, the interesting quantity is :

    A_k(N-τ) = ∑_p=1^+∞∑_n_1, ⋯, n_p⩾ 1∑_ϵ_0∈{-1, 1}| m_ϵ(ν)|^2k∏_i=1^pu_n_i(N-τ)^2k/u_n_i(N)^2k-2.

Since | z| = 1 for all z∈, | m_ϵ(ν)|⩽ 1 for all ϵ and the sum over ϵ_0 can be removed and replaced by a multiplicative factor 2. After these simplifications, the estimates of Lemma <ref> yield

    A_k(N-τ)    ⩽ 2∑_p=1^+∞∑_n_1, ⋯, n_p⩾ 1q(N)^(2k-2)(∑ n_i-p)/q(N-τ)^2k∑ n_i(1/N^2k-2(1-q(N-τ)^2)^2k)^p
        = 2∑_p=1^+∞q(N-τ)^-2kp(1/N^2k-2(1-q(N-τ)^2)^2k)^p∑_n_1, ⋯, n_p⩾ 1(q(N)^2k-2/q(N-τ)^2k)^∑ n_i-p

In the last line above, we have for each p a sum over p-tuples which only depends on n = n_1 + ⋯ + n_p. This suggests to rewrite it using integer partitions. If π_p(n) denotes the number of partitions of n into exactly p parts, the associated generating function is

    ∑_n=p^+∞π_p(n)x^n = x^p/(1-x)⋯(1-x^p) = ∏_i=1^px/1-x^i⩽(x/1-x)^p

for all 0 < x < 1. The proof is elementary and we refer the reader for instance to <cit.>. Thus,

    A_k(N-τ)    ⩽ 2∑_p=1^+∞(1/N^2k-2q(N-τ)^2k(1-q(N-τ)^2)^2k)^p∑_n=p^+∞π_p(n)(q(N)^2k-2/q(N-τ)^2k)^n-p
       ⩽ 2∑_p=1^+∞(1/N^2k-2q(N-τ)^2k(1-q(N-τ)^2)^2k)^p(1/1-(q(N)^2k-2/q(N-τ)^2k))^p.

Recall from the proof of <cit.> and Equation (<ref>) that under our assumption on N,

    q(N)^2k-2/q(N-τ)^2k⩽ e^-2τ c and 1/N^2kq(N-τ)^2k(1-q(N-τ)^2)^2k⩽e^-2τ c/N^2

so that

    A_k(τ)    ⩽ 2∑_p=1^+∞(e^-2τ c/1-e^-2τ c)^p
        = 2e^-2τ c/1 - 2e^-2τ c

where the sum is finite because of our assumption on c. Applying Lemma <ref> then yields the result.


The statement of Proposition <ref> seems incomplete since we have to assume that c > ln(2)/2τ. This could be removed by using Nln(N)/τ + ln(2)N/2τ as the cut-off parameter. However, since the second term has strictly lower order than the first one, only Nln(N)/τ is meaningful (see for instance Proposition <ref> for an illustration of this idea). Note that in <cit.>, U. Porod also has to assume that c is greater than some (non-explicit) constant c_0.



 §.§ Lower bound


To complete the proof of the cut-off phenomenon, we will now prove that if k = Nln(N)/τ - cN, then the total variation distance is close to 1. One efficient strategy to do this uses the Chebyshev inequality and therefore requires to consider a self-adjoint element. The natural candidate is χ = χ_1z + zχ_1. However, if m_1(ν) = 0 = m_-1(ν) (for instance if ν is the Haar measure of ) then φ_t, ν(χ) = 0 and we cannot use this to produce a lower bound. We will therefore use χ_2 instead, which makes the computations a bit more involved but works whatever the measure ν is.


Let us set

    D(τ) = 2/τ + 2τ + √(3τ^2/2 + 3).

Then, for any N⩾ D(τ) and any c > 0,

    φ_N-τ, ν^∗ Nln(N) - cN - h_TV⩾ 1 - 405/8e^6τe^-2cτ.




Let us set k_0 = Nln(N)/τ. The first step is to find a lower bound for the expectation

    φ_N-τ, ν^∗ k_0(χ_2) = ((N-τ)^2 - 1)^k_0/(N^2-1)^k_0-1 = (N^2-1)(1-2Nτ - τ^2/N^2-1)^Nln(N)/τ.

Recall the lower bound used in Lemma <ref> :

    ln(1-x)⩾ - x - x^2/2(1-x)

which we will now apply. For simplicity, let us study each term separately. Setting x = (2Nτ - τ^2)/(N^2-1), we have

    k_0x = ln(N)2N^2 - Nτ/N^2 - 1 = 2ln(N) + ln(N)2-Nτ/N^2-1

which is less than 2ln(N) as soon as N⩾ 2/τ. On the other hand,

    k_0x^2/2(1-x)    = Nln(N)τ(2N - τ/N^2-1)^2N^2 - 1/2((N-τ)^2 - 1)
        = ln(N)τ(2N-τ)^2/2(N-τ)^2 - 2N/N^2-1
        = τln(N)/N-1N/N+1(2N-τ)^2/2(N-τ)^2 - 2.

The first two fractions are less than one for any N⩾ 3. As for the third one, it can be written as

    2 + 4τ N - 3τ^2 + 4/2N^2 - 4τ N + 2τ^2 - 2

and the fraction appearing above is less than one provided 2N^2 - 8τ N + 5τ^2 - 6⩾ 0, which is satisfied as soon as N⩾ 2τ + √(3τ^2/2 + 3). Summing up, as soon as N⩾ D(τ),

    φ_N-τ, ν^∗ Nln(N)/τ(χ_2) ⩾ (N^2-1)exp(-2ln(N) - 3τ) = e^-3τN^2-1/N^2⩾8e^-3τ/9.

Moreover, for any N⩾ (τ+√(τ^2-4))/2, 2N^2 - τ N ⩾ N^2 - 1 so that

    (1 - 2Nτ - τ^2/N^2-1)^-cN⩾exp(c2N^2τ - Nτ^2/N^2-1)⩾ e^cτ

Gathering both inequalities and the fact that (τ+√(τ^2-4))/2⩽τ⩽ D(τ), we see that for N⩾ D(τ),

    φ_N-τ, ν^∗ Nln(N)/τ - cN(χ_2) = (N^2-1)(1-2Nτ - τ^2/N^2-1)^Nln(N)/τ(1-2Nτ - τ^2/N^2-1)^-cN⩾8e^-3τ/9e^cτ.

We can now apply the strategy of <cit.>, bounding the variance of χ_2 by  χ_2_∞^2 = 9. Since h(χ_2) = 0 and h(χ_2^2) = 1, this yields

    φ_N-τ, ν^∗ Nln(N)/τ - cN - h_TV⩾ 1-810/16e^6τe^-2cτ

from which the result follows.


Gathering the upper and lower bound yields the announced cut-off phenomenon.


Let τ > 0 and let ν be a probability measure on the circle. Then, for N⩾max(τ + C(τ), D(τ)) the random walk associated to φ_N-τ, ν has a cut-off at Nln(N)/τ steps.


The striking fact in this theorem is of course that the probability measure ν has no impact on the threshold. Indeed, since the moments of ν are bounded by one, they cannot increase the cut-off parameter in the sense that A_k(N-τ) is always less than its version without ν. However, they could improve the cut-off parameter by making the sum converge faster. This does not happen because the even characters of O_N^+ are also characters of U_N^+ and have the correct lower bound.



 §.§ Random reflections


We now want to take a step further and study random walks coming from classical unitary groups. To our knowledge, the only cut-off phenomenon for unitary groups was proved by U. Porod in <cit.> for random walks generated by reflections. More precisely, any reflection is unitarily conjugate to a diagonal matrix with coefficients (z, 1, ⋯, 1) for some z∈. Thus, given a measure μ on the circle one can pick z at random according to μ and then conjugate it by a Haar distributed random unitary matrix to produce a "random reflection" giving one step of the random walk.



  §.§.§ One conjugacy class


In the quantum setting, we start with the random walk on one conjugacy class, whose construction is explained in <cit.>. If g∈ U_N is a unitary matrix, the evaluation map _g : u_ij↦ g_ij induces a state on the central subalgebra of Ø(U_N^+) which in turn yields a central state on the whole of Ø(U_N^+). Note that since _g is a *-homomorphism, it is completely determined by its image on χ_1z, which is (g). Thus, it coincides with φ_|(g)|, δ_((g)) since this is also a *-homomorphism on the central algebra.

By Theorem <ref>, the corresponding cut-off parameter therefore only depends on the modulus of the trace of g. Setting z = e^iθ, we get |(g)|^2 = N^2 - 2N(1-cos(θ)) + 2(1-cos(θ)) so that

    N - |(g)| = N - √(N^2 - 2N(1-cos(θ)) + 2(1-cos(θ))) = 1-cos(θ) + O(1/N).

This means that the leading term in Nln(N)/τ is Nln(N)/(1-cos(θ)) so that this should be the real cut-off parameter. Let us prove this.


Let φ_θ be the state coming from the uniform measure on the quantum conjugacy class of the diagonal matrix g_θ with coefficients (e^iθ, 1, ⋯, 1). Then, for N⩾max(τ_θ + C(τ_θ), D(τ_θ)) the random walk associated to φ_θ has a cut-off at Nln(N)/(1-cos(θ)) steps.



For convenience, let us set τ_θ = N - |(g_θ)| and λ_θ = 1-cos(θ) and note that

    (N-τ_θ)^2 = N^2 - 2Nλ_θ + 2λ_θ > (N-λ_θ)^2

so that λ_θ > τ_θ. Moreover, using √(1-x)⩽ 1-x/2 we have

    τ_θ = N(1 - √(1-2λ_θ/N + 2λ_θ/N^2)) ⩾λ_θ - λ_θ/N

so that

    d_θ = 1/τ_θ - 1/λ_θ⩽1/τ_θ - N-1/N1/τ_θ = 1/Nτ_θ.

In particular, ln(N)d_θτ_θ⩽ln(4)/4 for all N⩾ 4 (note that D(τ)⩾ 4) and

    φ_θ^∗Nln(N)/λ_θ + cN - h_TV    = φ_θ^∗Nln(N)/τ_θ + (c-d_θln(N))N - h_TV
       ⩽1/√(2-4e^-2cτ_θ)e^d_θτ_θln(N)e^-cτ_θ
       ⩽1/√(1-2e^-2cτ_θ)e^-cτ_θ
       ⩽1/√(1-2e^-3cλ_θ/2)e^-3cλ_θ/4.


As for the lower bound, by Proposition <ref>,

    φ_θ^∗ Nln(N)/λ_θ - cN - h_TV    = φ_θ^∗ Nln(N)/τ_θ - (c+d_θln(N))N - h_TV
       ⩾ 1 - 405/6e^6τ_θe^-2(c+d_θln(N))τ_θ
       ⩾ 1 - 405/6e^6τ_θe^-2cτ_θ.





  §.§.§ Mixed reflections


In <cit.>, U. Porod considered a random walk on the classical unitary group U(N) where the angle θ of the random reflection is chosen using a probability measure μ_N on [0, 2π[ with density (4W_N-1)^-1|sin(θ/2)|^N-1, where W_N = ∫_0^π/2sin(θ)^Nθ is the N-th Wallis integral. A natural idea to study the corresponding problem on U_N^+ would be to try to use our previous results to obtain a cut-off for this random walk and the results of <cit.> together with Proposition <ref> tell us that the cut-off parameter should be Nln(N)/λ with

    λ = ∫_0^2πλ_θμ_N(θ) = ∫_0^2π (1-cos(θ))μ_N(θ) = 2W_N+1/W_N-1 = 2N+1/N+2 = 2 - 2/N+2.

Again in the spirit Proposition <ref>, the cut-off parameter would then be given by the leading term Nln(N)/2, which is exactly the result of <cit.> in the classical case. However, as already noticed in the end of Section 3 of <cit.>, adapting the ideas of <cit.> is not enough since our upper bounds are only valid for N larger than some quantity which goes to infinity as θ goes to 0.

The proof of the cut-off phenomenon must therefore go through a direct computation. This is what we will do now. For clarity, we will split the computations into several lemmata and we first set some notations. Let φ_μ_N be the state on Ø(U_N^+) defined for x∈Ø(U_N^+) by

    φ_μ_N(x) = ∫_0^2πφ_g_θ(x)μ_N(x) = ∫_0^2πφ_N-τ_θ, δ_((g_θ))(x)μ_N(x),

setting as before τ_θ = N - |(g_θ)|. The strategy is to replace τ_θ by λ_θ = 1-cos(θ) to simplify the computations while keeping a control on the difference between the two quantities. The first problem in this approach is that φ_μ_N is not a free product state any more, hence Lemma <ref> does not apply. However,

    |φ_μ_N(z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+)|    = |∫_0^2πφ_g_θ(z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+)μ_N(θ)|
       ⩽∫_0^2π|φ_g_θ(z^[ϵ_0]_-χ_n_1z^ϵ_1⋯ z^ϵ_p-1χ_n_pz^[ϵ_p]_+)|μ_N(θ) 
       ⩽∫_0^2π| m_ϵ(ν)∏_i=1^pu_n_i(N-τ_θ)|μ_N(θ) 
       ⩽∫_0^2π∏_i=1^pu_n_i(N-τ_θ)μ_N(θ)

and the same computation as in the beginning of the proof of Proposition <ref> shows that it is enough to bound

    ∫_0^2π(1/N^2k-2q(N-τ_θ)^2k(1-q(N-τ_θ)^2)^2k)^p∑_n_1, ⋯, n_p⩾ 1(q(N)^2k-2/q(N-τ_θ)^2k)^∑ n_i-pμ_N(θ).

for each p and then compute the sum. Moreover, we can replace ∑ n_i by just one integer n if we multiply by a suitable number of integer partitions. We start by studying the corresponding quantity with τ_θ replaced by λ_θ.


Let us set, for p⩾ 1,

    B_p, n(k) = ∫_0^2π(1/N^2k-2q(N-λ_θ)^2k(1-q(N-λ_θ)^2)^2k)^p(q(N)^2k-2/q(N-λ_θ)^2k)^n-pμ_N(θ).

Then, writing a_N = N-2+2/N, we have

    B_p, n(k) ⩽(a_N^2k/N^2k-2(1-q(N-2)^2)^2k)^p(a_N^2kq(N)^2k-2)^n-p.




Using q(N-λ_θ)⩽ q(N-2), we can bound (1-q(N-λ_θ))^-1 so that we only have one term left in the integral which depends on θ, namely (noticing that q(t)^-1⩽ t)

    ∫_0^2π q(N-λ_θ)^-2knμ_N(θ) ⩽∫_0^2π (N-λ_θ)^2knμ_N(θ).

Let us fix an integer α > 0. Since 1-cos(θ) = 2sin(θ/2)^2, we see that for any ℓ⩽α,

    ∫_0^2πλ_θ^ℓμ_N(θ)     = 1/4W_N-1∫_0^2π 2^ℓ|sin(θ/2)^2ℓ+N-1|θ
        = 2^ℓW_N-1+2ℓ/W_N-1
        = 2^ℓ∏_s=1^ℓN+2s/N+2s+1
       ⩽ 2^ℓ(N+2α/N+2α+1)^ℓ

so that

    ∫_0^2π (N-λ_θ)^αμ_N(θ)    ⩽∑_ℓ=0^ααℓN^α-ℓ(-1)^ℓ2^ℓ(N+2α/N+2α+1)^ℓ
        = (N-2N+2α/N+2α+1)^α
        = (N-2+2/N+2α+1)^α
       ⩽(N-2+2/N)^α.

Applying this for α = 2kn then yields the announced estimate.


If we had q(N-2)^-1 instead of a_N in the bound of Lemma <ref>, then we could use the estimates from <cit.> to finish the computation. It is therefore natural to try to show that a_N is close enough to q(N-2)^-1 so that the aformentioned estimates will still be valid.


For any N⩾ 4,

    a_Nq(N-2)⩽ 1 + 8/(N-2)^2.




It follows from the definition that tq(t) = 1 + q(t)^2, thus

    a_Nq(N-2) = (N-2)q(N-2) + 2/Nq(N-2) = 1 + q(N-2)^2 + 2/Nq(N-2).

Using q(t) ⩽ 2/t and 1/N⩽ 1/(N-2) we get the desired inequality.


As explained in the beginning of this subsection, we must also control the gap between λ_θ and τ_θ and this is the content of the next lemma. We already compared their inverses in the proof of Proposition <ref> but we now need to compare the values of the polynomials u_n at N-λ_θ and N-τ_θ.


For any N⩾ 6 and any θ∈ [0, 2π[,

    u_n(N-τ_θ)/u_n(N-λ_θ)⩽ e^4n/(N-2)^2.




The estimates of Lemma <ref> yield

    u_n(N-τ_θ)/u_n(N-λ_θ)   ⩽1/(N-λ_θ)(1-q(N-τ_θ)^2)q(N-λ_θ)^n-1/q(N-τ_θ)^n
        = 1/(N-λ_θ)q(N-τ_θ)(1-q(N-τ_θ)^2)(q(N-λ_θ)/q(N-τ_θ))^n-1.

Using the fact that q(t) = (1+q(t)^2)/t and the inequality q(t)⩽ 2/t, we get

    1/(N-λ_θ)q(N-τ_θ)(1-q(N-τ_θ)^2)    = N-τ_θ/N-λ_θ1/1-q(N-τ_θ)^4
        = (1 + λ_θ - τ_θ/N-λ_θ)(1 + q(N-τ_θ)^4/1-q(N-τ_θ)^4) 
       ⩽(1 + λ_θ - τ_θ/N-λ_θ)(1 + 16/(N-τ_θ)^4-16).

As for the other term, we need a finer estimate on q(t). Recall from the proof of <cit.> that if (a_n)_n∈ denotes the sequence of coefficients of the power series expansion of the square root function at 1, then

    q(t) = 1/t + ∑_n=2^+∞a_n(2/t)^2n-1.

Since a_n⩽ 1/8 for all n⩾ 2, 1/t⩽ q(t) ⩽ 1/t + 1/(t^3-4t) hence

    q(N-λ_θ)/q(N-τ_θ)   ⩽N-τ_θ/N-λ_θ(1 + 1/(N-λ_θ)^2 - 4) 
       ⩽( 1 + λ_θ-τ_θ/N-λ_θ)(1 + 2/(N-λ_θ)^2)

where we used the fact that for N⩾ 5, (N-λ_θ)^2⩾ 8 and 1/(x-4)⩽ 2/x as soon as x⩾ 8. It follows that

    u_n(N-τ_θ)/u_n(N-λ_θ)   ⩽exp(nλ_θ - τ_θ/N-λ_θ + (n-1)2/(N-λ_θ)^2 + 16/(N-τ_θ)^4-16) 
       ⩽exp(nλ_θ - τ_θ/N-λ_θ + (n-1)2/(N-2)^2 + 16/(N-2)^4-16) 
        = exp(nλ_θ - τ_θ/N-λ_θ + n2/(N-2)^2)exp(-2/(N-2)^2 + 16/(N-2)^4-16)

The second exponential will be less than 1 as soon as 8(N-2)^2⩽ (N-2)^4 - 16, which is satisfied if N⩾ 2 + 2√(1 + √(2)) and this number is less than 6. Moreover, we have seen in the proof of Lemma <ref> that τ_θ⩾ (N-1)λ_θ/N so that

    λ_θ - τ_θ/N-λ_θ⩽λ_θ/N(N-λ_θ)⩽2/N(N-2)⩽2/(N-2)^2

and the result follows.


We are now ready to prove the cut-off for the random walk associated to φ_μ_N. Let us set

    A_k(μ_N) = ∑_p=1^+∞∑_n_1, ⋯, n_p⩾ 1∑_ϵ_0∈{-1, 1}|∫_0^2π m_ϵ(δ_(g_θ))∏_i=1^pu_n_i(N-τ_θ)^2k/u_n_i(N)^2k-2μ_N(θ)|^2k.



For N⩾ 12, the random walk associated to the state φ_μ_N has a cut-off at Nln(N)/2 steps.



We start with the upper bound and we will prove that for any N⩾ 12 and any c > 4 + ln(2),

    φ_μ_N^∗ Nln(N)/2 + cN - h_TV⩽e^2/√(2-4e^4-c)e^-c/2.

Setting b_N = e^4/(N-2)^2, we have by Lemma <ref>

    ∫_0^2π∏_i=1^pu_n_i(N-τ_θ)^2k/u_n_i(N)^2k-2⩽ b_N^2k∑ n_i∫_0^2π∏_i=1^pu_n_i(N-λ_θ)^2k/u_n_i(N)^2k-2.

Thus, Lemma <ref> implies through the same computations as in Proposition <ref> that

    A_k(μ_N)    ⩽ 2∑_p=1^+∞∑_n=p^+∞π_p(n)b_N^2knB_p, n(k) 
       ⩽ 2∑_p=1^+∞((a_Nb_N)^2k/N^2k-2(1-q(N-2)^2)^2k)^p∑_n=p^+∞π_p(n)(q(N)^2k-2(a_Nb_N)^2k)^n-p
       ⩽ 2∑_p=0^+∞((a_Nb_N)^2k/N^2k-2(1-q(N-2)^2)^2k)^p(1/1-q(N)^2k-2(a_Nb_N)^2k)^p.

By Lemma <ref>, Lemma <ref> and the estimates of <cit.> (which are valid since N⩾ 2 + C(2)),

    q(N)^2k-2(a_Nb_N)^2k    = q(N)^2k-2/q(N-2)^2k(q(N-2)a_N)^2kb_N^2k
       ⩽ e^-4cexp((Nln(N)/2 + cN)(16/(N-2)^2 + 8/(N-2)^2)) 
       ⩽ e^-4ce^12Nln(N)/(N-2)^2e^24cN/(N-2)^2
       ⩽ e^4-c.

Here we have used the following two elementary facts : for N⩾ 12,


  * 24N/(N-2)^2⩽ 3,

  * 12Nln(N)/(N-2)^2⩽ 4.

Similarly,

    (a_Nb_N)^2k/N^2k-2(1-q(N-2)^2)^2k⩽ e^4-c

so that as soon as c > 4, everything is summable and

    A_k(μ_N)⩽ 2∑_p=1^+∞(e^4-c/1-e^4-c)^p.

For c > 4 + ln(2), this sum converges and we conclude as in Proposition <ref> that

    φ_μ_N^∗ Nln(N)/2 + cN - h_TV⩽e^2/√(2-4e^4-c)e^-c/2.


For the lower bound, we will again consider the self-adjoint element χ = χ_1z + zχ_1. We have

    ∫_0^2πcos(θ)μ_N(θ) = ∫_0^2π1-sin(θ/2)^2μ_N(θ) = 1 - W_N+1/W_N-1

while by parity the integral of sin(θ) with respect to μ_N vanishes. It follows that

    φ_μ_N(χ) = 2(N-1+1-W_N+1/W_N-1) = N-2+2/N+2,

hence by Lemma <ref> (with a=2),

    φ_μ_N^∗ k(χ)     = 2N(1 - 2/N + 2/N(N-2))^k
       ⩾ 2N(1 - 2/N)^Nln(N)/2(1 - 2/N)^-cN
       ⩾e^-1/e/√(2)e^2c

Moreover, _φ_μ_N^∗ k(χ)⩽χ_∞^2⩽ 4 and h(χ) = 0 while h(χ^2) = 2 so that the general method of <cit.> yields

    φ_μ_N^∗ k - h_TV⩾ 1 - 8e^2/ee^-2c(4 + 2) ⩾ 1 - 101e^-2c.





§ FREE WREATH PRODUCTS


The quantum reflection groups H_N^s+ were introduced by T. Banica in R. Vergnioux in <cit.> as quantum versions of the complex reflection groups H_N^s of matrices with one s-th root of unity in each row and column and all other coefficients equal to 0. It is well-known that these can also be seen as wreath products via the isomorphism H_N^s≃_s≀ S_N^+. In the quantum case, this wreath product decomposition has an analogue involving the notion of free wreath product introduced by J. Bichon in <cit.> : to any compact quantum group  and integer N it associates a new compact quantum group ≀_∗S_N^+. A particular case is when = Γ is the dual of a discrete group Γ, and when Γ = _s we recover the quantum reflection groups H_N^s+. Our aim is to prove a cut-off result for central random walks on quantum reflection groups and more generally on free wreath products of duals of finite groups by S_N^+.

For this purpose, we need a description of the representation theory of Γ≀_∗S_N^+ as well as a method to construct explicit central states. Both can be obtained thanks to the notion of monoidal equivalence from <cit.>, which is a useful technical tool from quantum group theory. Instead of introducing it, we will simply give the results needed in the sequel :


  * It follows from <cit.> that if two compact quantum groups are monoidally equivalent, then there is a bijection between their sets of equivalence classes of irreducible representations which induces a bijection between their central states,

  * By <cit.>, Γ≀_∗ S_N^+ is monoidally equivalent to the quantum subgroup of SU_q(√(N))(2)∗Γ generated by the coefficients of the irreducible representations of the form u^1γ u^1 for all γ∈Γ. Here, SU_q(2) is S.L. Woronowicz' quantum SU(2) group introduced in <cit.>.

To complete the description, we have to explain what is the representation theory of SU_q(2), but this is the same as O_N^+ except that the dimension of the n-th irreducible representation is u_n(q+q^-1) = (q^-n-1 - q^n+1)/(q^-1 - q). On can then show (see for instance the beginning of Section 3 of <cit.>) that the characters are all words of the form

    χ_2n_0+1γ_1χ_2n_1+2γ_2⋯χ_2n_p-1+2γ_pχ_2n_p+1.


Now, given a state φ_t on Ø(SU_q(2)) and any state ψ on Ø(Γ) = [Γ], we can form their free product, restrict it to the subgroup indicated above and then transfer it through monoidal equivalence. Note that because SU_q(2) is not of Kac type, it is not clear that φ_t : χ_n↦ u_n(t) extends to a central state (there is no Haar state preserving conditional expectation onto the central algebra). This is nevertheless true by <cit.>, so let ψ be a state on Ø(Γ) and let φ_t, ψ be the corresponding state on Ø(Γ≀_∗S_N^+). The right-hand side of the inequality in Lemma <ref> can be written as

    A_k(t) = ∑_p=0^+∞∑_n_0, ⋯, n_p∑_γ_1, ⋯, γ_p|ψ(γ_1⋯γ_p)|u_2n_0+1(t)^2ku_2n_p+1(t)^2k/u_2n_0+1(√(N))^2k-2u_2n_p+1(√(N))^2k-2∏_i=1^p-1u_2n_i+2(t)^2k/u_2n_i+2(√(N))^2k-2.

The expression above is slightly ambiguous as far as the term for p=0 is concerned. We write it this way for concision, but when computing we will distinguish in the end the case p = 0 from the other cases. As for free unitary quantum groups in Section <ref>, we will see that the cut-off parameter does not depend on the state ψ. Note that because ψ has norm one and any element of Γ is a unitary, we have the inequality

    ∑_γ_1, ⋯, γ_p∈Γ|ψ(γ_1⋯γ_p)|⩽|Γ|^p.



To see this let us set

    K(ψ) = ∑_γ∈Γ|ψ(γ)|.

We will use the following elementary fact :


For an integer p⩾ 1,

    ∑_γ_1, ⋯, γ_p∈Γ|ψ(γ_1⋯γ_p)| = |Γ|^p-1K(ψ) ⩽|Γ|^p.




Let us set, for γ∈Γ,

    S_p(γ) = {(γ_1, ⋯, γ_p)∈Γ^p|γ_1⋯γ_p = γ}.

For γ≠γ'∈Γ, the map ϕ_γ, γ' : S_p(γ)→ S_p(γ') sending (γ_1, ⋯, γ_p) to (γ'γ^-1γ_1, ⋯, γ_p) is a bijection with inverse ϕ_γ', γ. Thus, the cardinality of S_p(γ) does not depend on γ. Since moreover the disjoint union of these |Γ| sets is Γ^p, they have cardinality |Γ|^p/|Γ| = |Γ|^p-1. Thus,

    ∑_γ_1, ⋯, γ_p∈Γ|ψ(γ_1⋯γ_p)| = |Γ|^p-1∑_γ∈Γ|ψ(γ)| = |Γ|^p-1K(ψ).

The inequality in the statement follows from the fact that ψ, being a state, has norm one and γ is unitary for all γ∈Γ.



As usual, we will consider a parameter t of the form N-τ. This means that we need estimates for expressions involving powers of the function q evaluated at √(N) and √(N-τ). For τ = 2, such estimates where obtained in the proof of <cit.>. We will now expand the argument to other values of τ. However, and quite surprisingly, we will see that we need to assume that τ is larger that 7/4 to get the required estimate. We are therefore not able to prove as general a result as <cit.>.


There exist a degree four polynomial Q∈[X] such that for any τ > 7/4 and N⩾ Q(τ)/(4τ - 7),

    q(√(N))/√(N)q(√(N-τ))^2(1-q(√(N-τ))^2)⩽ e^-τ/N.




Proceeding as in the proof of <cit.> and using the fact that e^τ/(t+τ)⩽ 1 + τ/t, we know that for t = N - τ⩾ 12 the inequality in the statement is implied by the inequality

    √(t+τ)√(t+τ) + √(t+τ - 4)/2(1/t + 1/t^2 + 1/2t^3) ⩾ 1 + τ/t.

Developing the left-hand side and letting aside the terms with t^3 at the denominator yields the stronger inequality

    1 + τ/t⩽1/2 + 1/2t + 1/4t^2 + τ/2t + τ/2t^2 + √((t+τ)(t+τ-4))/2t + √((t+τ)(t+τ-4))/2t^2.

which, after multiplying by 2t^2, yields

    t^2 + (τ-1)t ⩽1/2 + τ + (t+1)√((t+τ)(t+τ-4)).

Let us set f(t) = √((t+τ)(t+τ-4)). Using the lower bound √(1+x)⩾ 1+x/2-x^2/8 yields

    f(t)     = t√(1 + 2τ - 4/t + τ^2-4τ/t^2)
       ⩾ t(1 + τ-2/t + τ^2 - 4τ/2t^2 - τ^2-4τ+4/2t^2-(τ-2)(τ^2-4τ)/2t^3 - (τ^2-4τ)^2/8t^4) 
        = t + (τ-2) - 2/t - (τ - 2)(t^2 - 4τ)/2t^2 - (τ^2 - 4τ)^2/8t^3

so that

    (t+1)f(t) ⩾ t^2 + (τ-1)t + τ - 4 - 4 + τ^3 - 6τ^2 + 8τ/2t - (τ^2-4τ)(τ^2-8)/8t^2 - (τ^2 - 4τ)^2/8t^3.

Since t⩾ 14, it is enough to have

    4× 14^2(4 + τ^3 - 6τ^2 + 8τ) + 14(τ^2-4τ)(τ^2-8) + (τ^2 - 4τ)^2/8× 14^2× t⩽ 2τ - 7/2

and the proof is complete, noticing that the above condition and N⩾τ + 12 can be expressed with one polynomial Q(τ).


It is easy to extract from the above proof an explicit polynomial Q which works. We did not do it in order to lighten the proof, but let us give it as a separate statement :


In the statement of Proposition <ref>, one can take the polynomial

    Q(τ) = τ^4/28 + 2τ^3 - 8τ^2 + 59τ - 76.




Let us denote by P(τ) the numerator of the left-hand side of Equation (<ref>). To take into account the extra condition N⩾τ + 12, we have to consider the polynomial R(τ) = P(τ) + (4τ - 7)(τ  + 12). Developping and simplifying then yields

    R(τ) = τ^4 + 52τ^3 - 232τ^2 + 1628τ - 2128/28

which is less than the polynomial in the statement.


Note that using this and micking the proof of <cit.>, one obtains a proof of the cut-off for the uniform quantum random walk on m-cycles for arbitrary m mentioned in the end of <cit.>. We are now ready for the proof of the cut-off phenomenon for free wreath products.


Let τ > 7/4 and N⩾ Q(τ)/(4τ - 7). Then, the random walk associated to φ_N-τ, ψ has a cut-off at Nln(N)/τ steps.



As usual, we start with the upper bound and we will prove that for k = Nln(N)/τ and any c > ln(1+√(|Γ|))/2τ,

    φ_N-τ, ψ^∗ Nln(N)/τ + cN - h_TV⩽e^-τ c/√(1 - 1e^-2τ c)√(1+√(|Γ|)).

This requires bounding A_k(√(N-τ)) and we will first consider the sum over (n_0, ⋯, n_p). By Lemma <ref>,

    ∑_n_0, ⋯, n_p⩾ 1u_2n_0+1(√(N-τ))^2k/u_2n_0+1(√(N))^2k-2u_2n_p+1(√(N-τ))^2k/u_2n_p+1(√(N))^2k-2∏_i=1^p-1u_2n_i+2(√(N-τ))^2k/u_2n_i+2(√(N))^2k-2
    ⩽   ∑_n_0, ⋯, n_p⩾ 1q(√(N))^(2k-2)(p-1+2∑ n_i)/q(√(N-τ))^2k(2p + 2∑ n_i)(1/√(N)^2k-2(1-q(√(N-τ))^2)^2k)^p+1
    
    =    q(√(N))^(2k-2)(p-1)/q(√(N-τ))^4kp(1/√(N)^2k-2(1-q(√(N-τ))^2)^2k)^p+1∑_n=p+1^+∞π_p+1(n)(q(√(N))^4k-4/q(√(N-τ))^4k)^n
    ⩽   q(√(N))^(2k-2)(p-1)/q(√(N-τ))^4kp(1/√(N)^2k-2(1-q(√(N-τ))^2)^2k)^p+1(q(√(N))^4k-4/q(√(N-τ))^4k)^p+1
       ×(1/1 - q(√(N))^4k-4/q(√(N-τ))^4k)^p+1
    
    =    (q(√(N))^4k-4/q(√(N-τ))^4k)^p(q(√(N))^2k-2/√(N)^2k-2q(√(N-τ))^4k(1-q(√(N-τ))^2)^2k)^p+1(1/1 - q(√(N))^4k-4/q(√(N-τ))^4k)^p+1.

It follows from the proof of <cit.> that

    q(√(N))^4k-4/q(√(N-τ))^4k⩽ e^-2τ c

and under our assumption on N, Proposition <ref> yields (through a computation similar to that of <cit.>)

    q(√(N))^2k-2/√(N)^2k-2q(√(N-τ))^4k(1-q(√(N-τ))^2)^2k⩽ e^-2τ c.

Combining both estimates with Equation (<ref>) and separating the term for p=0, we get

    A_k(√(N-τ))    ⩽e^-2τ c/1-e^-2τ c + ∑_p=1^+∞|Γ|^p(e^-2τ c)^p(e^-2τ c/1-e^-2τ c)^p+1.

The series converges for c⩾1/2τln(1+√(|Γ|))⩾1/2τln(1 + √(4|Γ|+1)/2) and

    A_k(√(N-τ))    ⩽e^-2τ c/1-e^-2τ c + e^-2τ c/1-e^-2τ c|Γ| e^-4τ c/1-e^-2τ c/1 - |Γ| e^-4τ c/1-e^-2τ c
        =e^-2τ c/1-e^-2τ c(1 + |Γ| e^-4τ c/1 - e^-2τ c - |Γ| e^-4τ c).

The assumption on c implies that

    |Γ| e^-4τ c/1 - e^-2τ c - |Γ| e^-4τ c⩽|Γ|/(1 + √(|Γ|))^2 - (1+√(|Γ|)) - |Γ| = √(|Γ|)

and the claim follows.

As for the lower bound, we simply have to consider the character χ_2. Its expectation and variance under the Haar state h are respectively equal to 0 and 1. 
Using the same inequality as in Lemma <ref>, we see that for N⩾ 2+τ

    (N-1)(1 - τ/N-1)^Nln(N)/τ   ⩾N-1/Ne^-ln(N)/N-1(1 + Nτ/2(N-1-τ))
       ⩾3/4e^-e^-1 - e^-1τ(τ+2)/2
       ⩾1/2e^-τ(τ+2)/5.

so that

    φ_N-τ, ψ^∗ k(χ_2)      = (N-1)(N-τ-1/N-1)^k
       ⩾ (N-1)(N-τ-1/N-1)^Nln(N)/τe^cNτ/N-1
       ⩾1/2e^-τ(τ+2)/5e^2τ c.

Moreover, _φ_N-τ, ψ^∗ k(χ_2)⩽χ_2_∞^2⩽ 9 so that (using τ > 7/4)

    φ_N-τ, ψ^∗ k - h_TV⩾ 1 - 40e^-2τ(τ+2)/5e^4τ c.




amsplain


