Eric Duch Êne

Michel Rigo

CUBIC PISOT UNIT COMBINATORIAL GAMES

Keywords: 2000 Mathematics Subject Classification. Primary: 68R15 ; Secondary: 11A67, 91A46 Combinatorics on words, Two-player combinatorial game, Numeration system, Morphic sequences

Generalized Tribonacci morphisms are defined on a three letters alphabet and generate the so-called generalized Tribonacci words. We present a family of combinatorial removal games on three piles of tokens whose set of P-positions is coded exactly by these generalized Tribonacci words. To obtain this result, we study combinatorial properties of these words like gaps between consecutive identical letters or recursive definition of these words. βnumeration systems are then used to show that these games are tractable, i.e., deciding whether a position is a P-position can be checked in polynomial time.

Introduction

In the game of Nim played on two heaps of tokens, on their turn two players choose a heap and remove any positive number of tokens from that heap. The person making the last move wins. Wythoff 's game is also played with two heaps, the players have the same options as in Nim, or alternatively they may remove the same positive number of tokens from both heaps (Wythoff's rule).

Both Nim and Wythoff's games belong to the family of classical games which are without ties or draws, and where the winner is always the player making the last move. More details on such games can be found in books like [START_REF] Berlekamp | Winning ways (two volumes)[END_REF][START_REF] Conway | On number and games[END_REF]. In a classical game, the set of positions can be partitionned into two parts, according to whether the first or the second player can force a win. This leads to the following definitions: Definition 1. A P-position is one in which the next player has no good move and in an N -position, the next player does have a good move.

From [START_REF] Berlekamp | Winning ways (two volumes)[END_REF][START_REF] Conway | On number and games[END_REF], the set of P-positions of a classical game is characterized by the two following properties:

• Every move from a P-position lands in a N -position.

• From any N -position, there exists a move that leads to a P-position.

The below definition deals with the concept of complexity of a two-players game which is detailed in [START_REF] Fraenkel | Complexity, appeal and challenges of combinatorial games[END_REF]. Definition 2. A game is said to be tractable if the status of a position (i.e., P or N ) can be computed in polynomial time and the winner can consumate a win in at most an exponential number of moves.

We say that a tractable game is polynomial if the next good move (from a Nposition) can also be computed in polynomial time.

The game of Nim is the first classical game for which the polynomiality was proved (see [START_REF] Bouton | Nim, a game with a complete mathematical theory[END_REF]). Wythoff's game is known to be tractable (see [START_REF] Wythoff | A modification of the game of Nim[END_REF]), but the polynomiality has not yet been proved. In the literature, lots of variations of Wythoff's game were investigated. The modifications often concern Wythoff's rule. For example, in the generalized Wythoff 's game (see [START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF]), one can remove k and tokens from both heaps provided |k -| < s, where s is a fixed positive integer. Note that the orginal Wythoff's game is the generalized game of parameter s = 1. In [START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF], the condition k ≤ < 2k + 2 must be satisfied. These two variations of Wythoff's game are proved to be tractable [START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF][START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF]. For Wythoff's game and almost all of its tractable variations, the polynomial characterization of a P-position can be found through the use of an original numeration system. As an example, a game position (a, b), a < b of Wythoff's game is P if and only if its representation in the Fibonacci numeration system is (w, w0), where w is any allowed representation ending with an even number of zeros, see [START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF]. As an illustration, [START_REF] Bertrand-Mathis | Comment écrire les nombres entiers dans une base qui n'est pas entière[END_REF][START_REF] Berlekamp | Winning ways (two volumes)[END_REF] and [START_REF] Bouton | Nim, a game with a complete mathematical theory[END_REF][START_REF] Conway | On number and games[END_REF] are P-positions of Wythoff's game since their representation in the Fibonacci system are respectively [START_REF] Bertrand-Mathis | Comment écrire les nombres entiers dans une base qui n'est pas entière[END_REF][START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF] and (100, 1000).

In addition to this arithmetic characterization, there also exists an "algebraic" polynomial way to compute the P-positions. Indeed, for all n ≥ 0, the nth Pposition of Wythoff's game is ( nτ , nτ 2 ), where τ is the golden ratio. See [START_REF] Wythoff | A modification of the game of Nim[END_REF] for the proof.

The generalized Wythoff's game of parameter s has also its P-positions that can be computed thanks to a numeration system derived from the "generalized Fibonacci" sequence U n+2 = sU n+1 + U n . See more details in [START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF][START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF] about the construction of such numeration systems.

In this paper, we point out a characterization of the P-positions of the generalized Wythoff's game which was not yet considered in the literature. Let s ≥ 1. Consider the "generalized Fibonacci" morphism ζ s : {a, b} → {a, b} * defined by

ζ s : a → a s b b → a
We denote by z (s) the infinite word obtained as z (s) := ζ ω s (a) = lim n→∞ ζ n s (a). As an example, we have z (2) = aabaabaaabaabaaabaabaabaaabaabaaabaabaaba • • • .

For each word z (s) , it turns out that the pairs (a n , b n ) are exactly the P-positions of the generalized Wythoff's game of parameter s, where a n (resp. b n ) is the position of the nth letter a (resp. b) in z (s) . Notice that deciding whether a game position of generalized Wythoff's game is P cannot be done in polynomial time thanks to the word z (s) , unlike the numeration system mentionned above. (A proof of this statement follows the same ideas as the one developped for s = 1 in [START_REF] Duchêne | A morphic approach to combinatorial games: the Tribonacci case[END_REF].)

This "morphic" approach is the ground of the actual paper. Given any morphism ϕ over a finite alphabet {a, b, . . .} such that there exists an infinite word which is the limit of ϕ n (a), we wonder whether there exists a game whose P-positions derive from the word ϕ ω (a), and whose rules are easy to express. Of course, this question might be too ambitious. We restrain ourselves to a family of morphisms. We know that the generalized Fibonacci morphism is related to the generalized Wythoff's game. Therefore it seems natural to investigate the case of morphisms over three letters, and in particular those which do not differ much from the Fibonacci one. In [START_REF] Duchêne | A morphic approach to combinatorial games: the Tribonacci case[END_REF], the Tribonacci morphism was treated. We here consider the following questions about the set of "generalized Tribonacci" morphisms which extend the Tribonacci morphism in the same way as ζ s extends the usual Fibonacci morphism.

• Starting from a generalized Tribonacci morphism, does it exist a game whose P-positions are given by the infinite word produced by the morphism ? • Is it possible to choose the rules of the game such that it defines an extension of generalized Wythoff's game on three heaps ? • Does it exist a numeration system derived from the morphism which allows to compute the P-positions in polynomial time ?

This paper answers positively to these three questions.

This paper is organized as follows. In Section 2, we present the so-called "generalized Tribonacci" morphisms ϕ s , with parameter s ≥ 1, over a three letters alphabet {a, b, c} and we study relevant combinatorial properties of the corresponding generated infinite words (e.g., gaps between two consecutive identical letters, gaps between the nth occurrence of two different letters, recursive definition of the "generalized Tribonacci" words given by Proposition 4, particular factors occurring in these words, . . . ). In Section 3, we define a family of games on three piles whose main property -stated as Theorem 7 -is that the set of P-positions is coded by the "generalized Tribonacci" words (Section 5 is devoted to the proof of this property). We call these games Cubic Pisot unit games because the "generalized Tribonacci" morphisms are related to some cubic Pisot unit β > 1, namely to the unique real root of X 3 -sX 2 -X -1, for s ∈ N \ {0, 1} (i.e., the characteric polynomial of the matrix associated with ϕ s is the minimal polynomial of β). In Section 4, we prove the tractability of these games thanks to the machinery coming from β-numeration systems (in particular, we use the fact that if β is a Parry number which is in particular true for Pisot numbers, then the associated β-shift is sofic or of finite type). It turns out that we even get a polynomial time decision procedure for a wider class of morphisms containing the "generalized Tribonacci" morphisms and related to β-numeration systems. The exact formulation of this result is the core of Theorem 10.

Generalized Tribonacci words and their properties

Let us first introduce the "generalized Tribonacci" morphisms and study some properties of the infinite words they generate. Definition 3. Let s ≥ 1. Consider the morphism ϕ s : {a, b, c} → {a, b, c} * defined by

ϕ s :    a → a s b b → ac c → a
We denote by t (s) the infinite word obtained as t (s) := ϕ ω s (a) = lim n→∞ ϕ n s (a). As an example, we have

t (2) = aabaabacaabaabacaabaaabaabacaabaabacaa • • • t (3) = aaabaaabaaabacaaabaaabaaabacaaabaaabaaabacaaabaaaab • • • Remark 1. Notice that the 3 × 3 matrix M =   s 1 0 1 0 1 1 0 0  
whose entries are indexed by a, b, c and where M u,v counts the number of v appearing in ϕ s (u) has -X 3 + sX 2 + X + 1 has characteristic polynomial, u, v ∈ {a, b, c}. This polynomial is the minimal polynomial of a cubic Pisot unit (see Section 4 for definition of a Pisot number; a Pisot unit is a Pisot number β which is a unit of the integer ring of Q[β]) and this explains how we choose the title of this paper.

We use the convention that the nth letter of t (s) is written t

(s)
n and its first letter has index 1. For X = A, B, C (resp. x = a, b, c), define the sets

