Jean-Christophe Sibel
email: jean-christophe.sibel@ensea.fr

Sylvain Reynal
email: reynal@ensea.fr

David Declercq
email: declercq@ensea.fr

A novel region graph construction based on trapping sets for the Generalized Belief Propagation

The Belief Propagation (BP) is an inference algorithm used to estimate marginal probability distributions for any Markov Random Field (MRF). In the realm of Low-Density Parity-Check (LDPC) codes that can be represented by MRF called Tanner graphs, the BP is used as a decoding algorithm to estimate the states of bits sent through a noisy channel. Known to be optimal when the Tanner graph is a tree, the BP suffers from suboptimality when the Tanner graph has a loop-like topology. Furthermore, combinations of loops, namely the trapping sets, are particularly harmful for the decoding. To circumvent this problem were proposed other algorithms, like the Generalized Belief Propagation (GBP) that comes from statistical physics. This algorithm allows to absorb topological structures inside new nodes called regions. An advantage is that the resulting graph, the region graph, is not unique then according to its construction this region graph is a media for the GBP that can provide more accurate estimates than the BP.

In this paper, we propose novel constructions of the region graph for the famous Tanner code of length N = 155 by making use of the trapping sets as basis for the regions.

I. INTRODUCTION

A well-known problematic of the Markov Random Fields (MRF) is to extract their marginal probability distributions. This inference problem has numerous applications in computer vision, neural networks, image processing, statistical physics and channel coding. In [START_REF] Pearl | Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] has been proposed the Belief Propagation (BP), known to provide accurate estimates. In the realm of error-correcting coding theory, the BP is a decoding algorithm that helps to recover a sequence of bits sent through a noisy channel. To this end the BP is associated to Low-Density Parity-Check (LDPC) codes that consist in applying artifical constraints between the bits, namely the parity-check equations. The sets of the bits joined with the set of the constraints form an MRF, called the Tanner graph, used as a media for the BP [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF]. It is an accurate inference algorithm, meaning that it has relevant performance in terms of the bit-error rate (BER). However the Tanner graphs of most LDPC codes have loop-like topologies, that leads the BP to wrong estimates, making this algorithm suboptimal [START_REF] Murphy | Loopy belef propagation for approximate inference: an empirical study[END_REF]. In particular, the combination of short loops, as the trapping sets [START_REF] Richardson | Error floors of LDPC codes[END_REF], [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF], are very harmful. To circumvent this phenomenon, we bring out that the BP is equivalent to the Bethe approximation [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF], a method used in statistical physics to estimate averages of thermodynamics quantities by neglecting -to some extent -correlations between interacting variables [START_REF] Bethe | Statistical Theory of Superlattices[END_REF]. As the BP, this technique suffers from the loop-like topology of the graphical representation of the problem, like spin glasses. It has been generalized to the Kikuchi approximation, a technique that consists in gathering interacting variables to absorb loops [START_REF] Kikuchi | A Theory of Cooperative Phenomena[END_REF]. The resulting graph, called the region graph, is a media for a new message-passing algorithm, the Generalized Belief Propagation (GBP) that turns out to be more accurate than the BP provided that the region graph has absorbed damageable structures. Along the whole paper, we focus on the Tanner code [START_REF] Tanner | A Class of Group-Structured LDPC Codes[END_REF] whose main property is that it can be entirely described by a set of known trapping sets. Then the region graph can be built by working on them, that allows to lower BER of the GBP comparing with the BP one.

In [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF] has been highlighted that the update equations of the GBP does not provide convergence of the algorithm therefore it was proposed to relax the update with the memory by the introduction of a uniform weighting. However, this choice seems quite restrictive.

Here we propose a general point of view of the relaxation by the use of a damping factor that depends on the iteration, and we make reveal that it provides relevant properties of the GBP.

The section II deals with preliminaries about the LDPC codes, the BP and the trapping sets. In the section III, are exposed the origins of the GBP, the region graph construction rules. We resume with a classical construction and two novel constructions adapted to the Tanner code. We also introduce the general damping factor and the different evolutions we propose with associated results. In the section IV, we expose results about our novel constructions.

II. PRELIMINARIES

A. LDPC Codes -Belief Propagation

We consider N bits X = {x1, . . . , xN } sent through a noisy channel. In the whole paper, we use the additive white gaussian channel whose power is given by the Signal-to-Noise Ratio (SNR). An LDPC code of length N is modeled by M < N parity-check equations C = {c1, . . . , cM } such that:

∀j ∈ {1, . . . , M }, cj(x1, . . . , xN ) = x i ∈N j xi
where the sum is computed over GF [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF], and Nj is a set of bits that are the neighborhood of cj determined by the code. We define Ni the neighborhood of xi by the set {cj|xi ∈ Nj}j. A couple {xi, cj ∈ Ni} forms an edge eij between a variable node associated to xi and a check node associated to cj in a bipartite graph G = {X ∪ C} {eij}ij. We call this graph the Tanner graph. The BP is an inference algorithm that consists in passing messages along the edges of G. We denote m

(k) ij (resp. n (k)
ji ) the message from the variable node xi (resp. the check node cj) to the check node cj (resp. the variable node xi) at iteration k, where a message is the probability distribution of the receiver conditionned to the emitter. For any edge eij the update equations are [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF]:

n (k) ji (0) = 1 2 + 1 2 X i ′ ∈N j \X i 2m (k-1) i ′ j (0) -1 n (k) ji (1) = 1 -n (k) ji (0) (1)
m (k) ij (xi) = li(xi) Zij C j ′ ∈N i \C j n (k) j ′ i (xi) (2)
where Zij is a normalization factor such that:

m (k) ij (0) + m (k) ij (1) = 1.
To initialize the algorithm, we use the likelihoods {li(xi) = pi(yi|xi)}i computed with observable nodes {y1, . . . , yN }: ∀eij, m (0) ij = li(xi). The estimate of the marginal probability distribution on xi, i.e., the belief on a variable xi is:

b (k) i (xi) = li(xi) Zi j∈N i n (k) ji (xi) (3)
where Zi is a normalization factor such that: bi(0) + bi(1) = 1. The estimate of the sent bits are: ∀i ∈ {1, . . . , N },

x(k

) i = arg maxx i b (k) i (xi).
The algorithm is stopped as soon as all the parity-check equations are verified by the output bits or if the convergence is reached: ∀xi, ∀cj ∈ Nj, n

(k+1) ji = n (k) ji .

B. Trapping-sets

When N is infinite, it has been prooved [START_REF] Richardson | Error floors of LDPC codes[END_REF] that the BP reaches the optimal solution given by the maximum likelihoods decoder because the Tanner graph is a tree. However, in pratical cases, N is finite, and most LDPC codes contain loops inside their Tanner graph making the BP suboptimal [START_REF] Murphy | Loopy belef propagation for approximate inference: an empirical study[END_REF]. Furthermore, the short loops and the combinations thereof are very harmful. The trapping sets exposed in [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF] are well- known topological structures that harm the decoding. A trapping set TS(a,b) is a Tanner graph that contains a variable nodes and b unverified check nodes. We consider the case a = 5 and b = 3 whose Tanner graph is represented on Fig. 1. Such a structure takes place in many LDPC codes, including the Tanner code [START_REF] Tanner | A Class of Group-Structured LDPC Codes[END_REF] of length N = 155 with M = 93. The interesting property of this LDPC code is that it is entirely covered by a set T of 155 trapping sets, i.e.:

∀cj ∈ C, ∃t ∈ T , cj ∈ t (4) ∀xi ∈ X, ∃t ∈ T , xi ∈ t (5)
The BER of the Tanner code suffers from an error floor [START_REF] Richardson | Error floors of LDPC codes[END_REF] for high SNR values, especially due to the TS [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF][START_REF] Murphy | Loopy belef propagation for approximate inference: an empirical study[END_REF]. A current problematic is then to lower the error floor. The finite alphabet iterative decoders are good challengers to solve this problem but we do not deal with these algorithms, we invite the interested reader to pay attention to the article [START_REF] Danjean | On the Selection of Finite Alphabet Iterative Decoders for LDPC codes on the BSC[END_REF] for more details.

III. GENERALIZED BELIEF PROPAGATION

A. Origins

In statistical physics, spin glasses are well-known Markov Random Fields (MRF) in which a problem is to minimize the free energy. This optimization has been demonstrated to be equivalent to the inference problem [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF]. Most methods rely on region-based approximations, where the MRF is clustered such that the belief b(x) is a product of the beliefs {br(xr)}r over the clusters:

b(x) = r∈R b cr r (xr) (6)
where {cr}r are overcounting numbers provided to account only once each variable of the MRF [START_REF] Pakzad | Estimation and marginalization using Kikuchi approximation methods[END_REF]. The Bethe Approximation (BA) [START_REF] Bethe | Statistical Theory of Superlattices[END_REF] is a region-based approximation that takes into account the shortrange correlations between the spins. It can be modeled by a factor graph that is identical to a Tanner graph if and only if the factors define hard constraints, which is the case of LDPC codes. Therefore, with computations detailed in [START_REF] Yuille | CCCP algorithms to minimize the Bethe and Kikuchi free energies: Convergent alternatives to belief propagation[END_REF], it has been concluded that the BA was equivalent to the BP. This equivalence provides a solution to the problem of the loop-like structure of the Tanner graph. Indeed, the BA has been extended to the Kikuchi Approximation (KA) [START_REF] Kikuchi | A Theory of Cooperative Phenomena[END_REF], a method to minimize the free energy as the BA with the slight difference that it considers larger ranges of correlation, thereby can absorb loops. The associated inference algorithm is the GBP.

B. Region-graph

The GBP is a message-passing algorithm that runs on a Bayesian network, namely the region graph, whose nodes are called regions. Each region r is compouned of a set of check nodes Cr and a set of variables Xr = ∅ with the following condition: if Cr is not an empty set then ∀cj ∈ Cr, Nj ⊆ Xr. Here we expose the rules of construction then we present three different constructions, two of which are our novel constructions suited to the Tanner code.

1) Rules of construction: The region graph is a graph of L levels. We present the construction in two steps. The first step is the construction of the first level: it is the choice of the initial regions set R0 = {r 0 k } k , i.e. the choice of the harmful structures of the Tanner graph that need to be neutralized. R0 is valid if:

∀cj ∈ C, ∃r 0 k ∈ R0, cj ∈ C r 0 k , Nj ⊆ X r 0 k ∀xi ∈ X, ∃r 0 k ∈ R0, xi ∈ X r 0 k
The second step is the construction of the other levels {R1, . . . , RL-1}. To build R l we search for the common variables and checks between the regions of the previous level R l-1 . Thus a region r l k belongs to R l if we can find an associated parent set

P l k ⊂ R l-1 such that: ∀cj ∈ C r l k , ∀r l-1 j ∈ P l k , cj ∈ C l-1 j ∀xi ∈ X r l k , ∀r l-1 j ∈ P l k , xi ∈ X l-1 j
The region graph reaches its last level RL-1 when there is no intersection anymore between the regions of RL-1. To each region r is associated an overcounting number cr ∈ Z such that a graph of regions is a true region graph if:

∀r ∈ R, p∈R r⊆p cp = 1 (7)
where r ⊂ p means that Xr ⊆ Xp and Cr ⊆ Cp.

2) Classical construction: Proposed in [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF], it consists in including only one check node per initial region:

∀cj ∈ C, ∃!r 0 k ∈ R0, C r 0 k = cj ∀(r 0 k , r 0 j ) ∈ R 2 0 , C r 0 k ∩ C r 0 j = ∅
The next levels are constructed as exposed previously. As an example we display on Fig. 2(a) the Tanner graph of the Hamming code, and on Fig. 2(b) the region graph from this method. In this case, the region graph has its own topology. However, for most LDPC codes, the sparsity of the Tanner graph makes this method generate a region graph whose topology is identical to the Tanner graph one. Thus the GBP provides the same solution as the BP, which is not relevant.

3) Novel constructions: In the case of the Tanner code, we use the trapping sets TS(5,3) introduced previously to create the level R0. The complexity of the GBP grows as the number of variable nodes contained in the regions is increased. A complete TS(5,3), i.e. the TS(5,3) together with the neighborhoods of all the check nodes, is

x 1 x 2 x 3 x 4 x 5 x 6 x 7 c 1 c 2 c 3 (a) Tanner graph c 1 x 1 , x 2 , x 3 , x 5 c 2 x 1 , x 2 , x 4 , x 6 c 3 x 1 , x 3 , x 4 , x 7 x 1 , x 2 x 1 , x 3 x 1 , x 4
x 1 (b) Region-graph Fig. 2. Hamming code compouned of 35 variable nodes then any message from R0 to R1 amounts to 2 35 operations, which is not fair at all. Therefore, we must use smaller initial regions to lower the complexity.

The first idea we propose is presented on Fig. 3, where each TS(5,3) is split into three initial regions, each of them containing two check nodes, one unverified check node, and their associated neighborhoods. We call this construction a triplets construction.

c 1 , c 4 , c 7 x 1 , x 2 , x 4 c 2 , c 5 , c 8 x 2 , x 3 , x 4 c 3 , c 6 , c 9 x 2 , x 4 , x 5
x 2 , x 4 Fig. 3. Region-graph of the TS(5, 3) -Triplets split Each initial region contains 13 variable nodes, making the computation of a message from R0 to R1 of 2 13 operations, which is dramatically less than the complexity given by the previous proposition. Locally, the region graph of a TS(5,3) is loop free, that makes the decoding optimal. In [START_REF] Welling | On the Choice of Regions for Generalized Belief Propagation[END_REF] is introduced that a region graph can offer a GBP more accurate than the BP simply by adding to the Tanner graph super regions. Therefore, we only link the triplets to the check nodes of the Tanner graph considering that a region constituted by a check cj is actually {cj ∪Nj}. Unfortunately, when we consider the whole code, the trapping sets are strongly correlated each other to each other. Thus, the region graph is not loop free, making the decoding not optimal. However, the construction provides a GBP that can offer better properties than the BP as we will see in the results part.

The second proposition is presented on Fig. 4, where each TS(5,3) is split into three initial regions, each of them containing four check nodes, two unverified check nodes and their associated neighborhoods. We call this a triangles construction. Each initial region contains 24 variable nodes, making the computation of a message from R0 to R1 of 2 24 which is greater than what we got from the previous construction, but still lower than 2 35 . The advantage of this construction is that it absorbs the short loops of the TS(5,3) and the unverified check nodes. As for the triplets construction, locaaly the region graph is loop free but embedded to the whole Tanner graph, a

c 1 , c 2 , c 4 , c 5 , c 7 , c 8 x 1 , x 2 , x 3 , x 4 c 2 , c 3 , c 5 , c 6 , c 8 , c 9 x 2 , x 3 , x 4 , x 5 c 1 , c 3 , c 4 , c 6 , c 7 , c 9 x 1 , x 2 , x 4 , x 5
x 2 , x 4 Fig. 4. Region-graph of the TS(5, 3) -Triangles split TS(5,3) has complex links with its fellow beings. However, we can hope that it won't be affected by trapping sets effects. We expose the results of these construction in the next section.

C. Message-passing

The GBP consists in passing messages along the edges of the region graph. Unlike the Tanner graph, this one is a directed graph because of the parent links. Thus, we compute a message m (k) rq if and only if r is a parent of q, i.e. q is a child of r denoted q ∈ Cr. We define Fr the family of r as {q|Cq ⊆ Cr, Xq ⊆ Xr}q, and its descendants Dr = Fr\r. According to [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF], [START_REF] Pakzad | Estimation and marginalization using Kikuchi approximation methods[END_REF] the messages from a region r to a region q at iteration k are:

m (k) rq (xq) =
where:

• x r\q is the state of X r\q = Xr\Xq, • L r\q (x r\q ) = x i ⊂X r\q li(xi),
• c r\q (xr) = c j ∈Cr \Cq cj(xN j ),

• Zrq is a normalization factor to ensure that: xq m (k) rq (xq) = 1. In [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF] is assumed that the iteration indices of the messages at the denominator must be the same as the one of mrq to keep relevant performance. Though, it prevents from using an efficient parallelisation of the computation. Simulations have shown that it is possible to replace at the denominator the messages m

where Zr is a normalization factor to ensure that xr b

(k) r (xr) = 1.
To get the beliefs for the single variables we only need to compute the marginal probability distributions of the regions beliefs. Thus for any region r:

∀xi ∈ Xr, b (k) i (xi) = 1 Zi x r\i b (k) r (xr) ( 10
)
where Zi is a normalization factor to ensure that

x i b (k) i (xi) = 1.
The estimates {x1, . . . , xN } are computed then as for the BP.

D. Damping factor

In [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF] it has been highlighted the fact that the GBP suffers from a poor convergence. Therefore the authors introduced a constant uniform damping factor w = 0.5 that helps to balance between the memory {m (k-1) rq }rq of the algorithm and the update {Frq}rq by the following relaxation:

∀q ∈ R, ∀r ∈ Pq, m (k) rq = 1 2 Frq + 1 2 m (k-1) rq ( 11
)
Here we propose a more general point of view by writing:

∀q ∈ R, ∀r ∈ Pq, m (k) rq = w k Frq + (1 -w k )m (k-1)
rq [START_REF] Yuille | CCCP algorithms to minimize the Bethe and Kikuchi free energies: Convergent alternatives to belief propagation[END_REF] where w k is a decreasing damping factor. The last value wK must be a null value to ensure that at the end:

∀q ∈ R, ∀r ∈ Pq, m (K) rq = m (K-1)

rq

The challenge is to find a suited sequence {w0, . . . , wK } that provides both convergence and relevant performance. We consider four different functions displayed on the Fig. 5: The balance between the memory m (k-1) rq and the update Frq is different from case to case. In the case of a parabolic function, the memory is quickly highlighted at the expense of the update, whereas in the case of an inverse parabolic function the memory is practically ignored for a long time. The affine coefficient enables a progressive oversight of the update up to a complete use of the memory. The constant function is what is proposed in [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF] with different values. We present on Fig. 6 the evolution of the average Bit-Error Rate BER k along the iterations with these different damping factors for four different initializations w0. The simulations have been realized with an SNR of 2.90 dB, i.e. at the end of the waterfall where the trapping sets are really harmful. The first observation to do from 6(d) is that a constant damping factor to the value w k = 1.00 provides the worst BER k meaning that the pure update is not efficient at all as it was indicated previously. From Fig. 6(a) joined with Fig. 6(b), it appears that a low value of w0 is recommended to get fast convergence of the GBP. In addition, we see that whatever the decreasing rule of w k , the value w0 = 0.5 lower the BER to a steady value at k = 19 unlike the value w0 = 0.25 has a longer transcient phase before convergence at k22. Thus, the initial uniform distribution between the memory and the update is the more relevant choice. Furthermore, on Fig. 6(c) and 6(d) we observe that for high w0 the parabolic w k , that gives quickly a low w k , fosters the fastest convergence compared with the constant, the affine and the inverse parabolic one. As an example, we see that the parabolic GBP, i.e. the GBP with the parabolic w k , converges at k = 22, whereas the inverse parabolic GBP converges at k = K i.e. when the convergence is completely forced. Although the parabolic GBP is dramatically faster, the steady value BERK are the same for both, meaning that w k is a convergence booster. The second convergence booster is the affine one, which is not surprising because it is a particular case of the parabolic function with n = 1. Then one could assume that increasing n provides faster convergence. However other simulations that we do not present here do not confirm this, from n = 2 the BER k are indistinguishable for the parabolic law. On the four figures, we can extract, among other, a common property: whatever w0 the parabolic GBP always converges nearly k = 20. This invariance is crucial because it brings out that w0 is a degree of freedom for the parabolic GBP, unlike the other decreasing laws. The surprising information from these observations is that they indicate that a fast and accurate GBP is enhanced by the memory and not by the update that defines the GBP itself. Thus, an assumption is that the GBP acts like a starter we must forget as quick as possible, it seems more relevant to use only a small percentage of the update for small value of k and to forget it as quick as possible. We do not display the result of the triangles contruction here to keep a reasonnable paper length, but simulations carried on this case highlight the same assumption. Simulations on other values of the SNR and other codes like the Hamming code made also reveal the same conclusion. It seems that the property of choosing a parabolic decreasing of w k with w0 < 0.5 to obtain relevant performance with few iterations belongs to the GBP and not to the code.

• (C) constant: w k = w0, • (A) affine: w k = w0(1 -k K ), • (P) parabolic: w k = w0(1 -k K ) n , n > 1, • (IP) inverse parabolic: w k = w0 1 -( k K ) n , n > 1.

IV. RESULTS

In this section we expose results of simulations in terms of the BER between the BP and the GBP. We present first the results on the Hamming code to evaluate the classical construction. Then we present the results on the Tanner code with our two constructions to bring out their efficiency.

A. Hamming Codes

On Fig. 7 is displayed the average BER along the SNR values for the BP and the GBP, used on Hamming codes of length N = 7 and N = 15. On Fig. 7(a) we displayed the GBP with parabolic damping factor. It appears that the GBP is not very different to the BP except for high SNR values for which we see that the BER of the GBP is lower than the BP one. This indicates that the classical construction brings only a slight improvement in this case. Concerning Fig. 7(b), the GBP reveals better performance for an affine damping factor, which is a parabolic one with n = 1, than for a constant damping factor w = 1. Once again, it is a relevant illustration of the poor result of the GBP pure update. Actually, these examples are useful to highlight the fact that the GBP turns out to be performant with the classical construction if the region graph is of different topology compared with the Taner graph. Moreover, for most LDPC codes, the sparsity of the Tannre graph implies a region graph whose topology is the same as the Tanner graph one. Thus in these cases, there is not any improvement.

B. Tanner Code

On Fig. 8 we display the BER k for a particularly error event of 7 errors that makes the decoding by the BP oscillate because of the TS [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF][START_REF] Murphy | Loopy belef propagation for approximate inference: an empirical study[END_REF]. We also have simulated on other noise realizations that harm the estimation for the same reason and we obtain the same results as what is presented. First of all, we can see that the GBP by the triplets construction has BER k values lower than that of the BP. Furthermore, it appears on Fig. 8(c) that the inverse parabolic function implies errors from k = 22, unlike the parabolic and the affine ones. This is another test to assert that the parabolic damping factor is the best choice for a relevant GBP. A first conclusion is that the triplets construction provides a GBP that converges fast, contrary to the BP that can only oscillate. The number of errors is 8 which is truly more accurate than the BP even though one error has been added comparing with the error event. Afterthat, considering the triangles construction result, we see that the convergence is quickly reached even for the inverse parabolic function. In addition, the number of errors by this construction is 7 i.e. there is no more errors than in the error event. Thus the GBP has a more powerful error correction by this construction than the triplets construction. One would assert that periodically, the BP corrects more errors than the GBP, whatever the construction. Indeed, every 9 iterations in average, the BP reaches a BER k of 0.0322581, meaning that there are only 5 errors left. However, this result cannot be accurately predicted because the periodical aspect is not perfect. Moreover, the difference between this minimum value and the maximum average BER = 0.32 is too large to use this pseudo-periodical pattern as a result to assert that around 9 iterations the lowest BER k is reached. Therefore, the GBP is truly more reliable than the BP, because the BER k does not change. In addition, other simulations for other SNR values with different error events made us convinced that the GBP always gets a BER equal or lower than the BP one, making it an accurate algorithm, provided that it is run on suited region graph constructions as we proposed.

