Keywords: Matrice d'intervalles, matrice symétrique, analyse par intervalles, valeur propre, borne sur les valeurs propres

Caractérisation et approximation des ensembles de valeurs propres des matrices symétriques intervalles

Résumé : We consider the eigenvalue problem for the case where the input matrix is symmetric and its entries perturb in some given intervals. We present a characterization of some of the exact boundary points, which allows us to introduce an inner approximation algorithm, that in many case estimates exact bounds. To our knowledge, this is the first algorithm that is able to guarantee exactness. We illustrate our approach by several examples and numerical experiments.

Introduction

Computing eigenvalues of a matrix is a basic linear algebraic task used throughout in mathematics, physics and computer science. Real life makes this problem more complicated by imposing uncertainties and measurement errors on the matrix entries. We suppose we are given some compact intervals in which the matrix entries can perturb. The set of all possible real eigenvalues forms a compact set, and the question that we deal with in this paper is how to characterize and compute it.

The interval eigenvalue problem has its own history. The first results are probably due to Deif [START_REF] Deif | The interval eigenvalue problem[END_REF] and Rohn & Deif [START_REF] Rohn | On the range of eigenvalues of an interval matrix[END_REF]: bounds for real and imaginary parts for complex eigenvalues were studied by Deif [START_REF] Deif | The interval eigenvalue problem[END_REF], while Rohn & Deif [START_REF] Rohn | On the range of eigenvalues of an interval matrix[END_REF] considered real eigenvalues. Their theorems are applicable only under an assumption on sign pattern invariancy of eigenvectors, which is not easy to verify (cf. [START_REF] Deif | On the invariance of the sign pattern of matrix eigenvectors under perturbation[END_REF]). A boundary point characterization of eigenvalue set was given by Rohn [START_REF] Rohn | Interval matrices: Singularity and real eigenvalues[END_REF], and it was used by Hladík et al. [START_REF] Hladík | An algorithm for the real interval eigenvalue problem[END_REF] to develop a branch & prune algorithm producing an arbitrarily tight approximation of the eigenvalue set. Another approximate method was given by Qiu et al. [START_REF] Qiu | An approximate method for the standard interval eigenvalue problem of real non-symmetric interval matrices[END_REF]. The related topic of finding verified intervals of eigenvalues for real matrices was studied in e.g. [START_REF] Alefeld | Interval analysis: Theory and applications[END_REF].

In this paper we focus on the case of the symmetric eigenvalue problem. Symmetric matrices naturally appear in many practical problems, but symmetric interval matrices are hard to deal with. This is so, mainly due to the so-called dependencies, that is, correlations between the matrix components. If we "forget" these dependencies and solve the problem by reducing it to the previous case, then the results will be greatly overestimated, in general (but not the extremal points, see Theorem 2). From now on we consider only the symmetric case.

Due to the dependencies just mentioned, the theoretical background for the eigenvalue problem of symmetric interval matrices is not wide enough and there are few practical methods. The known results are that by Deif [START_REF] Deif | The interval eigenvalue problem[END_REF] and Hertz [START_REF] Hertz | The extreme eigenvalues and stability of real symmetric interval matrices[END_REF]. Deif [START_REF] Deif | The interval eigenvalue problem[END_REF] gives an exact description of the eigenvalue set together with restrictive its assumptions. Hertz [START_REF] Hertz | The extreme eigenvalues and stability of real symmetric interval matrices[END_REF] (cf. [START_REF] Rohn | A handbook of results on interval linear problems[END_REF]) proposed a formula for computing two extremal points of the eigenvalue set-the largest and the smallest one. As the problem itself is very hard, it is not surprising conjectures on the problem [START_REF] Qiu | Solution theorems for the standard eigenvalue problem of structures with uncertain-but-bounded parameters[END_REF] turned out to be wrong [START_REF] Yuan | An evolution strategy method for computing eigenvalue bounds of interval matrices[END_REF].

In the recent years, several approximation algorithms have been developed. An evolution strategy method by Yuan et al. [START_REF] Yuan | An evolution strategy method for computing eigenvalue bounds of interval matrices[END_REF] yields an inner approximation of the eigenvalue set. By means of matrix perturbation theory, Qiu et al. [START_REF] Qiu | Bounds of eigenvalues for structures with an interval description of uncertain-but-non-random parameters[END_REF] proposed an algorithm for approximate bounds, and Leng & He [START_REF] Leng | Computing eigenvalue bounds of structures with uncertain-but-non-random parameters by a method based on perturbation theory[END_REF] for an outer estimation. An outer estimation was also considered by Kolev [START_REF] Kolev | Outer interval solution of the eigenvalue problem under general form parametric dependencies[END_REF], but for general case with nonlinear dependencies. Some initial bounds that are easy and fast to compute were discussed by Hladík et al. [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF]. An iterative algorithm for outer estimation was given by Beaumont [START_REF] Beaumont | An algorithm for symmetric interval eigenvalue problem[END_REF].

This problem has a lot of applications in the field of mechanics and engineering. Let us mention for instance automobile suspension systems [START_REF] Qiu | An approximate method for the standard interval eigenvalue problem of real non-symmetric interval matrices[END_REF], mass structures [START_REF] Qiu | Bounds of eigenvalues for structures with an interval description of uncertain-but-non-random parameters[END_REF], vibrating systems [START_REF] Dimarogonas | Interval analysis of vibrating systems[END_REF], principal component analysis [START_REF] Gioia | Principal component analysis on interval data[END_REF], and robotics [START_REF] Chablat | An interval analysis based study for the design and the comparison of 3-dof parallel kinematic machines[END_REF]. Another applications arise from the engineering area concerning singular values and condition numbers. Using the well-known Jordan-Wielandt transformation [START_REF] Golub | Matrix computations. 3rd ed[END_REF][START_REF] Horn | Matrix analysis[END_REF][START_REF] Meyer | Matrix analysis and applied linear algebra[END_REF] we can simply reduce a singular value calculation to a symmetric eigenvalue one.

The rest of the paper is structured as follows: In Sec. 2 we introduce the notation that we use throughout the paper. In Sec. 3 we present our main theoretical result, and in Sec. 4 we develop our algorithms for the problem. Finally, in Sec. 5 we demonstrate our approach by a number of examples and numerical experiments, and we conclude in Sec. 6.

Basic definitions and theoretical background

Let us introduce some notions first. An interval matrix is defined as

A := [A, A] = {A ∈ R m×n ; A ≤ A ≤ A},
where A, A ∈ R m×n , A ≤ A, are given matrices. By

A c := 1 2 (A + A), A ∆ := 1 2 (A -A)
we denote the midpoint and the radius of A, respectively. By an interval linear system of equations Ax = b we mean a family of systems Ax = b, such that A ∈ A, b ∈ b. In a similar way we introduce interval linear systems of inequalities and mixed systems of equations and inequalities. A vector x is a solution of Ax = b if it is a solution of Ax = b for some A ∈ A and b ∈ b. We assume that the reader is familiar with the basics of interval arithmetic; for further details we refer to e.g. [START_REF] Alefeld | Introduction to interval computations[END_REF][START_REF] Hansen | Global optimization using interval analysis[END_REF][START_REF] Neumaier | Interval methods for systems of equations[END_REF].

Let F be a family of n × n matrices. We denote the eigenvalue set of the family F by Λ(F ) := {λ ∈ R; Ax = λx, x = 0, A ∈ F }.

A symmetric interval matrix as defined as

A S := {A ∈ A | A = A T }.
It is usually a proper subset of A. Considering the eigenvalue set Λ(A), it, generally, represents an overestimation of Λ(A S ). That is why we focus directly on eigenvalue set of the symmetric counterpart, even though we must take into account the dependencies between the elements, in the definition of A S . A real symmetric matrix A ∈ R n×n has always n real eigenvalues, let us sort them in a non-increasing order

λ 1 (A) ≥ λ 2 (A) ≥ • • • ≥ λ n (A).
We extend this notation for symmetric interval matrices [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF]. The intervals can be disjoint, can overlap, or some of them, can be identical. However, what it can not happen is one interval to be a proper subset of another interval. The union of these intervals produces Λ(A S ).

λ i (A S ) := λ i (A) | A ∈ A S .

These sets represent n compact intervals λ

i (A S ) = [λ i (A S ), λ i (A S )], i = 1, . . . , n; cf.
Throughout the paper we use the following notation:

λ i (A)
the ith eigenvalue of a symmetric matrix A (in a nonincreasing order) σ i (A) the ith singular value of a matrix A (in a non-increasing order) v i (A) the eigenvector associated to the ith eigenvalue of a symmetric matrix A ρ(A)

the spectral radius of a matrix A ∂S the boundary of a set S conv S the convex hull of a set S diag(y) the diagonal matrix with entries y 1 , . . . , y n sgn(x) the sign vector of a vector x, i.e., sgn(x) = (sgn(x 1 ), . . . , sgn(x n )) T

x 2 the Euclidean vector norm, i.e.,

x 2 = √ x T x x ∞
the Chebyshev (maximum) vector norm, i.e., x ∞ = max {|x| i ; i = 1, . . . , n} x ≤ y, A ≤ B vector and matrix relations are understood component-wise

Main theorem

The following theorem is the main theoretical result of the the present paper. We remind the reader that the principal m × m submatrix of a given n × n matrix is any submatrix obtained by eliminating any nm rows and the same nm columns.

Theorem 1. Let λ ∈ ∂Λ(A S

). There is a principal submatrix A S ∈ R k×k of A S such that:

• If λ = λ j (A S ) for some j ∈ {1, . . . , n}, then λ ∈ λ i A c + diag(z) A ∆ diag(z) ; z ∈ {±1} k , i = 1, . . . , k . (1)
• If λ = λ j (A S ) for some j ∈ {1, . . . , n}, then

λ ∈ λ i A c -diag(z) A ∆ diag(z) ; z ∈ {±1} k , i = 1, . . . , k . (2)
Proof. Let λ ∈ ∂Λ(A S ). Then either λ = λ j (A S ) or λ = λ j (A S ), for some j ∈ {1, . . . , n}. We assume the former case. The latter could be proved similarly. The eigenvalue λ is achieved for a matrix A ∈ A. It is without loss of generality to assume that the corresponding eigenvector x, x 2 = 1, is of the form x = (0 T , y T ) T , where y ∈ R k and y i = 0, for all 1 ≤ i ≤ k, and for some k ∈ {1, . . . , n}. The symmetric interval matrix A S can be written as

A S = B S C C T D S ,
where

B S ⊂ R (n-k)×(n-k) , C ⊂ R (n-k)×k , D S ⊂ R k×k .
From the basic equality Ax = λx it follows that

Cy = 0 for some C ∈ C, (3)
and

Dy = λy for some D ∈ D S . (4)
We focus on the latter relation; it says that λ is an eigenvalue of D. We will show that D S is the required principal submatrix A S and D could be written as in [START_REF]CLAPACK -Linear Algebra PACKage written for C[END_REF]. From (4) we have that λ = y T Dy, and hence the partial derivatives are

∂λ ∂d ij = y i y j = 0, i, j = 1, . . . , k.
This relation strongly influences the structure of D. If y i y j > 0, then

d ij = d ij .
This is so, because otherwise by increasing d ij we also increase the value of λ, which contradicts our assumption that λ lies on the upper boundary of Λ(A S ). Likewise, y i y j < 0 implies d ij = d ij . This allows us to write D in the following more compact form

D = D c + diag(z) D ∆ diag(z), (5)
where z = sgn(y) ∈ {±1} k . Therefore, λ belongs to a set as the one presented in the right-hand side of (1), which completes the proof.

Note that not every λ j (A S ) or λ j (A S ) is a boundary point of Λ(A S ). Theorem 1 is also true for such λ j (A S ) or λ j (A S ) that are non-boundary, but make no multiple eigenvalue (since the corresponding eigenvector is uniquely determined). However, truthfulness of Theorem 1 for all λ j (A S ) and λ j (A S ), j = 1, . . . , n, is still an open question. Moreover, full characterization of all λ j (A S ) and λ j (A S ), j = 1, . . . , n, is lacking, too.

As we have already mentioned, in general, the eigenvalue set of an interval matrix is larger than the eigenvalue set of its symmetric counterpart. This is true even if both the midpoint and radius matrices are symmetric (see Example 1). The following theorem says that overestimation caused by the additional matrices is somehow limited by the intermediate area.

Theorem 2. Let A c , A ∆ ∈ R n×n be symmetric matrices. Then conv Λ(A S ) = conv Λ(A).

Proof. The inclusion conv Λ(A S ) ⊆ conv Λ(A) follows from the definition of the convex hull.

Let A ∈ A be arbitrary, λ one of its real eigenvalues, and x the corresponding eigenvector, where x 2 = 1. Let B := 1 2 (A + A T ) ∈ A S , then the following holds:

λ = x T Ax ≤ max y 2=1 y T Ay = max y 2=1 y T By = λ 1 (B) ∈ conv Λ(A S ). Similarly, λ = x T Ax ≥ min y 2=1 y T Ay = min y 2=1 y T By = λ n (B) ∈ conv Λ(A S ).
Therefore λ ∈ conv Λ(A S ), and so conv Λ(A) ⊆ conv Λ(A S ), which completes the proof.

Theorem 1 naturally yields an algorithm to compute a very sharp inner approximation of Λ(A S ), which could also be exact in some cases. We will present the algorithm in the sequel (Section 4.3). First, we define some notions and propose two simple but useful methods for inner approximations.

Any subset of S is called an inner approximation. Similarly, any set that contains S is called an outer approximation. In our case, an inner approximation of the eigenvalue set λ i (A S ), is denoted by

