Frédéric Naud
email: frederic.naud@imj-prg.fr

RANDOM COVERS OF COMPACT SURFACES AND SMOOTH LINEAR SPECTRAL STATISTICS BY FR ÉD ÉRIC NAUD

This paper is dedicated to the memory of Steve Zelditch, pioneer global analyst who introduced quantum ergodicity into the realm of pure mathematics.

Introduction and main results

It is a long standing conjecture that the fine spectral statistics of classically chaotic quantum systems should follow, in the semi-classical regime, a universal behavior related to random matrices. In particular, Berry gave some theoretical evidence [START_REF] Berry | Fluctuations in numbers of energy levels[END_REF][START_REF] Berry | Semiclassical mechanics of regular and irregular motion[END_REF] that time reversible systems, in a well chosen spectral window, should follow the spectral statistics of the Gaussian orthogonal ensemble (GOE), while non-reversible systems should follow the statistics of the Gaussian unitary ensemble (GUE). In the mathematical litterature, there are almost no rigourous results known, except the negative answer to Berry's conjecture in the case of arithmetic surfaces by Luo and 1 Sarnak [START_REF] Luo | Number variance for arithmetic hyperbolic surfaces[END_REF] and the recent preprint of Rudnick [START_REF] Rudnick | Spectral statistics on the moduli space of surfaces of large genus[END_REF]. Rudnick's approach builds on the Weil-Petersson model of random hyperbolic surfaces and the celebrated integration formulas of Mirzakhani [START_REF] Mirzakhani | Simple geodesics and Weil-Petersson volumes of moduli spaces of bordered Riemann surfaces[END_REF] and most importantly Mirzhakani-Petri [START_REF] Mirzakhani | Lengths of closed geodesics on random surfaces of large genus[END_REF]. In this paper, instead of averages over the whole moduli space, we will perform averages over the finite space of covers of degee n and use the notion of random covers of compact hyperbolic surfaces defined by Magee, Puder and the author to study spectral gaps in [START_REF] Magee | The asymptotic statistics of random covering surfaces[END_REF][START_REF] Magee | A random cover of a compact hyperbolic surface has relative spectral gap 3 16[END_REF].

Let H denote the hyperbolic plane endowed with its metric of constant curvature -1, and let Γ ⊂ PSL 2 (R) be a co-compact Fuchsian group so that X = Γ\H is a compact hyperbolic surface. Let φ n : Γ → S n be a group homomorphism, where S n is the symmetric group of permutations of [n] := {1, . . . , n}. The discrete group Γ acts on H × [n] by γ.(z, j) := (γ(z), φ n (γ)(j)).

The resulting quotient X n := Γ\H × [n] is then a finite cover of degree n of X, possibly not connected. By considering the (finite) space of all homomorphism φ n : Γ → S n , endowed with the uniform probability measure, we obtain a notion of Random covering surfaces of degree n, X n → X. The expectation of any random variable Y with respect to this uniform measure is denoted by E n (Y ). We point out that we can also view (up to isometry) the random cover X n as

X n = p k=1 Γ k \H,
where each Γ k is (in general non-normal) subgroup of Γ given by Γ k = Stab Γ (i k ) = {γ ∈ Γ : φ n (γ)(i k ) = i k } where i 1 , . . . , i k ∈ [n] are representatives of the orbits of Γ (acting on [n] via φ n ). In general, the cover X n is not connected, but it follows directly from Liebeck and Shalev [START_REF] Liebeck | Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks[END_REF] that the probability that this cover is connected (i.e. Γ acts transitively on [n] via φ n ) tends to 1 as n goes to infinity.

In order to allow us to observe different statistical behaviors, we also fix a complex unitary representation, globally defined on Γ,

ρ : Γ → GL(V ρ ),
where V ρ is a finite-dimensional complex vector space.

Each surface X n comes with a self-adjoint Laplace operator ∆ n,ρ , the hyperbolic Laplacian on X n twisted by ρ. The spectrum of ∆ n,ρ is denoted (with multiplicity) by

λ j,n = 1 4 + (r j,n ) 2 , j ∈ N ,
where r j,n ∈ R ∪ iR.

Let ψ be a real valued even smooth test function on R whose Fourier transform ψ is compactly supported in R. The Fourier transform is in our case given by

ψ(ξ) = 1 2π +∞ -∞ ψ(x)e -ixξ dx.
Note that ψ is therefore an entire holomorphic function on C. We take α, L > 0 and consider the smooth counting function

N n (L) := ∞ j=0 {ψ(L(r j,n -α)) + ψ(L(r j,n + α))} .
We will fix α (the energy level) and let L -1 (the band width) go to zero and n go to infinity. It is easy to see that for fixed L, we have as n goes to infinity,

E n (N n (L)) ∼ C α (g -1)dim(V ρ )n L R ψ(r)dr,
where g is the genus of the base surface X, and C α = 2α tanh(πα). One of the simplest quantity to investigate is the so-called "number variance" which measures "spectral rigidity". We will therefore focus on the probabilistic variance

V n (L) := E n |N n (L) -E n (N n (L))| 2 .
Our main result is the following.

Theorem 1.1. Fix X = Γ\H and a unitary abelian character ρ : Γ → C as above. We fix an energy level α > 0, then we have the double limit

lim L→∞ lim n→∞ V n (L) = Σ 2 GOE (ψ) if ρ 2 = 1 Σ 2 GUE (ψ) if ρ 2 = 1. The quantity Σ 2 GOE (ψ)
is the "smoothed" number variance of random matrices for the GOE model in the large dimension limit and given by

Σ 2 GOE (ϕ) = 2 R |x|( ψ(x)) 2 dx, while Σ 2 GUE (ψ) = 1 2 Σ 2 GOE (ψ).
This result is in accordance with Berry's conjecture: the hypothesis ρ 2 = 1 corresponds to breaking the time reversal symmetry i.e. the character χ is sensitive to the orientation of closed geodesics. The computation of number variances in the model cases of GUE, GOE goes back to Dyson and Mehta in [START_REF] Dyson | Statistical theory of the energy levels of complex systems[END_REF], see Mehta [START_REF] Madan | Random matrices[END_REF], Appendix A.39 and also chapter 16.

What about higher dimensional twists and Laplacians acting on associated flat vector bundles? We denote by U (N ) the unitary group, SU (N ) the special unitary group, Sp(N ) the compact symplectic group, SO(N ) the special orthogonal group. Note that SU (N ), SO(N ) are Lie subgroups of U (N ) while for the compact symplectic group

Sp(N ) = Sp(2N, C) ∩ U (2N )
is a Lie subgroup of U (2N ). In the text below G will denote a compact connected real Lie subgroup of U (N ) for some N . Notice that by a celebrated theorem of Tannaka, see Chevalley [START_REF] Chevalley | Theory of Lie Groups[END_REF] , this is automatically a real algebraic group. We show the following . Theorem 1.2. Let G be as above, and assume it is not conjugated to a direct product of Lie groups. Fix X = Γ\H and a unitary representation ρ : Γ → G whose image is Zariski dense in G. We fix an energy level α > 0, then we have the double limit

lim L→∞ lim n→∞ V n (L) = Σ 2 GOE (ψ) if g → Tr(g) ∈ R, Σ 2 GUE (ψ) otherwise.
In particular, we have the following behavior for classical compact Lie groups.

• For G = U (N ), or G = SU (N ) with N ≥ 3, we are in the GUE case.

• For G = SO(N ), Sp(N ), we are in the GOE case.

In a nutshell, if the trace map on G is real-valued then we get GOE statistics while if the trace map takes complex values, we have GUE statistics. Representation of surface groups with Zariski dense images in the above cases do exist under some mild dimensional assumptions, see for example in the paper of Kim and Pansu, [START_REF] Kim | Density of Zariski density for surface groups[END_REF] and also Kishore [START_REF] Kishore | Representation variety of surface groups[END_REF]. More details can be found at the end of the paper, §5.

While our results have the same flavor as in [START_REF] Rudnick | Spectral statistics on the moduli space of surfaces of large genus[END_REF], here are the main differences:

• We take finite averages over (increasingly bigger) sets of surfaces. In particular we cannot rely as much on oscillatory integral techniques and integration by parts as in the smooth model of Weil-Petersson. • Our result is at fixed frequency α while Rudnick in [START_REF] Rudnick | Spectral statistics on the moduli space of surfaces of large genus[END_REF] lets both L = O(log α)), α go to ∞ . However, it is not really necessary at the technical level in [START_REF] Rudnick | Spectral statistics on the moduli space of surfaces of large genus[END_REF] to let the energy level α go to infinity in order to observe the universal behaviour for the variance so both result are actually the same. • Our model also allows to study twisted Laplacians and prove the conjectured effect of time reversal symmetry on the spectral statistics. It would be interesting to know to what extent Mirzakhani's formalism needs to be modified to allow unitary twists in the analysis of Rudnick. • If Γ is an arithmetic groups, then all the random covers X n are also arithmetic surfaces. It was shown in [START_REF] Luo | Number variance for arithmetic hyperbolic surfaces[END_REF], see also [START_REF] Bogomolny | Chaotic billiards generated by arithmetic groups[END_REF], that in the semi-classical regime, the number variance exhibits some poissonian behaviour, due to the high multiplicities in lengths of closed geodesics. Our result shows that in the large n regime we still get GOE/GUE statistics despite arithmeticity. The paper is organized as follows. In §2 we explain how the spectrum of ∆ n,ρ can be studied via an n × dim(V ρ )-dimensional unitary twist of the Laplacian on the base surface X, mostly by using the induction formula from representation theory. We then state the ad-hoc Selberg trace formula that we will later use in the proof. In §3 we review the asymptotic statistics (in the large n regime) of the number of fixed points of "random" permutation φ n (γ): when γ is primitive, this random variable behaves essentially like a Poisson variable with parameter 1. When γ 1 = γ 2 are in two different primitive conjugacy class (and are not inverses of each other), the associated number of fixed points of φ n (γ 1 ) and φ n (γ 2 ) are asymptotically independent. This will play a key role in the proof of Theorem 1.1. We point out that a similar behaviour occur in the smooth Weil-Peterssen model where the core argument in [START_REF] Mirzakhani | Lengths of closed geodesics on random surfaces of large genus[END_REF] shows independency and Poissonian behaviour for lengths of simple closed geodesics.

In §4 we provide some asymptotic results for the (weighted) counting function for the closed geodesics on X, which we derive from some standard facts on twisted Laplaclans for unitary representations and the trace formula. Finally, §5 is devoted to the proof of Theorems 1.1 and 1.2 which in turn is broken into several steps.

Acknowledgements. The author wants to thank Michael Magee, Stéphane Nonnenmacher, Doron Puder and Zeev Rudnick for several discussions around this work.

Representations, twisted laplace spectrum and trace formula

Let ρ : Γ → U (V ρ ) be a unitary representation of Γ, with finite dimensional complex representation space V ρ , and inner hermitian product ., . ρ . The twisted Laplacian ∆ ρ is the Laplacian acting on smooth functions

ψ : H → V ρ satisfying the equivariance property ∀ γ ∈ Γ, ψ(γz) = ρ(γ)ψ(z).
We endow this space with an L 2 -norm given by

ψ 2 ρ := F ψ(z) 2 ρ dVol(z),
where F ⊂ H is a compact fundamental domain for Γ and Vol is hyperbolic volume. This Laplacian ∆ ρ has a unique self-adjoint extension with discrete spectrum. Alternatively, one can view ∆ ρ as a self-adjoint Bochner-Laplace operator associated to a metric connection on the flat vector Bundle E ρ → X associated to the representation ρ of the fundamental group Γ. Spectral theory and trace formulas for such Laplacians are well documented in [START_REF] Hejhal | The Selberg trace formula for PSL[END_REF][START_REF] Venkov | Spectral theory of automorphic functions and its applications[END_REF].

We have the following fact.

Proposition 2.1. There exists an n × dim(V ρ )-dimensional complex representation n : Γ → U (V n ) such that the spectrum of ∆ n,ρ on the random surface X n coincides (with same multiplicity) with the spectrum of the twisted Laplacian ∆ n . In addition, we have the character formula for all γ ∈ Γ,

Tr( n (γ)) = Tr(ρ(γ))|Fix(φ n (γ))|,
where Fix(φ n (γ)) denotes the set of fixed points in [n] of the permutation φ n (γ).

Proof. We set d = dim(V ρ ). We recall that we have

X n = p k=1 Γ k \H, where Γ k = Stab Γ (i k ) = {γ ∈ Γ : φ n (γ)(i k ) = i k } where i 1 , . . . , i k ∈ [n]
are representatives of the orbits of Γ (acting on [n] via φ n ). Working on each connected components of X n , it is enough to assume that X n is actually connected, i.e. Γ acts transitively on [n]. Let us set

Γ 1 := Stab Γ (1),
and we write the right cosets decomposition of Γ as

Γ = Γ 1 g 1 ∪ Γ 1 g 2 ∪ . . . ∪ Γ 1 g n ,
where g 1 = Id and we have ordered the cosets such that φ n (g i )(i) = 1 for all i = 1, . . . , n. It is a well known fact (see for example Venkov [START_REF] Venkov | Spectral theory of automorphic functions and its applications[END_REF], page 51) that the Laplacian ∆ ρ on X n = Γ 1 \H is unitarily conjugated to the Laplacian on E n , where n is the induced representation of ρ on Γ 1 to Γ. More precisely, n (γ) acts on V n = C d×n via the block-matrix

Mat C d×n ( n (γ)) = ρ(g i γg -1 j ) 1≤i,j≤n
, where ρ(g) = ρ(g) if g ∈ Γ 1 and ρ(g) = 0 elsewhere. On the diagonal part of this matrix, observe that if

φ n (γ)(i) = i then ρ(g i γg -1 i ) = 0 while ρ(g i γg -1 i ) = ρ(g i γg -1 i ) = ρ(g i )ρ(γ)ρ(g i ) -1 if φ n (γ)(i) = i. Computing traces yields Tr( n (γ)) = i : φn(γ)(i)=i Tr(ρ(g i )ρ(γ)ρ(g i ) -1 ) = Tr(ρ(γ))|Fix(φ n (γ))|,
and the proof is done.

We will use twisted versions of Selberg's trace formula which is as follows, see for example in [START_REF] Hejhal | The Selberg trace formula for PSL[END_REF][START_REF] Venkov | Spectral theory of automorphic functions and its applications[END_REF]. Let : Γ → U (V ) be a general unitary, finite dimensional, representation of Γ. For all eigenvalue λ j ( ) of the Laplacian ∆ , we fix r j (ρ) such that λ j ( ) = 1/4 + (r j ( )) 2 . Let h be an even function whose Fourier transform h is compactly supported and smooth, then we have the celebrated identity:

Theorem 2.2. (Twisted trace formula) ∞ j=0 h(r j ( )) = (g -1)dim(V ) ∞ -∞ h(r)r tanh(πr)dr + γ∈P k≥1 Tr( (γ k )) (γ) h(k (γ)) 2 sinh(k (γ)/2) .
In the above formula, g denotes the genus of the base surface X, P is the set of primitive conjugacy classes in Γ (different from identity) and if γ ∈ P, (γ) denotes the length of the associated closed geodesic on X. The sum over k runs over all positive integers.

Character statistics in the large n regime

In this section we review some key facts on the integer valued random variables |Fix(φ n (γ))|, for γ ∈ Γ and where φ n : Γ → S n is a random homomorphism. To simplify further notations, we will denote simply |Fix(φ n (γ))| by F n (γ). Our analysis will based on the following facts. We recall that P denotes the set of primitive conjugacy classes (different from identity) in Γ. Proposition 3.1. Under the above notations, the following holds.

(1) For all γ ∈ P and k ≥ 1, we have as n goes to ∞,

E n (F n (γ k )) = d(k) + O 1 n ,
where d(k) denotes the number of divisors of k.

(2) For all γ 1 , γ 2 ∈ P such that γ 1 ∈ {γ 2 , γ -1 2 }, for all k 1 , k 2 ≥ 1, we have as n → ∞, E n (F n (γ k 1 1 )F n (γ k 2 2 )) = E n (F n (γ k 1 1 ))E n (F n (γ k 2 2 )) + O 1 n .
(3) For all k 1 , k 2 ≥ 1 and γ ∈ P, the limit

lim n→+∞ E n F n (γ k 1 ) -E n (F n (γ k 1 )) F n (γ k 2 ) -E n (F n (γ k 2 )) := V(k 1 , k 2 ) exists. If k 1 = k 2 = 1 then V(1, 1) = 1. Moreover we have the formula V(k 1 , k 2 ) = d| gcd(k 1 ,k 2 ) d.
Proof. From [START_REF] Puder | Local statistics of random permutations from free products[END_REF][START_REF] Magee | The asymptotic statistics of random covering surfaces[END_REF], see for example in [START_REF] Puder | Local statistics of random permutations from free products[END_REF] Theorem 1.4, we have directly [START_REF] Anantharaman | A high-genus asymptotic expansion of Weil-Petersson volume polynomials[END_REF]. From [START_REF] Puder | Local statistics of random permutations from free products[END_REF], Theorem 1.13, we know that if γ 1 , γ 2 do not belong to the same cyclic subgroup, then the random variables F n (γ 1 ), F n (γ 2 ) are asymptotically independent which implies [START_REF] Berry | Fluctuations in numbers of energy levels[END_REF]. Denote by C n,d (γ) the number of d-cycles of the random permutation φ n (γ), where γ is primitive. As usual Z λ will denote a Poisson variable with parameter λ > 0 whose law is given by

P(Z λ = q) = e -λ λ q q! ,
and satisfies

E(Z λ ) = λ, E(Z 2 λ ) = λ 2 + λ.
We know from [START_REF] Puder | Local statistics of random permutations from free products[END_REF][START_REF] Magee | The asymptotic statistics of random covering surfaces[END_REF], Theorem 1.14 that as n goes to ∞, C n,d (γ) converges in distribution to a Poisson variable Z 1/d . We point out that this result was already known for free groups since Nica [START_REF] Nica | On the number of cycles of given length of a free word in several random permutations[END_REF].