V. CONCLUSION In this paper, we have exposed novel constructions of the region graph for the Tanner code, based on its trapping sets. The simulations we presented indicated that the performance of the GBP were improved by these constructions, raising that a triangles construction absorb the trapping sets better than a triplets construction. We have showed that the use of a damping factor is necessary to ensure relevant performance in terms of the BER, and that the classical proposition is not the best choice. More generally, our work enabled to understand that the GBP needs extensive research on its region graph to give interesting performance, that can go beyond the BP. Finally, the constructions we proposed can be adapted to any LDPC code whose Tanner graph can be represented by a set of trapping sets, making our studies relevant.

9 Fig. 1 .

 91 Fig. 1. Tanner graph of the TS(5,3)

  x r\q L r\q (x r\q )c r\q (xr)

  results of the algorithm, it helps to get a faster parallel algorithm. For any region r at iteration k we compute the beliefs:

Fig. 5 .

 5 Fig. 5. Damping factors, w 0 = 0.85

Fig. 6 .

 6 Fig. 6. BER k of the GBP on the Tanner code with the triplets construction, K = 100

Fig. 7 .

 7 Fig. 7. BER of the BP and the GBP with the classical construction on Hamming codes

Fig. 8 .

 8 Fig. 8. BER k of the BP and the GBPs on the Tanner code

ACKNOWLEDGMENT

This work was supported by the French ANR Defis program under contract ANR-08-EMER-003 (COCQ project).


Lorenzo Brasco
email: brasco@cmi.univ-mrs.fr

Giovanni Franzina
email: franzina@science.unitn.it

A NOTE ON POSITIVE EIGENFUNCTIONS AND HIDDEN CONVEXITY

Keywords: 1991 Mathematics Subject Classification. 35P30, 47A75 Nonlinear eigenvalue problems, uniqueness of eigenfunctions

We give a simple convexity-based proof of the following fact: the only eigenfunction of the p-Laplacian that does not change sign is the first one. The method of proof covers also more general nonlinear eigenvalue problems.

Introduction

Let Ω ⊂ R N be a connected open set and p ∈ (1, ∞). A (positive) number λ is said to be a Dirichlet eigenvalue of the p-Laplace operator if (1.1) -div (|∇u| p-2 ∇u) = λ |u| p-2 u, in Ω, holds for some nontrivial function u ∈ W 1,p 0 (Ω). In this case the function u is called eigenfunction. Here solutions to (1.1) are always intended in a weak sense. Observe that eigenvalues can be characterized as critical values of the nonlinear Dirichlet integral Ω |∇u| p , restricted to the manifold S p = {u ∈ W 1,p 0 (Ω) : u L p (Ω) = 1}. The corresponding critical points are the eigenfunctions, normalized by the constraint on the L p norm. The first eigenvalue λ 1 (Ω) plays a distinguished role, since it corresponds to the global minimum of the Dirichlet integral on S p . Modulo the choice of its sign, the first (normalized) eigenfuction is unique (see [START_REF] Belloni | A direct uniqueness proof for equations involving the p-Laplace operator[END_REF]).

The aim of this short note is to show that a subtle form of hidden convexity 1 implies the well-known result, that the only eigenfunctions with constant sign are the ones associated with λ 1 (Ω). This has been derived in various places, under different assumptions on the regularity of Ω (see [START_REF] Anane | Simplicité et isolation de la première valeur propre du p-Laplacien avec poids[END_REF][START_REF] Kawohl | Positive eigenfunctions for the p-Laplace operator revisited[END_REF][START_REF] Lindqvist | On the equation div (|∇| p-2 ∇u) + λ |u| p-2 u = 0[END_REF] and [START_REF] Ôtani | On the first eigenvalue of some quasilinear elliptic equations[END_REF] for example). We believe that the most simple and direct proof of this fact was given by Kawohl and Lindqvist ([4]), in turn inspired by [START_REF] Ôtani | On the first eigenvalue of some quasilinear elliptic equations[END_REF].

The proof in [START_REF] Kawohl | Positive eigenfunctions for the p-Laplace operator revisited[END_REF] is based on a clever use of the equation, but it does not clearly display the reason behind such a remarkable result. As we will show, it is just a matter of convexity of the energy functional Ω |∇u| p . More precisely, Ω |∇u| p enjoys a sort of geodesic convexity on the intersection between the cone of positive functions and the manifold S p . This allows one to conclude that on this space the global analysis of Ω |∇u| p is trivial, because convexity implies that there can not be any critical point, except for the global minimizer, which as already said is unique (except for its sign). In the end, we believe this to be the deep reason why it is impossible to have positive eigenfunctions corresponding to a λ > λ 1 (Ω).

The plan of this small note is the following. In the next section, we prove a convexity property of variational integrals, whose Lagrangians depend homogeneously on the gradient. This is a variation on the convexity principle used by Belloni and Kawohl in [START_REF] Belloni | A direct uniqueness proof for equations involving the p-Laplace operator[END_REF] (see also [START_REF] Belloni | The pseudo p-Laplace eigenvalue problem and viscosity solution as p → ∞[END_REF]), in order to prove the uniqueness of the first (normalized) eigenfunction of the p-Laplacian. Then, Section 3 shows how this convexity can be used to derive the above claimed result about positive eigenfunctions. For the sake of generality, we will give the result in a slightly more general version (see Theorem 3.1), that can be applied to more general nonlinear eigenvalue problems such as

(1.2) -div∇H(x, ∇u) = b(x) λ |u| p-2 u,
where H : Ω× R N → R is C 1 convex and p-positively homogeneous in the gradient variable and b ∈ L ∞ (Ω), with b ≥ 0.

The Hidden Convexity Lemma

The main tool of our proof is the following convexity principle, used by Belloni and Kawohl in [START_REF] Belloni | A direct uniqueness proof for equations involving the p-Laplace operator[END_REF] for the functional |∇u| p . In order to make the paper selfcontained, we repeat here the proof. The statement is slightly more general than in [START_REF] Belloni | A direct uniqueness proof for equations involving the p-Laplace operator[END_REF] so as to include a wider list of functionals. Moreover, we relax the strict posivity requirement on the functions.

Lemma 2.1. Given Ω ⊂ R N an open set, let p ≥ 1 and let H : Ω × R N → R + be a measurable function such that z → H(x, z) is convex and positively homogeneous of degree p, i.e. H(x, tz) = t p H(x, z) for every t ≥ 0, (x, z) ∈ Ω × R N . (2.1) If for every u 0 , u 1 ∈ W 1,p (Ω) such that u 0 , u 1 ≥ 0 on Ω and Ω H(x, ∇u i (x)) dx < +∞, i = 0, 1, σ t (x) is defined by σ t (x) := (1 -t) u 0 (x) p + t u 1 (x) p 1 p , t ∈ [0, 1], x ∈ Ω,
then the mapping

(2.2) t → Ω H(x, ∇σ t (x)) dx is convex on [0, 1].
Proof. We claim that

Ω H(x, ∇σ t (x)) dx ≤ (1 -t) Ω H(x, ∇u 0 (x)) dx + t Ω H(x, ∇u 1 (x)) dx, t ∈ [0, 1]. (2.3)
It is easily seen that for every t ∈ [0, 1], σ t defines an element of W 1,p (Ω). Indeed, this is nothing but the composition of the vector-valued Sobolev map

(1 -t)

1 p u 0 , t 1 p u 1 ∈ W 1,p (Ω; R 2 ),
with the ℓ p norm, i.e. (x, y) ℓ p = (|x| p + |y| p ) 1/p . Moreover, the latter is a C 1 function outside the origin and ∇u i vanishes almost everywhere on the set u -1 i ({0}), i = 0, 1. Thus the usual chain rule formula holds, i.e. we obtain

∇σ t = σ 1-p t (1 -t) ∇u 0 (x) u p-1 0 + t ∇u 1 (x) u p-1 1 = σ t (1 -t) u p 0 σ p t ∇u 0 u 0 + t u p 1 σ p t ∇u 1 u 1 ,
almost everywhere in Ω. Observe that the latter is a convex combination of ∇u 0 /u 0 and ∇u 1 /u 1 . Using the convexity and homogeneity of H in the z variable, we then get

H(x, ∇σ t ) ≤ σ p t (1 -t) u p 0 σ p t H x, ∇u 0 u 0 + t u p 1 σ p t H x, ∇u 1 u 1 = (1 -t) u p 0 H x, ∇u 0 u 0 + t u p 1 H x, ∇u 1 u 1 = (1 -t) H(x, ∇u 0 ) + t H(x, ∇u 1 ).
By integrating over Ω, the claim (2.3) is proved. Finally, for every t 0 , t 1 ∈ [0, 1] we have

σ (1-λ) t0+λ t1 = (1 -λ) σ p t0 + λ σ p t1 1 p , λ ∈ [0, 1].
Thus (2.2) follows by inequality (2.3), replacing u 0 and u 1 by σ t0 and σ t1 , respectively.

Remark 2.2. It is noteworthy that the curves of the form

σ t (x) = (1 -t) u 0 (x) p + t u 1 (x) p 1 p , t ∈ [0, 1],
are the constant speed geodesics of C p = {u ∈ L p (Ω) : u ≥ 0}, endowed with the metric

d p (u 0 , u 1 ) = Ω |u 0 (x) p -u 1 (x) p | dx 1 p
.

Indeed, we have

d p (σ t , σ s ) = Ω |σ t (x) p -σ s (x) p | dx 1 p = |t -s| Ω |u 0 (x) p -u 1 (x) p | dx 1 p = |t -s| d p (u 0 , u 1 ),
for all s, t ∈ [0, 1].

The main result

We are going to prove the main result of this note. The argument is very simple and just based on the convexity principle of Lemma 2.1, but a mild approximation argument is needed. Since this is essentially a uniqueness result, we do not insist on the sharp hypotheses needed to obtain existence for the problem defining λ 1 (Ω) below. Rather, we will directly assume that this is well-defined. In what follows, for simplicity we will denote by ∇H(x, z) the gradient of H with respect to the z variable.

Theorem 3.1. Let Ω ⊂ R N be an open set, having finite measure and p > 1. Let H : Ω × R N → R + be a function such that z → H(x, z) is C 1 convex and homogeneous of degree p, i.e.

H(x, tz) = |t| p H(x, z) for every t ∈ R, (x, z) ∈ Ω × R N . (3.1)
Assume that the variational problem

λ 1 (Ω) = min u∈W 1,p 0 (Ω) Ω H(x, ∇u) dx : u L p (Ω) = 1 ,
admits at least one solution. If there exist λ and a strictly positive v ∈ W 1,p 0 (Ω) such that

(3.2) 1 p Ω ∇H(x, ∇v(x)), ∇ϕ(x) dx = λ Ω |v(x)| p-2 v(x) ϕ(x) dx, for all ϕ ∈ W 1,p 0 (Ω), then (3.3) λ = λ 1 (Ω).
Proof. First of all, we can assume that v L p (Ω) = 1, since equation (3.2) is (p -1)homogeneous and v ≡ 0. Moreover, by testing the equation with ϕ = v and by homogeneity of H, we get

