Alex Borello

Julien Cervelle

Pascal Vanier

Turing degrees of limit sets of cellular automata

Introduction

Cellular Automata (CAs for short) are both discrete dynamical systems and a model of computation. They were introduced in the late 1940s independently by John von Neumann and Stanislaw Ulam to study, respectively, self-replicating systems and the growth of quasi-crystals.

A d-dimensional CA consists of cells aligned on Z d that may be in a finite number of states, and are updated synchronously with a local rule, i.e. depending only on a finite neighborhood. All cells operate under the same local rule. The state of all cells at some time step is called a configuration. CAs are very well known for being simple systems that may exhibit complicated behavior.

A d-dimensional subshift of finite type (SFT for short) is a set of colorings of Z d by a finite number of colors containing no pattern from a finite family of forbidden patterns. Most proofs of undecidability concerning CAs involve the use of SFTs, so both topics are very intertwined [START_REF] Kari | Reversibility of 2D cellular automata is undecidable[END_REF][START_REF] Kari | The Nilpotency Problem of One-Dimensional Cellular Automata[END_REF][START_REF] Kari | Reversibility and surjectivity problems of cellular automata[END_REF][START_REF] Meyerovitch | Finite entropy for multidimensional cellular automata[END_REF][START_REF] Kari | Snakes and Cellular Automata: Reductions and Inseparability Results[END_REF]. A recent trend in the study of SFTs has been to give computational characterizations of dynamical properties, which has been followed by the study of their computational structure and in particular the comparison with the computational structure of effectively closed sets, which are the subsets of {0, 1} N on which some Turing machine does not halt. It is quite easy to see that SFTs are such sets.

In this paper, we follow this trend and study the limit set Ω (A) of a CA A, which consist of all the configurations of the CA that can occur after arbitrarily long computations. They were introduced by Culik, Pachl, and Yu [START_REF] Culik | On the limit sets of cellular automata[END_REF] in order to classify CAs. It has been proved that non-trivial properties on these sets are undecidable by Kari [Kar94b]; Guillon and Richard [START_REF] Guillon | Revisiting the Rice Theorem of Cellular Automata[END_REF] for CAs of all dimensions. Limit sets of CAs are subshifts, and the question of which subshifts may be limit sets of CA has been a thriving topic, see [Hur87; Hur90a; Hur90b; Maa95; FK07; LM09; BGK11]. However, most of these results are on the language of the limit set or on simple limit sets. Our aim here is to study the configurations themselves.

In dimension 1, limit sets are effectively closed sets, so it is quite natural to compare them from a computational point of view. The natural measure of complexity for effectively closed sets is the Medvedev degree [START_REF] Simpson | Mass problems associated with effectively closed sets[END_REF], which, informally, is a measure of the complexity of the simplest points of the set. As limit sets always contain a uniform configuration (wherein all cells are in the same state), they always contain a computable point and have Medvedev degree 0. Thus, if we want to study their computable structure, we need a finer measure; in this sense, the set of Turing degrees is appropriate.

It turns out that for SFTs, there is a characterization of the sets of Turing degrees found by Jeandel and Vanier [START_REF] Jeandel | Turing degrees of multidimensional {SFTs}[END_REF], which states that one may construct SFTs with the same Turing degrees as any effectively closed set containing a computable point. In the case of limit sets, such a characterization would be perfect, as limit sets always contain a computable point1 . This is exactly what we achieve in this article: Theorem 1. For any effectively closed set S, there exists a cellular automaton A such that

deg T Ω (A) = deg T S ∪ {0}.
In the way to achieve this theorem, we introduce a new construction which gives us some control over the limit set. We hope that this construction will lead to other unrelated results on limit sets of CAs, as it was the case for the construction in [START_REF] Jeandel | Turing degrees of multidimensional {SFTs}[END_REF], see [START_REF] Jeandel | Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type[END_REF].

The paper is organized as follows. In Section 2 we recall the usual definitions concerning CAs and Turing degrees. In Section 3 we give the reasons for each trait of the construction which allows us to prove theorem 1. In Section 4 we give the actual construction. We end the paper by a discussion, in Section 5, on the Cantor-Bendixson ranks of the limit sets of CAs. The choice has been made to have colored figures, which are best viewed on screen.

Preliminary definitions

A (1-dimensional) cellular automaton is a triple A = (Q, r, δ), where Q is the finite set of states, r > 0 is the radius and δ :

Q 2r+1 → Q the local transition function.
An element of i ∈ Z is called a cell, and the set i-r, i+r is the neighborhood of i (the elements of which are the neighbors of i). A configuration is a function c : Z → Q. The local transition function induces a global transition function (that can be regarded as the automaton itself, hence the notation), which associates to any configuration c its successor :

A(c) : Z → Q i → δ(c(i -r), . . . , c(i -1), c(i), c(i + 1), . . . , c(i + r))).
In other words, all cells are finite automata that update their states in parallel, according to the same local transition rule, transforming a configuration into its successor.

If we draw some configuration as a horizontal bi-infinite line of cells, then add its successor above it, then the successor of the latter and so on, we obtain a space-time diagram, which is a two-dimensional representation of some computation performed by A.

A site (i, t) ∈ Z 2 is a cell i at a certain time step t of the computation we consider (hereinafter there will never be any ambiguity on the automaton nor on the computation considered).

The limit set of A, denoted by Ω (A), is the set of all the configurations that can appear after arbitrarily many computation steps:

Ω (A) = k∈N A k (Q Z ).
For surjective CAs, the limit set is the set of all possible configurations Q Z , while for non-surjective CAs, it is the set of all configurations containing no orphan of any order, see [START_REF] Hurd | Nonrecursive Cellular Automata Invariant Sets[END_REF]. An orphan of order n is a finite word w which has no preimage by A n |Q |w| . An effectively closed set, or Π 0 1 class, is a subset S of {0, 1} N for which there exists a Turing machine that, given any x ∈ {0, 1} N , halts if and only if x ∈ S.

Equivalently, a class S ⊆ {0, 1} N is Π 0 1 if there exists a computable set L such that x ∈ S if and only if no prefix of x is in L. It is then quite easy to see that limit sets of CAs are Π 0 1 classes: for any limit set, the set of forbidden patterns is the set of all orphans of all orders, which form a recursively enumerable set, since it is computable to check whether a finite word is an orphan.

For x, y ∈ {0, 1} N , we say that x≤ T y if x is computable by a Turing machine using x as an oracle. If x≤ T y and x≥ T y, x and y are said to be Turing-equivalent, which is noted x≡ T y. The Turing degree of x, noted deg T x, is its equivalence class under relation ≡ T . The Turing degrees form a lattice whose bottom is 0, the Turing degree of computable sequences.

Effectively closed sets are quite well understood from a computational point of view, and there has been numerous contributions concerning their Turing degrees, see the book of Cenzer and Remmel [START_REF] Cenzer | Π 0 1 classes in mathematics[END_REF] for a survey. One of the most interesting results may be that there exist Π 0 1 classes whose members are two-by-two Turing incomparable [START_REF] Jockusch | Degrees of members of Π 0 1 classes[END_REF].

Requirements of the construction

The idea to prove Theorem 1 is to make a construction that embeds computations of a Turing machine that will check a read-only oracle tape containing a member of the Π 0 1 class S that will have to appear "non-deterministically". The following constraints have to be addressed.

• Since CAs are intrinsically deterministic, this non-determinism will have to come from the "past", i.e. from the "limit" of the preimages.

• The oracle tape, the element of {0, 1} N that needs to be checked, needs to appear entirely on at least one configuration of the limit set.

• Each configuration of the limit set containing the oracle tape needs to have exactly one head of the Turing machine, in order to ensure that there really is a computation going on in the associated space-time diagram.

• The construction, without any computation, needs to have a very simple limit set, i.e. it needs to be computable, and in particular countable; this to ensure that no complexity overhead will be added to any configuration containing the oracle tape, and that "unuseful" configurations of the limit set -the configurations that do not appear in a space-time diagram corresponding to a computation -will be computable.

