Lionel B Érard Bergery May

Semi-Riemannian Symmetric spaces

Keywords:

We begin with a general definition for (real smooth) symmetric spaces.

Definition 1.1.1 A (differential, real) symmetric space is a pair (M, S) where

• M is connected (real smooth) manifold (see comment below)

• S is a smooth map M × M -→ M satisfying the following Axioms

-(SS1) S(x, x) = x ∀ x ∈ M, - (
-(SS4) T (x,x) S(0, ξ) = -ξ ∀ x ∈ M, ∀ ξ ∈ T x M.
Comment 1.1.2 Symmetric spaces were first defined in the settings of smooth manifolds.

There are now various generalizations. In this paper, we will consider only the classical case and we will not repeat "real smooth". Also manifold will mean real smooth manifold whose topology is Hausdorff and first comptable. Usually, we consider only connected symmetric spaces.

Axioms (SS1) to (SS4) are quite convenient for computations, but their meaning is not so clear. A more "geometric" viewpoint is better for understanding the definition. We first introduce a notation.

Definition 1.1.3 For all x ∈ M , we denote by s x : M -→ M the map given by s x (y) = S(x, y) ∀ y ∈ M, and we call s x the symmetry (centered) at x.

Then Axiom (SS1) means that x is a fixed point of s x and Axiom (SS2) that any symmetry s x is an involutive diffeomorphism of M (for all x in M ). Now Axiom (SS3) may be written as the formula :

s x • s y • s x = s sx(y) .
In words : the conjugate of the symmetry s y by another symmetry s x is also a symmetry, more precisely the symmetry at s x (y). If we consider only Axioms (SS1), (SS2) and (SS3), the corresponding spaces are called "spaces with symmetries" (see Loos). Now Axiom (SS4) means T x s x = -Id TxM (for all x ∈ M ). It is often presented through a different (but equivalent) formulation : for any x in M , the point x is an isolated fixed point of the symmetry s x .

Examples of symmetric spaces

• Example 1 : Take M = R n with S(x, y) = 2xy . Then (R n , S) is a symmetric space. Here M is the canonical affine space and the symmetry s x is the (ordinary) affine symmetry through the point x. That example is often refered to as the canonical flat (1-connected) symmetric space.

• Example 2 : Consider R n+1 with its canonical Euclidean scalar product ., . . Let M be the canonical sphere S n = {x ∈ R n+1 ; x, x = 1}. We define S(x, y) = 2 x, y xy on S n , i.e. s x is the restriction to S n of the orthogonal symmetry through the line Rx.

Then (S n , S) is a symmetric space. That example is often refered to as the canonical Riemannian model space with constant curvature 1.

• Example 3 : Since we will consider semi-Riemannian symmetric spaces, we give here the following generalization of example 2. We denote by R p,q the affine space R p+q equipped with the "minkowskian" scalar product x, y = i=p i=1 x i y i -j=p+q j=p+1 x j y j . We consider in R p+1,q the "generalized sphere" S p,q = {x ∈ R p+1,q ; x, x = 1} and we define S(x, y) = 2 x, y xy as above. Then (S p,q , S) is a symmetric space, refered to as the "canonical" semi-Riemannian model space with signature (p, q) and constant curvature 1.

Notice that example 2 is the case q = 0. Now S p,q is diffeomorphic to S p × R q . In particular, S 0,q has 2 connected components and we replace S 0,q by the connected component of the point (1, 0, . . . , 0), usually denoted by S 0,q 0 , which is diffeomorphic to R q . Similarly, S 1,q is not simply connected, so we replace it by its universal covering, usually denoted by S 1,q . That one is diffeomorphic to R q+1 and it is possible to "lift" the symmetric structure S to S 1,q . For p 2, the space S p,q is simply connected. So, with these two replacements for p = 0 or 1, we get 1-connected models.

Here S p,q is indeed a semi-Riemannian manifold with the structure induced by the restriction of the minkowskian scalar product to its tangent spaces, and its signature is (p, q). If we consider the opposite semi-Riemannian structure, it has signature (q, p).

The corresponding semi-Riemannian manifold is denoted by H q,p and is known as the "canonical" semi-Riemannian model space with signature (p, q) and constant curvature -1, or the "generalized hyperbolic space". Notice that the symmetric structures of S p,q and H q,p are obviously the same! On the other hand, the canonical Riemannian hyperbolic space H n = H n,0 0 has the same symmetric structure as S 0,n 0 , which is different from S n .

• Example 4 : Let L be any connected Lie group. We define a symmetric structure on L by S(x, y) = xy -1 x. Then (L, S) is a symmetric space. Hence a Lie group is "canonically" a symmetric space. In that way, we get a lot of examples.

Notice that there are symmetric spaces which are not obtained in that way : for example, S 2 is not a Lie group (more precisely, there is no group structure on S 2 whose operations are smooth).

• Example 5 : The product of two symmetric spaces (M 1 , S 1 ) and (M 2 , S 2 ) is "canonically" a symmetric space for the obvious "product structure" : we take

M = M 1 × M 2 and S((x 1 , x 2 ), (y 1 , y 2 )) = (S 1 (x 1 , y 1 ), S 2 (x 2 , y 2 )), ∀ x 1 , y 1 ∈ M 1 , ∀ x 2 , y 2 ∈ M 2 .
In a similar way, we may build a symmetric space by the product of any (finite) number of symmetric spaces.

• Further examples : We will give some other "classical" examples below in (A COM-PLETER), including projective spaces, grassmannians and others.

1.1.3 Definitions : subspace and morphism Definition 1.1.4 Let (M, S) be a symmetric space. A symmetric subspace of M is a connected submanifold N which is "closed" for S, i.e. satisfies : ∀ x, y ∈ N, S(x, y) ∈ N .

Proposition 1.1.5 A symmetric subspace N of a symmetric space (M, S) is a symmetric space when equipped with the restricition of the symmetric structure S to N .

Comment 1.1.6 Be carefull that in our Example 2 above, S n is not a symmetric subspace of R n+1 , since we modify the symmetric structure. The same remark apply to Example 3.

On the other hand, a symmetric space has many subspaces. Here are some examples.

• Example 1 : Affine subspaces of the canonical affine space R n are symmetric subspaces.

• Example 2 : Any intersection of S n with a linear subspace in R n+1 is a symmetric subspace (which is also a sphere of lower dimension). This is also the case for S p,q , at least if the intersection is non void.

• Example 3 : Any (closed) Lie subgroup of a Lie group is a symmetric subspace.

• Example 4 : In a product of two symmetric spaces (M 1 , S 1 ) and (M 2 , S 2 ), any "factor" such as

M 1 × {x 2 } or {x 1 } × M 2 is a symmetric subspace (∀ x 1 ∈ M 1 , ∀ x 2 ∈ M 2 ).
Definition 1.1.7 Let (M 1 , S 1 ) and (M 2 , S 2 ) be two symmetric spaces. A morphism of symmetric spaces (or symmetric morphism for short) from

(M 1 , S 1 ) to (M 2 , S 2 ) is a smooth map f : M 1 -→ M 2 such that : S 2 (f (x), f (y)) = f (S 1 (x, y)) ∀x, y ∈ M 1 .
We may translate the above formula in terms of symmetries :

f • s x = s f (x) • f ∀x ∈ M 1 .
Obviously, symmetric spaces and morphisms form a category, but we will not comment on that here. We only give some elementary examples.

• Example 1 : Any affine map between canonical affine spaces is a symmetric morphism.

• Example 2 : The inclusion of a symmetric subspace in a symmetric space is a symmetric morphism.

• Example 3 : Any smooth group homomorphism between Lie groups is a symmetric morphism.

• Example 4 : Given a product of two symmetric spaces, the two natural projections onto the two factors are symmetric morphisms.

Once again, notice that the inclusion of S n in R n+1 is not a symmetric morphism.

Additionnal structures and classifications

Since the category of symmetric spaces contains the category of (connected) Lie group, any "classification" of (all) symmetric spaces or any (general) "structure theorem" has to include a similar result for Lie groups.

To study symmetric spaces, one may procede in the following way : consider classical results

for Lie groups and generalize them to symmetric spaces. In this paper, we will consider a different way. Symmetric spaces will be considered as "geometrical objects", and studied for their geometrical properties. As a consequence, we will study classes of symmetric spaces with additionnal (geometric) structures, with a particular attention for semi-Riemannian symmetric spaces. We begin with some definitions.

Definition 1.1.8 A semi-Riemannian symmetric space (M, S, g) is

• a symmetric space (M, S), together with

• a semi-Riemannian structure g on M such that : But there are many other semi-Riemannian symmetric spaces, contrarily to the Riemannian case.

s x is a g-isometry ∀x ∈ M Comment 1.1.9
A classification was given by M. CAHEN and N. WALLACH (A COMPLETER) for the Lorentz case (i.e. signature (1, n -1)), and by M. CAHEN and M. PARKER for the case with signature (2, n -2).

We will give a structure theorem for the general case and show how those works took place in the general picture.

• Example 1 : On the affine space R n , we consider a minkowskian scalar product, and translate it on R n , giving a (flat) semi-Riemannian metric g. Then we get a semi-Riemannian symmetric space. In that way, the (unique) canonical symmetric structure on R n admits a lot of compatible semi-Riemannian structures.

• Example 2 : The canonical sphere S n with its canonical Riemannian structure is a Riemannian symmetric space.

• Example 3 : In the same way, the space S p,q from (A COMPLETER) is a semi-Riemannian symmetric space, when equipped with the semi-Riemannian structure g p,q

induced on its tangent spaces by the minkowskian scalar product of the ambient R p+1,q . Also s H p,q is nothing but S q,p withg q,p .

• Example 4 : Any semi-simple Lie group G has a canonical semi-Riemannian structure, invariant through left and right translations and defined at its unit point e by the Killing form on the Lie algebra of G.

• Example 5 : Products of semi-Riemannian symmetric spaces are semi-Riemannian symmetric spaces for the product semi-Riemannian structure.

We may consider other structures. Here we only introduce the most classical ones. We will come back to that subject later with the concept of "holonomy" (see A COMPLETER).

Definition 1.1.10 A symmetric space (M, S) is called

• complex if M is a complex manifold and s x is a holomorphic map ∀x ∈ M .

• symplectic if M admits a symplectic structure ω such that s x is a symplectic map ∀x ∈ M .

Comment 1.1.11 As above, if g is a Riemannian structure (i.e. positive definite), then a semi-Kählerian symmetric space (M, S, g, J, ω) is called a Kählerian symmetric space.

Kählerian symmetric spaces were classified by E. CARTAN among the Riemannian ones.

Also, M. BERGER classified semi-Kählerian symmetric spaces among the symmetric spaces which are homogeneous under a simple (or semi-simple) Lie group.

Notice that semi-Kählerian symmetric spaces are symplectic. Ther are symplectic symmetric spaces which are not semi-Kählerian, but they are not "classical". We will give some examples below (see A COMPLETER).

Now we give some examples (and comments) for the complex case.

• Example 1 : The complex affine space C n , with S(x, y) = 2xy, is obviously a complex symmetric space. Notice that it is onced again the canonical symmetric space R 2n with a complex structure on it. Also R 2n has a lot of compatible complex structures.

• Example 2 : We consider on C n+1 the complex-quadratic non-degenerate structure (z, w) = j=n+1 j=1 z j w j . The "complex sphere" is

S n C = {z ∈ C n+1 ; (z, z) = 1}. We see easily that S n
C is a complex symmetric space for S(z, w) = 2(z, w)zw.

• Example 3 : We consider on C n+1 the semi-hermitian non-degenerate structures z, w = j=p+1 j=1 zj w j -k=n+1 k=p+2 zk w k and denote q = np. The subset S 2p+1,2q = {z ∈ C n+1 ; z, z = 1} is not a complex manifold. [Notive that the notation S 2p+1,2q is compatible with the previous one in (A COMPLETER) through an identification between C n+1 and R 2n+2 ].

Hence we consider the complex projective space CP n and the projection proj : C n+1 -{0} -→ CP n . We denote by CP p,q the image proj (S 2p+1,2q ). This an open set in CP n and it is the whole of CP n if p = 0 or q = 0.

For any z in S 2p+1,2q , we consider the hermitian reflexion s H z (w) = 2 z, w zw through the complex vector line Cz. Notice that s H z is a (complex) bijective linear map with respect to w, so s H induces a projective isomorphism s z . Now we may check easily

that if z, w ∈ S 2p+1,2q and [z] = proj(z), [w] = proj(w) ∈ CP n , then S([z], [w]) = s [z] ([w]) = [s H z (w)
] gives a symmetric strucutre on CP p,q . Moreover, we get a semi-Kählerian structure g p,q on CP p,q , with signature (p, q) [and a Kählerian structure on CP n if q = 0], through a projection on the tangent spaces to CP n at [z] of the scalar product ., . restricted to the (complex) vector space orthogonal to the line Cz. Also, we denote by CH p,q the complex symmetric space CP q,p together with the semi-Kählerian structure corresponding tog q,p . Here CH p,0 (usually denoted by CH n ) is Comment 1.1.12 1. Notice that there exists a construction analoguous to example 3

where we replace C by the field of quaternions H. The resulting spaces are not semi-Káhlerian and not even complex.

2. In example 1 above, C n admits (a lot of) semi-Kählerian (and Kählerian) compatible structures.

On the other hand, the complex sphere S n C admits no semi-Kählerian compatible structure, but it admits a compatible (real) semi-Riemannian structure [with signature (n,n)].

3. The "symmetric map" S is a holomorphic map in examples 1 or 2, but not in example 3.

Hence we may distinguish a special type of complex symmetric spaces, with the following definition.

Definition 1.1.13 A complex symmetric space (M, S) is called totally complex if the sym-

metric map S : M × M -→ M is a holomorphic map.
So C n and S n C are totally complex, while CP p,q and CH p,q are complex, but not totally complex.

Canonical groups acting on symmetric spaces

Symmetry group and transvection group

The main point of that section is the following : Theorem 1.2.1 A symmetric space is a homogeneous space.

We will be more precise. Indeed a manifold may be a homogeneous space under the action of a number of different groups. We will give here some "canonical" groups with a transitive action on a given symmetric space.

Definition 1.2.2 The symmetry group SG(M,S) (or for short SG) of a symmetric space (M, S) is the subgroup of the group of diffeomorphisms of M which is generated by the symmetries s x for all x in M .

The transvection group TG(M,S) (or for short TG) of a symmetric space (M, S) is the subgroup of the group of diffeomorphisms of M which is generated by the products of two symmetries s x • s y for all x , y in M .

There will be two possibilties whether T G = SG or T G = SG.

For example, if n is even, the symmetry group of the sphere S n is the special orthogonal group SO(n + 1) and T G = SG. On the other hand, if n is odd, the symmetry group of the sphere S n is the full orthogonal group O(n + 1) while the transvection group is SO(n + 1), so T G = SG here.

In the case T G = SG, then T G is a normal subgroup of SG with index 2. All the symmetries s x belong to SG -T G and SG is a semi-direct product of T G with the subgroup of order 2 generated by one symmetry s a for a choosen point a in M .

As an example, the tranvection group T G of the canonical symmetric space R n is its translation group (also denoted R n ) and its symmetry group SG is such that SG -T G is exactly the set of all symmetries s x for any x in R n .

Proof of the Theorem : We prove that T G acts transitively on M , so M is a homogeneous space under the action of both T G and SG.

(A REVOIR) Given any points x, y in M , we consider the map T x,y : M -→ M defined by

T x,y (z) = S(y, S(x, z)) = s y • s x (z). So T x,y is in T G. If x = y, then T x,x is the identity of M 1.2.

Automorphism group

We introduce another "canonical" group acting transitively on M . Definition 1.2.3 The automorphism group AG(M,S) (or for short AG) of a symmetric space (M, S) is the group of symmetric automorphisms of (M, S).

We recall that α : M -→ M is a symmetric automorphism of (M, S) if it is a diffeomorphism of M and satisfies : S(α(x), α(y)) = α(S(x, y)) ∀x, y ∈ M . Now the above formula may be written :

s α(x) • α = α • s x or equivalently α • s x • α -1 = s α(x) .
This last formula may be translated in words as "the conjugaison by α of the symmetry at x is the symmetry at α(x)".

The axiom (SS3) for symmetries shows that any symmetry s x is a symmetric automorphism, so SG is incuded in AG. As a consequence, AG acts transitively on M .

The automorphism group of the canonical symmetric space R n is the group of affine transformations, so it is much lager than its symmetry group. On the other hand, the automorphism group of the sphere S n is O(n + 1). So AG = SG for an odd dimensional sphere.

In the case where the symmetric space (M, S) is given with some compatible structure as in 1.1.4 above, we may consider other groups related to the struture.

First we have the group of automorphisms of the given structure :

• isometry group for a semi-Riemannian or semi-Kählerian structures;

• symplectic group for a symplectic structure;

• holomorphic group for a complex structure.

And we may consider the group of automorphisms of the structure which are also automorphisms of the symmetric structure. We will denote this group by IG.

Notice that isometries of semi-Riemannian (or semi-Kählerian) structures are always automorphisms of the symmetric structure. But that property is no more true for the symplectic or the complex case. This is already the case for R 2n with its canonical symplectic structure, and for C n with its canonical complex structure.

Notice that with our definition of a compatible structure any symmetry s x is in IG, so we have T G ⊂ SG ⊂ IG ⊂ AG. .

We will show below that

• AG is (in a canonical way) a Lie group which acts smoothly on M ,

• the subgroups T G, SG and IG are Lie subgroups,

• T G and SG are normal subgroups of IG and AG • T G is connected.

Isotropy groups

Let (M, S) be a symmetric space and G be one of the groups T G, SG,IG or AG. More generally we may choose any closed Lie subgroup of AG which contains T G, but we will suppose moreover that the subgroup G is invariant in AG through conjugation by (at least) one symmetry s x . That is obviously the case for SG, IG or AG, but it is also true for T G.. We denote by G σ the closed subgroup of G given by the fixed points of σ, and by G σ 0 the connected component of the identity in G σ .

We see easily that G σ is exactly the subgroup of elements in G which commutes (in AG) with the symmetry s a . .

Now H = {1} × O(n).
In the whole theory of symmetric space, we will not consider that isotropy subgroup as an abstract Lie group, but we will always consider it together with its canonical isotropy representation.

Definition 1.2.7 We denote by V the vector space T a M tangent to M at a. The isotropy representation ρ of M at a is the linear representation of the isotropy subgroup H at a

given by

ρ(α) = T a α ∈ Gl(V ).
Usually, we will consider it for the case of the transvection group T G.

Examples :

• For the canonical affine space R n , we have T G = R n , H = {Id}, V = R n and ρ is the trivial representation on R n .

• For the canonical sphere S n , we have

T G = SO(n + 1), H = SO(n), V = R n and ρ is (isomorphic to) the canonical representation of SO(n) in R n .
• For a (connected) Lie group L, viewed as a symmetric space, we may show that T G is the "adjoint" group, i.e. the quotient L/Z of L by its center Z, and ρ is the adjoint representation of L/Z on the Lie algebra of L.

Remarks : (1) Conversely, we may consider a pair (G, σ), where G is a (connected) Lie group and σ an involutive automorphism of G. then we take any subgroup H with G σ 0 ⊂ H ⊂ G σ . Then we may show that the quotient G/H becomes a symmetric space. Some authors even define symmetric spaces in that way. Notice that if G is a simple group, then G is indeed the corresponding transvection group. In the general case, we may get the same symmetric space with various groups G. That is the main reason for our choice of the "classical" definition.

More classical examples and coverings

With the preceding section, we may get many "classical" symmetric spaces through the involutive automorphisms of the "classical" groups. We describe here some of them from a "geometric" viewpoint.

Example 1 : We consider the vector space E = R n and the set D(p, np; R) of all decomposition of E in a direct sum F 1 F 2 where F 1 is a subspace with dimension p. Notice that such a direct sum is characterized by an involutive automorphism f of E with Ker(f -Id) = F 1 and Ker(f + Id) = F 2 . Then D(p, np; R) is a symmetric space in the following way : we consider Gl + (E) and the involutive automorphism given by the conjugation with one of these f .

Example 2 : We may also take R n with a non-degenerate symmetric or symplectic 2form, and consider the orthogonal direct sums with two non-degenerate subspaces. Here the involutive automorphismf is an isometry.

Example 3 : In the preceding examples, we may replace the field R by the fields C or H. And we may take non-degenerate (complex-)symmetric, (complex-)symplectic of (semi-)hermitian forms on C n , and (semi-)hermitian or skew-hermitian forms on H n .

Example 4 : On R 2n with a symplectic form or a symmetric form with signature (n, n) we may also consider direct sums of two totally isotropic subspaces (with dimension n). We may also consider C 2n with a (complex-)symplectic from, a non-degenerate (complex-)symmetric form or a semi-hermitian form with signature (n, n). And we may consider H 2n with a nondegenerate skew-hermitian form or a semi-hermitian form with signature (n, n).

Example 5 : Inside Gl(n, R), we may consider the subset of symmetric matrices, which contains different connected components according to the signature (p, np). Then each connected component is a symmetric subspace of the group Gl(n, R) with its symmetric structure.

Example 6 : Notice that we get a different symmetric space by considering only Sl(n, R), i.e. symmetric matrices with determinant 1 and a given signature (p, np).

Example 7 : In the preceding examples 5 and 6, we may consider skew-symmetric (or alternate) matrices instead of symmetric ones. We may also replace R by C or H, and consider hermitian or skew-hermitian matrices.

Coverings : Any connected covering of a symmetric space is still a symmetric space. Especially, the universal covering of a symmetric space is a symmetric space.

On the other hand, if the universal covering of a manifold is a symmetric space, the manifold itself is not necessarily a symmetric space, but the local structure is the same as a symmetric space.

Canonical connection

The canonical connection of a symmetric space

A symmetric space is in a canonical way an "affine" space, i.e. it admits a canonical (torsionfree) connection with many properties. Be carefull that it is not necessarily a "flat" affine space, since the connection may have non null curvature. We begin with the precise statement : Theorem 1.3.1 Let (M, S) be a symmetric space. Then there exists on M a unique connection ∇ which is invariant under the symmetries s x for all x in M . Moreover ∇ is torsion free and its curvature R satisfies ∇R = 0. Definition 1.3.2 We call ∇ the canonical connection of the symmetric space (M, S).

We recall that T x s x = -Id T xM . Hence, if a connection ∇ is invariant by s x , then any tensor built from ∇ with an odd number of components is necessarily 0 at x. That shows that the torsion T ∇ and the derivative of the curvature ∇R ∇ are null. On the other hand, the curvature is a (1, 3) tensor, so it is not necessarily null.

The existence of the canonical connection is not so obvious (A COMPLETER).

For further use, we recall some properties of the curvature :

Proposition 1.3.3 Let (M, S) be a symmetric space, and ∇ its canonical connection. Then the curvature R of ∇ satisfies the following 3 properties, ∀ V, W, X, Y, Z ∈ T x M and ∀ x ∈ M : (R1) The curvature is alternative :

R(X, Y )Z = -R(Y, X)Z; (R2) "First Bianchi identity" : R(X, Y )Z + R(Y, Z)X + R(Z, X)Y = 0; (R3) "Ricci identity" : R(V, W )R(X, Y )Z = R(R(V, W )X, Y )Z + R(X, R(V, W )Y )Z + R(X, Y )R(V, W )Z.
Moreover, for any x in M and any α in the isotropy group AH at x (with respect to the automorphism group AG), the curvature R at x is invariant by ρ(α).

Notice that :

• the first property is valid for the curvature of any connection;

• the first Bianchi identity is valid for any torsion-free connection;

• there exists a "second" Bianchi identity on ∇R ∇ , but it is void here;

• in the torsion-free case, the Ricci identity involves also the second derivative ∇∇R ∇ , which is null here.

The last assertion of the theorem follows from : Hence the curvature tensor is invariant by any element in AG.

Geodesics

Since the symmetries s x preserve the connection ∇, they also preserve all objects associated to the connection, in particular the geodesics and the parallel transport along any smooth curve.

First we show that the geodesics are exactly the one-dimensional symmetric subspaces of the given symmetric space.

Proposition 1.3.5 Let (M, S) be a symmetric space.

1. The canonical connection ∇ is geodesically complete.

2. For any geodesic c : R -→ M , we have :

s c(u) (c(t)) = c(2u -t).
3. The geodesics of ∇ are exactly the non-constant symmetric homomorphisms from R to M . Now we relate the transvections to the parallel transport.

Proposition 1.3.6 Let (M, S) be a symmetric space.

1. For any geodesic c : R -→ M , we have :

s c(v) • s c(u) (c(t)) = c(t + 2(v -u)).
2. The transvection tr c,w = s c(t+w) • s c(t) depends only on the geodesic c and w, and not on t.

3. We have : tr c,t • tr c,u = tr c,t+u and tr c,-t = (tr c,t ) -1 . 4. The tangent map T c(t) tr c,w of the transvection tr c,w at the point c(t) of the geodesic c coincides with the parallel transport along c from c(t) to c(t + 2w).

Then we may deduce :

Corollary 1.3.7 A geodesic in a symmetric space (M, S) is either injective or periodic.

If a geodesic is periodic with period w, it is a symmetric homomoprhism of a "circle" S 1 w = R/ wR into M . Now that has consequences for any symmetric subspace.

Corollary 1.3.8 A symmetric subspace of a symmetric space (M, S) is totally geodesic.

Holonomy

Once again, we choose a base point a in the symmetric space (M, S), and we call V the tangent vector space to M at a, i.e. V = T a M .

We recall that the holonomy group H ∇ of the connection ∇ at the point a is the subgroup of the linear group Gl(V ) generated by all the parallel transports along the closed piece-wise smooth curves in M with origin and end in a.

The restricted holonomy subgroup H ∇ is the connected component of the identity in H ∇ .

It also the subgroup of H ∇ generated by the parallel transport along those closed piece-wise smooth curves in M [with origin and end in a] which are homotopic to the constant curve in a. It is known that H ∇ is a Lie subgroup of Gl(V ), but it is not necessarily closed.

We consider now the Lie subalgebra H ∇ of H ∇ 0 in the Lie algebra GL(V ) [which is also the Lie subalgebra corresponding to H ∇ ]. We call it the holonomy subalgebra of (M, S) at a.

For a symmetric space, the (restricted) holonomy is related to the curvature tensor in the following way :

Theorem 1.3.9 Let (M, S) be a symmetric space and a a base point in M .

The holonomy subalgebra of (M, S) at a is exactly the linear subspace of GL(V ) generated by all the endomorphisms R(X, Y ) for all vectors X, Y in V = T a M .

With the relation between parallel transport and transvection we have : Theorem 1.3.10 Let (M, S) be a symmetric space and a a base point in M .

The holonomy subalgebra of (M, S) at a is exactly the Lie subalgebra of the isotropy subgroup T H at a for the action of the transvection group T G on M .

Lie or symmetric triple system

We begin with a definition which will summarize most properties of the curvature at a point in a symmetric space.

Definition 1.3.11 Let V be a vector space. A Lie triple system (or symmetric triple) is a 3-linear map : [., ., .] : V × V × V -→ V with the following properties for any X, Y, Z, U, W in V :

• (LT 1) it is alternate for thefirst two variables, i.e.

[X, Y, Z] = -[Y, X, Z] ;

• (LT 2) it satisfies a Jacobi identity :

[X, Y, Z] + [Y, Z, X] + [Z, X, Y ] = 0 ;
Definition 2.1.1 A (general) representation is a (non void) subset M of the space of endomorphisms End(E) of a finite-dimensional vector space E.

For the case of a representation ρ of a Lie group G or a Lie algebra G we take M = ρ(G) or

M = ρ(G).
Also we may consider as well real, complex or quaternionic vector spaces. The basic technics are completely algebraic in this chapter, so they apply to any field. In order to have both the real and the complex case, we will denote by K the field.

In this chapter, a representation will be a general representation in the above sense.

Definition 2.1.2 Given a representation M ⊂ End(E) of a finite-dimensional vector space E, a linear subspace F is called M -invariant (or for short invariant) if it is invariant by any element f in M .

Notice that the intersection or the sum of two invariant subspaces are obviously invariant subspace. Hence the set of all invariant subspaces of a representation is a lattice (a sublattice of the lattice of all linear subspaces of E).

Definition 2.1.3 Given a representation M ⊂ End(E) of a finite-dimensional vector space E, we denote by L(M) the lattice of M -invariant subspaces of E.

In this chapter, we will try to describe such a lattice. More precisely, we will not try to enumerate all the elements, but instead look for "canonical" elements in L(M) and also for "canonical" maximal flags maid with elements of L(M).

Definition 2.1.4 Given a representation M ⊂ End(E) of a finite-dimensional vector space E, a maximal flag in L(M) is an ordered finite family of M -invariant subspaces :

{0} = F 0 ⊂ F 1 ⊂ F 2 ⊂ • • • ⊂ F m-1 ⊂ F m ⊂ F m+1 = E
such that for all j = 0, • • • , m F j = F j+1 and there is no invariant subspace F = F j orF j+1 such that F j ⊂ F ⊂ F j+1 .

We precise now what we consider as "canonical". In the lattice L(M), there may be an infinite number of subspaces and even continuous families. We will be interested by some subspaces which are "unique" (for some property). We will consider some of them that we get through some precise construction. They will share a common "general" property, that is to be invariant under any automorphism of the full picture.

Definition 2.1.5 Given a representation M ⊂ End(E) of a finite-dimensional vector space E, an automorphism of the representation is a linear automorphism θ of E such that θ

• f ∈ M, ∀f ∈ M . Such a θ is called a commuting automorphism of moreover θ • f = f, ∀f ∈ M .
The set Aut(M ) of automorphisms of the representation M is a closed subgroup of Gl(E), and the set Com(M ) of commuting automorphisms is a closed normal subgroup of Aut(M ). So we will be interested by some of the subspaces in L(M) which are invariant by any element of Aut(M ). Notice that we do not pretend to give here all the Aut(M )-invariant subspaces.

Simple and semi-simple representations

Given a representation M ⊂ End(E) and a subspace F ∈ L(M), we may retrict the action of the elements of M to the subspace F . We get in that way another representation M F ⊂ End(F ), where M F is the set oif restrictions of the elements of M to F .

We call M F ⊂ End(F ) a sub-representation of M . Since it is characterized by the invariant subspace F , we will say for short that "F is a subrepresentation".

We may also consider the quotient space E/F and the set M G/F of endomorphisms of G/F induced by the elements of M . We get another representation M G/F ⊂ End(G/F ).

We call M G/F ⊂ End(G/F ) a quotient representation of M . As above, we will say for short that "G/F is a quotient representation.

Definition 2.1.6 A representation M ⊂ End(E) is called simple if E = {0} and there exists no non-trivial invariant subspace, i.e. L(M) contains only the two "trivial" elements 0 and E.

A representation M ⊂ End(E) is called semi-simple if it is a direct sum of simple repre- sentations.
Notice that a 1-dimensional representation is always simple in the above sense. Some authors exculde that 1-dimensional case of the definition of "simple" representations, but here we will not exclude it.

Proposition 2.1.7 A representation is semi-simple if and only if ∀F ∈ L(M), there exists

(at least one) F ′ ∈ L(M) such that E = F F ′ .
Notice that for a semi-simple representation, its decomposition in a (finite) direct sum is not unique. We may only show that the simple factors are unique up to order and isomorphisms.

An illustration of that fact is the following "trivial" case.

We recall that all the linear suspaces of E are invariant in a representation M if and only if

M is a subset of the space of homotheties of E, i.e. M ⊂ Ht(E) = {λId E ∈ Gl(E); ∀λ ∈ K}.

Such a "trivial" representation is indeed semi-simple and we may choose any decompositions of E in a direct sum of 1-dimensional subspaces.

Definition 2.2.5 For any p = 2, • • • , d we denote :

• R p = (pr 1 ) -1 • • • • • (pr p-1 ) -1 ( R p ), • S p = (pr 1 ) -1 • • • • • (pr p-1 ) -1 ( S p ).
We denote by L ⌋ (M) the lattice of subspaces of E generated by the subspaces R p and S p for p = 1, • • • , d and we call it the first canonical lattice of M .

We recall that a lattice generated by a family of subspaces of E is the set of subspaces that one may get by successive applications of intersections and sums. By convention, that lattice contains {0} and E.

Such a lattice may contains an infinite number of spaces, even if the given family is finte. But our canonical lattice has many properties.

Theorem 2.2.6 The lattice L ⌋ (M) is finite.

More precisely, we may enumerate all the elements of L ⌋ (M).

For any subset

V ⊂ {1, • • • , d}, we denote S V = S v 1 + S v 2 + • • • + S vm where the v j (with 1 v 1 < v 2 < • • • < v m d)
are the elements of V . For the case V = ∅, we set S ∅ = {0}.

Similarly, we set by convention R 0 = E. We have also some inclusions :

• (R p ∩ S p ) ⊂ (R p+1 ∩ S p+1 ) ∀p = 1, • • • , d -1 • R p+1 ⊂ R p ∀p = 1, • • • , d -1 • S(p, V ) ⊂ R(p, V ) • S(p, V ) ⊂ S(p + 1, W ) ∀V ⊂ W • R(p + 1, V ) ⊂ R(p, W ) ∀V ⊂ W
The first three inclusions are always strict, except perhaps the inclusion S(d, V ) ⊂ R(d, V ).

On the other hand, the last two inclusions are not necessarily strict.

More precisely, at each step we may consider the subspace A p = A( E p ) which is an invariant subspace of E p , supplementary of R p ∩ S p into S p . That space is semisimple and may be zero or not. We have A p = {0} if and only if S p ⊂ R p .

With that, we see that the lattice L(M) has at most 2 d+2 -2 elements [if all the A p are non-zero, for all p = 1, • • • , d] and at least 2d + 1 elements [if all the A p are zero].

Maximal flags

We will consider now some "maximal" flags in L(M), i.e. ordered families of subspaces in

L(M) : 0 = F 0 ⊂ F 1 ⊂ F 2 ⊂ • • • ⊂ F m ⊂ F m+1 = E
such that for any j = 1, • • • , d, we have F j = F j+1 and there is no other subspace of L(M) between F j and F j+1 .

There may be many different maximal flags in L(M), but the "length" of those flags [i.e. the number m + 2 of elements of the flag, including {0} and E] depends only on L(M). That length depends on the number t M of those p such that A p = {0}. We will describe some flags in the maximal case where t M = 0, and it will be easy to see which spaces has to be suppressed in order to obtain a "true" maximal flag when t M = 0.

Proposition 2.2.8 The flag :

• F i = S(i, ∅) = R i ∩ S i for0 i d • F d+j = S(d, {1, • • • , j}) = (R d ∩ S d ) + S 1 + • • • + S j for1 j d • F 2d+1 = R(d, {1, • • • , d}) = R d + S 1 + • • • + S d • F 2d+1+k = R(d -k, {1, • • • , d -k}) = R d-k + S 1 + • • • + S d-k for1 i d
is a flag in L(M), which is maximal (with length 3d + 2) when t M = 0.

If t M = 0, we suppress all the F d+j such that A j = {0} and we get a maximal flag in L(M)

with length 3d + 2 -t M .
If all the A j = {0}, i.e. if t M = d + 1, then we suppress all the F d+j forallj = 1, • • • , d + 1

above and the length of the maximal flag is 2d + 1.

For simplicity, we may consider the subflag given by suppressing all these F d+j forallj = 1, • • • , d. It is already sufficient for some applications that we will consider.

Theorem 2.2.9 The flag : For the successive (other) subquotients, which are always nonzero, we have

• JH i = F i for0 i d • JH d+1 = F 2d+1 • JH d+1+k = F 2d+1+k for1 i d

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Semi-Riemannian symmetric spaces 3.1 titre de sous-section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Semi-simple case 4.1 titre de sous-section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Open questions 5.1 titre de sous-section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  SS2) S(x, S(x, y)) = y ∀ x, y ∈ M, -(SS3) S(x, S(y, z)) = S(S(x, y), S(x, z)) ∀ x, y, z ∈ M,

  Definition 1.2.4 We choose a base point a ∈ M . The isotropy subgroup of G at a, denoted H a (or for short H) is the closed subgroup H = {α ∈ G; α(a) = a}. Now the canonical map (associated to a) ev a : G -→ M given by ev a (α) = α(a) induces a canonical identification of M with the quotient G/H. Definition 1.2.5 We denote by σ the involutive automorphism of G induced by the conjugation by the symmetry s a , i.e. σ(α) = s a • α • s a ∀α ∈ G.

  We have G σ 0 ⊂ H ⊂ G σ .Example : We consider the canonical sphere S n and choose a = (1, 0, • • • , 0). Then AG = O(n + 1) and AG σ = O(1) × O(n) has 4 connected components, with AG σ = {1} × SO(n)