Ω H(x, ∇v(x)) dx = 1 p Ω ∇H(x, ∇v(x)), ∇v(x) dx = λ ≥ λ 1 (Ω),
since v is admissible for the problem defining λ 1 (Ω). Let us assume by contradiction that (3.3) is not true. This means that we have

(3.4) λ 1 (Ω) -λ < 0.
Then we take a minimizer u ∈ W 1,p 0 (Ω) for (3.3). Thanks to the homogeneity of H, we can suppose that u ≥ 0 without loss of generality. Indeed, the function u = |u| is nonnegative and still satisfies the constraint on the L p norm. Since H(x, z) = H(x, -z), we get H(x, ∇ u) = H(x, ∇u) almost everywhere and

Ω H(x, ∇ u(x)) dx = Ω H(x, ∇u(x)) dx = λ 1 (Ω).
For every ε ≪ 1, we set for simplicity

u ε = u + ε and v ε = v + ε.
Now we define as before the following curve of functions

σ t (x) = (1 -t) v ε (x) p + t u ε (x) p 1 p , x ∈ Ω, t ∈ [0, 1],
connecting v ε and u ε . By Lemma 2.1 we can infer that

Ω H(x, ∇σ t (x)) dx ≤ (1 -t) Ω H(x, ∇v ε (x)) dx + t Ω H(x, ∇u ε (x)) dx = t Ω H(x, ∇u(x)) dx - Ω H(x, ∇v(x)) dx + Ω H(x, ∇v ε (x)) dx, t ∈ [0, 1],
where we used that ∇u ε = ∇u and ∇v ε = ∇v. The last estimate implies that

Ω H(x, ∇σ t (x)) -H(x, ∇σ 0 (x)) t dx ≤ Ω H(x, ∇u(x)) -H(x, ∇v(x)) dx = λ 1 (Ω) -λ, t ∈ (0, 1],
where we used that σ 0 = v ε by construction. By the convexity of H in the left-hand side we can infer

Ω ∇H(x, ∇σ 0 (x)), ∇σ t (x) -∇σ 0 (x) t dx ≤ λ 1 (Ω) -λ.
Since ∇σ 0 = ∇v ε = ∇v, we can use the equation (3.2) and test it with ϕ = σ t -σ 0 ∈ W 1,p 0 (Ω). This yields

p λ Ω v(x) p-1 σ t (x) -σ 0 (x) t dx ≤ λ 1 (Ω) -λ, for every ε ≪ 1, t ∈ (0, 1].
We first pass to the limit as t goes to 0. Observe that by concavity of the function s → s 1/p , we have

v p-1 σ t -σ 0 t ≥ v p-1 (σ 1 -σ 0 ) = v p-1 (u ε -v ε ) ∈ L 1 (Ω), t ∈ (0, 1],
then by Fatou Lemma the limit as t goes to 0 gives

λ Ω v(x) v ε (x) p-1 u ε (x) p -v ε (x) p dx ≤ λ 1 (Ω) -λ, for every ε ≪ 1.
We now send ε to 0. Since u and v have the same L p norm, we finally end up with

0 = λ Ω u(x) p dx - Ω v(x) p dx ≤ λ 1 (Ω) -λ,
where we also used that v > 0 on Ω. This contradicts assumption (3.4), hence the Theorem is proved.

Remark 3.2. Observe that we required the solution v to (3.2) to be strictly positive on Ω. This is not a big deal, since in many situations of interest Harnack's inequality holds true and guarantees that nontrivial nonnegative solutions of (3.2) do not vanish at interior points of Ω. This is the case for example for H : Ω × R N → R + satisfying (3.1) and the growth conditions

c 1 |z| p ≤ H(x, z) ≤ c 2 |z| p , (x, z) ∈ Ω × R N , with two positive constants c 1 ≥ c 2 > 0.
The uniqueness of positive eigenfunctions of the p-Laplacian is now an easy consequence of Theorem 3.1.

Corollary 3 . 3 . 1 ( 1 . 3 . 4 .

 331134 Let Ω ⊂ R N be a connected open set having finite measure. Then the only Dirichlet eigenfunctions of the p-Laplacian having constant sign are those corresponding to the first eigenvalue, that is defined byλ )| p dx : u L p (Ω) =Remark The same conclusions can be drawn for the Dirichlet eigenfunctions of the so called pseudo p-Laplacian ∆ p , defined by∆ p u := N i=1 ∂ xi |∂ xi u| p-2 ∂ xi u .Here the eigenvalue problem (introduced in[START_REF] Belloni | The pseudo p-Laplace eigenvalue problem and viscosity solution as p → ∞[END_REF]) consists in finding the positive numbers λ > 0, such that the equation-∆ p u = λ |u| p-2 u,has nontrivial solutions in W 1,p 0 (Ω). The proof amounts to applying again Theorem 3.1, now with the variational integral N i=1 Ω |∂ xi u(x)| p dx. Remark 3.5. We observe that the statement of Theorem 3.1 holds true and the proof is exactly the same if we replace the L p constraint u L p (Ω) = 1 by the following weighted one Ω b(x) |u(x)| p dx = 1. Here b(x) is any nonnegative bounded measurable weight such that the nonlinear eigenvalue problem -div ∇H(x, ∇u(x)) = λ b(x) |u(x)| p-2 u(x), admits a first eigenfunction.

Acknowledgement. The authors would like to thank Bernd Kawohl for his kind interest in this work, as well as the Centre International de Rencontres Mathématiques (Marseille) and its facilities, where this paper has been written.


Florent Benaych-Georges

A UNIVERSALITY RESULT FOR THE GLOBAL FLUCTUATIONS OF THE EIGENVECTORS OF WIGNER MATRICES

Keywords: September 28, 2012. 2000 Mathematics Subject Classification. 15A52, 60F05 Random matrices, Haar measure, eigenvectors, Wigner matrices, bivariate Brownian motion, bivariate Brownian bridge

We prove that for [ui,j] n i,j=1 the eigenvectors matrix of a Wigner matrix, under some moments conditions, the bivariate random process 0

converges in distribution to a bivariate Brownian bridge. This result has already been proved for GOE and GUE matrices. It is conjectured here that the necessary and sufficient condition, for the result to be true for a general Wigner matrix, is the matching of the moments of orders 1, 2 and 4 of the entries of the Wigner with the ones of a GOE or GUE matrix. Surprisingly, the third moment of the entries of the Wigner matrix has no influence on the limit distribution.

Introduction

It is well known that the matrix U n = [u i,j ] n i,j=1 whose columns are the eigenvectors of a GOE or GUE matrix X n can be chosen to be distributed according to the Haar measure on the orthogonal or unitary group. As a consequence, much can be said about the u i,j 's: their joint moments can be computed via the so-called Weingarten calculus developed in [START_REF]Collins Moments and Cumulants of Polynomial Random Variables on Unitary Groups, the Itzykson-Zuber Integral, and Free Probability[END_REF][START_REF] Collins | Sniady Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF], any finite (or not too large) set of u i,j 's can be approximated, as n → ∞, by independent Gaussian variables (see [START_REF] Jiang | How many entries of a typical orthogonal matrix can be approximated by independent normals?[END_REF][START_REF] Chatterjee | Meckes Multivariate normal approximation using exchangeable pairs[END_REF]) and the global asymptotic fluctuations of the |u i,j |'s are governed by a theorem of Donati-Martin and Rouault, who proved in [START_REF] Donati-Martin | Rouault Truncations of Haar unitary matrices, traces and bivariate Brownian bridge[END_REF] that as n → ∞, the bivariate càdlàg process     B n s,t := β 2 1≤i≤ns, 1≤j≤nt

(|u i,j | 2 -1/n)     (s,t)∈[0,1] 2
(where β = 1 in the real case and β = 2 in the complex case) converges in distribution, for the Skorokhod topology, to the bivariate Brownian bridge, i.e. the centered continuous Gaussian process (B s,t ) (s,t)∈[0,1] 2 with covariance (1) E[B s,t B s ,t ] = (min{s, s } -ss )(min{t, t } -tt ).

A natural question is the following:

What can be said beyond the Gaussian case, when the entries of the Wigner matrix X n are general random variables ?

For a general Wigner matrix 1 , the exact distribution of the matrix U n cannot be computed and few works had been devoted to this subject until quite recently. One of the reasons is that while the eigenvalues of an Hermitian matrix admit variational characterizations as extremums of certain functions, the eigenvectors can be characterized as the argmax of these functions, hence are more sensitive to perturbations of the entries of the matrix. However, in the last three years, the eigenvectors of general Wigner matrices have been the object of a growing interest, due in part to some relations with the universality conjecture for the eigenvalues. In several papers (see, among others, [START_REF] Erdös | Yau Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices[END_REF][START_REF] Erdös | Local semicircle law and complete delocalization for Wigner random matrices[END_REF][START_REF] Erdös | Wegner estimate and level repulsion for Wigner random matrices[END_REF]), a delocalization property was shown for the eigenvectors of random matrices. More recently, Knowles and Yin in [START_REF] Knowles | Yin Eigenvector Distribution of Wigner Matrices[END_REF] and Tao and Vu in [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF] proved that if the first four moments of the atom distributions of X n coincide with the ones of a GOE or GUE matrix, then under some tail assumptions on these distributions, the u i,j 's can be approximated by independent Gaussian variables as long as we only consider a finite (or not too large) set of u i,j 's.

In this paper, we consider the global behavior of the |u i,j |'s. By global behavior, we mean that we consider functionals of the |u i,j |'s that involve all of them, at the difference of the works of Knowles and Yin in [START_REF] Knowles | Yin Eigenvector Distribution of Wigner Matrices[END_REF] and Tao and Vu in [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF]. Our work is in the same vein as Silverstein's paper [START_REF] Silverstein | Weak convergence of random functions defined by the eigenvectors of sample covariance matrices[END_REF] or Bai and Pan's paper [START_REF] Bai | Pan Limiting Behavior of Eigenvectors of Large Wigner Matrices[END_REF]. We prove (Theorem 2.3) that for Wigner matrices whose entries have moments of all orders, the process (B n s,t ) (s,t)∈[0,1] 2 has a limit in a weaker sense than for the Skorokhod topology and that this weak limit is the bivariate Brownian bridge if and only if the off-diagonal entries of the matrix have the same fourth moment as the GOE or GUE matrix (quite surprisingly, no hypothesis on the third moment is necessary). Under some additional hypotheses on the atom distributions (more coinciding moments and continuity), we prove the convergence for the Skorokhod topology (Theorem 2.6). This result was conjectured by Djalil Chafaï, who also conjectures the same kind of universality for unitary matrices appearing in other standard decompositions, such as the singular values decomposition or the Housholder decomposition of matrices with no symmetry, as long as the matrix considered has i.i.d. entries with first moments agreeing with the ones of Gaussian variables. It would also be interesting to consider the same type of question in the context of band matrices, connecting this problem with the so-called Anderson conjecture (see e.g. the works of Erdös and Knowles [START_REF] Erdös | Quantum Diffusion and Eigenfunction Delocalization in a Random Band Matrix Model[END_REF][START_REF] Erdös | Quantum Diffusion and Delocalization for Band Matrices with General Distribution[END_REF], of Schenker [START_REF] Schenker | Eigenvector localization for random band matrices with power law band width[END_REF] or of Sodin [START_REF] Sodin | The spectral edge of some random band matrices[END_REF], or, for a short introduction, the blog note by Chafaï [START_REF] Chafaï Anderson Localization | [END_REF]).

