Daciberg Lima

Gonc ¸alves

John Guaschi
email: john.guaschi@unicaen.fr

Vinicius Casteluber Laass
email: vinicius.laass@ufba.br

The Borsuk-Ulam property for homotopy classes of selfmaps of surfaces of Euler characteristic zero

Keywords: Borsuk-Ulam theorem, homotopy class, braid groups, surfaces

Let M and N be topological spaces such that M admits a free involution τ . A homotopy class β ∈ [M, N ] is said to have the Borsuk-Ulam property with respect to τ if for every representative map f : M → N of β, there exists a point x ∈ M such that f (τ (x)) = f (x). In the case where M is a compact, connected manifold without boundary and N is a compact, connected surface without boundary different from the 2-sphere and the real projective plane, we formulate this property in terms of the pure and full 2-string braid groups of N , and of the fundamental groups of M and the orbit space of M with respect to the action of τ . If M = N is either the 2-torus T 2 or the Klein bottle K 2 , we then solve the problem of deciding which homotopy classes of [M, M ] have the Borsuk-Ulam property. First, if τ : T 2 → T 2 is a free involution that preserves orientation, we show that no homotopy class of [T 2 , T 2 ] has the Borsuk-Ulam property with respect to τ . Secondly, we prove that up to a certain equivalence relation, there is only one class of free involutions τ : T 2 → T 2 that reverse orientation, and for such involutions, we classify the homotopy classes in [T 2 , T 2 ] that have the Borsuk-Ulam property with respect to τ in terms of the induced homomorphism on the fundamental group. Finally, we show that if τ : K 2 → K 2 is a free involution, then a homotopy class of [K 2 , K 2 ] has the Borsuk-Ulam property with respect to τ if and only if the given homotopy class lifts to the torus.

Introduction

In the early twentieth century, St. Ulam conjectured that if f : S n → R n is a continuous map, there exists x ∈ S n such that f (A(x)) = f (x), where A : S n → S n is the antipodal map. The confirmation of this result by K. Borsuk in 1933 [START_REF] Borsuk | Drei Sätze über die n-dimensionale Euklidische Sphäre[END_REF], known as the Borsuk-Ulam theorem, was the beginning of what we now refer to as Borsuk-Ulam type theorems or the Borsuk-Ulam property. More information about the history and some applications of the Borsuk-Ulam theorem may be found in [START_REF] Matoušek | Using the Borsuk-Ulam Theorem[END_REF], for example.

One possible generalisation of the classical Borsuk-Ulam theorem is to substitute S n and R n by other spaces and to replace the antipodal map by a free involution. A natural question is the following: does every continuous map collapse an orbit of the involution? More precisely, given 1 INTRODUCTION 2 topological spaces M and N such that M admits a free involution τ , we say that the triple (M, τ ; N) has the Borsuk-Ulam property if for every continuous map f : M → N, there exists a point x ∈ M such that f (τ (x)) = f (x). Note that in the whole of this paper, we suppose without further comment that our topological spaces are connected.

In [START_REF] Gonçalves | The Borsuk-Ulam theorem for surfaces[END_REF], if M is a compact surface without boundary, D. Gonçalves presented a complete description of the triples (M, τ ; R 2 ) that have the Borsuk-Ulam property. In [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF], if M and N are compact surfaces without boundary, D. Gonçalves and J. Guaschi described the triples (M, τ ; N) that have the Borsuk-Ulam property. If the triple (M, τ ; R 2 ) does not have the Borsuk-Ulam property, by definition, there exists a continuous map f : M → R 2 such that f (τ (x)) = f (x) for all x ∈ M. The fact that there is a single homotopy class of maps from M to R 2 implies that if g : M → R 2 is a continuous map such that g(τ (x)) = g(x) for some x ∈ M, then g is homotopic to f . In other words, g is homotopic to a continuous map that does not collapse the orbits of the involution τ .

The situation is different if the triple (M, τ ; N) does not have the Borsuk-Ulam property and the set [M, N] has cardinality greater than one. Once more, there exists a map f : M → N such that f (τ (x)) = f (x) for all x ∈ M. But if g : M → N is a continuous map such that g(τ (x)) = g(x) for some x ∈ M, we do not know whether g is homotopic to a map that is injective on each orbit of the involution, unless g is homotopic to f . From these observations, we have a natural refinement of the Borsuk-Ulam property, in the following way: we say that a homotopy class β ∈ [M, N] satisfies the Borsuk-Ulam property with respect to τ if for every map f : M → N, where f ∈ β, there exists x ∈ M such that f (τ (x)) = f (x). In conjunction with [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF], these observations give rise to the following Borsuk-Ulam problem: given compact surfaces M and N without boundary and a free involution τ : M → M, classify the elements of the set of homotopy classes [M, N] that have the Borsuk-Ulam property. Before Proposition 9, we recall the definition of an equivalence relation on free involutions. This relation is suitable for the study of this problem.

In this paper, we solve this problem for the cases where M and N coincide and are compact surfaces without boundary of Euler characteristic zero, namely the 2-torus T 2 or the Klein bottle K 2 . We have three main results. First, suppose that M = T 2 . Theorem 1. Let τ : T 2 → T 2 be a free involution that preserves orientation. If β ∈ [T 2 , T 2 ] is a homotopy class then β does not have the Borsuk-Ulam property with respect to τ .

Let us consider free involutions of the torus that reverse orientation. We will show that there is only one equivalence class of such involutions. Let τ 2 : T 2 → T 2 be the orientation-reversing involution that admits the lifting to the plane given by τ 2 (x, y) = (x + 1 2 , 1 -y) for all (x, y) ∈ R 2 (see Section 5).

Theorem 2. Let β ∈ [T 2 , T 2 ] be a homotopy class and let β 1,1 β 1,2 β 2,1 β 2,2 be the integral matrix of the

In Lemma 5, we determine an algebraic criterion to decide whether a given homotopy class contains a representative that is an equivariant map. If N is a compact surface without boundary different from S 2 and RP 2 , in Propositions 6 and 7 we give an algebraic condition to decide whether a homotopy class of maps between M and N has the Borsuk-Ulam property, and in Proposition 10 we show that the set of equivalence classes of free involutions of a compact surface without boundary different from S 2 and RP 2 is in one-to-one correspondence with the equivalence classes of certain short exact sequences. In Section 3 (resp. Section 4), we study the 2-string braid groups of M, where M = T 2 (resp. M = K 2 ). In Theorem 11 (resp. Theorem 16), we give a presentation of P 2 (M), from which we deduce in Theorem 14 (resp. Theorem 23

) that P 2 (M) is isomorphic to F (x, y) ⊕ Z ⊕ Z (cf. [2, Lemma 17
]), where F (x, y) is the free group on the set {x, y} (resp. to a semi-direct product of the form F (u, v) ⋊ θ (Z ⋊ Z)). In Theorem 14 (resp. Theorem 24), we describe the action by conjugation of the element σ ∈ B 2 (M)\P 2 (M) on P 2 (M). In Section 5, in Theorem 25, we show that up to the above-mentioned equivalence relation, there are precisely two classes of free involutions of the torus that correspond to the orientation-preserving and orientation-reversing involutions respectively, and we develop some results and arguments necessary to prove Theorem 1 and 2. Finally, in Section 6, we show in Theorem 33 that up to the above-mentioned equivalence relation, there is just one class of free involutions of the Klein bottle, and we prove Theorem 3.

Preliminaries and Generalities

Let (M, m 1 ) and (N, n 1 ) be pointed manifolds, and suppose that

π i (N, n 1 ) is trivial for all i ≥ 2. Let [M, N] (resp. [M, m 1 ; N, n 1 ]
) denote the set of free (resp. pointed) homotopy class of maps from M to N (resp. from (M, m 1 ) to (N, n 1 )), and let Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) denote the set of homomorphisms between the fundamental groups of M and N. If f, g : (M, m 1 ) → (N, n 1 ) are homotopic pointed maps, denoted by f ≃ g (rel. m 1 ), then the induced homomorphisms f # , g # : π 1 (M, m 1 ) → π 1 (N, n 1 ) on the level of fundamental groups are equal. Given a pointed homotopy class α ∈ [M, m 1 ; N, n 1 ], we may thus associate a homomorphism α # ∈ Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) by choosing a representative map f : (M, m 1 ) → (N, n 1 ) of α, and by taking the induced homomorphism. This gives rise to the following well-defined map:

Γ M,N : [M, m 1 ; N, n 1 ] -→ Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) α = [f ] -→ α # := f # . (1)
It is well known that the map Γ M,N is a bijection [START_REF] Whitehead | Elements of homotopy theory[END_REF]Chapter V,Theorem 4.3]. If f, g : (M, m 1 ) → (N, n 1 ) are pointed maps such that f ≃ g (rel. m 1 ), then omitting the base points, the maps f, g : M → N are homotopic. Given a pointed homotopy class α ∈ [M, m 1 ; N, n 1 ], we may thus associate a free homotopy class α F ∈ [M, N] by choosing a representative map f : (M, m 1 ) → (N, n 1 ) of α, and by taking the free homotopy class α F that represents the map f : M → N, from which we obtain the following well-defined map:

Λ M,N : [M, m 1 ; N, n 1 ] -→ [M, N] α = [f ] -→ α F := [f ], (2)
that is surjective by [START_REF] Vick | Homology Theory: An Introduction to Algebraic Topology[END_REF]Lemma 6.4]. Two homomorphisms h 1 , h 2 ∈ Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) are said to be equivalent, written h 1 ∼ h 2 , if there exists ω ∈ π 1 (N, n 1 ) such that h 1 (υ) = ωh 2 (υ)ω -1 for all υ ∈ π 1 (M, m 1 ). It is straightforward to see that ∼ is an equivalence relation. The associated canonical projection shall be denoted as follows:

Υ M,N : Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) -→ Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) ∼ . (3)
By [START_REF] Whitehead | Elements of homotopy theory[END_REF]Chapter V,Corollary 4.4], there exists a bijective map:

∆ M,N : [M, N] -→ Hom(π 1 (M, m 1 ), π 1 (Y, n 1 )) ∼ such that ∆ M,N • Λ M,N = Υ M,N • Γ M,N . Given an element β ∈ [M, N],
we denote the equivalence class ∆ M,N (β) by β # . We sum up these observations in the following theorem, that we shall often use in this paper.

Theorem 4. If (M, m 1 ) and (N, n 1 ) are pointed manifolds such that π i (N, n 1 ) is trivial for all i ≥ 2, then the following diagram is commutative:

[M, m 1 ; N, n 1 ] Γ M,N / / Λ M,N Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) Υ M,N [M, N] ∆ M,N / / Hom(π 1 (M, m 1 ), π 1 (N, n 1 )) ∼ , (4)
where the horizontal arrows are bijections, and the vertical arrows are surjective.

Let M be a manifold, and let τ : M → M be a free involution. Let M τ denote the corresponding orbit space, which is also a manifold, and let p τ : M → M τ denote the associated double covering. This gives rise to the following short exact sequence:

1 / / π 1 (M, m 1 ) (pτ ) # / / π 1 (M τ , p τ (m 1 )) θτ / / Z 2 / / 1, (5)
that we call the short exact sequence induced by τ , and that we denote by S τ , where we identify

π 1 (M τ , p τ (m 1 )) (p τ ) # (π 1 (M, m 1 ))
with Z 2 = {0, 1}, and θ τ is the natural projection onto the quotient.

We now prove an algebraic criterion to decide whether a pointed homotopy class has an equivariant representative map, which will help in simplifying the proofs of Propositions 6 and 10.

Lemma 5. Let (M, m 1 ) and (N, n 1 ) be pointed manifolds (resp. compact surfaces without boundary) such that π i (N, n 1 ) is trivial for all i ≥ 2, let τ : M → M and τ 1 : N → N be free involutions. Given a pointed homotopy class α ∈ [M, m 1 ; N, n 1 ], the following conditions are equivalent:

1. there exists a representative map (resp. homeomorphism) f : (M, m 1 ) → (N, n 1 ) of α that is (τ, τ 1 )-equivariant, i.e. f (τ (x)) = τ 1 (f (x)) for all x ∈ M.

2. there exists a homomorphism (resp. isomorphism) ψ :

π 1 (M τ , p τ (m 1 )) → π 1 (N τ 1 , p τ 1 (n 1 )
) such that the following diagram is commutative:

π 1 (M, m 1 ) α # / / (pτ ) # π 1 (N, n 1 ) (pτ 1 ) # π 1 (M τ , p τ (m 1 )) ψ / / θτ & & N N N N N N N N N N N N π 1 (N τ 1 , p τ 1 (n 1 )) θτ 1
w w p p p p p p p p p p p p

Z 2 . (6)
Proof. (1 ⇒ 2) Suppose first that f : (M, m 1 ) → (N, n 1 ) is a representative map of α that is (τ, τ 1 )equivariant. Then f {x, τ (x)} = {f (x), τ 1 (f (x))} for all x ∈ M, and hence the map f induces a map of the corresponding orbit spaces, in other words, there exists a map f : (M τ , p τ (m 1 )) → (N τ 1 , p τ 1 (n 1 )) such that the following diagram is commutative:

(M, m 1 ) f / / pτ (N, n 1 ) pτ 1 (M τ , p τ (m 1 )) f / / (N τ 1 , p τ 1 (n 1 )). (7)
Diagram [START_REF] Gonçalves | The Borsuk-Ulam theorem for surfaces[END_REF] implies that (p τ 1 ) # • α # = ψ • (p τ ) # , and also implies that θ τ 1 • ψ = θ τ using standard covering space arguments and the fact that the map f is equivariant. We thus obtain the commutative diagram [START_REF] Fadell | Configuration Spaces[END_REF]. Further, if f is a homeomorphism, then f is too, and so the induced homomorphism