Theorem 1. 3 . 4

 34 The automorphism group AG of a symmetric space coincides with the affine group of the canonical connection ∇ [i.e. the group of diffeomorphisms of M which preserves the connection].

  The subspaces S(p, V ) = (R p ∩ S p ) + S V and R(p, V ) = R p + S V , for all p = 0, • • • , d and all subsets V ⊂ {1, • • • , p},are all the elements of the lattice L ⌋ (M). Some special cases are R p = R(p, ∅) and S p = S(p, {p}).

  is a Jordan-Hölder decomposition of the representation M if t M = d.In the case tM = d [i.e. if we have S p ⊂ R p ∀p = 1, • • • , d -1 and R d = S d ,then we have to suppress JH d+1 to obtain a Jordan-Hölder decomposition.Notice that the proposition says that the quotient(F 2d+1 )/(F d ) = (R d + S 1 + • • • + S d )/(R d ∩ S d ) is indeed semisimple. It is isomorphicto the direct sum of all the representations A p for all p = 1, • • • , d + 1.

• (LT 3) it satisfies :

We have immediately :

Proposition 1.3.12 Let (M, S) be a symmetric space, a a base point in M , and V = T a M .

Then the curvature tensor at a : (X, Y, Z) -→ R(X, Y )Z is a Lie triple system.

Notice that we may build what may seem other examples :

Example : Let L be any Lie algebra. Then the map : (X, Y, Z) -→ [[X, Y ], Z] is a Lie triple system.

But those are also symmetric examples with a suitable identification of the tangent space at the unit element of a connected Lie group L with its Lie algebra L. Then L has a symmetric structure and the curvature of the canonical (symmetric) connection is 1 4 [[X, Y ], Z]. Now we consider a Lie triple system (V, [., ., .]) and build a symmetric space with it.

We consider the linear subspace H of G (V ) generated by all the map ev X,Y : Z -→ [X, Y, Z] for all the vectors X, Y in V . With (LT 3), we see that H is a subalgebra of G (V ).

Then we consider the vector space G which is the direct sum H V . We define a bracket [., .] on G in the following way :

Proposition 1. 3.13 The bracket [., .] defined above is a Lie algebra structure on G.

Define the linear map

Then σ is an involutive automorphism of the Lie algebra G.

The "first factor" H = H × {0} is the Lie subalgebra of G formed with the vectors fixed under σ.

We denote by Q the "second factor" {0} × V . Then we have : Then the quotient M = G/H σ is a symmetric space whose transvection group is precisely G.

One may also take any subgroup H such that H σ 0 ⊂ H ⊂ H σ , where H σ 0 is as always the connected component of the unit element in H σ

The corresponding quotients G/H are also symmetric spaces, which are coverings of the preceding ones.

With H = H σ 0 , the quotient G/H σ 0 is even simply connected.

Final Remarks

In the preceding two chapters, we saw that there are many ways to consider symmetrci spaces.

• In A REVOIR { sssec111} , we gave a general "algebraic" definition, where a symmetric space is defined through an "operation", i.e. a map with "algebraic" axioms.

• In A REVOIR { sssec123} , we presented symmetric spaces as special homogeneous spaces

• In A REVOIR { sssec134} , we introduced Lie triple systems, which correspond to the "local" description of a symmetric space near some base point

In the following, we will focuss on the infinitesimal viewpoint. In particular, we will consider the following objects :

• the holonomy representation

• the adjoint representation of the transvection group

• the curvature tensor (at some base point) Indeed, the infinitesimal approch describes symmetric spaces up to covering.

2 Representations and invariant subspaces

Introduction and definitions

Introduction

In this chapter, we will consider "ordinary" representations : i.e. finite dimensional linear representations of Lie groups, but also representations of Lie algebras. We will be interested in the invariant subspaces. The general procedure will be exactly the same for both cases.

So we will consider a general setting which will cover all the cases.

The "socle" of a representation

Given a representation M ⊂ End(E), we consider all the simple subrepresentations F . We see easily that there exists at least one simple subrepresentation in any representation : we take one invariant suspace F with minimal dimension (among the invariant subspaces).

The subspace F for a simple subrepresentation is not necessarily "canonical" (in our sense), so we consider all of them altogether :

Definition 2.1.8 The socle S(M, E) (or for short S(E) or S 1 ) of a representation M ⊂

End(E) is the sum of all subspaces of simple subrepresentations of M ⊂ End(E).

Proposition 2.1.9 The socle S(E) of a representation M ⊂ End(E) is an (non-zero) invariant subspace.

The subrepresentation S(E) is semi-simple.

For any semi-simple subrepresentation of M , the corresponding subspace F is included in

The socle S(E) coincides with E if and only if M is a semi-simple representation.

In other words, S(E) is the invariant subspace of the "maximal" semi-simple subrepresentation of M , i.e. it contains all the other subspaces of semi-simple subrepresentations.

We see easily that S(E) is "canonical" : it is given by a precise construction, and it is obviously invariant by any automorphism of the given representation.

Duality

We will be interested in particular by minkowskian representations. In that case the orthogonal subspace of any invariant subspace of a representation is also invariant if M "preserves" the scalar product, or at least preserves the orthogonality relation between subspaces.

[Be carefull that "preserving the scalar product" has a different meaning for representations of Lie groups or representations of Lie algebras, but "preserving the orthogonality relation"

is the same for a connected Lie subgroup of Gl(E) and its associated Lie algebra.] Also a non-degenerate scalar product gives a linear isomorphism between E and its "dual" space E ⋆ = Hom(E, K). In that case the socle of a representation coincides with the socle of the "contragrediant" representation in the following sense :

We introduce below a definition which will be interesting both for the orthogonal of the socle in the minkowskian case, and for the duality in the general case.

) is semi-simple, or equivalently if the subspace F is the intersection of the subspaces of co-simple representations.