µ i (A S ) = [µ i (A S ), µ i (A S )] ⊆ λ i (A S ),
and an outer approximation is denoted by

ω i (A S ) = [ω i (A S ), ω i (A S )] ⊇ λ i (A S ), where 1 ≤ i ≤ n.
From a practical point of view, an outer approximation is usually more useful. However, an inner approximation is also important in some applications. For example, it could be used to measure quality (sharpness) of an outer approximation, or it could be used to prove (Hurwitz or Schur) unstability of certain interval matrices, cf. [START_REF] Rohn | An algorithm for checking stability of symmetric interval matrices[END_REF].

Local improvement

The first algorithm that we present is based on local improvement search technique. A similar method, but for another class of symmetric interval matrices was proposed by Rohn [START_REF] Rohn | An algorithm for checking stability of symmetric interval matrices[END_REF]. The basic idea of the algorithm is to start with an eigenvalue, λ i (A c ), and the corresponding eigenvector, v i (A c ), of the midpoint matrix, A c , and then move to an extremal matrix in A S according to the sign pattern of the eigenvector. The procedure is repeated until no improvement is possible.

Algorithm 1 outputs the upper boundaries µ i (A S ) of the inner approximation [µ i (A S ), µ i (A S )], where 1 ≤ i ≤ n. The lower boundaries, µ i (A S ), can be obtained similarly. The validity of the procedure follows from the fact that every considered matrix, A, belongs to A S . Algorithm 1 (Local improvement for µ i (A S ), i = 1, . . . , n)

1: for i = 1, . . . , n do 2: µ i (A S ) = -∞; 3: A := A c ; 4: while λ i (A) > µ i (A S ) do 5: D := diag(sgn(v i (A))); 6: A := A c + DA ∆ D; 7: µ i (A S ) := λ i (A); 8:
end while 9: end for 10: return µ i (A S ), i = 1, . . . , n.

The algorithm terminates after, at most, 2 n iterations. However, usually in practice the number of iterations is much smaller, which makes the algorithm attractive for applications. Our numerical experiments (Section 5) indicate that the number of iterations is rarely greater than two, even for matrices of dimension 20. Moreover, the resulting inner approximation is quite sharp, depending on the width of intervals in A S . This is not surprising as whenever the input intervals are narrow enough, the algorithm produces, sometimes even after the first iteration, exact bounds; see [START_REF] Deif | The interval eigenvalue problem[END_REF]. We refer the reader to Section 5 for a more detailed presentation of the experiments.

Vertex enumeration

The second method that we present is based on vertex enumeration. It consists of inspecting all matrices

A z := A c + diag(z) A ∆ diag(z), z ∈ {±1} n , z 1 = 1,
and continuously improving an inner approximation µ i (A S ), whenever λ i (A z ) > µ i (A S ), where 1 ≤ i ≤ n. The lower bounds, µ i (A S ), could be obtained in a similar way using the matrices A cdiag(z) A ∆ diag(z), where z ∈ {±1} n , and z 1 = 1. The condition z 1 = 1 follows from the fact that diag(z) A ∆ diag(z) = diag(-z) A ∆ diag(-z), which gives us the freedom to fix one component of z. The number of steps that the algorithm performs is 2 n-1 . Therefore, this method is suitable only for matrices of moderate dimensions.

The main advantages of the vertex enumeration approach are the following. First, it provides us with sharper inner approximation of the eigenvalue sets than the local improvement. Second, two of the computed bounds are exact; by Hertz [START_REF] Hertz | The extreme eigenvalues and stability of real symmetric interval matrices[END_REF] (cf. [START_REF] Rohn | A handbook of results on interval linear problems[END_REF]) and Hertz [START_REF] Hertz | Interval analysis: Eigenvalue bounds of interval matrices[END_REF] we have that µ 1 (A S ) = λ 1 (A S ) and µ n (A S ) = λ n (A S ). The other bounds calculated by the vertex enumeration, even though it was conjectured that there were exact [START_REF] Qiu | Solution theorems for the standard eigenvalue problem of structures with uncertain-but-bounded parameters[END_REF], it turned out that they were not exact, in general [START_REF] Yuan | An evolution strategy method for computing eigenvalue bounds of interval matrices[END_REF] The assertion by Hertz [16, Theorem 1] that µ 1 (A S ) = λ 1 (A S ) and µ n (A S ) = λ n (A S ) is wrong, too; see Example 3. Nevertheless, Theorem 1 and its proof indicate a sufficient condition: If no eigenvector corresponding to an eigenvalue of A S has a zero component, then the vertex enumeration yields exactly the eigenvalue sets λ i (A S ), i = 1, . . . , n.

The efficient implementation of this approach is quite challenging. In order to overcome in practice the exponential complexity of the algorithm, we implemented a branch & bound algorithm, which is in accordance with the suggestions of Rohn [START_REF] Rohn | An algorithm for checking stability of symmetric interval matrices[END_REF]. However, the adopted bounds are not that tight, and the actual running times are usually worse than the direct vertex enumeration. That is why we do not consider further this variant. The direct vertex enumeration scheme for computing the upper bounds, µ i (A S ), is presented in Algorithm 2.

Submatrix vertex enumeration

In this section we present an algorithm that is based on Theorem 1, and it usually produces very tight inner approximations, even exact ones in some cases. The basic idea the algorithm is to enumerate all the vertices of all the principal submatrices of A S . The number of steps performed with this approach is

2 n-1 + n2 n-2 + n 2 2 n-2 + • • • + n2 0 = 1 2 (3 n -1) .
To overcome the obstacle of the exponential number of iterations, at least in practice, we notice that not all eigenvalues of the principal submatrices of the matrices in A S belong to some of the eigenvalue sets λ i (A S ), where 1 ≤ i ≤ n.

For this we will introduce a condition for checking such an inclusion.

Algorithm 2 (Vertex enumeration for µ i (A S ), i = 1, . . . , n)

1: for i = 1, . . . , n do 2:

µ i (A S ) = λ i (A c ); 3: end for 4: for all z ∈ {±1} n , z 1 = 1, do 5:

A := A c + diag(z) A ∆ diag(z); 6: for i = 1, . . . , n do 7: if λ i (A) > µ i (A S ) then 8: µ i (A S ) := λ i (A); 9: end if 10:
end for 11: end for 12: return µ i (A S ), i = 1, . . . , n.

Assume that we are given an inner approximation µ i (A S ) and an outer approximation ω i (A S ) of the eigenvalue sets λ i (A S ); that is µ i (A S ) ⊆ λ i (A S ) ⊆ ω i (A S ), where 1 ≤ i ≤ n. As we will see in the sequel, the quality of the output of our methods depends naturally on the sharpness of the outer approximation used.

Let D S ⊂ R k×k be a principal submatrix of A S and, without loss of generality, assume that it is situated in the right-bottom corner, i.e.,

A S = B S C C T D S ,
where B S ⊂ R (n-k)×(n-k) and C ⊂ R (n-k)×k . Let λ be an eigenvalue of some vertex matrix D ∈ D S which is of the form (5), and let y be the corresponding eigenvector. If the eigenvector is not unique then λ is a multiple eigenvalue and therefore it is a simple eigenvalue of some principal submatrix of D S ; in this case we restrict our consideration to this submatrix. We want to determine whether λ is equal to λ p (A S ) ∈ Λ(A S ) for some fixed p ∈ {1, . . . , n}, or if this is not possible, to improve the upper bound µ p (A S ); the lower bound can be handled accordingly. In view of (3), it must be 0 ∈ Cy , so that λ to be an eigenvalue of some matrix in A S . Now, we are sure that λ ∈ Λ(A S ) and it remains to determine whether λ also belongs to λ p (A S ).

If λ ≤ µ p (A S ), then it is useless to further considering λ, as it will not extend the inner approximation of the pth eigenvalue set. If p = 1 or λ < ω p-1 (A S ), then λ must belong to λ p (A S ), and we can improve the inner bound µ p (A S ) := λ. In this case the algorithm terminates early, and that is the reason we need ω i (A S ) to be as tight as possible, where 1 ≤ i ≤ n.

If p > 1 and λ ≥ ω p-1 (A S ), we proceed as follows. We pick an arbitrary C ∈ C, such that Cy = 0; we refer to, e.g. [START_REF] Rohn | Solvability of systems of interval linear equations and inequalities[END_REF] for details on the selection process. Next, we select an arbitrary B ∈ B S and let

A := B C C T D . (6)

RR n°7544

We compute the eigenvalues of A, and if µ p (A S ) < λ p (A), then we set µ p (A S ) := λ p (A), otherwise we do nothing. However, it can happen that λ = λ i (A S ), and we do not identify it, and hence we do not enlarge the inner estimation µ p (A S ). Nevertheless, if we apply the method for all p = 1, . . . , n and all principal submatrices of A S , then we touch all the boundary points of Λ(A S ). If λ ∈ ∂Λ(A S ), then λ is covered by the resulting inner approximation. In the case when λ is an upper boundary point, we consider the maximal i ∈ {1, . . . , n} such that λ = λ i (A S ) and then the ith eigenvalue of the matrix (6) must be equal to λ. Similarly test are valid for a lower boundary point.

Now we have all the ingredients at hand for the direct version of the submatrix vertex enumeration approach that is presented in Algorithm 3, which improves the upper bound µ p (A S ) of an inner approximation, where the index p is still fixed. Let us also mention that in step 4 of Algorithm 3, the decomposition of A S according to the index set J means that D S is a restriction of A S to the rows and the columns indexed by J, B S is a restriction of A S to the rows and the columns indexed by {1, . . . , n} \ J, and C is a restriction of A S to the rows indexed by {1, . . . , n} \ J and the columns indexed by J.

Algorithm 3 (Direct submatrix vertex enumeration for µ p (A S ))

1: compute outer approximation ω i (A S ), i = 1, . . . , n; 2: call Algorithm 1 to get inner approximation µ i (A S ), i = 1, . . . , n; 3: for all J ⊆ {1, . . . , n}, J = ∅, do

A := Bc C C T D ; 16: if λ p (A) > µ p (A S ) then 17:
µ p (A S ) := λ p (A); end for 23: end for 24: return µ p (A S ).

RR n°7544

Branch & bound improvement

In order to tackle the exponential worst case complexity of Algorithm 3, we propose the following modification. Instead of inspecting all non-empty subsets of {1, . . . , n} in step 3, we exploit a branch & bound method, which may skip some useless subsets. Let a non-empty J ⊆ {1, . . . , n} be given. The new, possible improved, eigenvalue λ must lie in the interval λ := [µ p (A S ), ω p (A S )]. If this is the case, then the interval matrix A S -λI must be irregular, i.e., it contains a singular matrix. Moreover, the interval system

(A S -λI)x = 0, x ∞ = 1 ,
has a solution x, where x i = 0 for all i ∈ J. We decompose A S -λI according to J, and, without loss of generality, we may assume that J = {n -|J| + 1, . . . , n}, then

A S -λI = B S -λI C C T
D S -λI .

The interval system becomes

Cy = 0, (D S -λI)y = 0, y ∞ = 1, (7)
where we considered x = (0 T , y T ) T . This is a very useful necessary condition. If [START_REF] Chablat | An interval analysis based study for the design and the comparison of 3-dof parallel kinematic machines[END_REF] has no solution, then we cannot improve the current inner approximation. We can also prune the whole branch with J as a root; that is, we will inspect no index sets J ′ ⊆ J. The strength of this condition follows from the fact that the system ( 7) is overconstrained, it has more equations than variables. Therefore, with high probability, that it has no solution, even for larger J.

Let us make two comments about the interval system [START_REF] Chablat | An interval analysis based study for the design and the comparison of 3-dof parallel kinematic machines[END_REF]. First, this system has a lot of dependencies. They are caused from the multiple occurrences of λ, and by the symmetry of D S . If no solver for interval systems that can handle dependencies is available, then we can solve [START_REF] Chablat | An interval analysis based study for the design and the comparison of 3-dof parallel kinematic machines[END_REF] as an ordinary interval system, "forgetting" the dependencies. The necessary condition will be weaker, but still valid. This is what we did in our implementation.

The second comment addresses the expression y ∞ = 1. We have chosen the maximum norm to pertain linearity of the interval system. The expression could be rewritten as -1 ≤ y ≤ 1 (for checking solvability of [START_REF] Chablat | An interval analysis based study for the design and the comparison of 3-dof parallel kinematic machines[END_REF] we can use either normalization y ∞ = 1 or y ∞ ≤ 1). Another possibility is to write

-1 ≤ y ≤ 1, y i = 1 for some i ∈ {1, . . . , |J|}.

This indicates that we can split the problem into solving |J| interval systems

Cy = 0, (D S -λI)y = 0, -1 ≤ y ≤ 1, y i = 1 ,
where i runs, sequentially, through all the values {1, . . . , |J|}; cf. the ILS method proposed in [START_REF] Hladík | An algorithm for the real interval eigenvalue problem[END_REF]. The advantage of this approach is that the overconstrained interval systems have (one) more equation than the original overconstrained system, and hence the resulting necessary condition could be stronger. Our numerical results discussed in Section 5 concern this variant. As a solver for interval systems we utilize the convex approximation approach by Beaumont [START_REF] Beaumont | Solving interval linear systems with linear programming techniques[END_REF]; it is sufficiently fast and produces narrow enough approximations of the solution set.

How to conclude for exact bounds?