Moreover, if d 1 = d 2 then the variables C n,d 1 (γ), C n,d 2 (γ) are asymptotically independent. Using the formula (for γ primitive)

F n (γ k ) = d|k dC n,d (γ), we get that E n (F n (γ k 1 )F n (γ k 2 )) = d 1 |k 1 d 2 |k 2 d 1 d 2 E n (C n,d 1 (γ)C n,d 2 (γ)).
By the Above facts, if

d 1 = d 2 then lim n→+∞ E n (C n,d 1 (γ)C n,d 2 (γ)) = E(Z 1/d 1 )E(Z 1/d 2 ) = 1 d 1 d 2 .
On the other hand, if

d 1 = d 2 then lim n→+∞ E n (C n,d 1 (γ)C n,d 2 (γ)) = E(Z 2 1/d 1 ) = 1 d 1 + 1 d 2 1
.

Using the fact that

lim n→+∞ E n (F n (γ k )) = d(k) = d|k 1 = d|k d lim n→∞ E n (C n,d (γ)),
we get that

lim n→+∞ E n F n (γ k 1 ) -E n (F n (γ k 1 )) F n (γ k 2 ) -E n (F n (γ k 2 )) = d 1 |k 1 d 2 |k 2 d 1 d 2 lim n→+∞ E n (C n,d 1 (γ)C n,d 2 (γ)) - 1 d 1 d 2 .
Noticing that the above terms vanish for d 1 = d 2 , we are left with

V(k 1 , k 2 ) = d|k 1 and d|k 2 d = d| gcd(k 1 ,k 2 ) d.
and the proof is done.

Bounds on closed geodesics and Chebotarev counting results

We will use throughout this paper the following standard summation by parts formula: this is standard in any introductory class in analytic number theory.

Proposition 4.1. Let 0 < 0 < 1 < . . . < n be an increasing sequence of positive real numbers with lim n→∞ n = +∞, and let (c n ) n∈N be an arbitrary sequence of complex numbers. Let f : (0, +∞) → C be a C 1 -function. We have for all x ≥ 0,

n≤x c n f ( n ) = A(x)f (x) - x 0 A(t)f (t)dt,
where

A(x) = n≤x c n if x ≥ 0 0 otherwise.
It will be sometimes convenient to use the formal notation

x 0 f (t)dA(t) := n≤x c n f ( n ),
which in the special case when (c n ) is positive, coincides with an actual Stieltjes integral.

4.1. Some counting bounds. Let N (T ) denote the counting function for closed geodesics on X = Γ\X whose length is smaller than T i.e.

N (T ) := k (γ))≤T 1,
where the sum runs over all integers k ≥ 1 and all γ ∈ P. One can also consider the primitive counting function

N 0 (T ) := (γ))≤T 1,
where the sum runs only on primitive conjugacy classes. It has been known since Huber [START_REF] Huber | Zur analytischen Theorie hyperbolischen Raumformen und Bewegungsgruppen[END_REF] that as T → +∞,

N 0 (T ) = e T T (1 + o(1)),
which is commonly referred as "the prime geodesic theorem". We point out that since we have

N (T ) = N 0 (T ) + k≥2 N 0 (T /k),
we actually have as T → +∞,

N (T ) = N 0 (T ) + O(T e T /2 ).
Later [START_REF] Peter | PRIME GEODESIC THEOREMS[END_REF][START_REF] Hejhal | The Selberg trace formula for PSL[END_REF] more precise remainders where proved: for all > 0, we have the following asymptotic formula as T goes to infinity

N (T ) = Li e T + O e α 0 ( )T , (1)
where α 0 ( ) = max{3/4 + , s 1 (X)}, where 0 < s 1 (X) < 1 is related to the first non-trivial eigenvalue of the Laplacian on X by s 1 (1 -s 1 ) = λ 1 (X).

From the fact that Li(x) :=

x 2 dt log t ,
it is immediate to check that as T → +∞,

N 0 (T ) = e T T 1 + O 1 T , (2)
which is sometimes sufficient. Given a unitary representation

ρ : Γ → GL(V ρ ),
we set χ 0 (γ) := Tr(ρ(γ)). We then consider the following counting function

N χ 0 (T ) := k (γ))≤T χ 0 (γ k ).
We will show the following fact.

Proposition 4.2. Assume that ρ does not contain the trivial representation, then there exists β 0 = β 0 (Γ, χ 0 ) < 1 such that as T → +∞,

|N χ 0 (T )| = O e β 0 T .
Proof. The proof follows from standard facts on the spectrum of the twisted Laplacian ∆ ρ and will certainly not surprise the experts. We nevertheless include a concise proof for completeness. Let 0 ≤ λ 0 (ρ) ≤ λ 1 (ρ) ≤ . . . denote the spectrum of ∆ ρ . From the analysis of Phillips-Sarnak [START_REF] Phillips | Geodesics in homology classes[END_REF] in the scalar case or from Sunada [START_REF] Sunada | Unitary representations of fundamental groups and the spectrum of twisted Laplacians[END_REF] in the general vector case, we know that if ρ does not contain the trivial representation, then we have λ 0 (ρ) > 0. To be more precise, it is actually shown in [START_REF] Sunada | Unitary representations of fundamental groups and the spectrum of twisted Laplacians[END_REF] that if A is a finite set of generators of Γ then there exists C(A, Γ) > 0 such that

C(A, Γ)δ A (ρ, 1) 2 ≤ λ 0 (ρ),
where δ A (ρ, 1) is Kazhdan's distance to the trivial representation 1. Kazhdan's distance is defined by

δ A (ρ, 1) = inf v∈Vρ v =1 max γ∈A ρ(γ)v -v .
It is straightworward to check that if δ A (ρ, 1) = 0, then one can find v = 0 ∈ V ρ such that for all γ ∈ Γ, ρ(γ)v = v i.e. ρ contains the trivial representation.

The end of the proof now follows from an application of the trace formula. First observe that we have

N χ 0 (T ) = k (γ))≤T χ 0 (γ k ) = γ∈P (γ)≤T χ 0 (γ) + O T e T /2 ,
just by noticing that by the prime orbit theorem we have

k (γ))≤T k≥2 1 = O T e T /2 .
Therefore it is enough to prove the desired result for

N 0 χ 0 (T ) := (γ))≤T χ 0 (γ).
Let 0 > 0 denote the shortest length of closed geodesics on X. Pick 0 < T 0 < T 0 + T 1 , and let 0 ≤ q(x) ≤ 1 be an even smooth compactly supported function on R such that q(x) = 0 for all x ∈ [-0 /2, + 0 /2] and q(x) = 1 for all 0 ≤ |x| ≤ T 0 while being supported inside {|x| ≤ T 0 + T 1 }.

In the latter we will choose T 1 as a function of T 0 satisfying T 1 = e -αT 0 , for some α > 0, while all the bounds will be relevant for T 0 → +∞. Moreover, it is possible to choose q such that for all k,

sup R |q (k) | ≤ C k T -k 1 .
Consider now the test function

ϕ T 0 ,T 1 (x) := 2 cosh(x/2) |x| q(x),
and set

h T 0 ,T 1 (u) := R e iux ϕ T 0 ,T 1 (x)dx.
Applying the trace formula from Theorem 2.2, a direct bound shows that the finite contribution from the low eigenvalues below 1/4 satisfies

j : r j ∈iR |h T 0 ,T 1 (r j )| = O T 0 e (1/2+s 0 )T 0 ,
where

s 0 = 1/4 -λ 0 if λ 0 ≤ 1/4, 0 otherwise.
Note that since λ 0 > 0, we have s 0 < 1/2. Integrating by parts 3 times yields

h T 0 ,T 1 (u) = O e T 0 /2 T -3 1 1 + |u| 3 ,
which gives by a crude bound

∞ -∞ h T 0 ,T 1 (r)r tanh(πr)dr = O e T 0 /2 T -3 1 .
We recall that by Weyl's law we have the bound #{j :

|r j | ≤ R} = O(R 2 ),
so that a standard summation by parts yields also the crude bound

j : r j ∈R |h T 0 ,T 1 (r j )| = O e T 0 /2 T -3 1 .
We now observe that

γ∈P k≥1 χ 0 (γ k ) (γ)ϕ T 0 ,T 1 (k (γ)) 2 sinh(k (γ)/2) = γ∈P χ 0 (γ)(tanh( (γ)/2)) -1 q( (γ))+O(T 0 e T 0 /2 ).
By the the fact that 1 tanh(x) = 1 + O(e -2x ), we have

γ∈P χ 0 (γ)(tanh( (γ)/2)) -1 q( (γ)) = γ∈P χ 0 (γ)q( (γ))+O γ e -(γ) q( (γ)) ,
and the latter term is easily shown to be O(1) by summation by parts. By the very definition of q we have obtained that

γ∈P k≥1 χ 0 (γ k ) (γ)ϕ T 0 ,T 1 (k (γ)) 2 sinh(k (γ)/2) = N 0 χ 0 (T 0 ) + O(T 0 e T 0 /2 ) + T 0 ≤ (γ)≤T 0 +T 1 χ 0 (γ)q( (γ)).
By the prime orbit theorem with remainder (1),