• The computation of the embedded Turing machine needs to go backwards, this to ensure that we can have the non-determinism. And an error in the computation must ensure that there is no infinite sequence of preimages.

• The computation needs to have a beginning (also to ensure the presence of a head), so the construction needs some marked beginning, and the representation of the oracle and work tapes in the construction need to disappear at this point, otherwise by compactness the part without any computation could be extended bi-infinitely to contain any member of {0, 1} N , thus leading to the full set of Turing degrees.

There are other constraints that we will discuss during the construction, as they arise.

In order to make a construction complying to all these constraints, we reuse, with heavy modifications, an idea of Jeandel and Vanier [START_REF] Jeandel | Turing degrees of multidimensional {SFTs}[END_REF], which is to construct a sparse grid. However, their construction, being meant for subshifts, requires to be completely rethought in order to work for CAs. In particular, there was no determinism in this construction, and the oracle tape did not need to appear on a single column/row, since their result was on two-dimensional subshifts.

The construction

A self-vanishing sparse grid

In order to have space-time diagrams that constitute sparse grids, the idea is to have columns of squares, each of these columns containing less and less squares as we move to the left, see fig. 1. The CA has three categories of states:

• a killer state, which is a spreading state that erases anything on its path;

• a quiescent state, represented in white in the figures; its sole purpose is to mark the spaces that are "outside" the construction;

• some construction states, which will be constituted of signals and background colors.

In order to ensure that just with the signals themselves it is not possible to encode anything non-computable in the limit set, all signals will need to have, at all points, at any time, different colors on their left and right, otherwise the local rule will have a killer state arise. Here are the main signals.

• Vertical lines: serve as boundaries between columns of squares and form the left/right sides of the squares.

• SW-NE and SE-NW diagonals: used to mark the corners of the squares, they are signals of respective speeds 1 and -1. Each time they collide with a vertical line (except for the last square of the row), they bounce and start the converse diagonal of the next square.

• Counting signal: will count the number of squares inside a column; every time it crosses the SW-NE diagonal of a square it will shift to the left. When it is superimposed to a vertical line, it means that the square is the last of its column, so when it crosses the next SE-NW diagonal, it vanishes and with it the vertical line.

• Starting signals: used to start the next column to the left, at the bottom of one column. Here is how they work.

-The bottommost signal, of speed -1 4 , is at the boundary between the empty part of the space-time diagram and the construction. It is started 4 time steps after the collision with the signal of speed -1 3 . -The signal of speed -1 3 is started just after the vertical line sees the incoming SE-NW diagonal of the first square of the row on the right, at distance 32 (the diagonal will collide with the vertical line 2 time steps after the start of that signal).

-At the same time as the signal of speed -1 3 is created, a signal of speed -1 2 is generated. When this signal collides with the bottommost signal, it bounces into a signal of speed 1 4 that will create the first SE-NW diagonal of the first square of the row of squares of the left, 4 time steps after it will collide with the vertical line.

On top of the construction states, except on the vertical lines, we add a parity layer {0, 1}: on a configuration, two neighboring cells of the construction must have different parity bits, otherwise a killer state appears. On the left of a vertical line there has to be parity 1 and on the right parity 0, otherwise the killer state pops up again. This is to ensure that the columns will always contain an even number of squares. The following lemmas address which types of configurations may occur in the limit set of this CA. First note that any configuration wherein the construction states do not appear in the right order do not have a preimage.

Lemma 4.1. The sequence of preimages of a segment ended by consecutive vertical lines (and containing none) is a slice of a column of squares of even side.

Proof. Suppose a configuration contains two vertical-line symbols, then to be in the limit set, in between these two symbols there needs to be two diagonal symbols, one for the SE-NW one and one for SW-NE one, a symbol for the counting signal, and in between these signals there needs to be the appropriate colors: there is only one possibility for each of them. If this is not the case, then the configuration has no preimage.

Also, the distance between the first vertical line and the SE-NW diagonal needs to be the same than the distance between the second vertical line and the SW-NE diagonal, otherwise the signals at the bottom -the ones starting a column, that are the only preimages of the first diagonals -would have, in one case, created a vertical line in between, and in the other case, not started at the same time on the right vertical.

The side of the squares is even, otherwise the parity layer has no preimage.

Lemma 4.2. A configuration of the limit set containing at least three verticalline symbols needs to verify, for any three consecutive symbols, that if the distance between the first one and the second one is k, then the distance between the second one and the third one needs to be (k + 2).

Proof. Let us take a configuration containing at least three vertical-line symbols, take three consecutive ones. The states between them have to be of the right form as we said above. Suppose the first of these symbols is at distance k 1 of the second one, which is at distance k 2 of the third one. This means that the first (resp. second) segment defines a column of squares of side k 1 (resp. k 2 ). It is clear that the second column of squares cannot end before the first one. Now let i be the position of the counting signal of the first column and j the distance between the SW-NE diagonal and the left vertical line. The preimage of the first segment ends (k 1 i + j) (resp. (k 1 (i -1) + j)) steps before if the counting signal is on the left (resp. right) of the SW-NE diagonal. Then, the preimages of the left and right vertical lines of this column are the creating signals. Before the signal created on the right bounces on the one of speed -1 4 created on the left, it collides with the one of speed -1 3 , thus determining the height of the squares on the right column of squares. So k 1 = k 2 -2. Lemma 4.3. A configuration having two vertical-line symbols pertaining to the limit set needs to verify one of the following statements.

• It is constituted of a finite number of vertical lines. Proof. We place ourselves in the case of a configuration of the limit set. Because of lemma 4.1, two consecutive vertical lines at distance k from each other define a column of squares. In a space-time diagram they belong to, on their left there necessarily is another column of squares, because of the starting signal generated at the beginning of the left vertical line, except when k = 3, in which case there is nothing on the left. In this column, the vertical lines are at distance (k -2), see lemma 4.2. So, if there is an infinite number of vertical lines, either it is of the form of fig. 1, or there is some killer state coming from infinity on the left and "eating" the construction.

Backward computation inside the grid

We now wish to embed the computation of a reversible Turing machine inside the aforementioned sparse grid, which for this purpose is better seen as a lattice.

The fact the TM is reversible allows us to embed it backwards in the CA. We will below denote by TM time (resp. CA time) the time going forward for the Turing machine (resp. the CA); on a space-time diagram, TM time goes from top to bottom, while CA time goes from bottom to top (cf. arrows in fig. 2a). That way, the beginning of the computation of the TM will occur in the first (topmost) square of the first (leftmost) column of squares.

We have to ensure that any computation of the TM is possible, and in particular ensure that such a computation is consistent over time; the idea is that at the first TM time step, i.e. the moment the sparse grid disappears, the tape is on each of the vertical line symbols, but since these all disappear a finite number of CA steps before, we have to compel all tape cells to shift to the right regularly as TM time increases.

Moreover, we want to force the presence of exactly one head (there could be none if it were, for instance, infinitely far right). To do that, the grid is divided into three parts that must appear in this order (from left to right): the left of the head, the right of the head (together referred to as the computation zone) and the unreachable zone (where no computation can ever be performed), resp. in blue, yellow and green in fig. 2a.

The vertices of our lattice are the top left corners of the squares, each one marked by the rebound of a SE-NW diagonal on a vertical line, while the top right corners will just serve as intermediate points for signals. More precisely, if we choose (arbitrarily) the top left corner of the first square of the first column to appear at site (0, 0), then for any i, j ∈ N, the respective sites for the top left and top right corners of s i,j , the (j + 1)-th square of the (i + 1)-th column, are the following (cf. fig. 2a):

s ℓ i,j = (i(i + 1), -2(i + 1)j) s r i,j = ((i + 1)(i + 2), -2(i + 1)j).
Fig. 2b illustrates a computation by the TM, with the three aforementioned zones, as it would be embedded the usual way (but with reverse time) into a CA, with site (i, -t) corresponding to the content of the tape at i ∈ N and TM time t ∈ N.