Let us summarize properties of the submatrix vertex enumeration method. On the one hand the worst case complexity of the algorithm is rather prohibitive, O(3 n ), but on the other, we obtain better inner approximations, and sometimes we get exact bounds of the eigenvalue sets. Theorem 1 and the discussion in the previous section allow us to recognize exact bounds. For any i ∈ {2, . . . , n}, we have that if λ i (A S ) < λ i-1 (A S ), then µ i (A S ) = λ i (A S ); a similar inequality holds for the lower bound. This is a rather theoretical recipe because we may not know a priori whether the assumption is satisfied. However, we can propose a sufficient condition: If ω i (A S ) < ω i-1 (A S ), then the assumption is obviously true, and we conclude µ i (A S ) = λ i (A S ); otherwise we cannot conclude.

This sufficient condition is another reason why we need a sharp outer approximation. The sharper it is, the more times we are able to conclude that the exact bound is achieved.

Exploiting the condition we can also decrease running time of submatrix vertex enumeration. We call Algorithm 3 only for p ∈ {1, . . . , n} such that p = 1 or ω p (A S ) < ω p-1 (A S ). The resulting inner approximation may be a bit less tight, but the number of exact boundary points of Λ(A S ) that we can identify remains the same.

Notice that there is enough open space for developing better conditions. For instance, we do not know whether µ i (A S ) < µ i-1 (A S ) (computed by submatrix vertex enumeration) can serve also as a sufficient condition for the purpose of determining exact bounds.

Numerical experiments

In this section we present some examples and numerical results illustrating properties of the proposed algorithms. The experiments we performed on a PC Intel(R) Core 2, CPU 3 GHz, 2 GB RAM, and the source code was written in C++. We use GLPK v.4.23 [START_REF] Makhorin | GLPK -GNU Linear Programming Kit[END_REF] for solving linear programs, CLAPACK v.3.1.1 for its linear algebraic routines, and PROFIL/BIAS v.2.0.4 [START_REF] Knüppel | PROFIL/BIAS -a C++ class library[END_REF] for interval arithmetic and basic operations. Notice, however, that routines of GLPK and CLAPACK [START_REF]CLAPACK -Linear Algebra PACKage written for C[END_REF] do not produce verified solutions; for real-life problems this may not be acceptable.

Example 1. Consider the following symmetric interval matrix

A S =   1 2 [1, 5] 2 1 1 [1, 5] 1 1   S .
Local improvement (Algorithm 1) yields an inner approximation The same result is obtained by the vertex enumeration (Algorithm 2). Therefore, µ 1 (A S ) = λ 1 (A S ) and µ 3 (A S ) = λ 3 (A S ). An outer approximation that is

RR n°7544

needed by the submatrix vertex enumeration (Algorithm 3) is computed using the methods of Hladík et al. [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF][START_REF] Hladík | A filtering method for the interval eigenvalue problem[END_REF]. It is Since the outer approximation intervals do not overlap, we can conclude that this approximation is exact, that is, λ i (A S ) = µ ′ i (A S ), i = 1, 2, 3. This example shows two important aspects of the interval eigenvalue problem. First, it demonstrates that the vertex enumeration does not produce exact bounds in general. Second, the symmetric eigenvalue set can be a proper subset of the unsymmetric one, i.e., Λ(A S ) Λ(A). This could be easily seen in the matrix  

1 2 1 2 1 1 5 1 1   .
It has three real eigenvalues 4.6458, -0.6458 and -1.0000, but the second one does not belong to Λ(A S ). Indeed, using the method by Hladík et al. [START_REF] Hladík | An algorithm for the real interval eigenvalue problem[END_REF] we obtain Example 2. Consider the example given by Qiu et al. [START_REF] Qiu | Bounds of eigenvalues for structures with an interval description of uncertain-but-non-random parameters[END_REF] (see also [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF][START_REF] Yuan | An evolution strategy method for computing eigenvalue bounds of interval matrices[END_REF]): The vertex enumeration (Algorithm 2) produces the same result. Hence we can state that µ 1 (A S ) and µ 4 (A S ) are optimal.