Notice that a F is co-simple (respectively co-semi-simple) for a representation M if and only if its orthogonal F ⊥ si simple (respectively semi-simple) for the contragrediant representation

If M leaves invariant the orthogonality relation for subspaces (with respect to a non degenerate scalar product or a non-degenrate symplectic form), then the orthogonal F ⊥ in the dual space is sent to the usual orthogonal of F in E (so we use the same notation for them).

Minimal radical

Once again, there exists at least one co-simple representation if M is not a simple representation itself. And we may consider all the co-simple representations.

Definition 2.1.11 The minimal radical R(M, E) (or for short R(E) or R 1 ) of a representation M ⊂ End(E) is the intersection of all subspaces of co-simple subrepresentations of

We may have called it the "co-socle" but it is indeed related to various notions of "radical".

Proposition 2.1.12 The minimal radical R(E) of a representation M ⊂ End(E) is an invariant subspace, always different from E.

The subrepresentation R(E) is semi-simple or R(E) = {0}

For any co-semi-simple subrepresentation of M , the corresponding subspace F contains R(E).

The socle R(E) is {0} if and only if M is a semi-simple representation.

In other words, R(E) is the invariant subspace of the "minimal" co-semi-simple subrepresentation of M , i.e. it is included in all the other subspaces of co-semi-simple subrepresentations.