Fig. 2c represents another, still simple, embedding, which is a distortion of the previous one: the head moves every even time step within a tape that is shifted every odd time steps, so that instead of site (i, -t), we have two sites, (i + t, -2t) and (i + t, -2t -1), resp. the computation site (big circle on fig. 2c) and the shifting site (small circle on fig. 2c). The head only reads the content of the tape when it lies on a computation site. This type of embedding can easily be realized forwards or backwards (provided the TM is reversible).

Our embedding, derived from the latter, is drawn on fig. 2a. The "only" difference is the replacement of sites (i + t, -2t) and (i + t, -2t -1) by sites s ℓ i,t and s ℓ i,t+1 . Notice that as the number of squares in a column is always finite, each square can "know" whether its top left corner is a computation or a shifting site with a parity bit. More precisely, the j-th square (from bottom to top) of a column has a computation site on its top left if and only if j is even.

Let s i,j be a square of our construction. s ℓ i,j is either a computation site or a shifting site. In the latter case, it is supposed to receive the content of a cell of the TM tape with an incoming signal of speed -1. All it has to do is to send it to s ℓ i,j-1 (at speed 0), which is a computation site. In the former case, however, things a slightly more complicated. The content of the tape has to be transmitted to s ℓ i-1,j-1 (which is a shifting site). To do that, a signal of speed 0 is sent and waits for site s r i-1,j , which sends the content to s ℓ i-1,j-1 with a signal of speed -1 along the SE-NW diagonal. The problem is to recognize which s r site is the correct one. Fortunately, there are only two possibilities: it is either the first or the second s r site to appear after (in CA time, of course) s ℓ i,j on the vertical line. The first case corresponds exactly to the unreachable zone (where j ≤ i), hence the result if the three zones are marked. The lack of other cases is due to the number of s i squares, which is only 2(i + 1).

Another issue is the superposition of such signals. Here again, there are only two cases: in the unreachable zone there is none, whereas in the computation zone a signal of speed 0 from a computation site can be superimposed to the signal of speed 0 sent by the shifting site just above it. As aforesaid, there is no other case because of the limited number of s i squares. Thus, there is no problem to keep the number of states of the CA finite, since the number of signals going through a same cell is limited to two at the same time.

While the two parts of the computation zones are to be separated by the presence of a head, the unreachable zone is at the right of a signal that is sent from any computation site that has two diagonals (one from the left and one from the right) below it (indicated as circles on fig. 1), goes at speed 0 until the next s r site, then at speed 1 (along SE-NW diagonals) to the second next shifting site, and finally at speed 0 again, to the next computation site (cf. fig. 2a), which also has two diagonals below it if the grid contains no error. Another way to detect the unreachable zone is to detect that the counting signal crossed the SW-NE diagonal exactly two CA time steps after it has crossed the SE-NW diagonal. This means that the unreachable zone is structurally coded in the construction. Now only the movements of the head remain to be described (in black on fig. 2a). Let s ℓ i,j be a computation site containing the head. • If the previous move of the head (previous because we are in CA time, that is, in reverse TM time) was to the left, the next computation site is the one just above, that is, s ℓ i,j-2 . The head is thus transferred by a simple signal of speed 0.

• If the previous move was to stand still, the next computation site is s ℓ i-1,j-2 . It can be reached by a signal of speed 0 until the second next s r site, from which a signal of speed -1 (along a SE-NW diagonal) is launched, to be replaced by another signal of speed 0 from s ℓ i-1,j-1 on.

• If the previous move was to the right, the next computation site is s ℓ i-2,j-2 . It can be reached by a signal of speed 0 until the second next s r site, from which a signal of speed -1 (along a SE-NW diagonal) is launched, to be replaced by another signal of speed 0 from s ℓ i-1,j-1 on, which itself waits for the next s r site (which is s r i-2,j ) to start another signal of speed 1 (along a SW-NE diagonal) that is finally succeeded to by a last signal of speed 0 from s ℓ i-2,j-1 on.

The computation itself

As we said before, the computation will take place on the computation sites, which will contain two kinds of tape cells: one for the oracle and one for the work. In the unreachable zone there are only oracle cells, which do not change over time except for the shifting. Now we want to eliminate all space-time diagrams corresponding to rejecting computations of some Turing machine M . Bennett [START_REF] Bennett | Logical Reversibility of Computation[END_REF] has proved that for any Turing machine, we can construct a reversible one computing the same function. So a first idea would just be to encode this reversible Turing machine in the sparse grid; however there is no way to guarantee that the work tape that was non-deterministically inherited from the past corresponds to a valid configuration and by the time the Turing machine "realizes" this it will be too late, there will already exist configurations containing some oracle that we would otherwise have rejected.

The solution to this problem is to use a robust Turing machine in the sense of Hooper [START_REF] Hooper | The Undecidability of the Turing Machine Immortality Problem[END_REF], that is to say a Turing machine that regularly rechecks its whole computation. Kari and Ollinger [START_REF] Kari | Periodicity and Immortality in Reversible Computing[END_REF] have constructed reversible such machines. In these constructions the machines constructed were working on a bi-infinite tape, which had the drawback that some infinite side of the tape might not be checked; here it is not the case, hence we can modify the machine so that on an infinite computation it visits all cells of the tape (we omit the details for brevity's sake).

In terms of limit sets, this means that if some oracle is rejected by the machine, then it must have been rejected an infinite number of times in the past (CA time). So, only oracles pertaining to the desired class may appear in the limit set.

Furthermore, even if some killer state coming from the right eats the grid, at some point in the past of the CA, it will be in the unreachable zone, and stay there for ever, so the computation from that moment on even ensures that the oracle computed is correct. Though, that doesn't matter, because in this case the configurations of the corresponding space-time diagram that are in the limit set are uniform both on the right and on the left except for a finite part in the middle, and are hence computable.

5 Cantor-Bendixson rank of limit sets

The Cantor-Bendixson derivative of some set S ⊆ Σ Z , with Σ finite, is noted D (S) and consists of all configurations of S except the isolated ones. A configuration c is said to be isolated if there exists a pattern P such that c is the only configuration of S containing P (up to a shift). For any ordinal λ we can define S (λ) , the Cantor-Bendixson derivative of rank λ, inductively: γ) .