ψ = f # : π 1 (M τ , p τ (m 1 )) → π 1 (N τ 1 , p τ 1 (n 1 )
) is an isomorphism.

(2 ⇒ 1) Suppose that there exists a homomorphism ψ :

π 1 (M τ , p τ (m 1 )) → π 1 (N τ 1 , p τ 1 (n 1 )) for which diagram (6) is commutative. Since p τ 1 : N → N τ 1 is a covering map, the triviality of π i (N, n 1 ) implies that of π i (N τ 1 , p τ 1 (n 1
)) for all i ≥ 2. It follows from Theorem 4 that there exists a map f : (M τ , p τ (m 1 )) → (N τ 1 , p τ 1 (n 1 )) such that f # = ψ, and so by [START_REF] Fadell | Configuration Spaces[END_REF], there exists a map f : (M, m 1 ) → (N, n 1 ) that is a lift of the map f • p τ for the covering p τ 1 , so that we have the commutative diagram [START_REF] Gonçalves | The Borsuk-Ulam theorem for surfaces[END_REF]. Using the short exact sequences induced by τ and τ 1 in the sense of ( 5), one sees that α # = f # and so by Theorem 4, f is a representative map of α. We claim that f is (τ, τ 1 )-equivariant.

To do so, note that for all x ∈ M, we have:

(p τ 1 • f • τ )(x) = (f • p τ • τ )(x) = (f • p τ )(x) = (p τ 1 • f )(x). Hence either f (τ (x)) = f (x), or f (τ (x)) = τ 1 (f (x)). Let ξ : [0, 1] → M be an arc from m 1 to τ (m 1 ). Then the loop γ = p τ • ξ satisfies θ τ ([γ]) = 1
. By [START_REF] Fadell | Configuration Spaces[END_REF] we have:

θ τ 1 ( f • γ ) = θ τ 1 • f # ([γ]) = θ τ ([γ]) = 1,
and since f • ξ is a lift of the loop f • γ by the covering p τ 1 , it is an arc that is not a loop. Therefore

f (m 1 ) = (f • ξ)(0) = (f • ξ)(1) = f (τ (m 1
)), and so f (τ (m 1 )) = τ 1 (f (m 1 )). Using standard covering space arguments and the hypothesis that N is connected, it follows in a straightforward manner that the equality f (τ (x)) = τ 1 (f (x)) holds for all x ∈ M. This proves the claim. Finally, if M and N are compact surfaces without boundary and ψ is an isomorphism, it follows from the classification theorem for surfaces and [18, Theorem 5.6.2] that ψ is induced by a homeomorphism. So without loss of generality, we may take f to be a homeomorphism, and thus f is also a homeomorphism.

Let N be a compact surface without boundary with base point

n 1 ∈ N. Recall that F 2 (N) = {(y 1 , y 2 ) ∈ N × N | y 1 = y 2 } is the 2 nd configuration space of N, and if τ 1 : F 2 (N) → F 2 (N) is the involution defined by τ 1 (x 1 , x 2 ) = (x 2 , x 1 ), then D 2 (N) is the associated orbit space. Let n 2 ∈ N -{n 1 }, and let n = (n 1 , n 2 ) ∈ F 2 (N). By [6, Corollary 2.2], if N is different from S 2 and RP 2 , F 2 (N) and D 2 (N) are manifolds for which π i (F 2 (N), n) and π i (D 2 (N), p τ 1 (n)) are trivial for all i ≥ 2. The groups P 2 (N) = π 1 (F 2 (N), n) and B 2 (N) = π 1 (D 2 (N), p τ 1 (n 1 )
) are the pure and full 2-string braid groups of N respectively, related by the following short exact sequence:

1 / / P 2 (N) ι / / B 2 (N) π / / Z 2 / / 1, (8)
where ι = (p τ 1 ) # and π = θ τ 1 .

The following result generalises [8, Proposition 13] and gives an algebraic criterion in terms of braid groups to decide whether a pointed homotopy class has the Borsuk-Ulam property. Proposition 6. Let (M, m 1 ) be a pointed manifold, let τ : M → M be a free involution, and let (N, n 1 ) be a compact surface without boundary different from S 2 and RP 2 . For a pointed homotopy class α ∈ [M, m 1 ; N, n 1 ], the following conditions are equivalent:

1. α does not have the Borsuk-Ulam property with respect to τ .

there exist homomorphisms

ϕ : π 1 (M, m 1 ) → P 2 (N) and ψ : π 1 (M τ , p τ (m 1 )) → B 2 (N) for
which the following diagram is commutative:

π 1 (M, m 1 ) ϕ / / (pτ ) # α # ) ) P 2 (N) ι (p 1 ) # / / π 1 (N, n 1 ) π 1 (M τ , p τ (m 1 )) ψ / / θτ & & N N N N N N N N N N N N B 2 (N) π { { w w w w w w w w Z 2 , (9)
where

p 1 : F 2 (N) → N is projection onto the first coordinate. Proof. (1 ⇒ 2) If α does not have the Borsuk-Ulam property, there exists a map f : (M, m 1 ) → (N, n 1 ) such that α = [f ] and f (τ (x)) = f (x) for all x ∈ M. Hence the map F : M → F 2 (N) given by F (x) = (f (x), f (τ (x))
) is well defined, (τ, τ 1 )-equivariant and satisfies

p 1 • F = f . Let ϕ : π 1 (M, m 1 ) → P 2 (N) be the homomorphism induced by F . So, we have (p 1 ) # • ϕ = (p 1 ) # • F # = (p 1 • F ) # = f # = α # .
By Theorem 4 and Lemma 5, there exists a homomorphism ψ :

π 1 (M τ , p τ (m 1 )) → B 2 (N) such that ψ • (p τ ) # = ι • ϕ and π • ψ = θ τ . This completes the first part of the proof. (2 ⇒ 1) Suppose that diagram (9) is commutative. Recall that F 2 (N) is a manifold which is a K(π, 1)
. So, Theorem 4 and Lemma 5 imply that the homomorphism ϕ is induced by a (τ, τ 1 )equivariant map

F : M → F 2 (N). Let f, g : M → N be maps such that F (x) = (f (x), g(x)
) for all x ∈ M. Since F is equivariant, we have f (τ (x)) = g(x) = f (x) for all x ∈ M. Again, by [START_REF] Gonçalves | The Borsuk-Ulam theorem for manifolds, with applications to dimensions two and three[END_REF] and Theorem 4 we have α = [f ], and thus α does not have the Borsuk-Ulam property.

The following result shows that to solve the Borsuk-Ulam problem for free homotopy classes, it suffices to solve it for pointed homotopy classes.

Proposition 7. Suppose that the hypotheses of Proposition 6 hold.

1. Let α, α ′ ∈ [M, m 1 ; N, n 1 ]
and suppose that the homomorphisms α # , α ′ # : π 1 (M, m 1 ) → π 1 (N, n 1 ) are equivalent. Then α does not have the Borsuk-Ulam property with respect to τ if and only if α ′ does not have the Borsuk-Ulam property with respect to τ .

Let

β ∈ [M, N]. Then there exists α ∈ [M, m 1 ; N, n 1 ] such that β = α F . Further, β does not
have the Borsuk-Ulam property with respect to τ if and only if α does not have the Borsuk-Ulam property with respect to τ .

Proof. To prove part 1, first note that by the symmetry of the statement with respect to α and α ′ , it suffices to prove one of the implications of the conclusion. So suppose that α does not have the Borsuk-Ulam property with respect to τ . By Proposition 6, there exist homomorphisms ϕ :

π 1 (M, m 1 ) → P 2 (N) and ψ : π 1 (M τ , p τ (m 1 )) → B 2 (N) such that diagram (9) is commutative. Since the homomorphism (p 1 ) # : P 2 (N) → π 1 (N, n 1
) is surjective by [START_REF] Birman | Braids, Links, and Mapping Class Groups[END_REF]Theorem 1.4], and the homomorphisms α # and α ′ # are equivalent via an element of π 1 (N, n 1 ), γ say, there exists b

∈ P 2 (N) such that (p 1 ) # (b) = γ. If ϕ ′ : π 1 (M, m 1 ) → P 2 (N) (resp. ψ ′ : π 1 (M τ , p τ (m 1 )) → B 2 (N)) is the homomorphism given by ϕ ′ (v) = bϕ(v)b -1 for all v ∈ π 1 (M, m 1 ) (resp. ψ ′ (w) = ι(b)ψ(w)ι(b) -1 for all w ∈ π 1 (M τ , p τ (m 1 )
)) where ι is as in [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF], then diagram (9) remains commutative if we replace α # , ϕ and ψ by α ′ # , ϕ ′ and ψ ′ . It follows from Proposition 6 that α ′ does not have the Borsuk-Ulam property with respect to τ .

To prove part 2, if β ∈ [M, N], by Theorem 4 there exists α ∈ [M, m 1 ; N, n 1 ] such that β = α F . Suppose that β does not have the Borsuk-Ulam property with respect to τ . So there exists a map f : M → N such that β = [f ] and f (τ (x)) = f (x) for all x ∈ M. By [START_REF] Vick | Homology Theory: An Introduction to Algebraic Topology[END_REF]Lemma 6.4], there exists a homeomorphism H : N → N that is homotopic to the identity such that H(f (m 1 )) = n 1 . Thus the pointed homotopy class α

′ = [H • f ] ∈ [M, m 1 ; N, n 1 ]
does not have the Borsuk-Ulam property with respect to τ . By equations ( 1) and ( 2) and Theorem 4 it follows that:

Υ M,N (α # ) = (Υ M,N • Γ M,N )(α) = (∆ M,N • Λ M,N )(α) = ∆ M,N (α F ) = ∆ M,N (β) = ∆ M,N ([f ]) = ∆ M,N ([H • f ]) = ∆ M,N ((α ′ ) F ) = (∆ M,N • Λ M,N )(α ′ ) = (Υ M,N • Γ M,N )(α ′ ) = Υ M,N (α ′ # ).
Hence the homomorphisms α # and α ′ # are equivalent by [START_REF] Birman | Braids, Links, and Mapping Class Groups[END_REF]. We conclude from part 1 that α does not have the Borsuk-Ulam property with respect to τ . The converse is obvious.

Remark 8. Taken together, Theorem 4 and Propositions 6 and 7 provide an algebraic criterion to solve the Borsuk-Ulam problem for free homotopy classes.

To end this section, we discuss briefly which involutions of compact surfaces we should consider in order to solve the Borsuk-Ulam problem for homotopy classes. As in [9, Corollary 2.3] if τ 1 , τ 2 : M → M are free involutions, we say that τ 1 and τ 2 are equivalent, written τ 1 ∼ τ 2 , if there exists a (τ 1 , τ 2 )-equivariant homeomorphism H : M → M. Proposition 9. Let M and N be topological spaces, and let

τ 1 , τ 2 : M → M be equivalent free involutions. Let H : M → M be a (τ 1 , τ 2 )-equivariant homeomorphism. Then the map H : [M, N] → [M, N] defined by H([f ]) = [f • H -1 ] is a bijection.
→ N such that [f 1 ] = β and f 1 (τ 1 (x)) = f 1 (x) for all x ∈ M. So the map f 2 = f 1 • H -1 : M → N satisfies [f 2 ] = H(β) and f 2 (τ 2 (x)) = f 2 (x)
for all x ∈ M, in other words H(β) does not have the Borsuk-Ulam property with respect to τ 2 . The converse follows in a similar manner. Now let:

I = {τ : M → M | τ is a free involution, M is a compact surface without boundary, M = S 2 , RP 2 },
and let I = I/ ∼ be the corresponding quotient set. We give an algebraic interpretation of this definition. Let E denote the set of all short exact sequences of the form 1

→ A i → B j → Z 2 → 1,
where A and B are fundamental groups of compact surfaces without boundary different from S 2 and RP 2 . If k ∈ {1, 2}, and S k is an element of E of the form 1

→ A k i k → B k j k → Z 2 → 1,
we say that S 1 and S 2 are equivalent, written S 1 ≈ S 2 , if there exist isomorphisms ϕ : A 1 → A 2 and ψ : B 1 → B 2 such that the following diagram is commutative:

1 / / A 1 i 1 / / ϕ B 1 j 1 / / ψ Z 2 / / Id 1 1 / / A 2 i 2 / / B 2 j 2 / / Z 2 / / 1,
where Id denotes the identity. It is easy to see that ≈ is a equivalence relation on E. Let E = E/≈ be the corresponding quotient set. Then we have the following proposition.

Proposition 10. The map I -→ E given by ( 5) that to a free involution τ associates the short exact sequence S τ gives rise to a bijection Σ : I → E.

Proof. By Lemma 5, Σ is well defined and injective. It remains to show that Σ is surjective. Let S ∈ E be a short exact sequence of the form 1

→ A i → B j → Z 2 → 1, let M
and N be compact surfaces without boundary such that A = π 1 (M) and B = π 1 (N), and let N be the double covering of N determined by the subgroup A ⊂ B. Since M and N have isomorphic fundamental groups, there exists a homeomorphism h : M → N that realises a given isomorphism between the fundamental groups of M and N . Then the composition of h with the double covering N → N is a double covering of N that determines a free involution τ on M, and Σ[τ ] = [S] as required.

The braid groups of the torus

The aim of this section is to prove Theorem 14 that provides an explicit isomorphism between P 2 (T 2 ) and F (x, y) ⊕ Z ⊕ Z and describes the action of σ on P 2 (T 2 ).

If G is a group and a, b ∈ G, let [a, b] = aba -1 b -1 denote their commutator. The following presentation of P 2 (T 2 ) may be found in [5, Section 4].

Theorem 11. The following is a presentation of P 2 (T 2 ):

generators: ρ 1,1 , ρ 1,2 , ρ 2,1 , ρ 2,2 , B. relations: (i) [ρ 1,1 , ρ -1 1,2 ] = [ρ 2,1 , ρ -1 2,2 ] = B. (ii) ρ 2,k ρ 1,k ρ -1 2,k = Bρ 1,k B -1 and ρ -1 2,k ρ 1,k ρ 2,k = ρ 1,k [B -1 , ρ 1,k ] for all k ∈ {1, 2}. (iii) ρ 2,1 ρ 1,2 ρ -1 2,1 = Bρ 1,2 [ρ -1 1,1 , B] and ρ -1 2,1 ρ 1,2 ρ 2,1 = B -1 [B, ρ 1,1 ]ρ 1,2 [B -1 , ρ 1,1 ]. (iv) ρ 2,2 ρ 1,1 ρ -1 2,2 = ρ 1,1 B -1 and ρ -1 2,2 ρ 1,1 ρ 2,2 = ρ 1,1 B[B -1 , ρ 1,2 ].
Note that B may be removed from the list of generators using relation (i). In order to obtain a presentation of P 2 (T 2 ) that is more suitable for our purposes, we shall use the following lemma.

Lemma 12. With respect to the presentation of P 2 (T 2 ) given in Theorem 11, the following relations hold:

(v) ρ 2,k Bρ -1 2,k = Bρ -1 1,k Bρ 1,k B -1 for all k ∈ {1, 2}. (vi) ρ 1,k B -1 ρ 2,k ρ i,j ρ -1 2,k Bρ -1 1,k = ρ i,j for all i, j, k ∈ {1, 2}. Observe that relation (vi) implies that for k ∈ {1, 2}, ρ 1,k B -1 ρ 2,k belongs to the centre of P 2 (T 2 ).
Proof of Lemma 12. We have:

ρ 2,1 Bρ -1 2,1 (i) = [ρ 2,1 ρ 1,1 ρ -1 2,1 , ρ 2,1 ρ -1 1,2 ρ -1 2,1 ] (ii),(iii) = ρ 1,1 ρ -1 1,2 ρ -1 1,1 ρ 1,2 ρ -1 1,1 Bρ 1,1 B -1 (i) = Bρ -1 1,1 Bρ 1,1 B -1 , and ρ 2,2 Bρ -1 2,2 (i) = [ρ 2,2 ρ 1,1 ρ -1 2,2 , ρ 2,2 ρ -1 1,2 ρ -1 2,2 ] (ii),(iv) = ρ 1,1 ρ -1 1,2 ρ -1 1,1 Bρ 1,2 B -1 (i) = Bρ -1 1,2 Bρ 1,2 B -1 ,
which proves (v). To prove (vi), first let i = 1. If j = k, the relation follows directly from (ii). If j = k, we have:

ρ 1,2 B -1 ρ 2,2 ρ 1,1 ρ -1 2,2 Bρ -1 1,2 (iv) = ρ 1,2 B -1 ρ 1,1 ρ -1 1,2 (i)
= ρ 1,1 and

ρ 1,1 B -1 ρ 2,1 ρ 1,2 ρ -1 2,1 Bρ -1 1,1 (iii) = ρ 1,1 ρ 1,2 ρ -1 1,1 B (i) = ρ 1,2 .
Suppose that i = 2. If j = k then:

ρ 1,k B -1 ρ 2,k ρ 2,k ρ -1 2,k Bρ -1 1,k = ρ 1,k B -1 ρ 2,k Bρ -1 1,k ρ -1 2,k ρ 2,k (ii),(v) = ρ 2,k .
Now suppose that j = 1 and k = 2. By (iii) and (v), we have

ρ 2,1 Bρ -1 1,2 ρ -1 2,1 = Bρ -1 1,2 B -1
, and thus

ρ 1,2 B -1 ρ 2,2 ρ 2,1 ρ -1 2,2 Bρ -1 1,2 = ρ 1,2 B -1 ρ 2,2 ρ 2,1 ρ -1 2,2 ρ -1 2,1 Bρ -1 1,2 B -1 ρ 2,1 (i) = ρ 1,2 B -1 ρ 2,2 Bρ -1 2,2 Bρ -1 1,2 B -1 ρ 2,1 (v) = ρ 2,1 .
Finally, for j = 2 and k = 1, we have:

ρ 1,1 B -1 ρ 2,1 ρ 2,2 ρ -1 2,1 Bρ -1 1,1 (i) =ρ 1,1 B -1 ρ 2,2 ρ -1 1,1 (iv) = ρ 2,2 .
By [6, Theorem 1], the projection p 1 : F 2 (T 2 ) → T 2 onto the first coordinate is a locally-trivial fibre space whose fibre may be identified with T 2 -{ * }. This gives rise to the following short exact sequence:

1 / / π 1 (T 2 -{ * }) / / P 2 (T 2 ) (p 1 ) # / / π 1 (T 2 ) / / 1. ( 10
)
Remark 13. By [5, Figure 4.1], π 1 (T 2 -{ * }) is a free group generated by ρ 2,1 and ρ 2,2 , which we denote by F (ρ 2,1 , ρ 2,2 ). The elements (p 1 ) # (ρ 1,1 ) and (p 1 ) # (ρ 1,2 ) generate the free Abelian group π 1 (T 2 ) that we shall identify with Z ⊕ Z under the correspondence of (p 1 ) # (ρ 1,1 ) (resp. (p 1 ) # (ρ 1,2 )) with (1, 0) (resp. (0, 1)).

By Lemma 12(vi), the map ϕ : π 1 (T 2 ) → P 2 (T 2 ) defined on the generators of π 1 (T 2 ) by ϕ(1, 0) = ρ 1,1 B -1 ρ 2,1 and ϕ(0, 1) = ρ 1,2 B -1 ρ 2,2 is a homomorphism that may be seen to be a section for (p 1 ) # using Remark 13. By the short exact sequence [START_REF] Gonçalves | Wecken type problems for self-maps of the Klein bottle[END_REF], we conclude that:

P 2 (T 2 ) ∼ = F (ρ 2,1 , ρ 2,2 ) ⊕ Z[ρ 1,1 B -1 ρ 2,1 ] ⊕ Z[ρ 1,2 B -1 ρ 2,2 ]. (11)
In particular, the centre of

P 2 (T 2 ) is generated by ρ 1,1 B -1 ρ 2,1 and ρ 1,2 B -1 ρ 2,2 .
Let σ be the standard generator of B 2 (T 2 ) that swaps the two base points, so B = σ 2 . By [8, Section 5], the automorphism l σ : P 2 (T 2 ) → P 2 (T 2 ) given by conjugation by σ satisfies l σ (ρ

1,k ) = ρ 2,k and l σ (ρ 2,k ) = Bρ 1,k B -1
for all k ∈ {1, 2}. Using the decomposition given in [START_REF] Laass | A propriedade de Borsuk-Ulam para funções entre superfícies[END_REF], for all k ∈ {1, 2}, we have

l σ (ρ 2,k ) = Bρ -1 2,k (ρ 1,k B -1 ρ 2,k ) and l σ (ρ 1,k B -1 ρ 2,k ) = ρ 1,k B -1 ρ 2,k
. By [START_REF] Laass | A propriedade de Borsuk-Ulam para funções entre superfícies[END_REF] and the fact that B 2 (T 2 ) is generated by {σ, ρ 1,1 , ρ 1,2 , ρ 2,1 , ρ 2,2 }, this implies that the centre of B 2 (T 2 ) is generated by ρ 1,1 B -1 ρ 2,1 and ρ 1,2 B -1 ρ 2,2 . Writing x = ρ 2,1 and y = ρ 2,2 and identifying

Z[ρ 1,1 B -1 ρ 2,1 ] ⊕ Z[ρ 1,2 B -1 ρ 2,2 ] with Z ⊕ Z,
we may summarise the main algebraic properties of P 2 (T 2 ) as follows.

Theorem 14. Up to isomorphism, P 2 (T 2 ) may be written in the form F (x, y) ⊕ Z ⊕ Z, and relative to this identification: (c) the images of the generators of P 2 (T 2 ) under the homomorphism l σ : P 2 (T 2 ) → P 2 (T 2 ) given by conjugating by σ are as follows:

l σ (x, 0, 0) = (Bx -1 , 1, 0), l σ (y, 0, 0) = (By -1 , 0, 1), l σ (½, 1, 0) = (½, 1, 0) and l σ (½, 0, 1) = (½, 0, 1),

where ½ denotes the trivial element of F (x, y).

The following equation will be used for various computations and arguments in Section 5. Let | • | x , | • | y : F (x, y) → Z be the exponent sum homomorphisms that are defined on the generators of F (x, y) by |x| x = |y| y = 1 and |x| y = |y| x = 0. By Theorem 14, we have l σ (x, 0, 0) = ((x -1 y)x -1 (x -1 y) -1 , 1, 0) and l σ (y, 0, 0) = ((x -1 y)y -1 (x -1 y) -1 , 0, 1). From these, if w = w(x, y) ∈ F (x, y), we obtain the following equality:

l σ (w(x, y), 0, 0) = xy -1 w(x -1 , y -1 )yx -1 , |w| x , |w| y . ( 12
)
4 The braid groups of the Klein bottle

In this section, we give a presentation of P 2 (K 2 ) in Theorem 16, and we give an explicit description of the semi-direct product structure of this group in Theorem 23. We then determine the action by conjugation of σ on the elements of P 2 (K 2 ) in Theorem 24 that will be used in later sections.

If G is a group and a, b ∈ G, we define their anti-commutator by [a, b] ′ = abab -1 . By [1, Theorem A.3], B 2 (K 2 ) has the following presentation.

Theorem 15. The following is a presentation of B 2 (K 2 ): generators: a 1 , a 2 , σ. relations:

(R2) σ -1 a r σ -1 a r = a r σ -1 a r σ, for all r ∈ {1, 2}. (R3) σ -1 a 1 σa 2 = a 2 σ -1 a 1 σ. (TR) a 2 1 a 2 2 = σ 2 .
In order to exhibit a presentation of P 2 (K 2 ), we apply the Reidemeister-Schreier rewriting process that is described in detail in [12, Chapter 2, Theorem 2.8] and briefly in [14, Appendix I, Theorem 6.3]. We use the notation of [START_REF] Murasugi | A Study of Braids[END_REF].

Theorem 16. The following is a presentation of P 2 (K 2 ):

generators: a 1 , a 2 , b 1 , b 2 , B. relations: (i) b r a r = Ba r B -1 b r B, for all r ∈ {1, 2}. (ii) [a r , b r ] = a r Ba -1
r , for all r ∈ {1, 2}.

(iii) b 1 Ba 2 B -1 = Ba 2 B -1 b 1 . (iv) [a 1 , b 2 ] = 1. (v) a 2 1 a 2 2 = b 2 1 b 2 2 = B.
The inclusion ι :

P 2 (K 2 ) → B 2 (K 2
) is defined on the generators of P 2 (K 2 ) by ι(a r ) = a r , ι(b r ) = σa r σ -1 , r ∈ {1, 2}, and ι(B) = σ 2 .

Proof. First note that {½, σ} is a Schreier system of P 2 (K 2 ). Let us compute the generators of P 2 (K 2 ). For r ∈ {1, 2}, we have:

̺(½, a r ) = ½a r ½a r -1 = a r . ̺(½, σ) = ½σ½σ -1 = ½. ̺(σ, a r ) = σa r σa r -1 = σa r σ -1 = b r . ̺(σ, σ) = σσσσ -1 = σ 2 = B.
To determine the relations, we apply the Reidemeister-Schreier rewriting process. We leave the straightforward calculations to the reader.

Recall that the projection p 1 : F 2 (K 2 ) → K 2 onto the first coordinate is a locally-trivial fibre space whose fibre may be identified with K 2 -{ * } [6, Theorem 1], from which we obtain the following short exact sequence:

1 / / π 1 (K 2 -{ * }) / / P 2 (K 2 ) (p 1 ) # / / π 1 (K 2 ) / / 1. (13)
Using [1, Figure 10] and the presentation of P 2 (K 2 ) given by Theorem 16, we conclude that π 1 (K 2 -{ * }) is the free group generated by {b 1 , b 2 }, which we denote by

F (b 1 , b 2 ). For k ∈ {1, 2}, let a k = (p 1 ) # (a k )
. By Theorem 16 and the short exact sequence (13), we have

π 1 (K 2 ) = a 1 , a 2 | a 2 1 a 2 2 = ½ . Let u 1 = a 1 a 2 and v 1 = a -1 2 . Then a 1 = u 1 v 1 and a 2 = v -1
1 . This choice of elements yields another classical presentation of the fundamental group of the Klein bottle of the form π

1 (K 2 ) = u 1 , v 1 | [u 1 , v 1 ] ′ = ½ = Z[u 1 ] ⋊ Z[v 1 ].
Remark 17. As a set, the group Z⋊Z is the Cartesian product of Z with itself. The group operation is given by (r 1 , s 1 )(r 2 , s 2 ) = (r 1 + (-1) s 1 r 2 , s 1 + s 2 ), the identity element is (0, 0), the inverse of an element (r, s) is ((-1) s+1 r, -s), and there is a canonical isomorphism between Z[u 1 ] ⋊ Z[v 1 ] and Z ⋊ Z. In the rest of this paper, we identify π 1 (K 2 ) with Z ⋊ Z in this way.

Since K 2 admits a non-vanishing vector field, the projection p 1 admits a geometric section [START_REF] Fadell | Configuration Spaces[END_REF], and this implies that the short exact sequence (13) splits. In the following proposition, we give an explicit algebraic section.