We see easily that R(E) is "canonical" : it is given by a precise construction, and it is obviously invariant by any automorphism of the given representation.

Canonical Jordan-Hölder decomposition of a representation

Jordan-Hölder decompositions

"Jordan-Hölder decomposition" is a very general notion, which is used in many settings. Here we will adapt it to our notion of representation.

Definition 2.2.1 Given a representation M ⊂ End(E), a Jordan-Hölder decomposition of M is a family

of invariant subspaces such that :

We will not consider the general theory of Jordan-Hölder decompositions. We only recall that we may refine such a decomposition such that all quotients are simple, and then the quotients are unique up to order and isomorphisms.

Once again, we will be interested by "canonical" Jordan-Hölder decompositions. It is easy to get two of them by using in an iterative way either the socle or the radical.

But here we want to use both the socle and the radical altogether. Since the following construction seems to be new (at least for the author), we will give details below. In particular, we will detail the various steps of the iteration in the decompositions that we will consider.

We will introduce some more invariant subspaces through iteration.

First step

Let M ⊂ End(E) be a representation. Then the socle S 1 = S(E) and the minimal radical

are invariant subspaces, the subrepresentation S 1 is semi-simple and the quotient representation E/R 1 is also semi-simple.

We consider the intersection S 1 ∩ R 1 and the sum S 1 + R 1 .