T 0 ≤ (γ)≤T 0 +T 1 χ 0 (γ)q( (γ)) ≤ O N 0 (T 0 + T 1 ) -N 0 (T 0 ) = O(e T 0 T 1 )+O(e α 0 T 0 ).
Gathering all these estimates, we have thus

N 0 χ 0 (T 0 ) = O(T 0 e T 0 /2 )+O(e T 0 T 1 )+O(e α 0 T 0 )+O e T 0 /2 T -3 1 +O T 0 e (1/2+s 0 )T 0 ,
where α 0 < 1, and s 0 < 1/2. Setting α = 1 8 gives

N 0 χ 0 (T 0 ) = O(T 0 e T 0 /2 ) + O(e α 0 T 0 ) + O T 0 e (1/2+s 0 )T 0 + O e 7 8 T 0 ,
and the proof is done.

Notice that we have not attempted at all to optimize the error term since any exponent β 0 < 1 will be enough for our application. We will now apply this result to prove the following asymptotic formula. where I is the contragredient representation of I, see for example [START_REF] Bump | Lie groups[END_REF] Proposition 2.6. The finite-dimensional representation

I ⊗k ⊗ I ⊗l
can in turn be written as a finite direct sum of irreducible representations of G, hence (Tr(g)) k (Tr(g)) l can be expressed as a finite linear combination of characters Tr(λ(g)), and so does f (g). The uniqueness of Peter-Weyl decomposition then implies that only finitely many coefficients c λ must be non-vanishing, notice in addition that we have

c trivial = G f (g)dg.
We then write

(γ)≤x f (ρ(γ)) = λ∈ G c λ (γ)≤x Tr(λ(ρ(γ))) = G f (g)dg (γ)≤x 1 + λ∈ G λ non trivial c λ (γ)≤x
Tr(λ(ρ(γ))).

Assume now that if λ is irreducible and assume that λ•ρ contains the trivial representation. This means that there exists a non vanishing vector v ∈ V λ such that for all γ ∈ Γ,

λ • ρ(γ)v = v. Denote by Z λ the set Z λ := {g ∈ G : λ(g)v = v}.
Since λ is irreducible, Z λ G and it is a real algebraic subset of G. Indeed all irreducible representations can be included 1 in

I ⊗k ⊗ I ⊗l
for some k, l ∈ N, and thus matrix coefficients are Laurent polynomials in the matrix coefficients of elements of G. This translates (by taking real and imaginary parts) into real algebraic equations. Since ρ(Γ) is assumed to be Zariski dense, we must have ρ(Γ) ∩ Z c λ = ∅, and thus λ • ρ cannot contain the trivial representation. The sum over irreducible λ being finite, we can apply the prime orbit theorem with remainder and Proposition 4.2 to conclude the proof.

We point out that the leading term in the above asymptotic should follow directly from a dynamical result of Parry and Pollicott [START_REF] Parry | The Chebotarov theorem for Galois coverings of Axiom A flows[END_REF], provided that one can check the weak-mixing property of the associated extension of the geodesic flow via the Zariski density assumption. We have chosen here a more self-contained and scenic road which gives a stronger result which might be useful in future applications.

Proof of the main theorem

5.1. An equidistribution result. In core of the proof of the main theorem, we will need to use the following equidistribution result which we state and prove here. Lemma 5.1. Let 0 < 0 < 1 < . . . < n be a sequence such that n → +∞ as n → +∞ and let (a n ) n≥0 be a sequence of positive real numbers. Consider the counting function

Π(x) := n≤x a n ,
1 This is a folklore theorem in the representation theory of compact Lie groups and can be proved in multiple ways see for example the discussion at https://mathoverflow.net/questions/58633/does-every-irreducible-representation-of-acompact-group-occur-in-tensor-product and references given here.

and assume that as x → +∞, we have Π(x) ∼ κ e x x , for some κ > 0. Assume that g : R + → R + is a continuous function such that g(x) = x 2 e x (1 + O(1/x)) as x → +∞. Pick ψ a positive valued, compactly supported C ∞ function on R + . Fix α ∈ R. Then as T → +∞, we have

n a n cos 2 (α n )g( n ) ψ n T ∼ κT 2 2 ∞ 0 u ψ(u)du, if α = 0, while n a n cos 2 (α n )g( n ) ψ n T ∼ κT 2 ∞ 0 u ψ(u)du if α = 0.
Proof. First notice that for some constant C > 0, we have the following bound valid for all x ≥ 0,

Π(x) ≤ C e x x if x ≥ 1 C if 0 ≤ x ≤ 1. Set S T := n a n cos 2 (α n )g( n ) ψ n T .
By the asymptotic behaviour of g, we have as T → ∞,

S T = ∞ 0 cos 2 (αx) x 2 e x ψ x T dΠ(x) + O C 1 T 0 x e x dΠ(x) ,
for some C 1 > 0 which depends on the support of ψ. Using the above bound for Π(x) and a summation by parts we get

C 1 T 0 x e x dΠ(x) = C 1 T 0 e -x (x -1)Π(x)dx = O(T ).
We are left to analyze

S 0 T := ∞ 0 cos 2 (αx) x 2 e x ψ x T dΠ(x).
Using the identity

cos 2 (z) = cos(2z) + 1 2 ,
we write S 0 T := S T + S 1 T , where

S T = 1 2 ∞ 0 x 2 e x ψ x T dΠ(x), S 1 T = 1 2 ∞ 0 cos(2αx) x 2 e x ψ x T dΠ(x).
We first deal with S T . A summation by parts yields

S T = 1 2 ∞ 0 e -x (x 2 -2x) ψ x T Π(x)dx - 2 T ∞ 0 x 2 e x ψ x T Π(x)dx.
We then observe that 1

T ∞ 0 x 2 e x ψ x T Π(x)dx = O 1 T ∞ 0 x ψ x T dx = O(T ), while ∞ 0 e -x (x 2 -2x) ψ x T Π(x)dx = ∞ 0 x 2 e -x ψ x T Π(x)dx + O(T ).
Therefore as T → +∞,

S T = 1 2 ∞ 0 x 2 e -x ψ x T Π(x)dx + O(T ).
By a change of variable, we have

∞ 0 x 2 e -x ψ x T Π(x)dx = T 2 ∞ 0 f T (u)du,
where f T (u) = T u 2 e -T u ψ(u)Π(T u). Notice that we have for fixed u ≥ 0, lim

T →∞ f T (u) = κu ψ(u).
On the other hand we have for all T large, for all u ≥ 0,

0 ≤ f T (u) ≤ Cu ψ(u), therefore Lebesgue's dominated convergence theorem yields lim T →∞ S T T 2 = κ 2 ∞ 0 u ψ(u)du,
which is the asymptotic formula expected. If α = 0, then the proof is done since S 1 T = S T . We now deal with S 1 T assuming α = 0. A summation by parts combined with the crude bound on Π(x) as above yields for large T

S 1 T = 1 2 ∞ 0 cos(2αx)x 2 e -x ψ x T Π(x)dx +α ∞ 0 sin(2αx)x 2 e -x ψ x T Π(x)dx + O(T ).
Let us analyze the term

I T := ∞ 0 cos(2αx)x 2 e -x ψ x T Π(x)dx,
the other term involving the sine being similar. By a change of variable we get

I T = T 3 ∞ 0 u 2 e -T u cos(2αT u)Π(T u) ψ(u)du = T 2 ∞ 0 f T (u) cos(2αT u)du,
where f T (u) = T u 2 e -T u Π(T u) ψ(u) as above. We then write

I T T 2 = ∞ 0 (f T (u) -κu ψ(u)) cos(2αT u)du + κ ∞ 0 u ψ(u) cos(2αT u)du,
and a single integration by parts shows that

∞ 0 u ψ(u) cos(2αT u)du = O 1 T , while ∞ 0 (f T (u) -κu ψ(u)) cos(2αT u)du ≤ R + |f T (u) -κu ψ(u)|du.
By applying Lebesgue's theorem as before, we finally conclude that lim

T →+∞ I T T 2 = 0,
and thus lim

T →+∞ S T T 2 = lim T →+∞ S T T 2 = κ 2 ∞ 0 u ψ(u)du,
and the proof is done. The rest of this section is devoted to the proof of Theroem 1.1 and is naturally subdivided into three main steps. We recall that we investigate the spectrum of ∆ n,ρ where ρ : Γ → GL(V ρ ) is a finite dimensional unitary representation. For simplicity we will denote the character of ρ by χ(γ) := Tr(ρ(γ)).

Let ψ be a C ∞ function whose Fourier transform ψ = ψ is in C ∞ 0 (R), is even, and takes its values in R + . Notice that ψ is given by

ψ(r) = R ψ(u)e iru du,
and is therefore even too. We will apply the (twisted) trace formula to

h(r) = ψ(L(r -α)) + ψ(L(r + α)),
where α is fixed and L will be taken large. We then have

h(u) = 2 cos(αu) L ψ u L , so that N n (L) = (g-1)ndim(V ρ ) R (ψ(L(r -α)) + ψ(L(r + α))) r tanh(πr)dr+N 0 n (L),
where we have set