X (s) = {X (s) 1 < X (s) 2 < X (s) 3 < • • • } = {n ∈ N | t (s) n = x} Moreover we set A (s) 0 = B (s) 0 = C (s) 0 = 0.
Example 1. For s = 3, the first values of the three sequences (A

(3) n ) n≥0 , (B (3) n ) n≥0 and (C (3) n ) n≥0 are given in
n ) n≥0 , (B (3) n ) n≥0 and (C (3) n ) n≥0 . Remark 2.
In what follows, for convenience we will omit the reference to s and use notation like t, ϕ, (A n ) n≥0 , (B n ) n≥0 and (C n ) n≥0 being understood that s is fixed and given once and for all.

Definition 4. For X = A, B, C (resp. x = a, b, c), we define ∆ n (x) := X n+1 -X n .
For convenience, we define three triples of integers that will be extensively used through all the paper.

G 1 := (1, s + 1, s 2 + s + 2) G 2 := (2, s + 2, s 2 + 2s + 3) M := (2, s + 3, s 2 + 2s + 4).
Lemma 1. For all n ≥ 0, we have

(∆ n (a), ∆ n (b), ∆ n (c)) ∈ {G 1 , G 2 , M }.
Proof. The case n = 0 is checked by direct inspection. Since t = ϕ(t), each factor ax (with x a letter) occurring in t produces a factor u = ϕ(a)ϕ(x) = a s bϕ(x) inside t. Assume that the first a in u is the nth occurrence of a in t, n ≥ 1. Therefore ∆ n (a) = • • • = ∆ n+s-2 (a) = 1. Moreover, since the image of any letter x by ϕ starts with a, we also have ∆ n+s-1 (a) = 2. In the same way, each factor bx (resp. cx) produces a factor u = acϕ(x) (resp. u = aϕ(x)). Therefore, if the first a in u is the nth occurrence of a in t, then ∆ n (a) = 2 (resp. ∆ n (a) = 1). Let us define

θ a : {a, b, c} → N * :    a → 1 s-1 2 b → 2 c → 1
It is clear that (∆ n (a)) n≥0 = θ a (t). The same idea can be applied to obtain (∆ n (b)) n≥0 (resp. (∆ n (c)) n≥0 ). It is enough to observe that t = ϕ 2 (t) (resp. t = ϕ 3 (t)) and that the first occurrence of b (resp. c) in ϕ 2 (x) (resp. ϕ 3 (x)) appears in position s + 1 (resp. s 2 + s + 2) for all x = a, b, c. We define

θ b : {a, b, c} → N * :    a → (s + 1) s-1 (s + 3) b → (s + 2) c → (s + 1)
and

θ c : {a, b, c} → N * :    a → (s 2 + s + 2) s-1 (s 2 + 2s + 4) b → (s 2 + 2s + 3) c → (s 2 + s + 2) such that (∆ n (b)) n≥0 = θ b (t) and (∆ n (c)) n≥0 = θ c (t). The conclusion follows from the fact that |θ a (x)| = |θ b (x)| = |θ c (x)| for all x = a, b, c.
As a consequence of the previous lemma, the sequence (∆ n (a), ∆ n (b), ∆ n (c)) n≥0 is an infinite word over the alphabet {G 1 , G 2 , M }. We will show that this infinite word can be derived from t. Definition 5. We denote by ψ : {a, b, c} → {G 1 , G 2 , M } * the morphism given by ψ :

   a → G s-1 1 M b → G 2 c → G 1
The following result is an easy consequence of the arguments given in the proof of Lemma 1.

Lemma 2. With the above notation, we have

w := G 1 ψ(t) = ((∆ n (a), ∆ n (b), ∆ n (c))) n≥0 .
Proof. From the definition of ψ, θ a , θ b and θ c , we clearly have

ψ(t) = ((∆ n (a), ∆ n (b), ∆ n (c))) n≥1 .
Moreover by computing the prefix ϕ 2 (a) of t, it can checked that (A

1 , B 1 , C 1 ) = G 1 . Corollary 1. The sequences (B n -A n ) n≥0 and (C n -B n ) n≥0 are increasing. Proof. Observe that ∆ n (b) -∆ n (a) > 0 and ∆ n (c) -∆ n (b) > 0.
Remark 3. In fact, the sequences (B n -A n ) n≥0 and (C n -B n ) n≥0 can again be derived from t thanks respectively to the morphisms

µ 1 :    a → s s-1 (s + 1) b → s c → s and µ 2 :    a → (s 2 + 1) s-1 (s 2 + s + 1) b → (s 2 + s + 1) c → (s 2 + 1)
These two morphisms are easily obtained from θ a , θ b and θ c . Notice also that |ψ(x)| = |µ 1 (x)| = |µ 2 (x)| for x = a, b, c and ψ(a), µ 1 (a) and µ 2 (a) have the same form

x s-1 y. Consequently, (B n -A n )-(B n-1 -A n-1 ) or (C n -B n )-(C n-1 -B n-1 )
depends only on the (n -1)-st letter in w :

w n-1 (B n -A n ) -(B n-1 -A n-1 ) (C n -B n ) -(C n-1 -B n-1 ) G 1 s s 2 + 1 G 2 s s 2 + s + 1 M s + 1 s 2 + s + 1
See for instance Example 2 for an illustration.

The following result gives some informations about the language, i.e., the set of factors, of t.

Corollary 2. Any factor of w = ((∆ n (a), ∆ n (b), ∆ n (c))) n≥0 which contains i) δ M 's contains at least (s -1)(δ -1) G 1 's, ii) 2 G 2 's contains at least s M 's. Proof. Consider a factor u of ((∆ n (a), ∆ n (b), ∆ n (c))) n≥0 = G 1 ψ(t). i) Assume u contains δ M 's.
From the definition of ψ, any occurrence of M in w is preceded by at least s -1 letters G 1 . Since u is a factor of w it contains at least (s -1)(δ -1) G 1 's. ii) Assume u = xG 2 yG 2 z. Since ψ(b) = G 2 and G 2 does not occur in ψ(a)

or ψ(c), there exists a unique factor bqb of t such that ψ(bqb) = G 2 yG 2 .

Observe that in t, any letter b is preceded by at least s letters a. So ψ(q) contains at least s letters M .

The elements occurring in the sequence (C n -B n ) n≥0 are strongly related to some of the elements in the sequence (B n -A n ) n≥0 . The relationship is explained in the next two lemmas and summarized by Corollary 3.

Lemma 3. For all m ≥ 1, there exists a unique n such that

C m -B m = B n -A n + 1. Moreover n satisfies A n = B m -1 and (∆ n (a), ∆ n (b), ∆ n (c)) = M .
Proof. Observe that the mth occurrence of c in t appears in the image by ϕ of the mth b. Due to the definition of ϕ, each occurrence of b in t is preceded and followed by a. Let u = aba be the factor containing the mth b in t. Hence the mth letter c of t appears in the factor ϕ(u) = a s-1 baca s-1 b. Let n be the such that the first occurrence of b in ϕ(u) is the nth occurrence of b in t. Since the nth occurrence of b in t appears in the image by ϕ of the nth occurrence of a, this means that the first a in u is nth a in t.

t = • • • n | a m | b a u • • • s a • • • a n | b a m | c s a • • • a b ϕ(u) Collecting these informations, we get C m -B m = B n -A n + 1, A n = B m -1, ∆ n (a) =
B k -A k ) k≥0 is increasing. Lemma 4. For all n such that (∆ n (a), ∆ n (b), ∆ n (c)) = M , i.e., such that (B n+1 - A n+1 ) -(B n -A n ) = s + 1, there exists m ≤ n such that B n -A n = C m -B m -1. Moreover n satisfies A n = B m -1.
Proof. Observe that the nth occurrence of b in t appears in the image by ϕ of the nth a. Since ∆ n (a) = 2, consider u = axa the factor of length 3 starting with the nth occurrence of a in t with x ∈ {b, c}. Therefore, ϕ(u) = a s bϕ(x)a s b where the first b in ϕ(u) is the nth b in t. Since ∆ n (b) = s + 3, we conclude that |ϕ(x)| = 2. Therefore x = b and ϕ(u) = a s baca s b. Let m be such that the b occurring in u is the mth b in t. In other words, the c in ϕ(u) is the mth c in t and the conclusion follows easily.

Putting together the previous two lemmas, we can formulate the following result.

Corollary 3. The sets {C i -B i | i ≥ 1} and {B j -A j + 1 | j : (∆ j (a), ∆ j (b), ∆ j (c)) = M } are the same.
Example 2. We continue Example 1 by taking s = 3. The correspondence given by the previous corollary is shown by using bold face letters.

j
(∆ j (a), ∆ j (b), ∆ j (c)) G 1 G 1 G 1 M G 1 G 1 M G 1 G 1 M G 2 G 1
Let U be a subset of N. The value Mex(U ) which stands for Minimum EXcluded value [START_REF] Berlekamp | Winning ways (two volumes)[END_REF] is the least nonnegative integer not in U . For instance, Mex({0, 1, 3, 9}) = 2. As for the generalized Fibonacci words [START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF], the next result presents a recursive definition of the generalized Tribonacci words.