Our first step will be the (complete) sublattice L 1 (E) of L(M) given by :

We may extract two "maximal flags" from L 1 (E) :

We have one more property that we will use afterwards Proposition 2.2.2 The subspace R 1 ∩ S 1 is a direct factor in S 1 , i.e. there exists a M -

Notice that A 1 is a semisimple subrepresentation.

But A 1 is not "canonical" : it is not unique and it may happen that no such space is invariant under the automorphisms of M . So A 1 will be usefull to understand the full structure, but we will not keep it in our "canonical lattice.

We have R 1 + S 1 = R 1 ⊕ A 1 , and the quotient representations (R 1 + S 1 )/S 1 and S 1 /R 1 ∩ S 1 are isomorphic to the subrepresentation A 1 .

Definition 2.2.3 A 1 is a direct factor in E, i.e. there exists a M -invariant subspace B 1 such

Once again, B 1 is not canonical.

Iteration

We will now iterate the preceding step. We describe below the second step.

We define

. It is a quotient representation of M . It may be a semisimple representation, in which case we stop the iteration. If not, we may apply the construction above (first step) to it.

We denote R 2 = R( E 2 ) and S 2 = S( E 2 ). We may also pick some A 2 = A( E 2 ).

Then we go to

We describe formally the iteration :

We begin with E 1 = E and we define :

As long as the representation E p is non zero and non semi-simple, then the subspaces R p+1 and S p+1 are non zero and different from E p , so the dimension of the quotient E p+1 = R p+1 /( R p+1 ∩ S p+1 ) is strictly less than the dimension of E p (at least 2 dimension less). Since the dimension of E is finite, that iterative processe ends after a finite number of steps.

We stop it when E p+1 is a semisimple representation.

Definition 2.2.4

The first p such that E p+1 is a semisimple representation is called the depth of the representation M . We will denote it by d.

So for example, depth d = 0 means that M is semisimple.

First canonical lattice

Now the above spaces are subspaces of different quotients. More precisely for p = 1 we have R 1 = R 1 and S 1 = S 1 which are suspaces of E. But for p > 1 we get subspaces in quotients, and not subspaces of E itself. In order to get a lattice of subspaces in E we will "lift" all those spaces to E through the different quotients.

We define the quotients map pr p : R p -→ E p+1 for p = 1, • • • , d. Notice that R p ⊂ E p , so we may compose the pull-back (pr p ) -1 in the definition below :

• For any k = 1, • • • , d, JH d+1+k /JH d+k is isomorphic to ( E d+1-k )/( R d+1-k + S d+1-k )

We may consider that Jordan-Hölder decomposition as the "minimal canonical" one.

Notice there other maximal flags in L(M) if t M = 0. They depend on the places where we had the spaces S p . Here are three of them :

Case 1 :

Case 2 :

Case 3 :


Shub Blum

Smale Model

Jérôme Durand-Lose
email: durand-lose@univ-orleans.fr

Abstract geometrical computation and the linear

Keywords: Abstract geometrical computation, Analog computation, BSS model, Signal machine

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

There is no agreed analog counterpart of the Church-Turing thesis; relating the models is crucial to understand the differences between the various computing capabilities. For example, Bournez et al. related Moore's recursion theory on R [START_REF] Moore | Recursion theory on the reals and continuous-time computation[END_REF], computable analysis [START_REF] Weihrauch | Introduction to computable analysis[END_REF] and the general purpose analog computer [START_REF] Bournez | An analog characterization of elementarily computable functions over the real numbers[END_REF][START_REF] Bournez | The general purpose analog computer and computable analysis are two equivalent paradigms of analog computation[END_REF]. The aim of this paper is to link two analog models of computation. One, abstract geometrical computation deals with regular and automatic drawing on the euclidean plane, while the second, the Blum, Shub and Smale model [START_REF] Blum | Complexity and real computation[END_REF] relies on algebraic computations over R n . Let us note that Bournez [START_REF] Bournez | Some bounds on the computational power of piecewise constant derivative systems[END_REF] already provide some relations between linear BSS and Piecewise Constant Derivative systems. The latter also generate Euclidean drawings.

Abstract geometrical computation (ACG) arises from the common use in cellular automata (CA) literature of Euclidean settings to explain an observed dynamics or to design a CA for a particular purpose. But CA operate in discrete time over discrete space, while Euclidean geometry deals with both continuous time and space. This switch of context is justified by the scaling invariance of CA and comes for our preference and ability for thinking in classical continuous terms rather than in discrete terms (for example just think how recent and complex is discrete geometry compared to the Euclidean one). Abstract geometrical computation works in a continuous setting: discrete signals/particles become dimensionless points; the local function of CA, computing the next state of a cell according to the states of neighbouring cells, is replaced by collision rules: which signals emerges from a collision of signals. Signals and rules define signal machines (SM). This recent model, even restricted to rational numbers, is able to carry out any (discrete) Turing-computation [START_REF] Durand-Lose | Reversible conservative rational abstract geometrical computation is Turing-universal[END_REF]. With continuous time, Zeno paradox arises: not only are accumulations possible, but they can be used to decide recursively enumerable problems by using the black-hole principle [START_REF] Durand-Lose | Abstract geometrical computation for black hole computation (extended abstract)[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 1: Embedding black hole computations with rational numbers[END_REF]. Let us note that if accumulations can be generated at will, they can hardly be foreseen [START_REF] Durand-Lose | Forcasting black holes in abstract geometrical computation is highly unpredictable[END_REF]. In this paper, we are not interested by accumulations and the super-Turing capability that they bring forth in the discrete computability. We are interested on considering AGC as an analog model, thus there is no rational number restriction and accumulations are not encompassed (they are considered as divergent computations).

In the Blum, Shub and Smale model (BSS), machines computes over any ring. Roughly speaking, polynomial functions can be performed on variables as well as test (according to some order) for branching. Linear BSS [START_REF] Meer | A survey on real structural complexity theory[END_REF] is the restriction where it is forbidden to multiply two variables, but it is still allowed to multiply by constants. In the case where the dimension of the input is not bounded or the number of registers needed to compute is not bounded, a shift operator is provided on order to access any register (finitely many registers hold non zero values since only finitely many registers can be accessed in finite time). We prove the equivalence of AGC and linear BSS over R in infinite dimension. For the sake of simplicity, we consider that there is no shift operator but indirect addressing through addresses (natural counters, the term address is used to distinguish from real registers) and that all operations are carried out on an accumulator; this corresponds to the real number unlimited register machine (R-URM) [START_REF] Novak | The real number model in numerical analysis[END_REF] (the arguments for the full BSS translate to the linear case).

To simulate a lin-R-URM with a SM, the value of each register is encoded as the distance between two signals. A lin-R-URM is considered as an assembly language program and we show how to translate each instruction. Since the reader might not be familiar with ACG, the first and simplest constructions are more detailed to provide examples.

To simulate a SM with a lin-R-URM, a configuration is encoded as a finite sequence of, alternatively, signal value and distance to the next one. Although signal machines work with continuous time, the only important discrete dates are when a collision occurs. The simulation goes from a collision date to the next. This is achieved in three steps: compute the next collision time, then update the distances between the signals and finally carry out the collision(s).

Section 2 gives the definition of both models. Section 3 provides the simulation of any lin-R-URM by a SM while Sect. 4 carries the simulation the other way round. Conclusion, remarks and perspective are gathered in Sect. 5.

Definitions

Abstract geometrical computations. In this model, dimensionless objects are moving on the real axis. When a collision occurs they are replaces by others. This is defined by the following machines: Definition 1 A signal machine is defined by (M, S, R) where M (meta-signals) is a finite set, S (speeds) a mapping from M to R and R (collision rules) a partial mapping from the subsets of M of cardinality at least two into subsets of M (speeds must differ in both domain and range).

The elements of M are called meta-signals. Each instance of a meta-signal is a signal. The mapping S assigns speeds to meta-signals. They correspond to the inverse slopes of the segments in space-time diagrams. The collision rules, denoted ρ -→ρ + , define what emerges (ρ + ) from the collision of two or more signals (ρ -). Since R is a mapping, signal machines are deterministic. The extended value set, V , is the union of M and R plus two symbols: one for void, ⊘, and one for an accumulation (which is not addressed here). A configuration, c, is a total mapping from R to V such that the set

{ x ∈ R | c(x) = ⊘ } is finite.
A signal corresponding to a meta-signal µ at a position x, i.e. c(x) = µ, is moving uniformly with constant speed S(µ). A signal must start (resp. end) in the initial (resp. final) configuration or in a collision. These correspond to condition 2 in Def. 2. At a ρ -→ρ + collision signals corresponding to the metasignals in ρ -(resp. ρ + ) must end (resp. start) and no other signal should be present (condition 3).

Definition 2

The space-time diagram issued from an initial configuration c 0 and lasting for T , is a mapping c from [0, T ] to configurations (i.e. a mapping from R ×

[0, T ] to V ) such that, ∀(x, t) ∈ R × [0, T ] : 1. ∀t∈[0, T ], { x ∈ R | c t (x) = ⊘ } is finite, 2. if c t (x)=µ then ∃t i , t f ∈[0, T ] with t i <t<t f or 0=t i =t<t f or t i <t=t f =T s.t.: -∀t ′ ∈ (t i , t f ), c t ′ (x + S(µ)(t ′ -t)) = µ , -t i = 0 or c ti (x i ) ∈ R and µ ∈ (c ti (x i )) + where x i = x + S(µ)(t i -t) , -t f = T or c t f (x f ) ∈ R and µ ∈ (c t f (x f )) -where x f = x + S(µ)(t f -t) ; 3. if c t (x)=ρ -→ρ + ∈ R then ∃ε, 0<ε, ∀t ′ ∈[t-ε, t+ε] ∩ [0, T ], ∀x ′ ∈[x -ε, x + ε], -c t ′ (x ′ ) ∈ ρ -∪ρ + ∪ {⊘}, -∀µ∈M , c t ′ (x ′ )=µ ⇒ µ ∈ ρ -and t ′ < t and x ′ = x + S(µ)(t ′ -t)) , µ ∈ ρ + and t < t ′ and x ′ = x + S(µ)(t ′ -t)) .
On space-time diagrams, the traces of signals represent line segments whose directions are defined by (S(.), 1) (1 is the temporal coordinate). Collisions correspond to the extremities of these segments. In the space-time diagrams, time increases upwards.

A configuration is composed of the identities and positions of all the present signals. Since the origin is not relevant (because of the shift invariance), if is enough to have the identities and the distances between signals from left to right. At any time, there are finitely, although unbounded, many signals.

As a computing device, the input is the initial configuration and the output is the final configuration (e.g. when no collision can happen).

Linear real number unlimited register machines. We do not use the definition of [START_REF] Blum | Complexity and real computation[END_REF] (graph with input, output, computation and branch nodes plus a shift node to deal with infinite dimension). Instead, we use the more assembly language like definition of linear R-URM. Each register holds a real number (with exact precision). Inputs as well as outputs are stored in the registers. The machine can add, multiply (by a constant) and copy values. To cope with infinite dimension, address (natural integers) registers are used for indirect addressing. To simplify our constructions we suppose that all real computations are done with one accumulator (which corresponds to a constant slowdown).

Definition 3 A linear real number unlimited register machine (lin-R-URM) is described by a sequence of instructions among the following ones:

inc A i , dec A i and if 0<A i goto n for the addresses, and