N 0 n (L) = 2 L γ∈P k≥1 χ(γ k )F n (γ k ) (γ) ψ(k (γ)/L) 2 sinh(k (γ)/2) cos(αk (γ)).
Notice that if γ is a representative of a primitive conjugacy class, then γ -1 represents another conjugacy class which corresponds to a closed geodesic with reversed orientation. Therefore the character χ breaks the time reversal symmetry if and only if it can distinguish the orientation of some closed geodesics. As emphasized by the physical intuition, it will prove more convenient to re-write the above sum over non-oriented primitive closed geodesics: we set P 0 = P/{Id, Inv}, where Inv : P → P is the involution given by the inversion, acting on conjugacy classes. We then have

N 0 n (L) = 2 L γ∈P 0 k≥1 χ(γ k ) + χ(γ k ) F n (γ k ) (γ) ψ(k (γ)/L) 2 sinh(k (γ)/2) cos(αk (γ)).
5.2. Expectation and variance in the large n limit. We first observe that by taking expectations and using the fact that for all k,

lim n→ E n (F n (γ k )) = d(k)
exists, we obtain that for large n (here α, L are fixed),

E n (N n (L)) = (g-1)ndim(V ρ ) R (ψ(L(r -α)) + ψ(L(r + α))) r tanh(πr)dr+O L (1),
which is a smooth probabilistic Weyl law in the large n regime. The quantum variance is

V n (L) := E n |N n (L) -E n (N n (L))| 2 = E n N 0 n (L) -E n (N 0 n (L)) 2 .
for simplicity set

G k (γ) := χ(γ k ) + χ(γ k ) cos(αk (γ)) (γ) ψ(k (γ)/L) 2 sinh(k (γ)/2) , so that we have V n (L) = 4 L 2 γ 1 ,k 1 γ 2 ,k 2 G k 1 (γ 1 )G k 2 (γ 2 )E n F n (γ k 1 1 ) -E n (F n (γ k 1 1 )) F n (γ k 2 2 ) -E n (F n (γ k 2 2 )) .
The parameter L being fixed, we observe by Proposition 3.1 (1) + ( 2) that whenever γ 1 = γ 2 ∈ P 0 we have

lim n→+∞ E n F n (γ k 1 1 ) -E n (F n (γ k 1 1 )) F n (γ k 2 2 ) -E n (F n (γ k 2 2 )) = 0, therefore by Proposition 3.1 (3) we get lim n→+∞ V n (L) := S(L) := 4 L 2 k 1 ,k 2 V(k 1 , k 2 )S k 1 ,k 2 (L), where S k 1 ,k 2 (L) := γ∈P 0 G k 1 (γ)G k 2 (γ).
We have obtained a "near diagonal" sum, and the goal of the remaining subsections is to analyze the asymptotic behaviour as L → +∞ of each term S k 1 ,k 2 (L).

5.3.

The non-primitive contribution. The non-primitive contribution corresponds to the sum over integers k 1 , k 2 such that k 1 + k 3 ≥ 3. We warn the reader that in the estimates below, the implied constants do not depend on L, k 1 , k 2 and may change from line to line. We will therefore use for simplicity Vinogradov's notation f (T ) g(T ) which means that f (T ) = O(g(T )) as T → +∞. By a crude bound we have

|S k 1 ,k 2 (L)| γ∈P 0 e -k 1 +k 2 2 (γ) (γ) 2 .
so that it is actually uniformly bounded with respect to L. By a Sieltjes integration by parts we have

|S k 1 ,k 2 (L)| ∞ 0 e -k 1 +k 2 2 u k 1 + k 2 2 u 2 -2u N 0 (u)du (k 1 + k 2 ) ∞ 0 e -( k 1 +k 2 2 -1)u u 2 du,
by using a crude bound on N 0 (u) ≤ Ce u . Using the fact that for all α > 0 we have

∞ 0 e -αt t 2 dt = 1 α 3 , we get for all k 1 + k 2 ≥ 3, |S k 1 ,k 2 (L)| 1 (k 1 + k 2 ) 2 .
We are now ready to estimate

S N P (L) := k 1 +k 2 ≥3 V(k 1 , k 2 )S k 1 ,k 2 (L).
We will show that S N P (L) log 2 (L), following a computation that was suggested to us by Zeev Rudnick. First observe that since ψ has compact support, the sum over k 1 , k 2 is limited to the range

k 1 , k 2 L.
Notice that we have also

V(k 1 , k 2 ) σ(gcd(k 1 , k 2 )), where σ(n) = d|n d
is the sum of divisors function. Hence we have

S N P (L) k 1 ,k 2 L σ(gcd(k 1 , k 2 )) (k 1 + k 2 ) 2 .
By writing for j = 1, 2, k j = Dm j with gcd(m 1 , m 2 ) = 1, we get

S N P (L) D m 1 D,m 2 D L σ(D) D 2 (m 1 + m 2 ) 2 D L σ(D) D 2   m 1 ,m 2 L 1 (m 1 + m 2 ) 2   . It is easy to check that   m 1 ,m 2 L 1 (m 1 + m 2 ) 2   log(L).
On the other hand, we can write

σ(D) = ab=D a so that D L σ(D) D 2 a,b L a (ab) 2 a L 1 a ∞ b=1 1 b 2 log(L).
In a nutshell, we have reached

lim n→+∞ V n (L) = S(L) = 4 L 2 k 1 ,k 2 V(k 1 , k 2 )S k 1 ,k 2 (L) = 4 L 2 S 1,1 (L) + O (log(L)) 2 L 2 ,
where

S 1,1 (L) = γ∈P 0 χ(γ) + χ(γ) 2 (γ) 2 ψ 2 ( (γ)/L) 4 sinh 2 ( (γ)/2) cos 2 (α (γ)).
5.4. Applying the equidistribution Lemma. We now know that lim

L→+∞ lim n→+∞ V n (L) = lim L→+∞ 4 L 2 S 1,1 (
L), thus we need to determine the asymptotic behaviour when L → +∞ of S 1,1 (L). We assume that α = 0. We will therefore apply Lemma 5.1 with The reader might wonder if representations ρ : Γ → G with Zariski dense images actually exist. A paper of Kishore [START_REF] Kishore | Representation variety of surface groups[END_REF], using results of Breuillard, Green, Gurnalik and Tao, shows that if G is real algebraic and semi-simple, then (Theorem 2.7), such a homomorphism always exists. This is enough to deal with G = SU (N ), SO(N ), SP (N ). More Generally, in [START_REF] Kim | Density of Zariski density for surface groups[END_REF], they show (Corollary 2.4) using a dimensional argument, that for any real algebraic reductive Lie Group G, the set of representations with Zariski dense image is non-empty (and actually dense) provided that

Π(x) = γ∈P 0 (γ)≤x χ(γ) + χ(γ) 2 , g(x) = x 2 4 sinh 2 (x/2) . Writing Π(x) = γ∈P 0 (γ)≤x χ 2 (γ) + γ∈P 0 (γ)≤x χ 2 (γ) + γ∈P 0 (γ)≤x 2
g ≥ (dim R (G)) 2 ,
where g is the genus of Γ\H and dim R is the real dimension of G. This allows to build representations with zariski dense images in U (N ) provided g ≥ N 4 .

Proposition 4 . 3 .

 43 (Chebotarev type asymptotic) Assume that ρ : Γ → G is a unitary representation where G is a compact algebraic Lie subgroup of GL N (C). Assume that the image of Γ by ρ is Zariski dense in G. Let f (g) = φ(Tr(g)) be a polynomial function of the trace. Then as x → +∞ we have(γ)≤x f (ρ(γ)) = G f (g)dg Li(e x ) + O(e α 0 x ),for some α 0 < 1 and where dg denotes normalized Haar measure on G.Proof. By Peter-Weyl theorem, since f (g) is a smooth central function we know that we can expand it asf (g) =λ∈ G c λ Tr(λ(g)), where c λ ∈ C the sum runs over all irreducible representations λ of G. This sum is actually finite: indeed by the polynomial hypothesis we have the finite sum f (g) = k,l a k,l (Tr(g)) k (Tr(g)) l , where each a k,l ∈ C. Let I : G → GL(C N ) denote the faithfull representation of G acting as usual on C N by left matrix product with column vectors. Then we have (Tr(g)) k (Tr(g)) l = Tr I ⊗k ⊗ I ⊗l (g) ,