Proposition 4. For n ≥ 1, A n = Mex({A i , B i , C i : 0 ≤ i < n}) B n = A n + Mex({0, 1, . . . , B n-1 -A n-1 } ∪ {C i -B i : 0 ≤ i < n}) + s -1 C n = sA n + B n + (s 2 -s + 1)n.
Proof. Proceed by induction on n.

For n = 1, A 1 = Mex({A 0 , B 0 , C 0 }) = Mex({0}) = 1, B 1 = A 1 + Mex({0}) + s -1 = s + 1, C 1 = s 2 + s + 2.
Assume that the three relations hold for n ≥ 1 and let us prove that it still holds for n + 1.

The kth letter a in t produces through ϕ the kth b which itself produces the kth c. This means that

A k < B k < C k for all k > 0. Consider the set {A i , B i , C i : 0 ≤ i ≤ n}.
The first gap inside this set must be filled with A n+1 . Indeed, filling this gap with some A n+ , > 1, would contradict the fact that the sequence (A k ) k≥0 is increasing. Filling this gap with some

B n+ or C n+ , ≥ 1, contradict the fact that A k < B k < C k for all k > 0. Hence A n+1 = Mex({A i , B i , C i : 0 ≤ i < n + 1}).
To prove the second part, let us consider two cases.

• Assume that (∆ n (a), ∆ n (b), ∆ n (c)) ∈ {G 1 , G 2 }. This means that B n+1 - A n+1 = B n -A n +s. From Corollary 3, we know that B n -A n +1 = C i -B i
for all i ≥ 0. Therefore, we trivially have