-load R i (load R (i) ), store R i (store R (i) ), add R i (add R (i) )
, mul α, and if 0<X goto n for the registers, where i is a natural integer, α is a constant real number, n is a line number, A i is an address, R i is a register and X is the accumulator. The indirect addressing, R (i) , corresponds to R Ai .

The first register has number 0 to avoid any addressing problem. All the operations are done on the accumulator; thus there is no second argument. There is no mul R i since multiplication is only by constant (otherwise it would not be linear). To simplify, there is no add α, additive constants are supposed to be stored in some registers.

A configuration consists of the line number, the values of the addresses and of the registers. There are finitely many addresses (their number is directly given by the code) and, at any instant, finitely many registers used (but their number is not bounded).

3 Linear R-URM simulation by signal machines

Encoding a configuration

A lin-R-URM configuration is composed of a line number, n, and values for addresses, {A i } i∈I , and registers, {R i } i∈K (I and K are finite initial segments of N). The set I is a constant of the machine while K may be enlarged during the computation. Since there are finitely many line numbers, each one can be identified by a meta-signal. The rest of the configuration is encoded with speed 0 signals ensuring its stability (parallel signals never interact). Since addresses are only used for indicating registers, they are added as markers on the corresponding registers (again the number of addresses is bounded and as many as needed metasignals are available from the start).

Registers. A register is encoded as the distance from a base signal to the pairing val signal. There is no absolute scale since signal machines are scale invariant. Two scale signals whose distance amounts for a scale are provided as depicted on Fig. 1. All registers use the same scale. For the value 0, the superposition of base and val is encoded as a single signal nul. This value is never considered in the rest of the paper; the reader is invited to check that it can be easily covered. The registers are always encoded with the same meta-signals, base and val. They are regularly displayed as depicted on Fig. 2. The signals base are at a distance, say d, one from the next, such that each val is at distance strictly less than d/2 from its corresponding base. Not to tangle one register encoding with another one during the computation, each pair is kept away from the others; if a value becomes too large (which is simple to check since sums and multiplications are done on the accumulator), each distance from val to base is scaled down as well as the scale pair to keep the same values.

The accumulator is encoded like a register and is displayed on the left of the registers. An end marker indicates the right limit of the configuration. It is used in order both to prevent signal from drifting forever on the right and to help enlarging the configuration when needed. The line number is encoded as a signal, line n , of negative speed which is about to hit the right scale and start the next iteration. A complete encoding is given on Fig. 2. Addresses. Since they are used to designate registers, they are encoded by marks on the corresponding base's. This is done by replacing base by any value in {base J } J⊆I (there are finitely many such meta-signals). Each i of I must appear in exactly one base J . If needed, dummy null registers are added to cover all the values of the addresses and all registers directly addressed in the code.

Updating the configuration

The simulation is as follows: line n bounces on scale and changes to whatever signal is used to carry out the instruction at line n. After the instruction is carried out, extra signals are disposed of and one signal with the new line number is sent to the scale. It remains to deal independently with each possible instruction.

Address manipulations. These are: increasing or decreasing by one and branch if non null. Decreasing corresponds to getting to the base J holding i and move the element i to the base on the left except when this register is number 0. To achieve this, signal ----→ n dec 0? i is send to the right. The left subscript n is used to record the line number; it is changed when the operation is performed. The superscript 0? indicates that, as far the computation has gone, the value of the address could still be zero. This signal moves to the right leaving every signal as it is until it reaches the first base J . If i belongs to J then the address is 0 and the signal goes back on the left as line n+1 (lower part of Fig. 3); otherwise it turns to ---→ n dec i and keep going right until it meets the base J such that i belongs to J. It then turns to ← --n dec i and goes on the left; as soon as it reaches a base J , it replaces it by base J∪{i} and turns to line n+1 (upper part of Fig. 3). Increasing A i corresponds to getting to the base J holding i and move i to the next base on the right (lower part of Fig. 4). When there is no more register on the right, end is reached and used to create a new nul register instead of end and to reposition end one step on the right (upper part of Fig. 4). This time, the meta-signals used are:

---→ n inc s i (searching) and --→ n inc i plus two extra signals,

← -

end and -→ end to regenerate end. The last two meta-signals must be three times faster than --→ n inc i in order to ensure the positioning of the new end at the same distance. Branching is very easy, the signal goes on the right, passes the accumulator and get to the first base J . Depending on whether i belongs to J, it comes back as the following line or the branch line number.

time scale accum base {7} base {8} end linen ---→ n in c s 7 ---→ n in c 7 li n e n + 1 -----→ n + 1 in c s 8 ----→ n + 1 in c 8 ← - end -→ end
Registers operations. We first present how to move a value from the accumulator to a given register (load R i is similar). The register can be indicated directly or indirectly. In the first case its number is know directly from the code, it is thus possible to make as many as needed meta-signals to count down from i to 0 (meta-signals are used as a finite unary counter). At each base J crossing, it is decremented until it reaches 0, the designated register is reached. In the second case, a signal is issued that looks for the base J such that i belongs to J (as in address manipulation).

The first column of Fig. 5 presents how the copy starts from the accumulator and is stored on the corresponding register. The second column shows the erasing of the previous value of the register. The first row deals with negative values and the second row with positive ones (handling 0 is trivial). What happens on the target register is the superposition of the right of left column and right column. There is no risk of collision with the new val since ←del and -→ del are below set - and set + . The value stored is exactly the same since set and n sto are parallel as well as the pair of set -(or of set + ). Copy the value Erase the previous value Fig. 5. Various cases to achieve store R6.

To handle multiplication, the scale invariance of AGC is used: if starting from two signals at distance 1, they end up at distance α, then starting from two signals at distance d, they end up at distance αd. There are two cases to consider: α<1 and 1<α (multiplication by 1 is not very interesting). The spacetime diagrams and (pre-computed) speeds are given on Fig. 6. Let us note that multiplication can produce an overflow: a value so large that it might provoke some entanglement between two registers. This is easy to detect: two dummy bounding signals are added around accum, whenever the multiplication crosses any of them an overflow flag is raised (i.e. some signal switches to a given meta-signal). The multiplication is carried out normally, but the val is replaced by over (to distinguish it from any other val). When an overflow occurs, a special subroutine is launched. It scales down by 1/α (for mul α with 1<α) all the registers, the accumulator and the scale. This way, all encoded real values are preserved. All the val and accum remain at their positions, only the left scale, over and all val are moved. The above multiplication scheme is used, this time no overflow can happen.

Addition is not presented, let us just say that it works exactly like load except that val (of the accumulator) is used as origin instead of accum, and deletion of the old val is slightly different. Let us note that addition as an overflow detection like multiplication, in such a case, all is scaled by one half.

Signal machines simulation by linear R-URM

This construction is less detailed since it relies on classical construction on register machines and the reader should have now a rather clear picture of what both models are (and also because of the lack of room). A SM configuration consists of an alternating sequence of meta-signals and distances, starting and ending with a meta-signal. This is straight forwardly be translated into a sequence of registers (meta-signals are encoded by integers starting at 1) followed by 0's.

Updating is done in three steps: first find the delay to the next collision, then update the distances and finally process the collision(s) (there might be synchronous ones). Finding the delay is just to go through the sequence and consider signals two by two: compute the delay before next collision (if any) and store the minimum. To achieve this, it loops through the configuration encoding (this is easy with indirect addressing; the loop stops at the first 0 for a meta-signal) and computes the collision delay. For the latter, there is a formula depending on the distance and speeds of meta-signals but it is not linear. Nevertheless, there are finitely many meta-signals and their speeds are known from the signal machine; each case is linear. It only remains to branch to the correct case with a big switch/if then else.

If no collision happens then the machine halts. Otherwise, it "advances" the time by the given duration (i.e. the distances are updated) then it goes through the configuration again and process each collision, i.e. signals at distance 0. There could be more than two signals involved in a collision (but no more than the number of meta-signals). Again, there are finitely many possible collision rules and they are all given by the signal machine. So to find one, a huge switch has to be provided (there is a case for each rule): first consider how many signals are involved then find the corresponding rule. In-coming signals are replaced by out-going. If their numbers are different, a procedure to compress or enlarge the configuration (exactly like one would do inside any array) is used.

We have proved that signal machines are equivalent to lin-R-URM and infinite dimensional linear R-BSS. Let us note that SM restricted to rational speeds and positions are equivalent to lin-Q-URM with the same constructions. The number of rules of the simulating SM is up bounded by an exponential in the number of lines of the lin-R-URM while the number of line of the simulating lin-R-URM is linear in the numbers of collisions and rules.

Considering the number of collisions as a complexity measure on SM, in each case, the slowdown is of the order of the number of signals/register, i.e. of space. Let us remember that all is constructed with lin-R-URM, not linear BSS and full BSS has also a weak model of complexity [START_REF] Koiran | A weak version of the Blum, Shub & Smale model[END_REF] so we do not go any further on complexity issues here.

Let us note that reversible and conservative signal machines on rational have full Turing-computability. Would reversible and conservative restrictions already be equivalent to linear BSS? In a rational setting, accumulation was used to climb up the arithmetical hierarchy. We believe that in the real setting, they could be used to provide inner multiplication and thus proved that signal machine could simulate the full BSS model. We believe that in such a case BSS would be a strictly less powerful model (unless some limit operator is provided).

Fig. 1 .

 1 Fig. 1. Encoding: scale and positions of val for values -π, -1.5, 0, √ 2 and e.

Fig. 2 .

 2 Fig. 2. Scale, line number, accumulator (-2), registers (-2.1, √ 2, e 2 , π 2 ) and end.

Fig. 3 .

 3 Fig. 3. Example of updating:n: dec A7 n+1: dec A8 .

Fig. 4 .

 4 Fig. 4. Example of updating:n: inc A7 n+1: inc A8 .

Fig. 6 .

 6 Fig. 6. Multiplication scheme.


Tom Besson

Jérôme Durand-Lose

Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata

Keywords: Abstract geometrical computation, Automatic discretization, Cellular automata, Signal machines, Unconventional models of computation

Cellular Automata (CA) operate in discrete time and space whereas Signal Machines (SM) have been developed as a continuous idealization of CA capturing the key concept of signals/particles and collisions. Inside a Euclidean space, dimensionless signals move freely; collisions are instantaneous. Today's issue is the automatic generation of a CA mimicking a given SM. On the one hand, many ad hoc manual conversions exist. On the other hand, some irrational or 4+-speed SM exhibit Zeno-like behaviors / space-time compression or rely on information being locally unbounded, both being incompatible with CA. This article provides a solution to automatically generate an exactly mimicking CA for a restricted class of SM: the ones that uses only three rational speeds, and rational initial positions. In these SM, signals are always contained inside a regular mesh. The discretization brings forth the corresponding discrete mesh. The simulation is valid on any infinite run and preserves the relative position of collisions.

Introduction

Cellular automata (CA) are massively synchronous, uniform and local discrete dynamical systems. Since their introduction by J. Von Neumann in the forties [START_REF] Neumann | Theory of Self-Reproducing Automata[END_REF], a lot of research, from dynamics to algorithmic, have been made. However, a recurrent problem is to create CA for a specific purpose, exhibiting a given behavior. Dedicated CA are crafted by experts, in the same way that programming a computer used to be reserved to specialists. As of now, coding became easier and easier with more and more abstract languages. What would these be such for CA?

