Michael Magee

Frédéric Naud

Extension of Alon's and Friedman's conjectures to Schottky surfaces

Let X = Λ\H be a Schottky surface, that is, a conformally compact hyperbolic surface of infinite area. Let δ denote the Hausdorff dimension of the limit set of Λ.

We prove that for any compact subset K ⊂ { s : Re(s) > δ 2 }, if one picks a random degree n cover X n of X uniformly at random, then with probability tending to one as n → ∞, there are no resonances of X n in K other than those already belonging to X (and with the same multiplicity). This result is conjectured to be the optimal one for bounded frequency resonances and is analogous to both Alon's and Friedman's conjectures for random graphs, which are now theorems due to Friedman and Bordenave-Collins, respectively.

Introduction

Let X be an infinite area surface equipped with a metric of constant curvature -1, with a finitely generated non-abelian fundamental group and without cusps. Such a surface is called a conformally compact hyperbolic surface.

This paper addresses the question of whether typical such surfaces have (almost) optimal spectral gaps. Here, a spectral gap refers either to a gap in the spectrum of the Laplace-Beltrami operator or, more ambitiously, to a region where there are no resonances of the meromorphically continued resolvent. We give the background to this spectral theory now; for general background on the spectral theory of infinite area hyperbolic surfaces the reader should see [START_REF] Borthwick | Spectral theory of infinite-area hyperbolic surfaces[END_REF].

One can obtain X as a quotient X = Λ\H where H is the hyperbolic upper half plane and Λ is a discrete, finitely generated, non-abelian free subgroup of PSL 2 (R), and, in fact, by a result of Button [But98] there are generators γ 1 . . . , γ d of Λ for some d ≥ 2 which form a Schottky system in the sense of § §2.1. The orbit of Λ on any fixed point of H accumulates on ∂H in a set called the limit set of Λ; we write δ = δ(Λ) for the Hausdorff dimension of the limit set. The assumption that Λ is non-abelian and X is infinite area implies δ ∈ (0, 1).

Let ∆ X denote the Laplace-Beltrami operator on L 2 (X). The spectrum of ∆ X in the range [ 1 4 , ∞) is always continuous with no embedded eigenvalues, and the spectrum is always discrete below 1 4 , by work of Lax-Phillips [LP81]. If δ > 1 2 then the bottom of the spectrum occurs at δ(1 -δ) by a result of Patterson [Pat76]. Therefore a naive definition of spectral gap in this case is λ 1 -δ(1 -δ) where λ 1 is the minimum element of the spectrum other than δ(1 -δ), including δ(1 -δ) itself if it occurs with multiplicity larger than one. However, if δ ≤ 1 2 then the spectrum is precisely [ 1 4 , ∞) and this notion of spectral gap has no meaning. Moreover, even if δ > 1 2 , it does not give the strongest possible information as we explain now.

The resolvent operator

R X (s) def = (∆ X -s(1 -s)) -1 : C ∞ 0 (X) → C ∞ (X)
has meromorphic continuation from Re(s) > 1 2 to the entire complex plane [MM87]. The poles of this family of operators are called resonances of X. The multiplicity of a resonance s is given by rank γ R Y (s)ds where γ is an anticlockwise oriented circle enclosing s and no other resonance of X. Resonances s with Re(s) > 1 2 yield eigenvalues s(1 -s) with the same multiplicity. We write R X for the multiset of resonances of X, including multiplicities. Now it is apparent that beyond L 2 spectral gaps, we can ask for resonance-free regions of the complex plane. We summarize what is known in this regard assuming that X is connected (otherwise there is no spectral gap in any sense). In the half-plane Re(s) > 1 2 , there are finitely many resonances that all lie on the real line, the right-most one being at s = δ. If δ ≤ 1 2 , then we know from [START_REF] Naud | Expanding maps on Cantor sets and analytic continuation of zeta functions[END_REF] that there exists (Λ) > 0 such that in the half plane {Re(s) > δ -}, the only resonance is at s = δ. Therefore the spectral gap is then defined as the maximal size of this (Λ). It was shown in [START_REF] Jakobson | Large covers and sharp resonances of hyperbolic surfaces[END_REF] that this gap can be arbitrarily small. A conjecture of Jakobson and Naud [JN12, Conj. 2] predicts (among other things) that for any > 0 there are infinitely many resonances with Re(s) > δ 2 -and hence one does not expect to obtain spectral gap larger than δ 2 . It is a pressing question as to whether 'typical' surfaces have a spectral gap close to this optimal value; this question has famous analogs in graph theory that we will turn to shortly.

In [MN20] we introduced a model of random conformally compact hyperbolic manifolds based on random covering spaces. For any n ∈ N the collection of degree n Riemannian covering spaces of X is a finite set and hence we can pick one of these covering spaces uniformly at random. Note that if X covers X, then any resonance of X is a resonance of X , with at least as large multiplicity. The main theorem of this paper is the following.

Theorem 1.1. Let X n denote a uniformly random degree n covering space of X. For any compact set K ⊂ { s : Re(s) > δ 2 }, with probability tending to one as n → ∞

R Xn ∩ K = R X ∩ K.
This theorem says that for any > 0, the resonance set of random X n in the region { s : Re(s) > δ 2 + } is almost surely optimal provided we restrict to bounded frequency (imaginary part). A weaker version of Theorem 1.1 with δ 2 replaced by 3δ 4 was proved in [MN20, Thm. 1.1] Theorem 1.1 together with the main result of [BMM17] implies the following corollary on L 2 eigenvalues.

Corollary 1.2. Assume that δ >1 2 , and that the base surface 1 X has Euler characteristic -1. Let X n denote a uniformly random degree n covering space of X. With probability tending to one as n → ∞ the only eigenvalue of ∆ Xn is δ(1 -δ).

We now explain the analogy with random graphs; this is also discussed in detail in [MN20,Introduction]. A celebrated conjecture of Alon [START_REF] Alon | Eigenvalues and expanders[END_REF] predicted that for any > 0, a uniformly random d-regular graph on n vertices, with probability tending to one as n → ∞, has no eigenvalues of its adjacency operator larger than 2 √ d -1 + , other than d. The relevance of the value 2 √ d -1 is both that it is the spectral radius of the adjacency operator on the universal cover of a d-regular graph (a d-regular tree), and also, a result of Alon-Boppana [Nil91] states that any sequence of d-regular graphs on n vertices has second largest eigenvalue of their adjacency operators at least 2 √ d -1-o(1) as n → ∞. Hence the value 2 √ d -1 is analogous to δ 2 here. It is interesting however that even though the Alon-Boppana bound is not very hard to prove, the analog of this fact in the current setting is still only a conjecture. Alon's conjecture was proved by Friedman in [Fri08] (see also [Bor] for a new proof and [Pud15] for a proof of only slightly weaker result).

Friedman conjectured in [START_REF] Friedman | Relative expanders or weakly relatively Ramanujan graphs[END_REF] that a variant of Alon's conjecture should hold for random degree n covering spaces2 of a fixed finite base graph provided The first result on spectral gap of random hyperbolic surfaces is due to Brooks and Makover [BM04] who prove that for a combinatorial model of random closed hyperbolic surface, depending on a parameter n that influences the genus (non-deterministically), that there exists a constant C > 0 such that with probability tending to one as n → ∞, the first non-zero eigenvalue (λ 1 ) of the Laplacian satisfies λ 1 ≥ C. Mirzakhani proved in [Mir13] that for Weil-Petersson random closed hyperbolic surfaces of genus g, with probability tending to one as g → ∞ one has λ 1 ≥ 0.0024. In [MN20] the authors of the current paper proved that Theorem 1.1 holds with δ 2 replaced by 3δ 4 . Returning to closed surfaces, by building on [MP20], the authors and Puder proved in [START_REF] Magee | A random cover of a compact hyperbolic surface has relative spectral gap 3 16 -ε[END_REF] that for a uniformly random degree n cover of a fixed closed hyperbolic surface, there are for any > 0, with probability tending to one as n → ∞, no new eigenvalues of the covering space below 3 16 -. This result was adapted to Weil-Petersson random surfaces independently by Wu and Xue [WX21] and Lipnowski and Wright [LW21]; here the corresponding statement is that there are no eigenvalues between 0 and 3 16 -. These ' 3 16 ' results are, when it comes solely to L 2 eigenvalues, at the strength of the result of [MN20] giving resonance-free regions in terms of 3δ 4 ; for compact surfaces δ = 1 and the eigenvalue is written λ = s(1 -s)