Proposition 18. The correspondences ϕ(1, 0) = b 1 a 1 b 2 a 2 and ϕ(0, 1) = a -1 2 b -1 2 define a homomorph- ism ϕ : π 1 (K 2 ) → P 2 (K 2 ) that is a section for the homomorphism (p 1 ) # : P 2 (K 2 ) → π 1 (K 2 ).
Proof. We have that:

[ϕ(1, 0), ϕ(0, 1)] ′ = b 1 a 1 b 1 a 1 b 2 a 2 b 2 a 2 = [b 1 , a 1 ]a 1 b 2 1 a 1 b 2 a 2 [b 2 , a 2 ]a 2 b 2 (ii) = a 1 B -1 b 2 1 a 1 b 2 a 2 2 B -1 b 2 (v) = a 1 b -2 2 a 1 b 2 a -2 1 b 2 (iv) = ½.
where we make use of the relations given in Theorem 16. So by Remark 17, ϕ is a well-defined homomorphism. Using the relations a 1 = u 1 v 1 and a 2 = v -1 1 , it follows that ϕ is a section for (p 1 ) # . Proposition 18 and Remark 19 imply that

P 2 (K 2 ) ∼ = F (b 1 , b 2 ) ⋊ θ (Z ⋊ Z).
In the following result, we describe the action by conjugation of a r on the elements b k and B for all r, k ∈ {1, 2}.

Lemma 20. In P 2 (K 2 ), the following relations hold:

(1) a 1 b 1 a -1 1 = b -1 1 b -2 2 .
(

) a 1 b 2 a -1 1 = b 2 . 2
(

) a 1 Ba -1 1 = b -1 1 B -1 b 1 . (4) a 2 b 1 a -1 2 = b -1 2 B -1 b -1 2 b 1 b 2 Bb 2 . 3
(

) a 2 b 2 a -1 2 = b -1 2 B -1 b 2 2 . ( 5
) a 2 Ba -1 2 = b -1 2 B -1 b 2 . 6
Proof. First, we have:

(a 1 b 1 a 1 ) 2 (v) = a 1 Bb -2 2 a -1 1 (iv) = a 1 Ba -1 1 b -2 2 (ii) = (a 1 b 1 a -1 1 )b -1 1 b -2 2 .
This equality implies relation [START_REF] Bellingeri | On presentations of surface braid groups[END_REF]. Relation (2) follows directly from (iv). Further:

a 1 Ba -1 1 (v) = a 1 b 2 1 b 2 2 a -1 1 (iv) = (a 1 b 1 a -1 1 ) 2 b 2 2 (1) = b -1 1 b -2 2 b -1 1 (v) = b -1 1 B -1 b 1 ,
which proves relation [START_REF] Birman | Braids, Links, and Mapping Class Groups[END_REF]. It remains to prove relations (4), ( 5) and ( 6). We have:

b 1 Ba 2 B -1 a -1 2 (iii) = Ba 2 B -1 b 1 a -1 2 = B(a 2 B -1 a -1 2 )(a 2 b 1 a -1 2 ), which implies that a 2 b 1 a -1 2 = a 2 Ba -1 2 B -1 a 2 B -1 a -1 2 , (14)
θ(0, n) :

     u -→ B -δn u (-1) n B δn v -→ vB δn B -→ B (-1) n where δ n = 0 if n is even 1 if n is odd.
Proof. By relation (v) of Theorem 16, we have ϕ(0, 1) = B -1 a 2 1 a 2 b -1 2 . Using this equality, the idea of the proof is similar to that of Lemma 21, and we leave the calculations to the reader.

We are now able to describe the homomorphism θ.

Theorem 23. The homomorphism θ : Z ⋊ Z → Aut(F (u, v)) is defined by: θ(m, n) :

     u -→ B m-δn u (-1) n B -m+δn v -→ B m vu -2m B -m+δn B -→ B (-1) n , where B = [u, v] ′ and δ n = 0 if n is even 1 if n is odd.
With the notation of Remark 19, the isomorphisms

F (u, v) ⋊ θ (Z ⋊ Z) λ / / P 2 (K 2 ) γ o o
are given by: λ :

               (u; 0, 0) -→ b 1 b 2 (v; 0, 0) -→ b -1 2 (B; 0, 0) -→ B (½; 1, 0) -→ b 1 a 1 b 2 a 2 (½; 0, 1) -→ b 2 a 2 γ :                a 1 -→ (v -1 u -1 ; 1, 1) a 2 -→ (v; 0, -1) b 1 -→ (uv; 0, 0) b 2 -→ (v -1 ; 0, 0) B -→ (B; 0, 0).
Up these isomorphisms and the identification given by Remark 17, the homomorphism (p 1 ) # :

P 2 (K 2 ) → π 1 (K 2 )
is the projection onto the second coordinate, in other words, (p 1 ) # (w; m, n) = (m, n).

Proof. For all (m, n) ∈ Z ⋊ Z, we have θ(m, n) = θ(m, 0) • θ(0, n). The first part of the statement follows by combining Lemmas 21 and 22. Let us prove the second part. First, λ(u; 0, 0

) = u = b 1 b 2 , λ(v; 0, 0) = v = b -1 2 , λ(B; 0, 0) = B, λ(½; 1, 0) = ½ϕ(1, 0) = b 1 a 1 b 2 a 2 and λ(½; 0, 1) = ½ϕ(0, 1) = a -1 2 b -1 2 .
On the other hand:

γ(a 1 ) = (a 1 ϕ( a 1 ) -1 ; a 1 ) = (a 1 (ϕ(1, 0)ϕ(0, 1)) -1 ; 1, 1) = (b -1 1 ; 1, 1) = (v -1 u -1 ; 1, 1), γ(a 2 ) = (a 2 ϕ( a 2 ) -1 ; a 2 ) = (a 2 ϕ(0, 1); 0, -1) = (b -1 2 ; 0, -1) = (v; 0, -1),
γ(b 1 ) = (uv; 0, 0) and γ(b 2 ) = (v -1 ; 0, 0). From the isomorphism λ and Remark 17, we see that (p 1 ) # (u; 0, 0) = (p 1 ) # (v; 0, 0) = (0, 0), (p 1 ) # (½; 1, 0) = (1, 0) and (p 1 ) # (½; 0, 1) = (0, 1) as required.

Let c σ : P 2 (K 2 ) → P 2 (K 2 ) be the automorphism of P 2 (T ) given by conjugation by σ. By Theorem 16, we have

c σ (B) = B, c σ (a i ) = b i and c σ (b j ) = Ba j B -1 for all i, j ∈ {1, 2}. Let l σ : F (u, v) ⋊ θ (Z ⋊ Z) → F (u, v) ⋊ θ (Z ⋊ Z) be defined by the composition l σ = γ • c σ • λ.
To end this section, we give an explicit description of l σ on a set of generators.

Theorem 24. For all r, s, m, n ∈ Z, we have:

(1) l σ (u r ; 0, 0) = ((Bu -1 ) -r B -r ; r, 0).

(2) l σ (v s ; 0, 0) = ((uv) -s (uB) δs ; 0, s).

(3) l σ (B; 0, 0) = (B; 0, 0).

(4) l σ (½; m, 0) = (½; m, 0).

(5) l σ (½; 0, n) = (B δn ; 0, n).

Proof. Equation (3) follows easily from Theorem 23. Let us prove equation [START_REF] Bellingeri | On presentations of surface braid groups[END_REF]. For r = 0, the result is clear. If r = 1, we have:

l σ (u; 0, 0) = (γ • c σ )(b 1 b 2 ) = γ(Ba 1 a 2 B -1 ) = (B; 0, 0)(v -1 u -1 ; 1, 1)(v; 0, -1)(B -1 , 0, 0) = (Bv -1 u -1 θ(1, 1)(v)θ(1, 0)(B) -1 ; 1, 0) = (Bv -1 u -1 Bvu -2 B -1 ; 1, 0) = (Bu -1 B -1 ; 1, 0).
Now suppose that the result holds for all integers belonging to {1, . . . , r}, and let us show by induction that it is true for r + 1. We have:

l σ (u r+1 ; 0, 0) = l σ (u; 0, 0)l σ (u r ; 0, 0) = (Bu -1 B -1 ; 1, 0)((Bu -1 ) r B -r ; r, 0) = (Bu -1 B -1 θ(1, 0)(B)θ(1, 0)(u) -1 r θ(1, 0)(B) -r ; r + 1, 0) = (Bu -1 B -1 B(BuB -1 ) -1 r B -r ; r + 1, 0) = ((Bu -1 ) r+1 B -(r+1) ; r, 0).
and hence equation ( 1) holds for all r ≥ 0. Now assume that r < 0. Then -r > 0, and since l σ (u; 0, 0) = l σ (u -r ; 0, 0) -1 , it follows that:

l σ (u r ; 0, 0) = l σ (u -r ; 0, 0) -1 = ((Bu -1 ) -r B r ; -r, 0) -1 = ((θ(r, 0)((Bu -1 ) -r B r )) -1 ; r, 0) = (((θ(r, 0)(B)θ(r, 0)(u) -1 ) -r θ(r, 0)(B) r ) -1 ; r, 0) = (((B(B r uB -r ) -1 ) -r B r ) -1 ; r, 0) = ((Bu -1 ) r B -r ; r, 0).
This proves equation ( 1). Let us show that equation ( 2) holds. If s = 0, the result is immediate. For s = 1, 2, we have:

l σ (v; 0, 0) = (γ • c σ )(b -1 2 ) = γ(Ba -1 2 B -1 ) = (B; 0, 0)(v; 0, -1) -1 (B; 0, 0) -1 = (B; 0, 0)(θ(0, 1)(v) -1 ; 0, 1)(B -1 ; 0, 0) = (B(vB) -1 θ(0, 1)(B) -1 ; 0, 1)
= (v -1 B; 0, 1) = ((uv) -1 (uB) δ 1 ; 0, 1), and (16) l σ (v 2 ; 0, 0) = l σ (v; 0, 0)l σ (v; 0, 0) = (v -1 B; 0, 1)(v -1 B; 0, 1) = (v -1 Bθ(0, 1)(v) -1 θ(0, 1)(B); 0, 2) = ((v -1 B(vB) -1 B -1 ; 0, 2) = (v -2 B -1 ; 0, 2) = ((uv) -2 (uB) δ 2 ; 0, 2), [START_REF] Whitehead | Elements of homotopy theory[END_REF] and so equation (2) holds in these two cases. Now suppose that s is even. Then s = 2k for some k ∈ Z. We wish to show that l σ (v 2k ; 0, 0) = ((uv) -2k ; 0, 2k). If k = 1, the result holds by [START_REF] Whitehead | Elements of homotopy theory[END_REF]. Suppose that k ≥ 1 and that the result is true for all integers belonging to {1, . . . , k}. Then:

l σ (v 2(k+1) ; 0, 0) = l σ (v 2k ; 0, 0)l σ (v 2 ; 0, 0) = ((uv) -2k ; 0, 2k)((uv) -2 ; 0, 2) = ((uv) -2k (θ(0, 2k)(u)θ(0, 2k)(v)) -2 ; 0, 2k + 2) = ((uv) -2k (uv) -2 ; 0, 2(k + 1)) = ((uv) -2(k+1) ; 0, 2(k + 1)).
and so by induction, equation ( 2) holds for all k ≥ 1. Now suppose that k < 0. Then -k > 0, and since l σ (v 2k , 0, 0) = l σ (v -2k ; 0, 0) -1 , we see that:

l σ (v 2k ; 0, 0) = l σ (v -2k ; 0, 0) -1 = ((uv) 2k ; 0, -2k) -1 = ((θ(0, 2k)((uv) 2k )) -1 ; 0, 2k) = (((θ(0, 2k)(u)θ(0, 2k)(v)) 2k ) -1 ; 0, 2k) = ((uv) -2k ; 0, 2k),
and hence equation ( 2) holds for all s even. Now assume that s is odd, and let k ∈ Z be such that s = 2k + 1. Using ( 16) and the result for s even, we obtain:

l σ (v 2k+1 ; 0, 0) = l σ (v 2k ; 0, 0)l σ (v; 0, 0) = ((uv) -2k ; 0, 2k)(v -1 B; 0, 1) = ((uv) -2k θ(0, 2k)(v) -1 θ(0, 2k)(B); 0, 2k + 1) = ((uv) -2k v -1 B; 0, s) = ((uv) -s (uB) δs , 0, s).
This completes the proof of equation [START_REF] Bellingeri | Lower central series of Artin-Tits and surface braid groups[END_REF]. To obtain equation ( 4), it suffices to prove the result for m = 1. We have:

l σ (½; 1, 0) = (γ • c σ )(b 1 a 1 b 2 a 2 ) = γ(Ba 1 B -1 b 1 Ba 2 B -1 b 2 ) = (B; 0, 0)(v -1 u -1 ; 1, 1)(B; 0, 0) -1 (uv; 0, 0)(B; 0, 0)(v; 0, -1)(B; 0, 0) -1 (v -1 ; 0, 0) = (Bv -1 u -1 θ(1, 1)(B) -1 θ(1, 1)(u)θ(1, 1)(v)θ(1, 1)(B)θ(1, 1)(v)θ(1, 0)(B) -1 θ(1, 0)(v) -1 ; 1, 0) = (Bv -1 u -1 Bu -1 Bvu -2 B -1 Bvu -2 B -1 (Bvu -2 B -1 ) -1 ; 1, 0) = (½; 1, 0),
as required. Finally, to prove equation ( 5), if n ∈ Z, let k ∈ Z be such that n = 2k + δ n . Then: l σ (½; 0, n) = l σ (½; 0, 1) n = (B; 0, 1) n = (B; 0, 1) 2k (B; 0, 1) δn = ((B; 0, 1)(B; 0, 1)

) k (B δn ; 0, δ n ) = (Bθ(0, 1)(B); 0, 2) k (B δn , 0, δ n ) = (½; 0, 2k)(B δn ; 0, δ n ) = (θ(0, 2n)(B) δn ; 0, 2k + δ n ) = (B δn ; 0, n),
and thus equation ( 5) holds.

Proof of Theorems 1 and 2

The purpose of this section is to prove Theorems 1 and 2. We identify π 1 (T 2 ) with Z ⊕ Z and π 1 (K 2 ) with Z ⋊ Z as in Sections 3 and 4 respectively. Consider the following short exact sequences:

1 / / π 1 (T 2 ) i 1 / / π 1 (T 2 ) θ 1 / / Z 2 / / 1, where: (18) i 1 : (1, 0) -→ (2, 0) (0, 1) -→ (0, 1) θ 1 :
(1, 0) -→ 1 (0, 1) -→ 0 and

1 / / π 1 (T 2 ) i 2 / / π 1 (K 2 ) θ 2 / / Z 2 / / 1, where: (19)
i 2 :

(1, 0) -→ (1, 0) (0, 1) -→ (0, 2) θ 2 :

(1, 0) -→ 0 (0, 1) -→ 1.

By covering space theory, there exist double coverings c 1 : T 2 → T 2 and c 2 : T 2 → K 2 such that the induced homomorphisms on the fundamental group are i 1 and i 2 respectively. If k ∈ {1, 2} and τ k : T 2 → T 2 is the non-identity deck transformation associated with c k , then τ k is a free involution, and the short exact sequence induced by τ k is (18

) if k = 1 and is (19) if k = 2. Further, τ k lifts to a homeomorphism τ k : R 2 → R 2 , where τ 1 (x, y) = (x + 1 2 , y) and τ 2 (x, y) = (x + 1 2 , 1 -y) for all (x, y) ∈ R 2 .
As we shall now see, up to the equivalence relation defined just after Proposition 9, these are the only free involutions of the torus.

Proposition 25. The free involutions τ 1 and τ 2 are not equivalent. Further, let τ : T 2 → T 2 be a free involution. If τ preserves (resp. reverses) orientation, then τ is equivalent to τ 1 (resp. to τ 2 ).

Proof. The short exact sequences [START_REF] Zieschang | Surfaces and Planar Discontinuous Groups[END_REF] and ( 19) are not equivalent (in the sense described at the end of Section 2), since the middle groups are not isomorphic, and so τ 1 and τ 2 are not equivalent by Proposition 10. Now let τ : T 2 → T 2 be a free involution. Recall that T 2 τ is the corresponding orbit space, and that the natural projection p τ : T 2 → T 2 τ is a double covering. Suppose first that τ preserves orientation. Then T 2 τ is homeomorphic to the torus, and the short exact sequence induced by τ is of the following form:

1 / / π 1 (T 2 ) (pτ ) # / / π 1 (T 2 τ ) ∼ =Z⊕Z θτ / / Z 2 / / 1. (20)
By [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF]Proposition 30], there exists an isomorphism ψ : [START_REF] Zieschang | Surfaces and Planar Discontinuous Groups[END_REF] and (20) and using exactness and the 5-Lemma, it follows that ψ induces an isomorphism ϕ :