A S =     [
To call the last method, submatrix vertex enumeration (Algorithm 3) we need an outer approximation. We use the following by [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF]

RR n°7544

Hence, σ 1 (A) = 13.9371. As an outer approximation we use the following intervals, using [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF]. We cannot conclude that σ 3 (A) = µ 3 (A) = 0.1296, because ω 3 (M ) has a nonempty intersection with the fourth largest eigenvalue set, which is equal to zero. Also the other singular value sets remain uncertain, but within the computed inner and outer approximation. Notice that µ ′ 1 (M ) < µ 1 (M ), whence µ ′ 1 (M ) < λ 1 (M ) = σ 1 (A) disproving the Hertz's Theorem 1 from [START_REF] Hertz | Interval analysis: Eigenvalue bounds of interval matrices[END_REF] that the lower and upper limits of λ 1 (M ) and λ n (M ) are computable by the vertex enumeration method. It is true only for λ 1 (M ) and λ n (M ).

Example 4. In this example we present some randomly generated examples of large dimensions. The entries of the midpoint matrix, A c , are taken randomly in [-20, 20] using the uniform distribution. The entries of the radius matrix A ∆ are taken randomly, using the uniform distribution in [0, R], where R is a positive real number. We applied our algorithm on the interval matrix M := A T A, because it has a convenient distribution of eigenvalue set-some are overlapping and some are not. Sharpness of results is measured using the quantity

1 - e T µ ∆ (M S ) e T ω ∆ (M S )
,

where e = (1, . . . , 1) T . This quantity lies always within the interval [0, 1]. The closer to zero it is, the tighter the approximation. In addition, if it is zero, then we achieved exact bounds. The initial outer approximation, ω i (M S ), where 1 ≤ i ≤ n, was computed using the method due of Hladík et al. [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF], and filtered by the method proposed by Hladík et al. in [START_REF] Hladík | A filtering method for the interval eigenvalue problem[END_REF]. Finally, it was refined according to the comment in Section 4.3.2. For the submatrix vertex enumeration algorithm we implemented the branch & bound improvement, which is described in Section 4.3.1 and 4.3.2.

The results are displayed in Table 1.

Example 5. In this example we present some numerical results on approximating singular value sets as introduced in Example 3. The input consists of an interval (rectangular) matrix A ⊆ R m×n which is selected randomly as in the previous example. We proposed a new solution theorem for the symmetric interval eigenvalue problem, which describes some of the boundary points of the eigenvalue set. Unfortunately the complete characterisation is still a challenging open problem.

We developed an inner approximation algorithm (submatrix vertex enumeration), which in the case where the eigenvalue sets are disjoint, and the intermediate gaps are wide enough, output exact results. To our knowledge, even under this assumption, this is the first algorithm that can guarantee exact bounds.

Based on our numerical experiments suggest that the local search algorithm is superior to the submatrix vertex enumeration algorithm when the input matrices are not of very small dimension.

4 : 5 : 7 :

 457 decompose A S = B S C C T D S according to J; for all z ∈ {±1} |J| , z 1 = 1, do 6: D := D c + diag(z) D ∆ diag(z); for i = 1, . . . , |J| do 8: λ := λ i (D); 9: y := v i (D); 10: if λ > µ p (A S ) and λ ≤ ω p (A S ) and 0 ∈ Cy then 11: if p = 1 or λ < ω p-1 (A S ) then 12: µ p (A S ) := λ; 13: else 14: find C ∈ C such that Cy = 0; 15:

µ 1 (

 1 A S ) = [3.7321, 6.7843], µ 2 (A S ) = [0.0888, 0.3230], µ 3 (A S ) = [-4.1072, -1.0000].

ω 1 (

 1 A S ) = [3.5230, 6.7843], ω 2 (A S ) = [0.0000, 1.0519], ω 3 (A S ) = [-4.1214, -0.2019]. Now, the submatrix vertex enumeration algorithm yields the inner approximation µ ′ 1 (A S ) = [3.7321, 6.7843], µ ′ 2 (A S ) = [0.0000, 0.3230], µ ′ 3 (A S ) = [-4.1072, -1.0000].

Λ

  (A) = [3.7321, 6.7843] ∪ [-0.6458, 0.3230] ∪ [-4.1072, -1.0000].

.

  The local improvement (Algorithm 1) yields an inner approximation µ 1 (A S ) = [12560.8377, 12720.2273], µ 2 (A S ) = [7002.2828, 7126.8283], µ 3 (A S ) = [3337.0785, 3443.3127], µ 4 (A S ) = [842.9251, 967.1082].

ω 1 (

 1 A S ) = [12560.6296, 12720.2273], ω 2 (A S ) = [6990.7616, 7138.1800], ω 3 (A S ) = [3320.2863, 3459.4322], ω 4 (A S ) = [837.0637, 973.1993].

ω 1 (

 1 M ) = [4.3308, 14.0115], ω 2 (M ) = [1.9305, 11.6111], ω 3 (M ) = [0.0000, 5.1000]. Running the submatrix vertex enumeration, we get the inner approximation µ ′ 1 (M ) = [4.5548, 13.9371], µ ′ 2 (M ) = [2.2140, 11.5077], µ ′ 3 (M ) = [0.1296, 2.9517].

Table 2

 2 presents our experiments. The time in the table corresponds to the computation of the approximation of only the q largest eigenvalue sets of the Jordan-Wielandt matrix.

	n	R	Algorithm 1	Algorithm 2	Algorithm 3
			sharpness	time sharpness	time sharpness	time
	5 0.001	0.05817 0.00 s	0.05041	0.00 s	0.00000	0.04 s
	5 0.01	0.07020 0.00 s	0.05163	0.00 s	0.00000	0.03 s
	5 0.1	0.26273 0.00 s	0.23389	0.00 s	0.17332	0.04 s
	5 1	0.25112 0.00 s	0.23644	0.00 s	0.20884	0.01 s
	10 0.001	0.08077 0.00 s	0.07412	0.09 s	0.00000	1.15 s
	10 0.01	0.13011 0.01 s	0.11982	0.08 s	0.04269	1.29 s
	10 0.1	0.27378 0.01 s	0.25213	0.09 s	0.12756	3.17 s
	10 1	0.56360 0.01 s	0.52330	0.09 s	0.52256	2.58 s
	15 0.001	0.07991 0.02 s	0.07557	7.3 s	0.00000	16.47 s
	15 0.01	0.21317 0.02 s	0.19625	6.5 s	0.11341	2 m 29 s
	15 0.1	0.36410 0.02 s	0.34898	7.0 s	0.34869	4 m 58 s
	15 1	0.76036 0.02 s	0.73182	7.2 s	0.73182	7.5 s
	20 0.001	0.09399 0.06 s	0.09080	7 m 21 s	0.00000	13 m 46 s
	20 0.01	0.24293 0.06 s	0.22976	7 m 6 s	0.12574 1 h 14 m 55 s
	20 0.1	0.24293 0.06 s	0.22976	7 m 14 s	0.12574 1 h 15 m 41 s
	20 1	0.82044 0.06 s	0.79967	7 m 33 s	0.79967	7 m 39 s
	25 0.001	0.14173 0.13 s	0.13397 6 h 53 m 0 s	0.02871 9 h 32 m 54 s

Table 1 :

 1 Eigenvalues of random interval symmetric matricesA T A of dimension n × n.

	m	n	R	Algorithm 1	Algorithm 2	Algorithm 3
				sharpness	time sharpness	time sharpness	time
	5	5 0.01	0.08945 0.00 s	0.07716	0.10 s	0.00000	0.53 s
	5	5 0.1	0.09876 0.01 s	0.09270	0.08 s	0.00000	0.73 s
	5	5 1	0.43560 0.01 s	0.31419	0.10 s	0.26795	4.34 s
	5 10 0.01	0.11320 0.02 s	0.10337	5.79 s	0.00000	7.91 s
	5 10 0.1	0.13032 0.02 s	0.12321	5.98 s	0.00000	8.40 s
	5 10 1	0.35359 0.02 s	0.33176	5.52 s	0.22848	21.53 s
	5 15 0.01	0.10603 0.05 s	0.09424	5 m 31 s	0.00000	5 m 36 s
	5 15 0.1	0.17303 0.04 s	0.16758	5 m 33 s	0.00000	7 m 58 s
	5 15 1	0.46064 0.05 s	0.39708	5 m 32 s	0.31847	15 m 47 s
	10 10 0.01	0.10211 0.06 s	0.09652	8 m 3 s	0.00000	8 m 19 s
	10 10 0.1	0.13712 0.07 s	0.13387	8 m 10 s	0.00000	14 m 12 s
	10 10 1	0.39807 0.07 s	0.35580	7 m 52 s	0.30279 26 h 48 m 38 s
	10 15 0.01	0.09561 0.12 s	0.09116 5 h 51 m 53 s	0.00000	5 h 54 m 56 s

Table 2 :

 2 Singular values of random interval matrices of dimension m × n.

	RR n°7544

RR n°7544

Acknowledgment. ET is partially supported by an individual postdoctoral grant from the Danish Agency for Science, Technology and Innovation.

Now, submatrix vertex enumeration yields the same inner approximation as the previous methods. However, now we have more information. Since the outer approximation interval are mutually disjoint, the obtained results are the best possible. Therefore, µ i (A S ) = λ i (A S ), where i = 1, . . . , 4.

Example 3. Herein, we present two examples for approximating the singular values of an interval matrix. Let A ∈ R m×n and q := min{m, n}. By the Jordan-Wielandt theorem [START_REF] Golub | Matrix computations. 3rd ed[END_REF][START_REF] Horn | Matrix analysis[END_REF][START_REF] Meyer | Matrix analysis and applied linear algebra[END_REF] the singular values, σ 1 (A) ≥ • • • ≥ σ q (A), of A are identical with the q largest eigenvalues of the symmetric matrix 0 A T A 0 .

Thus, if we consider the singular value sets σ 1 (A), . . . , σ q (A) of some interval matrix A ∈ R m×n , we can identify them as the q largest eigenvalue sets of the symmetric interval matrix

(1) Consider the following interval matrix from [START_REF] Deif | Singular values of an interval matrix[END_REF].

Both the local improvement and the vertex enumeration result the same inner approximation, i.e. Thus, σ 1 (A) = 4.5431. Additionally, consider the following outer approximation from [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF].


Nicolas Crouseilles
email: crouseil@math.u-strasbg.fr

Erwan Faou
email: erwan.faou@inria.fr

Approximate travelling wave solutions to the 2D Euler equation on the torus

We consider the two-dimensional Euler equation with periodic boundary conditions. We construct approximate solutions of this equation made of localized travelling profiles with compact support propagating over a stationary state depending on only one variable. The direction or propagation is orthogonal to this variable, and the support is concentrated around flat points of the stationary state. Under regularity assumptions, we prove that the approximation error can be made exponentially small with respect to the width of the support of the travelling wave. We illustrate this result by numerical simulations.

Introduction

We consider the two-dimensional Euler equation written in terms of vorticity

∂ t ω + u • ∇ω = 0,
where ω(t, x, y) ∈ R, ∇ = (∂ x , ∂ y ) T with (x, y) ∈ T 2 the two-dimensional torus (R/2πZ) 2 . The divergence free velocity field u is given by the formula u = J∇ψ with ψ = (-∆) -1 ω, where J = 0 -1 1 0

is the canonical symplectic matrix. Here (-∆) -1 is the inverse of the Laplace operator on functions with average 0 on T 2 . We can rewrite this equation as

   ∂ t ω + {ψ, ω} = 0, -∆ψ = ω, (1.1)
with the 2D Poisson bracket for functions on T 2 :

{f, g} = (∂ x f )(∂ y g) -(∂ y f )(∂ x g).
For two functionals H(ω) and G(ω), we set

{H, G} ω = T 2
δH δω δG δω , ω = -{G, H} ω .

The Euler equation (1.1) is a Hamiltonian PDE associated with this non canonical Poisson structure, and with Hamiltonian

E(ω) = 1 (2π) 2 T 2 1 2 u 2 = 1 2(2π) 2 T 2 ω(-∆) -1 ω = ω 2 H -1 ,
which is quadratic in ω. In other words, we can write (1.1) as

∂ t ω + δE δω , ω = 0,
and from the definition of the Poisson structure, we observe that E(ω(t)) = E(ω(0)) for all time (preservation of the energy). Moreover, the flow is volume preserving in the sense that for all smooth functions h : R → R, we have

∀ t ≥ 0 T 2
h(ω(t, x, y))dxdy = T 2 h(ω(0, x, y))dxdy,

which expresses the preservation of the Casimirs of the Poisson structure.

The equation (1.1) possesses many stationary states. For all functions F : R → R and ψ 0 : T 2 → R satisfying ∆ψ 0 = F (ψ 0 ), then the couple of functions ω(t, x, y) = F (ψ 0 (x, y)) and ψ(t, x, y) = ψ 0 (x, y) solve (1.1). Another class of stationary states are given by functions depending only on one variable (shear flows): for any smooth V (y) periodic in y, the couple ω(t, x, y) = V ′′ (y) and ψ(t, x, y) = -V (y) is solution of the 2D Euler equation.

The goal of this paper is to construct approximate travelling solutions of (1.1) based on such stationary states. More precisely, we will construct families of functions of the form

ω ε (t, x, y) = V ′′ (y) + Ω ε (x -x 0 -ct, y -y 0 ) (1.3)
for ε sufficiently small, where the functions Ω ε (x, y) are profiles exponentially decaying with respect to (|x| + |y|)/ε, and with compact support. Then, under the assumption that V is smooth and that y 0 is such that V is locally linear around y 0 -so that V ′′ is locally zero -we can prove that (1.3) is solution of (1.1) for all time up to an error of order ε N for all N . If moreover V has a Gevrey regularity, we can optimize the truncation error and obtain an exponentially small error with respect to ε. Strikingly, this construction holds when the velocity c is given by c = V ′ (y 0 ). In other words, the speed of the profile depends on the local shape of the surface defined by the stationary state V (y). Moreover, we can take Ω ε L ∞ ≃ ε -α where α is any real number.

Note that as ω ε (t, x, y) is a travelling wave with constant velocity, it automatically satisfies the preservation law (1.2), and we can easily prove that the energy is preserved up to exponentially small terms for all times.

The method of proof is based of an asymptotic matching between the profiles and the shear flow V (y) as in [START_REF] Vishik | Regular degeneration and boundary layers for linear differential equations with small parameter[END_REF]. Such technic has already been used in the context of Euler equations, see for instance [START_REF] Balmforth | Dynamics of vorticity defects in shear[END_REF][START_REF] Balmforth | Disturbing vortices[END_REF] and the references therein.

We conclude this introduction by remarking that the construction can be easily extended to a finite number of travelling profiles if V ′′ (y) possesses several flat points, by just adding exponentially decreasing profile with non interacting supports:

ω ε (t, x, y) = V ′′ (y) + K k=0 Ω ε k (x -x k -c k t, y -y k ) (1.4)
where the points y k are flat points of V ′′ (y). Note that this can be done at the same level y 1 = y 0 provided x 1 = x 0 and ε small enough to ensure the non interaction of the supports of the profiles. Therefore, the function (1.4) is a quasi-periodic function satisfying (1.1) up to exponentially small terms. The question of the existence of quasi-periodic exact solutions for the 2D Euler equation, possibly close to the functions constructed above, remains an open problem.

We conclude this paper by a numerical illustration of the previous results.

These functions satisfy

   ∂ t ξ + V ′ ∂ x ξ + V ′′′ ∂ x η + {η, ξ} = 0, -∆η = ξ.
(2.1)

Let ε > 0 and (x 0 , y 0 ) ∈ T 2 . We search a formal solution of the previous equation under the form

ξ ε (t, x, y) = ε -α Ω x -x 0 -ct ε , y -y 0 ε (2.2)
and

η ε (t, x, y) = ε 2-α Ψ x -x 0 -ct ε , y -y 0 ε , (2.3)
where Ω and Ψ are profiles decreasing away from (0, 0). Note that α is here arbitrary and can be positive or negative. We assume that y 0 is such that

V ′′ (y 0 ) = • • • = V (n) (y 0 ) = 0, ∀ n ≥ 2. (2.4)
It means that V ′′ is flat in the variable y in the vicinity of y 0 . We perform the scaling

X = x -x 0 ε , Y = y -y 0 ε , and
T = t ε , (2.5)
and plug the expressions (2.2) and ( 2.3) into (2.1). This yields

   -c∂ X Ω + V ′ (y 0 + εY )∂ X Ω + ε 2 V ′′′ (y 0 + εY )∂ X Ψ + ε 1-α {Ψ, Ω} = 0, -∆ X,Y Ψ = Ω, (2.6
) where the Poisson bracket and the Laplace operator express in terms of X and Y . Note that here we consider (X, Y ) ∈ R 2 . This is a profile equation as for boundary layers in singular perturbation theory, see for instance [START_REF] Vishik | Regular degeneration and boundary layers for linear differential equations with small parameter[END_REF]. Now under the assumption (2.4), we have that for all N , V ′ (y

0 + εY ) = V ′ (y 0 ) + O(ε N Y N ) and similarly V ′′′ (y 0 + εY ) = O(ε N Y N ).
Hence at least from the formal point of view, we can solve (2.6) up to high powers of ε if we take c = V ′ (y 0 ), and if Ω and Ψ are solutions of the equation

-∆ X,Y Ψ = Ω, and {Ψ, Ω} = 0 in R 2 , (2.7) where ∆ X,Y = ∂ 2 X + ∂ 2 Y is the Laplace operator in coordinates (X, Y ) ∈ R 2 .
This equation means that (Ψ, Ω) is a stationary state of the Euler equation on R 2 . To match the asymptotic profile with the stationary state V (y), we naturally seek for exponentially decreasing solutions.

We are lead to make the following assumption:

Hypothesis 2.1 The functions Ω(X, Y ) and Ψ(X, Y ) satisfy (2.7) and are exponentially decreasing in the sense that there exists constants µ and β such that

∀ (X, Y ) ∈ R 2 , ∀ m = 0, 1, |∇ m Ω(X, Y )| + |∇ m Ψ(X, Y )| ≤ µe -β(|Y |+|X|) . (2.8) Example 2.2 Let g be a smooth function from R to itself. If (Ψ, Ω) are solutions of the problem -∆ X,Y Ψ = g(Ψ) =: Ω, (2.9)
then it is automatically a solution of (2.7). For example we can take the soliton equation

∆Ψ + Ψ 3 -Ψ in R 2 ,
and the associated ground state with radial symmetry, which yields exponentially decaying solutions in the previous sense, see [START_REF] Strauss | Existence of solitary waves in higher dimensions[END_REF][START_REF] Weinstein | Modulational stability of ground states of nonlinear Schrödinger equations[END_REF]. We also refer to [START_REF] Ambrosetti | Existence of Steady Vortex Rings in an Ideal Fluid[END_REF][START_REF] Hill | On a spherical vortex[END_REF][START_REF] Caglioti | A Special Class of Stationary Flows for Two-Dimensional Euler Equations: A Statistical Mechanics Description[END_REF][START_REF] Caglioti | On a constrained 2-D Navier-Stokes equation[END_REF] and the references therein for other examples of stationary states of the twodimensional Euler equation on R 2 . Theorem 3.1 Assume that V satisfies (2.4) for some y 0 ∈ T 2 , and let (Ψ, Ω) a couple of functions satisfying Hypothesis 2.1. For x 0 ∈ T 2 , α ∈ R, and ε > 0, we define

Approximate solution

ω ε (t, x, y) = V ′′ (y) + ε -α Ω x -x 0 -ct ε , y -y 0 ε χ(x -x 0 -ct, y -y 0 ) (3.2)
and

ψ ε (t, x, y) = -V (y) + ε 2-α Ψ x -x 0 -ct ε , y -y 0 ε χ(x -x 0 -ct, y -y 0 ), (3.3)
where c = V ′ (y 0 ). Then for all N , there exists constants ε 0 and C N such that for all ε < ε 0 , the couple (ω ε , ψ ε ) satisfies

∀ t ∈ R, ∂ t ω ε + {ψ ε , ω ε } L ∞ + ∆ψ ε + ω ε L ∞ ≤ C N ε N . (3.4)
Proof. First, we note that as b < π/2, the functions ω ε and ψ ε define smooth periodic functions in (x, y) ∈ T 2 . We calculate, omitting the argument (x -x 0ct, y -y 0 )/ε, that

∆ x,y ψ ε = -V ′′ (y) + ε -α+2 (∆ x,y χ)Ψ + χ∆ x,y Ψ + 2∇ x,y χ • ∇ x,y Ψ) ,
where here ∆

x,y = ∂ 2 x + ∂ 2 y . Hence we get ∆ x,y ψ ε + ω ε = ε -α χ(ε 2 ∆ x,y Ψ + Ω) + R(t, x, y, ε), where R(t, x, y, ε) = ε -α+2 (∆ x,y χ)Ψ + 2∇ x,y χ • ∇ x,y Ψ) .
By construction and with the notation (2.5), we have

(ε 2 ∆ x,y Ψ + Ω) x -x 0 -ct ε , y -y 0 ε χ(x -x 0 -ct, y -y 0 ) = (∆ X,Y Ψ + Ω)(X -cT, Y )χ(ε(X -cT ), εY ) = 0, using (2.9)
, and where this expression is well defined as χ is with compact support. Now let us examine the terms in R(t, x, y, ε). We consider for example the term

ε -α+2 ∂ x χ(x -x 0 -ct, y -y 0 )∂ x Ω x -x 0 -ct ε , y -y 0 ε (3.5)
This expression vanishes unless (t, x, y) satisfies

a < |x -x 0 -ct| + |y -y 0 | < b,
which corresponds to the interval where the gradient of χ is non zero (see (3.1)).

For such points, we have

∂ x Ω x -x 0 -ct ε , y -y 0 ε = 1 ε ∂ X Ω x -x 0 -ct ε , y -y 0 ε ≤ ε -1 µe -βa/ε , (3.6
) owing to (2.8). As χ is smooth with bounded gradient, this shows that the term (3.5) is smaller than c N ε N for a suitable constant N and a sufficiently small ε. The other are treated similarly, and we finally get

R(x, y, t) L ∞ ≤ C N ε N . (3.7)
This shows that for all time t, we have

∆ψ ε + ω ε L ∞ ≤ C N ε N . Similarly, we can write ∂ t ω ε + {ψ ε , ω ε } = ∂ t ω ε + (∂ x ψ ε )(∂ y ω ε ) -(∂ y ψ ε )(∂ x ω ε ) = ∂ t ξ ε + V ′ ∂ x ξ ε + V ′′′ ∂ x η ε + {η ε , ξ ε }
where we have set ξ ε = ω ε -V ′′ (y) and η ε = ψ ε + V (y). In this expression, by similar arguments using the exponential decay of Ω and Ψ and the fact that χ is constant near (0, 0), we have

{η ε , ξ ε } = ε -2α χ(∂ X Ψ∂ Y Ω -∂ X Ω∂ Y Ψ) + O(ε N ) = O(ε N ),
as the couple (Ψ, Ω) satisfies (2.7). Hence it remains to consider