( 3 4 1 -3 4 = 3 16
). On the other hand, closed surfaces involve additional difficulties due to their non-free fundamental groups.

There are other related works on Weil-Petersson random surfaces that do not imply spectral gaps, but instead offer some spectral delocalization results [Mon20, GLMST21].

Uniform spectral gap for (deterministic) covering spaces of infinite area hyperbolic surfaces has also been of interest in number theoretic settings; see [BGS11, OW16, MOW17, Gam02] for a selection of results; the single quantitative result here is by Gamburd [START_REF] Gamburd | On the spectral gap for infinite index "congruence" subgroups of SL 2 (Z)[END_REF]. Much of the motivation of these spectral gap results came from the 'thin groups' research program; see Sarnak's article [Sar14] for an overview.

Another closely related concept is that of essential spectral gap; referring to a half-plane where only finitely many resonances appear. Two important results here are due to Bourgain and Dyatlov. Let X be conformally compact as above. The first result, proved in [START_REF] Bourgain | Fourier dimension and spectral gaps for hyperbolic surfaces[END_REF], says that there is > 0, depending only on δ, such that there are only finitely many resonances in { s : Re(s) > δ -}. This result is relevant if δ ≤ 1/2. On the other hand, it is proved in [START_REF] Bourgain | Spectral gaps without the pressure condition[END_REF] that there are only finitely many resonances in { s : Re(s) > 1 2 -η } for some η = η(Λ) > 0, this result being relevant if δ > 1 2 . A conjecture of Jakobson-Naud [JN12] says that the optimal essential spectral gap corresponds to finitely many resonances in Re(s) > δ 2 + ε for any ε > 0. We do not know yet if our probabilistic techniques can be used to address high frequency problems (i.e. resonances with large imaginary parts) and have not attempted to do so in the present paper, however the present paper says that in some sense this conjecture holds in the bounded frequency, large cover regime. For a broader perspective on resonances of hyperbolic surfaces than we are able to offer here, the reader can see Zworski's survey article [Zwo17].

Preliminaries

Boundary coding of Schottky groups and Bowen's formula

In this section, we set some notations (which are essentially similar to [MN20] and [START_REF] Bourgain | Fourier dimension and spectral gaps for hyperbolic surfaces[END_REF] with some slight changes).

Let d ≥ 2 and I = {1, . . . , 2d}. If i ∈ I, then we write ī def = i + d mod 2d so i ∈ I. For each i ∈ Iwe are given an open disc D i in C with center in R. The closures of the discs D i for i ∈ I are assumed to be disjoint from one another. We let

I i def = D i ∩ R, an open interval.
We write D def = ∪ i∈I D i for the union of the discs. We consider the usual action of SL 2 (R) by Möbius transformations on the extended complex plane Ĉ = C ∪ {∞}. We are given for each i ∈ I a matrix γ i ∈ SL 2 (R) with the mapping property

γ i Ĉ\Dī = D i , γī = γ -1 i .
We recall that we denote Λ def = γ i : i ∈ I for the group generated by the γ i . Since the discs D i are disjoint, Klein's Ping-Pong Lemma shows that Λ is a free subgroup of SL 2 (R). The converse is actually true in dimension 2: every conformally compact hyperbolic surface X can be uniformized by a Schottky group Λ so that X = Λ\H, see [But98]. The elements of Λ can be encoded by words in the alphabet I as follows. A word is a finite sequence i = (i 1 , . . . , i n ), n ∈ N ∪ {0} such that i j = i j+1 for j = 1, . . . , n -1. We say that n is the length of i and denote this by |i| = n. We write W for the collection of all words, W N for the words of length N , and W ≥N for the words of length ≥ N . We write ∅ for the empty word and write W • = W -{∅}. For i = (i 1 , . . . , i n ), j = (j 1 , . . . j m ) ∈ W we write

• i def = (i 1 , . . . , i n-1 ) if i = (i 1 , . . . , i n ) and n ≥ 1. • î def = (i 2 , . . . , i n ) if i = (i 1 , . . . , i n ) and n ≥ 1.
• i → j if either of i or j is empty, or else i n = j 1 , in which case (i 1 , . . . , i n , j 1 , . . . , j m ) is in W • and we write ij for this concatenation.

If i = (i 1 , . . . , i n ) ∈ W then we associate to i the group element γ i def = γ i 1 . . . γ in ; here γ ∅ = id.

The map i ∈ W → γ i ∈ Γ is a one-to-one encoding of Γ. We write i def = (i n , . . . , i 1 ) and call this the mirror word of i. Note that

γ i = γ -1 i . If i = (i 1 , . . . , i n ) ∈ W • we set D i = γ i (D in ), I i = γ i (I in )
and write |I i | for the length of the open interval I i . We view this set up as fixed henceforth, so all constants will depend on Λ. The Bowen-Series map T : D → Ĉ is given by

T | D i = γ -1 i = γī.
The Bowen-Series map is eventually expanding [Bor16, Prop. 15.5]; this will be made explicit below so we do not give the general definition now. The limit set K = K(Λ) of Λ, defined in the Introduction, coincides with the non-wandering set of T :

K(Λ) def = ∞ n=1 T -n (D).
The limit set K is a compact T -invariant subset of R. Given a Hölder continuous map ϕ : K → R, the topological pressure P (ϕ) can be defined through the variational formula:

P (ϕ) def = sup µ h µ (T ) + Λ ϕdµ ,
where the supremum is taken over all T -invariant probability measures on K(Λ), and h µ (T ) stands for the measure-theoretic entropy. A famous result of Bowen [START_REF] Bowen | Hausdorff dimension of quasicircles[END_REF] says that the map R → R, r → P (-r log |T |) is convex 3 , strictly decreasing and vanishes exactly at r = δ def = δ(Λ), the Hausdorff dimension of the limit set K(Λ). In addition, it is not difficult to see from the variational formula that P (-r log |T |) tends to -∞ as r → +∞. For simplicity, we will use the notation P (r) in place of P (-r log |T |). The pressure functional plays an important role in the sequel.

Random covering spaces, permutations, and representations

Let S n denote the group of permutations of [n] def = {1, . . . , n}. Our random covering spaces of X are parameterized by φ ∈ Hom(Λ, S n ).

Of course, choosing φ is the same as choosing

σ = (σ 1 , . . . , σ d ) ∈ S d n where σ i def = φ(γ i ).
We view σ and φ as coupled in this way in the rest of the paper. Given φ ∈ Hom(Λ, S n ), we construct a covering space of X as follows. Let Λ act on

H × [n] by γ(z, i) = (γ.z, φ(γ)[i])
where the action on the first factor is by Möbius transformation. The quotient

X φ def = Λ\ φ (H × [n])
is a degree n cover of X. Choosing φ uniformly at random in Hom(Λ, S n ), the resulting X φ is a uniformly random degree n Riemannian cover of X.

Let V n def = 2 ([n]
). Given φ ∈ Hom(Λ, S n ) as above, we let ρ n : Λ → End(V n ) be the representation obtained by composing φ with the standard permutation representation

S n → End(V n ).
We let ρ 0 n denote the restriction of ρ n to the space V 0 n of functions on [n] that are orthogonal to constants. The parameters φ, ρ n , and ρ 0 n (as well as σ) are now coupled for the rest of the paper.

Transfer operator and function spaces

Let V be a finite dimensional complex Hilbert space. We consider the Bergman space H(D; V ) that is the space of V -valued holomorphic functions on D with finite norm with respect to the given inner product

f, g def = D f (x), g(x) V dm(x).
Here dm is Lebesgue measure on D. This splits as an orthogonal direct sum

H(D; V ) = i∈I H(D i ; V ). If {e k } ∞ k=1 is any orthonormal basis of H(D i ; C), and x 1 , x 2 ∈ D i , then the sum ∞ k=1 e k (x 1 )e k (x 2 ) def = B D i (x 1 , x 2 )
converges uniformly on every compact subset of D i and is called the Bergman kernel of D i .

It is given by the explicit formula (cf. [Bor16, pg. 378])

B D i (x 1 , x 2 ) = r 2 i π r 2 i -(x 2 -c i )(x 1 -c i ) 2 (2.1)
where r i , c i are the radius and center of D i . We let

B D (z, w) def = i∈I 1{z, w ∈ D i }B D i (z, w).
An important fact that will be used several times in this paper is the reproducing property of the Bergman kernel: if f ∈ H(D, V ), then we have for all z ∈ D,