4 L 2 S 1 , 1 (L) = 4 ∞ 0 u ψ 2 2 Rx x + O e x x 2 +Π 2 . 2 G 2 G( 2 GOE

 4211402222222 ,we observe that two cases can occur. Either χ 2 ≡ 1 and we have by the prime orbit theorem (recall that we are summing over P 0 ) (u)du = |u| ψ(u))2 du = Σ 2 GOE (ψ).Or we have χ 2 ≡ 1 and we can apply Proposition 4.2 to get as x → +∞ Π(x) = e O e β 0 x , for some β 0 < 1. Therefore as x → +∞ we have proved. We now show how Theorem 1.2 follows. In view of the above dicussion, all we have to do is to compute the asymptotics ofΠ(x) = γ∈P 0 (γ)≤xTr(ρ(γ)) + Tr(ρ(γ))We can apply Proposition 4.3 with G as in Theorem 1.2 andf (g) = Tr(g) + Tr(g) Assume that G ⊂ U (N ). First we can observe that G f (g)dg = G (Tr(g)) 2 dg + G (Tr(g)) 2 dg + |Tr(g)| 2 dg.As done previously in §4, letI : G → GL(C N )denote the standard representation of G acting on C N by left matrix multiplication. Since G is not a direct product, I is actually irreducible, hence Schur orthogonality says that G |Tr(g)| 2 dg = G |Tr(I(g))| 2 dg = 1. On the other hand, G (Tr(g)) 2 dg = G Tr(I ⊗ I(g))dg = d trivial , where d trivial denotes the multiplicity of the trivial representation in the irreducible decomposition of I ⊗ I, in particular it is a non-negative integer. Since G (Tr(g)) 2 dg ≤ G |Tr(g)| 2 dg = 1, we must have d trivial ∈ {0, 1}. To summarize, G f (g)dg = Tr(g)) 2 dg + 2 ∈ {2, 4}, which shows that the only possible limits of the spectral variance are Σ g)) 2 dg = G (Re(Tr(g))) 2 dg-G (Im(Tr(g))) 2 dg ≤ G |Tr(g)| 2 dg = 1. Clearly if g → Tr(g) ∈ R, then G (Tr(g)) 2 dg = G |Tr(g)| 2 dg = 1, and we are in the GOE case. If there exists g ∈ G such that Im(Tr(g)) = 0, then a simple continuity argument shows that G (Tr(g)) 2 dg < G |Tr(g)| 2 dg = 1, and therefore G (Tr(g)) 2 dg = 0, we are in the GUE case. Applying this criterion to the classical groups shows that G = SO(N ), Sp(N ) will fall in the GOE case since traces are always real. On the other hand, for G = U (N ) and G = SU (N ) with N ≥ 3, traces can take complex values and we get the GUE case. Notice that Sp(1) = SU (2). Theorem 1.2 is now proved. .


Eduardo Pavez

Benjamin Girault

Antonio Ortega

Philip A Chou

SPECTRAL FOLDING AND TWO-CHANNEL FILTER-BANKS ON ARBITRARY GRAPHS

Keywords: graph filterbank, graph Fourier transform, multiresolution representation, two channel filterbank

In the past decade, several multi-resolution representation theories for graph signals have been proposed. Bipartite filter-banks stand out as the most natural extension of time domain filter-banks, in part because perfect reconstruction, orthogonality and bi-orthogonality conditions in the graph spectral domain resemble those for traditional filter-banks. Therefore, many of the well known orthogonal and bi-orthogonal designs can be easily adapted for graph signals.

A major limitation is that this framework can only be applied to the normalized Laplacian of bipartite graphs. In this paper we extend this theory to arbitrary graphs and positive semi-definite variation operators. Our approach is based on a different definition of the graph Fourier transform (GFT), where orthogonality is defined with respect to the Q inner product. We construct GFTs satisfying a spectral folding property, which allows us to easily construct orthogonal and bi-orthogonal perfect reconstruction filter-banks. We illustrate signal representation and computational efficiency of our filter-banks on 3D point clouds with hundreds of thousands of points.

INTRODUCTION

Graph signal processing (GSP) provides a toolbox for analysis and manipulation of signals living in irregular domains [START_REF] Ortega | Graph signal processing: Overview, challenges, and applications[END_REF][START_REF] Shuman | The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[END_REF]. Given the success of multi-resolution representations (MRR) to analyze and process traditional signals [START_REF] Vetterli | Wavelets and subband coding[END_REF], significant efforts have been put into extending MRRs for graph signals [START_REF] David I Shuman | Localized spectral graph filter frames: A unifying framework, survey of design considerations, and numerical comparison[END_REF].

Applications often require these MRRs to: (i) be perfect reconstruction (invertible), (ii) be critically sampled (non redundant), (iii) be orthogonal, and (iv) have compact support (polynomial filter implementation). In the graph setting, it has proven challenging to find theories that satisfy more than a few of these properties simultaneously. Current theories require strong assumptions on the graph topology (e.g., bipartite [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF], circulant [START_REF] Kotzagiannidis | Splines and wavelets on circulant graphs[END_REF]), and are valid for a single type of graph operator (e.g., normalized Laplacian or adjacency). Narang and Ortega [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF] proposed two channel filter-banks on bipartite graphs, composed of graph filters, vertex down-sampling, and vertex up-sampling operators (see Figure 1). These bipartite filterbanks (BFB) obey (i), (ii), and either (iii) or (iv), can be designed in the frequency domain, and can be implemented using low degree polynomials. In addition, regular domain filter-banks can be easily converted to the graph domain [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF][START_REF] Sakiyama | Spectral graph wavelets and filter banks with low approximation error[END_REF][START_REF] Tay | Techniques for constructing biorthogonal bipartite graph filter banks[END_REF][START_REF] Tay | Bipartite graph filter banks: Polyphase analysis and generalization[END_REF]. Given their strong theoretical properties and efficient implementations, BFB have found numerous applications [START_REF] Anis | Compression of dynamic 3d point clouds using subdivisional meshes and graph wavelet transforms[END_REF][START_REF] Tzamarias | Compression of hyperspectral scenes through integer-tointeger spectral graph transforms[END_REF][START_REF] Levorato | Reduced dimension policy iteration for wireless network control via multiscale analysis[END_REF][START_REF] Qiao | Target recognition in sar images via graph wavelet transform and 2dpca[END_REF]].

Author's email: pavezcar@usc.edu. This work was funded in part by a Google Faculty Research Award. Despite all these remarkable properties, BFB theory [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF] only applies to normalized Laplacians and adjacency matrices of bipartite graphs. These are major limitations since the graph structure is rarely bipartite (which dictates the down-sampling operator), whereas the graph variation operator (or graph shift) is determined by the application. To overcome these issues, we propose a new theory that can be applied to: 1) arbitrary graphs, 2) any vertex partition for down-sampling, and 3) positive semi-definite variation operators (see [START_REF] Girault | Irregularity-aware graph fourier transforms[END_REF][START_REF] Anis | Efficient sampling set selection for bandlimited graph signals using graph spectral proxies[END_REF][START_REF] Egilmez | Graph learning from data under laplacian and structural constraints[END_REF][START_REF] Pavez | Region adaptive graph Fourier transform for 3D point clouds[END_REF] for examples). The proposed filter-banks also satisfy (i), (ii), and either (iii) or (iv), as with BFBs.

We consider the (M, Q) graph Fourier transform ((M, Q)-GFT), a generalization of the GFT to arbitrary finite dimensional Hilbert spaces [START_REF] Girault | Irregularity-aware graph fourier transforms[END_REF][START_REF] Girault | Graph vertex sampling with arbitrary graph signal hilbert spaces[END_REF] with inner product x, y Q = y Qx and variation operator M. BFB theory is built upon a spectral folding property of the eigenvectors and eigenvalues of the normalized Laplacian of bipartite graphs [START_REF] Rk | Spectral graph theory[END_REF]. We follow a similar strategy and prove a new spectral folding property for the (M, Q)-GFT. Interestingly, our perfect reconstruction and orthogonality conditions match those of the BFB framework [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF], and as a result their filter designs, or any of the more recent improvements [START_REF] Sakiyama | Spectral graph wavelets and filter banks with low approximation error[END_REF][START_REF] Tay | Techniques for constructing biorthogonal bipartite graph filter banks[END_REF] can be reused. When the graph is bipartite, and M is the normalized or combinatorial Laplacian, we recover the nonZeroDC and ZeroDC filter-banks, respectively [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF].

Early MRRs on arbitrary graphs were constructed by scaling and shifting spectral graph filters [START_REF] Crovella | Graph wavelets for spatial traffic analysis[END_REF][START_REF] Coifman | Diffusion wavelets[END_REF][START_REF] Hammond | Wavelets on graphs via spectral graph theory[END_REF]. These methods are difficult to invert (e.g., requiring least squares), are not critically sampled, and lack orthogonality. More recent approaches are redundant [START_REF] Shuman | A multiscale pyramid transform for graph signals[END_REF][START_REF] Sakiyama | Oversampled graph laplacian matrix for graph filter banks[END_REF], lack perfect reconstruction [START_REF] Li | Scalable m-channel critically sampled filter banks for graph signals[END_REF][START_REF] Anis | Critical sampling for wavelet filterbanks on arbitrary graphs[END_REF], or change the graph to a bipartite one [START_REF] Narang | Local two-channel critically sampled filter-banks on graphs[END_REF][START_REF] Zeng | Bipartite approximation for graph wavelet signal decomposition[END_REF][START_REF] Jiang | Admm-based bipartite graph approximation[END_REF][START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF]. While some of these approaches [START_REF] Narang | Local two-channel critically sampled filter-banks on graphs[END_REF][START_REF] Zeng | Bipartite approximation for graph wavelet signal decomposition[END_REF][START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF] can exploit efficient filter-bank implementations, once a sparse bipartite graph is available, obtaining the bipartite graph itself, either by graph approximation or through graph learning may be computationally infeasible for large graphs. More recently, [START_REF] Sakiyama | Twochannel critically sampled graph filter banks with spectral domain sampling[END_REF] proposed graph filter-banks with spectral domain down-sampling. This sampling operator induces spectral folding of the GFT which is exploited to obtain perfect reconstruction conditions. Although this approach can be used for arbitrary graphs and variation operators, it requires computing a full GFT, which does not scale to large graphs.