∂ t ξ ε + V ′ ∂ x ξ ε + V ′′′ ∂ x η ε = ε -α (∂ x χ)(-cΩ + V ′ Ω + ε 2 V ′′′ Ψ) + χε -α-1 (-c∂ X Ω + V ′ ∂ X Ω + ε 2 V ′′′ ∂ X Ψ).
Using again the exponential decay of Ω and Ψ, the term in factor of ∂ x χ is O(ε N ). Considering the second term in the right-hand side of the previous equation, we have

ε -α-1 χ(x -x 0 -ct, y -y 0 )V ′′′ (y)∂ X Ψ x -x 0 -ct ε , y -y 0 ε = ε -α-1 χ(ε(X -cT ), εY )V ′′′ (y 0 + εY )∂ X Ψ(X -cT, Y ),
using the notation (2.5). For |εY | > b, this expression vanishes as χ is identically equal to zero. Let us consider now the case |εY | < a. As V is smooth and satisfies (2.4), then for all m there exists a constant C m such that for all z such that |z| < a, we have using a Taylor expansion, that

|V ′′′ (y 0 + z)| ≤ C m |z| m . (3.8)
Hence for Y such that |εY | ≤ a and all X, we have with (2.8)

|V ′′′ (y 0 + εY )∂ X Ψ(X -cT, Y )| ≤ C m µε m |Y | m e -β|Y | ≤ Cm ε m (3.9)
for some constant Cm . Applying this formula with m = N + α + 1, we get

χε -α-1 V ′′′ ∂ X Ψ L ∞ ≤ C N ε N
for some constant C N and ε < ε 0 sufficiently small. Similarly, as -c + V ′ (y) = V ′ (y) -V ′ (y 0 ) satisfies an estimate similar to (3.8), we can prove that

χε -α-1 (-c + V ′ )∂ X Ω = O(ε N ).
Gathering together the previous inequalities yields the result.

Remark 3.2 By construction, the function ω ε is a travelling wave at constant velocity. Hence the preservation property (1.2) holds for all functions h. In particular all the L p norms of ω ε are preserved for all time. Similarly, using the estimate (3.4), the energy

E(t) = T 2 ω ε (t, x, y)(-∆) -1 ω ε (t, x, y)dxdy = T 2 ω ε (t, x, y)ψ ε (t, x, y)dxdy + O(ε N ) = E(0) + O(ε N )
is almost preserved for all times.

Remark 3.3 The same result holds true for the function (1.4), under the hypothesis that the supports of the functions Ω ε k do not interact. The proof is very similar to the previous one and left to the reader.

Exponential estimates

We now make the supplementary assumption that V has Gevrey regularity around y 0 : Hypothesis 4.1 The function V satisfies (2.4), and moreover, there exist positive constants M , R and δ ≥ 1, such that

∀ n ∈ N, ∀ y such that |y -y 0 | < 2a, |V (n) (y)| ≤ M R n n δn . (4.1)
A typical example of Gevrey function around y 0 is given by the function e -1/(y-y 0 ) 2 if y > y 0 and 0 if y ≤ y 0 . Theorem 4.2 Assume that V satisfies Hypothesis 4.1 for some y 0 ∈ T 2 and δ ≥ 1, and let (Ψ, Ω) a couple of functions satisfying Hypothesis 2.1. For x 0 ∈ T 2 , α ∈ R, and ε > 0, let ω ε (t, x, y) and ψ ε (t, x, y) the functions defined in (3.2) and (3.3). Then there exist constants ε 0 , γ and C such that for all ε < ε 0 , the couple

(ω ε , ψ ε ) satisfies ∀ t ∈ R, ∂ t ω ε + {ψ ε , ω ε } L ∞ + ∆ψ ε + ω ε L ∞ ≤ Ce -γε -σ , (4.2)
where σ = 1/(δ + 1).

Proof. The method of proof is the same as the proof of Theorem 3.1. First, we note that all the estimates involving derivatives of the cut-off functions are in fact exponentially decreasing with respect to ε, see (3.6), so that (3.7) can be easily refined to

R(t, x, y) L ∞ ≤ Ce -κ/ε
for some constants κ and C, and ε < ε 0 sufficiently small.

The second source in the error term comes from equation (3.8). Under the assumption (4.1), (3.8) becomes for all |z| < a,

|V ′′′ (y 0 + z)| = 1 m! |z| m sup |t|≤a |V (m+3) (y 0 + t)| ≤ M m! |z| m R m+3 (m + 3) δ(m+3) ,
and hence for m > m 0 sufficiently large, we get

∀ |z| < a, |V ′′′ (y 0 + z)| ≤ K|z| m m δm .
for some constant K independent on m. Hence the second estimate (3.9) yields now an error of the form

Km δm µε m |Y | m e -β|Y | ≤ Kµ m (δ+1) ε eβ m ,
for m > m 0 , owing to the estimate

∀ x > 0, x m e -βx ≤ m eβ m . Taking m = β ε 1 δ+1
for ε < ε 0 sufficiently small to ensure m > m 0 then yields an error of the form Ce -γε -σ with σ = 1/(δ + 1), C = Kµ and γ = β 1 δ+1 . The other error terms are similar.

Numerical illustration

In this last section, we would like to show the validity of the previous analysis by a numerical experiment. In the example below, we consider an initial value made of two localized Gaussians over a stationary state V containing large flat parts, and we show the evolution of localized packets at the expected speed c = V ′ (y 0 ). For practical reasons, the following numerical simulations below are made on the equation ∂ t ω -{ψ, ω} = 0, and -∆ψ = ω, which can be obtained from (1.1) by a change t → -t. Hence the localized profiles are expected to travel at the speed -V ′ (y 0 ) which we will numerically aproximate by ∂ y ψ(x, y 0 ).

We take the initial condition (x 0 = π/2, x 1 = 2π/3 and y 0 = π/4, y 1 = 7π/4)

ω(t = 0, x, y) = V ′′ (y) + 5 exp - (x -π/2) 2 + (y -π/4) 2 ε 2 - 5 exp - (x -2π/3) 2 + (y -7π/4) 2 ε 2 ,
where V ′′ (y) is the function

V ′′ (y) = exp -10(y -2π/3) 2 -exp -10(y -4π/3) 2 .
We choose ε = 0.1. Figure 1 shows the initial condition. To simulate the solution, we use a semi-Lagrangian scheme (we refer to [6, 7] for the details of the method). The numerical parameters are chosen as follows: we take N x = N y = 512 grid points in each direction and the time step is ∆t = 0.05.

As expected, the localized profiles start to move in the x-direction, (see Figures 4-5), and remain localized at least for a time t ≤ 20 ≃ O(ε -1 ). After this time, the structure is lost, which makes sense since the Gaussians are not stable states of the 2D Euler equation on R 2 .

We look at the velocity of the profile during this regime. It can be computed numerically, and compared to the value c = -V ′ (y 0 ) = ∂ y ψ(t = 0, x = 0, y 0 ). This last value is observed on the y-profile of ψ, which is linear in a vicinity of 1: Numerical values of the center of the profiles, the corresponding time, the displacement with respect to the previous time and the corresponding velocity. y 0 . Figure 2 confirms the linear behaviour around y 0 = π/4 (we superimpose a linear function of slope -0.19). This value of the velocity can be compared to the velocity of the localized profiles. On Figure 3, x-profiles of ω are plotted for y = π/4. We can observe the travel of the profile along the periodic x-direction. Each consecutive plot is plotted every t = 5 so that the velocity is estimated to -0.19, which is in very good agreement with the previous computed one. More details are given in Table 1. We can observe that the numerical diffusion is quite low since the maximum of the profiles decreases slowly as time advances.

  Let a, b two real numbers such that 0 < a < b < π/2, and let χ(x, y) be a smooth cut-off function satisfying χ(x, y) = 0 for |x| + |y| > b, and χ(x, y) = 1 for |x| + |y| < a. (3.1)

Figure 1 :

 1 Figure 1: Initial condition ω(t = 0, x, y).

Figure 2 : 11 Figure 4 :

 2114 Figure 2: y-profile of ψ at t = 0, and the linear function of slope -0.19.

Figure 3 :

 3 Figure 3: Time evolution of the profile: ω(t, x, y = π/4) as a function of x for different times: t = 0, t = 5, t = 10, t = 15, t = 20, t = 25.

AnsatzLet (ω, ψ) a solution of (1.1), and V (y) a smooth periodic function. Let us set ξ(t, x, y) = ω(t, x, y) -V ′′ (y), and η(t, x, y) = ψ(t, x, y) + V (y).

Acknowledgements: It is a great pleasure to thank Sergei Kuksin for many helpful discussions and encouragement during the preparation of this work, and Freddy Bouchet for useful comments.


Jozef Bobok
email: bobok@mat.fsv.cvut.cz

Serge Troubetzkoy
email: troubetz@iml.univ-mrs.fr

CODE & ORDER IN POLYGONAL BILLIARDS

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Consider a simply connected polygon P with k sides. Code each the billiard orbit by the sequence of sides it hits. We study the following question: can the arising sequence be realized as the coding of a billiard orbit in another polygon? Of course if the orbit is not dense in the boundary ∂P , then we can modify P preserving the orbit by adding sides on the untouched part of the boundary. In the case that the orbit is periodic we have even more, there is an open neighborhood of P in a co-dimension one submanifold of the set of all k-gons for which the periodic orbit persists [T]. It is therefore natural to study this question under the assumption that the orbit is dense in the boundary. More precisely, we say that two polygons P, Q are code equivalent if there are forward billiard orbits u, v whose projections to the boundaries ∂P , ∂Q are dense. We study this question under this assumption and under various regularity conditions on the orbit u.

We first assume a weak regularity condition, a direction θ is called non-exceptional if there is no generalized diagonal in this direction. All but countably many directions are non-exceptional. Under this assumption we show that an irrational polygon can not be code equivalent to a rational polygon (Theorem 5.3) and if two rational polygons are code equivalent then the angles at corresponding corners are equal (Theorem 7.1), for triangles this implies they must be similar (Corollary 7.2). Next we assume a stronger regularity condition on the angle, unique ergodicity of the billiard flow in the direction θ, which is verified for almost every direction in a rational polygon. Under this assumption we show that two rational polygons which are code equivalent must be affinely similar and if the greatest common denominator of the angles is at least 3 then they must be similar (Theorem 7.4,Corollary 7.5).

In [BT] we proved analogous results under the assumption that P, Q are order equivalent. Our investigation of code equivalence is motivated by Benoit Rittaud's review article on these results [Ri]. We compare our results with those of [BT]. We show that under the weak regularity condition order equivalence implies code equivalence (Theorem 8.2), while under the strong regularity condition they are equivalent (Theorem 8.3,Corollary 8.4). The proof of this equivalence uses Corollary 7.5. We do not know if under the weak regularity condition code equivalence implies order equivalence.

Polygonal Billiards

A polygonal billiard table is a polygon P . Our polygons are assumed to be planar, simply connected, not necesarily convex, and compact, with all angles non trivial, i.e. in (0, 2π)\{π}. The billiard flow {T t } t∈R in P is generated by the free motion of a point mass subject to elastic reflections in the boundary. This means that the point moves along a straight line in P with a constant speed until it hits the boundary. At a smooth boundary point the billiard ball reflects according to the well known law of geometrical optics: the angle of incidence equals the angle of reflection. If the billiard ball hits a corner, (a non-smooth boundary point), its further motion is not defined. Additionally to corners, the billiard trajectory is not defined for orbits tangent to a side.

By D we denote the group generated by the reflections in the lines through the origin, parallel to the sides of the polygon P . The group D is either

• finite, when all the angles of P are of the form πm i /n i with distinct co-prime integers m i , n i , in this case D = D N the dihedral group generated by the reflections in lines through the origin that meet at angles π/N, where N is the least common multiple of n i 's, or

• countably infinite, when at least one angle between sides of P is an irrational multiple of π. In the two cases we will refer to the polygon as rational, respectively irrational.

Consider the phase space P × S 1 of the billiard flow T t , and for θ ∈ S 1 , let R θ be its subset of points whose second coordinate belongs to the orbit of θ under D. Since a trajectory changes its direction by an element of D under each reflection, R θ is an invariant set of the billiard flow T t in P . The set P × θ will be called a floor of the phase space of the flow T t .

As usual, π 1 , resp. π 2 denotes the first natural projection (to the foot point), resp. the second natural projection (to the direction). A direction, resp. a point u from the phase space is exceptional if it is the direction of a generalized diagonal (a generalized diagonal is a billiard trajectory that goes from a corner to a corner), resp. π 2 (u) is such a direction. Obviously there are countably many generalized diagonals hence also exceptional directions. A direction, resp. a point u from the phase space, which is not exceptional will be called non-exceptional.

In a rational polygon a billiard trajectory may have only finitely many different directions. The set R θ has the structure of a surface. For non-exceptional θ's the faces of R θ can be glued according to the action of D N to obtain a flat surface depending only on the polygon P but not on the choice of θ -we will denote it R P .

Let us recall the construction of R P . Consider 2N disjoint parallel copies P 1 , . . . , P 2N of P in the plane. Orient the even ones clockwise and the odd ones counterclockwise. We will glue their sides together pairwise, according to the action of the group D N . Let 0 < θ = θ 1 < π/N be some angle, and let θ i be its i-th image under the action of D N . Consider P i and reflect the direction θ i in one of its sides. The reflected direction is θ j for some j. Glue the chosen side of P i to the identical side of P j . After these gluings are done for all the sides of all the polygons one obtains an oriented compact surface R P .