f (z) = D B D (z, w)f (w)dm(w),
in particular for all compact subsets K ⊂ D, the above explicit formulas for the kernels show that there exists

C K > 0 such that sup z∈K f (z) V ≤ C K f H(D,V ) .
Throughout the sequel, ρ : Λ → U(V ) will denote a finite dimensional unitary representation of the Schottky group Λ. The transfer operator acting on H(D, V ) is defined as follows:

L s,ρ [f ](x)f def = i∈I i→j γ i (x) s ρ(γ -1 i )f (γ i (x)) x ∈ D j , j ∈ I.
Here (γ i (x)) s is understood as

(γ i (x)) s := e -sτ (γ i (x)) , where τ (z) is the analytic continuation to ∪ |i|=2 D i of τ (x) = log |T (x)|
, and where T is, as defined above, the Bowen-Series map. In addition, we can assume that τ is also continuous on ∪ |i|=2 D i .

The following result appears in [Bor16, Lemma 15.7] in the case V = C, and easily extends to the case of finite dimensional V .

Lemma 2.1. The operator L s,ρ is a trace class operator on the Hilbert space H(D, V ).

Our interest in considering these operators stems from setting ρ = ρ 0 n from § §2.2. The following fact follows from [MN20, Thm 2.2. and Prop. 4.4(2)].

Proposition 2.2. If s is a resonance of X φ that appears with greater multiplicity than in X, for example, by not being a resonance of X, then

det(1 -L s,ρ 0 n ) = 0
and hence 1 is an eigenvalue of L s,ρ 0 n . (The determinant above is a Fredholm determinant.)

Deterministic a priori bounds

We will now introduce a useful notation from [MN20]. In the rest of the paper, for any i ∈ W • , we define

Υ i def = |I i |,
that is the length of the interval I i associated to the word i. For all i ∈ W ≥2 , we have obviously

Υ i ≤ Υ i (2.2) since I i ⊂ I i . Therefore there exists trivially c = c(Λ) > 0 such that for any i ∈ W o , 0 < Υ i ≤ c. (2.3)
Lemma 2.3. There exists a constant K = K(Λ) > 1 such that the following bounds hold.

(Rough multiplicativity) For all i, j ∈ W • with i → j, we have

K -1 Υ i Υ j ≤ Υ ij ≤ KΥ i Υ j .
(2.4) (Mirror estimate) For all j ∈ W • , we have

K -1 Υ j ≤ Υ j ≤ KΥ j .
(2.5) (Derivatives) For all x ∈ D i |i| , we have

K -1 Υ i ≤ |γ i (x)| ≤ KΥ i . (2.6) (Exponential Bound) There is a constant D = D(Γ) > 1 such that Υ i ≤ KD -|i| . (2.7)
The proof of these bounds follow from [MN20, Lemmas 3.1, 3.2, 3.4, 3.5] and follows previous estimates from [START_REF] Bourgain | Fourier dimension and spectral gaps for hyperbolic surfaces[END_REF]. The following result is [MN20, Lemma 3.10].

Lemma 2.4. For all r 1 , Q ∈ R such that 0 ≤ r 1 < Q there is a constant C = C(r 1 , Q) > 0 such that for all N ∈ N 0 and r ∈ [r 1 , Q] we have i∈W N Υ r i ≤ C exp(N P (r 1 )). (2.8) Lemma 2.5. Suppose that K ⊂ C is compact. There is a constant C = C(K) > 0 such that for all ∈ N and s, s 0 ∈ K L s,ρ 0 n -L s 0 ,ρ 0 n ≤ |s -s 0 |C ,
where . denotes the operator norm on H(D, V 0 n ).

Proof. Let f ∈ H(D, V 0 n ). We write L s,ρ 0 n (f ) -L s 0 ,ρ 0 n (f ) 2 = D L s,ρ 0 n (f ) -L s 0 ,ρ 0 n (f ) 2 V 0 n dm = 2d j=1 D j i→j, |i|= e -sτ ( ) (γ i z) -e -s 0 τ ( ) (γ i z) ρ 0 n (γ -1 i )f (γ i z) 2 V 0 n dm(z),
where we have set

τ ( ) (γ i z) def = τ (γ i 1 ...i z) + τ (γ i 2 ...i z) + . . . + τ (γ i z).
Notice that there exists M > 0 independent of such that for all z, i above we have |τ ( ) (γ i z)| ≤ M . We will then use the following basic bound, valid for all z 1 , z 2 ∈ C:

|e z 1 -e z 2 | ≤ |z 1 -z 2 |e max{Re(z 1 ),Re(z 2 )} ,
which yields e -sτ ( ) (γ i z) -e -s 0 τ ( )

(γ i z) ≤ M |s -s 0 |e M max{|s 0 |,|s|} .
Using unitarity of the representation ρ 0 n and triangle inequality leads to the very crude bound

i→j, |i|= e -sτ ( ) (γ i z) -e -s 0 τ ( ) (γ i z) ρ 0 n (γ -1 i )f (γ i z) V 0 n ≤ M |s-s 0 |e M max{|s 0 |,|s|} #W sup i→j sup z∈D j f (γ i z) V 0 n , which then gives L s,ρ 0 n (f )-L s 0 ,ρ 0 n (f ) 2 ≤ m(D) (M |s -s 0 |) 2 e 2 M max{|s 0 |,|s|} (#W ) 2 sup i→j sup z∈D j f (γ i z) 2 V 0 n .
By the reproducing property of Bergman's kernel, and since all γ i map uniformly each D j in a compact subset of D, we deduce that there exists a constant C > 0 uniform in such that

sup i→j sup z∈D j f (γ i z) 2 V 0 n ≤ C f 2 H(D,V 0 n ) .
The proof is now done if we use the fact that s, s 0 are in a compact set.

We then define the following operators A i (s) :

H(D, C) → H(D, C) by A i (s)[f ](x) def = 1{x / ∈ D i }e -sτ (γī(x)) f (γī(x)).
(2.9)

Being a composition operator which maps admissible discs D i compactly into D, it is easy to see that each operator A i (s) is trace class on H(D; C). If i = (i 1 , i 2 , . . . , i ) is an admissible word, we can then define the following composition

A(s) i def = A i 1 (s)A i 2 (s) . . . A i (s)[f ] = 1{x / ∈ D i 1 }e -sτ ( ) (γīx) f • γī(x),
where we have set for all admissible word j of length , τ ( ) (γ j z) = τ (γ j 1 ...j z) + τ (γ j 2 ...j z) + . . . + τ (γ j z). It will be useful in the following to have a kernel formula for the action of the adjoint operator A(s) * i . Lemma 2.6. Using the above notations, we have for all f ∈ H(D, C),

A(s) * i [f ](x) = D\D i 1 e -sτ ( ) (γ i z) B D (x, γ i z)f (z)dm(z).
Proof. Using the reproducing kernel property, we have for all f, g ∈ H(D, C),

A(s) i f, g = D 1{z / ∈ D i 1 }e -sτ ( ) (γ i z) D B D (γ i z, w)f (w)dm(w)g(z)dm(z).
We observe that since there exists a compact set K ⊂ D such that for all z / ∈ D i 1 , γī(z) ∈ K, we have (by using the explicit formula for the Bergman kernel) sup z,w∈D

|B D (γīz, w)1{z / ∈ D i 1 }| < ∞.
Therefore we have

D D 1{z / ∈ D i 1 } e -sτ ( ) (γ i z) |B(γ i z, w)f (w)g(z)|dm(z)dm(w) < ∞,
and we can use Fubini's theorem to write

A(s) i f, g = D f (w) D 1{z / ∈ D i 1 }e -sτ ( ) (γ ī z) B D (w, γ i z)g(z)dm(z)dm(w),
where we have used the fact that B D (z, w) = B D (w, z) and the proof is done.

Notice that we have A * i (s) = A i (s), which is a source of non-selfadjointness issues and (besides the obvious infinite dimensional setting) one of the main differences with [BC19], where a symmetry hypothesis is assumed. See § §4.1 for a more detailed discussion of these differences to [BC19].

In this paper, we will have to deal with integral operators acting on H(D, C) (or their vector valued extensions). We need a simple criterion to compute their traces, which is as follows.