We show in our experiments with 3D point clouds, that in contrast to previous approaches, the proposed filter-banks can be implemented efficiently on large graphs (e.g., with hundreds of thousands of nodes), as long as these are sparse, and outperform BFBs in energy compaction and run time. The rest of the paper is organized as follows. In Sections 2 and 3 we review the fundamentals of GSP on arbitrary Hilbert spaces, and two channel filter-banks on bipartite graphs, respectively. Our theory is presented in Section 4. We end this paper with numerical results and conclusions in Sections 5 and 6, respectively.

GSP IN ARBITRARY HILBERT SPACES

Scalars, vectors and matrices are written in lower case regular, lower case bold and upper case bold respectively (e.g., a, b, C). Positive definite and semi-definite matrices are denoted by A 0 and A 0 respectively. Consider a weighted undirected graph

G = (V, E, M) with vertex set V = {1, 2, • • • , n}, edge set E ⊂ V × V, and varia- tion operator M = (mij), satisfying mij = mji = 0 when ij ∈ E, and mij = 0 otherwise. A graph signal is a function x : V → R, that can be represented by a vector x = [x1, • • • , xn]
. The variation operator is assumed to be positive semi-definite, and the variation of a signal is ∆(x) = x Mx ≥ 0. Intuitively, signals with increased variation are said to have higher frequency content. We will further assume that M is irregular, that is, the graph is connected. Typical examples of variation operators include the combinatorial and normalized Laplacian matrices. For a symmetric non negative matrix W = (wij), degree of node i is di = j∈V wij, and the degree matrix is [START_REF] Girault | Irregularity-aware graph fourier transforms[END_REF] introduced the idea of using an inner product x, y Q = y Qx, and induced norm given by x Q =

D = diag(d1, • • • , dn). The combinato- rial Laplacian is L = D -W, while the normalized Laplacian is L = D -1/2 LD -1/2 = I -D -1/2 WD -1/2 .
x, x Q , with Q 0. The (M, Q)-GFT basis vectors are the columns of U = [u1, • • • , un], which solve the generalized eigenvalue problem

Mu k = λ k Qu k , (1)
and 0 ≤ λ1 ≤, • • • , ≤ λn. The set of eigenvalues (spectrum) of a graph is denoted by σ(M, Q). The generalized eigenvectors are Q-orthonormal, hence ui Q = 1, ∀i ∈ V, and ui, uj Q = 0, ∀i = j, that is, U QU = I in matrix form. A graph signal x has the following repesentation in the (M, Q)-GFT basis

x = n i=1 x, ui Q ui = Ux. (2)
The (M, Q)-GFT of x is denoted by x, with coordinates xi = x, ui Q . In matrix form this corresponds to x = U Qx, while the inverse transform is given by x = Ux, since UU Q = I. A linear operator H is a spectral filter if there is a function h :

R+ → R so that H = Uh(Λ)U Q = h(Z), where Z = Q -1 M = UΛU Q is the fundamental matrix, and Λ = diag(λ1, • • • , λn).

TWO CHANNEL FILTER-BANKS

In this section we define two channel filter-banks on arbitrary graphs, and review the BFB theory [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF]. A two channel filter-bank is depicted in Figure 1. The analysis filters are H0 and H1, while the synthesis filters correspond to G0 and G1. Consider the set A and B = A \ V, which form a partition of the vertex set V. Without loss of generality we assume that A = {1, 2, • • • , |A|}. Down-sampling a signal x on a set A corresponds to keeping the entries xi : i ∈ A, and discarding the rest. This can be represented by xA = SAx, where SA = [IA, 0] is a |A|×|V| selection matrix. The up-sampling operator is S A . Down-sampling followed by up-sampling sets to zero the entries in B, thus S A xA = S A SAx = x A 0 .

Vertex domain conditions for arbitrary graphs

The analysis operator (filtering and down-sampling) from Fig. 1 is

Ta = S A SAH0 + S B SBH1 = SAH0 SBH1 . ( 3
)
The outputs of the low pass and high pass channels, called approximation a and detail d coefficients, respectively, are given by:

Tax = a d = SAH0x SBH1x . (4)
The synthesis operator has a similar expression

Ts = G0S A SA + G1S B SB = G0S A G1S B . (5)
We say that a two channel filter-bank is perfect reconstruction (PR) if TsTa = TaTs = I. A linear operator T is Q-orthogonal if for each x, the norm of the transformed signal is preserved, that is,

Tx Q = x Q .
In matrix form this corresponds to T QT = Q. For a PR two channel filter-bank, Ta is Q-orthogonal if and only if Ts is Q-orthogonal. Finding operators Ta, Ts that are orthogonal and PR is not that difficult, in fact, any non-singular orthogonal matrix can be used for Ta, and the synthesis operator can be chosen as Ts = Q -1 T a Q. The challenge is finding operators that exploit the graph structure, and that can be efficiently implemented on large arbitrary graphs. In the next subsection we review the approach of [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF] to design BFB using spectral graph filters.

Spectral domain conditions for bipartite graphs

BFBs can be constructed on bipartite graphs:

Definition 1. A graph G = (V, E) is bipartite on (A, B), if i) (A, B)
forms a partition, that is, A ∩ B = ∅, and A ∪ B = V, and ii) for all (i, j) ∈ E, i ∈ A and j ∈ B, or i ∈ B and j ∈ A.

In bipartite graphs, only edges between sets A and B are allowed, therefore the Laplacian matrices have the form

L = DA -WAB -WBA DB , L = IA -WAB -WBA IB , (6)
where

L = D -1/2 LD -1/2 = I-W, and W = D -1/2 WD -1/2 .
Spectral filters are defined using the (L, I)-GFT, thus Z = L, and

Hi = hi(L), Gi = gi(L), for i ∈ {0, 1}. (7)
We define J = diag(f ), where fi = 1 if i ∈ A, and fi = -1 when i ∈ B. Then S A SA = 1 2 (I + J), and S B SB = 1 2 (I -J), and the PR condition becomes

I = 1 2 (G0H0 + G1H1) + 1 2 (G0JH0 -G1JH1) . ( 8
)
The BFB framework achieves PR by designing filters that obey G0H0 + G1H1 = 2I, and G0JH0 -G1JH1 = 0. (9) Theorem 1.

[5] For a BFB with filters given by ( 7), a necessary and sufficient condition for PR is that ∀λ ∈ σ(L, I),

h0(λ)g0(λ) + h1(λ)g1(λ) = 2 (10) h0(λ)g0(2 -λ) -h1(λ)g1(2 -λ) = 0. (11)
I-orthogonal filter-banks can be realized if and only if for all λ ∈ σ(L, I), the filters also satisfy

h 2 0 (λ) + h 2 1 (λ) = 2, (12) h0(λ)h0(2 -λ) -h1(λ)h1(2 -λ) = 0. (13)
Orthogonal filter-banks are PR, while the converse is not true in general. In fact, filters h0, h1, g0, g1 obey ( 12) and ( 13), if and only if, they obey [START_REF] Tay | Bipartite graph filter banks: Polyphase analysis and generalization[END_REF], [START_REF] Anis | Compression of dynamic 3d point clouds using subdivisional meshes and graph wavelet transforms[END_REF] and hi = gi. These filters are not polynomial, thus requiring full eigendecomposition for implementation. To overcome this, filters can be approximated with Chebyshev polynomials [START_REF] Hammond | Wavelets on graphs via spectral graph theory[END_REF][START_REF] Sakiyama | Spectral graph wavelets and filter banks with low approximation error[END_REF]. An alternative is to use PR bi-orthogonal filters

h0(λ) = g1(2 -λ), h1(λ) = g0(2 -λ), (14)
which can be designed to be near orthogonal and polynomial [START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF].

The proofs of orthogonality and PR (Theorem 1) use Proposition 1, which holds only for the normalized Laplacian of bipartite graphs.

Proposition 1.

[20][Spectral folding.] If Lu = λu, then Ju is an eigenvector with eigenvalue 2 -λ.

To the best of our knowledge no other variation operators have this property for bipartite or arbitrary graphs.

MAIN RESULTS

We start by establishing conditions under which the (M, Q)-GFT has the spectral folding property.

Theorem 2 (Spectral folding). Consider an arbitrary partition of the vertices, A and B = V \A. Without loss of generality we assume A = {1, 2, • • • , |A|}. Let Q 0 and the variation operator be

M = MAA MAB MBA MBB 0, (15)
then the following statements are equivalent:

1. The inner product matrix is equal to

Q = MAA 0 0 MBB . ( 16
)
2. There is a full set of generalized eigenvectors, and