Let p i be the i-th vertex of P with the angle πm i /n i and denote by G i the subgroup of D N generated by the reflections in the sides of P , adjacent to p i . Then G i consists of 2n i elements. According to the construction of R P the number of copies of P that are glued together at p i equals to the cardinality of the orbit of the test angle θ under the group G i , that is, equals 2n i .

The billiard map T :

V P = ∪e × Θ ⊂ δP × (-π 2 , π
2 ) → V P associated with the flow T t is the first return map to the boundary δP of P . Here the union ∪e × Θ is taken over all sides of P and for each side e over the inner pointing directions θ ∈ Θ = (-π 2 , π 2 ) measure with respect to the inner pointing normal. We will denote points of V P by u = (x, θ).

We sometimes use the map ̺ 1 , ̺ 2 and ̺ mapping (e × (-

π 2 , π 2 )) 2 into R + defined as ̺ 1 (u, ũ) = |π 1 (u) -π 1 (ũ)|, ̺ 2 (u, ũ) = |π 2 (u) -π 2 (ũ)| and ̺ = max{̺ 1 , ̺ 2 }. Clearly the map ̺ is a metric.
The bi-infinite (forward, backward) trajectory (with respect to T ) is not defined for all points from V P . The set of points from V P for which the bi-infinite, forward and backward trajectory exists is denoted by BIV P , F V P and BV P respectively.

For a simply connected polygon we always consider counterclockwise orientation of its boundary δP . We denote [x, x ′ ] ((x, x ′ )) a closed (open) arc with outgoing endpoint x and incoming endpoint x ′ .

If P, Q are simply connected polygons, two sequences {x n } n≥0 ⊂ ∂P and {y n } n≥0 ⊂ ∂Q have the same combinatorial order if for each nonnegative integers k, l, m

(1)

x k ∈ [x l , x m ] ⇐⇒ y k ∈ [y l , y m ].
We proceed by recalling several well known and useful (for our purpose) results about polygonal billiards (see for example [MT]). Recall that a flat strip T is an invariant subset of the phase space of the billiard flow/map such that 1) T is contained in a finite number of floors, 2) the billiard flow/map dynamics on T is minimal in the sense that any orbit which does not hit a corner is dense in T , 3) the boundary of T is non-empty and consists of a finite union of generalized diagonals. The set of the corners of P is denoted by C P . As usual, an ω-limit set of a point u is denoted by ω(u).

Proposition 2.1. [MT] Let P be rational and u ∈ F V P . Then exactly one of the following three possibilities has to be satisfied.

(i) u is periodic.

(ii) orb(u) is a flat strip; the billiard flow/map is minimal on orb(u).

(iii) For the flow T t , ω(u) = R π 2 (u) . The billiard flow/map is minimal on R π 2 (u) . We have

#({π 2 (T n (u)) : n ≥ 0}) = 2N,
and for every x ∈ ∂P \ C P ,

#{u 0 ∈ ω(u) : π 1 (u 0 ) = x} = N,
where N = N P is the least common multiple of the denominators of angles of P . Moreover, in this case

π 2 ({u 0 ∈ ω(u) : π 1 (u 0 ) = x}) = π 2 ({u 0 ∈ ω(u) : π 1 (u 0 ) = x ′ })
whenever x ′ / ∈ C P belongs to the same side as x. Case (iii) holds whenever u ∈ F V P is non-exceptional.

Corollary 2.2. Let P be rational and u ∈ F V P , then u is recurrent and the ω-limit set ω(u) coincides with the forward orbit closure orb(u).

Theorem 2.3. [START_REF] Bobok | Does a billiard orbit determine its (polygonal) table? to appear[END_REF]Theorem 4.1] Let P be irrational and u ∈ F V P .

(i) If π 2 (u) is non-exceptional then {π 2 (T n u) : n ≥ 0} is infinite.

(ii) If u is not periodic, but visits only a finite number of floors then (u is uniformly recurrent and) orb(u) is a flat strip.

Combining Proposition 2.1 and Theorem 2.3(ii) yields

Corollary 2.4. Let P be a polygon and u ∈ V P visits a finite number of floors. Then u is uniformly recurrent.

Let G be a function defined on a neighborhood of y. The derived numbers D + G(y), D + G(y) of G at y are given by

D + G(y) = lim sup h→0 + G(y + h) -G(y) h , D + G(y) = lim inf h→0 + G(y + h) -G(y) h
and the analogous limits from the left are denoted by D -G(y), D -G(y).

Let (z, y) be the coordinates of R 2 and let p a,b ⊂ R 2 be the line with equation y = a + z tan b. For short we denote p y 0 ,G(y 0 ) by p G(y 0 ) . The following useful lemma was proven in [BT].

Lemma 2.5. Let G : (c, d) → (-π 2 , π 2 ) be a continuous function. Fix C ⊂ (c, d) countable.
Assume that for some y 0 one of the four possibilities

D + G(y 0 ) > 0, D + G(y 0 ) < 0, D -G(y 0 ) > 0, D -G(y 0 ) < 0 is fulfilled. Then there exists a sequence {y n } n≥1 ⊂ (c, d) \ C such that lim n y n = y 0 and the set of crossing points {p G(y 0 ) ∩ p G(yn) : n ≥ 1} is bounded in the R 2 .

Coding by sides

For a simply connected k-gon P we always consider counterclockwise numbering of sides e

1 = [p 1 , p 2 ], . . . , e k = [p k , p 1 ]; we denote e • i = (p i , p i+1 ).
The symbolic bi-infinite (forward, backward) itinerary of a point u = (x, θ) ∈ BIV P (u ∈ F V P , u ∈ BV P ) with respect to the sides of

P is a sequence σ(u) = {σ i (u)} ∞ i=-∞ , (σ + (u) = {σ i (u)} i≥0 , σ -(u) = {σ i (u)} i≤0 ) of numbers from {1, . . . , k} defined by π 1 (T i u) ∈ e • σ i . Let Σ P := {σ + (u) : u ∈ F V P }. For a sequence σ = {σ i } i≥0 ∈ Σ P
we denote by X(σ) the set of points from V P whose symbolic forward itinerary equals to σ.

Theorem 3.1. [GKT] Let P be a polygons and σ ∈ Σ P be periodic. Then each point from X(σ) has a periodic trajectory.

We will repeatedly use the following result.

Theorem 3.2. [GKT] Let P be a polygon and σ ∈ Σ P be non-periodic, then the set X(σ) consists of one point.

For u ∈ F V P and m ≥ 1 denote anddefine positive numbers ε i,m , i = 1, 2 andε m by (2) ε

F V P (u, m) = {w ∈ F V P : σ i (u) = σ i (w), i = 0, . . . , m -1}
i,m = sup{̺ i (w, u) : w ∈ F V P (u, m)}, ε m = max{ε 1,m , ε 2,m }.
We remind the reader the notion of an unfolded billiard trajectory. Namely, instead of reflecting the trajectory in a side of P one may reflect P in this side and unfold the trajectory to a straight line. As a consequence of Theorem 3.2 we obtain

Proposition 3.3. If u ∈ F V P is non-periodic then lim m ε m = 0.
Proof. Unfolding billiard trajectories immediately yields lim m ε 2,m = 0. Note that ε m is decreasing and assume that

ε 0 = lim m ε m > 0. Then necessarily also ε 0 = lim m ̺ 1 (u, w m ) for some w m = (x m , θ m ) ∈ F V P (u, m), i.e., lim m x m = x ∈ e σ 0 (u) and |π 1 (u) -x| = ε 0 . Denoting x the middle of an arc with the endpoints π 1 (u), x, we get σ + ((x, π 2 (u)) = σ + (u), what is impossible by Theorem 3.2.
We let to the reader the verification of the following fact.

Proposition 3.4. Let P be a polygon. For every δ > 0 there exists an m = m(δ) ∈ N such that whenever u, ũ ∈ V P satisfy ̺ 2 (u, ũ) > δ and for some n, |n| ≥ m, the symbols σ n (u), σ n (ũ) exist, then σ n (u) = σ n (ũ).

An increasing sequence {n(i)} i≥0 of positive integers is called syndetic if the sequence {n(i + 1) -n(i)} i≥0 is bounded. A symbolic itinerary σ + is said to be (uniformly) recurrent if for every initial word (σ 0 , . . . , σ m-1 ) there is a (syndetic) sequence {n

(i)} i≥0 such that (σ n(i) , • • • , σ n(i)+m-1 ) = (σ 0 , • • • , σ m-1
) for all i. For a polygon P and billiard map T :

V P → V P , a point u = (x, θ) ∈ F V P is said to be (uniformly) recurrent if for every ε > 0 there is a (syndetic) sequence {n(i)} i≥0 such that ̺(T n(i) u, u) < ε for each i.
It is easy to see that a (uniformly) recurrent point u has a (uniformly) recurrent symbolic itinerary. It is a consequence of Theorems 3.1,3.2 that the opposite implication also holds true.

Proposition 3.5. Let P be a polygon and u ∈ F V P . Then σ + (u) is (uniformly) recurrent if and only if u is (uniformly) recurrent.

Proof. Suppose σ + (u) is (uniformly) recurrent. By Theorem 3.1 we are done if σ + (u) is periodic. If it is non-periodic, Proposition 3.3 says that lim m ε m = 0, where ε m were defined in (2). Choose an ε > 0. Then ε m < ε for some m and we can consider a (syndetic) sequence {n(i, m)} i≥0 corresponding to the initial word (σ 0 , . . . , σ m-1 ) of σ + (u). Clearly,

̺(T n(i,m) u, u) ≤ ε m < ε
for each i. The converse is clear.

Code Equivalence

Definition 4.1. We say that polygons P, Q are code equivalent if there are points

u ∈ F V P , v ∈ F V Q such that (C1) {π 1 (T n u)} n≥0 = ∂P , {π 1 (S n v)} n≥0 = ∂Q, (
C2) the symbolic forward itineraries σ + (u), σ + (v) are the same; the points u, v will be sometimes called the leaders.

Clearly any two rectangles are code equivalent, and also two code equivalent polygons P, Q have the same number of sides. In this case we always consider their counterclockwise numbering e

1 = [p 1 , p 2 ], . . . , e k = [p k , p 1 ] for P , resp. f 1 = [q 1 , q 2 ], . . . , f k = [q k , q 1 ]
for Q. We sometimes write e i ∼ f i to emphasize the correspondence of sides e i , f i . The verification that this relation is reflexive, symmetric and transitive is left to the reader. Definition 4.2. Let P be a polygon and u, ũ ∈ F V P . We say that trajectories of u, ũ intersect before their symbolic separation if either (p) for some positive integer ℓ, σ ℓ (u) = σ ℓ (ũ),

σ k (u) = σ k (ũ) whenever k ∈ {0, . . . , ℓ -1}
and for some k 0 ∈ {0, . . . , ℓ -1}, the segments with endpoints

π 1 (T k 0 u), π 1 (T k 0 +1 u) and π 1 (T k 0 ũ), π 1 (T k 0 +1 ũ) intersect; or (n) for some negative integer ℓ, σ ℓ (u) = σ ℓ (ũ), σ k (u) = σ k (ũ) whenever k ∈ {ℓ + 1, . . . , 0}
and for some k 0 ∈ {ℓ, . . . , -1}, the segments with endpoints

π 1 (T k 0 u), π 1 (T k 0 +1 u) and π 1 (T k 0 ũ), π 1 (T k 0 +1 ũ) intersect.
For u ∈ F V P , a side e of P and θ ∈ (-π 2 , π 2 ) we put

(3)

I(u, e, θ) = {n ∈ N ∪ {0} : π 1 (T n u) ∈ e, π 2 (T n u) = θ}.
Throughout the section let

u n = T n u, x n = π 1 (u n ), v n = S n v, y n = π 1 (v n ).
Proposition 4.3. Let polygons P, Q be code equivalent with leaders u, v, u recurrent. For any m, n ∈ I(u, e, θ), the trajectories of S m v, S n v cannot intersect before their symbolic separation.

x m(1) x n(1)

x m(1)+ℓ Proof. The case when x m < x n and y m < y n , resp. y n < y m will be called increasing, resp. decreasing. Thus, using the two parts of Definition 4.2 and assuming that the conclusion is not true we can distinguish the following four possibilities: (p)-increasing, (p)-decreasing, (n)-decreasing and (n)-increasing. Let us prove the (n)-increasing case. In this case there are m, n ∈ I(u, e, θ), some negative ℓ, k 0 such that x m < x n , y m < y n and the second part (n) of Definition 4.2 is fulfilled.

Note that we have only assumed that the forward iterates of x and y have the same code, but in the (n)-increasing case we want to exclude the intersection of their backwards orbits. We overcome this problem by approximating x m and y n by their forward orbits. This can be done since the leader u is recurrent, hence by Proposition 3.5 v is also recurrent. We consider sufficiently large integers m(1), n(1) ∈ 1)+k (v) whenever k ∈ {ℓ + 1, . . . , 0}; since for some k 0 ∈ {ℓ, . . . , -1}, the segments with endpoints π 1 (T m(1)+k 0 v), π 1 (T m(1)+k 0 +1 v) and π 1 (T n(1)+k 0 v), π 1 (T n(1)+k 0 +1 v) intersect and the points u m(1) , u n(1) are (almost) parallel, we get

