key: cord-0043812-vhyb3f6s
authors: Lietard, Florian; Rosenfeld, Matthieu
title: Avoidability of Additive Cubes over Alphabets of Four Numbers
date: 2020-05-26
journal: Developments in Language Theory
DOI: 10.1007/978-3-030-48516-0_15
sha: 692d943dc3f2f078d0717a39d9324a733ee83dd1
doc_id: 43812
cord_uid: vhyb3f6s

Let [Formula: see text] be a set of size 4 such that [Formula: see text] cannot be obtained by applying the same affine function to all of the elements of [Formula: see text]. We show that there is an infinite sequence of elements of [Formula: see text] that contains no three consecutive blocks of same size and same sum (additive cubes). Moreover, it is possible to replace [Formula: see text] by [Formula: see text] in the statement.

Let k ≥ 2 be an integer and (G, +) a semigroup. An additive kth power is a non-empty word w 1 · · · w k over A ⊆ G such for every i ∈ {2, . . . , k}, |w i | = |w 1 | and w i = w 1 (where v denotes the sum of the letters in v seen as numbers). It is a longstanding question whether there exists an infinite word w over a finite subset of N that avoids additive squares (additive 2nd powers) [3, 4, 6] . One motivation for studying this problem is that a positive answer to this question would imply that additive squares are avoidable over any semigroup that contains some finitely generated infinite semigroup [6] (an application of van der Waerden's theorem shows that additive powers are not avoidable over any other semigroup [4] ). Cassaigne et al. [1] showed that there exists an infinite word over the finite alphabet {0, 1, 3, 4} ⊂ Z without additive cubes (additive 3rd powers). Rao [7] used this result to show that there exist infinite words avoiding additive cubes over any alphabet {0, i, j} ⊂ N 3 with i and j coprime, i < j and 6 ≤ j ≤ 9 (and he conjectured that the second condition can be replaced by 6 ≤ j). This motivates the following more general problem: Problem 1. Characterize the finite subsets of N over which additive cubes are avoidable.

It seems restrictive to use N instead of R (or C), but solving Problem 1 for alphabets of the form {0, a 1 , . . . , a m } ∈ N with the a i 's being coprime completely solves the problem for any finite alphabet over C (if the a i 's are given in increasing order one can additionally assume a 1 be smaller than a m − a m−1 ). For the sake of completeness, we give a short proof of this fact in Sect. 2.

If Rao's conjecture were true then the only remaining 3-letter alphabets over C to characterize would be {0, 1, 2}, {0, 1, 3}, {0, 1, 4} and {0, 2, 5} (see [9, Section 2.2.2] for details). However, this conjecture is known to be true for only finitely many such alphabets (up to a trivial equivalence relation defined in Sect. 2.1). In the present paper we propose a twist on previously used ideas to show our main theorem (see Corollary 1).

Let A ⊂ C be an alphabet with |A| ≥ 4. If A is not equivalent to {0, 1, 2, 3} then additive cubes are avoidable over A.

This also implies that additive cubes are avoidable over any alphabet of complex numbers of size at least 5. Rao used the fact that additive cubes are avoidable over {0, 1, 3, 4} to show that they are avoidable over some 3-letter alphabets [7, Section 3.2], so our result might also be of importance for tackling Problem 1 for alphabets of size 3.

The present paper is organized as follows. We first recall some notation and we define the equivalence between two alphabets. Equipped with this equivalence relation we explain why it is enough to study alphabets of integers or alphabets of the form {0, 1, a 2 , a 3 , . . . , a m } with m ∈ N and a 2 , . . . , a m ∈ Q. Then we introduce the word W a,b,c,d , based on the construction of [1] , and we show that for all but finitely (up to our equivalence relation) many values of a, b, c, and d, the word W a,b,c,d avoids additive cubes. Finally, using the literature for the remaining alphabets, we conclude that additive cubes are avoidable over all the remaining alphabets of size 4, with the sole exception of {0, 1, 2, 3}. We leave the case of {0, 1, 2, 3} open, and comment on our calculations regarding this case in the last section.