π 1 (T 2 ) → π 1 (T 2 τ ) such that θ τ • ψ = θ 1 . Comparing diagrams
π 1 (T 2 ) → π 1 (T 2 ) such that (p τ ) # • ϕ = ψ • i 1 .
So the exact sequences [START_REF] Zieschang | Surfaces and Planar Discontinuous Groups[END_REF] and (20) are equivalent, and we conclude that τ and τ 1 are equivalent by Proposition 10. Now suppose that τ reverses orientation. Then T 2 τ is homeomorphic to the Klein bottle, and the short exact sequence induced by τ is of the following form:

1 / / π 1 (T 2 ) (pτ ) # / / π 1 (T 2 τ ) ∼ =Z⋊Z θτ / / Z 2 / / 1. ( 21
)
Using the identification described in Remark 17, we have an isomorphism γ : Z ⋊ Z → π 1 (T 2 τ ). The elements γ(0, 1) = v 1 and γ(1, 1) = u 1 v 1 represent loops in T 2 τ that reverse orientation. Since

p τ : T 2 → T 2 τ is a covering, we have θ τ • γ(1, 0) = θ τ • γ(1, 1) = 1, so the element (1, 0) = (1, 1)(0, 1) -1 satisfies θ τ •γ(1, 0) = 0, and thus θ τ •γ = θ 2 . Let ψ : π 1 (K 2 ) → π 1 (T 2
τ ) be an isomorphism. Comparing diagrams ( 19) and ( 21) and using exactness and the 5-Lemma once more, it follows that ψ induces an isomorphism ϕ :

π 1 (T 2 ) → π 1 (T 2 ) such that (p τ ) # • ϕ = ψ • i 2 .
So the exact sequences ( 19) and ( 21) are equivalent, and we conclude that τ and τ 2 are equivalent by Proposition 10.

Theorem 4 gives rise to the following commutative diagram, where the maps are bijections (we simplify the notation):

[T 2 , * ; T 2 , * ] Λ * * Γ / / Hom(Z ⊕ Z, Z ⊕ Z) [T 2 , T 2 ]. ∆ o o (22)
We shall now solve the Borsuk-Ulam problem for homotopy classes with respect to the involution τ 1 .

We first state and prove the following lemma. (iii) β # (0, 1) = (p 1 ) # (b).

Proof. Suppose that β does not have the Borsuk-Ulam property with respect to τ 1 . By (22) and Proposition 7, there exists a pointed homotopy class α that does not have the Borsuk-Ulam property and for which α F = Λ(α) = β. Using Proposition 6, there exist homomorphisms ϕ : π 1 (T 2 ) → P 2 (T 2 ) and ψ : π 1 (T 2 ) → B 2 (T 2 ) that make diagram (9) commute. By [START_REF] Zieschang | Surfaces and Planar Discontinuous Groups[END_REF], ψ(1, 0) ∈ B 2 (T 2 )\P 2 (T 2 ) and ψ(0, 1) ∈ P 2 (T 2 ). From the short exact sequence (8) and Theorem 14, there exist a, b ∈ P 2 (T 2 ) such that:

(1) ψ(1, 0) = aσ.

(2) ψ(0, 1) = b.

Since π 1 (T 2 ) is an Abelian group, we have [ψ(1, 0), ψ(0, 1)] = aσbσa -1 a -1 b -1 = ½, which is equivalent to al σ (b) = ba, from which we obtain (i). The commutativity of (9) implies that: from which we obtain (ii) and (iii). Conversely, suppose that there exist a, b ∈ P 2 (T 2 ) such that (i), (ii) and (iii) are satisfied. We define ψ : π 1 (T 2 ) → P 2 (T 2 ) (resp. ϕ : π 1 (T 2 ) → B 2 (T 2 )) on the generators of π 1 (T 2 ) by the correspondences (1) and (2) (resp. ( 3) and ( 4)). Since:

[ϕ(1, 0), ϕ(0, 1)] = al σ (a)σ 2 , b = aσaσ -1 σ 2 bσ -2 σa -1 σ -1 a -1 b -1 = al σ (al σ (b)a -1 )a -1 b -1 (i) = al σ (baa -1 )a -1 b -1 (i) = baa -1 b -1 = ½, and [ψ(1, 0), ψ(0, 1)] = [aσ, b] = aσbσ -1 a -1 b -1 = al σ (b)a -1 b -1 (i) = baa -1 b -1 = ½.
these correspondences extend to homomorphisms. As in the first part of the proof, ψ and ϕ make the diagram (9) commute, so by Theorem 6 and (22), β does not have the Borsuk-Ulam property with respect to τ 1 .

For each β ∈ [T 2 , T 2 ], let β 1,1 , β 2,1 , β 1,2 , β 2,2 ∈ Z be such that:

β # (1, 0) = ∆(β)(1, 0) = (β 1,1 , β 2,1 ) and β # (0, 1) = ∆(β)(0, 1) = (β 1,2 , β 2,2 ). Proposition 27. If β ∈ [T 2 , T 2
] is a homotopy class then β does not have the Borsuk-Ulam property with respect to τ 1 .

Proof. Let r, s ∈ Z and i, j ∈ {0, 1} be such that β 1,1 = 2r + i and β 2,1 = 2s + j. With the identification of Theorem 14, let a = (x i y j , r, s) and b = (½, β 1,2 , β 2,2 ) of P 2 (T 2 ). Let us show that these elements satisfy (i), (ii) and (iii) of Lemma 26, from which it will follow that β does not have the Borsuk-Ulam property with respect to τ 1 . First: al σ (b) = (x i y j , r, s)(½, β 1,2 , β 2,2 ) = (½, β 1,2 , β 2,2 )(x i y j , r, s) = ba, which yields (i). Using [START_REF] Magnus | Combinatorial Group Theory: Presentations of groups in terms of generators and relations[END_REF], we obtain:

(p 1 ) # (al σ (a)) = (r, s) + (i, j) + (r, s) = (β 1,1 , β 2,1 ) = β # (1, 0),
which proves (ii). Finally, we have:

(p 1 ) # (b) = (β 1,2 , β 2,2 ) = β # (0, 1), whence (iii).
Proof of Theorem 1. The result is a consequence of Propositions 9, 25 and 27.

We now solve the Borsuk-Ulam problem with respect to the involution τ 2 . This case is more delicate than the previous one. We first prove some preliminary results.

Lemma 28. A free homotopy class β ∈ [T 2 , T 2 ] does not have the Borsuk-Ulam property with respect to τ 2 if and only if there exist a, b ∈ P 2 (T 2 ) such that:

(i) abl σ (a) = b. (ii) β # (1, 0) = (p 1 ) # (a). (iii) β # (0, 1) = (p 1 ) # (bl σ (b)).
Lemma 31. Let z, w ∈ F (x, y) be such that w is non trivial, |w| x and |w| y are even and zwz -1 = w(x -1 , y -1 ) -1 .

(23)

Then |z| x or |z| y is even.

Proof. The result is immediate if z is trivial. So assume that z is non trivial. Without loss of generality, we may suppose that z and w are each written in reduced form. Since ℓ(w) = ℓ(w(x -1 , y -1 ) -1 ), there must be cancellation on the left-hand side of equation ( 23). We are interested in the parity of |z| x and |z| y . The following operations show that, while respecting the hypotheses of the statement of the lemma, we may modify z and w so as to control better the possible cancellations in (23). In what follows, let g ∈ {x, y}.

Step 1: We may assume that cancellation occurs at zw or at wz -1 , but not at both. For suppose that cancellation occurs at zw and at wz -1 . Then z = z 1 k and w = k -1 w 1 k in reduced form for some k ∈ {x, x -1 , y, y -1 } and some z 1 , w 1 ∈ F (x, y). Now w 1 is non trivial and |w 1 | x and |w 1 | y are even. Also, (k -1 z 1 )w 1 (k -1 z 1 ) -1 = w 1 (x -1 , y -1 ) -1 by ( 23). This equation is of the same nature as that of (23), and it is easy to see that |k -1 z 1 | g ≡ |z| g mod 2. If cancellation occurs at (k -1 z 1 )w 1 and at w 1 (k -1 z 1 ) -1 , we repeat the argument. After a finite number of operations (possibly zero, and at most ℓ(z) times), we obtain elements z ′ , w ′ ∈ F (x, y) in reduced form for which |z ′ | g ≡ |z| g mod 2, that continue to satisfy the hypotheses of the lemma, and such that any cancellation in z ′ w ′ z ′-1 occurs either at zw ′ or at zw ′-1 , but not at both.

Step 2: We may assume that cancellation occurs at zw. For if cancellation occurs at wz -1 , by setting w ′ = w -1 , the elements z, w ′ ∈ F (x, y) satisfy the hypotheses of the lemma, and cancellation occurs at zw ′ .

Step 3: We may assume that z cannot be written in reduced form z ′ w ε , where ε ∈ {-1, 1}. For if z = z 1 w ε 1 in reduced form for some z 1 ∈ F (x, y) and some ε 1 ∈ {-1, 1}, then z 1 wz -1 1 = w(x -1 , y -1 ) -1 by (23). Hence the elements z 1 , w ∈ F (x, y) satisfy the hypotheses of the lemma, and

|z| g = |z 1 | g + ε 1 |w| g ≡ |z 1 | g mod 2.
If z 1 may be writen in reduced form z 2 w ε 2 , for some z 2 ∈ F (x, y) and some ε 2 ∈ {-1, 1}, we repeat the argument. After a finite number of operations, we obtain an element z ′ ∈ F (x, y) such that z ′ and w satisfy the hypotheses of the lemma, z ′ cannot be written in reduced form zw ε for some z ∈ F (x, y) and some ε ∈ {-1, 1}, and |z| g ≡ |z ′ | g mod 2.

After applying steps 1, 2 and 3 as many times as necessary, we may suppose without loss of generality that there exist elements z 1 , z 2 , w 1 , w 2 ∈ F (x, y) such that z = z 1 z 2 and w = w 1 w 2 in reduced form, w 1 and w 2 are non trivial, w 1 = z -1 2 , and there is no cancellation either at z 1 w 2 or at w 2 z -1 2 . By (23), we have:

z 1 w 2 w 1 z -1 1 = w 2 (x -1 , y -1 ) -1 w 1 (x -1 , y -1 ) -1 . (24)
By hypothesis, there is no cancellation in z 1 w 2 w 1 z -1 1 . But ℓ(w 2 w 1 ) = ℓ(w 1 w 2 ), which in turn is equal to ℓ(w 2 (x -1 , y -1 ) -1 w 1 (x -1 , y -1 ) -1 ). So by (24), z 1 is trivial and w i = w i (x -1 , y -1 ) -1 , for all i ∈ {1, 2}. Thus z = w -1