(-ℓ, ∞) such that v m(1) , resp. v n(1) approximates v m , resp. v n . Then σ m(1)+ℓ (v) = σ n(1)+ℓ (v), σ m(1)+k (v) = σ n(
sgn (σ m(1)+ℓ (u) -σ n(1)+ℓ (u)) = sgn (σ m(1)+ℓ (v) -σ n(1)+ℓ (v)),
what is not possible for the leaders u, v. The other three cases are analogous.

In the last part of this section we present Corollaries 4.5-4.9 of Proposition 4.3 under the following Assumption 4.4. Let P ,Q be code equivalent polygons with leaders u, v and the set of directions {π 2 (T n u) : n ≥ 0} along the trajectory of u is finite.

When proving Corollaries 4.5-4.9 we denote α n = π 2 (u n ), β n = π 2 (v n ). By Definition 4.1(C1) the first projection of the forward trajectory of u, resp. of v is dense in ∂P , resp. ∂Q, so in particular, neither u nor v is periodic. In any case, the set I(u, e, θ) defined for a side e = e i in (3) is nonempty only for θ's from the set {π 2 (T n u) : n ≥ 0} which is assumed to be finite. In what follows we fix such e and θ.

Applying Corollary 2.4 and Proposition 3.5 we obtain that both the leaders u and v are uniformly recurrent.

Obviously the set (4) J (e, θ) = {y n : n ∈ I(u, e, θ)} is a perfect subset of a side f = f i ∼ e. The counterclockwise orientation of ∂Q induces the linear ordering of f and we can consider two elements min J (e, θ), max J (e, θ) ∈ f . Define a function g : {y n } n∈I(u,e,θ) → (-π 2 , π 2 ) by g(y n ) = β n . Corollary 4.5. The function g can be extended continuously to the map G :

J (e, θ) → [-π 2 , π 2 ]. Moreover, G(y) ∈ (-π 2 , π 2 ) for each y ∈ J (e, θ) \ {min J (e, θ), max J (e, θ)}. Proof. Put G(y n ) = β n . Proposition 4.3 clearly shows that for n(k) ∈ I(u, e, θ), y n(k) → k y ∈ J (e, θ) implies β n(k) → β ∈ [- π 2 , π 2 ]
and we can put G(y) = β.

Let y ∈ J (e, θ) \ {min J (e, θ), max J (e, θ)} and choose y n(i) , y n(j) such that (5) y ∈ (y n(i) , y n(j) ).

If G(y) = -π 2 , resp. G(y) = π 2 then by ( 5) and the continuity of G, for some v n(k) sufficiently close to (y, -π 2 ), resp. (y, π 2 ), the trajectories of v n(j) , v n(k) , resp. v n(i) , v n(k) intersect before their symbolic separation, what contradicts Proposition 4.3. Thus G(y) ∈ (-π 2 , π 2 ). The notion of combinatorial order has been introduced in (1).

Corollary 4.6. The sequences {x n } n∈I(u,e,θ) ⊂ e and {y n } n∈I(u,e,θ) ⊂ f have the same combinatorial order.

Proof. The conclusion is true when #I(u, e, θ) ≤ 1. Assume to the contrary that for some m, n ∈ I(u, e, θ), x m < x n and y n < y m .

Since by Proposition 4.3 the trajectories of v m , v n cannot intersect before their symbolic separation,

sgn (σ k (u m ) -σ k (u n )) = sgn (σ k (v m ) -σ k (v n ))
for some k ∈ N, what is not possible for the leaders u, v. The case x n < x m and y m < y n can be disproved analogously. where the number of summands on the left is by Assumption 4.4 finite, Baire's theorem [START_REF] Rudin | Real and Complex Analysis[END_REF]Theorem 5.6] implies that there exists a side e and an angle θ for which J (e, θ) has a nonempty interior. Denote [c, d] a nontrivial connected component of J (e, θ). Put

τ = {(y, G(y)) : y ∈ [c, d]}.
Corollary 4.7. There is a countable subset τ 0 of τ such that each point from τ \ τ 0 has a bi-infinite trajectory (either the forward or backward trajectory starting from any point of τ 0 finishes in a corner of Q).

Proof. Assume that there are two points v, ṽ ∈ τ such that π 1 (v) < π 1 (ṽ), for some

k ∈ N π 1 (S k v) = π 1 (S k ṽ) is a common corner and σ i (v) = σ i (ṽ) for i ∈ {0, . . . , k -1}. As before let v n = S n v. Choose three of these points v ℓ , v m , v n ∈ τ satisfying • π 1 (v m ) < π 1 (v ℓ ) < π 1 (v n ) • v m , resp. v n is (sufficiently) close to v, resp. ṽ
Then the trajectories of either v m , v ℓ or v ℓ , v n intersect before their symbolic separation, contradicting Proposition 4.3. Thus for each k ≥ 1 and each v, ṽ ∈ τ with common symbolic itenerary of length k, we can not have π 1 (S k v) = π 1 (S k ṽ) is a corner, or equivalently each corner can have at most one preimage of order k for each forward symbolic itinerary segment of length k. This implies that the set τ 0,F = τ \ F V Q is at most countable. This is also true for τ 0,B = τ \ BV Q and we can put τ 0 = τ 0,F ∪ τ 0,B .

= π 1 (τ 0 ) is countable and G is continuous, it is sufficient to show that G ′ (ỹ 0 ) = 0 whenever ỹ0 ∈ (c, d) \ C.
To simplify the notation, choose the origin of S 1 to be the direction perpendicular to the side of Q containing (c, d) and fix ỹ0 ∈ (c, d) \ C; then by Corollary 4.5 for a sufficiently small neighborhood U(ỹ 0 ) of ỹ0 , G(U(ỹ 0 )) ⊂ (-π 2 , π 2 ). For ỹ ∈ U(ỹ 0 ) \ C consider the unfolded (bi-infinite) billiard trajectory of (ỹ, G(ỹ)) under the billiard flow {S t } t∈R in Q. Via unfolding, this trajectory corresponds to the line p G(ỹ) with the equation y = ỹ + z tan G(ỹ).

Claim 4.9. There is no sequence {ỹ n } n≥1 ⊂ (c, d)\C such that lim n ỹn = ỹ0 and the set of crossing points {p G(ỹ 0 ) ∩ p G(ỹn) : n ≥ 1} is bounded.

Proof. Assuming the contrary of the conclusion we can consider sufficiently large n and some point v k , resp. v ℓ approximating (ỹ 0 , G(ỹ 0 )), resp. (ỹ n , G(ỹ n )) such that the trajectories of v k , v ℓ intersect before their symbolic separation, what is impossible by Proposition 4.3. Now, applying Lemma 2.5 and Claim 4.9 we obtain that the function G satisfies G ′ (ỹ 0 ) = 0 for every ỹ0 ∈ (c, d)\C, i.e., for some ϑ ∈ (-

π 2 , π 2 ), G ≡ ϑ is constant on [c, d].

Rational versus Irrational

Lemma 5.1. Let P ,Q be code equivalent with leaders u, v; P rational. Then the set of directions

{π 2 (S n v) : n ≥ 0}
along the trajectory of v is finite.

Proof. Applying Lemma 2.5 and Corollary 4.9 we obtain that the function G defined in Corollary 4.5 satisfies G ′ (ỹ 0 ) = 0 for every ỹ0 ∈ (c, d) \ C, i.e., for some ϑ ∈ (-π 2 , π 2 ), G ≡ ϑ is constant on [c, d], where [c, d] is a nontrivial connected component of J (e, θ) defined in (4).

We know that the leader v is uniformly recurrent. Take a positive integer n ∈ I(u, e, θ) and a positive ε 0 such that

(y n -ε 0 , y n + ε 0 ) ⊂ (c, d).
There is a syndetic sequence {n(i)} i≥0 ⊂ I(u, e, θ) for which

̺(S n(i) v n , v n ) < ε 0 , π 2 (S n(i) v n ) = ϑ
for each i. This shows that the set of directions {π 2 (S n v) : n ≥ 0} along the trajectory of v is finite.

Remark 5.2. In Lemma 5.1 we do not assume that u is non-exceptional.

Theorem 5.3. Let P , Q be code equivalent with leaders u, v; P rational, u non-exceptional. Then Q is rational with v non-exceptional.

Proof. As before, we put x n = π 1 (T n u) and y n = π 1 (S n v). Assume v is exceptional. By Definition 4.1 v is non-periodic. At the same time Lemma 5.1 says that the set of directions

{π 2 (S n v) : n ≥ 0}
along the trajectory of v is finite. Thus Proposition 2.1 implies that if Q is rational then v is minimal in a flat strip or in an invariant surface R π 2 (v) . On the other hand if Q is irrational, Lemma 5.1 and Theorem 2.3(ii) imply that v is minimal in a flat strip.

Suppose that v is exceptional, then it is parallel to a generalized diagonal d which is the boundary of a minimal flat strip. The minimality implies that v is not only parallel to d, but v also approximates d. Denote y, resp. y ′ an outgoing, resp. incoming corner of d with ( 6)

y ′ = π 1 (S ℓ (y, β))
for some ℓ ∈ N and a direction β with respect to a side f = f i = [q i , q i+1 ]. Let us assume that y = q i and that v approximates d from the side f (the case when v approximates d from the other side, i.e. y = q i+1 is similar). Since v approximates d and the set {π 2 (S n v) : n ≥ 0} is finite we can consider a sequence {n(k)} k≥0 such that for each k,

S n(k) v = (y n(k) , β), y n(k) ∈ f, S n(k)+ℓ v = (y n(k)+ℓ , β ′ ), y n(k)+ℓ ∈ f ′ ,
lim k→∞ y n(k) = y and lim k→∞ y n(k)+ℓ = y ′ , where ℓ is given by ( 6) and f ′ is the appropriate side of Q with endpoint y ′ . Let e = e i = [p i , p i+1 ], resp. e ′ be the sides of P corresponding to f , resp. f ′ . Since P is rational, we can assume that {n(k)} k≥0 ⊂ I(u, e, α) and {n(k) + ℓ} k≥0 ⊂ I(u, e ′ , α ′ ) for some α, α ′ ∈ (-π 2 , π 2 ) and Corollary 4.6 can be used. By that corollary the combinatorial order of the sequences {x n } n∈I(u,e,α) ⊂ e and {y n } n∈I(u,e,α) ⊂ f , resp. {x n } n∈I(u,e ′ ,α ′ ) ⊂ e ′ and {y n } n∈I(u,e ′ ,α ′ ) ⊂ f ′ are the same. We assume the leader u to be non-exceptional hence by Proposition 2.1, the sequence {x n } n∈I(u,e,α) , resp. {x n } n∈I(u,e ′ ,α ′ ) is dense in the side e, resp. e ′ . Then necessarily lim k→∞ x n(k) = x ∈ C P ∩ e and lim k→∞ x n(k)+ℓ = x ′ ∈ C P ∩ e ′ , hence

x ′ = π 1 (T ℓ (x, α)),
what contradicts our choice of non-exceptional u. Thus, the leader v has to be non-exceptional.

In order to verify that Q is rational, one can simply use Theorem 2.3(i) and Lemma 5.1.

Rational versus Rational -Preparatory Results

Throughout this section we will assume that P, Q are rational and code equivalent with non-exceptional leaders u, v, Theorem 5.3 implies that the assumption that v is non-exceptional is redundant. Lemma 6.1. Let P, Q rational be code equivalent with non-exceptional leaders u, v. For every side e i and every direction θ ∈ π 2 ((e i ×(-

π 2 , π 2 ))∩ ω(u)) there exists a direction ϑ ∈ π 2 ((f i × (-π 2 , π 2 )) ∩ ω(v)
) such that I(u, e i , θ) = I(v, f i , ϑ) and the sequences {π 1 (T n u)} n∈I and {π 1 (S n v)} n∈I have the same combinatorial order.

Proof. Let us fix a side e i and a direction θ ∈ π 2 ((e i × (-π 2 , π 2 )) ∩ ω(u)). Using Corollaries 4.5, 4.8 we obtain for some ϑ ∈ π 2 ((

f i × (-π 2 , π 2 )) ∩ ω(v)) I(u, e i , θ) ⊂ I(v, f i , ϑ); starting from f i , ϑ we get I(u, f i , ϑ) ⊂ I(v, e i , θ) hence I = I(u, f i , ϑ) = I(v, e i , θ
). The fact that the sequences {π 1 (T n u)} n∈I and {π 1 (S n v)} n∈I have the same combinatorial order is a direct consequence of Corollary 4.6.

Proposition 2.1 and Lemma 6.1 easily yield Corollary 6.2. Let P, Q rational be code equivalent with non-exceptional leaders u, v. Then N P = N Q .

Lemma 6.3. Suppose P, Q are rational and code equivalent with nonexceptional leaders u, v; let σ + = {σ k } k≥0 denote their common itinerary.

If

σ m = σ n then π 2 (T m u) < π 2 (T n u) ⇐⇒ π 2 (S m v) < π 2 (S n v).
Proof. As before we denote

u n = T n u, x n = π 1 (u n ), v n = S n v, y n = π 1 (v n ). Let σ m = σ n = i ∈ {1, . . . , k} for some m, n ∈ N ∪ {0}; it follows from Lemma 6.1 that θ 1 = π 2 (u m ) = π 2 (u n ) = θ 2 if and only if ϑ 1 = π 2 (v m ) = π 2 (v n ) = ϑ 2 . If our conclusion does not hold we necessarily have (7) - π 2 < θ 1 < θ 2 < π 2 and - π 2 < ϑ 2 < ϑ 1 < π 2 .
By Proposition 2.1, each of the two sequences

X j = {x n : n ∈ I(u, e i , θ j )}, j ∈ {1, 2}
is dense in e i and an analogous statement is true for

Y j = {y n : n ∈ I(u, f i , ϑ j )}, j ∈ {1, 2}.
Moreover, from Lemma 6.1 we know that the sequences X j and Y j , j ∈ {1, 2} have the same combinatorial order.

Let m = max{m(|θ 1 -θ 2 |), m(|ϑ 1 -ϑ 2 |)} due to Proposition 3.4. To a given ε > 0 one can consider integers m(1), m(2) ∈ (m, ∞), m(1) < m(2), for which x m(1) , x m(2) ∈ [p i , p i + ε], π 2 (u m(1) ) = θ 1 , π 2 (u m(2) ) = θ 2
and also

y m(1) , y m(2) ∈ [q i , q i + ε], π 2 (v m(1) ) = ϑ 1 , π 2 (v m(2) ) = ϑ 2 . Then σ m(1)-m (u), σ m(2)-m (u), resp. σ m(1)-m (v), σ m(2)-m (v)
(σ m(1)-m (u) -σ m(2)-m (u)) = sgn (σ m(1)-m (v) -σ m(2)-m (v)),
what is impossible for the leaders u, v, a contradiction.

For a polygon P and its corner p j ∈ C P , an element w ∈ V P points at p j if π 1 (T w) = p j . For u ∈ F V P we denote N(u, p j ) the number of elements from ω(u) that point at p j . Lemma 6.4. Let P, Q rational be code equivalent with non-exceptional leaders u, v. Then N(u, p j ) = N(v, q j ), 1 ≤ j ≤ k, where k is a common number of sides of P, Q.

Proof. Let (x, θ) ∈ ω(u) point at p j , x ∈ e = e i . Since u is nonexceptional, (x, θ) ∈ BV P is not periodic and it is a bothside limit of {T n u} n∈I , where I = I(u, e, θ). Using Lemma 6.1 we can consider a direction ϑ ∈ π 2 ((f i ×(-π 2 , π 2 ))∩ω(v)) such that I(u, e, θ) = I(v, f, ϑ) and the (dense) sequences {π 1 (T n u)} n∈I , {π 1 (S n v)} n∈I have the same combinatorial order. Clearly, there is a unique element (y, ϑ) ∈ ω(v) (with the same address as (x, θ)) pointing at q j and satisfying (y, ϑ) ∈ BV Q , σ -((x, θ)) = σ -((y, ϑ)). The last equality and Theorem 3.2 imply N(u, p j ) ≤ N(v, q j ). The argument is symmetric, thus we obtain N(u, p j ) = N(v, q j ).

Rational versus Rational -Main Results

Let A(p) ∈ (0, 2π) \ {π} denote the angle at the corner p ∈ C P .

Theorem 7.1. Let P, Q be code equivalent with leaders u, v; P rational, u non-exceptional. Then A(p i ) = A(q i ), 1 ≤ i ≤ k.

Proof. Theorem 5.3 implies that also Q is rational with a non-exceptional leader v. Let k = #C P = #C Q ; Since P , Q are rational and simply connected, A(p i ) = πm P i /n P i and A(q

i ) = πm Q i /n Q i , where m P i , n P i , resp. m Q i , n Q i are coprime integers.
In what follows, we will show that n P i = n Q i and m P i = m Q i . We know from Corollary 6.2 that N P = N Q = N. Thus, both rational billiards correspond to the same dihedral group D N .