The paper is organized as follows. The main results are stated in Section 2, where we also make some comments on their hypotheses ; outlines of the proofs and the formal proofs are given in Section 3 ; and Section 4 is devoted to the definitions of the functional spaces and their topologies and to the proofs of several technical results needed in Section 3.

Acknowledgements: It is a pleasure for the author to thank Djalil Chafaï for having generously pointed out this problem to him and for the nice discussions we had about it. We also would like to thank Alice Guionnet, for her availability and her precious advices, and Terry Tao, who kindly and patiently answered several naive questions asked by the author on his blog. At last, we would like to thank the anonymous referee who pointed a mistake in the proof of Proposition 2.10 and brought the paper [START_REF] Bai | Pan Limiting Behavior of Eigenvectors of Large Wigner Matrices[END_REF] to the attention of the author. 1 A Wigner matrix is a real symmetric or Hermitian random matrix with independent, centered entries whose variance is one. Its atom distributions are the distributions of its entries.

Main results

For each n, let us consider a real symmetric or Hermitian random matrix

X n := 1 √ n [x (n) i,j ] n i,j=1 .
For notational brevity, x

i,j will be denoted by x i,j . Let us denote by λ 1 ≤ • • • ≤ λ n the eigenvalues of X n and consider an orthogonal or unitary matrix

U n = [u i,j ] n i,j=1 such that X n = U n diag(λ 1 , . . . , λ n )U * n .
Note that U n is not uniquely defined. However, one can choose it in any measurable way.

We define the bivariate càdlàg process

    B n s,t := β 2 1≤i≤ns, 1≤j≤nt (|u i,j | 2 -1/n)     (s,t)∈[0,1] 2
, where β = 1 in the real case and β = 2 in the complex case.

Assumption 2.1. For each n, the random variables x i,j 's are independent (up to the symmetry), with the same distribution on the diagonal and the same distribution above the diagonal.

Assumption 2.2. For each k ≥ 1, sup n E[|x 1,1 | k + |x 1,2 | k ] < ∞. Moreover, (2)
E[x 1,1 ] = E[x 1,2 ] = 0, E[|x 1,2 | 2 ] = 1 and E[|x 1,2 | 4 ] has a limit as n → ∞.
The bivariate Brownian bridge has been defined in the introduction and the definitions of the functional spaces and their topologies can be found in Section 4.1.

Theorem 2.3. Suppose that Assumptions 2.1 and 2.2 are satisfied. Then the sequence

(distribution(B n )) n≥1
has a unique possible accumulation point supported by C([0, 1] 2 ). This accumulation point is the distribution of a centered Gaussian process which depends on the distributions of the x i,j 's only through

lim n→∞ E[|x 1,2 | 4 ],
and which is the bivariate Brownian bridge if and only if

lim n→∞ E[|x 1,2 | 4 ] = 4 -β.
More precisions about the way the unique possible accumulation point depends on the fourth moment of the entries are given in Remark 2.8.

To get a stronger statement where the convergence in distribution to the bivariate Brownian bridge is actually stated, one needs stronger hypotheses.

Assumption 2.4. The distributions of the entries of X n are absolutely continuous with respect to the Lebesgue measure.

The following hypothesis depends on an integer m ≥ 2.

Assumption 2.5. For each k ≥ 1, sup n E[|x 1,1 | k + |x 1,2 | k ] < ∞. Moreover, for each r, s ≥ 0, (3) r + s ≤ m -2 =⇒ E[ (x 1,1 ) r (x 1,1 ) s ] = E[ (g 1,1 ) r (g 1,1 ) s ]
and

(4) r + s ≤ m =⇒ E[ (x 1,2 ) r (x 1,2 ) s ] = E[ (g 1,2 ) r (g 1,2 ) s ].
where the g i,j 's are the entries of a standard GOE or GUE matrix.

Theorem 2.6. Suppose that Assumptions 2.1 and 2.4 are satisfied, as well as Assumption 2.5 for m = 12. Then, as n → ∞, the bivariate process B n converges in distribution, for the Skorokhod topology in D([0, 1] 2 ), to the bivariate Brownian bridge.

Remark 2.7. Weakening of the assumptions. As explained above, the distributions of the entries x i,j = x (n) i,j are allowed to depend on n. In order to remove Assumption 2.4 below (which we did not manage to do yet), it mights be useful to weaken Assumptions 2.2 and 2.5 in the following way: one can easily see that the proofs of Theorems 2.3 and 2.6 and Proposition 2.10 still work if, in Equations ( 2), ( 3) and ( 4), one replaces the identities by the same identities up to an error which is O(n -α ) for all α > 0.

Remark 2.8. Complements on Theorem 2.3. One can wonder how the unique accumulation point mentioned in Theorem 2.3 depends on the fourth moment of the entries of X n . Let G := (G s,t ) (s,t)∈[0,1] 2 be distributed according to this distribution. We know that (G s,t ) (s,t)∈[0,1] 2 is the bivariate Brownian bridge only in the case where lim n→∞ E[|x 1,2 | 4 ] = 4 -β. In the other cases, defining F semicircle as the cumulative distribution function of the semicircle law, the covariance of the centered Gaussian process (5)

2 u=-2 u k G s,F semicircle (u) du s∈[0,1],k≥0
can be computed thanks to Lemma 3.4 and Proposition 3.5. By Lemma 3.3, it determines completely the distribution of the process G. However, making the covariance of G explicit out of the covariance of the process of ( 5) is a very delicate problem, and we shall only stay at a quite vague level, saying that it can be deduced from the proof of Proposition 3.5 that the variances of the one-dimensional marginals of G are increasing functions of lim n→∞ E[|x 1,2 | 4 ]. More specifically, one can deduce from Lemma 3.4 and Proposition 3.5 that for all 0 ≤ s 1 , s 2 ≤ 1,

Cov 2 u=-2 u 2 G s 1 ,F semicircle (u) du, 2 u=-2 u 2 G s 2 ,F semicircle (u) du = E[|x 1,2 | 4 ] -1 4 (min{s 1 , s 2 } -s 1 s 2 ).
Remark 2.9. Comments on the hypotheses of Theorem 2.6 [START_REF] Anderson | An Introduction to Random Matrices[END_REF]. In order to prove the convergence in the Skorokhod topology, we had to make several hypotheses on the atom distributions: absolute continuity, moments of all orders and coincidence of their 10 (on the diagonal) and 12 (above the diagonal) first moments with the ones of a GOE or GUE matrix. We needed these assumptions to control the discontinuities of the process B n . Even though these hypotheses might not be optimal (especially the continuity one), a bound on the tails of the atom distributions seems to be necessary to avoid too large variations of the process B n . Indeed, as illustrated by Figure 1, for a GOE matrix (left picture), |u i,j | 2 is close to 1/n for all i, j with high probability, whereas when the atom distributions have not more than a second moment (right picture), the matrix X n looks more like a sparse matrix, and so does U n , which implies that for certain (i, j)'s, |u i,j | 2 -1/n is not small enough. Since |u i,j | 2 -1/n is the jump of the process B n at (s, t) = (i/n, j/n), this could be an obstruction to the existence Note that it follows from the previous theorem that for all 0 ≤ s < s ≤ 1 and 0 ≤ t < t ≤ 1, the sequence of random variables 1

(s -s)(t -t) ns<i≤ns nt<j≤nt (|u i,j | 2 -1/n)
admits a limit in distribution as n → ∞, hence is bounded in probability (in the sense of [START_REF] Tao | with an appendix by M. Krishnapur) Random matrices: Universality of ESDs and the circular law[END_REF]Def. 1.1]). In the same way, it follows from [START_REF] Knowles | Yin Eigenvector Distribution of Wigner Matrices[END_REF] and [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF] that the sequence n|u i,j | 2 -1 is bounded in probability. In the next proposition, we improve these assertions by making them uniform on s, s , t, t , i, j and upgrading them to the L 2 and L 4 levels. The proof of the proposition is postponed to Section 4.5.

Proposition 2.10. Suppose that Assumptions 2.1, 2.4 and 2.5 for m = 4 (resp. m = 8) are satisfied. Then as n → ∞, the sequence

(6) n|u i,j | 2 -1 (resp. 1 (s -s)(t -t) ns<i≤ns nt<j≤nt (|u i,j | 2 -1/n) )
is bounded for the L 4 (resp. L 2 ) norm, uniformly in i, j (resp. s < s , t < t ,).

Remark 2.11. Comments on the hypotheses of Theorem 2.6 (2). This proposition is almost sufficient to apply the tightness criterion that we use in this paper. Would the second term of ( 6) have been bounded for the L 2+ε norm (instead of L 2 ), Assumption 2.5 for m = 8 would have been enough to prove that B n converges in distribution, for the Skorokhod topology in D([0, 1] 2 ), to the bivariate Brownian bridge.

3. Proofs of Theorems 2.3 and 2.6

3.1. Outline of the proofs. Firstly, Theorem 2.6 can be deduced from Theorem 2.3 by proving that the sequence (distribution(B n )) n≥1 is tight and only has C([0, 1] 2 )-supported accumulation points. This can be done via some upper bounds on the fourth moment of the increments of B n and on its jumps (or discontinuities). These bounds are given in the proof of Lemma 3.1 below, and rely on the existing bounds in the case where X n is a GOE or GUE matrix and on the "one-by-one entries replacement method" developed by Terence Tao and Van Vu in recent papers, such as [START_REF] Tao | Vu Random matrices: universality of local eigenvalue statistics[END_REF][START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF].

Secondly, the proof of Theorem 2.3 relies on the following remark, inspired by some ideas of Jack Silverstein (see [START_REF] Bai | Silverstein Spectral analysis of large dimensional random matrices[END_REF]Chap. 10] and [START_REF] Silverstein | Weak convergence of random functions defined by the eigenvectors of sample covariance matrices[END_REF]): even though we do not have any "direct access" to the eigenvectors of X n , we have access to the process (B n s,Fµ Xn (u) ) s∈[0,1],u∈R , for

F µ Xn (u) := 1 n #{i ; λ i ≤ u}. Indeed, B n s,Fµ Xn (u) = β 2 1≤i≤ns 1≤j≤n s.t. λ j ≤u (|u i,j | 2 -1/n), hence for all fixed s ∈ [0, 1], the function u ∈ R -→ B n s,Fµ Xn (u) is the cumulative distribution function of the signed measure 2 (7) β 2 1≤i≤ns n j=1 (|u i,j | 2 -1/n)δ λ j ,
which can be studied via its moments

1≤i≤ns e * i X k n e i - 1 n Tr X k n (k ≥ 1)
, the e i 's being the vectors of the canonical basis. From the asymptotic behavior of the moments of the signed measure of (7), one can then find out the asymptotic behavior of its cumulative distribution function.