Lemma 2.7. Let T K : H(D, C) → H(D, C) be an integral operator whose kernel K (z, w) satisfies the following properties: assume that K ∈C 0 (D × D), and that for all w ∈ D, the map z → K (z, w) is holomorphic and extends to a C 2 function on the boundary ∂D. Then, if T K is trace class, we have the identity Since z → K (z, w) is holomorphic on the unit disc, we know that we have the convergent Taylor expansion

tr(T K ) = D K (z, z)dm(z).
K (z, w) = ∞ p=0 a (w)z ,
where for all 0 < r < 1, we can write Lemma 2.8. Let K be any compact subset of C. There is C = C(K) > 0 such that for any s = r + it ∈ K, all m > 0 and all 2m-tuples of admissible sequences i 1 , . . . , i m , j 1 , . . . , j m , we have

a (w) = 1 2π 2π 0 K (re iθ , w) re iθ - dθ. because z → K (z,
tr A(s) i 1 A(s) * j 1 A(s) i 2 A(s) * j 2 • • • A(s) i m A(s) * j m ≤ C m m k=1 Υ r i k Υ r j k .
Proof. Given an admissible word i, we denote by K i (z, w) the integral kernel of A(s) i which is given by

K i (z, w) = 1{z / ∈ D i 1 }e -sτ (|i|) (γ i z) B D (γ i z, w).
Similarly we will denote by K * i (z, w) the integral kernel of A(s) * i , which is

K * i (z, w) = 1{w / ∈ D i 1 }e -sτ (|i|) (γ i w) B D (z, γ i w).
An important observation is due to the fact that each γī maps D\D i 1 uniformly and compactly into D, one can use the explicit formula for the Bergman kernel to prove that there exists C 0 > 0 such that for all admissible i,

sup z,w∈D 1{z / ∈ D i 1 }B(γ i z, w) ≤ C 0 and sup z,w∈D 1{w / ∈ D i 1 }B(z, γ i w) ≤ C 0 .
Because each kernel K i (z, w), K * j (z, w) is bounded on D × D (by the above observation), we can use Fubini's theorem to compute the kernel of

A(s) i 1 A(s) * j 1 A(s) i 2 A(s) * j 2 • • • A(s) i m A(s) * j m ,
which is given by

K i 1 ,j 1 ,...,i m ,j m (z, w) = D 2m-1 K i 1 (z, w 1 )K * j 1 (w 1, w 2 )K i 2 (w 2 , w 3 ) . . . K * j m (w 2m-1, w)dm(w 1 ) . . . dm(w 2m-1 ).
We can then check that z → K i 1 ,j 1 ,...,i m ,j m (z, w) is holomorphic with an analytic extension to ∂D. Being a product of trace class operators, A(s

) i 1 A(s) * j 1 A(s) i 2 A(s) * j 2 • • • A(s) i m A(s) * j m
is therefore trace class and we can use Lemma 2.7 to obtain (again rearranging the order of integration by Fubini)

tr A(s) i 1 A(s) * j 1 A(s) i 2 A(s) * j 2 • • • A(s) i m A(s) * j m = D 2m K i 1 (w 2m , w 1 )K * j 1 (w 1, w 2 ) . . . K i m (w 2m-2 , w 2m-1 )K * j m (w 2m-1, w 2m )dm(w 1 ) . . . dm(w 2m ).
We now recall that for all z

∈ D \ D i 1 , e -sτ (|i|) (γ i z) = (γ i (z)) s = e s log γ i (z) ,
where log(w) = log |w| + i arg(w) is the principal branch of the complex logarithm on C \ (-∞, 0]. Using (2.6), this leads to the bound for s ∈ K

(γ i (z)) s ≤ e Re(s log γ i (z)) ≤ C 1 (K)Υ Re(s) i ,
where C 1 (K) > 0. Using the mirror estimate (2.5), we end up with (up to a slight change of constant)

(γ i (z)) s ≤ C 2 (K)Υ Re(s) i .
We have therefore if Re(s) = r

tr A(s) i 1 A(s) * j 1 A(s) i 2 A(s) * j 2 • • • A(s) i m A(s) * j m ≤ C 2m 0 (C 2 (K)) 2m (Vol(D)) 2m m k=1 Υ r i k Υ r j k ,
which concludes the proof.

3 Random permutations and random graphs

Symmetric random permutations

We write [n] def = {1, . . . , n} and we write S n for the symmetric group of permutations of [n].

We view d ≥ 2 as a fixed integer as in § §2.1. As before, for i

∈ [2d] let ī def = i + d mod 2d so ī ∈ [2d]. We say that a tuple in (S n ) 2d is symmetric if σī = σ -1 i .
To obtain symmetric random permutations we choose σ 1 , . . . , σ d independently and uniformly in S n . (Of course, choosing these plays the same role as in § §2.2 and hence is the same thing as choosing our random cover X φ .)

We let σī = σ -1 i to extend the indices of σ i to [2d] and we write S i for the matrix representing σ i as a 0-1 matrix. We also let

S i def = S i - 1 n 1 ⊗ 1, 14
this is just the matrix of σ i acting in V 0 n .

Graphs and paths

First following [BC19, Def. 6] we define the category of graphs that we work with.

Definition 3.1. A colored edge is an equivalence class of element (x, i, y)

of [n] × [d] × [n]
with respect to the equivalence relation generated by (x, i, y) ∼ (y, ī, x).

(3.1)

A colored graph is a pair consisting of a vertex set V ⊂ [n] and a set of colored edges E as above. It is clear that any colored graph has underlying multigraph obtained by forgetting colors. When we refer to paths, cycles, etc, in colored graphs, they are just paths and cycles in the underlying multigraph.

For symmetric permutations (σ 1 , . . . , σ 2d ) in (S n ) 2d , G σ is the colored graph with vertex set [n] and colored edges given by [x, i, y] such that σ i (x) = y, modulo the equivalence relation on colored edges.

We also introduce a way to talk about paths and the graphs they trace out.

Definition 3.2. The set E is the collection of pairs e = (x, i) with x ∈ [n] and i ∈ [2d]. Each of these be thought of as a half-edge emanating from x and labeled by i. A path of length k is a sequence in E k . For k ∈ N let γ = (γ 1 , . . . , γ k ) ∈ E k be a path, and write each

γ t = (x t , i t ) ∈ [n] × [2d].
• Let V γ = {x t : 1 ≤ t ≤ k} and E γ = {[x t , i t , x t+1 ] : 1 ≤ t ≤ k -1}. We denote by G γ the colored graph with vertex set V γ and colored edges E γ modulo the equivalence relation (3.1).

• A path is non-backtracking if for each 1 ≤ t ≤ k -1 as above, i t = īt+1 . We write Γ k for the subset of of non-backtracking paths in E k . For e, f ∈ E we write Γ k ef ⊂ Γ k for the non-backtracking paths with γ 1 = e, γ k = f . Remark 3.3. Note that in Definition 3.2 the paths, etc have nothing a priori to do with G σ . Rather, their role is as objects that could potentially appear in G σ . Definition 3.4. Given a non-backtracking path γ = ((x 1 , i 1 ), . . . , (x k , i k )) ∈ Γ k , the color sequence of the path is i(γ) def = (i 1 , . . . , i k ).

Tangles

One important notion in the works of Bordenave-Collins [BC19], originating in Friedman [Fri08], is tangles. These relate to events of small probability that make large, argumentdestroying, contributions to the expected value of traces. The following definition is [BC19, Def. 19] Definition 3.5. Let H be a colored graph. H is tangle-free if it contains at most one cycle.

For any vertex x of H, let (H, x) denote the subgraph of H containing all colored edges and vertices that belong to a path of length at most beginning at x. H is -tangle-free if for any vertex x, (H, x) is tangle-free, and H is -tangled otherwise. We say that a path γ ∈ E k is tangle-free if G γ is tangle-free. We write F k (resp. F k ef ) for the collection of tangle-free non-backtracking paths in Γ k (resp. Γ k ef ).

The following lemma appearing in [BC19, Lemma 23] gives the probability that G σ is -tangled when (σ i ) are symmetric random permutations in (S n ) 2d . Lemma 3.6. There is a constant c > 0 such that for (σ i ) symmetric random permutations in (S n ) 2d and 1 ≤ ≤ √ n, the probability that G σ is -tangled is at most

c 3 (2d -1) 4 n .
4 Non-backtracking operator and path decomposition

Conjugation between transfer operator and non-backtracking operator

The purpose of this section is to show how the transfer operator, after a unitary conjugation, is roughly of the form as the non-backtracking operator of [BC19]. This conjugation is not essential for the argument and merely makes it easier to read the current work alongside [BC19].

Recall from § §2.3 that our transfer operator

L s,ρn [f ](x) def = i∈A e -sτ (γ i (x)) ρ n (γ i ) -1 f (γ i (x))
acts on H(D, V n ) and the restriction of this operator to H(D, V 0 n ) coincides with L s,ρ 0 n ; we aim to prove for certain values of s that L s,ρ 0 n has no eigenvalue 1 (cf. Proposition 2.2). Let

K 0 def = H(D) ⊗ V 0 n ⊂ H(D) ⊗ 2 ([n]).
We let S i denote the 0-1 matrix of σ i = φ(γ i ) as in § §2.2 (recall also that ρ n and φ are coupled). For each element e = (x, i) ∈ E we consider the subspace

H e def = H(Dī) ⊗ Cx ⊂ H(D) ⊗ 2 ([n]).
(The reason ī appears here is to make things line up with Bordenave-Collins machinery). In 2 ([n]), we write y for the indicator function of y (this corresponds to identification of 2 ([n])

with formal complex linear combinations of [n]). This gives

H(D) ⊗ 2 ([n]) = e∈E H e .
Write • our H(D) is the analog of C r ⊗ 2 ([2d]), however, H(D) does not split as a tensor product in this way.

• Also, our A j (s) is slightly more general (in the Bordenave-Collins setting, it is equivalent to considering a j ∈ End(C r ⊗ 2 ([2d])) rather than a j ∈ End(C r )).

• each A j (s) acts on a infinite dimensional Hilbert space H(D).

• most critically, the symmetry condition A i = A * ī that Bordenave-Collins assume does not hold here.

These differences, and especially the lack of the symmetry condition, have to be worked around in the sequel. Proof. First of all, by the obvious identification

H(D, V n ) ∼ = H(D) ⊗ 2 ([n]) the operator L s,ρn is conjugated to b(s) ∈ End(H(D) ⊗ 2 ([n])), b(s) def = i A i (s) ⊗ σ i .
Consider the unitary operator Q ∈ End(H(D) ⊗ 2 ([n])) defined for e = (x, i) and f = (y, j) by

Q ef def = p e Id H(Dj ) ⊗ σ -1 j p f . Then for F ⊗ y ∈ H f , f = (y, j), F ∈ H(Dj), using A i (s)F = 0 unless i = j we obtain [Q -1 b(s)Q] ef [F ⊗ y] = p e Qb(s)[F ⊗ σ -1 j (y)] = p e Q[(A j (s)F ) ⊗ y] = p e A j (s)F ⊗ σ -1 i (y) = 1{i = j}1{σ i (x) = y}p e (A j (s)F ⊗ x) = B(s) ef [F ⊗ y] proving that Q -1 b(s)Q = B(s).
It is also not hard to see that B(s) leaves K 0 invariant and Q also conjugates the restriction B(s)| K 0 to L s,ρ 0 n . Finally, noting that the conjugation between L s,ρn and B(s) does not depend on s completes the proof.

Bordenave's path decomposition

Here we perform a path decomposition method that originates in work of Bordenave [Bor]. Recall from Definition 3.5 that F +1 is the collection of tangle-free paths in Γ +1 . For 1 ≤ k ≤ we write F +1 k for the collection of paths γ in Γ +1 such that the first k half-edges of γ (in Γ k ) form a tangle-free path and the last -k + 1 half-edges (in Γ -k+1 ) also form a tangle-free path.

Recall the definition of i(γ) from Definition 3.4 and the notation î = (i 2 , . . . , i n ) from § §2.1. As in [BC19, pg. 834] we obtain with e = (x, i) and f = (y, j)

B(s) ef = p e    γ∈Γ +1 ef (A(s) î(γ) ⊗ E xy ) t=1 (S it ) xtx t+1    p f (4.2)
For ∈ N we define as in [BC19, (32), (34)]

B(s) ( ) def = γ=((x 1 ,i 1 ),...,(x +1 ,i +1 ))∈F +1 p (x 1 ,i 1 ) [A(s) î(γ) ⊗ E x 1 x +1 ]p (x +1 ,i +1 ) t=1 (S it ) xtx t+1 , R k (s) ( ) def = γ=((x 1 ,i 1 ),...,(x +1 ,i +1 ))∈F +1 k \F +1 p (x 1 ,i 1 ) [A(s) î(γ) ⊗ E x 1 x +1 ]p (x +1 ,i +1 ) k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1 .
Remark 4.2. Since each A(s) i is trace class (see § §2.4), both B(s) ( ) and R k (s) ( ) are trace class operators for any ∈ N.

The following is proved by Bordenave and Collins in the course of proving [BC19, Lemma 20] (see the last display equation before [BC19, Lemma 20]).

Lemma 4.3. Let ≥ 1 be an integer and suppose G σ is -tangle free. Then for all F ∈ K 0 ,

B(s) F = B(s) ( ) - 1 n R k (s) ( ) F. (4.3) Hence B(s) | K 0 ≤ B(s) ( ) + 1 n k=1 R k (s) ( ) .
Proof. It clearly suffices to prove the first statement. This is similar to [BC19, pgs. 836-837] but there are subtle differences so we give the details for completeness. Let e = (x, i) and f = (y, j) in E. Beginning with the expression (4.2) for B(s) ef , on the event that G σ is -tangle free we can write

B(s) ef =p e    γ∈Γ +1 ef (A(s) î(γ) ⊗ E xy ) t=1 (S it ) xtx t+1    p f =p e    γ∈F +1 ef (A(s) î(γ) ⊗ E xy ) t=1 (S it ) xtx t+1    p f (4.4) + 1 n k=1 p e    γ∈F +1 ef (A(s) î(γ) ⊗ E xy ) k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1    p f , (4.5)
where the last equality used

t=1 (S it ) xtx t+1 = t=1 (S it ) xtx t+1 + 1 n k=1 k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1 .
The operator on line (4.4) is B(s)

( )
ef so it suffices to describe the operator on line (4.5). We write

p e    γ∈F +1 ef (A(s) î(γ) ⊗ E xy ) k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1    p f =p e    γ∈F +1 k,ef (A(s) î(γ) ⊗ E xy ) k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1    p f (4.6) -p e    γ∈F +1 k,ef \F +1 ef (A(s) î(γ) ⊗ E xy ) k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1    p e . (4.7)
The terms in line (4.7) give the required contributions to -1 n R k (s) ( ) in (4.3) so it suffices to show that the operator M defined by

M ef def = (4.6) kills every element of K 0 . Let J : H(D) ⊗ 2 ([n]) → H(D) ⊗ 2 ([n]
) denote the operator defined for e = (x, i), f = (y, j)

J ef = 1{i = j}p e [A j (s) ⊗ E xy ]p f (contrast this to (4.1)). Note that if F = F 0 ⊗v ∈ K 0 , with F 0 ∈ H(Dj) and v = (v 1 , . . . , v n ) ∈ V 0 n , y∈[n] v y = 0, then J[F 0 ⊗ v] = e=(x,i) i = j y∈[n] p e [A j (s) ⊗ E xy ]p (y,j) (F 0 ⊗ v) = e=(x,i) i = j y∈[n] v y p e [A j (s) ⊗ E xy ] (F 0 ⊗ y) = e=(x,i) i = j [(A j (s)F 0 ) | Dī ⊗x] y∈[n] v y = 0.
This implies K 0 ⊂ ker J.

Since we still assume G σ is -tangle-free, and hence k-tangle free for all k ∈ [ ], we have

M ef = p e    γ∈F +1 k,ef (A(s) î(γ) ⊗ E xy ) k-1 t=1 (S it ) xtx t+1 t=k+1 (S it ) xtx t+1    p f = ( M JB(s) -k ) ef
for some operator M . Since B(s) preserves K 0 , this implies K 0 is in the kernel of M as required.

Lemma 4.3 tells us that bounds on both B(s) ( ) and R k (s) ( ) that hold with high probability can be coupled with the fact that G σ is -tangle-free with high-probability (for in a suitable range) to establish bounds for B(s) | K 0 that hold with high probability. A high probability bound for B(s) ( ) is the subject of § §5.1 and high probability bounds for R k (s) ( ) are the subject of § §5.2.

5 High trace method 5.1 Norm of B(s) ( ) The main result of this §5.1 is the following.

Proposition 5.1. Let K be a compact subset of {s : Re(s) > δ 2 }. There is c = c(K) > 1, ρ = ρ(K) < 1 such that for all s ∈ K, for all 1 ≤ ≤ log n the event

B(s) ( ) ≤ (log n) 20 ρ holds with probability at least 1 -c exp -log n c log log n .
Here we follow the structure of [BC19, § § §4.4.1] up to Proposition 5.6, when we make our departure. The method used here to bound B(s) ( ) is the 'high-trace' method originating in work of Füredi and Komlós [START_REF] Füredi | The eigenvalues of random symmetric matrices[END_REF].

For , m ∈ N we let W ,m denote the set of

γ = (γ 1 , . . . , γ 2m ) ∈ (F +1 ) 2m
such that for j = 1, . . . , m, the first half-edge (i.e. γ 2j,1 = (x 2j,1 , i 2j,1 )) of γ 2j is the same as the first half-edge of γ 2j+1 , and the last half-edge of γ 2j-1 is the same as the last half-edge of γ 2j . Here we let γ 2m+1 def = γ 1 . Following [BC19, (36)] we get

B(s) ( ) 2m ≤tr B(s) ( ) (B(s) ( ) ) * m = γ=(γ 1 ,...,γ 2m )∈W ,m γ j =((x j,1 ,i j,1 ),...,(x j, +1 ,i j, +1 )) tr A(s) î(γ 1 ) A(s) * î(γ 2 ) • • • A(s) î(γ 2m-1 ) A(s) * î(γ 2m ) • 2m j=1 t=1
(S i j,t ) x j,t x j,t+1 .

Here we used that all A(s) î and indeed also B(s) ( ) are trace class operators (cf. Remark 4.2).

Therefore

E[ B(s) ( ) 2m ] ≤ γ=(γ 1 ,...,γ 2m )∈W ,m γ j =((x j,1 ,i j,1 ),...,(x j, +1 ,i j, +1 )) tr A(s) î(γ 1 ) A(s) * î(γ 2 ) • • • A(s) î(γ 2m-1 ) A(s) * î(γ 2m ) • E   2m j=1 t=1
(S i j,t ) x j,t x j,t+1   .

(5.1)

Both the expectation and the absolute value of the trace in the right hand side of the above inequality will be estimated in terms of topological properties of γ, among other things. Recall that in Definition 3.2 we defined for a path γ ∈ E k a colored graph G γ that is roughly speaking the image of the path γ. Now, for γ = (γ 1 , . . . , γ 2m ) ∈ W ,m we define G γ to be the union of the graphs G γ i . In other words, the vertices of G γ are the elements of [n] visited by γ and the edges are just the ones followed by γ with their corresponding colors. We say that a colored edge of G γ has multiplicity one if it is traversed exactly once by γ (in either direction, so an edge traversed in both directions is not multiplicity one).

Notice that for γ ∈ W ,m , G γ is always connected. We let W ,m (v, e) denote the collection of γ ∈ W ,m such that G γ has v vertices and e edges; by the previous remark W ,m (v, e) is empty unless e -v + 1 ≥ 0.

We say two elements γ and γ of W ,m are isomorphic if γ is obtained from γ by changing the labels (in Lemma 5.4. There is a constant c > 0 such that if 2 m ≤ √ n and γ = (γ 1 , . . . , γ 2m ) ∈ W ,m (v, e),with γ j = ((x j,1 , i j,1 ), . . . , (x j, +1 , i j, +1 )) for j ∈ [2m], with G γ having e 1 edges of multiplicity 1, then

E   2m j=1 t=1 (S i j,t ) x j,t x j,t+1   ≤ c m+rank 1 n e 6 m √ n max(e 1 -4•rank-4m,0)
, where rank = e -v + 1.

Remark 5.5. The quantity E 2m j=1 t=1 (S i j,t ) x j,t x j,t+1 is constant on isomorphism classes in W ,m . Now grouping terms in (5.1) into isomorphism classes and using the previous lemmas (this will be done formally later), the only estimate left is the following one. This is a main point of departure from Bordenave-Collins and replaces [BC19, Lemma 26].

Proposition 5.6. For any compact subset K ⊂ { s : Re(s) > δ 2 }, there is ρ = ρ(K) < 1 such that for all s ∈ K, all m > 0 and γ 0 ∈ W ,m (v, e)

γ isomorphic to γ 0 γ=(γ 1 ,...,γ 2m ) tr A(s) î(γ 1 ) A(s) * î(γ 2 ) • • • A(s) î(γ 2m-1 ) A(s) * î(γ 2m ) ≤ C m+rank+e 1 n v ρ 2 m .
where e 1 is the number of edges of G γ 0 of multiplicity one and rank = e -v + 1.

Proof. Write s = r + it. First, we use Lemma 2.8 to get

γ isomorphic to γ 0 γ=(γ 1 ,...,γ 2m ) tr A(s) î(γ 1 ) A(s) * î(γ 2 ) • • • A(s) î(γ 2m-1 ) A(s) * î(γ 2m ) ≤ C m γ isomorphic to γ 0 γ=(γ 1 ,...,γ 2m ) Υ r î(γ 1 ) Υ r î(γ 2 ) • • • Υ r î(γ 2m ) ≤ C m 1 γ isomorphic to γ 0 γ=(γ 1 ,...,γ 2m ) Υ r i(γ 1 ) Υ r i(γ 2 ) • • • Υ r i(γ 2m )
(5.2)

for some C 1 (K) > 0, where the last inequality used (2.2), Υ i ≥ c(Γ) > 0 for i ∈ [2d], and (2.4) to deduce

Υ î ≤ c -1 Υ îΥ i 1 ≤ c -1 KΥ i ≤ c -1 KΥ i .
Here we view γ 0 as fixed; let γ 0 = (γ 0 1 , . . . , γ 0 2m ), γ 0 j = ((x 0 j,1 , i 0 j,1 ), . . . , (x 0 j, +1 , i 0 j, +1 )).

We build a graph G as follows. Let Ṽ denote the vertices of G γ 0 that are either of degree ≥ 3 or of the form x 0 j,1 or x 0 j, +1 for j ∈ [2m]. Now, every vertex of G γ 0 that is not in Ṽ has degree 2 and for each of these vertices, we remove it by merging the two adjacent edges into one edge; this can be done sequentially. The resulting graph on Ṽ is called G and has edge set that we call Ẽ. Every edge of Ẽ is labeled by a sequence of edges of G γ 0 . We write e for the number of vertices of G and v for the number of vertices. Recall that rank (5.4)

Choosing γ isomorphic to γ 0 amounts to the following choices:

• Choosing distinct numbers in n for the vertices of G γ 0 , and, independently,

• Choosing 'allowable' labels in [2d] for the edges of E γ 0 .

There are clearly (n

)(n -1) • • • (n -v + 1) ≤ n v
of the first kind of choice. We will later incorporate this into our final estimate. Now we count the second kind of choice.

The reason for manipulating (5.2) into its current form is that the sequences i(γ 1 ) , i(γ 2 ) , . . . , i(γ 2m ) (5.5) appearing therein are exactly the sequence of edge colors read by walking in G γ according to the respective γ j . Note that by assumption, the underlying graph of G γ (forgetting edge colors) is the same as that of G γ 0 and hence has underlying topological graph G. For each edge of G, the number of times it is covered by γ is the number of times γ traverses it in either direction. (Note that γ and γ 0 cover each edge of G the same number of times, and in the same orders and directions.) We now partition separately each i(γ j ) in (5.2) into subsequences of three5 mutually exclusive types: 0) a subsequence that arises from γ traversing an edge of G that is only ever covered once by γ 0 and hence also γ.

1) a subsequence that arises from γ traversing an edge of G for the first or second time (in any direction) that is covered at least two times by γ 0 and hence also γ.