B n -A n + 1 = Mex({0, 1, . . . , B n -A n } ∪ {C i -B i : 0 ≤ i ≤ n}.
Consequently,

B n+1 -A n+1 = Mex({0, 1, . . . , B n -A n } ∪ {C i -B i : 0 ≤ i ≤ n}) + s -1. • Assume now that (∆ n (a), ∆ n (b), ∆ n (c)) = M . This means that B n+1 - A n+1 = B n -A n + s + 1. From Lemma 4, there exists m ≤ n such that B n -A n + 1 = C m -B m . Moreover B n -A n + 2 does not belong to {C i -B i | i ≥ 0} because for all k ≥ 0, C k+1 -B k+1 -(C k -B k ) ≥ 1+s 2 ≥ 2. Hence B n -A n + 2 = Mex({0, 1, . . . , B n -A n } ∪ {C i -B i : 0 ≤ i ≤ n}).
Consequently,

B n+1 -A n+1 = Mex({0, 1, . . . , B n -A n } ∪ {C i -B i : 0 ≤ i ≤ n}) + s -1.
Let us consider the third relation. By induction hypothesis,

C n = sA n + B n + (s 2 -s + 1)n. Assume (∆ n (a), ∆ n (b), ∆ n (c)) = G 1 . Therefore A n+1 = A n + 1, B n+1 = B n +1+S, C n+1 = C n +2+s+s 2
. By substitution, one can easily check that the relation holds for n+1 and the same can be done when

(∆ n (a), ∆ n (b), ∆ n (c)) = G 2 or M . Corollary 5. For s ≥ 2, the sets {B i -A i | i > 0} and {C i -B i | i > 0} are disjoint. Proof. Let n > 0. Using Lemma 3, there exists m such that C n -B n = B m -A m +1. From Lemma 2, for any k ≥ 0, B k+1 -A k+1 -(B k -A k ) ≥ s. Consequently, C n -B n does not belong to {B i -A i | i > 0}. Lemma 5. Let us define f : N → N : n → C n -A n -sB n . We have f (N) = N. Moreover, if f (j) -f (i) ≥ s -1, then j > i.
The function f also satisfies the following property:

(1)

f (t) = n ⇒ (∀y < n, ∃x < t : f (x) = y). - 6 Graph of f for s = 3. - B B B B B B B B B B B B B B n f (n) Graph of f for s = 5.
Proof. Let g :

N 3 → N : (x, y, z) → z -x -sy. Notice g(G 1 ) = g(G 2 ) = 1 and g(M ) = -s + 2. Since (A n , B n , C n ) = n-1 i=0 (∆ a (i), ∆ b (i), ∆ c (i)) = n-1 i=0 w i then f (n) = g(A n , B n , C n ) = g n-1 i=0 w i = n-1 i=0 g(w i ). Therefore, if w n-1 ∈ {G 1 , G 2 } then f (n) = f (n -1) + 1 and if w n-1 = M then f (n) = f (n -1) -s + 2.
The word w has G s 1 as prefix and after each M appear at least s -1 letters G 1 before the next M . Roughly speaking, when increasing the function f is increased by one unit at each step and when it falls down of s -2 units it is immediately followed by at least s -1 increasing steps. The conclusion follows easily.

A combinatorial game with generalized Tribonacci words coding P-positions

This short section is primarily devoted to the definition of a family of combinatorial game with parameter s. We aim to show that the sets of P-positions are coded by t (s) . Fact 6. For any nonnegative integers i 1 , i 2 , i 3 , the following linear system of equations

(2)   i 1 i 2 i 3   =   1 2 2 1 + s 2 + s 3 + s 2 + s + s 2 3 + 2s + s 2 4 + 2s + s 2     µ ν δ  
has a unique solution because the determinant of the matrix equals s 2s + 1 and is nonzero.

Definition 6. Let us defined a subset M al(s) of N 3 as follows {µG 1 +νG 2 +δM : 0 ≤ ν ≤ 1, 1 ≤ δ ≤ s-1 and (δ -1)(s-1) ≤ µ ≤ δ(s-2)-ν}. Notice that if (i 1 , i 2 , i 3 ) belongs to M al(s) then i 1 < i 2 < i 3 and i 3 ≤ s i 2 + i 1 .
Moreover, testing whether a triple (i 1 , i 2 , i 3 ) belongs to M al(s) reduces to the resolution of the system (2) and checking whether the solution (µ, ν, δ) has integer components satisfying the conditions of M al(s). Consequently, one can check that #M al(s) = s 2 -2s + 1. The notation M al(s) stems from "malicious" because this set is strongly related with forbidden moves in the game defined below. Definition 7. Let s ≥ 1. We define Cubic(s) as the removal game on three piles with the following rules. We denote positions of Cubic(s) by (a, b, c), with 0 ≤ a ≤ b ≤ c.

I. Any positive number of tokens from up to two piles can be removed. II. Let i 1 , i 2 , i 3 be positive integers. Let σ be a permutation of {1, 2, 3} such that i σ(1) ≤ i σ(2) ≤ i σ(3) . From position (a, b, c) with 0 ≤ a ≤ b ≤ c, one can remove i 1 , i 2 and i 3 tokens from the piles consisting of a, b and c tokens respectively, subject to the conditions:

i σ(3) ≤ s i σ(2) + i σ(1)
,

(i σ(1) , i σ(2) , i σ(3) ) ∈ M al(s) and b -i 2 < a -i 1 < c -i 3 is forbidden. III. Let i 1 , i 2 , i 3 be positive integers. Let σ be a permutation of {1, 2, 3} such that i σ(1) ≤ i σ(2) ≤ i σ(3)
. From position (a, b, c) with 0 ≤ a ≤ b ≤ c, one can remove i 1 , i 2 and i 3 tokens from the piles consisting of a, b and c respectively, subject to the conditions:

(3) |i σ(1) -i σ(2) | < s or |i σ(2) -i σ(3) | < s and a -i 1 < c -i 3 < b -i 2 is forbidden.
The (normal) convention is that the first player who is unable to move, loses the game.

Remark 4. Notice that Cubic(1) was studied in [START_REF] Duchêne | A morphic approach to combinatorial games: the Tribonacci case[END_REF]. One can see that the rules defined above coincide with those of [START_REF] Duchêne | A morphic approach to combinatorial games: the Tribonacci case[END_REF] We are now able to state precisely our main result linking the cubic Pisot unit games with the "generalized Tribonacci" words. To lighten the presentation its proof is postponed to Section 5.

Theorem 7. Let s ≥ 1. The set P (s) = {(A (s) n , B (s) n , C (s) n ) | n ≥ 0} is the set of P -positions of the Cubic(s) game.
To conclude this section, let us consider a technical lemma that will be used in Section 5 to prove Theorem 7.

Lemma 6. Let w = w 0 w 1 • • • = G 1 ψ(t) = ((∆ n (a), ∆ n (b), ∆ n (c))) n≥0
. For all n < 1 + s(s -1), we have n = 1 + q.s + r with 1 ≤ q ≤ s -2 and 0 ≤ r ≤ a -2 and the smallest k < n such that

(A n , B n , C n ) -(A k , B k , C k ) = n-1 i=k w i ∈ M al(s) satisfies k ≥ 1 + q + r. Moreover, for all n ≥ 1 + s(s -1), the smallest k < n such that (A n , B n , C n ) -(A k , B k , C k ) = n-1 i=k w i ∈ M al(s) satisfies k ≥ n -(s -1) 2 .
Proof. Let us extend the map g introduced in the proof Lemma 5 to an additive map g :

{G 1 , G 2 , M } * → Z. Recall that g(G 1 ) = g(G 2 ) = 1 and g(M ) = -s + 2 and for y 1 • • • y ∈ {G 1 , G 2 , M } * , we set g(y 1 • • • y ) = i=1 g(y i ). Notice that i=1 y i ∈ M al(s) ⇒ g(y 1 • • • y ) ≤ 0. (A) Let n < 1 + s(s -1)
. Hence we write n = 1 + q.s + r with 1 ≤ q ≤ s -2 and 0 ≤ r ≤ s -2. Notice that the prefix of w of length 1 + s(s -1) is

G 1 (G s-1 1 M ) s-1
and that the factorisation of

w 0 • • • w n-1 is depicted as follows (4) G 1 | s G 1 • • • G 1 M |G 1 • • • G 1 M | • • • |G 1 • • • G 1 M | qs G 1 • • • G 1 r . If i < 1 + q + r, then g(w i • • • w n-1 ) > 0 and (A n , B n , C n ) -(A i , B i , C i ) ∈ M al(s). (B) Let n ≥ 1 + s(s -1). We have to show that g(w i • • • w n-1 ) > 0 for all i < n -(s -1) 2 .
Notice that any factor of length (s -1) 2 contains at most s -1 letters M since any M is preceeded and followed by at least s -

1 letters in {G 1 , G 2 }. If it contains exaxtly s -1 letters M then it is of the form u = M (G s-1 1 M ) s-2 . Observe that g(u) = 0. Let us consider two cases about the factor f = w n-(s-1) 2 • • • w n-1 of w of length (s -1) 2 . Assume first that f contains exactly s -1 letters M . Then f = u and g(f ) = 0. Since the first letter of f is M , this factor is preceeded in w by at least s -1 letters G 1 . Therefore, for all n -(s -1) 2 -s + 1 ≤ i < n -(s -1) 2 , g(w i • • • w n-1 ) = n -(s -1) 2 -i > 0.
Observe that for all factor v in w, g(v) ≥ -s + 2, the minimal value corresponding to v = M . This latter observation combined with the fact that

g(w n-(s-1) 2 -s+1 • • • w n-1 ) = s -1
and that g is additive leads to the conclusion.

Assume now that f contains less than s -1 letters M . Since it contains at most s-2 letters M , we have g(f ) ≥ -(s-2) 2 +(s-1) 2 -(s-2) = s-1. The conclusion follows the same lines.

Numeration systems and tractability of the game

The aim of this section is to prove that Cubic(s) is a tractable game. We have to show that for any given triple t = (a, b, c) of integers, deciding whether t is or not in P (s) can be done in polynomial time (details about the usual meaning of this sentence was given in [START_REF] Duchêne | A morphic approach to combinatorial games: the Tribonacci case[END_REF], i.e., polynomialy with respect to the size of a relevant coding of the instance). In fact, we obtain a result on a larger class of morphisms which contains in particular the generalized Tribonacci morphisms. For the sake of completeness, we first recall some well-known facts about β-numeration systems.

4.1. β-numeration. We collect some facts about β-expansions, more details can be found in [START_REF] Lothaire | Algebraic Combinatorics on words[END_REF]. Let β > 1 be a real number and A β = {0, . . . , β -1}. Any x ∈ [0, 1] can be written as

x = +∞ i=1 c i β -i , with c i ∈ A β , ∀i ≥ 1.
The sequence (c i ) i≥1 is said to be a β-representation of x. Amongst all the possible β-representations of x, the maximal one for the lexicographic order is said to be the β-expansion of x and is denoted d β (x). If d β (1) is finite or ultimately periodic, then β is said to be a Parry number. Lemma 7 (Parry condition [START_REF] Parry | On the β-expansions of real numbers[END_REF]). A sequence (x n ) n≥1 belongs to D β if and only if for all k ≥ 1, (x n ) n≥k < lex d * β (1). As a consequence of this result, if β is a Parry number, one can built in a canonical way a finite deterministic automaton A β recognizing exactly the language F (D β ) (see [START_REF] Frougny | On representation of integers in linear numeration systems[END_REF] for details). For instance, if

If d β (1) = t 1 • • • t m is finite (t m = 0), we set d * β (1) := (t 1 • • • t m-1 (t m - 1
d β (1) = t 1 • • • t m , A β has Q = {1, .
. . , m} as set of states. All states are final and 1 is the initial state. The (partial) transition function δ : Q × A β → Q is defined as follows for 1 ≤ j < m, δ(j, t j ) = j + 1 and for 1 ≤ j ≤ m, δ(j, r) = 1 whenever r < t j . The other transitions are not defined (or go to some "sink state"). The same kind of construction can be done in the ultimately periodic case, the automaton A β has thus a second "component" taking care of the period.

Recall that a Pisot number is an algebraic integer greater than one whose all conjugates have modulus less than one. In particular, any Pisot number is a Parry number. This example can be easily generalizes to the polynomial X 3 -sX 2 -X -1 which has a unique real root which is a Pisot number for all integers s ≥ 1.

Canonical linear recurrent numeration system. To any real number

β > 1, if d * β (1) = t 1 t 2 • • •
, one can canonically associate with β a strictly increasing sequence of integers U β = (u n ) n≥1 defined by ( 5)

u 1 = 1 and ∀n ≥ 1, u n = t 1 u n-1 + • • • + t n u 0 + 1.
Indeed, the sequence is strictly increasing because t 1 ≥ 1 and all the t i 's are nonnegative. It is not difficult to see that this sequence turns out to be linearly recurrent whenever d * β (1) is ultimately periodic. Therefore one can associate with any Parry number β > 1, a canonical positional numeration system built on the linear recurrent sequence

U β . If d β (1) = t 1 • • • t m is finite (t m = 0), the sequence (u n ) n≥0 defined in (5) satisfies u n = t 1 u n-1 + • • • + t m u n-m for all n ≥ m, u 0 = 1 and for 1 ≤ i ≤ m -1, u i = t 1 u i-1 + • • • + t i u 0 + 1. If d β (1) = t 1 • • • t m (t m+1 • • • t m+p
) ω (m and p being chosen minimal), then the sequence (u n ) n≥0 defined in [START_REF] Conway | On number and games[END_REF] satisfies for all n ≥ m + p

u n = t 1 u n-1 + • • • + t m+p u n-m-p + u n-p -t 1 u n-p-1 -• • • -t m u n-m-p , u 0 = 1 and for 1 ≤ i ≤ m + p -1, u i = t 1 u i-1 + • • • + t i u 0 + 1.
Definition 8. Any positive integer x can be greedily decomposed using terms of the sequence U β , x = i=0 x i U i with x = 0, and rep

U β (x) = x • • • x 0 is said to be the U β -representation of x.
By convention, 0 is represented by the empty word ε. Moreover, when β is a Parry number, the so-called Bertrand's Theorem implies that rep

U β (N) = F (D β )
which in particular is recognized by A β (see [START_REF] Bertrand-Mathis | Comment écrire les nombres entiers dans une base qui n'est pas entière[END_REF]). We denote by val U β the function mapping

x • • • x 0 onto i=0 x i U i .
Example 5. We continue Example 4. The sequence associated with β satisfies u 0 = 1, u 1 = 3u 0 + 1 = 4, u 2 = 3u 1 + u 0 + 1 = 14 and for all n ≥ 0,

u n+3 = 3 u n+2 + u n+1 + u n .
So the first terms of U β are 1, 4, 14, 47, 159, . . .. For instance, the U β -representation of 158 is 3103. More generally, the sequence associated with the real root of X 3 -sX 2 -X -1 satisfies u 0 = 1, u 1 = s + 1, u 2 = s 2 + s + 2 and for all n ≥ 0, u n+3 = s u n+2 + u n+1 + u n .

Remark 7. For a Parry number β, the sequence U β counts the number u n of words of length n accepted by A β .

4.3. Morphisms and automata. Let ϕ : A → A * be a morphism and a ∈ A be such that ϕ ω (a) is infinite. Set k := max b∈A |ϕ(b)| and Σ ϕ = {0, . . . , k -1}. To ϕ one can associate in a canonical way a deterministic finite automaton A ϕ (this construction goes back to Cobham in [START_REF] Cobham | Uniform tag sequences[END_REF] where morphisms of constant length are considered). This automaton has the alphabet A as set of states, all states are final, the initial state is a and the transition function δ :

A × Σ ϕ → A is given by for all b ∈ A, if ϕ(b) = µ 0 • • • µ r-1 then δ(b, i) = µ i , i = 0, . . . , r -1.
Notice that by definition of k, we have r ≤ k. We set

L ϕ := L(A ϕ ) \ 0Σ * ϕ
where L(A ϕ ) is the language accepted by A ϕ . The n-th word of L ϕ enumerated by the genealogical ordering induced by the natural ordering of the digits is denoted rep Lϕ (n -1) (indeed, the first word of the language is meant to represent zero and that is the reason for this shift of one). Recall that to order words by genealogical (or radix) ordering, first order words by increasing length and for words of the same length, this ordering coincides with the lexicographical ordering. Moreover, since U β counts the number u n of words of length n accepted by A β where leading zeroes are allowed, u n is also equal to the number of words of length ≤ n in L ϕ . Example 6. The automaton A ϕ3 associated with ϕ 3 is the same as in Figure 1 and the first words (without leading zeroes) of the language accepted by this automaton are ε, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 100, . . . .

Feeding A ϕ3 with these words and starting each time from the state a, gives the sequence of states aaabaaabaaabaca which is a prefix of t (3) . In particular, since A β = A ϕ3 for β given in Example 4, to obtain t

n for any n ≥ 1, one has only to compute the U β -representation of n -1 (with U β the linear sequence given in Example 5) and feed the automaton A ϕ3 with this representation rep U β (n -1).

The reached state δ(a, rep

U β (n -1)) is t (3) n .
Proposition 9. Let ϕ : A → A * be a morphism and a ∈ A be such that ϕ ω (a) =

t 1 t 2 • • • is infinite. With the above notation, if t n = b and ϕ(b) = µ 0 • • • µ r-1 then δ(a, rep Lϕ (n -1) i) = µ i , ∀i = 0, . . . , r -1.
Proof. This is a direct consequence of the definition of the automaton A ϕ . Observe that L ϕ is a prefix-closed language. If w ∈ L ϕ is such that δ(a 1 , w) = b with ϕ(b) = µ 0 • • • µ r-1 , then w can be extended to exactly r words of length |w| + 1 in L ϕ : w0, . . . , w(r -1). Roughly speaking, each word w in L ϕ corresponds to exactly one letter b in ϕ ω (a). Through ϕ this letter b produces a word ϕ(b) which corresponds exactly to the words w0, . . . , w(|ϕ(b)| -1) ∈ L ϕ . 4.4. Polynomial time decision procedure. Let A = {a 1 , . . . , a }, ϕ : A → A * be a morphism and a 1 ∈ A be such that ϕ ω (a 1 ) = t 1 t 2 • • • is infinite. Assuming that each letter of A appears infinitely often in ϕ ω (a 1 ), we denote by A i,n the position of the n-th letter a i in ϕ ω (a 1 ), i = 1, . . . , .

Theorem 10. Let A = {a 1 , . . . , a }, ϕ : A → A * be a morphism and a 1 ∈ A be such that ϕ ω (a 1 ) = t 1 t 2 • • • is infinite. Assume that there exists a Pisot number β such that A ϕ = A β and that the characteristic polynomial of U β is the minimal polynomial of β. Given any -tuple

T = (n 1 < • • • < n ) ∈ N
deciding whether there exists k ≥ 1 such that T = (A 1,k , . . . , A ,k ) can be done in polynomial time.

Proof. We will first consider the case where the d β (1) = t 1 • • • t m is finite. Since A ϕ = A β , = m and the morphism ϕ is given (up to a renaming of the letters of A) by ϕ :

             a 1 → a t1 1 a 2 a 2 → a t2 1 a 3 . . . a m-1 → a tm-1 1 a m a m → a tm 1 .
Consequently, all letters of A occur infinitely often in ϕ ω (a 1 ) and the n-th a j+1 is obtained from the n-th a j . Therefore

A 1,n < A 2,n < • • • < A m,n for all n ≥ 1.
The size of the instance is |T | = i log 2 (n i ). By Remark 6, observe that the length of rep U β (n 1 ) is proportional to log β n 1 = log β 2 log 2 n 1 . Therefore computing rep U β (n 1 ) from the binary representation of n 1 can be done in polynomial time with respect to log 2 n 1 .

Observe that reading a word w in A ϕ starting from state a 1 leads to state a 1 if and only if w does not have any prefix of t 1 • • • t m-1 as a nonempty suffix. From Proposition 8, there exists k ≥ 1 such that n 1 = A 1,k if and only if rep U β (n 1 -1) does not have any prefix of t 1 • • • t m-1 as a nonempty suffix. This can again be checked in polynomial time with respect to log 2 n 1 .

For j = 1, . . . , m, if δ(a 1 , rep U β (n -1)) = a j with n = A j,k , using Proposition 9, since ϕ(a j ) = a tj j a j+1 and since the k-th a j+1 is obtained from the k-th a j , we get

δ(a 1 , rep U β (n -1) t j ) = a j+1 and val U β (rep U β (n -1) t j ) + 1 = A j+1,k . Consequently, if there exists k ≥ 1 such that n 1 = A 1,k , one has still to check wether          val U β (rep U β (n 1 -1)t 1 ) + 1 = n 2 val U β (rep U β (n 1 -1)t 1 t 2 ) + 1 = n 3 . . . val U β (rep U β (n 1 -1)t 1 t 2 • • • t m-1 ) + 1 = n m .
To conclude observe that val U β (w) can be computed in polynomial time exactly as rep U β is.

The case where

d β (1) = t 1 • • • t m (t m+1 • • • t m+p )
ω is ultimately periodic follows essentially the same scheme. The main difference is that the form of automaton A β is a little more complicated because it has an extra component which takes into account the periodic part of d β (1) (see for instance [START_REF] Frougny | On representation of integers in linear numeration systems[END_REF]). But again, we can deduce from its form that the n-th a j+1 is obtained from the n-th a j . The criterion to determine whether there exists k ≥ 1 such that n

1 = A 1,k is that rep U β (n 1 -1) should not have any prefix of t 1 • • • t m (t m+1 • • • t m+p ) ω
as a nonempty suffix. The end of the proof can then be easily adapted.

Example 7. Consider again the morphism ϕ 3 which satisfies the assumptions of the previous theorem. The sequence associated with β is given in Example 5. To check that (20, 69, 234) is of the form (A

(3) n , B (3) n , C (3)
n ) for some n, we proceed as follows. First we compute rep U β (19) = 111 and observe that 3 and 31 are not suffixes of 111 (recall that d β (1) = 311). Then we check that val U β (1113) = 68 and val U β (11131) = 234.

To conclude this section, we simply have to observe that the morphism associated with Cubic(s) belongs to the family of morphisms described in the previous theorem.

Proof of Theorem 7

Proof. In [START_REF] Duchêne | A morphic approach to combinatorial games: the Tribonacci case[END_REF] the result is proved for s = 1. Let us therefore fix s ≥ 2. Throughout this proof, we will omit reference to s which is given once and for all. We proceed in two steps:

• Whatever the chosen rule is, a player moving from a position (A n , B n , C n ) in P always lands in a position not in P. • Given a position (a, b, c) not in P, there exists a move to some (A n , B n , C n ) ∈ P. Let us first introduce some notations to simplify our presentation. Remember to specify that the position (x, y, z) is obtained from (a, b, c) using rule R. As an example, we write [START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF]22,30) 12,0,20 -→ [0, 22, 10] = (0, 10, 22) and [START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF]22,30) I -→ (0, 10, 22).

• First part of the proof. Assume that a player moves from a position (A n , B n , C n ) in P to another position (A m , B m , C m ) in P. Since the three sequences (A i ) i≥0 , (B i ) i≥0 , (C i ) i≥0 are increasing, we have m < n. We show that such a move never occurs by considering the possible application of the different rules.

First, we cannot have

(A n , B n , C n ) I -→ (A m , B m , C m ).
Indeed none of the elements in the first triple is equal to any element of the second triple because

{A j | j ≥ 1} ∪ {B j | j ≥ 1} ∪ {C j | j ≥ 1} is a partition of N ≥1 .
The application of rule I would imply that at least one pile remains unchanged.

Assume now that

(A n , B n , C n ) II -→ (A m , B m , C m ). a)
As a first case, suppose that the resulting position has been obtained from

(A n , B n , C n ) α,β,γ -→ [A m , B m , C m ] = (A m , B m , C m )
with α, β, γ > 0 satisfying the conditions of rule II. In view of Lemma 1, there exist nonnegative coefficients µ, ν, δ such that

(6) (α, β, γ) = (A n -A m , B n -B m , C n -C m ) = µG 1 + νG 2 + δM.
Observe that the three coordinates of G 1 (resp. G 2 , M ) are ordered by increasing order. Therefore α < β < γ and since rule II is satisfied, we know that γ ≤ s β + α. Substituting in (6) G 1 , G 2 and M with their values from Definition 4, this latter inequality can be rewritten as

(7) µ ≤ (s -2) δ -ν.
From [START_REF] Frougny | On representation of integers in linear numeration systems[END_REF], δ = 0 would imply µ = ν = 0 which is impossible since m < n. Hence δ ≥ 1. From Corollary 2, we know that µ ≥ (s -1)(δ -1). Therefore, we get from (7) that δ ≤ s -1. By Corollary 2, ν ≥ 2 would imply δ ≥ s which contradicts the latter inequality. Hence we have ν ∈ {0, 1}. Putting together all the informations on µ, ν and δ, the triple (α, β, γ) belongs to M al(s) which contradicts the fact that rule II has been applied. b) As a second case, assume that the position

