We prove that additive cubes are avoidable over the alphabet {0,1,2,3}, thereby solving a long-standing question initiated by Pirillo and Varricchio in 1994. By extending the reduction and spectral machinery of Cassaigne, Currie, Schaeffer, and Shallit (2014), we prove that the search for additive cubes in such morphic images reduces to a finite graph traversal. We exhibit eight explicit morphisms from {0,1,3,4}∗ to {0,1,2,3}∗ of length 3 whose images on the Cassaigne et al. infinite word contain no additive cubes.
Introduction and main result
Throughout the present document, terminology and notations follow standard conventions on combinatorics on words [3]. All the alphabets are finite sets included in N. Let Σ⊂N be an alphabet. A finite word u∈Σ∗ has length∣u∣=n. The sum of the letters of u is sum(u)=
k=0∑n−1uk
(with sum(ε)=0).
Definition 1 (Additive cube). A non-empty finite wordu over an alphabet Σ⊆N is an additive cube if u=u1u2u3 with u1, u2, u3∈Σ∗, ∣u1∣=∣u2∣=∣u3∣ and sum(u1)=sum(u2)=sum(u3). A word (finite or infinite) is without additive cubes or avoids additive cubes, if none of its finite factors is an additive cube.
The question of the existence of an infinite word avoiding additive cubes over a finite alphabet was raised by Pirillo and Varricchio [4] in 1994. Cassaigne, Currie, Schaeffer and Shallit [1] showed the existence of a pure morphic infinite word over {0,1,3,4} without additive cubes. Lietard and Rosenfeld [2] proved that additive cubes are avoidable by pure morphic words over all alphabets of four integers that are not affinely equivalent to {0,1,2,3}. Rao [5] extended the avoidability of additive cubes to ternary alphabets such as {0,1,5}. The question for {0,1,2,3} (question 5 of [5]) is, to our knowledge, still open.
We exhibit eight morphisms from {0,1,3,4} to {0,1,2,3} such that the image of the infinite word introduced in [1] under each of these morphisms avoids additive cubes.
Our proof scheme is largely inspired by—and builds directly on—the approach of [1]. The key to our method lies in a slightly stronger use of Theorem 14 (Theorem 8 in [1]); although it is restated and slightly reformulated here, this essential property is entirely due to [1].
From now on, Σ denotes the alphabet {0,1,3,4}, φ:Σ∗→Σ∗ denotes the morphism
φ(0)=03,φ(1)=43,φ(3)=1,φ(4)=01.
and w=limn→∞φn(0)=0314301103434303101101…=φ(w).
Theorem 2 ([1]). The infinite word w contains no additive cube.
Let τ:Σ∗→{0,1,2,3}∗ be a non-erasing morphism, that is ∣τ(a)∣≥1 for every a∈Σ. We denote:
We will check that the morphisms τ1,…,τ8 listed in Table 2 on page 15 satisfy two hypotheses:
τ(0),τ(1),τ(3),τ(4)
ℓ
s
detΦ
∣F0∣
∣R∣
R∩Zτ
21,100,3,23
2,3,1,2
3,1,3,5
−10.53
67
78340
∅
12,233,0,10
2,3,1,2
3,8,0,1
+10.53
67
78340
∅
122,331,0,10
3,3,1,2
5,7,0,1
+10.32
119
78340
∅
211,002,3,23
3,3,1,2
4,2,3,5
−10.32
119
78340
∅
021,001,323,321
3,3,3,3
3,1,8,6
−21.07
89
78340
∅
312,332,010,012
3,3,3,3
6,8,1,3
+21.07
89
78340
∅
132,332,101,102
3,3,3,3
6,8,2,3
+19.01
87
78340
∅
201,001,232,231
3,3,3,3
3,1,7,6
−19.01
87
78340
∅
Table 2. Result of the traversal of G′ for the eight candidate morphisms.
(H0) for every a∈Σ, τ(a) contains no additive cube;
(T)transversality: a specific 4×4 matrix Φ depending on τ is invertible (Definition 27).
Theorem 3 (Reduction theorem, precise statement in Theorem 33). Let τ:Σ∗→{0,1,2,3}∗ be a non-erasing morphism satisfying (H0) and (T). There exist a finite graph G′, a starting set A0 of at most 9 vertices and an accepting set Zτ such that, denoting by R the set of vertices of G′ reachable from A0:
x=τ(w) avoids additive cubes⟺R∩Zτ=∅.
Theorem 4 (Result of the computation, § 6). For each of the eight morphisms τ1,…,τ8 of Table 2 on page 15, the hypotheses (H0) and (T) are satisfied and the traversal of G′ gives R∩Zτ=∅. By Theorem 3, τi(w) is an infinite word over {0,1,2,3} without additive cubes.
A direct consequence of Theorem 4 and [5] (see Table 3 and Question 5) is the avoidability of additive cubes over two ternary alphabets:
Corollary 5.Additive cubes are avoidable over the alphabets {0,1,4} and {0,2,5}.
In the following, we are not going to detail every example, but only focus on a particular case as a running example: τ1:0↦21,1↦100,3↦3,4↦23. For this morphism, we have ℓ=t(2,3,1,2), s=t(3,1,3,5),
The other morphisms are handled in exactly the same way, and we will provide the numerical results for each of them.
Our entire work is a direct adaptation of the work by Cassaigne, Currie, Schaeffer, and Shallit [1]. The core proof strategy—analyzing the genealogy of factors, bounding spectral projections, and reducing the search to an induced finite graph—is already present in [1]. In fact, their original theorem can be viewed as the canonical base case where τ=idΣ, without boundary shifts. Our contribution adapts their machinery to handle the deformations induced by a coding morphism τ.
The computer verification relying on Theorem 4 was carried out by a C++ program. This program is an updated version of the code that the first author originally developed to search for candidate morphisms whose fixed points avoid additive cubes. These morphisms were then studied and proven in [2].
Properties of the word w
While the content of this section is largely based on [1], we recall and detail its main components in order to make the present paper self-contained and easy to follow.
Notation
We endow R4 with the canonical basis (e0,e1,e3,e4) indexed by the letters of Σ. The Parikh vector of a finite word u is ψ(u)=t(∣u∣0,∣u∣1,∣u∣3,∣u∣4)∈N4. For p≤q, we denote w[p,q)=wp⋯wq−1 (with w[p,p)=ε) and σ(p)=ψ(w[0,p)) is the Parikh vector of the prefix w0⋯wp−1; hence σ(0)=0 and, for every factor b=w[p,q), ψ(b)=σ(q)−σ(p).
The incidence matrix of φ is defined as the 4×4 matrix whose columns are the Parikh vectors of the images of 0, 1, 3, and 4, in that order:
Let η(p)=∣φ(w[0,p))∣ be the length of the image of the prefix w[0,p) under φ.
For any integer q, the parent of q, denoted par(q), is the unique p such that η(p)≤q<η(p+1); we then say that q is a child of p. Roughly speaking, the parent of an index q is the unique index p such that the image φ(wp) covers the position q within the word w.
The word w begins with w[0,20)=03143011034343031011 (see Figure 1). Table 1 gives the values of η, parents, and children for the first few positions.
Figure 1. Splitting of the first 20 positions of w into images φ(wt). The indices under the brackets indicate the parent t=par(q).
position p
0
1
2
3
4
5
6
7
8
9
10
11
letter wp
0
3
1
4
3
0
1
1
0
3
4
3
η(p)
0
2
3
5
7
8
10
12
14
16
17
19
par(p)
0
0
1
2
2
3
3
4
5
5
6
6
children of p
{0,1}
{2}
{3,4}
{5,6}
{7}
{8,9}
{10,11}
{12,13}
{14,15}
{16}
{17,18}
{19}
Table 1. Values of η(p), par(p), and children for the first positions of w.
In Lemma 6, we recall the principal properties of η and par:
Lemma 6 (see Section 2.2 in [1]). 1. For every p, w[η(p),η(p+1))=φ(wp), that is the children of p are exactly the integers η(p),η(p)+1,…,η(p)+∣φ(wp)∣−1.
η is strictly increasing, η(0)=0, and η(p)>p for every p≥1.
par is increasing (not necessarily strictly), par(0)=0, and par(p)<p for every p≥1. In particular, for every p, we can find k≥0 such that park(p)=0.
We denote by A the set of proper prefixes of the images under φ:
A={ε,0,4}.
For every position q with parent p, the prefix w[0,q) is the concatenation of the complete imageφ(w[0,p)) of the parent prefix and a proper prefix a∈A of the image of the next letter wp (Figure 2, case q=11):
Figure 2. Decomposition of the prefix w[0,11): the first ten letters form the complete image φ(w[0,6)), and the letter w10=4 is a proper prefix a=φ(w6)[0,1) of φ(w6).
Lemma 7 (see Lemma 3 in [1]). Let q∈N, p=par(q) and i=q−η(p) (0≤i<∣φ(wp)∣). The word a=φ(wp)[0,i) is a proper prefix of φ(wp) (hence a∈A) and
σ(q)=Mσ(p)+ψ(a).
Corollary 8 (see Corollary 4 in [1]). Let p0∈N and pi+1=par(pi). For i≥0, we set ai=w[η(pi+1),pi)∈A. Then
σ(p0)=i≥0∑Miψ(ai),
a finite sum since pi=0 and ai=ε for i large enough.
Corollary 9 (see Corollary 4 in [1]). Let b=w[p,q) be a factor and b′=w[par(p),par(q)) its parent factor. Then
ψ(b)=Mψ(b′)+δ,δ=ψ(a′)−ψ(a)∈D:=ψ(A)−ψ(A),
where a=w[η(par(p)),p) and a′=w[η(par(q)),q) are the proper prefixes of Lemma 7 at the boundaries p and $q.
Remark 10 (Finiteness of boundary perturbations). Since ψ(ε)=0, ψ(0)=e0, ψ(4)=e4, the set D contains only 7 vectors: D={0,±e0,±e4,±(e0−e4)}. It is this finiteness that allows us to bound the boundary errors at all scales.
Ancestral chains (parents, grandparents, etc.) are strictly determined by local rules: the edge label (the prefix a) depends entirely on the parent letter and the child’s index in the image, which allows us to encode this local information in a graph.
Definition 11 (The graph Q (Figure 3), See Section 2.4 in [1]). The graph Q has the letters of Σ as vertices. For each letter c and each 0≤i<∣φ(c)∣, it has an edge e=(c,i) with source c, target the letter φ(c)[i], and label φ(c)[0,i)∈A.
Figure 3. The graph Q: parent → child transitions and their labels.
By Lemma 6(1), if q is a child of p, then q=η(p)+i with i<∣φ(wp)∣; the pair (wp,i) is an edge of Q with source wp, target wq and label a=w[η(p),q). In other words, the children of p in w are in bijection with the edges of Q whose source is wp.
The spectrum of M
The characteristic polynomial of M is X4−X3−2X2+2X−1 and its roots are:
The eigenvalues are all simple, hence M is diagonalizable over C: M=QΛQ−1 with Λ=diag(λ1,λ2,λ3,λ4).
Definition 12 (Linear forms θj). For each j, let qj∈C4 be a unit eigenvector (∥qj∥2=1) related to the eigenvalue λj, normalized such that its first component is real and strictly positive. The eigencoordinates θ1,…,θ4:C4→C are the rows of Q−1.
Contracting directions: every deviation is bounded
We now exploit the contracting eigendirections to bound any Parikh deviation between factors of w.
Definition 13 (Set of paths Dℓ, Definition 7 in [1]). For ℓ≥1, Dℓ⊂Z4 is the set of vectors
i=0∑ℓ−1Miψ(ai),
where (e0,…,eℓ−1) ranges over the sequences of edges of Q such that the target of ei+1 is the source of ei for 0≤i<ℓ−1 (the path is read from the oldest generation eℓ−1 to the most recent one e0), and ai is the label of ei.
The graph Q has 466 paths of length 9, which generate 301 distinct vectors in D9 (see proof of Theorem 8 [1]). We set:
Theorem 14 (Theorem 8 in [1]). For every pair of factors b, c of w (not necessarily of the same length, not necessarily consecutive):
∣θ3(ψ(b)−ψ(c))∣≤C3and∣θ4(ψ(b)−ψ(c))∣≤C3.
Expanding directions: stability under ascent
Let b, c be two factors of w with parents b′, c′. By Corollary 9, the deviation Δ=ψ(b)−ψ(c) and the deviation Δ′=ψ(b′)−ψ(c′) satisfy:
Δ=MΔ′+ρ,ρ=δ(b)−δ(c)∈E:=D−D,
where E is a finite subset of Z4. In the expanding directions (j=1,2), applying this relation towards the children would amplify the deviation by a factor ∣λj∣>1.5 at each generation. We invert it: applying θj,
θj(Δ′)=λjθj(Δ)−θj(ρ).
Definition 15 (Constants κ1 and κ2). For j∈{1,2}, κj=maxρ∈E∣θj(ρ)∣; numerically κ1≈1.3137 and κ2≈1.5060.
Iterating from an initial deviation Δ0, the deviation at the i-th generation is:
Lemma 16 (Stability under ascent). Let j∈{1,2} and (Δi)i≥0 be the sequence of deviations along a chain of ancestors, with ρk∈E. If ∣θj(Δ0)∣≤B, then for every i≥0:
∣θj(Δi)∣≤max(B,∣λj∣−1κj).
Proof. The case i=0 holds. For i≥1, the triangle inequality gives
Since ∣λj∣>1, α=∣λj∣−i∈]0,1] and the right-hand side is a convex combination αB+(1−α)∣λj∣−1κj of B and of ∣λj∣−1κj, hence bounded by their maximum.
Consequently, at every scales, the Parikh deviation between any two factors of w is bounded: by C3 in directions 3, 4 (Theorem 14), and by max(B,κj/(∣λj∣−1)) in directions 1, 2 (Lemma 16), where B is the initial bound.
Additive cubes in x=τ(w) via w
Positions in x
For a∈Σ and 0≤r≤ℓ(a), we denote hr(a)=sum(τ(a)[0,r))=∑k=0r−1τ(a)k the sum of the prefix of length r of τ(a) (with h0(a)=0).
In general, a position q of x does not fall strictly between two images, but occurs at some rank (offset) r within the image of a letter wp. There exists a unique pair (p,r) with 0≤r<ℓ(wp) and
x[0,q)=τ(w[0,p))⋅τ(wp)[0,r).
The offset r is the number of letters “already consumed” from the image τ(wp).
Lemma 17 (Positions). Let P={(p,r):p∈N,0≤r<ℓ(wp)} and pos(p,r)=ℓ⋅σ(p)+r. The map pos:P→N is a bijection, strictly increasing for the lexicographic order, and the sum H(q)=sum(x[0,q)) satisfies, for q=pos(p,r),
H(q)=s⋅σ(p)+hr(wp).
Proof. The prefix τ(w[0,p)) of x has length ℓ⋅σ(p) and sum s⋅σ(p); the next r letters form a prefix of τ(wp) of length r<ℓ(wp) and sum hr(wp). The monotonicity comes from the fact that ℓ⋅σ(p+1)=ℓ⋅σ(p)+ℓ(wp). Surjectivity comes from the fact that every position q can be written in this way (see above).
The discrete curve of cumulative sums
For q=pos(p,r), we denote
Λ(q)=(qH(q))=(ℓ⋅σ(p)s⋅σ(p))+(rhr(wp)).(1)
For q0=pos(p0,r0)≤q1=pos(p1,r1) and d0=w[p0,p1):
the imbalances between neighboring blocks of w. The three factors x[q0,q1), x[q1,q2), x[q2,q3) form an additive cube if and only if Λ(q1)−Λ(q0)=Λ(q2)−Λ(q1)=Λ(q3)−Λ(q2), that is, if and only if:
x[q0,q1)⋅x[q1,q2)⋅x[q2,q3) is an additive cube⟺Γu+b(c,r)=Γv+b′(c,r)=0.(2)
The terms b,b′ depend only on the four letters c=(c0,c1,c2,c3) and the four offsets r=(r0,r1,r2,r3): they take only finitely many values.
Hypothesis (H0) and accepting set
Definition 18 (Local hypothesis (H0)).The morphismτsatisfies (H0) if for everya∈Σ, τ(a)contains no additive cube;
The morphisms in Table 2 on page 15 have images of length at most 3 and no image is of the form ccc. Hence every morphism satisfies hypothesis (H0).
Definition 19 (Accepting set Zτ).The setZτ⊂Σ4×Z4×Z4is the set of triples(c,u,v)for which there exist offsetsrj∈{0,…,ℓ(cj)−1}(j=0,…,3)such that
Γu+b(c,r)=0andΓv+b′(c,r)=0.
Then, an additive cube ofxwith boundaries(pj,rj)corresponds to a triple(c,u,v)∈Zτ, wherec=(wp0,wp1,wp2,wp3)is the quadruple of letters at the boundaries, whileuandvmeasure the Parikh imbalances between the consecutive blocksdj=w[pj,pj+1). The offsetsrjare only required in this final membership test.
The tree of quadruples and the descent automaton
The tree T of quadruples, the map g and the automaton G
An additive cube is delimited by four positions. We therefore consider quadruples p=(p0,p1,p2,p3)∈N4 of positions. A child of p is a quadruple p′=(p0′,p1′,p2′,p3′) where each pj′ is a child of pj. The parent of p is par(p):=(par(p0),…,par(p3)). This defines a directed tree T rooted at (0,0,0,0) with edges from parents to children (see Figure 4 for an example). Each quadruple has at most 24=16 children. We do not require the quadruples p to be ordered: relative order between coordinates can be modified during the tree descent (from parents to children) when two coordinates in the parent are equal, but it will be fully recovered upon arrival by the equations (2).
Figure 4. A fragment of the tree T: the parent quadruple (2,3,5,6) generates (3,6,8,11) with the quadruple of labels (ε,0,ε,4). The latter has 23=8 children because three of its positions (those equal to 4, 1 and 0 in w) have an image of length 2, whereas the position equal to 3 has an image of length 1.
For instance, the following edges exist in T
(3,3,5,6)(ε,0,ε,ε)(5,6,8,10)
(3,3,5,6)(0,ε,ε,ε)(6,5,8,10)
(3,3,5,6)(0,ε,0,4)(6,5,9,11)
Let p∈N4 and let p′ be a child of p. By Lemma 7, for each j, one has σ(pj′)=Mσ(pj)+ψ(aj), where aj=φ(wpj)[0,pj′−η(pj))∈A is the label of the edge taken in Q. Combining these equalities, the imbalances u′=σ(p0′)−2σ(p1′)+σ(p2′) and v′=σ(p1′)−2σ(p2′)+σ(p3′) are equal to
In particular, a quadruple of positions p delimits an additive cube in x=τ(w) (for some offsets r) if and only if g(p)∈Zτ.
Instead of storing the positions p=(p0,p1,p2,p3), which grow arbitrarily large, we only need to remember the four boundary letters and the pair of imbalance vectors (u,v). The automaton G (see Definition 20 below) computes their evolution during the descent by multiplying by M and adding the boundary corrections. Searching for an additive cube thus reduces to a reachability problem in G.
Definition 20 (The infinite automaton G). The vertices of G are the states (c,u,v)∈Σ4×Z4×Z4. For each letter cj of the quadruple c, let ej=(cj,cj′) be an edge of Q with source cj, target cj′, and label aj∈A. Then G contains a directed edge from (c,u,v) to (c′,u′,v′), where
Hence, a state has as many outgoing transitions as there are combinations of choices for its four letters in Q (at most 24=16). Figure 5 illustrates three transitions from the state (c,u,v)=((0,0,0,3),0,e0). Since the letter 0 admits two outgoing edges in Q (towards 0 with label ε, or towards 3 with label 0) and the letter 3 has only one (towards 1 with label ε), this state has exactly 23×1=8 outgoing edges in G.
Figure 5. Local transitions in G from the state ((0,0,0,3),0,e0). Each edge corresponds to a 4-tuple of transitions in Q with labels (a0,a1,a2,a3), from which u′ and v′ are computed using M, u, v, and the Parikh vectors ψ(a0), ψ(a1), ψ(a2) and ψ(a3).
Lemma 21 (Compatibility of G with tree descent). Let p∈N4.
If p′ is a child of p in T, then g(p)→g(p′) is an edge in G.
Conversely, every edge in G leaving g(p) has the form g(p)→g(p′) for some child p′ of p in T.
Consequently, the map g establishes a label-preserving bijection between paths from p in T and paths from g(p) in G (see Figure 6).
Figure 6. Local commutation between tree descent in T and transitions in G.
Proof. 1. For each j∈{0,1,2,3}, let pj′=η(pj)+ij with 0≤ij<∣φ(wpj)∣. By Lemma 6(1), this gives the edge ej=(wpj,ij) of Q with target wpj′ and label aj. Applying Lemma 7 to each coordinate gives the formulas for u′ and v′ in Definition 20, so g(p)→g(p′) is an edge of G.
Conversely, an edge leaving g(p)=(c,u,v) corresponds to four edges ej=(cj,ij) in Q. Setting pj′=η(pj)+ij, each pj′ is a child of pj by Lemma 6(1), and part (1) shows that the target in G is precisely g(p′).
The 9 starting states
Let C be an additive cube in x=τ(w) with boundary positions qj=pos(pj,rj) satisfying p0≤p1≤p2≤p3 and p0<p3 (see Proposition 25). Following the ancestral chain of p=(p0,p1,p2,p3) in w, there exists k≥0 such that the four coordinates of park(p) fall within the image φ(wt) of a single letter wt. Since ∣φ(a)∣≤2 for every a∈Σ, these four positions can only take two consecutive values, say e and e+1. With p0<p3, this forces ∣φ(wt)∣=2 (so wt∈{0,1,4}) and leaves only three possible non-decreasing configurations for park(p):
(e,e,e,e+1),(e,e,e+1,e+1),and (e,e+1,e+1,e+1).
Since the parent letter wt belongs to {0,1,4}, this produces exactly 3×3=9 candidate starting quadruples.
Definition 22 (Seed set X). We define the set of seeds X⊂N4 by
Proof. Let p∈X. By the discussion above, p is one of the three configurations with positions in {e,e+1} (where e=η(t)), and its parent letter wt∈{0,1,4} satisfies φ(wt)=xy. We compute g(p)=(c,u,v) for each case:
If p=(e,e,e,e+1), then (d0,d1,d2)=(ε,ε,x), which gives c=(x,x,x,y), u=0, and v=ψ(x).
If p=(e,e,e+1,e+1), then (d0,d1,d2)=(ε,x,ε), which gives c=(x,x,y,y), u=ψ(x), and v=−ψ(x).
If p=(e,e+1,e+1,e+1), then (d0,d1,d2)=(x,ε,ε), which gives c=(x,y,y,y), u=−ψ(x), and v=0.
Running over xy∈{03,43,01} yields the nine stated triples. □
Explicitly, since ψ(0)=e0 and ψ(4)=e4, the nine starting states of g(X) are:
Lemma 24 (Every additive cube “descends” from a starting state). Let p∈N4 with p0≤p1≤p2≤p3 and p0<p3. There exists k≥0 such that park(p)∈X.
Proof. From Lemma 6(3) we know that the function par is increasing (not necessarily strictly). Hence, we have pari(p0)≤pari(pj)≤pari(p3) for every j∈{0,…,3} and every i≥0. By Lemma 6(3) again, pari(p0)=pari(p3)=0 for sufficiently large i. Since p0<p3, then there exists a maximal integer k≥0 such that park(p0)<park(p3). By maximality of k, we have park+1(p0)=park+1(p3). The inequalities then force all four coordinates of park(p) to share the same parent, which proves that park(p)∈X. □
Characterizing additive cubes by reachability in G
Proposition 25. Under (H0):
(a) If x contains an additive cube with boundaries qj=pos(pj,rj), then p0≤p1≤p2≤p3, p0<p3, and there exists an integer k≥0 such that park(p)∈X. Moreover,
g(park(p)),g(park−1(p)),…,g(p)
is a path in G from a vertex of g(X) to a vertex of Zτ.
(b) Conversely, if a path in G leads from a vertex of g(X) to a vertex of Zτ, then x contains an additive cube.
Proof. (a) Since the positions qj are strictly increasing, one has p0≤p1≤p2≤p3 (Lemma 17). If p0=p3, then all four positions pj are equal, and since r3<ℓ(wp0), the factor x[q0,q3) is entirely contained in τ(wp0), which contradicts (H0). Hence p0<p3, and from Lemma 24 there exists an index k≥0 such that park(p)∈X. By Lemma 21(1), descending from park(p) to p in T projects via g onto a valid path in G. Finally, the equations (2) characterizing the additive cube ensure that g(p)∈Zτ.
(b) Conversely, consider now a path in G from g(p′) (with p′∈X) to (c,u,v)∈Zτ. By Lemma 21(2), this path is the image under g of a path of descendants in T from p′ to some quadruple p, so that g(p)=(c,u,v). Since p0′<p3′ and η is strictly increasing, the relative order is preserved and p0<p3.
Let r be the offsets given by Definition 19 and let qj=pos(pj,rj). Since cj=wpj, these are valid positions in x. The equations defining Zτ imply q0−2q1+q2=0 and q1−2q2+q3=0, so the length L:=qj+1−qj is constant for j∈{0,1,2}. Furthermore,
q0<ℓ⋅σ(p0)+ℓ(wp0)=ℓ⋅σ(p0+1)≤ℓ⋅σ(p3)≤q3,
which gives 3L=q3−q0>0, hence L>0 and q0<q1<q2<q3. The other two equations give the equality of the sums: x[q0,q3) is an additive cube.
Thus, searching for an additive cube in x is equivalent to searching for a path in the infinite graph G from one of the nine vertices of g(X) to a vertex of Zτ. It remains to make this graph finite.
Restricting the graph G to a finite subgraph
Level zero and the transversality hypothesis (T)
Constraints at the leaf level. If x contains an additive cube, then the imbalance vectors u,v and their sum u+v=ψ(d2)−ψ(d0) (a Parikh difference between two factors of w) satisfy
Definition 26 (Initial state of level zero F0). We denote F0={z∈Z4∣Γz∈S and ∣θ3(z)∣≤C3}.
If x contains a cube, then u,v,u+v∈F0.
Why (T) is necessary: a cylinder cut by a hyperplane For F0 to be finite, an equation Γz=t (t∈S) and the bound ∣θ3(z)∣≤C3 must leave only finitely many integer points. For our eight morphisms, s is not collinear with ℓ: Γ has rank 2 and the set of real solutions of Γz=t is an affine plane z0+kerΓ. This equation alone is not sufficient. On the other hand, the bound on θ3 places z in the closed cylinder kerθ3+K, with axis kerθ3=VectR(q1,q2)⊂R4 and compact section K=VectR(Req3,Imq3)∩{∣θ3∣≤C3}. The intersection of the affine plane and the cylinder is compact if and only if kerΓ∩kerθ3={0}.
Definition 27 (Transversality hypothesis (T)). The morphism τ satisfies (T) if the real 4×4 matrix
Lemma 29. (Finiteness of level zero.) Under (T), the set F0 is finite.
Proof.Φ:R4→R4 is a linear isomorphism. Identifying C with R2: F0=Z4∩Φ−1(S×{ζ∈C:∣ζ∣≤C3}), and the preimage of a compact set under an isomorphism is compact; its intersection with the lattice Z4 is therefore finite.
The box U, the state space H and the finite graph G′
Following the reduction strategy introduced in [1], we now bound all coordinates to restrict the exploration of G to a finite induced subgraph. In [1], the initial bounds on θ1 and θ2 were deduced from a fixed two-dimensional integer lattice. Here, since τ and the boundary offsets modify lengths and sums, these initial bounds are instead controlled by the finite set F0, whose finiteness is ensured by the transversality hypothesis (T).
Definition 30. (Constants, box U, space H and graph G′.) For j∈{1,2}, we set
Cj=max(z∈F0max∣θj(z)∣,∣λj∣−1κj),C4=C3,
then
U={z∈Z4∣∣θj(z)∣≤Cj for 1≤j≤4},H={(c,u,v)∈Σ4×Z4×Z4∣u,v,u+v∈U}.
G′ is the subgraph of G induced on H, A0=g(X)∩H, and R is the set of vertices of G′ reachable from A0. Each θj is bounded on U and z=Qθ(z) (Definition 12), hence U is finite; H and G′ are finite too, with at most 44∣U∣2 vertices.
Remark 31. (One may always round up.) The rest of the work only uses the fact that U contains the vectors that actually occur. One may therefore replace each Cj by any upper bound: U, H, G′, R grow and Theorem 33 remains valid. This is what the numerical computation does (§ 6).
Proposition 32. (Confinement in H.) Under the hypotheses of Proposition 25(a), all vertices g(pari(p)), 0≤i≤k, belong to H.
Proof. Set dj(i)=w[pari(pj),pari(pj+1)) for j=0,1,2. The three vectors u(i)=ψ(d1(i))−ψ(d1(0)), v(i)=ψ(d2(i))−ψ(d2(0)) and u(i)+v(i)=ψ(d2(i))−ψ(d1(0)) are deviations Δi for a pair of factors.
Level 0. By (4) and (5), these three vectors are in F0; hence ∣θj(Δ0)∣≤maxF0∣θj∣ for j=1,2.
Levels i≥0. For j=1,2, Lemma 16 (with B=maxF0∣θj∣) gives ∣θj(Δi)∣≤Cj; for j=3,4, Theorem 14 gives ∣θj(Δi)∣≤C3. The three vectors are therefore in U.
Theorem 33. (Reduction Theorem.) Let τ:Σ∗→{0,1,2,3}∗ be non-erasing, satisfying (H0) and (T). Then
x=τ(w) is without additive cubes⟺R∩Zτ=∅.
Proof. (⇐) Suppose that x contains an additive cube. By Proposition 25(a), there exists a path in G from a vertex of g(X) to a vertex of Zτ. By Proposition 32, all its vertices are in H: it is a path of G′ issuing from A0, and its endpoint is in R∩Zτ.
(⇒) If R∩Zτ=∅, there exists a path of G′⊂G from A0⊂g(X) to Zτ; Proposition 25(b) provides an additive cube in x. □
Theorem 33 shows that the exhaustive search is indeed a proof: if an additive cube exists in x, even arbitrarily far away, its genealogy will leave a trace in the finite graph G′, from one of the 9 seeds to Zτ. For τ=id, we recover exactly the Theorem of [1].
Computation and results
The C++ program proof.cpp follows the proof:
it reads τ and tests (H0);
it computes M, its eigenvalues, its eigenvectors of norm 1, the forms θj, and tests (T) (detΦ=0);
it computes D9 (in integers, via Q), C∗, C3 and the κj;
it enumerates S and F0, then computes C1, C2 and enumerates U;
it performs a breadth-first traversal of G′ from A0, the edges being generated “on the fly” by Definition 20;
for each vertex reached, it tests membership in Zτ by running through the offsets r (at most 81 cases).
Everything is exact (integers) except steps 2 to 4; the constants computed there are rounded upwards (relative margin 10−9), which is permitted by Remark 31.
For τ1:0↦21,1↦100,3↦3,4↦23:
det(Φ)≈−10.53,∣S∣=43,∣F0∣=67,C1≈1.9032,
C2≈2.9818,C3≈2.1758,∣U∣=497.
The 9 starting states are in H. The traversal reaches ∣R∣=78340 vertices, at maximal depth 23, and 4078 patterns (b,b′) are tested; no vertex reached is in Zτ. Theorem 33 applies: τ1(w) contains no additive cube.
In fact, for all eight morphisms, the computation of F0 gives maxz∈F0∣θj(z)∣≤κj/(∣λj∣−1) for j∈{1,2}. Consequently, C1 and C2 are entirely determined by the second term of the maximum in Definition 30, which depends only on φ. Hence the box U, the state space H, the graph G′, and the set R are identical for all eight morphisms; only F0 and Zτ change. The eight morphisms were obtained by an exhaustive search of candidates (images of length ≤3, prefix of 106 letters without additive cubes):
ChatGPT (OpenAI, GPT-6) played a notable role in initiating this work. When consulted by the second author regarding the avoidability of additive cubes over {0,1,2,3}, it suggested a first candidate morphism, τ1, inspired by the morphism in [1], without a proof of correctness. The authors then proved that the infinite word τ1(w) is additive-cube-free and conducted an exhaustive search, which provided seven further morphisms as well as additional candidates of greater length, all of which can be proved by the same method. The authors take full responsibility for all mathematical results, proofs, and computations presented in this paper.
It is somewhat surprising that such an exhaustive search had not been done earlier; the emphasis in [5] on uniform morphisms of length at least 16 both discouraged any such search and directed intuition away from shorter and non-uniform ones, at least in the case of the first author.
References
[1]J. Cassaigne, J. D. Currie, L. Schaeffer, and J. Shallit. Avoiding three consecutive blocks of the same size and same sum. Journal of the ACM, 61(2):10:1–10:25, 2014. arXiv:1106.5204.arxiv.org/abs/1106.5204
[2]F. Lietard and M. Rosenfeld. Avoidability of additive cubes over alphabets of four numbers. In Developments in Language Theory (DLT 2020), volume 12086 of Lecture Notes in Computer Science, pages 192–206. Springer, 2020.DOI
[3]M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1983.
[4]G. Pirillo and S. Varricchio. On uniformly repetitive semigroups. Semigroup Forum, 49:125–129, 1994.DOI
[5]M. Rao. On some generalizations of abelian power avoidability. Theoretical Computer Science, 601:39–46, 2015.DOI