2) a subsequence that arises from γ traversing a sequence of edges of G where each edge is traversed for at least the third time (in either direction).

(Here subsequences are repeated according to their multiplicity.) There are at most 2e subsequences of type 0 or type 1 and hence also at most 2e + 4m subsequences of type 2 and at most 4e + 4m subsequences in total. We use the multiplicative estimate (2.4) for Υ to obtain

Υ r i(γ 1 ) Υ r i(γ 2 ) • • • Υ r i(γ 2m ) ≤ K (8e +8m)r   type 0 u Υ r u     type 1 u Υ r u     type 2 u Υ r u   . (5.6)
We deal with these factors in turn. Write {U i } for the type 0 subsequences of γ. Their total length is clearly e 1 and there are at most e of them.

The subsequences of type 1 come in pairs u, v of the form either

u = v, or u = v.
In either case the contribution of this pair to type 1 u Υ r u , by the mirror estimate (2.5), is

≤ K r Υ 2r u .
Let {u i } denote a collection of representative subsequences of type 1, one for each pair of type 1. The total number of these pairs is ≤ e . The total length of the u i is e -e 1 . Therefore

type 1 u Υ r u ≤ i K r Υ 2r u i = K e r i Υ 2r u i .
(5.7)

Finally we deal with the type 2 subsequences. Recalling that there are at most 2e + 4m of these and their total length is 2( m -e) + e 1 as in [BC19, (44)], by using (2.7) we obtain