We use the standard notation introduced in Chapter 1 of [5] . In the rest of the present article all of our alphabets are finite sets of complex numbers. For the rest of this section, let A ⊂ C be such an alphabet. We denote by ε the empty word and by |A| the cardinality of the alphabet A. Given a word w ∈ A * , we denote by |w| the length of w and by |w| α the number of occurrences of the letter α ∈ A in w. Two words u and v are abelian equivalent, denoted by u ab v if u and v are permutations of each other. They are additively equivalent, denoted by

where v denotes the sum of the letters in v (this make sense since the letters are complex numbers). A word uvw ∈ A * is an abelian cube (respectively, an additive cube) if u ab v ab w (respectively, if u ad v ad w).

For any function h : A → C and words w over A ⊂ C, the word h(w) is obtained by replacing each letter of w by its image under h. We say that two alphabets A, A ⊂ C of same size are equivalent if there is a function h :

Let us now show that for any alphabet of complex numbers, we either already know that additive cubes are avoidable or the alphabet is equivalent to an alphabet of integers. We start by giving sufficient conditions for two alphabets to be equivalent.

The proof is left to the reader. Recall that two complex numbers a and b are said to be rationally independent if k 1 a + k 2 b = 0 for (k 1 , k 2 ) ∈ Z 2 implies k 1 = k 2 = 0.

Let A ⊂ C. Proof.

(i) This statement follows from the fact that abelian cubes are not avoidable over two letters [2] . 

Since abelian cubes are avoidable over 3 letters [2] , we deduce that additive cubes are avoidable over A.

Thus there exists a q ∈ Z such that for all i, q bi−b1 b2−b1 ∈ Z and gcd q b2−b1 b2−b1 , q b3−b1 b2−b1 , . . . , q bm−b1 b2−b1 = 1. Let s = min 1≤i≤m q bi−b1 b2−b1 . Finally, we apply Lemma 1 with f : x → q x−b1 b2−b1 − s and we get that the alphabet

. . , q bm−b1 b2−b1 − s} satisfies all the required conditions. This concludes the proof.

Thus solving Problem 1 for alphabets of the form {0, a 1 , . . . , a m } ⊂ N with coprime a i 's completely solves the problem for any finite alphabet over C. Notice that, in case (iii), one can add the condition that a 1 < a m − a m−1 , (otherwise apply f : x → a m − x to this alphabet). One could also add that in the case |A| = 2, one can avoid additive 4th powers (with an argument similar to (ii) and the fact that abelian 4th powers are avoidable over 2 letters [2] ).

a1−a0 . Therefore, in Sects. 3 and 4, instead of considering alphabets of four integers we consider alphabets of the form {0, 1, c, d} ⊂ Q.

Cassaigne et al. [1] showed in 2014 that W 0,1,3,4 avoids additive cubes. In particular, this implies that W 0,1,3,4 avoids abelian cubes. This property does not depend on the choice of a, b, c, d, therefore we deduce the following lemma. We define the Parikh vector Ψ as the map

Let M ϕ = 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 be the adjacency matrix of ϕ a,b,c,d and τ be the vector corresponding to the numerical approximation 1 τ=

, which is 1 We stress the fact that this is not an issue to use numerical approximation. Indeed, all our computations are numerically stable (additions, multiplications and no divisions by numbers close to zero) and if we start with sufficiently accurate approximations, we get sufficiently accurate approximations at the end (see footnote 2 for the only case where it matters that a coefficient is exactly 0). Moreover, there is an algebraic extension of Q of degree 24 that contains all the eigenvalues of the matrices (according to mathematica) and thus we could use the original proof of [1, Theorem 8] to get an exact value for C and only use exact computation in our article. However, one might think that this is convenient to use the fact that these roots can be expressed with radicals, but maintaining exact expressions involving radicals is much more inefficient and would lead to even more unreadable computations.