(A m , B m , C m ) has been obtained from (A n , B n , C n ) α,β,γ -→ [x, y, z] = (A m , B m , C m ). Otherwise stated [x, y, z] is a non-trivial permutation of (A m , B m , C m ). Observe that z = C m , because rule II forbids [x, y, z] = [B m , A m , C m ]. Since for X = A, B, C, we have X n > X m , there exist some 0 < α < β < γ such that (A n , B n , C n ) α ,β ,γ -→ [A m , B m , C m ] = (A m , B m , C m ).
In view of a), we have either γ > sβ + α or (α , β , γ ) ∈ M al(s). Moreover observe that [START_REF] Fraenkel | A generalization of Wythoff's game[END_REF] α

+ β + γ = α + β + γ . b.1) Assume that γ > sβ + α . b.1.1)
We first treat the following situations. Assume [x, y, z] equals either to

[A m , C m , B m ], [B m , C m , A m ] or [C m , B m , A m ]. Hence α ≤ α , β ≤ β and γ > γ .
Since γ > β > α , we have to consider two cases:

• if α ≤ β < γ, then γ > γ > sβ + α ≥ sβ + α which contradicts the fact that rule II is applied; • if β < α < γ, then γ > γ > sβ + α ≥ sα + β ≥ sα + β which leads to the same contradiction. b.1.2) The last case is [x, y, z] = [C m , A m , B m ]. Hence α < α , β > β and γ > γ . There exist µ, ν, δ ≥ 0 such that (A m , B m , C m ) = µG 1 + νG 2 + δM. Notice that γ -γ = C m -B m = µ(1 + s 2 ) + (δ + ν)(1 + s + s 2 ).
In the same way, sβsβ = s(B m -A m ) = (µ + ν)s 2 + δ(s + s 2 ). Hence we get sβ -sβ ≤ γ -γ . We have γ > sβ +α and adding γ -γ on the l.h.s. and sβ -sβ on the r.h.s., we get γ > sβ + α . Since α < α , we conclude that γ > sβ + α which contradicts rule II because we have α < β < γ (indeed, α < α < β < β).