Mu = λQu ⇐⇒ MJu = (2 -λ)QJu. ( 17
)
Due to space limitations, we only sketch the proof of 1) ⇒ 2). A complete proof can be found in [START_REF] Pavez | Two channel filterbanks on arbitrary graphs with positive semidefinite variation operators[END_REF]. Let u = [u A , u B ] be a generalized eigenvector of M with eigenvalue λ, then MAAuA+MABuB = λQAuA, MBAuA+MBBuB = λQBuB.

Set v = Ju = [u A , -u B ]
, and compute Mv. Using the fact that u is a generalized eigenvector, and ( 16) produces the desired result. For this (M, Q)-GFT, the fundamental matrix is:

Z = Q -1 M = IA M -1 AA MAB M -1 BB MBA IB = UΛU Q,
and Λ = diag(λ1, λ2, • • • , λn). This (M, Q)-GFT shares some properties with the (L, I)-GFT of bipartite graphs. First, the generalized eigenvalues obey 0 ≤ λi ≤ 2, and inequalities become strict when M is non-singular. Second, the eigenvalue λ = 1 has multiplicity at least ||A| -|B||, thus the middle graph frequency is less selective when the down-sampling sets have uneven size. Finally, when M = L + V and V is diagonal, i.e., L is a generalized Laplacian [START_REF] Egilmez | Graph learning from data under laplacian and structural constraints[END_REF], the multiplicity of λ1 (smallest eigenvalue) is equal to the number of connected components of the graph. Now we state our result for PR filter-banks.

Theorem 3 (Perfect reconstruction). For any positive semi definite variation operator M, and any vertex partition V = A ∪ B. Choose the inner product matrix Q according to Theorem 2, and spectral graph filters for i ∈ {0, 1}

Hi = Uhi(Λ)U Q, Gi = Ugi(Λ)U Q. ( 18
)
The functions hi, gi for i ∈ {0, 1} obey conditions ( 10) and ( 11) for all λ ∈ σ(M, Q), if and only if the filter-bank of Figure 1 is PR.

The proof follows from Theorem 2 and similar arguments as those used in [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF] to prove [START_REF] Tay | Techniques for constructing biorthogonal bipartite graph filter banks[END_REF]. Theorem 3 implies that our framework can be implemented using filters designed for bipartite graphs (see [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF][START_REF] Tay | Techniques for constructing biorthogonal bipartite graph filter banks[END_REF][START_REF] Sakiyama | Spectral graph wavelets and filter banks with low approximation error[END_REF]). We can also construct Q-orthogonal filter-banks.

Theorem 4 (Parseval). Under the conditions of Theorem 3, the analysis filters obey ( 12) and ( 13) for all λ ∈ σ(M, Q), if and only if,

Tax, Tay Q = x, y Q .
Theorem 4 could be stated replacing Ta by Ts. We have preservation of the Q norm, thus Tax

2 Q = x 2 Q , and Tsx 2 Q = x 2
Q . When Q = I, the synthesis operator is the transpose of Ta, however, in general we have the relation Ts = Q -1 T a Q. The authors in [START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF] showed that orthogonal filter-banks cannot be implemented with polynomials of L. The same arguments lead to Qorthogonal filter-banks not having implementations with polynomial of Z. As an alternative, bi-orthogonal filters [START_REF] Qiao | Target recognition in sar images via graph wavelet transform and 2dpca[END_REF] were proposed, which have polynomials implementations, and can be designed to be approximately Q-orthogonal (see [Section III-B][6]), and satisfy

α x Q T * x Q β x Q ∀x, (19)
where * can be a or s, and

α 2 = 1 2 inf λ∈[0,2] (h 2 0 (λ) + h 2 1 (λ)), β 2 = 1 2 sup λ∈[0,2] (h 2 0 (λ) + h 2 1 (λ)).
Remark 1. The zeroDC filter-banks [START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF], were introduced so that the smoothest basis function is constant. This approach can be implemented by multiplying the input by D 1/2 before applying the analysis filter-bank, and multiplying by D -1/2 at the output of the synthesis filter-bank. This ensures that a constant input signal has zero response in the high pass channel. Bi-orthogonal zero-DC filter-banks can be implemented with polynomials of the random walk Laplacian of a bipartite graph [START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF]. The zeroDC filter-banks can be derived as a special case of our framework, since for bipartite graphs with Laplacian L, the inner product matrix from Proposition 2 is Q = D, and the fundamental matrix is the random walk Laplacian Z = D -1 L.

NUMERICAL RESULTS

We implement a "lazy" bi-orthogonal filter-bank, with filters H0 = I, H1 = Z, G0 = 2I -Z, and G1 = I. The down-sampling set A is chosen so that a node i ∈ A with probability 1/2, leading to |A| ≈ |B|. We iterate this filter-bank in the low pass channel L times, producing L high frequency channels, and 1 low pass channel. The low pass channel has approximately n2 -L coefficients, while the -th level high pass channel has approximately n2 -coefficients. 3D point clouds consist of a list of points in 3D space represented by their coordinates vi = [xi, yi, zi], and attributes ai. We use the "longdress" point cloud from the "8iVFBv2" dataset [START_REF] D'eon | 8i voxelized full bodies-a voxelized point cloud dataset[END_REF], which comes with color attributes. Each point vi is assigned a node in a graph, and an edge between nodes i and j is added if i is one of the K nearest neighbors of j, or vice versa. Edge weights are computed as wij = 1/ vivj . Point cloud down-sampling corresponds to selecting a subset of points, therefore we can repeat this graph construction procedure on a smaller point cloud, at the output of the low pass channel. For each two-channel filter-bank we follow the steps: 1) construct a graph with K nearest neighbor (KNN) algo-rithm and compute its combinatorial Laplacian matrix, 2) generate a random down-sampling set A, and B A c , and 3) if a bipartite graph is desired, keep edges between A and B and remove the rest.

Signal representation. We apply the iterated filter-bank with L = 7 levels to the color attributes of a single frame of the "longdress" sequence. For each L, we reconstruct the color signal using only the low frequency coefficients. We compare the proposed filterbanks with the BFBs as a function of m/n, where m is the number of coefficients in the low pass channel, and n is the total number of coefficients. Figure 2 shows that the proposed filter-bank has the best energy compaction when the KNN graph has fewer edges (K = 5), and performance decreases as K increases. The best performance of the BFBs is achieved with an intermediate value of K = 10. In Figure 3 we show the reconstructions of regions of the point cloud. When the bipartite graph is too sparse (K = 5), several artifacts can be observed, which can be attributed to points/nodes in the high pass channel that do not have connections in the low pass channel. When the bipartite graph is denser K = 20, the reconstruction has no artifacts, however details are smoothed more aggressively. The proposed filter-bank, with a sparser graph, better preserves textures and facial features (e.g., eyes, mouth and hair).

Complexity. We compare the run time of the iterated analysis filter-bank (L = 7) applied to 20 frames of the "longdress" sequence. We run the experiment using Matlab 2019. The bipartite filter-bank with K = 20 and K = 10 takes 14.3 and 8.23 seconds per frame respectively, while the proposed filter-bank with the best performance (K = 5), takes 6.72 seconds per frame. These point clouds have an average of 795, 000 points per frame. The complexity of our implementation is dominated by two factors. Graph construction, which is implemented using approximate KNN, with complexity proportional to K. Complexity of filtering is dominated by the product Zx. When the graph is bipartite, Zx is a sparse matrixvector product. In the non-bipartite case, Zx is computed in two steps, first we perform a sparse matrix-vector product y = Lx, and then solve the linear system Qz = y. Since Q is sparse, a numerically accurate approximation of z = Q -1 y can be found efficiently using the "\" operator in Matlab.

CONCLUSION

This paper extended the graph filter-bank framework of [START_REF] Narang | Perfect reconstruction twochannel wavelet filter banks for graph structured data[END_REF][START_REF] Narang | Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[END_REF], which uses the normalized Laplacian of bipartite graphs, to positive semidefinite variation operators, arbitrary graphs, and arbitrary downsampling operators. We achieve this by proving that the spectral folding property is not unique to the normalized Laplacian of bipartite graphs, and in fact, it is satisfied by certain generalized eigenvalues and eigenvectors of non-bipartite graphs. Based on this, we proposed a new Q-orthogonal graph Fourier transform, that leads to perfect reconstruction, orthogonal and bi-orthogonal conditions, equivalent to those already known for the bipartite graph case. We implemented a simple degree 1 polynomial "lazy" filter-bank on 3D point clouds graphs with hundreds of thousands of vertices (points). Our numerical results indicate that our framework outperforms the lazy filter-bank, implemented with bipartite graphs at various sparsity levels, in terms of run-time and energy compaction.

Fig. 1 :

 1 Fig. 1: Perfect reconstruction two channel filter-bank with analysis filters H0, H1, and synthesis filters G0 and G1. a and d denote approximation (low pass) and detail (high pass) coefficients respectively. Sampling sets are denoted by A and B.

Fig. 2 :

 2 Fig. 2: Linear approximation of 3D point clouds attributes using iterated two channel filter-banks.

Fig. 3 :

 3 Fig. 3: Top m/n = 0.25, bottom m/n = 0.125. Comparison of linear approximation using BFB and proposed filter-banks.