related to the eigenvalue 0.4074+0.4766i of M ϕ and precisely defined in Sect. 2.1 of [1] . For the sake of conciseness, the definition is omitted here. We recall the following result from [1] .

There exists a positive real constant C such that for any two factors of W a,b,c,d (not necessarily adjacent) u and v

Let us summarize the main idea behind Theorem 1. The asymptotic behavior of the Parikh vectors of factors is closely related to the asymptotic behavior of the iterations of the matrix M ϕ (since Ψ (ϕ(u)) = M ϕ (Ψ (u))). Moreover, the eigenvalue corresponding to this eigenvector is of norm less than 1 and thus the associated subspace is contracting. We deduce that τ (Ψ (u)) is bounded for any factor u. Theorem 1 provides good bounds in this particular case. Equipped with Lemma 3 and Theorem 1 we deduce the following one. 1,c,d ) . For any reals m and n, if mα + nβ is an integral vector then m ∈ N (resp., n ∈ N) because otherwise its third (resp., its fourth) coordinate is not an integer and mc + nd ∈ Z, otherwise the first and second coordinates are not integers. We deduce that

Thus, we only need to show that, under the assumptions, for any m, n ∈ Z with mc + nd ∈ Z and (m, n) = (0, 0), we get 1.06114, x) ). We distinguish several cases depending on the value of c.

-If c > 2.85 a straightforward computation gives |τ · α| > C and |τ · mα| > C.

-If c ∈ [1.9, 2.9] \ {2}, a computation gives |τ · α| > C 2 . Moreover, in this case m ∈ Z and mc ∈ Z imply |m| ≥ 2 (since c ∈ Z) and |τ · mα| > C.

-If c ∈ [1.55, 1.95], a computation gives |τ · α| > C 3 . Moreover, in this case m ∈ Z and mc ∈ Z imply |m| ≥ 3 (since 2c ∈ Z) and we get |τ · mα| > C.

-If c ∈ [1.3, 1.65] \ {4/3, 3/2}, a computation gives |τ · α| > C 4 . Moreover, in this case m ∈ Z and mc ∈ Z imply |m| ≥ 4 (since 3c, 2c ∈ Z) and we get |τ · mα| > C.

-If c ∈]1, 1.35] \ {5/4, 4/3}, a computation gives |τ · α| > C 5 . Moreover, in this case m ∈ Z and mc ∈ Z imply |m| ≥ 5 (since 4c, 3c, 2c ∈ Z) and we get |τ · mα| > C.

Let us show that (1) is true if |n| ≥ 4 and m ∈ Z. We have

where k = |τ · α| Im τ ·β τ ·α . Numerical computations give: (2) to get that if |n| ≥ 4, then |mτ · α + nτ · β| > C.

It remains to deal with the cases |n| ∈ {1, 2, 3}. It is enough in (1) to consider the cases n ∈ {1, 2, 3}. We treat each case in a similar way. Let us start with the case n = 1. We get numerically Table 1 , for each of them the condition on the reals and the assumptions that allow us to conclude. 

The next case is n = 2 and we treat it in a similar fashion. We get numerically

Computing the discriminant yields P c,d,2 (m) > 0, for all d ∈ R if and only if Δ c (d) := 78.9442 + (24.5715 − 5.00433m)m < 0. This is a quadratic inequality in m and solving it yields m ∈ [−2.21427, 7.12433] =⇒ |τ · (mα + β)| > C. Thus we only need to check that, under the assumptions, for every m ∈ {7, 6, 5, 4, 3, 2, 1, 0, −1, −2} such that mc + 2d ∈ Z, P c,d,2 (m) > 0. Each case is similar to the cases with n = 1. We give, in Table 2 , for each of them the condition on the reals and the assumptions that allow us to conclude. The only remaining case is n = 3 and we treat it in a similar fashion. We get numerically P c,d,3 (m) := |τ · (mα + 2β)| 2 − C 2 = 0.362434 + 2.13722m − 3.52118bm + 1.83908m 2 − 3.05698cm 2 + 1.44043c 2 m 2 + (−10.5635 − 9.17095m + 8.64256cm)d + 12.9638d 2 .