b.2) We still have to consider the case (α , β , γ ) ∈ M al(s). b.2.1) Assume that n = 1+s(s-1). From Lemma 6, we have m ≥ n-(s-1) 2 = s. We will now show that for all s ≤ k < n, C k > B n .

From Lemma 2 and by computing the prefix of length n = 1+s(s-1) of G 1 ψ(t), we deduce that

(A n , B n , C n ) = (s -1)M + (1 + (s -1) 2 )G 1 and (A s , B s , C s ) = sG 1 . Hence B n -B s = s 3 -s 2 + s -1 and C s -B s = s 3 + s. Therefore C s > B n . Since (C k ) k≥0 is increasing, we have C k > B n
for all k ≥ s. In particular, it holds for k = m, C m > B n . Moreover since B n > A n and C m is equal to x or y, this would mean α < 0 or β < 0 which is a contradiction. b.2.2) Assume that n = 1 + s(s -1) + t with t > 0. Again, from Lemma 6, we have m ≥ s + t. From the previous point, we already know that C s > B 1+s(s-1) . According to Lemma 2, notice that for s ≥ 1, the third component of G 1 , G 2 or M is greater or equal than the second component of any of these elements. Therefore, C i > B j implies C i+t > B j+t for all t ≥ 0 and in particular, we have

C s+t > B 1+s(s-1)+t = B n . Since (C k ) k≥0 is increasing, we have C k > B n for all k ≥ s + t.
In particular, it holds for k = m, C m > B n and we conclude as in the previous case.

b.2.3) Assume that n < 1 + s(s -1). We have

n = 1 + q.s + r, with 1 ≤ q ≤ s -2, 0 ≤ r ≤ s -2.
From the first part of Lemma 6, we get m ≥ 1 + q + r.

As usual w = G 1 ψ(t) = w 1 w 2 • • • . Assume first r = 0. Since 1 + q ≤ s -1 and w 1 • • • w 1+q = (G 1 ) 1+q
, we obtain from Lemma 2 that C 1+q -B 1+q = (s 2 + 1)(1 + q). From (4), in w 1+q • • • w n there are exactly q letters M and q(s -2) letters G 1 . Hence from Lemma 2, we have B n -B 1+q = q(s 2 + 1). We deduce that

C 1+q -B n = (C 1+q -B 1+q ) -(B n -B 1+q ) = s 2 + 1 > 0. Since (C k ) k≥0 is increasing, we have C m -B n > 0 for all m ≥ 1 + q.
If r > 0, from the above discussion, we know that C 1+q > B n-r . As in the previous point, we conclude that C 1+q+r > B n . As before, since (C k ) k≥0 is increasing, we have C m -B n > 0 for all m ≥ 1 + q + r.

Assume now that

(A n , B n , C n ) III -→ (A m , B m , C m ).
The resulting position has been obtained from

(A n , B n , C n ) α,β,γ -→ [x, y, z] where [x, y, z] is a permutation of [A m , B m , C m ].
We have five cases to consider depending on which permutation of (A m , B m , C m ) corresponds to the reordering of [x, y, z] (remember that one permutation is forbidden with rule III). With the same reasoning as before, there exist α , β , γ > 0 such that

(A n , B n , C n ) α ,β ,γ -→ [A m , B m , C m ] = (A m , B m , C m ).
From Lemma 2, we have

β > α + s -1, γ > β + s -1, γ ≥ α + β .
because these inequalities are satisfied for the corresponding components of G 1 , G 2 , M .

γ -s -β < β -β = α -α ≤ α
where the central equality comes from [START_REF] Fraenkel | A generalization of Wythoff's game[END_REF]. Consequently, we get

(9) γ -α -β < s. Notice now that (α , β , γ ) = (A n -A m , B n -B m , C n -C m ) = µG 1 + νG 2 + δM
for some nonnegative coefficients µ, ν, δ. From Lemma 2, we obtain γαβ = µs 2 + (ν + δ)(s 2 + s -1) ≥ s which contradicts [START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF].

B n -A n = Mex({0, 1, . . . , B n-1 -A n-1 } ∪ {C i -B i : 0 ≤ i < n}) + s -1.
Assume first that C m -B m < B n-1 -A n-1 . In view of the above formula,

B n -A n ≥ B n-1 -A n-1 + s > C m -B m + s which is a contradiction. Assume now that B n-1 -A n-1 < C m -B m < B n -A n . In view of Lemma 3, we necessarily have C m -B m = B n-1 -A n-1 + 1. Notice that Mex({0, 1, . . . , B n-1 -A n-1 } ∪ {C i -B i : 0 ≤ i < n}) ≥ B n-1 -A n-1 + 2.
Consequently, we obtain

B n -A n ≥ C m -B m + s
which is also a contradiction.

As a last case, assume that

C m -B m > B n -A n . From Lemma 3, there exists k such that C m -B m = B k -A k + 1 and A k = B m -1. If k > n then according to Lemma 2, (C m -B m ) -(B n -A n ) ≥ s which is a contradiction. Consequently, the only remaining case is k = n which implies that A n = B m -1 which is a contradiction with the move (A n , B n , C n ) → [B m , C m , A m ]. (e) If [x, y, z] = [C m , A m , B m ], then α < α , β > β and γ > γ . The only possibility to apply rule III is |γ -β| < s but γ -β = γ -β + (C m -B m ) -(B m -A m ) ≥ s + (C m -B m ) -(B m -A m ) ≥ s.
Notice that last inequality comes from the fact C i -B i ≥ B i -A i for all i.

• Second part of the proof. Let (x, y, z) be a position not in P with x ≤ y ≤ z. Our aim is to show that there exists an allowed move from (x, y, z) to some element in P.

Note that when rule I or rule III is applied, the corresponding moves do not belong to M al(s).

There are a few cases that we can directly deal with:

• If x = 0, then (x, y, z) I -→ (0, 0, 0). • If |x -y| < s or |z -y| < s, then (x, y, z) III -→ (0, 0, 0). • If z ≤ x + sy and (x, y, z) ∈ M al(s), then (x, y, z) II -→ (0, 0, 0). • If z ≤ x+sy and (x, y, z) ∈ M al(s). There exist nonnegative integers µ, ν, δ such that (x, y, z)

= µG 1 + νG 2 + δM with 0 ≤ ν ≤ 1, 1 ≤ δ ≤ s -1 and (δ -1)(s -1) ≤ µ ≤ δ(s -2) -ν. Now consider (x , y , z ) = (µ + ν + 1)G 1 + (δ -1)M.
First notice that under these conditions, (x , y , z ) ∈ P because the prefix of (4) of length µ + ν + δ (≤ (s -1) 2 ) contains exactly µ + ν + 1 symbols G 1 and δ -1 symbols M . Since So in all what follows, we may assume that (10)

       x > 0 x + s ≤ y y + s ≤ z z > sy + x
There exists a unique n > 0 such that x is a component of the triple (A n , B n , C n ). We therefore discuss three cases: (b.2) Otherwise z < C n and we will show that this situation never occurs. From Lemma 2, we have B n -A n ≥ sn which leads to [START_REF] Fraenkel | Complexity, appeal and challenges of combinatorial games[END_REF] sB n ≥ sA n + s 2 n.

x = A n , x = B n or x = C n . (a) If x = C n , then A n < B n < C n = x ≤ y ≤ z.
Again Lemma 2 gives C n ≤ A n + B n + n(s 2 + s -1). Moreover, since B n x ≤ y, we have

(1 + s)B n ≤ x + sy < z < C n
and putting these last two inequalities together, we get

sB n < A n + n(s 2 + s -1).
From this last inequality and (11), we obtain A n < n which never occurs.

B m -A m ≤ t = y -x < B n -A n .
From this, Corollary 1 implies that m < n. Moreover m > 0 because

t ≥ s = B 1 -A 1 . Thus A m < A n = x, C m < C n ≤ z and y -x ≥ B m -A m implies that y > B m . Consequently since |t -(B m -A m )| = |y -B m -(x - A m )| < s we play (x, y, z) III -→ [A m , B m , C m ]. (c.2.2) Assume that for all m such that |t -(B m -A m )| < s, we have t < B m -A m . As before, we know that (B m -A m ) -(B m-1 -A m-1 ) ∈ {s, s + 1}. The only case to consider is (B m -A m ) -(B m-1 -A m-1 ) = s + 1 and B m -A m = t + 1.
Indeed, if this is not the case then we would have |t -(B m-1 -A m-1 )| < s and t ≥ B m-1 -A m-1 and we would be in the situation of (c.2.1). So, [START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF], we know that zxsy > 0 and with Lemma 5, we consider the smallest integer m > 0 such that