Once the asymptotic distribution of the process (B n s,Fµ Xn (u) ) s∈[0,1],u∈R identified, one can obtain the asymptotic distribution of the process (B n s,t ) s∈[0,1],t∈[0,1] because the function F µ Xn tends to the (non random) cumulative distribution function F semicircle of the semicircle law. So let us now prove Theorem 2.3 under Assumptions 2.1 and 2.2. Note that it suffices to prove that the sequence (distribution(B n )) n≥1 has a unique possible accumulation point supported by C([0, 1] 2 ) and that this accumulation point is the distribution of a centered Gaussian process which depends on the distributions of the x i,j 's only through lim n→∞ E[|x 1,2 | 4 ] (and actually 2 Note that the random probability measures P n j=1 |ui,j| 2 δ λ j have been studied in [START_REF] Bai | Pan Limiting Behavior of Eigenvectors of Large Wigner Matrices[END_REF] (convergence to the semicircle law and fluctuations). Here, we are somehow considering the fluctuations of large sums of such random probability measures (1 ≤ i ≤ ns) around the empirical spectral law The following proposition is the key of the proof, since it allows to transfer the problem from the eigenvectors to some more accessible objects: the weighted spectral distributions of X n . Proposition 3.2. Let e i denote the ith vector of the canonical basis. To prove Theorem 2.3, it suffices to prove that each finite-dimentional marginal distribution of the process

  1≤i≤ns e * i X k n e i - 1 n Tr X k n   s∈[0,1],k≥1
converges to a centered Gaussian measure and that the covariance of the limit process depends on the distributions of the x i,j 's only through

lim n→∞ E[|x 1,2 | 4
] and actually does depend on

lim n→∞ E[|x 1,2 | 4 ].
Proof. Let µ Xn := 1 n n i=1 δ λ i be the empirical spectral law of X n and F µ Xn (u) := 1 n #{i ; λ i ≤ u} be its cumulative distribution function. It is a well known result [3, Th. 2.5] that F µ Xn converges in probability, as n tends to infinity, to the cumulative distribution function F semicircle of the semicircle law in the space D c (R, [0, 1]) (see Section 4.1 for the definitions of the functional spaces and their topologies). Moreover, the map

D 0 ([0, 1] 2 ) × D c (R, [0, 1]) -→ D c ([0, 1] × R) ((G s,t ) s,t∈[0,1] , (g(u)) u∈R ) -→ (G s,g(u) ) (s,u)∈[0,1]×R
is continuous at any pair of continuous functions. Hence for any continuous process (B s,t ) s,t∈[0,1] whose distribution is an accumulation point of the sequence (distribution(B n )) n≥1 for the Skorokhod topology in D([0, 1] 2 ), the process

(B n s,Fµ Xn (u) ) (s,u)∈[0,1]×R
converges in distribution (up to the extraction of a subsequence) to the process

(B s,F semicircle (u) ) (s,u)∈[0,1]×R
(for the reader who is not used to weak convergence of probability measures, this assertion relies on two results which can be found in [START_REF] Billingsley | Convergence of Probability Measures[END_REF]: Theorem 4.4 and Corollary 1 of Theorem 5.1 in Chapter 1). Now, note that F semicircle : R → [0, 1] admits a right inverse, so the distribution of the process (B s,t ) s,t∈[0,1] is entirely determined by the one of the process (B s,

F semicircle (u) ) (s,u)∈[0,1]×R .
As a consequence, to prove Theorem 2.3, it suffices to prove that the sequence

(8) distribution((B n s,Fµ Xn (u) ) (s,u)∈[0,1]×R ) n≥1 has a unique possible C c ([0, 1] × R)-supported accumulation point as n → ∞. Now, note that any f ∈ C c ([0, 1] × R
) is entirely determined by the collection of real numbers ( u∈R u k f (s, u)du) s∈[0,1],k≥0 . Let us prove that this fact remains true in the "distribution sense" in the case where f is random. More precisely, let us prove the following lemma. Lemma 3.3. Let f be a random variable taking values in C c ([0, 1]×R) such that with probability one, f (s, u) = 0 when |u| > 2. Then the distribution of f is entirely determined by the finite dimensional marginals of the process

(9) u∈R u k f (s, u)du s∈[0,1],k≥0
. Moreover, in the case where the finite dimensional marginals of the process of (9) are Gaussian and centered, then so are the ones of f .

Proof. Let us fix (s, u 0 ) ∈ [0, 1] × [-2, 2] and let, for each p ≥ 1, (P p,q ) q≥1 be a sequence of polynomials that is uniformly bounded on [-3, 3] and that converges pointwise to 1 [u 0 ,u 0 +1/p] on [-3, 3]. Then one has, with probability one,

f (s, u 0 ) = lim p→∞ p u 0 +1/p u 0 f (s, u)du = lim p→∞ lim q→∞ p u∈R P p,q (u)f (s, u)du.
This proves the lemma, because any almost sure limit of a sequence of variables belonging to a space of centered Gaussian variables is Gaussian and centered.

Since the fourth moment of the entries of X n is bounded, by e.g. [3, Th. 5.1], we know that the extreme eigenvalues of X n converge to -2 and 2. As a consequence, for any random variable f taking values in C c ([0, 1] × R) such that the distribution of f is a limit point of the sequence of ( 8), we know that with probability one, f (s, u) = 0 when |u| > 2.

As a consequence, it follows from the previous lemma and from what precedes that to prove Theorem 2.3, it suffices to prove that each finite dimensional marginal distribution of the process

u∈R u k B n s,Fµ Xn (u) du s∈[0,1],k≥0
converges to a centered Gaussian measure and that the covariance of the limit process depends on the distributions of the x i,j 's only through lim n→∞ E[|x 1,2 | 4 ] and actually does depend on

lim n→∞ E[|x 1,2 | 4 ].
But for all (s, u)

∈ [0, 1] × R, B n s,Fµ Xn (u) = β 2 1≤i≤ns 1≤j≤n s.t. λ j ≤u (|u i,j | 2 -1/n), hence (10)
B n s,Fµ Xn (u) = β 2 1≤i≤ns F µ Xn,e i -µ Xn (u),
where:

• µ Xn is still the empirical spectral law of X n , • µ Xn,e i is the weighted spectral law of X n , defined by µ Xn,e i := n j=1 |u i,j | 2 δ λ j , • F µ Xn,e i -µ Xn is the cumulative distribution function of the null-mass signed measure µ Xn,e i -µ Xn .

The following lemma will allow to conclude the proof of Proposition 3.2.

Lemma 3.4. Let µ be a compactly supported null-mass signed measure and set F µ (u) := µ((-∞, u]). Then for all k ≥ 0,

u∈R u k F µ (u)du = - x∈R x k+1 k + 1 dµ(x).
Proof. Let a < b be such that the support of µ is contained in the open interval (a, b). F µ is null out of (a, b) and satisfies F µ (u) = -µ((u, b)), so by Fubini's Theorem,

u∈R u k F µ (u)du = b x=a x u=a -u k dudµ(x) = b x=a -x k+1 k + 1 dµ(x) + a k+1 k + 1 µ((a, b)) = b x=a -x k+1 k + 1 dµ(x).
It follows from this lemma and from ( 10) that for all s ∈ [0, 1], k ≥ 0,

u∈R u k B n s,Fµ Xn (u) du = -1 k + 1 β 2 1≤i≤ns e * i X k+1 n e i - 1
e i - 1 n Tr(X k n ))   s∈[0,1],k≥1
converges to a centered Gaussian measure. The covariance of the limit distribution, denoted by

(Cov s 1 ,s 2 (k 1 , k 2 )) s 1 ,s 2 ∈[0,1],k 1 ,k 2 ≥1 ,
depends on the distributions of the x i,j 's only through

lim n→∞ E[|x 1,2 | 4 ]. Moreover, we have Cov s 1 ,s 2 (2, 2) = ( lim n→∞ E[|x 1,2 | 4 ] -1)(min{s 1 , s 2 } -s 1 s 2 ).

Proofs of the technical results

4.1. Functional spaces and associated topologies. In this paper, we use several functional spaces:

• C([0, 1] 2 ) (resp. C c ([0, 1] × R))
is the set of continuous functions on [0, 1] 2 (resp. compactly supported continuous function on [0, 1]×R), endowed with the uniform convergence topology.

• D c (R, [0, 1]) is the set of compactly supported càdlàg functions on R taking values in [0, 1], endowed with the topology defined by the fact that f n -→ f if and only if the bounds of the support of f n tend to the ones of the support of f and for all M > 0, after restriction to [-M, M ], f n -→ f (the topology of D([-M, M ]) being deduced from the one of D([0, 1]) defined in [START_REF] Billingsley | Convergence of Probability Measures[END_REF]).

• D([0, 1] 2 ) (resp. D c ([0, 1] × R)) is the set of functions f : [0, 1] 2 → R (resp. of compactly supported functions f : [0, 1] × R → R)
admitting limits in all "orthants", more precisely such that for each s 0 , t 0 , for each pair of symbols , ∈ {<, ≥},

lim s s 0 t t 0 f (s, t)
exists, and is equal to f (s 0 , t 0 ) if both and are ≥. The space D([0, 1] 2 ) is endowed with the Skorokhod topology defined in [START_REF] Bickel | Wichura Convergence criteria for multiparameter stochastic processes and some applications[END_REF] and the space D c ([0, 1] × R) is endowed with the topology defined by f n -→ f if and only if for all M > 0, after restriction to

[0, 1] × [-M, M ], f n -→ f (the topology of D([0, 1] × [-M, M ]) being deduced from the one of D([0, 1] 2 )).
• D 0 ([0, 1] 2 ) is the set of functions in D([0, 1] 2 ) vanishing at the border of [0, 1] 2 , endowed with the induced topology.

4.2. Proof of Proposition 3.5. Note that by invariance of the law of X n under conjugation by any permutation matrix, the expectation of the random law µ Xn,e i does not depend on i. So for all s

∈ [0, 1], k ≥ 1, (11)
1≤i≤ns

(e * i X k n e i - 1 n Tr(X k n )) = 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ]) - ns n 1≤i≤n (e * i X k n e i -E[e * i X k n e i ]).
Hence we are led to study the limit, as n → ∞, of the finite-dimentional marginal distributions of the process

(12)   1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])   s∈[0,1],k≥1
The random variables of ( 12) are going to be studied via their joint moments. So let us fix p ≥ 1, s 1 , . . . , s p ∈ [0, 1] and k 1 , . . . , k p ≥ 1. We shall study the limit, as n tends to infinity, of ( 13)

E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])].
We introduce the set ( 14)

E := {0 1 , . . . . . . , k 1 1 } ∪ • • • • • • • • • • • • ∪ {0 p , . . . . . . , k p p },
where the sets {0 [START_REF] Erdös | Yau Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices[END_REF]. For each partition π of E, for each x ∈ E, we denote by π(x) the index of the class of x, after having ordered the classes according to the order of their first element (for example, π(1

1 ) = 1; π(2 1 ) = 1 if 1 1 π ∼ 2 1 and π(2 1 ) = 2 if 1 1 π 2 1 )
.

By Assumption 2.1, the expectation of ( 13) can be expanded and expressed as a sum on the set Part(E) of partitions of the set E introduced above. We get

E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])] = (15) n -k 1 +•••+kp 2 π∈Part(E) A(n, π)E p =1 x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) -E[x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) ] ,
where for each π ∈ Part(E), A(n, π) is the number of families of indices of (i 0 1 , . . . , i k 1 1 , i 0 2 , . . . , i k 2 2 , . . . . . . . . . , i 0 p , . . . , i kp p ) ∈ {1, . . . , n} E whose level sets partition is π and who satisfy, for each = 1, . . . , p,

(16) 1 ≤ i 0 = i k ≤ ns .
For any π ∈ Part(E), let us define G π to be the graph with vertex set the set {π(x) ; x ∈ E} and edge set