S (0) = S S (λ+1) = D S (λ) S (λ) = γ<λ S (
The Cantor-Bendixson rank of S, denoted by CB (S), is defined as the first ordinal λ such that S (λ+1) = S (λ) . In particular, when S is countable, S (CB(S)) is empty. An element s is of rank λ in S if λ is the least ordinal such that s / ∈ S (λ) . For more information about Cantor-Bendixson rank, one may skim [START_REF] Kechris | Classical descriptive set theory[END_REF].

The Cantor-Bendixson rank corresponds to the height of a configuration corresponding to a preorder on patterns as noted by Ballier, Durand, and Jeandel [START_REF] Ballier | Structural aspects of tilings[END_REF].Thus, it gives some information on the way the limit set is structured pattern-wise. A straightforward corollary of the construction above is the following.

Corollary 5.1. There exists a constant c ≤ 10 such that for any Π 0 1 class S, there exists a CA A such that CB (Ω (A)) = CB (S) + c.

Here the constant corresponds to the pattern overhead brought by the sparsegrid construction.

Figure 1 :

 1 Figure1: The sparse grid construction: it is based on columns containing a finite number of squares, whose number decreases when we go left. Note that the figure is squeezed vertically.

•

  It appears in the space-time diagram of fig. 1. • It is constituted of an infinite number of vertical lines, then starting from some position it is equal on the right to some (shifted) line of fig. 1.

Figure 2 :

 2 Figure2: The embedding of a Turing machine computation in the sparse grid (2a), compared to the usual embedding (2b) and a slightly distorted one (2c). The paths followed by the content of each cell of the tape are in red and orange (two colors just to keep track of the signals), while the one of the head is in black. The arrows indicate the next move of the head (for TM time, going towards the bottom). The green background denotes the zone the head cannot reach, while the computation zone is in blue on the left of the head and in yellow on its right.

Note that this is not the case for subshifts: there exist non-empty subshifts containing only non-computable points.

That can be done, provided the radius of the CA is large enough.

Acknowledgments

This work was sponsored by grants EQINOCS ANR 11 BS02 004 03 and TAR-MAC ANR 12 BS02 007 01. The authors would like to thank Nicolas Ollinger and Bastien Le Gloannec for some useful discussions.


Yves Colin De Verdière
email: yves.colin-de-verdiere@ujf-grenoble.fr

Semi-classical measures on Quantum graphs and the Gauß map of the determinant manifold

Introduction

The so-called Quantum Ergodic Theorem (QE), due mainly to Alexander Shnirelman [START_REF] Shnirelman | Ergodic properties of eigenfunctions[END_REF][START_REF] Shnirelman | On the asymptotic properties of eigenfunctions in the regions of chaotic motion[END_REF][START_REF] Zelditch | Uniform distribution of eigenfunctions on compact hyperbolic surfaces[END_REF][START_REF] Verdière | Ergodicité et fonctions propres du laplacien[END_REF], asserts that the eigenfunctions of the Laplace operator on a smooth closed Riemannian manifold whose geodesic flow is ergodic are equi-distributed on the manifold in the limit of large eigenvalues provided one removes a sub-sequence of density 0. The paper [START_REF] Jakobson | The semiclassical theory of discontinuous systems and ray-splitting billiards (with an Appendix of Yves Colin de Verdière)[END_REF] gives QE Theorems in the case of metrics with discontinuities on smooth manifolds: the Assumptions are ergodicity of the geodesic flow which in this context is a Markov process and the fact that recombining geodesics are exceptional. The results apply also to piecewise smooth metrics on simplicial complexes, in particular to metric graphs (also called "quantum graphs"). The geodesic flow is then ergodic, but they are many recombining geodesics. Hence the second assumption is not satisfied for quantum graphs. It is currently believed that QE does not hold in general for a FIXED quantum graph. In [START_REF] Berkolaiko | No Quantum Ergodicity for Star Graphs[END_REF], it is proved that QE does not holds in the limit of large irrational star graphs. This implies that QE does not hold for a fixed large irrational star graph; this is even proved for a fixed irrational star graph. Similar results are proven in [START_REF] Keating | Value Distribution of the Eigenfunctions and Spectral Determinants of Quantum Star Graphs[END_REF] (put f (x) = x 2 in Equation ( 51)). In the literature, QE for graphs means some property of the eigenfunctions in the limit of a sequence of graphs whose number of vertices is going to infinity (see for example [START_REF] Gnutzman | Eigenfunction statistics on quantum graphs[END_REF]).

In the present paper, our goal is to describe all weak limits of measures |φ j | 2 |dx| l , where (φ j ) is an orthonormal basis of eigenfunctions for the Laplacian ∆ l on a metric graph (G, l) and |dx| l is the Riemannian measure, and to get upper bounds on the densities of the associated sub-sequences of eigenfunctions. In particular we show that QE does not hold for a generic metric l on a fixed graph, except if the graph is homeomorphic to an interval or to a circle. In order to avoid confusion, we will denote this last property by QEF (Quantum Ergodicity for Fixed graph).

If G = (V, E) is a finite graph, we introduce, following ideas in [START_REF] Barra | On the Level Spacing Distribution in Quantum Graphs[END_REF][START_REF] Barra | Classical dynamics on graphs[END_REF], an algebraic sub-manifold Z G , which we call the "determinant manifold", of the torus T E := (R/2πZ) E which allows to compute the eigenvalues thanks to the so-called "secular equation". The Gauß map Γ associates to any point of the smooth part Z reg G of Z G the half-line of the cone P E := [0, +∞[ E \{0} which is orthogonal to Z G . Let us denote by M G the semi-algebraic set which is the closure of the image of Γ. Let us state the main result of this paper: Another related result is the description of all semi-classical measures with minimal support, which are analogs of the so-called "scars" in the case of manifolds: the supports of these scars are simple paths joining two vertices of degree one and simple cycles (this is related to the paper [START_REF] Schanz | Scars on Quantum Networks Ignore the Lyapunov Exponent[END_REF]). From this, we deduce that QEF does not hold for a generic l, except for graphs homeomorphic to intervals or circles.

Many thanks to the referees for the comments which allowed me to improve the results and the proofs.

The determinant manifold of a quantum graph

In this section, we recall the way to compute the spectra of the Laplacians ∆ l on a graph G = (V, E) from an algebraic hyper-surface Z G of the torus T E = (R/2πZ) E which depends only on the combinatorics of the graph and not on the lengths l. This approach is closely related to what people do in several papers like [BG00, BKW04, BW08, Ba12, BB13].

Let us consider a finite connected graph G = (V, E) where loops and multiple edges are allowed. We choose an orientation of the edges. We associate, in the usual way, to G a 1D singular manifold |G| by gluing together #E intervals, labelled by the set E, using the combinatorics of G. A (Riemannian) metric on |G| is given by the lengths of the edges. We will denote by l ∈]0, +∞[ E the collection of the lengths and the pair (G, l) is called a Metric Graph.

Definition 1.1 We will say that l is irrational if the components of l are independent over the rational numbers.

To any metric l is associated the Riemannian measure on |G| denoted by |dx| l = e∈E |dt e | where t e ∈ [-l e /2, l e /2] is the arc-length parametrization of the edge e following the given orientation and with the origin at the center of the edge e. We have |G| |dx| l = L where L = e∈E l e is the total length of (G, l). The Laplacian ∆ l is the self-adjoint operator on L 2 (|G|, |dx| l ) with domain consisting of the functions φ : |G| → C which are in the Sobolev space ⊕ e∈E H 2 (e), are continuous on |G| and satisfy the Kirchhoff condition that the sums of outgoing derivatives of φ at each vertex vanish. Then ∆ l φ is given by -d 2 φ/dt 2 e on each edge. The metric graph G with the previous Laplacian is also called a Quantum graph. More generally, a quantum graph is a metric graph with a self-adjoint differential operator on L 2 (|G|, |dx| l ). A good introduction to Quantum graphs is the recent book [START_REF] Berkolaiko | Introduction to quantum graphs[END_REF]. The operator ∆ l has a discrete spectrum given by

λ j = k 2 j with k 1 = 0 < k 2 ≤ • • • .
We denote by φ j : |G| → C an associated orthonormal basis of eigenfunctions. Let us remark that we can assume that G has no vertex of degree 2, because we allow multiple edges and loops.

Let us try to compute the non-zero part of the spectrum of ∆ l : let us look for an eigenfunction φ with eigenvalue k 2 with k > 0. On the edge e, we have φ(t e ) = a e cos kt e + b e sin kt e .

(

Let us define ξ e = cos kl e /2 and η e = sin kl e /2. From the continuity conditions and the Kirchhoff conditions, we get, for the function φ = φ a,b , a linear system The determinant of the system L ξ,η (a, b) = 0 is an homogeneous polynomial of degree 2 with respect to each ζ e = (ξ e , η e ). Hence, it can be expressed as a polynomial of total degree #E in the variables z e = (x e , y e ) with x e = cos kl e , y e = sin kl e which is of degree 1 w.r. to each pair (x e , y e ). Let θ e be the corresponding angles so that x e = cos θ e , y e = sin θ e . Let us denote this trigonometric polynomial δ G (θ) viewed as a function on the torus T E = (R/2πZ) E whose coordinates are denoted by θ = (θ e ) e∈E . The following fact is clear from what we said, the number k 2 , k > 0 is an eigenvalue of ∆ l if and only if δ G ([k l]) = 0 where [ ] means that we take the components modulo 2π. In other words, [k l] belongs to the algebraic hyper-surface Z G of equation δ G = 0 of T E . Let us remark that, by an elementary check, θ = 0 belongs too to Z G .

Let us discuss a few elementary property of Z G . We will say that [k l] is a smooth point of Z G if the differential of δ G at that point does not vanish. A point which is not smooth is called singular.

Theorem 1.1 If k 2 > 0 is a non degenerate eigenvalue of ∆ l , the point [k l]
is a smooth point of Z G and the tangent space to Z G at that point is given by e m e dθ e = 0 where m e = a 2 e + b 2 e for an eigenfunction given by Equation (1).

Conversely, if the eigenvalue k 2 of ∆ l is degenerate, [k l] is a singular point of Z G .
The manifold Z G is singular in a set of co-dimension at least 1 (w.r. to

Z G itself ) except if |G| is a circle.

Let us denote by

Z G = Z reg G ∪ Z sing G
the partition of Z G into the sets of regular and singular points. Using a result of L. Friedlander on the genericity of non degeneracy of the eigenvalues of ∆ l [START_REF] Friedlander | Genericity of simple eigenvalues for a metric graph[END_REF] if |G| is not a circle, we get the fact that, if |G| is not a circle, the set Z reg G is dense in Z G and hence, because Z G is an algebraic manifold, the set of singular points Z sing G has co-dimension larger than one w.r. to Z G .

Questions: as we will see from the examples in Sections 6.2 and 6.3, Z G can be reducible. For which graphs is Z G irreducible? A conjecture could be that Z G is reducible, if and only if |G| admits a non trivial symmetry group which is an isometry group for each metric and |G| is not an interval, more precisely: Proposition 1.1 The topological set |G| admits a non trivial symmetry group which acts by isometry for each choice of a metric l if and only if either |G| is homeomorphic to [-1, 1] (then the isometry group is generated by x → -x), either |Gis a circle with the antipody as a non trivial symmetry, or if |G| is obtained by adding to a |K| (associated to a graph K) some loops (at least 1) attached to vertices of K (then the symmetry group is generated by the involutions x → -x on one of the loops parametrized by -1 ≤ x ≤ +1).

Proof.-

We can assume that G has no vertex of degree 2. If G is a circle or an interval it admits clearly such a symmetry group. Let us assume moreover that G has no loops as in the Proposition. Then G admits a vertex of degree at least 3. Because the lengths of these edge are arbitrary, the isometries have to fix this vertex and the adjacent adges. An easy induction gives the result.

If the manifold Z G is irreducible, is the set of singular point of co-dimension ≥ 2 w.r. to Z G as expected from the generic co-dimension of symmetric matrices with som degenerate eigenvalue? Proof.-

(of Theorem 1.1)
• Using the homogeneity of the spectrum, i.e. , ∀c > 0, k j (c l) = c -1 k j ( l), we can assume that k = 1. In other words Z G is identified with the [ l]'s so that 1 is an eigenvalue of ∆ l . Let

z 0 = [ l] ∈ Z G .
We assume that the eigenvalue 1 is non-degenerate for ∆ l . Close to z 0 , the set Z G is defined by the equation k([ l]) = 1 meaning that 1 is an eigenvalue of ∆ l , so that Z G is smooth if dk = 0 and the tangent space is the kernel of dk.

From the calculation of dk in Appendix A, we get the result.

• Let us assume that k 2 0 > 0 is a degenerate eigenvalue of ∆ l . With the notations around Equation (1), this implies that dim ker L ξ 0 ,η 0 ≥ 2 with ξ 0 = (cos k 0 l e ), η 0 = (sin k 0 l e ). This implies that the diffenrential of the determinant of L ξ 0 ,η 0 with respect to any variation of ξ, η vanishes. The result follows.

The singularities of Z G are associated to the degenerate eigenvalues. A description of these singularities would be of interest, already for general star graphs or complete graphs. The case of diabolical singularities, corresponding to eigenvalues of multiplicity two, is used in [START_REF] Barra | On the Level Spacing Distribution in Quantum Graphs[END_REF] in order to study the behavior as s → 0 of the distribution P (s)ds of the level spacing λ j+1 -λ j defined by

P (s)ds = lim λ→∞ #{j|s ≤ λ j+1 -λ j ≤ s + ds} #{j|λ j ≤ λ} .
2 The Gauß map and semi-classical measures We can summarize the results as follows:

Theorem 2.1 1. Let µ = e∈E m e |dt| e be a semi-classical limit for ∆ l 0 , then there exists l ∞ and an eigenfunction φ ∞ of ∆ l∞ associated to the eigenvalue 1 so that µ = µ φ∞ .

2. Let us assume that φ is an eigenfunction of some ∆ l 0 with a simple eigenvalue k 2 0 , then µ φ is a semi-classical measure for ∆ l 0 and for any ∆ l with l irrational.

3. Let G G be the set of the l so that l is irrational and the line

{[k l] | k > 0}
does not meet Z sing G (or equivalently the set of l so that the eigenvalues of

∆ l are simple). If |G| is not a circel, the set G G is Baire generic and, if l 0 ∈ G G , the set of semi-classical measures for ∆ l 0 is the closure of the image of Z reg
G by the Gauß map.

Proof.-1. Let us consider a sequence of eigenfunctions of ∆ l defined by φ k j (t e ) = a e,j cos k j t e + b e,j sin k j t e . Then, for large k j 's, the measures e φ k j (t e ) 2 |dt e | have a weak limit if and only if the limits m e = lim j→∞ (a 2 e,j + b 2 e,j ) exist and this limit measure is given by e∈E m e |dt| e . By compactness of Z G , we can assume that [k j l 0 ] converges to [ l ∞ ] and we can assume that all components of l ∞ are > 0 . Then we can again extract a sub-sequence so that the numbers a e,j and b e,j converge to some limit which will be associated, by the closeness of the eigenfunctions equations, to an eigenfunction of ∆ l∞ with eigenvalue 1.

2. From the assumption and Theorem 1.1, we get that the set Z G is smooth near [k 0 l 0 ] and transverse to any curve t → [t l] if the components of l are all > 0. From this and the fact that the linear flows on tori are recurrent, we can get a sequence k j → +∞ so that [k j l 0 ] → [k 0 l 0 ] as j → ∞ and we have that

µ φ k j → µ φ . Similarly, if l is irrational, we can find k j → ∞ so that [k j l] ∈ Z G and [k j l] → [k 0 l 0 ].
3. The genericity comes from the fact that Z sing G is of co-dimension at least two in T E . From the previous part, we know already that each measure in the image of the Gauß map is a semi-classical measure and the same is true for a measure in the closure of this image, because the set of semi-classical measures is closed. On the other hand, we know that each semi-classical measure is the limit of a sequence of µ φ k j ; because of the assumption on l this implies that each semi-classical measure lies in the closure of the image of the Gauß map.

3 The Barra-Gaspard measure, Weyl formula and the densities of semi-classical limits

In [START_REF] Barra | On the Level Spacing Distribution in Quantum Graphs[END_REF], the authors introduce a l-dependent measure on Z reg G , which we will denote by µ BG, l . The manifold Z reg G is transverse to any vector with strictly positive coordinates and hence oriented. The measure µ BG, l is defined 1 by

µ BG, l = (2π) -#E |ι( l) ∧ e∈E dθ e |
(ι( V )ω is the inner product), which is a Radon measure with strictly positive density everywhere on Z reg G . Proposition 3.1 The mass of the measure µ BG, l is exactly L/π.

Proof.-

The total mass of the measure µ BG, l is less than L/π: let us consider, for e ∈ E, the canonical projection π e : Z G → (R/2πZ) E\e . From the definition of µ BG, l , we get

Z G µ BG, l = e∈E l e (R/2πZ) E\e deg e (θ)| ∧ dθ e |
where deg e (θ) is the cardinal of π -1 e (θ). The fact that δ G is of degree 1 w.r. to each (cos θ e , sin θ e ) implies that deg e ≤ 2 and the upper bound of the mass.

In fact deg e ≡ 2 as follows from Lemma 3.2 below and the Weyl asymptotic formula (see [START_REF] Berkolaiko | Introduction to quantum graphs[END_REF] p. 95)

1 Avoiding the intrinsic calculus of exterior differential forms, the Barra-Gaspard measure can be defined in the following less "cryptic" way: if dσ Z is the measure on Z reg G associated to the metric induced by the flat metric e∈E dθ 2 e on T E and ± ν are the unit normal vector fields to Z reg G , we put µ BG, l := (2π) -#E | ν. l|dσ Z .

Theorem 3.1 We have (Weyl's law)

lim K→∞ 1 K #{0 ≤ k ≤ K| [k l] ∈ Z G } = L π .
We will need the following Lemma, similar to Proposition 4.4 of [START_REF] Berkolaiko | Relationship between scattering matrix and spectrum of quantum graphs[END_REF] and coming also from the ideas of Barra-Gaspard:

Lemma 3.1 If l is irrational and D ⊂ Z reg
G is a compact domain with piecewise smooth boundary, we have

lim K→∞ 1 K #{k j | 0 < k j ≤ K, [k j l] ∈ D} = D µ BG, l .
Similarly, if f : Z G → R has a compact support in Z reg G , we have:

lim K→∞ 1 K 0<k j ≤K, [k j l]∈Z G f ([k j l]) = Z G f µ BG, l .
Proof.-Let us choose ε > 0 small enough so that the map

F : [-ε, ε] × D → T E , defined by F (t, θ) = θ + t l, is a smooth embedding of image D ε .
From the unique ergodicity of the Kronecker flows on the tori, we get

lim K→∞ 1 K |{k | 0 < k ≤ K, [k l] ∈ D ε }| = (2π) -#E vol(D ε ) (2)
where |X| denote the Lebesgue measure of a set X ⊂ R. We observe that [k l] belongs to D ε if and only if there exists j so that [k j l] ∈ D and k l = [k j l] + t l with |t| ≤ ε. The lefthandside of Equation ( 2) is equal to

lim K→∞ 2ε K #{k j | 0 < k j ≤ K, [k j l] ∈ D}
while, using the definition of µ BG, l , the righthandside of Equation ( 2) is equal to 2εµ BG, l (D).

We can remove the Assumption that D is compactly supported in Z reg G as follows:

Lemma 3.2 If l belongs to G G , we have lim K→∞ 1 K #{k j | 0 < k j ≤ K, [k j l] ∈ Z G } = Z G µ BG, l .
A similar result holds for the integration of a continuous function f on Z G :

lim K→∞ 1 K 0<k j ≤K, [k j l]∈Z G f ([k j l]) = Z G f µ BG, l .
Proof.-Let R ε be the ball of radius ε in Z G centered on Z sing G and Rε be the set Rε := {z + t l|z ∈ R ε , 0 ≤ t ≤ ε} .

We have vol( Rε ) = O(ε 2 ), because the codimension of Z sing G in T E is larger than 2. Using the result of Appendix D, there exists a constant C > 0, so that, for any n ∈ N, we have:

#{k|n < k ≤ n+1, [k l] ∈ R ε } ≤ C ε |{k ′ |n-ε ≤ k ′ ≤ n+1+ε, [k ′ l] ∈ Rε }| (if [k ′ l] belongs to Rε , there exists k so that [k l] ∈ R ε and |k -k ′ | ≤ ε;
the constant C is an uniform upper bound on the number of solutions of δ G (k l) = 0 with n < k ≤ n + 1). Assuming that K is an integer and summing the previous inequalities from n = 0 to n = K -1, we get a constant C so that

1 K #{k|0 < k ≤ K, [k l] ∈ R ε } ≤ C εK |{k ′ |0 ≤ k ′ ≤ K +1, [k ′ l] ∈ Rε }| .
The limit of the righthandside as K → ∞ is C/ε times the volume of Rε and can be close to 0 by choosing ε small enough. The proof is completed by writing

Z G = (Z G ∩ R ε ) ∪ (Z G \ Z G ∩ R ε )
, by using Lemma 3.1 for the main term and by using the finitness of the mass of µ BG, l (first part of the proof of Proposition 3.1).

The Barra-Gaspard measure is related to the densities of sequences of eigenvalues giving a given semi-classical limit. This density vanishes in general, so we have to say it in the following way: Theorem 3.2 Let D ⊂ P E be a compact domain with smooth boundary and consider a sequence of eigenfunctions φ k j of some ∆ l with l generic. Let us assume that all semi-classical limits of the µ φ k j lie in D, then the density of the sequence k j is bounded from above in terms of µ BG, l as follows:

lim sup K→∞ #{k j ≤ K} K ≤ µ BG, l Γ -1 (D) .
The converse is true; for any generic l and for any compact domain D ⊂ P E , there exists a sub-sequence φ k j of density µ BG, l (Γ -1 (D)) so that the semi-classical limits associated to sub-sequences of φ k j belongs to D.

Proof.-

Let D ′ ⊂ P E a neighborhood of D. Then for j large enough, Γ l ([k j l]) belongs to D ′ . So that, from a slight extension of Lemma 3.2 to domains in Z G , we get the upper bound µ BG, l (Γ -1 l (D ′ ). For, the converse, it is enough to take the sequence of k j 's so that [k j l] belongs to Γ -1 (D).

We get the following Corollary 3.1 If l belongs to Z reg G and l is generic, let φ be an eigenfunction of ∆ l with eigenvalue 1. Then, for all neighborhoods U of µ φ , there exists sub-sequences of positive densities of the eigenfunctions of ∆ l so that the semi-classical limits of sub-sequences belongs to Γ(U).

Corollary 3.2 If l is generic and there exists an eigenfunction φ of ∆ l so that µ φ is not the Liouville measure, then QEF does not holds for (G, l).

Moreover, we have the following link with the Liouville measure: Theorem 3.3 Let Γ l be the map Γ normalized so that the sums m e |dt e | are probabilities, then

Γ l (θ)dµ BG, l = 1 π e |dt e | .
This can be reformulated as "The average of the Gauß map with respect to µ BG, l is the Liouville measure". On the other hand, we have

Γ l ([k j l]) = 1 2 (a 2 j,e + b 2 j,e ) + O(1/k) . Using Lemma 3.2, we get lim K→∞ A e (K) = l e Z G Γ l (θ) e dµ BG, l .

Scars

Let us look at semi-classical measures with small supports; we have the: Theorem 4.1 Let G be given. The minimal supports of the semi-classical measures for a generic l are the simple cycles and the simple paths between two vertices of degree 1 of G. These measures are extremal points of the convex hull of all semi-classical measures.

We start with the Lemma 4.1 Let K ⊂ |G| be the support of a semi-classical measure µ. Then K is an union of edges of G and every vertex of K is of degree ≥ 2 in K or is of degree 1 in G.

Proof of the Lemma.-

From the first Assertion of Theorem 2.1, we deduce that µ = µ φ where φ is an eigenfunction of some ∆ l∞ on G. The Lemma follows then from the Kirchoff conditions applied to φ.

Proof of the Theorem.-

• Simple paths joining to vertices of degree 1 are minimal supports: Let γ be a simple oriented path whose N vertices are (1, 2, • • • , N) and choose a vector l so that the lengths of the edges of the path are

l 0 = (1/2, 1, 1, • • • , 1, 1/2).
If we parametrize this path by 0 ≤ t ≤ N -2, the function φ 1 defined by φ 1 = cos t on γ and 0 outside is an eigenfunction of ∆ l with eigenvalue π 2 . I claim that we can choose such a vector l extending l 0 so that the eigenvalue π 2 of ∆ l is simple: if it is not, let X := ker ∆ l -π 2 , and l t defined by (l t ) e = (1 -t)l e for e / ∈ γ and (l t ) e = l e for e ∈ γ. Then the quadratic form on X defined by f → ∆f |f vanishes on φ 1 and is > 0 in any other direction (because as we have seen the support of φ 1 is minimal). It implies that π 2 is a simple eigenvalue for ∆ lt for small non-zero t. It follows that the uniform measure on γ is a semi-classical measure for this choice of l and hence for all generic l's. The minimality follows from Lemma 4.1.

• Simple cycles are minimal supports: Let γ be a simple oriented cycle whose N vertices are (1, 2, • • • , N -1, N = 1) and choose a vector l so that the lengths of the edges of γ are 1. By an argument similar to the case of a simple path, we get that the uniform measure on γ is a semi-classical measure for this choice of l and all irrational l's.

Again the minimality follows from lemma 4.1.

• If K is the support of a semi-classical measure, K contains a simple path joining 2 vertices of degree 1 of G or a simple cycle of G: if K contains no simple cycles, K is a forest and every vertex of degree 1 of K is also of degree 1 in G. So that every sub-tree of K contains simple paths joining 2 vertices of degree 1 in G.

As a Corollary, we get Theorem 4.2 For a generic l, QEF holds for ∆ l if and only if |G| is homeomorphic to a circle or to an interval.

Any connected graph which is not homeomorphic to a circle or an interval contains as strict sub-graphs a simple cycle or a path whose ends are of degree one. The Theorem 3.3 implies that the image of Z reg G by the Gauß map contains at least one line distinct from the Liouville measure. The proof is completed by applying Corollary 3.2.

Ergodicity of the geodesic flow on graphs

In the case of a connected quantum graph, the classical dynamics is ergodic as shown from the study of the associated Perron-Frobenius operator done in [START_REF] Barra | Classical dynamics on graphs[END_REF]. The phase space Z of a Quantum graph G = (V, E, l) (the unit cotangent bundle) can be identified with the set of oriented edges: to a point x of an oriented edge, we associate the unit co-vector pointing in the direction given from the orientation. Using the probabilities given from the transition coefficients in Appendix B, we get the geodesic flow on Z as a Markov process. We have the Theorem 5.1 If G is connected and is not homeomorphic to a circle, the geodesic flow on (V, E, l) is ergodic.

In order to prove the previous result, we introduce the Perron-Frobenius semigroup T t , t ≥ 0 acting on L ∞ (|G|, |dx| l ) as follows:

T t f (x) = γ:[0,t]→|G|, γ(0)=x w(γ)f (γ(t)) ,
where the sum is over the continuous paths with speed 1 starting from x at time 0 and w(γ) is the product of the transitions probabilities at all t for which γ(t) is a vertex. Proof.-It is enough to prove that the only functions invariant by the Perron-Frobenius semi-group (T t ) t>0 are the constant functions. We see first that such a function f has to be constant on each oriented edge by using at a point x the invariance by T t for t small. Moreover if G is connected and is not homeomorphic to a circle, the geodesic flow is transitive: for any pair x, y ∈ Z there exists a geodesic from x to y. Let us choose f constant on the oriented edges and invariant by the semi-group (T t ) t>0 . Let us choose an edge e 0 sot that ∀x ∈ Z, f (x) ≤ f (e 0 ) and x 0 ∈ e 0 . We have T t f (x 0 ) = f (x 0 ) and T t f (x 0 ) = γ:[0,t]→Z w(γ)f (γ(t)). Using the fact that γ:[0,t]→Z w(γ) = 1, we get that f (y) = f (x 0 ) if there is a geodesic γ so that γ(0) = x 0 and γ(t) = y. This holds for all y ∈ Z if the geodesic flow is transitive.

From the previous study, we see that the QEF Theorem is not valid for Quantum Graphs even if the geodesic flow is ergodic, which is the case for all connected graphs which are not homeomorphic to a circle. In view of the main result of [START_REF] Jakobson | The semiclassical theory of discontinuous systems and ray-splitting billiards (with an Appendix of Yves Colin de Verdière)[END_REF] which says that QE holds if the geodesic flow is ergodic and the set of recombining geodesics is of measure 0, this is due to the fact that there are a lot of recombining geodesics: for example in a star graph, they are many geodesics starting from x in an edge e 1 an coming back to x in the opposite direction following a geodesic containing k 1 times the edge e 1 and k 2 times the edge e 2 with k 1 , k 2 ≥ 1 and with different orders.

Examples

The star graph with three edges

Let us consider for simplicity the case of a star graph with three edges G = (V, E) where l 1 , l 2 , l 3 are the lengths of three edges. The function δ G can be computed as follows: we assume that, we parametrize the jth edge by 0 ≤ t j ≤ l j where 0 corresponds to the vertex of degree 1. Then an eigenfunction of eigenvalue k 2 will be of the form φ(t j ) = a j cos kt j . Putting x j = cos kt j and y j = sin kt j , we get the three equations

a 1 x 1 = a 2 x 2 = a 3 x 3 , a 1 y 1 + a 2 y 2 + a 3 y 3 = 0 . Hence δ G (x, y) = x 1 x 2 y 3 + x 2 x 3 y 1 + x 3 x 1 y 2 .
Singularities of Σ: The surface Σ G ⊂ T E is invariant by the eight translations whose vectors have coordinates 0 or π. We will restrict ourselves to the intersection of Σ G with the cube C = [-π/2, π/2] 3 . The seven other cubes are deduced by translations. The surface Σ G is also invariant by the central symmetry σ : (θ j ) → (-θ j ).

We can cover Σ by four types of charts and use adapted coordinates taken from the set X j = x j /y j , Y j = y j /x j :

1. In the domain x 1 x 2 x 3 = 0, we get Y 1 + Y 2 + Y 3 = 0 which is smooth.

2. In the domain y 1 y 2 y 3 = 0, we get X 1 X 2 +X 2 X 3 +X 3 X 1 = 0 which is singular at the eight points where all x j vanish. They are "diabolical" points located at the vertices of the cubes.

3. In the domains, x 1 x 2 y 3 = 0 and x 1 y 2 y 3 = 0, Σ G is smooth.

The boundary of the closure of the intersection Σ 0 = Σ∩] -π/2, π/2[ 3 is the union of the six edges of C which have no vertex (-π/2, -π/2, -π/2) or (π/2, π/2, π/2). We call this closed path the equator of C. The surface Σ 0 is a smooth 2-disk whose boundary is the equator of C.

The set M G is the cone

3 i=1 m 2 i ≤ 2 1≤i<j≤3 m i m j .
In particular, this closed set is not equal to P E .

The eight figure

Let us denote by G 8 the graph with one vertex and two edges (two loops). We have

δ G 8 (θ 1 , θ 2 ) = sin θ 1 2 sin θ 2 2 sin θ 1 + θ 2 2 .
The set Z G 8 is the union of the circles θ 1 = 0, θ 2 = 0 and θ 1 + θ 2 = 0. The image by the Gauß map is the union of the three lines m 2 = 0, m 1 = 0 and m 1 = m 2 . The associated densities are up to global normalization l 1 , l 2 , l 1 + l 2 . This implies that there exactly three semi-classical limits for an irrational length vector. The Liouville measure |dt 1 |+|dt 2 | has relative density 1 2 . On this example we see that the set of semi-classical measure is not even connected and that the scars give measures which are extremal point of their convex hull.

The cherry

Let G C be the cherry graph consisting of one loop with an attached edge. Let us denote by l 1 the length of the loop and by l 2 the length of the edge. We get for Z G C the equation: sin θ 1 sin θ 2 + 2(1 -cos θ 1 ) cos θ 2 = 0.

The set Z G C is the union of the three circles

{θ 1 = 0} ∪ {tan θ 2 + 2 tan θ 1 /2 = 0}
The circle {θ 1 = 0} correspond to the scars localized on the loop ; the other part corresponds to a continuum of semi-classical measures

m 1 |dt 1 | + m 2 |dt 2 | with m 1 l 1 + m 2 l 2 = 1, 1 ≤ m 2 /m 1 ≤ 4.

Limits of graphs and a new proof of Friedlander's Theorem

From the characterization of the spectrum of ∆ l as the set of k 2 so that [k l] belongs to Z G , on can still define the spectrum of ∆ l for l a real vector. In particular, one can take some lengths to be zero and the others > 0. What is then the interpretation of this "spectrum"? Let G be a graph as before. Given a set of edges X ⊂ E, we introduce a new graph G X obtained by contracting all edges e ∈ X. From the point of view of Riemannian metrics, the graph G X can be interpreted as the graph G where the lengths of the edges in X vanish. We have the Lemma 7.1 For any connected graph G = (V, E) not homeomorphic to the circle or the interval, there exists a set X ⊂ E so that G X is homeomorphic to the star graph with three edges, to G 8 or to G C .

Let us denote by b 1 (G) the first Betti number of |G|, i.e. the dimension of the space of cycles of |G|.

The first case occur if G is a tree not reduced to an interval, the second one if b 1 (G) ≥ 2 and the third one if b 1 (G) = 1 and |G| is not a circle.

Let (Z G ) X be the intersection of Z G with the torus T X = {θ e = 0, ∀e ∈ X}. We have clearly an identification of (Z G ) X with Z G X .

Any non singular point of Z G X is in this way associated to a non singular point of Z G . This gives an independent proof of Friedlander's result by using the fact that, for each of the previous reduced graphs, the manifold Z G admits non singular points.

Theorem 0. 1

 1 Let us fix G. For a generic metric l, the set of non-normalized semi-classical measures is the set of all e∈E m e |dt e | where m ∈ M G and where |dt e | is the Riemannian measure on the edge e, i.e. t e is an arc-length parametrization of the edge e. Moreover the densities of the corresponding eigenfunctions sub-sequences are bounded in terms of the image by Γ of a measure µ BG, l on Z reg G introduced in [BG00, BG01].

L

  ξ,η (a, b) = 0 of 2#E equations with the same number of unknowns, because the values of the function φ and its derivatives divided by k at the vertices are (linear) functions of ξ e and η e . Let us remark that if we change any (ξ e , η e ) into (-ξ e , -η e ), the solutions of the new system are changed by (a e , b e ) → (-a e , -b e ).

  + b 2 j,e )where the normalized eigenfunction φ j writes, on the edge e, φ j (t e ) = a j,e cos kt e + b j,e sin kt e . From the local Weyl Theorem and the fact that e |φ j (t e )| 2 dt e = l e 2 (a 2 j,e + b 2 j,e ) + O(1/k) , we get that lim K→∞ A e (K) = l e /π .

Figure 1 :

 1 Figure 1: The 3 examples: the black circles are the vertices and the white circles are the middle of the edges

Figure 2 :

 2 Figure 2: the surface Z star and the equator of the cube; the map Γ from Z star to the semi-classical measures.

A

  The derivatives of the eigenvalues w.r. to the edge lengths This Lemma is contained in [Fr05]: Lemma A.1 If λ is a non degenerate eigenvalue of ∆ l with a normalized eigenfunction φ(t e ) = a e cos kt e + b e sin kt e on the edge e, the derivative of λ w.r. to l e is given by ∂λ ∂l e = -λ a 2 e + b 2 e . Proof.-Let us put t = t e , I =] -l e /2, l e /2[ and choose a function ψ ∈ C ∞ o (I, R) and the metric g u = exp(4uψ(t))|dt| 2 on the edge e and independent of u on the other edges. Then we have dl e /du = 2 I ψ(t)|dt|, φ 2 u = φ ′ 2 0 + I e 2uψ(t) φ 2 (t)|dt| , and the Dirichlet integral q u (φ) = q ′ 0 (φ) + I e -2uψ(t) φ ′ 2 (t)|dt| ,

  Definition 2.2 A semi-classical limit for ∆ l is a weak limit of a sequence of measures e∈E |φ k j (t e )| 2 |dt e | on |G| where φ k j are non-zero eigenfunctions of ∆ l with eigenvalues k 2 j → +∞. We do not ask the eigenfunctions to be L 2 -normalized. Our semiclassical limits are in general not probability measures.

	Remark 2.2
	Remark 2.1 We do not use a lift of the measures to the cotangent space as in
	the Shnirelman Theorem.

Let us denote by P E the cone [0, +∞[ E \{0}. For any m = (m e ) e∈E ∈ P E and any l, we identify m with the measure e∈E m e |dt e | on |G|. In other words, if l is given, we consider P E as a sub-cone of the cone of positive Radon measures on |G|. Our goal is to characterize the measures which are semi-classical limits. We will need a Definition 2.1 If φ is an eigenfunction of some ∆ l with eigenvalue k 2 > 0, the restriction of φ to the edge e writes φ(t e ) = a e cos kt e + b e sin kt e ; we denote by µ φ the measure on |G| defined by µ φ = e (a 2 e + b 2 e )|dt e | which belongs to P E .

where ′ 0 denotes the integrals on the other edges which are independent of u. Let now take the u-derivative of the Rayleigh quotient q u (φ)/ φ 2 u at u = 0, we get dλ/du = -2 I ψ(t)(φ ′ (t) 2 + λφ(t) 2 )|dt| from which the result follows.

B Appendix: the transition probabilities for a quantum graph

We want to describe the way a wave arriving at a vertex of a quantum graph splits into several waves. Let us denote by O the vertex of degree d and by e j , j = 1, • • • , d the d-edges arriving at O. Let us denote the arc-length coordinate x j along e j starting from 0 at O. Let us consider a function f 1 compactly supported in ]0, +∞[ and a wave u(x, t) defined on e 1 by u(x 1 , t) = f 1 (x 1 +t)+g 1 (x 1 -t) and, on e j for 2 ≤ j ≤ d, by u(x j , t) = g 2 (x j -t). From the Kirchhoff conditions, we get f

Integrating the second equation, we get f 1 (t) = g 1 (-t) + (d -1)g 2 (-t) (we see that the integration constant vanishes by putting t = 0). So that we get

The transition probabilities are the numbers

The quantum graph is said classically ergodic if the following Markov process defined on the unit tangent bundle of the metric graph is ergodic: follow the edges with unit speed and arriving at a vertex use the transition probabilities defined before. We can assume that the graph has no vertex of degree two.

In this case the spectrum is given by the k 2 j , k j ≥ 0 so that [k] ∈ Z G . Using Weyl asymptotics, the number of k j 's with multiplicity is 2#E. On the other hand, we find from [START_REF] Nicaise | Some results on spectral theory over networks, applied to nerve impulse transmission, Orthogonal polynomials and applications[END_REF][START_REF] Nicaise | Approche spectrale des problèmes de diffusion sur les réseaux[END_REF][START_REF] Cattaneo | The Spectrum of the Continuous Laplacian on a Graph[END_REF], that the eigenvalues of ∆ 1 are given in terms of the eigenvalues µ l , l = 1, • • • , #V, of the weighted adjacency operator defined

The result is the following one for the k j :

• For each |µ l | < 1, 2 values of k defined by cos k = µ l .

• The value k = 0 with multiplicity 1 + b 1 (G).

At the end, we have, in the bipartite case 2#E = 2(#V -2) + 2b 1 (G) + 2, and in the non-bipartite case 2#E = 2(#V -1) + 2b 1 (G). Both formulas give the Euler formula for G:

D Appendix: a Lemma on polynomial quasiperiodic functions

Let P be a non zero real valued polynomial of 2N variables and consider, for α ∈ R N , the function f (t) := P (cos tα 1 , sin tα 1 , cos tα 2 , • • • ) .

We have the Lemma D.1 The number N(x) of zeroes (with multiplicity) of f in the interval [x, x + 1] is uniformly bounded for x ∈ R.

Proof.-

The function f (t) extends to a bounded holomorphic function in the strip -2 < ℑt < 2. The set of functions f

Let us assume that N(x) is unbounded, we can choose a sequence x j so that N(x j ) → ∞ and f x j converges on D to a non-zero holomorphic function f ∞ . For j large enough, the number of zeroes N(x j ) of f x j on [0, 1] is less than the the (finite) number of zeroes of f ∞ on [-1, 2]. The contradiction follows.