1 , and therefore it is a palindrome. The result then follows from Lemma 30.

Proposition 32. Suppose that β ∈ [T 2 , T 2 ] satisfies (β 1,1 , β 2,1 ) = (0, 0), and β 1,2 and β 2,2 are even. Then β has the Borsuk-Ulam property with respect to τ 2 .

Proof. We argue by contradiction. Suppose that β does not have the Borsuk-Ulam property with respect to τ 2 . By Lemma 28, there exist a = (w(x, y), r a , s a ) and b = (z(x, y), r b , s b ) such that a, b and β # satisfy items (i), (ii) and (iii). By (ii), we have (r a , s a ) = (β 1,1 , β 2,1 ). Using (iii), [START_REF] Magnus | Combinatorial Group Theory: Presentations of groups in terms of generators and relations[END_REF] implies that:

(β 1,2 , β 2,2 ) = (p 1 ) # (bl σ (b)) = (|z| x + 2r b , |z| y + 2s b ),
and we see that |z| x and |z| y are even. Further:

abl σ (a) = (w, β 1,1 , β 2,1 )(z, r b , s b )(xy -1 w(x -1 , y -1 )yx -1 , |w| x + β 1,1 , |w| y + β 2,1 ) = (wzxy -1 w(x -1 , y -1 )yx -1 , 2β 1,1 + |w| x + r b , 2β 2,1 + |w| y + s b ).
By condition (i), it follows that |w| x = -2β 1,1 and |w| y = -2β 2,1 , and thus w is non trivial. Furthermore, wzxy -1 w(x -1 , y -1 )yx -1 = z by (i), and so:

(yx -1 z -1 )w(yx -1 z -1 ) -1 = w(x -1 , y -1 ) -1 .
By Lemma 31, we see that 6 Proof of Theorem 3

|yx -1 z -1 | x = -1 -|z| x or |yx -1 z -1 | y = 1 -
The purpose of this section is to prove Theorem 3. We identify π 1 (K 2 ) with Z ⋊ Z as in Section 4. Consider the following short exact sequence:

1 / / π 1 (K 2 ) i 3 / / π 1 (K 2 ) θ 3 / / Z 2 / / 1 (25)
i 3 :

(1, 0) -→ (2, 0) (0, 1) -→ (0, 1) θ 3 :

(1, 0) -→ 1 (0, 1) -→ 0.

By covering space theory, there exists a double covering c 3 : K 2 → K 2 such that the induced homomorphism on the fundamental group is i 3 . Let τ 3 : K 2 → K 2 be the non-identity deck transformation associated with c 3 . Then τ 3 is a free involution, and (25) is the short exact sequence induced by τ 3 . Further, τ 3 lifts to a homeomorphism τ 3 : R 2 → R 2 , where τ 3 (x, y) = (x, y + 1 2 ) for all (x, y) ∈ R 2 . As the following result shows, up to the equivalence relation defined just after Proposition 9, this is the only free involution on the Klein bottle.

Proposition 33. Let τ : K 2 → K 2 be a free involution. Then τ is equivalent to τ 3 .

Proof. Since the natural projection p τ : K 2 → K 2 τ is a covering, K 2 τ is homeomorphic to the Klein bottle, and the short exact sequence induced by τ is of the following form:

1 / / π 1 (K 2 ) = Z ⋊ Z (pτ ) # / / π 1 (K 2 τ ) θτ / / Z 2 / / 1. ( 26
)
By Remark 17 we have an isomorphism γ : Z ⋊ Z → π 1 (K 2 τ ). The composition θ τ • γ is different from the homomorphism θ 2 defined in (19). Indeed, if θ τ • γ = θ 2 , then π 1 (K 2 ) ∼ = ker θ τ • γ = ker θ 2 ∼ = π 1 (T 2 ), which is absurd. By [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF]Proposition 32], there exists an isomorphism ψ : π 1 (K 2 ) → π 1 (K 2 τ ) such that θ 3 = θ τ • ψ. Comparing (25) and (26) and using exactness and the 5-Lemma, it follows that ψ induces an isomorphism ϕ : π 1 (K 2 ) → π 1 (K 2 ) such that (p τ ) # • ϕ = ψ • i 3 . So the exact sequences (25) and ( 26 Remark 34. By [10, Lemma 3.1], for each h ∈ Hom(Z ⋊ Z, Z ⋊ Z), we have the following two possibilities for the images of the generators of Z ⋊ Z:

• h(1, 0) = (r 1 , 0) and h(0, 1) = (r 2 , 2s + 1) for some r 1 , r 2 , s ∈ Z. In this case, we say that h is of type A.

• h(1, 0) = (0, 0) and h(0, 1) = (r, 2s) for some r, s ∈ Z. In this case, we say that h is of type B.

Proposition 35. Let h ∈ Hom(Z ⋊ Z, Z ⋊ Z).

(a) If h is of type A then there exist unique integers i ∈ {0, 1}, r, s ∈ Z, where r ≥ 0, such that h is conjugate to the homomorphism given by (1, 0) -→ (r, 0) (0, 1) -→ (i, 2s + 1).

(b) If h is of type B then there exist unique integers r, s ∈ Z, where r ≥ 0, such that h is conjugate to the homomorphism given by (1, 0) -→ (0, 0) (0, 1) -→ (r, 2s).

Proof. If h : Z ⋊ Z → Z ⋊ Z is of Type A, then conjugating h by the element (a, b) ∈ Z ⋊ Z, we obtain a homomorphism h ′ : Z ⋊ Z → Z ⋊ Z that depends on r 1 and r 2 as follows:

• if r 1 ≥ 0 (resp. r 1 < 0) and r 2 is even, let a = -r 2 2 and b = 0 (resp. a = r 2 2 and b = 1). Then h ′ :

(1, 0) -→ (|r 1 |, 0) (0, 1) -→ (0, 2s + 1).

• if r 1 ≥ 0 (resp. r 1 < 0) and r 2 is odd, let a = -r 2 +1 If h : Z⋊Z → Z⋊Z is of Type B, then conjugating h by (0, 1), we obtain a homomorphism h ′ : Z⋊Z → Z ⋊ Z defined by: h ′ :

(1, 0) -→ (0, 0) (0, 1) -→ (-r, 2s). We conclude that each element h ∈ Hom(Z ⋊ Z, Z ⋊ Z)

is conjugate to one of the homomorphisms given in the statement of the proposition. Further, if h 1 , h 2 : Z ⋊ Z → Z ⋊ Z are two such homomorphisms, then we leave it as an exercise to show that if they are distinct, then they are non conjugate, and the result follows.

  Further, a homotopy class β ∈ [M, N] does not have the Borsuk-Ulam property with respect to τ 1 if and only if H(β) does not have the Borsuk-Ulam property with respect to τ 2 . Proof. Let τ 1 , τ 2 : M → M be free involutions, and suppose that H : M → M is a (τ 1 , τ 2 )-equivariant homeomorphism and that β ∈ [M, N]. If β does not have the Borsuk-Ulam property with respect to τ 1 , there exists a map f 1 : M

  (a) the homomorphism (p 1 ) # :P 2 (T 2 ) → π 1 (T 2 ) is projection onto the group Z ⊕ Z, in other words, (p 1 ) # (w, m, n) = (m, n) for all x ∈ F (x,y) and m, n ∈ Z. (b) the element σ belongs to B 2 (T 2 )\P 2 (T 2 ) and satisfies σ 2 = (B, 0, 0), where B = [x, y -1 ].

Remark 19 ./ ϕ g g 1 ,

 191 Given a split short exact sequence 1 / / A / / G π / / B / recall that there exists a homomorphism θ : B → Aut(A), defined by θ(b)(a) = ϕ(b)aϕ(b) -1 , and isomorphisms A ⋊ θ B λ / / G γ o o , defined by λ(a, b) = aϕ(b) and γ(g) = (gϕ(π(g)) -1 , π(g)).

Lemma 26 .

 26 A free homotopy class β ∈ [T 2 , T 2 ] does not have the Borsuk-Ulam property with respect to τ 1 if and only if there exist pure braids a, b ∈ P 2 (T 2 ) such that: (i) al σ (b) = ba. (ii) β # (1, 0) = (p 1 ) # (al σ (a)).

( 3 )

 3 ϕ(1, 0) = ψ((p τ 1 ) # (1, 0)) = ψ(2, 0) = (aσ) 2 = al σ (a)σ 2 , and (4) ϕ(0, 1) = ψ((p τ 1 ) # (0, 1)) = ψ(0, 1) = b.Finally, using (22), we have:β # (1, 0) = (p 1 ) # (ϕ(1, 0)) = (p 1 ) # (al σ (a)) + (p 1 ) # (B, 0, 0) = (p 1 ) # (al σ (a)), and β # (0, 1) = (p 1 ) # (ϕ(0, 1)) = (p 1 ) # (b),

  ) are equivalent, and we conclude that τ and τ 1 are equivalent by Proposition 10.By Theorem 4, the following diagram (we simplify the notation):[K 2 , * ; K 2 , * ] Γ / / Λ Hom(Z ⋊ Z, Z ⋊ Z) Υ [K 2 , K 2 ] ∆ / / Hom(Z ⋊ Z, Z ⋊ Z) ∼(27)is commutative, where the maps Γ and ∆ are bijections and the maps Λ and Υ are surjective. So, in order to determine the sets [K 2 , * ; K 2 , * ] and [K 2 , K 2 ], we will describe the elements of the sets Hom(Z ⋊ Z, Z ⋊ Z) and Hom(Z ⋊ Z, Z ⋊ Z) ∼ .

2

  and b = 0 (resp. a = r 2 +1 2 and b = 1). Then h ′ :(1, 0) -→ (|r 1 |, 0) (0, 1) -→ (1, 2s + 1).

Remark 36 .

 36 By diagram (27) and Proposition 35, there exists a bijection between the set [K 2 , K 2 ] and the subset of Hom(Z ⋊ Z, Z ⋊ Z) whose elements are described in parts (a) and (b) of Proposition 35. By abuse of notation, for each β ∈ [K 2 , K 2 ], the image of β under the above bijection shall be denoted by β # .

  |z| y is even, or equivalently, that |z| x or |z| y is odd. But this contradicts the fact that |z| x and |z| y are even. Thus β has the Borsuk-Ulam property with respect to τ 2 as required.Proof of Theorem 2. The result follows directly from Propositions 29 and 32.

Acknowledgements

Part of this work is contained in the Ph.D. thesis [11] of the third author who was supported by CNPq project n o 140836 and Capes/COFECUB project n o 12693/13-8. The first and second authors were partially supported by CNRS/FAPESP project number (2014/50131-7: Brazil; 2014/226555: France). The second author wishes to thank the 'Réseau Franco-Brésilien en Mathématiques' for financial support during his visit to the Instituto de Matemática e Estatística, Universidade de São Paulo, from the 9 th of July to the 1 st of August 2016.

Using ( 14) and [START_REF] Nielsen | Untersuchungen zur Topologie der geschlossenen zweiseitigen Flächen[END_REF], we obtain:

which implies relation [START_REF] Fadell | Configuration Spaces[END_REF]. Using relation [START_REF] Fadell | Configuration Spaces[END_REF], relations (4) and ( 5) then follow from ( 14) and ( 15) respectively.

To simplify various computations, it will be convenient to carry out the change of basis given by u

2 , so b 1 = uv and b 2 = v -1 . Note that in the new basis, B = [u, v] ′ . In order to determine the automorphism θ(m, n) : F (u, v) → F (u, v) for each (m, n) ∈ Z ⋊ Z, we require the following two lemmas.

Lemma 21. For all m ∈ Z, we have:

Proof. The result is clear if m = 0. If m = 1 then Proposition 18 and Lemma 20 imply that:

Suppose that the result holds for all integers belonging to {1, . . . , m}, and let us show by induction that it holds for m + 1. We have: m+1) , and

as required, and so the result holds for all m ≥ 0. Now suppose that m < 0. Then -m > 0, and so:

We also have:

thus θ(m, 0) = B m uB -m , and:

Lemma 22. For all n ∈ Z, we have:

Proof. We follow the proof of Lemma 26, replacing the homomorphism ψ (resp. ϕ) by the homomorphism ψ :

)) defined on the generators of π 1 (K 2 ) (resp. of π 1 (T 2 )) by ψ(1, 0) = a and ψ(0, 1) = bσ (resp. ϕ(1, 0) = a and ϕ(0, 1) = bl σ (b)σ 2 ). The details are left as an exercise.

Proposition 29. Suppose that β ∈ [T 2 , T 2 ] satisfies one of the following conditions:

1. at least one of β 1,2 and β 2,2 is odd.

2. (β 1,1 , β 2,1 ) = (0, 0) and β 1,2 and β 2,2 are both even.

Then β does not have the Borsuk-Ulam property with respect to τ 2 .

Proof. Assume that condition 1 of the statement is satisfied. Suppose first that β 1,2 and β 2,2 are odd. Let r, s ∈ Z be such that β 1,2 = 2r + 1 and β 2,2 = 2s + 1. With the identification of Theorem 14, consider the elements a = (x

). We will show that a and b satisfy (i), (ii) and (iii) of Lemma 28, from which it will follow that β does not have the Borsuk-Ulam property with respect to τ 2 . Using ( 12) we obtain:

and hence condition (i) is satisfied. Further:

from which it follows that conditions (ii) and (iii) are satisfied, and hence β does not have the Borsuk-Ulam property with respect to τ 2 . The remaining cases are analogous, and we just provide the elements a and b of P 2 (T 2 ) in each case that satisfy (i), (ii) and (iii) of Lemma 28, the details being left as an exercise. If β 1,2 is odd and β 2,2 is even, we take β 1,2 = 2r + 1 and β 2,2 = 2s, where r, s ∈ Z, and a = (x -β 1,1 y -2β 2,1 -1 x -β 1,1 y, β 1,1 , β 2,1 ) and b = (x -1 , r + 1, s). If β 1,2 is even and β 2,2 is odd, we set β 1,2 = 2r and β 2,2 = 2s + 1, where r, s ∈ Z, and a = (x -2β 1,1 +1 y -β 2,1 x -1 y -β 2,1 , β 1,1 , β 2,1 ) and b = (x -2β 1,1 +1 yx -1 , β 1,1 + r, s). Finally, if β satisfies condition 2 of the statement, we take β 1,2 = 2r and β 2,2 = 2s, where r, s ∈ Z, and a = (½, 0, 0) and b = (½, r, s).

Note that the case where (β 1,1 , β 2,1 ) = (0, 0) and β 1,2 and β 2,2 are even is not addressed by Proposition 29. Before analysing this situation, let z = z(x, y) be a reduced word in F (x, y). Then z is called a palindrome if z(x, y) = z(x -1 , y -1 ) -1 . This means that z reads the same backwards as forwards.

, where for all i = 1, . . . , m, w i ∈ {x, y} and ǫ i ∈ Z, the length ℓ(z) of z is defined to be equal to m i=1 |ǫ i |. We now prove two technical lemmas. Lemma 30. If z = z(x, y) ∈ F (x, y) is a palindrome, then |z| x or |z| y is even.

Proof. Let z = z(x, y) be a reduced word in F (x, y). If ℓ(z) = 0 or ℓ(z) = 1 then z is trivial or z ∈ {x, x -1 , y, y -1 } respectively, and at least one of |z| x and |z| y is zero. If ℓ(z) = 2 then z ∈ {x 2a , y 2a , x a y b , y b x a | a, b ∈ {-1, 1}}. Since z is a palindrome, z = x 2a or z = y 2b and the result follows. So suppose by induction that the result holds for palindromes of length less than or equal to r, where r ≥ 2, and let z be a palindrome such that ℓ(z) = r +1. By definition of palindrome, we have z = kz ′ k, where k ∈ {x, x -1 , y, y -1 }, z ′ ∈ F (x, y) and kz ′ k is in reduced form. Then ℓ(z ′ ) = r -2 and

Thus z ′ is a palindrome, and |z ′ | x or |z ′ | y is even by induction. The result follows using the fact that |z| g ≡ |z ′ | g mod 2 for all g ∈ {x, y}.

We now solve the Borsuk-Ulam problem for homotopy classes with respect to involution τ 3 . As in Lemmas 26 and 28, we have the following result: Lemma 37. A free homotopy class β ∈ [K 2 , K 2 ] does not have the Borsuk-Ulam property with respect to τ 3 if and only if there exist pure braids a, b ∈ P 2 (K 2 ) such that:

Proof. First, suppose that β does not have the Borsuk-Ulam property with respect to τ 3 . By (27) and Proposition 7, there exists a pointed homotopy class α that does not have the Borsuk-Ulam property such that α F = Λ(α) = β. By Proposition 6, there exist homomorphisms ϕ :

) and ψ(0, 1) ∈ P 2 (K 2 ). From the short exact sequence [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF] and Theorem 15, there exist a, b ∈ P 2 (T 2 ) such that:

(1) ψ(1, 0) = σa.

(2) ψ(0, 1) = b.

By Remark 17, we have ½ = [ψ(1, 0), ψ(0, 1)] ′ = σabσab -1 , which is equivalent to (σaσ -1 )(σbσ -1 )σ 2 a = b, and which yields (i). The commutativity of ( 9) gives rise to the following relations: 27), from which we obtain (ii) and (iii). Conversely, suppose that there exist a, b ∈ P 2 (K 2 ) such that conditions (i), (ii) and (iii) are satisfied. We define ψ :

) on the generators of π 1 (K 2 ) by equations ( 1) and (2) (resp. ( 3) and ( 4)). These maps extend to homomorphisms because: Now suppose that r is odd, and let m ∈ Z be such that r = 2m + 1. Consider the elements a = (uB -m ; m, 0) and b = (u -1 B δ (i+1) ; i, 2s + 1) of P 2 (K 2 ). The conclusion follows in a manner similar to that of the previous case, and the details are left as an exercise.

Proposition 39. With the notation of Proposition 35 and Remark 36, let β ∈ [K 2 , K 2 ] be such that the homomorphism β # : Z ⋊ Z → Z ⋊ Z is of Type B. Then β has the Borsuk-Ulam property with respect to τ 3 .

Proof. We argue by contradiction. Suppose that β does not have the Borsuk-Ulam property with respect to τ 3 . By Proposition 7 and diagram (27), there exists a pointed map f : (K 2 , * ) → (K 2 , * ) such that f # = β # and f (τ 3 (x)) = f (x) for all x ∈ K 2 . Notice that the image of f # is contained in the image of the homomorphism i 2 : π 1 (T 2 ) → π 1 (K 2 ) that is defined in (19). Recall that c 2 : T 2 → K 2 is the double covering such that (c 2 ) # = i 2 . So, by covering space theory, there exists a pointed map f : (K 2 , * ) → (T 2 , * ) such that c 2 • f = f . Therefore, the map f satisfies f (τ 3 (x)) = f (x) for all x ∈ K 2 , which implies that the triple (K 2 , τ 3 ; T 2 ) does not have the Borsuk-Ulam property. But this yields a contradiction using Remark 17, the short exact sequence (25) and [START_REF] Gonçalves | The Borsuk-Ulam theorem for maps into a surface[END_REF]Proposition 10]. The result then follows.

We are now able to prove the final main result of this paper.

Proof of Theorem 3. Using arguments similar to those of Proposition 39 and the notation of Remark 36, a homotopy class β ∈ [K 2 , K 2 ] lifts to the torus if and only if the homomorphism β # : Z ⋊ Z → Z ⋊ Z is of Type B. Further, if H : K 2 → K 2 is a homeomorphism and there exist maps f 1 , f 2 : K 2 → K 2 such that f 2 = f 1 • H -1 , then f 1 lifts to the torus if and only if f 2 lifts to the torus. The result then follows easily from Propositions 9, 33, 38 and 39.


Mahsa Najafzadeh
email: mahsa.najafzadeh@lip6.fr

Alexey Gotsman
email: alexey.gotsman@imdea.org

Hongseok Yang
email: hongseok00@gmail.com

Carla Ferreira
email: carla.ferreira@fct.unl.pt

Marc Shapiro
email: marc.shapiro@acm.org

The CISE Tool: Proving Weakly-Consistent Applications Correct

Keywords: Program Analysis, Consistency, Invariant

Designers of a replicated database face a vexing choice between strong consistency, which ensures certain application invariants but is slow and fragile, and asynchronous replication, which is highly available and responsive, but exposes the programmer to unfamiliar behaviours. To bypass this conundrum, recent research has studied hybrid consistency models, in which updates are asynchronous by default, but synchronisation is available upon request. To help programmers exploit hybrid consistency, we propose the first static analysis tool for proving integrity invariants of applications using databases with hybrid consistency models. This allows a programmer to find minimal consistency guarantees sufficient for application correctness.

INTRODUCTION

To achieve availability and scalability, many modern distributed systems rely on replicated databases, which maintain multiple replicas of shared data. Clients can access the data at any of the replicas, and these replicas communicate changes to each other using message passing. For example, large-scale Internet services use data replicas in geographically distinct locations, and applications for mobile devices keep replicas locally to support offline use. Ideally, we would like replicated databases to provide strong consistency, i.e., to behave as if a single centralised node handles all operations. However, achieving this ideal usually requires synchronisation among replicas, which slows down the database and even makes it unavailable if network connections between replicas fail [START_REF] Abadi | Consistency tradeoffs in modern distributed database system design: CAP is only part of the story[END_REF][START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF].

For this reason, modern replicated databases often eschew synchronisation completely; such databases are commonly dubbed Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. eventually consistent [START_REF] Vogels | Eventually consistent[END_REF]. In these databases, a replica performs an operation requested by a client locally without any synchronisation with other replicas and immediately returns to the client; the effect of the operation is propagated to the other replicas only eventually. Unfortunately, this way of processing operations exposes applications to undesirable concurrency behaviours, which may cause bugs such as state divergence or invariant violation [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF].

For instance, consider a bank account replicated at different bank branches, which supports operations deposit and withdraw. A programmer would like to ensure an integrity invariant that the balance is never negative. Assume that the balance is initially e100. Eventual consistency will allow two users to concurrently withdraw e60 at different branches and thus violate the integrity invariant. To ensure the invariant in this example, we have to introduce synchronisation between replicas, and, since synchronisation is expensive, we would like to introduce it sparingly. To allow this, some research [START_REF] Balegas | Putting consistency back into eventual consistency[END_REF][START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF][START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF][START_REF] Terry | Consistency-based service level agreements for cloud storage[END_REF] and commercial [START_REF]Supported operations in DynamoDB[END_REF][START_REF] Inc | Using strong consistency in Riak[END_REF][START_REF]Consistency levels in DocumentDB[END_REF] databases now provide hybrid consistency models that allow the programmer to request stronger consistency for certain operations and thereby introduce synchronisation. For example, to preserve the integrity invariant in our banking application, only withdraw operations need to use strong consistency, and hence, synchronise to ensure that the account is not overdrawn; deposit operations may use eventual consistency and hence proceed without synchronisation.

Unfortunately, using hybrid consistency models effectively is far from trivial. Requesting stronger consistency in too many places may hurt performance and availability, and requesting it in too few places may violate correctness. Striking the right balance requires the programmer to reason about the application behaviour on the subtle semantics of the consistency model, taking into account which anomalies are disallowed by a particular consistency strengthening and whether disallowing these anomalies is enough to ensure correctness.

To help programmers exploit hybrid consistency models, we propose the first static analysis tool (called CISE: 'Cause I'm Strong Enough) for proving integrity invariants of applications using replicated databases with a range of hybrid models. Our tool is based on a novel proof rule, which we have proved sound [START_REF] Gotsman | Cause I'm strong enough: Reasoning about consistency choices in distributed systems[END_REF]. The tool automates the proof rule by discharging its obligations using an SMT solver. If an obligation fails, the tool provides a counter-example, which the developer can use to understand the source of the problem. Using the tool, we have verified several example applications that require strengthening consistency in nontrivial ways [START_REF] Gotsman | Cause I'm strong enough: Reasoning about consistency choices in distributed systems[END_REF]. These include an extension of the above banking application, an online auction service and a course registration system. A demo of the tool is available online [START_REF] Najafzadeh | Demo of the CISE tool[END_REF].

In the rest of this paper, we explain our static analysis by the example of the above banking application.

SYSTEM MODEL

An application consists of a set of operations Op over some set of objects, and invariants over the objects. The database system consists of a set of replicas, each maintaining a full copy of the database state State.

The replication model uses a Read-One-Write-All (ROWA) approach [START_REF] Bernstein | Concurrency Control and Recovery in Database Systems[END_REF]. A client operation is initially executed at a single replica, which we refer to as its origin replica. This updates the replica state deterministically, and immediately returns a value to the client. After this, the replica sends a message to all other replicas containing the effector of the operation, which describes the updates done by the operation to the database state. Upon receipt, the replicas apply the effector to their state. Effectors of causally-dependent operations are executed in the same order at every replica; effectors of independent (concurrent) operations are executed in any order.

More precisely, the semantics of operations is defined by a partial function

F ∈ Op → (State (Val × (State → State) × P(Token))).
Given a state σ ∈ State in which an operation o ∈ Op executes at its origin replica, F(o)(σ) determines:

• The return value of the operation, from a set Val. We use a special value ⊥ for operations that return no value.

• A function defining the effector of the operation. This will be applied by every replica to its state: immediately at the origin replica, and after receiving the corresponding message at all other replicas.

• A set of tokens, used to introduce synchronisation. We explain them later.

For instance, consider the naïve banking application in Figure 1. A client can read the balance from the local replica, make deposits to and withdrawals from the account, and compute interest, all without communicating with the other replicas. Each operation is associated with a precondition-a predicate over the state of its origin replica and parameters that determines when the operation can be safely executed (and the F function defined). A minimal precondition of the deposit(amount) and withdraw(amount) operations is amount ≥ 0. Their effectors add amount to (respectively, subtract it from) the balance. The interest operation's precondition is true and its effector multiplies the balance by the interest rate. (As we will see later, the analysis shows that the precondition of withdraw needs to be strengthened, and that this effector of interest is unsafe.)

CISE ANALYSIS

Safety Analysis

The first CISE proof obligation, called the effector safety analysis, verifies that the effector of every operation maintains the invariant when applied to any state where the operation's precondition is true (not necessarily the one in which the operation was generated).

Let's try out the effector safety analysis on the simple banking application of Figure 1. According to the analysis, the effectors of deposit and interest always maintain the invariant. However, for withdraw, the obligation fails and our tool produces a counterexample: if the balance is zero, a non-zero withdraw operation makes the balance negative. Therefore, we must fix the issue by strengthening its precondition, so that the amount debited is less or equal than the current balance.

With this correction, the effector safety analysis succeeds. The corrected preconditions are shown at the bottom of Figure 2.

Commutativity Analysis

Effectors of concurrent operations may execute in different orders at different replicas. The second CISE obligation, called the commutativity analysis, checks if all pairs of effectors of such operations commute: executing them in any order yields the same result, whatever the starting state.

Let us check this obligation for the specification in Figure 1. Predictably, applying the commutativity analysis proves that deposit and withdraw effectors commute. However, the effector of interest does not commute with that of the other operations, and the tool returns a counter-example. Consider two replicas 1 and 2. The balance is initially e100. Replica 1 is the origin for an interest operation. Replica 2 is the origin for a deposit(20) operation. Replica 1 first applies the effector of interest and then that of deposit, whereas replica 2 applies them in the opposite order. Depending on the order of execution, the result is different, and the replicas diverge.