type 2 u Υ r u ≤ type 2 u K r D -r|u| ≤ K r(2e +4m) D -r
(2( m-e)+e 1 ) .

(5.8) Now, to choose γ isomorphic to γ 0 , we need to choose the vertex labels in [n] (of which there are ≤ n v choices) and then

• Choose the sequence of edge colors in each type 0 subsequence U i • Choose the sequence of edge colors in each type 1 subsequence u i • (This completes the choice of γ because type 2 subsequences are determined by the previous choices.)

Now combining (5.2), (5.5), (5.6), (5.7), (5.8) we obtain

γ isomorphic to γ 0 γ=(γ 1 ,...,γ 2m ) tr A(s) i(γ 1 ) A(s) * i(γ 2 ) • • • A(s) i(γ 2m-1 ) A(s) * i(γ 2m ) ≤ n v C m 1 K (11e +12m)r D -r(2( m-e)+e 1 ) i Υ r U i i Υ 2r u i .
(5.9) Now using the bound in terms of the pressure from Lemma 2.4 we obtain that (5.9)

≤ n v C m 1 K (11e +12m)r D -r(2( m-e)+e 1 ) C 2e i exp(|U i |P (r 1 )) i exp(|u i |P (2r 1 )) = n v C m 1 K ( 11e
+12m)r D -r(2( m-e)+e 1 ) C 2e exp(e 1 P (r 1 )) exp((e -e 1 )P (2r 1 ))