Computing the discriminant yields P c,d,3 (m) > 0, for all d ∈ R if and only if Δ c (d) := 92.7941 + 82.929m − 11.2597m 2 < 0. This is a quadratic inequality in m and solving it yields m ∈ [−0.986756, 8 .35184] =⇒ |τ · (mα + β)| > C. Thus we only need to check that, under the assumptions, for every m ∈ {8, 7, 6, 5, 4, 3, 2, 1, 0} such that mc + 3d ∈ Z, P c,d,3 (m) > 0. Each case is similar to the cases n = 1, 2. We give, in Table 3 , for each of them the condition on the reals and the assumptions that allow us to conclude. This finishes the proof of Theorem 2. 

In fact, using a symmetry argument we can improve the previous result. We get the set from Theorem 3 by simply computing the intersection of the two sets in (3) (this is done by solving the 169 equations).

Proof. Following the proof of Theorem 2, we only need to show that, under the assumptions, for any m, n ∈ Z with mc + nd ∈ Z, we have |τ · (mα + nβ)| > C, where α = (−c, c − 1, 1, 0) and β = (−d, d − 1, 0, 1). Let us first show that this is the case if n = 0. Two subcases occur:

-If c > 1.71 a computation gives |τ · α| > C and |τ · mα| > C.

-If c ∈]1, 2[, a computation gives |τ · α| > C 2 . Moreover, in this case m ∈ Z and mc ∈ Z imply |m| ≥ 2 (since c ∈ Z) and we get |τ · mα| ≥ C.

Let us now show that |τ · (mα + nβ)| > C if |n| ≥ 4 and m ∈ Z. The same computation as (2) gives:

The same approach as in proof of Theorem 2 can be used to verify that k 2 − ( C 4 ) 2 > 0 for any d > c > 1. This gives with inequality (4) that if |n| ≥ 4, then |mτ · α + nτ · β| > C. It remains to treat the cases |n| ∈ {1, 2, 3} but it is enough to consider the cases n ∈ {1, 2, 3}, as previously. We start with the case n = 1. Once again P c,d,1 (m) := |τ · (mα + β)| 2 − C 2 is a quadratic polynomial in d. Computing its discriminant yields P c,d,1 (m) > 0, for all c ∈ R if and only if Δ c (d) := 25.3914 + 3.07144m − 1.25108m 2 < 0. This is a quadratic inequality in m and solving it yields m ∈ [−3.44178, 5.89681] =⇒ |τ · (mα + β)| > C (the conditions on m happen to be exactly the same as in Sect. 4). Thus we only need to check that for every m ∈ {5, 4, 3, 2, 1, 0, −1, −2, −3} such that mc + d ∈ Z, we have P c,d,1 (m) > 0.

All the cases are similar to what we did in the previous proof. We give, in Table 4 , for each of them the condition on the reals and the assumptions that allow us to conclude. The next case is n = 2 and we treat it in a similar fashion.

We verify that the only interesting cases are m ∈ [−2.21427, 7.12433]. Thus we only need to check that for every m ∈ {7, 6, 5, 4, 3, 2, 1, 0, −1, −2} such that mc + 2d ∈ Z, we get P c,d,2 (m) > 0. Each case is similar to the cases with n = 1. We omit here, because of the lack of space, the table that give for each of them the condition on the reals and the assumptions that allow us to conclude. This table can be found at https://members.loria.fr/FLietard/tables-of-values/.

The only remaining case is n = 3. We once again compute the discriminant of P c,d,3 (m) seen as a polynomial in d. We deduce that m ∈ [−0.986756, 8 .35184] =⇒ |τ · (mα + β)| > C.

Summing up, we only need to check that for every m ∈ {8, 7, 6, 5, 4, 3, 2, 1, 0} such that mc + 3d ∈ Z, P c,d,3 (m) > 0. We prove this statement by solving each of the corresponding 9 equations and this concludes the proof of Theorem 4.

We could improve this result with the same approach as the one we used in the proof of Theorem 3, but we already have a strong enough result for our purpose. On the one hand, Rao [7] claims that he got a word of length 1.4 × 10 5 over the alphabet {0, 1, 2, 3} without additive cubes. Damien Jamet, the first author and Thomas Stoll constructed over this alphabet several words of length greater than 10 7 without additive cubes (see https://members.loria.fr/FLietard/un-mot-sur-0123/ for such a word). Therefore, it seems to be reasonable to believe that there exists an infinite word without additive cubes over {0, 1, 2, 3}. On the other hand, for every alphabet {a, b, c, d} different from {0, 1, 2, 3} it is possible to provide a short morphism with the same eigenvalues as those of ϕ a,b,c,d or ϕ 2 a,b,c,d with an infinite fixed point avoiding additive cubes. An exhaustive research shows, however, that every morphism over {0, 1, 2, 3} with images of size at most 7 fails to provide an infinite fixed point without additive cubes. We do not dare to conjecture whether or not a morphism providing such an infinite word exists.

It seems that additive cubes are avoidable over most alphabets of size 3. Our result might stimulate research to treat the following question.

Can we characterize the sets of integers of size 3 over which additive cubes are avoidable?

In fact, with the exception of {0, 1, 2, 3}, the alphabets of size three are the only remaining case of Problem 1 due to Lemma 2 and Theorem 8.

Avoiding three consecutive blocks of the same size and same sum

Strongly non-repetitive sequences and progression-free sets

An application of Van der Waerden's theorem in additive number theory

Généralisation du théorème de van der Waerden sur les semi-groupes répétitifs

Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications

On uniformly repetitive semigroups

On some generalizations of abelian power avoidability

Avoiding two consecutive blocks of same size and same sum over Z 2

Avoidability of Abelian Repetitions in Words

We show the next result by using a similar procedure as the one in the proof of Theorem 2 in Sect. 4.

Proof. Let X be the following set of pairs of parametric equations:For any pair e = (x(t), y(t)) of parametric equations, we denote by C(e) the associated parametric curve (that is the set of points defined by {(x(t), y(t)) : t ∈ R}). By the Theorem 2 for any c, d ∈ R with c > d > 1 and (c, d) ∈ e∈X C(e) additive cubes are avoidable over {0, 1, c, d}. Moreover, for any c, We use the fact that all but one of the remaining alphabets contain an alphabet equivalent to an alphabet from Theorem 6 or Theorem 7. Our main result after this reduction is the following: contains an alphabet equivalent to {0, 1, 5} (apply x → 9x− 9 to 1, 10 9 , 14 9 ). We deduce from Theorem 6 that additive cubes are avoidable over both alphabets. We proceed in a same way for the other alphabets and we provide for each of them the alphabet from Theorem 6 or from Theorem 7 in Table 5 . This concludes the proof. Table 5 . Each remaining alphabet, with exception of {0, 1, 2, 3}, contains an alphabet equivalent to an alphabet from Theorems 6 or 7. (2, 4) {0, 1, 2, 4} (3, 4) {0, 1, 3, 4}We reformulate this result in terms of Problem 1. Note that we have shown that for all but finitely many integral alphabets of size 4 (up to the equivalence relation given in Sect. 2.1) the word W a,b,c,d can be used to avoid additive cubes. This is probably not the only fixed point of a morphism with this property. Indeed, as long as the adjacency matrix of a