We fix this by changing the interest operation to compute the absolute interest at the origin replica and letting its effector add this amount to the local balance of every replica (Figure 2). With this corrected specification, our tool proves that the effector of interest does commute with those of the other operations.

Stability Analysis

The effector safety analysis verified that that the effector of each operation o maintains the invariant when executed in a state satisfying the precondition of the operation. The precondition holds at o's origin replica, but how do we know that it will hold when o's effector is applied at a different replica, which concurrently executes effectors of other operations? The third obligation of CISE analysis, called stability analysis, checks if executing the effector of any other operation o maintains the precondition of o.

Let us illustrate the stability analysis of the withdraw operation in Figure 1. The precondition of the withdraw operation is stable under the effectors of deposit and interest, but it is not stable under the effector of withdraw. The tool returns the following counterexample. Let the balance be e2. The precondition to withdraw(1) is verified. However, a concurrent withdraw(2) (whose precondition is also OK) at a different replica makes the balance zero, now violating the precondition of withdraw(1). If we were to continue, and to apply the effector of the first withdrawal operation at the second replica, the balance would become negative.

To fix the problem, the developer of the banking application may disallow the execution of withdrawals without synchronisation. To model such concurrency control, we use tokens Token = {τ, . . .} and a symmetric conflict relation ⊆ Token × Token between pairs of them. In the banking application, we associate a token τ to withdraw such that τ τ (similarly to a mutual exclusion lock). This ensures that any two withdrawals synchronise.

Figure 2 presents a corrected banking application, incorporating all the changes outlined above. Our static analysis confirms that this application indeed maintains the integrity invariant.

CONCLUSIONS AND FUTURE WORK

We implemented the CISE Tool to automatically discharge the CISE analysis. The tool enables an application developer to check whether her application maintains crucial application invariants, over a replicated database with a given synchronisation protocol.

In the future, we plan to study proof rules for reasoning about integrity invariants on consistency models weaker than causal consistency. We also intend to automate the analysis of counter-examples in order to generate corrections semi-automatically.

σFigure 1 :

 1 Figure 1: A simple banking application (incorrect).

σ

  init = 0 I = balance ≥ 0 Token = {τ } = {(τ, τ )} F deposit(amount) (balance) = (⊥, (λbalance . balance+ amount), ∅) F interest() (balance) = (⊥, (λbalance . (balance + 0.05 * balance)), ∅) F withdraw(amount) (balance) = (⊥, (λbalance . balanceamount), {τ }) Precondition Operation amount ≥ 0 deposit(amount) true interest() balance ≥ amount ≥ 0 withdraw(amount)

Figure 2 :

 2 Figure 2: A corrected banking application.


Matthieu Zimmer

Yann Boniface

Alain Dutech

Boniface Yann

Neural Fitted Actor-Critic

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Reinforcement learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning)[END_REF] is a framework for solving sequential decision problems where an agent interacts with its environment and adapts its policy based on a scalar reward signal. RL agents can autonomously learn difficult tasks, like navigating a maze or playing a video game [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF]. While the basic setting of RL is now well established, a number of researchers have been studying variants where environments with continuous spaces lead to more and more practical problems.

Thus, the purpose of this article is to present an RL algorithm respecting two main requirements : 1) dealing with continuous state and action spaces in order to address more realistic problems, 2) the knowledge added by the designer to the agent should be minimal, to allow the agent to acquire progressively its own representations in a developmental robotics perspective [START_REF] Asada | Cognitive Developmental Robotics : A Survey[END_REF].

Firstly, the common RL background of classical algorithms and their limitations are described. Secondly, the main algorithm of this paper is exposed with an experimental comparison on multiple environments.

Background

Reinforcement learning

RL is a framework that models sequential decision problems, in which an agent learns to take better decisions while interacting with its environment. Once an agent performs an action, the state changes and the agent receives a scalar value, which can be null, called reward, that encodes information about the quality of the actual transition. The goal of the agent is to maximize its long-term expected total reward. The underlying formalism of RL is that of Markov Decision Processes (MDP). An MDP is formally defined as a tuple S, A, T, R where S is a set of states, A a set of actions, T : S × A × S → [0, 1] are transition probabilities between states (T (s, a, s ) = p(s |a, s) is the probability of reaching state s from state s after executing action a) and R : S × A → R is a reward signal. A policy π : S × A → [0, 1] encodes how the agent will behave (the probability to take an action in a given state). An optimal policy π * maximizes the expected discounted reward, that is :

π * = arg max π J(π) = arg max π E ∞ t=0 γ t × R(s t , π t (s t )) (1)
where t denotes a time step and 0 < γ < 1 is a discount factor. In the RL setting, one tries to learn an optimal policy when the model, T and R, is unknown. Such a setting is considered in this paper.

Dealing with continuous state space

When the space S is continuous, classical value-function based RL methods like Least-Squares Temporal Difference (LSTD) [START_REF] Bradtke | Linear least-squares algorithms for temporal difference learning[END_REF] rely on an estimation of Q : S × A → R, the (sequential) values of actions in each state, or V : S → R the value of each state.

Q π (s, a) = E π ∞ k=0 γ k r t+k+1 s t = s, a t = a (2)
This estimation is usually a linear combination of provided basis functions, that must be carefully defined by an expert. Their nature and number limits the expressivity of the learned function. It also impedes the agent's capacity to develop its own representations. In order to minimize the knowledge brought by experts (requirement 2), the use of non-linear functions (like neural networks) will be explored as they have a greater expressiveness range and avoid the a priori definition of basis functions.

Dealing with continuous action space

Critic only : Critic-only methods derive a policy directly from the value function :

π(s) = M (Q, s, A) = arg max a∈A Q(s, a) (3)
where the function M can be the arg max operator, Boltzmann soft max, etc. Several algorithms [START_REF] Sutton | Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning)[END_REF] have been designed with different update rules : Q-Learning, Sarsa, LSTD, etc. Among these, Fitted Q Iteration (FQI) [START_REF] Riedmiller | Neural fitted Q iteration -First experiences with a data efficient neural Reinforcement Learning method[END_REF] is particularly interesting as it uses non-linear neural networks, is data efficient and takes advantage of the Rprop [START_REF] Igel | Improving the Rprop learning algorithm[END_REF][START_REF] Riedmiller | RPROP -A Fast Adaptive Learning Algorithm[END_REF] backpropagation algorithm.

The main issue with critic-only methods is that they are very difficult to apply to continuous action spaces. The argmax operator cannot be used and optimizing the Q function, a linear combination of non-linear basis functions, is a complex task.

Actor-only : On the other side, it is possible to define a parametric policy π θ without value function [START_REF] Sutton | Policy Gradient Methods for Reinforcement Learning with Function Approximation[END_REF]. The goal is to find the best parameters θ according to the cost function J(π θ ) from ( 1) by exploring the finite-dimensional parameter space Θ. Evolutionary algorithms like Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF] or gradient descent are common optimization tools. The major drawbacks of actor-only methods are the high variability of the cost J and, for gradient-based methods, the plateau effect and local minima that can lead to poor policies [START_REF] Grondman | A survey of actor-critic reinforcement learning: Standard and natural policy gradients[END_REF][START_REF] Konda | Actor-Critic Algorithms[END_REF].

Actor Critic : Actor-critic algorithms [START_REF] Konda | Actor-Critic Algorithms[END_REF] try to combine the advantage of both previous methods. The critic learns the value function to reduce the variability of the approximation of J and the actor learns the policy allowing the use of continuous actions. Continuous Actor Critic Learning Automaton (CACLA) is a successful actor-critic algorithm [START_REF] Van Hasselt | Reinforcement learning in continuous action spaces[END_REF] that uses neural networks for both the critic and the actor. However, it is an online algorithm, as such is not data efficient as every experienced interaction is only used once.

Neural Fitted Actor-Critic

Neural Fitted Actor-Critic (NFAC) is a novel actor-critic algorithm whose roots lie in both CACLA and Q-Fitted Iteration. It is an offline actor-critic algorithm that can re-use data and deal with continuous actions. It proceeds in two steps summarized in Figure 1 : 1) given the current policy π, it samples and collects interaction data into D π , 2) improves the critic approximation and actor policy with D π .

Interaction data collection D π is made of several tuple of (s t , u t , a t , r t+1 , s t+1 ). For a state s t , the actor provides the current best action u t , which is slightly altered in an exploration action a t (sometimes equals to u t ), which leads to a new state s t+1 and reward r t+1 .

Neural network estimation

The actor and the critic are implemented using multi-layer neural networks. Their update phases which are detailed below make use of Rprop back-propagation algorithm [START_REF] Igel | Improving the Rprop learning algorithm[END_REF][START_REF] Riedmiller | RPROP -A Fast Adaptive Learning Algorithm[END_REF] which avoids the definition of learning rates.

Critic update

The critic's update relies on several supervised learning iterations as done in FQI. At each iteration k, a learning base {(s t , v k,t )} of (S × R) |Dπ| is built from D π using the current approximation of V k . Each state s t of D π is associated a target v k,t which is either r t+1 + γV k (s t+1 ) or r t+1 when s t+1 is a goal state or absorbing state. Thus V k+1 is computed as follows :

V k+1 = argmin V ∈Fc st∈Dπ V (s t ) -v k,t 2 (4)
F c is the search space of the critic : a subset of learnable functions (for instance a multi-layer perceptrons). The learning base must be rebuilt at each iteration since the targets {v k,t } to learn V k+1 are dependent on V k . Unlike FQI which is off-policy, and because of the actor-critic setting, V is here an on-policy evaluation of the current actor. This implies that D π must be rebuilt after each modification of the actor.

Actor update

The actor update modifies the policy in order to reinforce exploratory actions a t that do better than the current policy actions u t . The actor update relies on the temporal difference error δ t = r t+1 + γV k (s t+1 ) -V (s t ). Since δ t depends on the approximation of V , the actor update is accomplished before the critic update. Like CACLA algorithm, the update is performed towards the exploratory action a t only when δ t > 0. However, the process is not online but done according to D π . A unique database S × A is enough : there is no incremental process as was required with the critic because there isn't a selfdependency in the update formula :

π * = argmin π∈Fa (st,ut,at)∈Dπ π(s t ) -a t 2 , if δ t > 0 π(s t ) -u t 2 , otherwise (5)
Notice that an exploitation case, where a t is equals to u t , could also result in a policy update. Whereas CACLA is online, and can only reinforce an exploration action, here the offline setting of NFAC allows modifying more deeply the policy by trying to reproduce this exploratory action.

1) interactions

2) a. actor update

2) b. critic update Environment u Agent s, r a ∼ π D π δ V 0 {s t , a t } {s t , u t } > 0 ≤ 0 π Rprop {s t , v k,t } V k V k+1 Rprop repeat Fig. 1: Flow diagram of NFAC algorithm.

Experimental Setup

NFAC and CACLA are compared in two continuous environments : Acrobot [START_REF] Spong | Swing up control problem for the acrobot[END_REF] and Cartpole [START_REF] Riedmiller | Evaluation of policy gradient methods and variants on the cart-pole benchmark[END_REF]. Acrobot (double swing-up) is an under actuated arm of two-link. The first joint cannot exert a torque where the second can. It always begins in the same position (straight down). The reward function is defined as 1) +1 if the goal is reached, 2) normalized max height of end effector if 500 steps are reached, 3) 0 otherwise.

Cartpole or inverted pendulum is also made of two joints. The first joint is a pivot point between the cart and the pole, where torques cannot be applied. The other joint controls the horizontal movement of the cart. The reward function is defined as 1) -1 when the pole touches the ground 2) +1 otherwise.

Simulations have been done with the Open Dynamics Engine (ODE) [START_REF] Smith | Open dynamics engine[END_REF] with the following parameters (soft erp : 0.05, soft cfm : 0. As seen in the Figure 2, NFAC has better performance than CACLA. In acrobot, 75% of NFAC agents reach their goal after only 151 episodes where CACLA agents need 544 episodes. The median shows that the quality of the policies found by NFAC are better. After 1000 episodes, 75 % of NFAC agents can reach the goal after only 313 steps versus 453 steps for CACLA.

In cartpole, 25% of NFAC agents can preserve the goal during 500 steps after 623 episodes versus 1419 episodes for CACLA. The median of NFAC is better than CACLA during the first episodes then converge after 2200 episodes.

Statistics have been made over 150 different runs after meta-parameters optimization for each algorithms (the number of hidden units for the policy is the same : 5). -greedy policies are used with acrobot, and Gaussian policies with cartpole. In some environments CACLA has shown better than CMA-ES and Natural Actor-Critic [START_REF] Van Hasselt | Reinforcement Learning in Continuous State and Action Spaces[END_REF].

Conclusions and further work

NFAC is an actor-critic algorithm that considers continuous spaces, using non-linear estimators for both the actor and the critic. It is inspired by CACLA and FQI. Unlike FQI, NFAC can be used in environment with continuous actions. Additionally, conducted experiments showed that NFAC performs better than CACLA with fewer meta-parameters. To further improve NFAC, data collected in previous episodes should be re-used, for instance by using an importance sampling algorithm where the difficulty lies in identifying pertinent data. This algorithm is also a first step towards deep reinforcement learning with continuous action spaces, since it would be able to use neural networks. Additionally, it could be used in a developmental robotic perspective since it requires very little predefined knowledge.

Fig. 2 :

 2 Fig.2: Median and quartile of the best registered performance in Acrobot (lower better) and Cartpole (higher better) environment during RL learning.

* The data has been numerically analyzed with the free software package GNU Octave[START_REF] Smith | Open dynamics engine[END_REF]. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).