The model chosen to serve this purpose is the signal machines (SM). Signal machines, originally thought as an idealization of CA, focus on continuous counterparts of (discrete) signals and collisions in CA. Signals and collisions are indeed key concepts of CA. They provide a lot of insight on the fabric of CA and are the foundation of collision computing [START_REF]Collision based computing[END_REF]. Some of their first usages stand in the generation of prime numbers by Fischer [13] and Goto's solution to the Firing Squad Synchronization Problem (FSSP) [START_REF] Goto | Ōtomaton ni kansuru pazuru [Puzzles on automata[END_REF]. Signals are commonly used: to solve the FSSP [START_REF] Yunès | Simple new algorithms which solve the firing squad synchronization problem: a 7-states 4n-steps solution[END_REF], to compute with rule 110 [START_REF] Cook | Universality in elementary cellular automata[END_REF] or with only four states [START_REF] Ollinger | Four states are enough! Theoret[END_REF], to understand one CA [START_REF] Crutchfield | The evolutionary design of collective computation in cellular automata[END_REF] and so on. In [START_REF] Richard | Systèmes de particules et collisions discrètes dans les automates cellulaires[END_REF] one important question is the automatic positioning of discrete signals. Discrete signals are studied in [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF].

In those references, as in many others, signals are represented by Euclidean lines to explain and reason as can be seen in Fischer's (Fig. 1(a)) and in Goto's (Fig. 1(b)) and Yunès's (Fig. 1(c)). Those constructions are understood in the continuum before being implemented in a discrete setting. Resulting states and transition functions are often left out because they are not used in the proof of constructions, obnoxious to establish, and cumbersome to read.