Second, consider the local picture around the ith vertex p i . Denote the two sides which meet at p i by e and e ′ . Suppose there are 2n P i copies of P which are glued at p i . Enumerate them in a cyclic counterclockwise fashion 1, 2, . . . , 2n P i . Since u is non-exceptional its orbit is minimal, so it visits each of the copies of P glued at p i . In particular the orbit crosses each of the gluings (copy j glued to copy j + 1). Now consider the orbit of v. We need to show that there are the same number of copies of Q glued at q i . Fix a j ∈ {1, . . . , 2n P i } viewed as a cyclic group. Since u is non-exceptional the orbit of u must pass from copy j to copy j + 1 of P or vice versa from copy j + 1 to copy j. Suppose that we are at the instant that the orbit u passes from copy j to copy j + 1 of P . At this same instant the orbit of v passes through a side. We label the two copies of Q by j and j + 1 respectively. This labeling is consistent for each crossing from j to j + 1.

Since this is true for each j, the combinatorial data of the orbit u glue the corresponding 2n P i copies of Q together in the same cyclic manner as the corresponding copies of P . Note that the common point of the copies of Q is a common point of f and f ′ -the sides of Q corresponding to e, e ′ -thus it is necessarily the point q i . In particular, since Lemma 6.3 applies, we have 2n P i copies of Q glued around q i to obtain an angle which is a multiple of 2π. Thus 2n Q i must divide 2n P i . The argument is symmetric, thus we obtain 2n P i divides 2n Q i . We conclude that n

P i = n Q i . Third, let us show that m Q i = m P i .
Realizing the gluing of 2n P i copies of P together at p i we get a point p ∈ R P with total angle of 2πm P i . If m P i > 1, the point p is a cone angle 2πm P i singularity. In any case, for the direction θ and the corresponding constant flow on R P , there are m P i incoming trajectories that enter p on the surface R P , hence also m P i points in V P that finish their trajectory after the first iterate at the corner p i . Repeating all arguments for Q and ϑ = π 2 (v), one obtain m Q i points in V Q that finish their trajectory after the first iterate at the corner q i . Since such a number has to be preserved by Lemma 6.4, the inequality m P i = m Q i contradicts our assumption that P and Q are code equivalent. Thus, m Q i = m P i . A triangle is determined (up to similarity) by its angles, thus Theorem 7.1 implies Corollary 7.2. Let P, Q be code equivalent with leaders u, v, P a rational triangle, u non-exceptional. Then Q is similar to P .

For a P rational, the union of edges of R P -we call it the skeleton of R P -will be denoted by K P .

It follows from Proposition 2.1 that for P rational with u ∈ V P nonexceptional, ω(u) = K P .

Proposition 7.3. Let P , Q be code equivalent with leaders u, v; P rational, u non-exceptional. The map Ψ : orb(u) → orb(v) defined by Ψ(T n u) = S n v, n ∈ N ∪ {0} can be extended to the homeomorphism Φ : K P → K Q satisfying (for all n ∈ Z for which the image is defined)

Φ(T n ũ) = S n Φ(ũ), ũ ∈ K P .
Proof. Proposition 2.1, Theorem 5.3 and Lemma 6.3 enable us to extend Ψ to the required homeomorphism Φ :

K P → K Q .
It is a well known fact that the billiard map T has a natural invariant measure on its phase space V P , the phase length given by the formula µ = sin θ dx dθ -see [MT]. In the case, when P is rational and the corresponding billiard flow is dense in the surface R P , the measure µ sits on the skeleton K P of R P . In particular, an edge e of K P associated with θ has the µ-length |e| • sin θ.

For any rational polygon with N = 2 we can speak -up to rotation -about horizontal, resp. vertical sides. Two such polygons, P and Q with sides e i resp. f i , are affinely similar if they have the same number of corners/sides, corresponding angles equal and there are positive As before the number N is defined as the least common multiple of n i 's, where the the angles of a simply connected rational polygon P are πm i /n i .

Theorem 7.4. Let P , Q be code equivalent with leaders u, v; P rational, u non-exceptional. Denote µ, ν the phase length measure sitting on the skeleton K

P , K Q respectively. If ν = Φ * µ then (1) if N = N P ≥ 3, Q is similar to P ; (2) if N = N P = 2, Q is affinely similar to P .
Proof. We know from Theorem 5.3 that under our assumptions also Q is rational with v non-exceptional. By Lemma 6. Assume that the least common multiple N of the denominators of angles of P is greater than or equal to 3. The polygons P , Q correspond to the same dihedral group D N generated by the reflections in lines through the origin that meet at angles π/N. The orbit of θ + 0 = π 2 (u 0 ), resp. ϑ + 0 = π 2 (u 0 ) under D N consists of 2N angles θ + j = θ + 0 + 2jπ/N, θ - j = θ - 0 + 2jπ/N, resp.

ϑ + j = ϑ + 0 + 2jπ/N, ϑ - j = ϑ - 0 + 2jπ/N. Since N ≥ 3, for each side e, resp. f one can consider the angles θ, θ + 2π/N, resp. ϑ, ϑ + 2π/N such that by Lemma 6. In a rational polygon we say that a point u is generic if it is nonexceptional, has bi-infinite orbit and the billiard map restricted to the skeleton K P of an invariant surface R P ∼ R π 2 (u) has a single invariant measure (this measure is then automatically the measure µ).

Corollary 7.5. Let P , Q be code equivalent with leaders u, v; P rational, u generic. Then

(1) if N = N P ≥ 3, Q is similar to P ;

(2) if N = N P = 2, Q is affinely similar to P .

Proof. Obviously the dynamical systems (K P , T ), (K Q , S) are conjugated via the conjugacy Φ, hence by our assumption on the element u, both of them are uniquely ergodic. It means that ν = Φ * µ, where µ, ν are the phase lengths and Theorem 7.4 applies.

Code versus order equivalence

In [BT] we have defined another kind of equivalence relation on the set of simply connected polygons. Namely, we used Definition 8.1. We say that polygons (or polygonal billiards) P, Q are order equivalent if for some u ∈ F V P , v ∈ F V Q (O1) {π 1 (T n u)} n≥0 = ∂P , {π 1 (S n v)} n≥0 = ∂Q, (O2) the sequences {π 1 (T n u)} n≥0 , {π 1 (S n v)} n≥0 have the same combinatorial order; the points u, v will be called leaders.

It is easy to see that any two rectangles are order equivalent. Let t = {x n } n≥0 be a sequence which is dense in ∂P . The t-address a t (x) of a point x ∈ ∂P is the set of all increasing sequences {n(k)} k of non-negative integers satisfying lim k x n(k) = x. It is clear that any x ∈ ∂P has a nonempty t-address and t-addresses of two distinct points from ∂P are disjoint.

  Figure 1. Parallel versus Crossing with k 0 = -2, the (n)-increasing case

Since

J

  (e, θ) = ∂Q,

Corollary 4. 8 .

 8 The continuous function G : J (e, θ) → [-π 2 , π 2 ] defined in Corollary 4.5 has to be constant on each connected component [c, d] of J (e, θ). Proof. Since by Corollary 4.7 the projection C

  exist and by Proposition 3.4 they are different. From (7) we get sgn

  numbers a, b ∈ R such that |e i |/|f i | = a, resp. |e i |/|f i | = b for any pair of corresponding horizontal, resp. vertical sides. Recall the map Φ defined in Proposition 7.3.

  2, N P = N Q . 1) For a side e of P and a θ ∈ [-π 2 , π 2 ] denote [e, θ] an edge of K P associated with e and θ. Let [f, ϑ] = Φ([e, θ])). Since ν = Φ * µ and µ, ν are the phase lengths, (8) |e| sin θ = |f | sin ϑ.

  3 Φ[e, θ] = (f, ϑ) and Φ[e, θ + 2π/N] = [f, ϑ + 2π/N]. Then as in (8), |e| sin θ = |f | sin ϑ, |e| sin(θ + 2π/N) = |f | sin(ϑ + 2π/N), hence after some routine computation we get |e| = |f |.2) By Theorem 7.1 the polygons P and Q are quasisimilar hence we can speak about corresponding horizontal, resp. vertical sides. Similarly as above, for a side e of P , some θ ∈[-π 2 , π 2 ] and [f, ϑ] = Φ([e, θ]), |e| sin θ = |f | sin ϑ,where θ, resp. ϑ can be taken the same for any pair of corresponding horizontal, resp. vertical sides. Thus, the number a = |e|/|f |, resp. b = |e|/|f | does not depend on a concrete choice of a pair of corresponding horizonal, resp. vertical sides. This finishes the proof of our theorem.

Acknowledgements We gratefully acknowledge the support of the "poste tcheque" of the University of Toulon. The first author was also supported by MYES of the Czech Republic via contract MSM 6840770010. The second author was supported by ANR-10-BLAN 0106 Perturbations.

For order equivalent polygons P , Q with leaders u, v, we will consider addresses with respect to the sequences given by Definition 8.1(O2):

It is an easy exercise to prove that the map φ : ∂P → ∂Q defined by ( 9)

is a homeomorphism. As before, the set of the corners p 1 , . . . , p k of P is denoted by C P .

Theorem 8.2. Suppose P , Q are order equivalent with leaders u, v; P rational, u non-exceptional. Then P , Q are code equivalent with leaders u, v.

the symbolic forward itineraries σ + (u), σ + (v) are the same.

Theorem 8.3. Suppose P, Q are code equivalent with leaders u, v; P rational, u generic. Then P, Q are order equivalent with leaders u, v.

Proof. Apply Corollary 7.5, then P and Q are similar (or affinely similar). Let Φ be the map defined in Proposition 7.3. N = 3. By Proposition 7.3, Φ(u) = v. Since P and Q are similar, Theorem 3.2 implies that v = u (up to similarity) for the same code of u, v hence P , Q are order equivalent with leaders u, v. N = 2. Arguing as in the proof of Corollary 7.5 we get ν = Φ * µ, where µ, ν are the phase lengths. Now, on different edges

of K P that correspond to the same side [a, b] of P the proportions given by µ are preserved, i.e., for µ i = µ|k i and each x ∈ (a, b) and corresponding

Since ν = Φ * µ and ν is the phase length, on ℓ i = Φ(k i ) the proportions given by ν are also preserved. It means that the sequences {π 1 (T n u)} n≥0 , {π 1 (S n v)} n≥0 have the same combinatorial order and P , Q are order equivalent with leaders u, v.

Corollary 8.4. Suppose P is a rational polygon and u ∈ F V P is generic. Then P, Q are code equivalent with leaders u, v if and only if P, Q are order equivalent with leaders u, v.

Proof. It follows from Theorems 8.2 and 8.3.