B m -A m = t + 1 < B n -A n + 1. Since B m -A m ≤ B n -A n , from Corollary 1, we get m ≤ n. Now, From Lemma 4, there exists p such that C p -B p = B m-1 -A m-1 + 1 and from Lemma 3 we know that A m-1 = B p -1. Hence, |y -C p -(x -B p )| = |t -(C p -B p )| = |t -(B m-1 -A m-1 + 1)| = |s -1| < s.

Moreover, we have

x = A n ≥ A m > A m-1 = B p -1, implying z ≥ x ≥ B p > A p , and
C p = t -s + 1 + B p ≤ y -x -s + 1 + x ≤ y. Consequently we play (x, y, z) III -→ [B p , C p , A p ]. (c.3) If y ≥ B n and z < C n . From
z -x -sy = f (m) = C m -A m -sB m .
Moreover, under the considered assumptions we have

f (m) = z -x -sy < C n -A n -sB n = f (n)
then, since m is minimal and from (1), we get m < n. Indeed, if n < m then there exists m < n < m such that f (m ) = f (m) which contradicts the minimality of m. Now we get

z -C m = x + sy -A m -sB m = A n -A m + s(y -B m ) > 0 because A n > A m and y ≥ B n > B m . We set α := x -A m = A n -A m > 0, β := y -B m and γ := z -C m . Since β ≥ B n -B m > A n -A m = α and z -C m γ = y -B m β + A n -A m + (s -1)(y -B m ) >0 we get, 0 < α < β < γ. Moreover, γ = α + sβ.
We will now prove that the move (x, y, z)

II -→ (A m , B m , C m )
is allowed. To do this, it remains to show that (α, β, γ) does not belong to M al(s). We proceed by contradiction and assume that (α, β, γ) ∈ M al(s).

From Lemma 1, there exists nonnegative integers µ, ν, δ such that

(A n -A m , B n -B m , C n -C m ) = µ G 1 + ν G 2 + δ M.
Since (α, β, γ) ∈ M al(s), there exists nonnegative integers µ , ν , δ such that

0 ≤ ν ≤ 1, 1 ≤ δ ≤ s -1, (δ -1)(s -1) ≤ µ ≤ δ (s -2) -ν and (α, β, γ) = (x -A m , y -B m , z -C m ) = µ G 1 + ν G 2 + δ M.
Since y ≥ B n and z < C n , there exist two integers b ≥ 0 and c > 0 such that y = B n + b and z = C nc . Therefore, we get

  µ -µ ν -ν δ -δ   = M -1   0 b -c  
where M is the matrix of the system given in (2) and thus

   (s 2 -s + 1)(µ -µ) = -2 b -2 c (s 2 -s + 1)(ν -ν) = -s 2 b -(s -1) c (s 2 -s + 1)(δ -δ) = (1 + s 2 ) b + s c . Consequently, δ < δ ≤ s-1. The finite word [(∆ k (a), ∆ k (b), ∆ k (c))] m≤k<n over {G 1 , G 2 , M } contains exactly µ (resp. ν, δ) letters G 1 (resp. G 2 , M ).
From the second part of Corollary 2, since δ < s -1, we deduce that ν < 2. Moreover, we have 0 ≤ ν < ν. Therefore, the only case which remains is ν = 1 and ν = 0 and we also obtain that

g(α, β, γ) = (µ + ν + δ )(s 2 -s + 1) > 0 which is a contradiction. If α ≤ β, then since γ = α + sβ we can play (x, y, z) II -→ (A m , B m , C m ) provided (α, β, γ) ∈ M al(s). Assume that (α, β, γ) ∈ M al(s).
From Lemma 1, there exist nonnegative integers µ, ν, δ such that

(A n -A m , B n -B m , C n -C m ) = µ G 1 + ν G 2 + δ M.
Since (α, β, γ) ∈ M al(s), there exist nonnegative integers µ , ν , δ such that

(12) 0 ≤ ν ≤ 1, 1 ≤ δ ≤ s -1, (δ -1)(s -1) ≤ µ ≤ δ (s -2) -ν and (α, β, γ) = (x -A m , y -B m , z -C m ) = µ G 1 + ν G 2 + δ M.
Since y < B n and z < C n , there exist integers b > 0 and c > 0 such that

y = B n -b and z = C n -c . Therefore, we get   µ -µ ν -ν δ -δ   = M -1   0 -b -c  
where M is the matrix of the system given in (2) and   

(s 2 -s + 1)(µ -µ) = 2 b -2 c (s 2 -s + 1)(ν -ν) = s 2 b -(s -1) c (s 2 -s + 1)(δ -δ) = -(1 + s 2 ) b + s c .
Since s 2s + 1 is odd, µµ must be even and therefore we define two integers k := (µµ)/2 and := νν. We can consider the latter system as a system of three equations with two unknowns b and c . The first two equations have a nonzero determinant and are therefore sufficient to obtain the following solution b = -k(s -1) + c = -ks 2 + . From this and the third equation of the system, we deduce that

   µ = µ + 2k ν = ν + δ = δ -k -.
Let us show that ∈ {-1, 0, 1}. Since b > 0, we get (13) > k(s -1).

Since ν ∈ {0, 1}, ν ≥ 0 and ν = ν + , we deduce that ≤ 1. Proceed now by contradiction and assume ≤ -2. In particular, this implies ν ≥ 2 and in view of (13) we also have k < 0. From Corollary 2, we get δ ≥ s. Since δδ = -k -> 0, we obtain δ > δ ≥ s which is in contradiction with [START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF]. Let us now discuss the possible values of k depending on . Observe first from (13) that ∈ {-1, 0} implies k < 0 and = 1 implies k ≤ 0. Substituting µ and δ in the l.h.s. of the third inequality of (12), we have µ + 2k ≥ (s -1)(δk --1).

Moreover, with the same arguments as in the proof of Corollary 2, we get µ ≤ (δ + 1)(s -1) + 1.

From these two inequalities, we obtain k ≥ -1 + (s -1)( + 2) s + 1 .

Therefore, the following table summarizes the four remaining cases to consider.

= -1 0 > k ≥ -s s+1 > -1 k ∈ ∅ = 0 0 > k ≥ -2s+1 s+1 > -2 k ∈ {-1} = 1 0 ≥ k ≥ -3s+2 s+1 > -3 k ∈ {-2, -1, 0} • = 1, k = 0, b = 1, c = 1.
We refer to the function f introduced in Lemma 5. We have A n = x, B n = y + 1, C n = z + 1 and

f (m) = C m -sB m -A m = z -sy -x = C n -sB n -A n + s -1 = f (n) + s -1.
From the second part of Lemma 5, we conclude that m > n which is a contradiction.