E π := { {π(m -1 ), π(m )} ; 1 ≤ ≤ p, m ∈ {1, . . . , k } }.
For the term associated to π in [START_REF] Erdös | Local semicircle law and complete delocalization for Wigner random matrices[END_REF] to be non zero, we need to have: (i) π(0 ) = π(k ) for each = 1, . . . , p, (ii) each edge of G π is visited at least twice by the union of the p paths (π(0 ), . . . . . . , π(k )) ( = 1, . . . , p), (iii) for each = 1, . . . , p, the exists = such that at least one edge of G π is visited by both paths (π(0 ), . . . . . . , π(k )) and (π(0 ), . . . . . . , π(k )). Indeed, (i) is due to ( 16), (ii) is due to the fact that the x i,j 's are centered and (iii) is due to the fact the the x i,j 's are independent.

Let us define a function s(•) on the set E in the following way: for each = 1, . . . , p and each m = 0, . . . , k , set

s(m ) = s if m = 0 or m = k , 1 otherwise, and (17)
s π := B bloc of π min x∈B s(x).
Then one can easily see that, as n → ∞,

(18) A(n, π) ∼ s π n |π| .
Thus for π to have a non zero asymptotic contribution to [START_REF] Erdös | Local semicircle law and complete delocalization for Wigner random matrices[END_REF], we need the following condition, in addition to (i), (ii) and (iii):

(iv)

k 1 +•••+kp 2 ≤ |π|.
The following lemma is a generalization of [1, Lem. 2.1.34]. Its proof goes along the same lines as the proof of the former.

|π| ≤ c π - p 2 + k 1 + • • • + k p 2 .
As a consequence, if π also satisfies (iv), we have

(a) c π = p/2, (b) p is even, (c) |π| = k 1 +•••+kp 2 (so that k 1 + • • • + k p is also even).
Note also that by (ii), we also have

(d) |E π | ≤ k 1 +•••+kp 2 .
To sum up, by ( 15) and ( 18), we have

lim n→∞ E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])] = (19) π s π lim n→∞ E p =1 x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) -E[x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) ] ,
where the sum is taken over the partitions π of E which satisfy (i), (ii), (iii) and (iv) above, and such partitions also do satisfy (a), (b), (c) and (d) above.

Case where p is odd: By (b), we know that when p is odd, there is no partition π satisfying the above conditions. So by [START_REF] Jiang | A variance formula related to a quantum conductance problem[END_REF],

lim n→∞ E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])] = 0.
Case where p = 2: In this case, by (a), for each partition π satisfying (i), (ii), (iii) and (iv),

G π is connected, so that |π| -1 ≤ |E π |. Hence by (c) and (d), |E π | is either equal to k 1 +k 2 2 or to k 1 +k 2 2 -1.
In the case where

|E π | = k 1 +k 2 2
-1, the graph G π has exactly one more vertex than edges, hence is a tree. As a consequence, the paths (π(0 1 ), . . . . . . , π(k 1 1 )) and (π(0 2 ), . . . . . . , π(k 2 2 )), which have the same beginning and ending vertices, have the property to visit an even number of times each edge they visit. By an obvious cardinality argument, only one edge is visited more than twice, and it is visited four times (twice in each sense). The other edges are visited once in each sense. It follows that the expectation associated to π in ( 19) is equal to

E[|x 1,2 | 4 ] -1.
In the case where

|E π | = k 1 +k 2 2
, by a cardinality argument again, we see that each edge of G π is visited exactly twice (in fact, the configuration is the one described in [1, Sect. 2.1.7], where G π is a bracelet). It follows that the expectation associated to π in [START_REF] Jiang | A variance formula related to a quantum conductance problem[END_REF] is equal to 1.

As a consequence, as n tends to infinity,

E   1≤i≤ns 1 (e * i X k 1 n e i -E[e * i X k 1 n e i ]) × 1≤i≤ns 2 (e * i X k 2 n e i -E[e * i X k 2 n e i ])  
converges to a number that we shall denote by

(20) Cov centered s 1 ,s 2 (k 1 , k 2 )
and which depends on the distributions of the x i,j 's only through

lim n→∞ E[|x 1,2 | 4 ].
Case where p is > 2 and even: By (a) above, for each partition π satisfying (i), (ii), (iii) and (iv), G π has exactly p/2 connected components. By (iii), each of them contains the support of exactly two of the p paths Let us define σ π to be the matching (i.e. a permutation all of whose cycles have length two) of {1, . . . , p} such that for all = 1, . . . , p, the paths with indices and σ π ( ) of the collection [START_REF] Schenker | Eigenvector localization for random band matrices with power law band width[END_REF] above are supported by the same connected component of G π .

We shall now partition the sum of ( 19) according to the value of the matching σ π defined by π. We get

lim n→∞ E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])] = σ π s π lim n→∞ E p =1 x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) -E[x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) ] ,
where the first sum is over the matchings σ of {1, . . . , p} and the second sum is over the partitions π satisfying (i), (ii), (iii) and (iv) such that σ π = σ.

Note that for each matching σ of {1, . . . , p}, the set of partitions π of E such that σ π = σ can be identified with the cartesian product, indexed by the set of cycles { , } of σ, of the set of partitions τ of the set

E , := {0 , . . . . . . , k } ∪ {0 , . . . . . . , k } (subset of E)
satisfying the following conditions

(i.2) τ (0 ) = τ (k ) and τ (0 ) = τ (k ), (ii.
2) each edge of the graph G τ is visited at least twice by the union of the 2 paths (τ (0 ), . . . . . . , τ (k ))

and (τ (0 ), . . . . . . , τ (k )), (iii.2) at least one edge of G τ is visited by both previous paths, (iv.2)

k +k 2 ≤ |τ |.
Moreover, by independence of the random variables x i,j 's, the expectation

E p =1 x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) -E[x π(0 ),π(1 ) • • • x π(k -1 ),π(k ) ]
factorizes along the connected components of G π . The factor s π , defined in [START_REF] Jacod | Shiryaev Limit theorems for stochastic processes[END_REF], also factorizes along the connected components of G π . It follows that we have

lim n→∞ E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])] = σ { , } lim n→∞ E 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ]) × 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ]) ,
where the sum is over the matchings σ of {1, . . . , p} and for each such σ, the product is over the cycles { , } of σ.

By the definition of Cov centered

s 1 ,s 2 (k 1 , k 2 ) in (20), we get lim n→∞ E[ p =1 1≤i≤ns (e * i X k n e i -E[e * i X k n e i ])] = σ matching { , } cycle of σ Cov centered s ,s (k , k ).
By Wick's formula and Equation [START_REF] Donati-Martin | Rouault Truncations of Haar unitary matrices, traces and bivariate Brownian bridge[END_REF], we have proved the first part of Proposition 3.5.

Computation of

s π × ( lim n→∞ E[|x 1,2 | 4 ] -1) + π, Gπ is a bracelet s π .
There is exactly one tree and zero bracelet with 2 vertices. We represent this tree in the following way: • -•. There are two associated partitions π:

-the first one is defined by

(π(0 1 ), π(1 1 ), π(2 1 )) = (π(0 2 ), π(1 2 ), π(2 2 )) = (•, •, •),
and satisfies s π = min{s 1 , s 2 }, -the second one is defined by

(π(0 1 ), π(1 1 ), π(2 1 )) = (•, •, •) , (π(0 2 ), π(1 2 ), π(2 2 )) = (•, •, •),
and satisfies s π = s 1 s 2 .

As a consequence, Cov centered

s 1 ,s 2 (2, 2) = (lim n→∞ E[|x 1,2 | 4 ] -1)(min{s 1 , s 2 } + s 1 s 2 ).
From this formula and Equation ( 11), we easily deduce the formula of Cov s 1 ,s 2 (2, 2). It concludes the proof of Proposition 3.5.

4.3.

A preliminary result for the proofs of Proposition 2.10 and Lemma 3.1. Proposition 4.3 below will allow to prove Lemma 3.1. Let us now consider two independent Wigner matrices X n , X n . Let us introduce a modified version of Assumption 2.5, also depending on an integer m ≥ 2:

Assumption 4.2. For each k ≥ 1, sup n E[|x 1,1 | k + |x 1,2 | k + |x 1,1 | k + |x 1,2 | k ] < ∞.
Moreover, there exists ε 0 > 0 such that for each r, s ≥ 0, [START_REF] Silverstein | Weak convergence of random functions defined by the eigenvectors of sample covariance matrices[END_REF] r

+ s ≤ m -2 =⇒ E[ (x 1,1 ) r (x 1,1 ) s ] -E[ (x 1,1 ) r (x 1,1 ) s ] = O(n -ε 0 +1+ r+s-m 2 )
and

(23) r + s ≤ m =⇒ E[ (x 1,2 ) r (x 1,2 ) s ] -E[ (x 1,2 ) r (x 1,2 ) s ] = O(n -ε 0 + r+s-m 2
).

Let U n = [u i,j ] n i,j=1 be the associated eigenvectors matrix of a matrix X n (like

U n = [u i,j ] n i,j=1
for X n ).

Proposition 4.3. We suppose that X n , X n both satisfy Assumptions 2.1 and 2.4, and satisfy Assumption 4.2. Let us fix a positive integer k and a polynomial function G on C k . For each n, let us consider a collection (i 1 , p 1 , q 1 ), . . . , (i k , p k , q k ) ∈ {1, . . . , n} 3 (this collection might depend on n). Then for a certain constant C independent of n and of the choices of (i 1 , p 1 , q 1 ), . . . , (i k , p k , q k ) (but depending on k and on G)

(24) | E[G(n u p 1 ,i 1 u q 1 ,i 1 , . . . , n u p k ,i k u q k ,i k )] -E[G(n u p 1 ,i 1 u q 1 ,i 1 , . . . , n u p k ,i k u q k ,i k )] | ≤ Cn 2-m 2 .
Proof. The proof follows the ideas developed by Terence Tao and Van Vu in recent papers, such as [START_REF] Tao | Vu Random matrices: universality of local eigenvalue statistics[END_REF][START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF]. More precisely, it makes an intensive use of the strategy and of some estimations given in [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF].

An event E = E (n) depending on the parameter n will be said to be true with overwhelming probability if for all c > 0, 1 -P(E) = O(n -c ). One can neglect any such event in the proof of [START_REF] Tao | with an appendix by M. Krishnapur) Random matrices: Universality of ESDs and the circular law[END_REF] because G has polynomial growth and the entries of unitary matrices are bounded by 1. By Assumption 2.5 and Chebyshev's inequality, that for each k, as t → ∞,

P(|x i,j | ≥ t) = O(t -k )
(uniformly in i, j and n), so that by the union bound, P(max 1≤i,j≤n |x i,j | ≥ n ε ) = O(n 2-kε ) for any ε, k. Hence by what precedes, for a fixed ε 1 (a parameter fixed later), one can suppose that for each n, the x i,j 's satisfy |x i,j | ≤ n ε 1 for all i, j. Of course, one can also suppose that |x i,j | ≤ n ε 1 for all i, j.

To prove [START_REF] Tao | with an appendix by M. Krishnapur) Random matrices: Universality of ESDs and the circular law[END_REF], it suffices to prove that we can replace the x i,j 's by the x i,j 's one by one up to an error in the considered expectation which is O(n 1-m 2 ) for each diagonal replacement and O(n -m 2 ) for each off-diagonal replacement (and, of course, that these bounds on the errors are uniform in the n(n+1) 2 replacements). So let us fix 1 ≤ p ≤ q ≤ n and define, for each z ∈ C (or z ∈ R if p = q), A p,q (z) be the matrix obtained by "mixing" the (rescaled) matrices X n and X n in the following way:

• for each 1 ≤ i ≤ j ≤ n such that (i, j) is below (p, q) for the lexicographic order, the i, j entry of A p,q (z) and its symmetric one are the corresponding ones in the entries of nX n , • the p, q entry of A p,q (z) and its symmetric one are z and z, • for each 1 ≤ i ≤ j ≤ n such that (i, j) is above (p, q) for the lexicographic order, the i, j entry of A p,q (z) and its symmetric one are the corresponding ones in the entries of nX n .

We set U (z) = [u i,j (z)] n i,j=1 to be the eigenvectors matrix of A p,q (z) and

F (z) := G(n u p 1 ,i 1 (z)u q 1 ,i 1 (z), . . . , n u p k ,i k (z)u q k ,i k (z)). Let E[ • | A p,q (0
)] denote the conditional expectation with respect to the σ-algebra generated by the entries of A p,q (0). We have to prove that with overwhelming probability, we have, uniformly on the probability space and on p, q,

E[F ( √ nx p,q ) | A p,q (0)] = E[F ( √ nx p,q ) | A p,q (0)] + O(n 1p=q-m 2 ). (25)
To prove it, we shall use the Taylor expansion of F around zero. Let us for example treat the case p = q. For |x| ≤ n ε 1 , we have

F ( √ nx) = r+s≤m n r+s 2 r!s! ∂ r (z) ∂ s (z) F (0) (x) s (x) s +O   n (m+1)(ε 1 +1/2) sup r+s=m+1 |z|≤n ε 1 +1/2 |∂ r (z) ∂ s (z) F (z)|    .
Moreover, by [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF]Propo. 20], we know that with overwhelming probability, A p,q (0) is a good configuration (in the sense of [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF]Def. 18]). By Equation ( 27) of [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF]Lem. 24], it implies that with overwhelming probability, for all l = 1, . . . , k, for all r, s such that r + s ≤ 10, sup

|z|≤n 1/2+ε 1 |∂ r (z) ∂ s (z) (nu p l ,i l (z)u q l ,i l (z)|) = O(n ε 1 -(r+s) )
(in the statement of [START_REF] Tao | Vu Random matrices: Universal properties of eigenvectors[END_REF]Lem. 24], m must be bounded above by 10, but the bound 10 can be replaced by any finite one). The function G is polynomial, let d be its degree. It follows that with overwhelming probability, for all r, s, we have sup

|z|≤n 1/2+ε 1 |∂ r (z) ∂ s (z) F (z)| = O(n dε 1 -(r+s) ).
As a consequence, by the bounds of ( 23),

E[F ( √ nx p,q ) | A p,q (0)] -E[F ( √ nx p,q ) | A p,q (0)] = r+s≤m O(n dε 1 -m 2 -ε 0 ) + O(n (m+1+d)ε 1 -m+1 2 )
Now, choosing ε 1 small enough so that dε 1 < ε 0 and (m + 1 + d)ε 1 < 1/2, we get (25). ] is bounded independently of i, j and n. To do so, let us apply Proposition 4.3 for X n a GOE or GUE matrix and m = 4: it allows to reduce the problem to the case where the u i,j 's are the entries of a Haar-distributed matrix. In this case, the distribution of u i,j does not depend on i, j and it is well known that the moments of √ nu 1,1 converge to the ones of a standard real or complex Gaussian variable. We did not find any concise enough reference for this moments convergence, but in the unitary case, Proposition 3.4 of [START_REF]Benaych-Georges Classical and free infinitely divisible distributions and random matrices[END_REF] allows to compute E[(n|u 1,1 | 2 -1) 4 ] and to verify its boundedness. To treat the orthogonal case, the most direct way to compute E[(n|u 1,1 | 2 -1) 4 ] is to use the fact that u 2 1,1 has the same distribution as Z 2 1 /(Z

(|u i,j | 2 -1/n)} 2 ] = n -2 O(n -2 (#I × J) 2 ) + n -2 (i ,j ) =1,2 ∈(I×J) 2 E[ =1,2 (n|u i ,j | 2 -1)],
where the term n -2 O(n -2 (#I × J) 2 ) is uniform in s, s , t, t , hence is bounded, for a certain constant C 1 , by C 1 (s -s)

n 2 E[|u i 1 ,j 1 | 2 |u i 2 ,j 2 | 2 ] -1 =      O(n -2 ) if i 1 = i 2 , j 1 = j 2 , O(n -1 ) if (i 1 = i 2 , j 1 = j 2 ) or (i 1 = i 2 , j 1 = j 2 ), O(1) if i 1 = i 2 , j 1 = j 2 ,
which is enough to deduce (26).

4.5. Proof of Lemma 3.1. To prove Lemma 3.1, we shall use the following proposition, which is the obvious multidimentional generalization of Proposition 3.26 of Chapter VI of [START_REF] Jacod | Shiryaev Limit theorems for stochastic processes[END_REF] (note also that the result of [START_REF] Jacod | Shiryaev Limit theorems for stochastic processes[END_REF] is devoted to pocesses on [0, ∞) and not on [0, 1], so that the N of [START_REF] Jacod | Shiryaev Limit theorems for stochastic processes[END_REF] means nothing to us).

For f ∈ D([0, 1] 2 ) and (s 0 , t 0 ) ∈ [0, 1] 2 , we define ∆ s 0 ,t 0 f to be the maximal jump of f at (s 0 , t 0 ), i.e. ∆ s 0 ,t 0 f := max , ∈{<,≥} f (s 0 , t 0 ) -lim s s 0 t t 0 f (s, t) . So to prove Lemma 3.1, let us first prove that the sequence (distribution(B n )) n≥1 is tight. Note that the process B n vanishes at the border of [0, 1] 2 . So according to [START_REF] Bickel | Wichura Convergence criteria for multiparameter stochastic processes and some applications[END_REF]Th. 3] and to Cauchy-Schwartz inequality, it suffices to prove that there is C < ∞ such that for n large enough, for all s < s , t < t ∈ [0, 1],

E[{ ns<i≤ns nt<j≤nt (|u i,j | 2 -1/n)} 4 ] ≤ C(s -s) 2 (t -t) 2 .
As in the proof of (26) above, one can suppose that the u i,j 's are the entries of a Haar-distributed matrix. But in this case, the job has already been done in [START_REF] Donati-Martin | Rouault Truncations of Haar unitary matrices, traces and bivariate Brownian bridge[END_REF]: the unitary case is treated in Section 3.4.1 (see specifically Equation (3.25)) and the orthogonal case is treated, more elliptically, in Section 4.5 (to recover the details of the proof, join Equations (3.26), (4.5) and (4.17)).

Let us now prove (27). Note that sup (s,t)∈[0,1] 2 ∆ s,t B n = max 1≤i,j≤n ||u i,j | 2 -1/n|. As a consequence, by the union bound, it suffices to prove that for each ε > 0, there is C < ∞ independent of i, j and n such that for all i, j, P(||u i,j | 2 -1/n| > ε) ≤ Cn -4 , which follows from Chebyshev's inequality and Proposition 2.10.

Figure 1 .

 1 Figure1. Influence of the tails of the atom distributions of X n on the |u i,j |'s: Plot of the map (i/n, j/n) -→ ||u i,j | 2 -1/n| for two different choices of atom distributions. Left: GOE matrix. Right: Wigner matrix with atom distribution admitting moments only up to order 2 + ε for a small ε. For both pictures, the matrices are n × n with n = 50.

3. 2 .

 2 Formal proofs. By a standard tightness + uniqueness of the accumulation point argument, Theorem 2.6 will follow from the following lemma and Theorem 2.3. The proof of the lemma is postponed to Section 4.5. Lemma 3.1. Under Assumptions 2.1, 2.4 and 2.5 for m = 12, the sequence (distribution(B n )) n≥1 is C-tight, i.e. is tight and has only C([0, 1] 2 )-supported accumulation points.

Lemma 4 . 1 .

 41 Let π ∈ Part(E) satisfy (i), (ii), (iii). The the number c π of connected components of G π is such that c π ≤ p/2 and

  , . . . . . . , π(k )) ( = 1, . . . , p).

Proposition 4 . 4 . 2 ∆

 442 If the sequence (distribution(B n )) n≥1 is tight and satisfies(27) ∀ε > 0, P( sup (s,t)∈[0,1] s,t B n > ε) -→ n→∞ 0,then the sequence (distribution(B n )) n≥1 is C-tight, i.e. is tight and can only have C([0, 1] 2 )supported accumulation points.

  depend on lim n→∞ E[|x 1,2 | 4 ]). Indeed, in this case, by Theorem 1.1 of[START_REF] Donati-Martin | Rouault Truncations of Haar unitary matrices, traces and bivariate Brownian bridge[END_REF], where the case of GOE and GUE matrices is treated, this limit distribution is the bivariate Brownian bridge if and only if lim n→∞ E[|x 1,2 | 4 ] is the same as for X n a GOE or GUE matrix, i.e. equal to 4 -β.

	1 n	P n j=1 δ λ j .

does

  Cov s 1 ,s 2 (2, 2): We have, by the paragraph devoted to the case p = 2 above,

	Cov centered s 1 ,s 2	(2, 2) =
		π, Gπ is a tree

  4.4. Proof of Proposition 2.10. Let us first prove that E[(n|u i,j | 2 -1) 4

  2 1 + • • • + Z 2 n ) for Z i independent standard Gaussian variables (see e.g. [19, Lem. 2.1]) and then to use [19, Lem. 2.4].Let us now prove that there is a constant C independent of n and of 0 ≤ s < s ≤ 1 and0 ≤ t < t ≤ 1 such that |u i,j | 2 -1/n)} 2 ] ≤ C(s -s)(t -t).Set I = {i = 1, . . . , n ; ns < i ≤ ns } and J = {j = 1, . . . , n ; nt < j ≤ nt }. We haveE[{ i∈I,j∈J (|u i,j | 2 -1/n)} 2 ] = n -2 (i ,j ) =1,2 ∈(I×J) 2 (n|u i ,j | 2 -1)].Let us now apply Proposition 4.3 for X n a GOE or GUE matrix and m = 4. Let U n = [u i,j ] n i,j=1 be a Haar-distributed orthogonal or unitary matrix. By Proposition 4.3, we have

	(26)	E[{
		ns<i≤ns nt<j≤nt
		E[
		=1,2
	E[{
	i∈I,j∈J

(

  So it suffices to prove the result forU n instead of U n . Since each |u i,j | 2 has expectation 1/n, | 2 -1)] = n 2 E[|u i 1 ,j 1 | 2 |u i 2 ,j 2 | 2 ] -1. Then, to compute E[|u i 1 ,j 1 | 2 |u i 2 ,j 2 | 2 ], one uses the Weingarten calculus, developed in[START_REF]Collins Moments and Cumulants of Polynomial Random Variables on Unitary Groups, the Itzykson-Zuber Integral, and Free Probability[END_REF][START_REF] Collins | Sniady Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF]. By the formulas of[START_REF] Collins | Sniady Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF] Sec. 6] for the orthogonal group and [9, Sec. 5.2] for the unitary group,

		2
	E[ (n|u i ,j Wg ortho (Id {1,2} ) = =1 n + 1 n(n -1)(n + 2)	,	Wg ortho ((12)) =	1 n(n -1)(n + 2)	,
	Wg unit (Id {1,2} ) =	1 n 2 -1	,		Wg unit ((12)) =	-1 n(n 2 -1)	,
	(where (12) denotes the transposition with support {1, 2}), one can easily verify that

2 (t -t) 2 ≤ C 1 (s -s)(t -t).

This work was partially supported by the Agence Nationale de la Recherche grant ANR-08-BLAN-0311-03 and partly accomplished during the author's stay at New York University Abu Dhabi, Abu Dhabi, U.A.E..