It is possible to simulate a CA with a SM [START_REF] Durand-Lose | Abstract geometrical computation 4: small Turing universal signal machines[END_REF]. However, the other way round is done only on particular ad hoc cases, often leaving the technical details out. The present paper provides an automatic conversion for a sub-class of signal machines: 3-speed rational. After a normalization phase, the states and the transition function are generated as well as initial configurations. In previous articles, one of the authors researched on the possibilities of the model, from its computational power [START_REF] Durand-Lose | Reversible conservative rational abstract geometrical computation is Turing-universal[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 4: small Turing universal signal machines[END_REF], to its ability to simulate other models (like the BSS model [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF] in [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum, Shub and Smale model[END_REF]).

In signal machines, collisions are discrete steps related by signals: a collision is right before another if a signal generated by the first one ends in the second one. The dynamics of a run of a SM lies entirely in this causal order which can be represented as a Labeled Directed Acyclic Graph (LDAG). Figure 2 provides a LDAG identification of discrete and continuous space-time diagrams. The present paper considers 3-speed rational SM: only three possible speeds are available and speeds as well as positions of signals in initial configurations are rational numbers. The behavior of these machines is limited since signals are trapped inside a regular, periodic-like mesh [START_REF] Becker | Abstract geometrical computation 8: Small machines, accumulations & rationality[END_REF][START_REF] Durand-Lose | Irrationality is needed to compute with signal machines with only three speeds[END_REF] which is essentially discrete (ensuring the discretization).

Time (N) Space (Z) (a) cellular automata Time (R + ) Space (R) (b) signal machine ⊥ ⊥ ⊥ ⊥ ⊥ (c) LDAG representation
The existence of such meshes is not guaranteed with four or more speeds or irrationality. Moreover, if discretization is always locally possible it is not at a large scale nor for an infinite computation. Zeno-like behaviors / space-time compression known as accumulation (which are highly unpredictable [START_REF] Durand-Lose | Forcasting black holes in abstract geometrical computation is highly unpredictable[END_REF]) leads to an infinite number of "objects" in bounded portion of a space-time diagram as depicted in figures 3(a) and 3(b).

An accumulation-less space-time diagram may not be discretizable into a CA as shown the one in Fig. 3(c). On the left, one solid signal is sent after 0, 1, 2, 3. . . dotted ones. This means that any number can be "stored" in-between the solid vertical signals. Discretization would lead to a finite number of cells and a bounded "storage capacity". Outside the case covered in the present article, discretization is only possible on special cases designed for with an extra piece of information (whatever it may be) ensuring the process to work.

The automatic conversion starts with a normalization to get simple speeds. Then meta-signals and collision rules are turned into states and transitions. The translation of configurations follows the same patterns: normalization into integer positions then conversion. Special care is taken so that the discrete signals evolve inside a discrete mesh. The correctness of the process comes from the "preservation" of it and the LDAG inside it.

In Section 2, the SM and CA models are defined as well as SM-meshes and CA-signals. Section 3 focuses on dynamics and simulation as well as normalization of SM. Section 4 describes the discretization: generated states and transitions and initial configurations. Section 5 deals with the correctness of the construction through CA-meshes and LDAG. Section 6 gathers concluding remarks.

Definitions and Properties

A signal machine regroups the definitions of its meta-signals and their dynamics: constant speed outside of collisions and rewriting rules at collisions. Definition 1. A signal machine (SM), A, is a triplet (M, S, R) such that: M is a finite set of meta-signals; S : M →R is the speed function (each meta-signal has a constant speed); and R is a finite set of collision rules written ρ = ρ -→ρ + where ρ -and ρ + are sets of meta-signals of distinct speeds. Each ρ -must have at least two meta-signals. R is deterministic: ρ =ρ implies ρ -=ρ -. If no collision rule is defined for a set of meta-signals, the collision is blank : the same meta-signals are output (ρ + = ρ -).

A (A-)configuration, c, is a mapping from the real line to either a meta-signal, a collision rule or the value indicating that there is nothing there. There are finitely many non-locations.

If there is a signal of speed s at x, then after a duration ∆t its position is x + s•∆t, unless it enters a collision before. At a collision, all incoming signals are immediately replaced according to collision rules by outgoing signals in the following configurations.

A space-time diagram is the collection of consecutive configurations forming a two dimensional picture (time is always elapsing upwards as in Fig. 2). Definition 2. A signal machine is 3-speed rational (3S-Q) if: only three speeds are available for the meta-signals and all speeds are rational numbers as well as any non-position in any initial configuration.

These machines have their signals trapped inside a mesh made of the union of half-lines following the three speeds like the one in Fig. 4. Definition 3. Let p, q and n be positive integers, p and q relatively prime, the (p, q, n)-(SM-)mesh corresponds to the union of the following half-lines of R×R + : -V v : 0 ≤ t and x = v/(p+q) where v ∈ {0, 1, 2, . . . , n(p+q)}, -L l : x ≤ n and x = (l -t)/q where l ∈ N, and -R r : 0 ≤ x and x = (t -r)/p where r ∈ {(-n.p), . . . , -1, 0, 1, . . .}.

0 1 2 3 4
Fig. 4. The (2, 3, 4)-mesh.

Properties 1 ([2, Lem. 1] and [12, Lem. 1]) In the space-time diagram generated from a 3S-Q signal machine with speeds -1 q , 0 and 1 p , p and q relatively prime, on an initial configuration where non-values are in {0, 1, . . . , n}, all the non-positions belong to the (p, q, n)-(SM-)mesh.

In the (p, q, n)-mesh, the (SM-)encounter of coordinates (v, r), e r v , is the intersection of V v , R r and L p+q ; that is v p+q , r+ p p+q v . Encounter e r+1 v directly depends on signals coming from e r+1 v-1 , e r v , and e r-1 v+1 (if they exist) or the initial configuration. The integers v and r are such that 0≤v≤n(p+q) and -n.q≤r. Encounters ordered according to dependencies form a well founded order used for inductive proofs. Definition 4. A (1-dimensional radius-1) cellular automaton (CA) is a triplet (Q, f, #) such that: Q is a finite set of states, f : Q 3 →Q is the local transition function, and # is a special state such that f (#, #, #) = # (the quiescent state). A configuration maps cells to states, i.e. it is an element of Q Z . In the evolution from a configuration c, the site, c t x , is the cell

x (∈ Z) at time-step t (∈ N). It is computed by c t+1 x = f (c t x-1 , c t x , c t x+1 ).
Definition 5. Let W = M ∪ R be the set of meta-signals and collision rules of a signal machine A and Q be the set of states of a CA A. A A-A representation relation R relates W and Q with the intended meaning that λ R q iff λ is represented by q. A state representing a collision rule does not represent anything else. A meta-signal can be represented by many states and a state can represent more than one meta-signal. A state representing nothing corresponds to . -

{ (x + ϕ + (t -a).S(µ) , t) | t ∈ [a, b] }, if 0 < S(µ) (rightward signal), -{ (x -ϕ -(t -a).S(µ) , t) | t ∈ [a, b] }, if S(µ) < 0 (leftward signal), or -{ (x, t) | t ∈ [a, b] }, otherwise (stationary signal). It must represent µ: µ R c t
x for all (x, t) in the µ-CA-signal. Moreover it should be maximal (not extendable as a µ-CA-signal). Its speed is the one of µ.

After the normalization, the non-stationary speeds are of the form ±1/d. Any non-stationary CA-signal has a simple periodic dynamics: it moves one cell on the side every d iterations. Figure 5 provides examples of CA-signals. For rightward signals, the phase ϕ is the distance between the bottom left corner of the cell and the place where the (continuous) signal enters the cell at the bottom. If the signal is leftward; the phase is the distance to the lower right corner of the cell. Phases are illustrated in Fig. 5.

Dynamics, Simulation and Normalization

The causal order of collisions in a space-time diagram can be represented as a Labeled Directed Acyclic Graph (LDAG) as illustrated in Fig. 2(c). If the LDAG's of two runs are identical, then the runs are dynamic-wise identical.

Formally, a A-DAG is a LDAG where edges (resp. vertices) are labeled with elements of M (resp. R ∪ {⊥, }). Bottom (resp. top) leaves are exactly the vertices labeled with ⊥ (resp. ). The label ⊥ is used for signals present in the initial configuration. The label is used for never-ending signals. The LDAG generated from an initial configuration c is denoted c.

A signal machine B simulates a SM A if there exist a conversion function

ζ : C A → C B and a relabeling function ψ : M B ∪R B → M A ∪R A such that: ∀c ∈ C A , c = ψ( ζ(c))
where ψ is canonically extended to LDAG as relabeling each edge and vertex.

Linearly (with positive coefficients) changing the speeds of the meta-signals or the initial positions does not affect the dynamics [START_REF] Durand-Lose | Calculer géométriquement sur le plan -machines à signaux[END_REF]Chap. 5]. Examples of such transformations are provided in Fig. 6.

A 3-speed rational signal machine is normalized with a positive linear operation so that its speeds are -1 q , 0, 1 p with p and q relatively prime. From now on, p and q are always used to refer to these denominators. Similarly, the positions in initial configurations are lifted onto N. Let R be a A-A representation relation, and c a A-configuration. The LDAG c R , as illustrated in Fig. 2(c), is formed as follows. The edges correspond to all the CA-signals in the space-time diagram. The vertices correspond to all the sites that represent a collision rule plus one ⊥ vertex for each CA-signal present in the initial configurations and one vertex for each infinite CA-signal. The edges are in-incident to vertices if the vector from the topmost site of the signal to the vertex site is (-1, 1), (0, 1) or (1, 1) (or an infinite CA-signal and the dedicated vertex). The edges are out-incident to vertices if the vector from the bottom-most site of the signal to the vertex site is (-1, -1), (0, -1) or (1, -1) (or present in the initial configuration and the dedicated ⊥ vertex). The labels correspond to µ for µ-CA-signal and the (unique) collision rule represented by the vertex. If the LDAG is ill formed or non-unique, then c R is undefined.

A cellular automaton A simulates a SM A if there exists a conversion function

ζ : C A → C A and a A-A representation relation R such that: ∀c ∈ C A , c = ζ(c) R
. Dynamic-wise simulation preserves collision interactions but discard anything relevant to positions. Nothing prevents the resulting space-time diagrams to be "bent" (as in [START_REF] Durand-Lose | Reversible space-time simulation of cellular automata[END_REF]) and one might want to preserve the geometry up to some linear operator (like grouping for CA in [START_REF] Mazoyer | Inducing an order on cellular automata by a grouping operation[END_REF]).

To cope with this, we say that a simulation is geometry-preserving if the positions of the CA-collisions can be computed from the one of the corresponding SM-collision with a linear function (plus some integral rounding). The construction presented here is geometry-preserving. The following states and transitions ensure the movement of isolated signals as illustrated in Fig. 5: -for each (rightward) r: states r k with 0≤k<p and ∀k, 0≤k<p Let ρ : {r, z, l} → {l , z , r } be any collision rule (any single r, z, l could be missing and any r , z , l could be missing). When signals enter the same cell, the following phase hypothesis is assumed: non-stationary signals start with phase 0 and stationary ones with phase θ. The continuous signals are considered to locate precisely the collision. They correspond to the lines y = px (rightward), y = -qx+q (leftward) and x = θ (stationary). Resolving this system gives: x= q p+q and y= p•q p+q . The collisions always happen inside a cell because p•q p+q / ∈ Z (since p and q are relatively prime). The delay from getting in the same cell to the actual collision is denoted κ 0 .

Formal Discretization

The states ρ k represent the steps of the collision when two or more signals are inside the same cell: ρ k means (r k :z θ :l k ) when k<κ 0 and (l k :z θ :r k ) when κ 0 <k. Let κ 1 be the last time-step at which all the out-signals are inside the same cell and κ 2 the last time-step at which two out-signals are inside the same cell. Their values are given on Table 1 and illustrated in Fig. 8.

Table 1. Main steps of a collision.

κ0 = p • q p + q
Emitted signals z and r l and z l and r l and z and r κ1 p

-1 q -1 min(p, q) -1 κ2 / / / max(p, q) -1
The signals enter the same cell (under the hypothesis) with

# zθ lq-1 ρ0 , rp-1 zθ # ρ0 , rp-1 # lq-1 ρ0
, or rp-1 zθ lq-1 ρ0

. Then, they are getting closer until the exact collision: ∀k, 0≤k<κ 0 , # ρk # ρk+1 .

If the collision emits no signal, # ρκ 0 # # is added. If the collision emits one signal as illustrated in Fig. 9(a), add: -if

-if ρ + = {r }: ρκ 0 # # r 0 if κ 0 + 1 = p,
ρ + = {l }: # # ρκ 0 l 0 if κ 0 + 1 = q, and # ρκ 0 # l κ 0 +1 otherwise; -if ρ + = {z }: # ρκ 0 # z θ
. If the collision emits more than one signal, it progresses until a signal leaves:

∀k, κ 0 ≤k<κ 1 : # ρk # ρk+1
. If the collision emits two signals as illustrated in Fig. 9(b):

-if ρ + = {z , r }, add: # ρκ 1 # z θ and ρκ 1 # # r 0 ; -if ρ + = {l , z }, add: # # ρκ 1 l 0 and # ρκ 1 # z θ ; -if ρ + = {l , r }, -if q<p (p<q is symmetrical), add: # # ρκ 1 l 0 and # ρκ 1 # r κ 1 +1
.

-if q = p = 1, add:

# # ρκ 1 l 0 and ρκ 1 # # r 0
. If the collision emits three signals, in the case q≤p (the rest is symmetric) as illustrated in Fig. 9(c), the following is added: After the collision, signals move away from each other as illustrated in Fig. 9. This is handled with the transitions:

-# # ρκ 1 l 0 , and ρκ 2 # # r 0 ; -let j = κ 2 -κ 1 -1, l j ρκ 2 # z θ if 0<j<q,
-∀k, 0≤k<p -1:

z θ r k # r k+1 and # z θ r k z θ , -∀k, 0≤k<q -1: # l k z θ l k+1 and l k z θ # z θ
, and -∀k, m, 0≤m<q -1 and 0≤k<p -1: l m z θ r k z θ . A scale is used to ensure that the continuous mesh is correctly discretized: spaces between stationary signals should be integers as well as times of collisions. From the definition of encounter, any (positive) multiple of p + q is enough. Let δ = 3(p + q) be the discretization scale.

Let c be an initial configuration of the discretized SM. The corresponding initial CA-configuration, c 0 , is defined by: ∀i∈Z, c 0 (i)=ψ(c(i/δ)) where ψ( )=#, ψ(z)=z θ for any stationary meta-signal, and ψ(µ)=µ 0 for any other. This ensures the validity of the phase hypothesis at the first round of collisions.

Correctness

In this section, q ≤ p is assumed (the rest follows by symmetry).

A discrete mesh is the discrete counterpart of the continuous meshes as illustrated in Fig. 11. The (δ, p, q, n)-CA-Mesh corresponds to the union of:

-

V v = {3v} × N with v ∈ {0, 1, 2, . . . , n(q + p)}, (3 = δ/(q + p)), -L l = (x, t) 0 ≤ t ∨ x ≤ nδ ∨ x = lδ-t q with l ∈ N, -R r = (x, t) 0 ≤ t ∨ 0 ≤ x ∨ x= t-rδ p with r ∈ {(-n.p), . . . , -1, 0, 1, . . .}.
Each set corresponds to a CA-signal (not necessary issued from the initial configuration). They can overlap for consecutive iterations (as in Figs. 9 and12).

In the (δ=3(p+q), p, q, n)-(CA-)mesh, the CA-encounter of coordinates (v, r), e r v , corresponds to:

δ p+q v + q p+q , rδ + pδ p+q v + pq p+q = (3v, 3pv + rδ + κ 0 )
where the (v, r) coordinates are integers such that 0 ≤ v ≤ n(p+q) and -n.q ≤ r.

The last term in the formula comes from the phases. Figure 12 depicts an entire (CA-)collision. Under the hypothesis that the κ 0 site is located at some e r v , ρ 0 has coordinates (3v, 3pv + rδ) and thus corresponds to the SM-encounter e r v at scale δ. This relates discrete and continuous meshes. With the same hypothesis, the following holds: ρ 0 belongs to V v , R r and L v+r , ρ κ2 belongs to R r , and ρ κ1 belongs to L v+r . This fixes all three CAsignals over a period. The whole collision is in the (δ, p, q, n)-CA-Mesh. As can be seen in Fig. 12, meta-signals extend out of the collision from both ends so that CA-signals directly connect into.

The hypothesis is always satisfied as can be proved by induction: CA-signals in the initial configuration are in the CA-Mesh with the right phases and if CAsignals from the mesh collide, so are the collisions and the resulting CA-signals. Altogether, it proves that: Theorem 1. All the non-quiescent sites of the run from the simulating CAconfiguration are located inside the (δ, p, q, n)-CA-Mesh. Up to scaling, this mesh coincides with the continuous (p, q, n)-SM-mesh.

The A-A representation relation is defined straightforwardly from the construction. Let l, z and r be any leftward, stationary and rightward meta-signals:

∀i, 0 ≤ i < q, l R l i z R z θ ∀i, 0 ≤ i < p, r R r i .

Let ρ = {r, z, l} → {l , z , r } be any rule.

∀i, 0 ≤ i < κ 0 , r R ρ i , z R ρ i , and l R ρ i , ρ R ρ κ0 , ∀i, κ 0 < i ≤ κ 1 , r R ρ i , z R ρ i , and l R ρ i , ∀i, κ 1 < i ≤ κ 2 , r R ρ i and z R ρ i .

A structural induction on the mesh proves that the SM and CA LDAG's are identical, so that: Theorem 2. Any 3-speed rational signal machine can be simulated exactly by a cellular automaton on any infinite run preserving the geometry.

Conclusion

The exact conversion of a 3-speed rational signal machine into a cellular automata has been proved and implemented in Java. The construction relies on preserving a dynamics that is trapped inside a discrete-like mesh. Moreover this is valid on any infinite run and preserves the relative position of collisions.

This result is tight: as soon as either irrationality [START_REF] Becker | Abstract geometrical computation 8: Small machines, accumulations & rationality[END_REF] or four speeds is allowed, Zeno-like phenomena (infinitely many collisions in finite duration) is possible and there is no hope for exact discretization. Even if the techniques presented here can be extended to any number of (rational) speeds, there is no information on how long the discretization remains valid. We believe that testing the validity for a given amount of time is as complex as running the signal machine and its simulation.

The construction presented here naturally extends to any SM computation that is constrained to remain on a mesh (we do not expect such a property to be decidable whether the mesh is provided or not in the general case). One perspective is to either work with some extra piece of information proving the containment into a mesh or the non-existence of an accumulation (which is highly non decidable [START_REF] Durand-Lose | Forcasting black holes in abstract geometrical computation is highly unpredictable[END_REF]) or other problematic behavior. One important step would be to discretize rational signal machines with four or more speeds known to be Turing complete without accumulating as in [START_REF] Durand-Lose | Abstract geometrical computation 4: small Turing universal signal machines[END_REF].

Another perspective is to provide approximation. The quality of the approximation would have to be defined and if possible a bound guaranteed.

Fig. 1 .

 1 Fig. 1. Examples of signal use in designing cellular automata.

Fig. 2 .

 2 Fig. 2. Identification of runs through the labeled DAG representation.

Fig. 3 .

 3 Fig. 3. Non discretizable space-time diagrams.

Definition 6 .

 6 For any meta-signal µ, a µ-CA-signal is defined by (x, a, b, ϕ) where: x∈Z is the base position, a, b ∈ N with a≤b (b can be +∞) are the birth and death dates, and ϕ∈[0, 1) is the phase. It corresponds to the set of sites:

3 Fig. 5 .

 35 Fig. 5. Examples of CA-signals and phases.

5 Fig. 6 .

 56 Fig. 6. Examples of linear transformations.

  -transition f (a, b, c) → d. The quiescent state # is left blank in the pictures. Any non-specified transition results in #. It is understood that r and r are any rightward meta-signals, l and l are any leftward ones and z and z are any stationary ones.

Fig. 7 .

 7 Fig. 7. Examples of A-CA-signals closing on each other.

and # ρκ 0 #Fig. 8 .

 08 Fig.8. Illustration of κ0, κ1 and κ2 with p = 6 and q = 5.

and # ρκ 2 #κ 1

 21 <k<κ 2 : l j ρk # ρk+1 for j = k -κ 1 -1 and j<q and # ρk # ρk+1 for κ 1 + q<k; -for 0≤j<q -1: # l j ρk l j+1for k = j + κ 1 + 1 and k≤κ 2 .

Fig. 9 .

 9 Fig. 9. Collisions and CA-Signals getting away from each other with p=3 and q=2.

Fig. 10 .

 10 Fig. 10. A continuous space-time diagram and the generated CA discretization.

Fig. 11 .

 11 Fig. 11. The (4,1,1,3)-CA-Mesh (δ = 8 = 4(1 + 1)).

Fig. 12 .

 12 Fig. 12. Entire generic collision ρ = {r, z, l} → {l , z , r }.