In the following three cases, the triple (α, β, γ) may belong to M al(s). Nevertheless we will find an alternative way to play from (x, y, z) to an element in P. By minimality of m, we have m ≤ M . Therefore α, β, γ ≥ 0 but this contradicts the assumptions of (c.4.2).

  2 and ∆ n (b) = s + 3. Consequently, we get (∆ n (a), ∆ n (b), ∆ n (c)) = M . The uniqueness of n comes from the fact that the sequence (

  )) ω . Otherwise, i.e., when d β (1) is infinite, we set d * β (1) := d β (1). The set of β-expansions of all real numbers in [0, 1[ is denoted D β and the set of all finite factors occurring in elements of D β is denoted F (D β ).

Remark 6 .Figure 1 .

 61 Figure 1. The automaton A β .

Proposition 8 . [ 15 ]Remark 8 .

 8158 Let ϕ : A → A * be a morphism and a ∈ A be such that ϕ ω (a) = t 1 t 2 • • • is infinite. With the above notation, we have t n = δ(a, rep Lϕ (n -1)). Let ϕ : A → A * be a morphism and a ∈ A be such that ϕ ω (a) = t 1 t 2 • • • is infinite. If there exists a Parry number β such that A β = A ϕ then rep U β = rep Lϕ .

Corollary 11 .

 11 Cubic(s) is a tractable game.Proof. The morphism ϕ s satisfies the assumption of the previous theorem. Moreover, the number of moves from a position T = (a, b, c) is bounded by a + b + c (which is exponential with respect to |T |).

  that we consider positions (a, b, c) ∈ N 3 such that a ≤ b ≤ c. So notation (a, b, c) contains the extra information a ≤ b ≤ c. If one removes nonnegative integers i 1 , i 2 and i 3 respectively from the three piles a, b and c, we get a = ai 1 , b = bi 2 and c = ci 3 and we use brackets [a , b , c ] instead of parentheses to specify that the resulting triple is not necessarily ordered. We shall therefore write (a, b, c) i1,i2,i3 -→ [a , b , c ]. Notice that if a < b = c or a = b < c or a = b = c , we consider naturally that the triple remains ordered. In particular, we write [a , b , c ] = (a , b , c ) if the order of the piles is unchanged after the move. Finally, we write (a, b, c) R -→ (x, y, z)

  (a) If [x, y, z] = (A m , B m , C m ), then with the same reasoning α = α , β = β and γ = γ . Therefore βα ≥ s and γβ ≥ s but this contradicts the fact that rule III has been applied. (b) If [x, y, z] = [C m , B m , A m ], then β = β, α < α and γ < γ. Consequently, γ > γ > β + s -1 = β + s -1 > α + 2s -2 > α + 2s -2 hence γ > β + s -1 and β > α + s -1, leading to the same contradiction as in (a). (c) If [x, y, z] = [B m , A m , C m ], then γ = γ, α > α and β < β. Since βα > βα ≥ s and since rule III is applied, then |γ -β| < s. Therefore

  (d) If [x, y, z] = [B m , C m , A m ], then α < α , β < β and γ > γ . Since |γ -β| > s, |γ -α| > s and since rule III is applied, then |β -α| < s. In other words, |(B n -A n ) -(C m -B m )| < s. By Corollary 5, C m -B m = B i -A i for all i > 0 and we consider three cases. Recall that Proposition 4 states that

  (xx , yy , zz ) = (1 + ν, 2 + ν, (ν + 1)(1 + s) + 1)and |yy -(xx )| = 1 < s, we play (x, y, z) III -→ (x , y , z ) ∈ P.

  Therefore, setting β := y -A n > 0 and γ := z -B n > 0, we get (x, y, z) 0,β,γ -→ [C n , A n , B n ] and we can apply rule I. (b) If x = B n . This case splits into two sub-cases. (b.1) If z ≥ C n and since A n < B n = x ≤ y, we set β := y -A n > 0 and γ := z -C n . We get (x, y, z)0,β,γ -→ [B n , A n , C n ]and we can again apply rule I.

  (c) If x = A n . This case splits into four sub-cases. (c.1) If y ≥ B n and z ≥ C n , then (x, y, z)I -→ (A n , B n , C n ). (c.2) If y < B n and z ≥ C n . Set t := yx. In particular, s ≤ t < B n -A n (the left inequality coming from (10)). Furthemore, there exists m ∈ N such that |t -(B m -A m )| < s. Indeed, from Lemma 2, (B i+1 -A i+1 ) -(B i -A i ) ∈ {s, s + 1} for all i.Notice that the existence of such an m is not guaranteed for s = 1. (c.2.1) Assume there exists m such that |t -(B m -A m )| < s and t ≥ B m -A m . Hence,

s 2 (= s 2 s - 1 - 1 .

 211 b -1) + (s -1) ( c + 1) = 0.Since (s -1) ( c + 1) > 0, this implies b = 0. Hence, we obtain that c If s > 2 then the r.h.s. of the equation is not an integer contradicting the fact that c is an integer. If s = 2, then c = 3, δ = 0 and δ = δ + 2 = 2 contradicting the fact that δ ≤ s -1.Hence we conclude that (α, β, γ) ∈ M al(s) and we can play (x, y, z)II -→ (A m , B m , C m ). (c.4) If y < B n and z < C n . Once again, consider the smallest integer m > 0 such that z -x-sy = C m -A m -sB m . Set α := x-A m , β := y-B m and γ := z -C m .(c.4.1) Assume as a first sub-case that α, β, γ ≥ 0. If α β γ = 0 then one can immediately apply rule I from (x, y, z) to (A m , B m , C m ). So let us assume now that α β γ > 0. Then A n = x > A m and so n > m. As for (c.3), we would like to apply rule II. Since γ = α + sβ, we know that γ > max{α, β}.If α > β, then γ = α + sβ < sα + β and we can play (x, y, z)II -→ (A m , B m , C m ) provided (β, α, γ) ∈ M al(s). Assume that (β, α, γ) ∈ M al(s). There exist nonnegative integers µ , ν , δ such that (β, α, γ) = µ G 1 + ν G 2 + δ M .Consider the multi-linear map generalizing the function f of Lemma 5g : N 3 → N : (u, v, w) → wusv.Notice that g(x, y, z) = g(A m , B m , C m ) = f (m) and g(x, y, z)-g(A m , B m , C m ) = g(α, β, γ) = 0. But since (α, β, γ) = (µ (1+s)+ν (2+s)+δ (3+s), µ +2(ν +δ ), µ (2+s+s 2 )+ν (3+2s+s 2 )+δ (4+2s+s 2 ))

•

  = 0, k = -1, b = s -1, c = s 2 . Let us show that in that case, we can play (x, y, z) III -→ (A n-1 , B n-1 , C n-1 ). We have here A n = x, B n = y + s -1 and C n = z + s 2 . From Lemma 2, we get y > B n-1 and z> C n-1 . If (∆ n-1 (a), ∆ n-1 (b), ∆ n-1 (c)) ∈ {G 1 , G 2 }, then |y -B n-1 -(x -A n-1 )| = 1 hence we can play the proposed move. In the same way, if (∆ n-1 (a), ∆ n-1 (b), ∆ n-1 (c)) = M then |y -B n-1 -(x -A n-1 )| = 2. If s > 2,once again rule III can be applied. If s = 2, then from[START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF] we get δ = 1 so δ = 0. This means that there is no occurrence of M in [(∆ k (a), ∆ k (b), ∆ k (c))] m≤k<n and (∆ n-1 (a), ∆ n-1 (b), ∆ n-1 (c)) cannot be equal to M and this latter situation never occurs.• = 1, k = -1, b = s, c = s 2 + 1.As in the previous case, we get|y -B n-1 -(x -A n-1 )| = 0 if (∆ n-1 (a), ∆ n-1 (b), ∆ n-1 (c)) ∈ {G 1 , G 2 }, 1 if (∆ n-1 (a), ∆ n-1 (b), ∆ n-1 (c)) = M,hence we can play (x, y, z)III -→ (A n-1 , B n-1 , C n-1 ). • = 1, k = -2, b = 2s -1, c = 2s 2 + 1.Let us show that in that case, we can play (x, y, z)III -→ (A n-2 , B n-2 , C n-2 ). Notice that n ≥ 2 because if n = 1 we would have z = C 1c = -s 2 + s + 1 < 0. Observe that from Lemma 2, we get y = B n -2s + 1 > B n-2 and z = C n -2s 2 -1 > C n-2 . Up to a permutation the factor κ = [(∆ k (a), ∆ k (b), ∆ k (c))] k=n-2,n-1 can take four values G 1 G 1 , G 1 G 2 , G 1 M and G 2 M . This leads to |y -B n-2 -(x -A n-2 )| = 1 if κ = G 1 G 1 , G 1 G 2 2 if κ = G 1 M, G 2 M.So we can play rule III as proposed except when s = 2 and κ = G 1 M or G 2 M . But, if s = 2 then δ = 1 so δ = 0 and as for the case = 0, k = -1 no M can appear in κ. (c.4.2) Assume that we are now in the situation where at least one of the elements α, β, γ defined in (c.4.1) is negative. SetM := max{k ∈ N | A k ≤ x, B k ≤ y, C k ≤ z}.Since x = A n , we conclude that M ≤ n. Moreover, M = n since y < B n and z < C n . So M + 1 ≤ n and A M +1 ≤ A n but by definition of M we must therefore have B M +1 > y or C M +1 > z. We consider these two cases separately.(c.4.2.1) Suppose thatB M +1 > y. Then B M +1 -A M +1 > yx (indeed remember that A M +1 ≤ A n = x).By Lemma 2, there existsK ≤ M such that 0 ≤ yx -(B K -A K ) ≤ s.Assume first that there exists some K ≤ M such that(14) 0 ≤ yx -(B K -A K ) < s.Since K ≤ M , we have x > A K , y ≥ B K and z ≥ C K . If y = B K or z = C K then we play (x, y, z)I -→ (A K , B K , C K ).Otherwise, we play (x, y, z) III -→ (A K , B K , C K ). Assume now that (14) never occurs. Then there exists K ≤ M such that yx -(B K -A K ) = s. In particular, this means that (B K+1 -A K+1 ) -(B K -A K ) = s + 1. From Lemma 4, there exists L ≤ K such that C L -B L = B K -A K + 1. In view of Lemma 3, we also have A K = B L -1. So yx -(C L -B L ) = s -1. Notice that z ≥ C M ≥ C L > A L , x ≥ A M +1 > A M ≥ A K = B L -1 and y -C L = x -B L + s -1 > 0. If x = B L ,we play (x, y, z) I -→ [B L , C L , A L ]. Otherwise, x > B L and we play (x, y, z) III -→ [B L , C L , A L ]. (c.4.2.2) Suppose that B M +1 ≤ y and C M +1 > z. Since z -C M +1 < 0 ≤ x -A M +1 + s(y -B M +1 ), we get f (m) = zxsy < C M +1 -sB M +1 -A M +1 = f (M + 1).

Table

Table 1 .

 1 . First values of the sequences (A

	n	0 1	2	3	4	5	6	7	8	9	10	11	12	13	14
	A	(3) n	0 1	2	3	5	6	7	9	10	11	13	15	16	17	19
	B	(3) n	0 4	8 12 18 22 26 32	36	40	46	51	55	59	65
	C	(3) n	0 14 28 42 61 75 89 108 122 136 155 173 187 201 220 234
												(3)

Acknowledgments

We would like to thank Professor A. Fraenkel for his appropriate comments and suggestions.