where

r 1 def = min{ Re(s) : s ∈ K } > δ 2 .
We conclude by using (5.3) and (5.4) to obtain for some consolidated constant c > 1 depending on all parameters (5.9) ≤ c m+rank+e 1 n v D -r 1 2( m-v) exp(vP (2r 1 )).

The key point here is that P (2r 1 ) < 0. If v ≤ m 2 we get the stated result with ρ = D -r 1 2 . Otherwise v > m 2 and we get the result with ρ = exp P (2r 1 ) 4 < 1. In any case we get the result with ρ < 1 equal to the maximum of these two values. This concludes the proof.

Proof of Proposition 5.1. Given Lemmas 5.2 and 5.4 and Proposition 5.6 the proof is very similar to [BC19, proof of Prop. 24] but we give the details here for completeness.

For n ≥ 3 let m = log n 13 log log n .

We partition all possible isomorphism classes of paths γ 0 in W ,m according to the number v of vertices and number e of edges of G γ 0 and also the number e 1 of edges of G γ 0 that are multiplicity one. We write rank If alternatively e 1 -4 • rank -4m ≥ 0 then by (5.10) we get

(5.11) ≤ n(cC 5 ) m+rank 1 n rank 6C m √ n e 1 -4•rank-4m ρ 2 m ≤ n(cC 5 ) m+rank 1 n rank 6C m √ n 2e-2 m-4•rank-4m ρ 2 m = n(cC 5 ) m+rank 1 n rank 6C m √ n 2v-2( +2)m-2•rank ρ 2 m .
In any case we get that the contribution to (5.1) from a single isomorphism class is

≤ n(cC 5 ) m+rank 1 n rank 6C m √ n max(2v-2( +2)m-2•rank,0)
ρ 2 m . Now, using Lemma 5.2 and summing over v and rank we get

E[ B(s) ( ) 2m ] ≤nρ 2 m ∞ v=1 ∞ rank=0 (4d m) 6m•rank+10m (cC 5 ) m+rank 1 n rank 6C m √ n max(2v-2( +2)m-2•rank,0)
. Now a series of elementary bounds involving geometric series that can be found in [BC19, proof of Prop. 24] leads to

E[ B(s) ( ) 2m ] ≤ nρ 2 m (c m) 10m
for some new constant c = c (K) > 0. Let ρ > ρ be a value in (ρ, 1). Applying Markov's inequality now gives

Prob[ B(s) ( ) ≥ (log n) 20 (ρ ) ] ≤ n(c m) 10m (log n) 40m ρ ρ 2 m ≤ n(c log n) 20m (log n) 40m ρ ρ 2 m ≤ C ρ ρ 2 m
as required.

5.2 Norm of R k (s) ( ) Proposition 5.7. Let K be a compact subset of {s : Re(s) > δ 2 }. There is c = c(K) > 0 and ρ 1 = ρ 1 (K) > 1 such that for any s ∈ K, for all 1 ≤ k ≤ ≤ log n the event R k (s) ( ) ≤ (log n) 40 ρ 1 holds with probability at least 1 -c exp -log n c log log n .

First we follow [BC19, § § §4.4.2] and define 6 Ŵ ,m,k to be the set of γ = (γ 1 , . . . , γ 2m ) satisfying the same conditions as the elements of W ,m except here, each γ i is required to be in F +1 k \F +1 , recalling the definition of F +1 k and F +1 from Definition 3.5.

6 Here there is a typo in [BC19]; we checked with the authors that they meant to define Ŵ ,m,k (which Bordenave-Collins call Ŵ ,m ) using F +1 k \F +1 (not F +1 k as written there).

We then obtain as in [BC19, pg 851] R k (s) ( ) 2m ≤tr R k (s) ( ) (R k (s) ( ) ) * m = γ=(γ 1 ,...,γ 2m )∈ Ŵ ,m,k γ j =((x j,1 ,i j,1 ),...,(x j, +1 ,i j, +1 )) tr A(s) î(γ 1 ) A(s) * î(γ 2 ) • • • A(s) î(γ 2m-1 ) A(s) * î(γ 2m )

• 2m j=1 k-1 t=1 (S i j,t ) x j,t x j,t+1 t=k+1 (S i j,t ) x j,t x j,t+1 .

(5.12)

Isomorphism classes of elements of Ŵ ,m,k are defined the same way as for isomorphism classes in W ,m .

For γ ∈ Ŵ ,m,k we define Ĝγ to be the following graph. If we write γ = (γ 1 , . . . , γ 2m ), γ j = ((x j,1 , i j,1 ), . . . , (x j, +1 , i j, +1 ))

then the vertex set of Ĝγ is defined to be the set of all x j,t with j ∈ [2m], t ∈ [ + 1] and the colored edges {[x j,t , i j,t , x j,t+1 ] :

1 ≤ t ≤ k -1, k + 1 ≤ t ≤ }
modulo the equivalence relation (3.1). Notice this is a sub-colored-graph of G γ with restriction on the edges corresponding to the matrix product in (5.12). For γ ∈ Ŵ ,m,k it is possible for Ĝγ to be disconnected but, as in [BC19, (53)], Ĝγ cannot have more vertices than edges; this is actually the purpose of ensuring each γ i is tangled. We have from [BC19, Lemma 29] the following result. where as before, rank def = e -v + 1 ≥ 1 if Ŵ ,m,k is non-empty.

We also have the following results from [BC19, pg. 853], the first of which is trivial.

Lemma 5.9. The number of elements of any isomorphism class in Ŵ ,m,k (v, e) is at most

n v d e .
Lemma 5.10. There is a constant c > 0 such that if 2 m ≤ √ n and γ = (γ 1 , . . . , γ 2m ) ∈ Ŵ ,m,k (v, e),with γ j = ((x j,1 , i j,1 ), . . . , (x j, +1 , i j, +1 )) for j ∈ Taking the expected value of (5.12), and using Lemma 2.8 and the fact that Υ i ≤ C for any i we obtain for C = C(Λ) > 0

E R k (s) ( ) 2m
≤C m γ=(γ 1 ,...,γ 2m )∈ Ŵ ,m,k γ j =((x j,1 ,i j,1 ),...,(x j, +1 ,i j, +1 ))

E   2m j=1 k-1 t=1
(S i j,t ) x j,t x j,t+1 t=k+1 (S i j,t ) x j,t x j,t+1   . Now noting that the product of matrix coefficients above is constant on isomorphism classes in Ŵ ,m,k (v, e), and using Lemmas 5.8, 5.9, and 5.10, we obtain for all s i ∈ N n . Now by Lemma 2.5 there is a constant C 0 = C 0 (K) > 0 such that for all s ∈ K, if s i is a point in N n for distance ≤ n -α from s then L s,ρ 0 n -L s 0 ,ρ 0 n ≤ |s -s 0 |C 0 ≤ n -α C 0 ≤ n (β log C 0 -α) < n -α 2 (6.4) by our choice of α in (6.2). Combining (6.3) and (6.4) we obtain that with probability tending to one as n → ∞, for all s ∈ K L s,ρ 0 n < 1.

E R k (s) ( ) 2m ≤ cC m
This immediately implies that L s,ρ 0 n does not have 1 as an eigenvalue, and hence by Proposition 2.2 there are no new resonances of the random cover X φ in K.

  Proof. It is enough to work in the unit disc D to simplify. Let (e p ) {p∈N} be the Hilbert basis of H(D, C) given explicitly by e p (z) = p + 1 π z p . Because T K is assumed to be trace class, we have tr(T K ) = ∞ p=0 T K e p , e p = p D D K (z, w)e p (w)dm(w)e p (z)dm(z), which by Fubini can be rewritten as tr(T K ) = p D D K (z, w)e p (z)dm(z)e p (w)dm(w).

KK

  w) is actually continuous up to the boundary we can write a ((e iθ , w) e iθdθ, and use the C 2 regularity to integrate by parts two times which yields uniformly for all w ∈ D, |a (w)| = O -2 . We now notice that D K (z, w)e p (z)dm(z) = a p (w) π p + 1 , which shows that uniformly for all w ∈ D, D K (z, w)e p (z)dm(z) |e p (w)| = O p -2 , and the series p D K (z, w)e p (z)dm(z)e p (w) are therefore uniformly convergent (with limit K (w, w)) on D, which allows to write tr(T K ) = (z, w)e p (z)dm(z)e p (w)   dm(w) = D K (w, w)dm(w), and the proof is done.

Proposition 4. 1 .

 1 There is a unitary operator U : H(D, V n ) → H(D) ⊗ 2 ([n]) such that 1. U conjugates the holomorphic family of trace class operators L s,ρn to the family of operators B(s). 2. U conjugates the holomorphic family of trace class operators L s,ρ 0 n to the family of operators B(s)| K 0 . As such, B(s) and B(s)| K 0 are holomorphic families of trace class operators and L s,ρ 0 n = B(s) | K 0 for all s ∈ C and ∈ N.

  [n]) of the vertices of G γ and changing the colors (in [2d]) assigned to edges in G γ ; these changes to G γ clearly induce a well-defined change of γ. The reader can see [BC19, pp. 841-842] for a more formal definition. Bordenave-Collins prove, by associating to each isomorphism class in W ,m a canonical element, and cleverly counting these canonial elements, the following result [BC19, Lemma 25]. Lemma 5.2. The number of isomorphism classes in W ,m (v, e) is ≤ (4d m) 6m•rank+10m where 4 rank def = e -v + 1. Remark 5.3. It is in this lemma that the tangle-free hypothesis is crucially used. Bordenave-Collins also prove the following random matrix result in [BC19, Lemma 27].

  def = e -v + 1. The following (in)equalities appear in [BC19, proof of Lemma 26] and are either obvious or not hard to check directly: e = v + rank -1, (5.3) e = v + rank -1, e ≤ 3 • rank + 4m -3.

  def = e -v + 1. We have the inequalities 2(e -m) ≤ e 1 ≤ e (5.10) by [BC19, Lemma 27] and can assume e -v + 1 ≥ 0 (or else W ,m (v, e) is empty). The contribution to (5.1) from a given isomorphism class with parameters v, e, e 1 is ≤ n(cC) m+rank 1 n rank 6 m √ n max(e 1 -4•rank-4m,0) C e 1 ρ 2 m (5.11) by Lemma 5.4 and Proposition 5.6. If e 1 -4 • rank -4m ≤ 0 then C e 1 ≤ (C 4 ) rank+m and therefore (5.11) ≤ n(cC 5 ) m+rank 1 n

Lemma 5. 8 .

 8 Let Ŵ ,m,k (v, e) denote the elements of Ŵ ,m,k such that Ĝγ has v vertices and e edges. The number of isomorphism classes in Ŵ ,m,k (v, e) is ≤ (2d m) 12m•rank+20m

(.

  S i j,t ) x j,t x j,t+1 t=k+1 (S i j,t ) x j,t x j,t+1   ≤ c 9 n e Proof of Proposition 5.7. Suppose n ≥ 3 and define m = log n 25 log log n .

.≤.

  The inner geometric series is convergent by our constraint on , m so we obtainE R k (s) ( ) 2m ≤ (C d m) (C d m) 32m (9d) 2 m . Using Markov's inequality yields Prob[ R k (s) ( ) ≥ (log n) 40 (10d) ] ≤ (C d m) 32m (log n)This directly implies the result.

•

  One replaces 2 √d -1 by the spectral radius of the adjacency operator on the universal cover of the graph, and• One allow eigenvalues of the adjacency operator that already belonged to the base graph (as one must).Friedman's conjecture was proved in a breakthrough work of Bordenave and Collins [BC19].In fact Bordenave-Collins proved a vast generalization of Friedman's conjecture where one twists a random Hecke operator, formed from random permutations, by arbitrary fixed finite dimensional matrices, assuming the matrices satisfy a symmetry condition that forces the resulting operator to be self-adjoint. The work of Bordenave-Collins is a vital ingredient of the current work.

  p e for the orthogonal projection onto H e . For any endomorphism M of H(D) ⊗ 2 ([n]) and for each e, f ∈ E we write M ef def = p e M p f .

	Clearly M is determined by the values M ef . Let E xy : 2 ([n]) → 2 ([n]) be the map with
		(E xy )(y ) = δ yy x
	and δ yy is the Kronecker delta.
	Recall the definition of operators A j (s) from (2.9). For e = (x, i) and f = (y, j) we define
	B(s) ef	def = 1{i = j}(S i ) xy p e [A j (s) ⊗ E xy ]p f ;	(4.1)

this defines B(s) ∈ End H(D) ⊗ 2 ([n]) . The operator B(s) is in a similar form to the operator B defined by Bordenave and Collins in [BC19, (

12

)] (cf. also the display equation following [BC19, (12)]). However our B(s) and Bordenave-Collins' B differ in the following ways:

In this case X is either a pair of pants with three funnels or a torus with one funnel.

In graph-theoretic literature, these are called n-lifts.

Convexity follows obviously from the variational formula above.

We choose to use rank rather than what Bordenave-Collins call χ, because of potential confusion with Euler characteristic.

In Bordenave-Collins type 0 and type 1 are considered as one type but here it is useful to separate these out.

Acknowledgments

We thank Charles Bordenave, Benoît Collins, and Doron Puder for helpful conversations related to this work.

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 949143).

Proof of Theorem 1.1

It is sufficient to prove Theorem 1.1 when K is a rectangle in { s : Re(s) > δ 2 } (by covering K with finitely many rectangles). So suppose K is such a rectangle. Let ρ and ρ 1 be the constants provided by Propositions 5.1 and 5.7 for this K. Let C 0 be the constant provided by Lemma 2.5 for this K.

We let

A δ-net of K is a finite subset of K such that any point of K is within Euclidean distance δ of some point of the δ-net. Now it is easy to see that for each n we can choose an n -α -net

for some C = C(K, α) > 0. We want all the following events to hold simultaneously for = β log n .

A G σ is -tangle-free. B B(s i ) ( ) ≤ (log n) 20 ρ for ρ < 1 as in Proposition 5.1 for all s i ∈ N n .

C R k (s i ) ( ) ≤ (log n) 40 ρ 1 for ρ 1 > 0 as in Proposition 5.2 for all s i ∈ N n and all 1 ≤ k ≤ .

By Lemma 3.6 and Propositions 5.1 and 5.2, these events all hold with probability at least

for some c > 0. The last term above tends to zero for any fixed α, β and the second term tends to zero by our choice of β in (6.1). So with probability tending to one as n → ∞, all three families A, B, C of events above hold. Now, if A, B, C hold then by Lemma 4.3

for all s i ∈ N n , where the last inequality used (6.1). Therefore by Proposition 4.1 we have