betaFeedback

WorksMathematics

Additive cubes are avoidable over {0,1,2,3}\{0,1,2,3\}, {0,1,4}\{0,1,4\} and {0,2,5}\{0,2,5\}

Abstract

We prove that additive cubes are avoidable over the alphabet {0,1,2,3}\{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}∗\{0,1,3,4\}^* to {0,1,2,3}∗\{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\mathbb{N}. Let Σ⊂N\Sigma\subset\mathbb{N} be an alphabet. A finite word u∈Σ∗u \in\Sigma^* has length ∣u∣=n|u| = n. The sum of the letters of uu is sum⁡(u)=\operatorname{sum}(u) =

∑k=0n−1uk\sum_{k=0}^{n-1} u_k

(with sum⁡(ε)=0\operatorname{sum}(\varepsilon) = 0).

Definition 1 (Additive cube). A non-empty finite word uu over an alphabet Σ⊆N\Sigma\subseteq\mathbb{N} is an additive cube if u=u1u2u3u = u_1u_2u_3 with u1u_1, u2u_2, u3∈Σ∗u_3 \in\Sigma^*, ∣u1∣=∣u2∣=∣u3∣|u_1| = |u_2| = |u_3| and sum⁡(u1)=sum⁡(u2)=sum⁡(u3)\operatorname{sum}(u_1) = \operatorname{sum}(u_2) = \operatorname{sum}(u_3). 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}\{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}\{0,1,2,3\}. Rao [5] extended the avoidability of additive cubes to ternary alphabets such as {0,1,5}\{0,1,5\}. The question for {0,1,2,3}\{0,1,2,3\} (question 5 of [5]) is, to our knowledge, still open.

We exhibit eight morphisms from {0,1,3,4}\{0,1,3,4\} to {0,1,2,3}\{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, Σ\Sigma denotes the alphabet {0,1,3,4}\{0,1,3,4\}, φ:Σ∗→Σ∗\varphi:\Sigma^* \to\Sigma^* denotes the morphism

φ(0)=03,φ(1)=43,φ(3)=1,φ(4)=01.\varphi(0)=03,\qquad\varphi(1)=43,\qquad\varphi(3)=1,\qquad\varphi(4)=01.

and w=lim⁡n→∞φn(0)=0314301103434303101101…=φ(w)\mathbf{w}=\lim_{n\to\infty}\varphi^n(0)=0314301103434303101101\ldots=\varphi(\mathbf{w}).

Theorem 2 ([1]). The infinite word w\mathbf{w} contains no additive cube.

Let τ:Σ∗→{0,1,2,3}∗\tau:\Sigma^* \to\{0,1,2,3\}^* be a non-erasing morphism, that is ∣τ(a)∣≥1|\tau(a)|\ge1 for every a∈Σa\in\Sigma. We denote:

ℓ:=(∣τ(0)∣∣τ(1)∣∣τ(3)∣∣τ(4)∣)=(ℓ(0)ℓ(1)ℓ(3)ℓ(4))∈(N∗)4,s:=(sum⁡(τ(0))sum⁡(τ(1))sum⁡(τ(3))sum⁡(τ(4)))=(s(0)s(1)s(3)s(4))∈N4,Γ:=(tℓts)∈Z2×4.\boldsymbol{\ell}:= \begin{pmatrix} |\tau(0)|\\ |\tau(1)|\\ |\tau(3)|\\ |\tau(4)| \end{pmatrix} = \begin{pmatrix} \ell(0)\\ \ell(1)\\ \ell(3)\\ \ell(4) \end{pmatrix} \in(\mathbb{N}^*)^4,\qquad \mathbf{s}:= \begin{pmatrix} \operatorname{sum}(\tau(0))\\ \operatorname{sum}(\tau(1))\\ \operatorname{sum}(\tau(3))\\ \operatorname{sum}(\tau(4)) \end{pmatrix} = \begin{pmatrix} s(0)\\ s(1)\\ s(3)\\ s(4) \end{pmatrix} \in\mathbb{N}^4,\qquad \Gamma:=\begin{pmatrix}\mathbf{t}_{\ell}\\\mathbf{t}_{s}\end{pmatrix}\in\mathbb{Z}^{2\times4}.

Let x=τ(w)=τ(w0)τ(w1)τ(w2)⋯\mathbf{x}=\tau(\mathbf{w})=\tau(w_0)\tau(w_1)\tau(w_2)\cdots.

We will check that the morphisms τ1,…,τ8\tau_1,\ldots,\tau_8 listed in Table 2 on page 15 satisfy two hypotheses:

τ(0), τ(1), τ(3), τ(4)\tau(0),\ \tau(1),\ \tau(3),\ \tau(4)ℓ\ells\mathbf{s}det⁡Φ\det\Phi∣F0∣\lvert F_0\rvert∣R∣\lvert R\rvertR∩ZτR \cap\mathbb{Z}_\tau
21, 100, 3, 2321,\ 100,\ 3,\ 232,3,1,22,3,1,23,1,3,53,1,3,5−10.53-10.5367677834078340∅\varnothing
12, 233, 0, 1012,\ 233,\ 0,\ 102,3,1,22,3,1,23,8,0,13,8,0,1+10.53+10.5367677834078340∅\varnothing
122, 331, 0, 10122,\ 331,\ 0,\ 103,3,1,23,3,1,25,7,0,15,7,0,1+10.32+10.321191197834078340∅\varnothing
211, 002, 3, 23211,\ 002,\ 3,\ 233,3,1,23,3,1,24,2,3,54,2,3,5−10.32-10.321191197834078340∅\varnothing
021, 001, 323, 321021,\ 001,\ 323,\ 3213,3,3,33,3,3,33,1,8,63,1,8,6−21.07-21.0789897834078340∅\varnothing
312, 332, 010, 012312,\ 332,\ 010,\ 0123,3,3,33,3,3,36,8,1,36,8,1,3+21.07+21.0789897834078340∅\varnothing
132, 332, 101, 102132,\ 332,\ 101,\ 1023,3,3,33,3,3,36,8,2,36,8,2,3+19.01+19.0187877834078340∅\varnothing
201, 001, 232, 231201,\ 001,\ 232,\ 2313,3,3,33,3,3,33,1,7,63,1,7,6−19.01-19.0187877834078340∅\varnothing

Table 2. Result of the traversal of G′\mathcal{G}' for the eight candidate morphisms.

  • (H0) for every a∈Σa\in\Sigma, τ(a)\tau(a) contains no additive cube;

  • (T) transversality: a specific 4×44\times4 matrix Φ\Phi depending on τ\tau is invertible (Definition 27).

Theorem 3 (Reduction theorem, precise statement in Theorem 33). Let τ:Σ∗→{0,1,2,3}∗\tau:\Sigma^* \to\{0,1,2,3\}^* be a non-erasing morphism satisfying (H0) and (T). There exist a finite graph G′G', a starting set A0A_0 of at most 9 vertices and an accepting set ZτZ_\tau such that, denoting by RR the set of vertices of G′G' reachable from A0A_0:

x=τ(w) avoids additive cubes⟺R∩Zτ=∅.\mathbf{x}=\tau(\mathbf{w})\text{ avoids additive cubes}\Longleftrightarrow R\cap Z_\tau=\varnothing.

Theorem 4 (Result of the computation, § 6). For each of the eight morphisms τ1,…,τ8\tau_1,\ldots,\tau_8 of Table 2 on page 15, the hypotheses (H0) and (T) are satisfied and the traversal of G′G' gives R∩Zτ=∅R\cap Z_\tau=\varnothing. By Theorem 3, τi(w)\tau_i(\mathbf{w}) is an infinite word over {0,1,2,3}\{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}\{0,1,4\} and {0,2,5}\{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\tau_1:0\mapsto21,\ 1\mapsto100,\ 3\mapsto3,\ 4\mapsto23. For this morphism, we have ℓ=t(2,3,1,2)\boldsymbol{\ell}={}^\mathrm{t}(2,3,1,2), s=t(3,1,3,5)\mathbf{s}={}^\mathrm{t}(3,1,3,5),

Γ=(23123135)andx=τ(0)τ(3)τ(1)τ(4)τ(3)τ(0)⋯=21 3 100 23 3 21⋯\Gamma=\begin{pmatrix}2&3&1&2\\3&1&3&5\end{pmatrix} \qquad\text{and}\qquad \mathbf{x}=\tau(0)\tau(3)\tau(1)\tau(4)\tau(3)\tau(0)\cdots=21\ 3\ 100\ 23\ 3\ 21\cdots

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⁡Σ\tau=\operatorname{id}_{\Sigma}, without boundary shifts. Our contribution adapts their machinery to handle the deformations induced by a coding morphism τ\tau.

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\mathbf{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\mathbb{R}^{4} with the canonical basis (e0,e1,e3,e4)(\mathbf{e}_0,\mathbf{e}_1,\mathbf{e}_3,\mathbf{e}_4) indexed by the letters of Σ\Sigma. The Parikh vector of a finite word uu is ψ(u)=t(∣u∣0,∣u∣1,∣u∣3,∣u∣4)∈N4\psi(u)={}^t(|u|_0,|u|_1,|u|_3,|u|_4)\in\mathbb{N}^{4}. For p≤qp\le q, we denote w[p,q)=wp⋯wq−1\mathbf{w}[p,q)=w_p\cdots w_{q-1} (with w[p,p)=ε\mathbf{w}[p,p)=\varepsilon) and σ(p)=ψ(w[0,p))\sigma(p)=\psi(\mathbf{w}[0,p)) is the Parikh vector of the prefix w0⋯wp−1w_0\cdots w_{p-1}; hence σ(0)=0\sigma(0)=\mathbf{0} and, for every factor b=w[p,q)b=\mathbf{w}[p,q), ψ(b)=σ(q)−σ(p)\psi(b)=\sigma(q)-\sigma(p).

The incidence matrix of φ\varphi is defined as the 4×44\times4 matrix whose columns are the Parikh vectors of the images of 00, 11, 33, and 44, in that order:

M=(ψ(φ(0))∣ψ(φ(1))∣ψ(φ(3))∣ψ(φ(4)))=(1001001111000100),ψ(φ(u))=Mψ(u).M=\bigl(\psi(\varphi(0))\mid\psi(\varphi(1))\mid\psi(\varphi(3))\mid\psi(\varphi(4))\bigr)=\begin{pmatrix}1&0&0&1\\0&0&1&1\\1&1&0&0\\0&1&0&0\end{pmatrix},\qquad\psi(\varphi(u))=M\psi(u).

Let η(p)=∣φ(w[0,p))∣\eta(p)=|\varphi(\mathbf{w}[0,p))| be the length of the image of the prefix w[0,p)\mathbf{w}[0,p) under φ\varphi.

For any integer qq, the parent of qq, denoted par⁡(q)\operatorname{par}(q), is the unique pp such that η(p)≤q<η(p+1)\eta(p)\le q<\eta(p+1); we then say that qq is a child of pp. Roughly speaking, the parent of an index qq is the unique index pp such that the image φ(wp)\varphi(w_p) covers the position qq within the word w\mathbf{w}.

The word w\mathbf{w} begins with w[0,20)=03143011034343031011\mathbf{w}[0,20)=03143011034343031011 (see Figure 1). Table 1 gives the values of η\eta, parents, and children for the first few positions.

Splitting of the first 20 positions of w into images $\varphi(w_t)$

Figure 1. Splitting of the first 20 positions of w\mathbf{w} into images φ(wt)\varphi(w_t). The indices under the brackets indicate the parent t=par⁡(q)t=\operatorname{par}(q).

position pp01234567891011
letter wpw_p031430110343
η(p)\eta(p)023578101214161719
par⁡(p)\operatorname{par}(p)001223345566
children of pp{0,1}\{0,1\}{2}\{2\}{3,4}\{3,4\}{5,6}\{5,6\}{7}\{7\}{8,9}\{8,9\}{10,11}\{10,11\}{12,13}\{12,13\}{14,15}\{14,15\}{16}\{16\}{17,18}\{17,18\}{19}\{19\}

Table 1. Values of η(p)\eta(p), par⁡(p)\operatorname{par}(p), and children for the first positions of w\mathbf{w}.

In Lemma 6, we recall the principal properties of η\eta and par⁡\operatorname{par}:

Lemma 6 (see Section 2.2 in [1]). 1. For every pp, w[η(p),η(p+1))=φ(wp)\mathbf{w}[\eta(p),\eta(p+1))=\varphi(w_p), that is the children of pp are exactly the integers η(p),η(p)+1,…,η(p)+∣φ(wp)∣−1\eta(p),\eta(p)+1,\ldots,\eta(p)+|\varphi(w_p)|-1.

  1. η\eta is strictly increasing, η(0)=0\eta(0)=0, and η(p)>p\eta(p)>p for every p≥1p\ge1.

  1. par⁡\operatorname{par} is increasing (not necessarily strictly), par⁡(0)=0\operatorname{par}(0)=0, and par⁡(p)<p\operatorname{par}(p)<p for every p≥1p\ge1. In particular, for every pp, we can find k≥0k\ge0 such that par⁡k(p)=0\operatorname{par}^{k}(p)=0.

We denote by A\mathcal{A} the set of proper prefixes of the images under φ\varphi:

A={ε,0,4}.\mathcal{A}=\{\varepsilon,0,4\}.

For every position qq with parent pp, the prefix w[0,q)\mathbf{w}[0,q) is the concatenation of the complete image φ(w[0,p))\varphi(\mathbf{w}[0,p)) of the parent prefix and a proper prefix a∈Aa \in\mathcal{A} of the image of the next letter wpw_p (Figure 2, case q=11q=11):

Decomposition of the prefix w[0, 11)

Figure 2. Decomposition of the prefix w[0,11)\mathbf{w}[0,11): the first ten letters form the complete image φ(w[0,6))\varphi(\mathbf{w}[0,6)), and the letter w10=4w_{10}=4 is a proper prefix a=φ(w6)[0,1)a=\varphi(w_6)[0,1) of φ(w6)\varphi(w_6).

w[0,q)=φ(w[0,p))⋅a=w[0,η(p))⋅w[η(p),q),a=φ(wp)[0,i),i=q−η(p).\mathbf{w}[0,q)=\varphi(\mathbf{w}[0,p))\cdot a=\mathbf{w}[0,\eta(p))\cdot\mathbf{w}[\eta(p),q),\qquad a=\varphi(w_p)[0,i),\qquad i=q-\eta(p).

Lemma 7 (see Lemma 3 in [1]). Let q∈Nq \in\mathbb{N}, p=par⁡(q)p=\operatorname{par}(q) and i=q−η(p)i=q-\eta(p) (0≤i<∣φ(wp)∣0 \le i < |\varphi(w_p)|). The word a=φ(wp)[0,i)a=\varphi(w_p)[0,i) is a proper prefix of φ(wp)\varphi(w_p) (hence a∈Aa \in\mathcal{A}) and

σ(q)=Mσ(p)+ψ(a).\sigma(q)=M\sigma(p)+\psi(a).

Corollary 8 (see Corollary 4 in [1]). Let p0∈Np_0 \in\mathbb{N} and pi+1=par⁡(pi)p_{i+1}=\operatorname{par}(p_i). For i≥0i \ge0, we set ai=w[η(pi+1),pi)∈Aa_i=\mathbf{w}[\eta(p_{i+1}),p_i) \in\mathcal{A}. Then

σ(p0)=∑i≥0Miψ(ai),\sigma(p_0)=\sum_{i\ge0}M^i\psi(a_i),

a finite sum since pi=0p_i=0 and ai=εa_i=\varepsilon for ii large enough.

Corollary 9 (see Corollary 4 in [1]). Let b=w[p,q)b=\mathbf{w}[p,q) be a factor and b′=w[par⁡(p),par⁡(q))b'=\mathbf{w}[\operatorname{par}(p),\operatorname{par}(q)) its parent factor. Then

ψ(b)=Mψ(b′)+δ,δ=ψ(a′)−ψ(a)∈D:=ψ(A)−ψ(A),\psi(b)=M\psi(b')+\delta,\qquad\delta=\psi(a')-\psi(a)\in D:=\psi(\mathcal{A})-\psi(\mathcal{A}),

where a=w[η(par⁡(p)),p)a=\mathbf{w}[\eta(\operatorname{par}(p)),p) and a′=w[η(par⁡(q)),q)a'=\mathbf{w}[\eta(\operatorname{par}(q)),q) are the proper prefixes of Lemma 7 at the boundaries pp and $q.

Remark 10 (Finiteness of boundary perturbations). Since ψ(ε)=0\psi(\varepsilon)=0, ψ(0)=e0\psi(0)=\mathbf{e}_0, ψ(4)=e4\psi(4)=\mathbf{e}_4, the set DD contains only 7 vectors: D={0,±e0,±e4,±(e0−e4)}D=\{0,\pm\mathbf{e}_0,\pm\mathbf{e}_4,\pm(\mathbf{e}_0-\mathbf{e}_4)\}. 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 aa) 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 QQ (Figure 3), See Section 2.4 in [1]). The graph QQ has the letters of Σ\Sigma as vertices. For each letter cc and each 0≤i<∣φ(c)∣0 \le i < |\varphi(c)|, it has an edge e=(c,i)e=(c,i) with source cc, target the letter φ(c)[i]\varphi(c)[i], and label φ(c)[0,i)∈A\varphi(c)[0,i) \in\mathcal{A}.

The graph $\mathcal{Q}$: parent $\to$ child transitions and their labels.

Figure 3. The graph Q\mathcal{Q}: parent →\to child transitions and their labels.

By Lemma 6(1), if qq is a child of pp, then q=η(p)+iq=\eta(p)+i with i<∣φ(wp)∣i<|\varphi(w_p)|; the pair (wp,i)(w_p,i) is an edge of QQ with source wpw_p, target wqw_q and label a=w[η(p),q)a=\mathbf{w}[\eta(p),q). In other words, the children of pp in ww are in bijection with the edges of QQ whose source is wpw_p.

The spectrum of MM

The characteristic polynomial of MM is X4−X3−2X2+2X−1X^4-X^3-2X^2+2X-1 and its roots are:

λ1≈+1.690284,λ2≈−1.505068,λ3≈0.407392+0.476565 i,λ4=λ3‾≈0.407392−0.476565 i(∣λ3∣=∣λ4∣≈0.626963).\begin{aligned} \lambda_1 &\approx+1.690284,\\ \lambda_2 &\approx-1.505068,\\ \lambda_3 &\approx0.407392+0.476565\,i,\\ \lambda_4=\overline{\lambda_3} &\approx0.407392-0.476565\,i \quad(|\lambda_3|=|\lambda_4|\approx0.626963). \end{aligned}

The eigenvalues are all simple, hence MM is diagonalizable over C\mathbb{C}: M=QΛQ−1M=Q\Lambda Q^{-1} with Λ=diag⁡(λ1,λ2,λ3,λ4)\Lambda=\operatorname{diag}(\lambda_1,\lambda_2,\lambda_3,\lambda_4).

Definition 12 (Linear forms θj\theta_j). For each jj, let qj∈C4q_j\in\mathbb{C}^4 be a unit eigenvector (∥qj∥2=1\lVert q_j\rVert_2=1) related to the eigenvalue λj\lambda_j, normalized such that its first component is real and strictly positive. The eigencoordinates θ1,…,θ4:C4→C\theta_1,\ldots,\theta_4:\mathbb{C}^4\to\mathbb{C} are the rows of Q−1Q^{-1}.

Q=(∣∣∣∣q1q2q3q4∣∣∣∣),Q−1=(− θ1 −− θ2 −− θ3 −− θ4 −).Q= \begin{pmatrix} | & | & | & |\\ q_1 & q_2 & q_3 & q_4\\ | & | & | & | \end{pmatrix}, \qquad Q^{-1}= \begin{pmatrix} -\ \theta_1\ -\\ -\ \theta_2\ -\\ -\ \theta_3\ -\\ -\ \theta_4\ - \end{pmatrix}.

For every z∈R4z\in\mathbb{R}^4: θj(Mz)=λjθj(z)\theta_j(Mz)=\lambda_j\theta_j(z), θ4(z)=θ3(z)‾\theta_4(z)=\overline{\theta_3(z)} (hence ∣θ3(z)∣=∣θ4(z)∣|\theta_3(z)|=|\theta_4(z)|), and z=∑j=14θj(z) qjz=\sum_{j=1}^4\theta_j(z)\,q_j.

Numerical values:

Q≈(0.47240.17810.62700.62700.55120.6714−0.2938−0.0553 i−0.2938+0.0553 i0.6056−0.56440.2782−0.4613 i0.2782+0.4613 i0.3261−0.4461−0.3715+0.2988 i−0.3715−0.2988 i),Q\approx \begin{pmatrix} 0.4724 & 0.1781 & 0.6270 & 0.6270\\ 0.5512 & 0.6714 & -0.2938-0.0553\,i & -0.2938+0.0553\,i\\ 0.6056 & -0.5644 & 0.2782-0.4613\,i & 0.2782+0.4613\,i\\ 0.3261 & -0.4461 & -0.3715+0.2988\,i & -0.3715-0.2988\,i \end{pmatrix},
Q−1≈(0.51240.59790.35370.65690.18060.6809−0.4524−0.57240.5788−0.5749 i−0.3219+0.2183 i−0.0690+0.6165 i−0.1662−0.6810 i0.5788+0.5749 i−0.3219−0.2183 i−0.0690−0.6165 i−0.1662+0.6810 i).Q^{-1}\approx \begin{pmatrix} 0.5124 & 0.5979 & 0.3537 & 0.6569\\ 0.1806 & 0.6809 & -0.4524 & -0.5724\\ 0.5788-0.5749\,i & -0.3219+0.2183\,i & -0.0690+0.6165\,i & -0.1662-0.6810\,i\\ 0.5788+0.5749\,i & -0.3219-0.2183\,i & -0.0690-0.6165\,i & -0.1662+0.6810\,i \end{pmatrix}.

Contracting directions: every deviation is bounded

We now exploit the contracting eigendirections to bound any Parikh deviation between factors of ww.

Definition 13 (Set of paths DℓD_\ell, Definition 7 in [1]). For ℓ≥1\ell\ge1, Dℓ⊂Z4D_\ell\subset\mathbb{Z}^{4} is the set of vectors

∑i=0ℓ−1Miψ(ai),\sum_{i=0}^{\ell-1} M^{i}\psi(a_i),

where (e0,…,eℓ−1)(e_0,\ldots,e_{\ell-1}) ranges over the sequences of edges of QQ such that the target of ei+1e_{i+1} is the source of eie_i for 0≤i<ℓ−10 \le i < \ell-1 (the path is read from the oldest generation eℓ−1e_{\ell-1} to the most recent one e0e_0), and aia_i is the label of eie_i.

The graph QQ has 466 paths of length 9, which generate 301 distinct vectors in D9D_9 (see proof of Theorem 8 [1]). We set:

C∗=max⁡s,t∈A∣θ3(ψ(s)−ψ(t))∣,C3=2(max⁡α,α′∈D9∣θ3(α)−θ3(α′)∣+C∗∣λ3∣91−∣λ3∣)≈2.175815.C_* = \max_{s,t\in A} \left|\theta_3(\psi(s)-\psi(t))\right|,\qquad C_3 = 2\left(\max_{\alpha,\alpha'\in D_9}\left|\theta_3(\alpha)-\theta_3(\alpha')\right|+\frac{C_*|\lambda_3|^9}{1-|\lambda_3|}\right)\approx2.175815.

Theorem 14 (Theorem 8 in [1]). For every pair of factors bb, cc of w\mathbf{w} (not necessarily of the same length, not necessarily consecutive):

∣θ3(ψ(b)−ψ(c))∣≤C3and∣θ4(ψ(b)−ψ(c))∣≤C3.\left|\theta_3(\psi(b)-\psi(c))\right|\le C_3\qquad\text{and}\qquad\left|\theta_4(\psi(b)-\psi(c))\right|\le C_3.

Expanding directions: stability under ascent

Let bb, cc be two factors of w\mathbf{w} with parents b′b', c′c'. By Corollary 9, the deviation Δ=ψ(b)−ψ(c)\Delta=\psi(b)-\psi(c) and the deviation Δ′=ψ(b′)−ψ(c′)\Delta'=\psi(b')-\psi(c') satisfy:

Δ=MΔ′+ρ,ρ=δ(b)−δ(c)∈E:=D−D,\Delta=M\Delta'+\rho,\qquad\rho=\delta(b)-\delta(c)\in E:=D-D,

where EE is a finite subset of Z4\mathbb{Z}^{4}. In the expanding directions (j=1,2j=1,2), applying this relation towards the children would amplify the deviation by a factor ∣λj∣>1.5|\lambda_j|>1.5 at each generation. We invert it: applying θj\theta_j,

θj(Δ′)=θj(Δ)−θj(ρ)λj.\theta_j(\Delta')=\frac{\theta_j(\Delta)-\theta_j(\rho)}{\lambda_j}.

Definition 15 (Constants κ1\kappa_1 and κ2\kappa_2). For j∈{1,2}j\in\{1,2\}, κj=max⁡ρ∈E∣θj(ρ)∣\kappa_j=\max_{\rho\in E}|\theta_j(\rho)|; numerically κ1≈1.3137\kappa_1\approx1.3137 and κ2≈1.5060\kappa_2\approx1.5060.

Iterating from an initial deviation Δ0\Delta_0, the deviation at the ii-th generation is:

Δi=M−iΔ0−∑k=0i−1M−(i−k)ρk,henceθj(Δi)=θj(Δ0)λji−∑m=1iθj(ρi−m)λjm.\Delta_i=M^{-i}\Delta_0-\sum_{k=0}^{i-1}M^{-(i-k)}\rho_k,\qquad\text{hence}\qquad\theta_j(\Delta_i)=\frac{\theta_j(\Delta_0)}{\lambda_j^i}-\sum_{m=1}^{i}\frac{\theta_j(\rho_{i-m})}{\lambda_j^m}.

Lemma 16 (Stability under ascent). Let j∈{1,2}j\in\{1,2\} and (Δi)i≥0(\Delta_i)_{i\ge0} be the sequence of deviations along a chain of ancestors, with ρk∈E\rho_k\in E. If ∣θj(Δ0)∣≤B|\theta_j(\Delta_0)|\le B, then for every i≥0i\ge0:

∣θj(Δi)∣≤max⁡(B,κj∣λj∣−1).|\theta_j(\Delta_i)|\le\max\left(B,\frac{\kappa_j}{|\lambda_j|-1}\right).

Proof. The case i=0i=0 holds. For i≥1i\ge1, the triangle inequality gives

∣θj(Δi)∣≤B∣λj∣i+κj∑m=1i1∣λj∣m=B∣λj∣i+κj∣λj∣−1(1−1∣λj∣i).|\theta_j(\Delta_i)|\le\frac{B}{|\lambda_j|^i}+\kappa_j\sum_{m=1}^{i}\frac{1}{|\lambda_j|^m}=\frac{B}{|\lambda_j|^i}+\frac{\kappa_j}{|\lambda_j|-1}\left(1-\frac{1}{|\lambda_j|^i}\right).

Since ∣λj∣>1|\lambda_j|>1, α=∣λj∣−i∈]0,1]\alpha=|\lambda_j|^{-i}\in]0,1] and the right-hand side is a convex combination αB+(1−α)κj∣λj∣−1\alpha B+(1-\alpha)\frac{\kappa_j}{|\lambda_j|-1} of BB and of κj∣λj∣−1\frac{\kappa_j}{|\lambda_j|-1}, hence bounded by their maximum.

Consequently, at every scales, the Parikh deviation between any two factors of w\mathbf{w} is bounded: by C3C_3 in directions 3, 4 (Theorem 14), and by max⁡(B,κj/(∣λj∣−1))\max(B,\kappa_j/(|\lambda_j|-1)) in directions 1, 2 (Lemma 16), where BB is the initial bound.

Additive cubes in x=τ(w)x=\tau(w) via ww

Positions in xx

For a∈Σa \in\Sigma and 0≤r≤ℓ(a)0 \le r \le\ell(a), we denote hr(a)=sum⁡(τ(a)[0,r))=∑k=0r−1τ(a)kh_r(a)=\operatorname{sum}(\tau(a)[0,r))=\sum_{k=0}^{r-1}\tau(a)_k the sum of the prefix of length rr of τ(a)\tau(a) (with h0(a)=0h_0(a)=0).

In general, a position qq of xx does not fall strictly between two images, but occurs at some rank (offset) rr within the image of a letter wpw_p. There exists a unique pair (p,r)(p,r) with 0≤r<ℓ(wp)0 \le r < \ell(w_p) and

x[0,q)=τ(w[0,p))⋅τ(wp)[0,r).x[0,q)=\tau(w[0,p))\cdot\tau(w_p)[0,r).

The offset rr is the number of letters “already consumed” from the image τ(wp)\tau(w_p).

Lemma 17 (Positions). Let P={(p,r):p∈N, 0≤r<ℓ(wp)}P=\{(p,r):p\in\mathbb{N},\ 0\le r<\ell(w_p)\} and pos⁡(p,r)=ℓ⋅σ(p)+r\operatorname{pos}(p,r)=\ell\cdot\sigma(p)+r. The map pos⁡:P→N\operatorname{pos}:P\to\mathbb{N} is a bijection, strictly increasing for the lexicographic order, and the sum H(q)=sum⁡(x[0,q))H(q)=\operatorname{sum}(x[0,q)) satisfies, for q=pos⁡(p,r)q=\operatorname{pos}(p,r),

H(q)=s⋅σ(p)+hr(wp).H(q)=s\cdot\sigma(p)+h_r(w_p).

Proof. The prefix τ(w[0,p))\tau(w[0,p)) of xx has length ℓ⋅σ(p)\ell\cdot\sigma(p) and sum s⋅σ(p)\mathbf{s}\cdot\sigma(p); the next rr letters form a prefix of τ(wp)\tau(w_p) of length r<ℓ(wp)r<\ell(w_p) and sum hr(wp)h_r(w_p). The monotonicity comes from the fact that ℓ⋅σ(p+1)=ℓ⋅σ(p)+ℓ(wp)\ell\cdot\sigma(p+1)=\ell\cdot\sigma(p)+\ell(w_p). Surjectivity comes from the fact that every position qq can be written in this way (see above).

The discrete curve of cumulative sums

For q=pos⁡(p,r)q=\operatorname{pos}(p,r), we denote

Λ(q)=(qH(q))=(ℓ⋅σ(p)s⋅σ(p))+(rhr(wp)).(1)\Lambda(q)= \begin{pmatrix} q\\ H(q) \end{pmatrix} = \begin{pmatrix} \ell\cdot\sigma(p)\\ \mathbf{s}\cdot\sigma(p) \end{pmatrix} + \begin{pmatrix} r\\ h_r(w_p) \end{pmatrix}. \tag*{(1)}

For q0=pos⁡(p0,r0)≤q1=pos⁡(p1,r1)q_0=\operatorname{pos}(p_0,r_0)\le q_1=\operatorname{pos}(p_1,r_1) and d0=w[p0,p1)d_0=w[p_0,p_1):

Λ(q1)−Λ(q0)=(∣x[q0,q1)∣sum⁡(x[q0,q1)))=Γψ(d0)+(r1−r0hr1(wp1)−hr0(wp0)).\Lambda(q_1)-\Lambda(q_0)= \begin{pmatrix} |x[q_0,q_1)|\\ \operatorname{sum}(x[q_0,q_1)) \end{pmatrix} =\Gamma\psi(d_0)+ \begin{pmatrix} r_1-r_0\\ h_{r_1}(w_{p_1})-h_{r_0}(w_{p_0}) \end{pmatrix}.

Equations of a cube

Let 0≤q0<q1<q2<q30\le q_0<q_1<q_2<q_3, qj=pos⁡(pj,rj)q_j=\operatorname{pos}(p_j,r_j), cj=wpjc_j=w_{p_j} (hence p0≤p1≤p2≤p3p_0\le p_1\le p_2\le p_3 by Lemma 17), and dj=w[pj,pj+1)d_j=w[p_j,p_{j+1}) for j=0,1,2j=0,1,2. We set:

u=ψ(d1)−ψ(d0)=σ(p0)−2σ(p1)+σ(p2),v=ψ(d2)−ψ(d1)=σ(p1)−2σ(p2)+σ(p3),\mathbf{u}=\psi(d_1)-\psi(d_0)=\sigma(p_0)-2\sigma(p_1)+\sigma(p_2),\qquad \mathbf{v}=\psi(d_2)-\psi(d_1)=\sigma(p_1)-2\sigma(p_2)+\sigma(p_3),

the imbalances between neighboring blocks of ww. The three factors x[q0,q1)x[q_0,q_1), x[q1,q2)x[q_1,q_2), x[q2,q3)x[q_2,q_3) form an additive cube if and only if Λ(q1)−Λ(q0)=Λ(q2)−Λ(q1)=Λ(q3)−Λ(q2)\Lambda(q_1)-\Lambda(q_0)=\Lambda(q_2)-\Lambda(q_1)=\Lambda(q_3)-\Lambda(q_2), that is, if and only if:

Λ(q0)−2Λ(q1)+Λ(q2)=0andΛ(q1)−2Λ(q2)+Λ(q3)=0.\Lambda(q_0)-2\Lambda(q_1)+\Lambda(q_2)=0 \quad\text{and}\quad \Lambda(q_1)-2\Lambda(q_2)+\Lambda(q_3)=0.

By (1), the first expression equals Γu+b(c,r)\Gamma\mathbf{u}+\mathbf{b}(\mathbf{c},\mathbf{r}) and the second Γv+b′(c,r)\Gamma\mathbf{v}+\mathbf{b}'(\mathbf{c},\mathbf{r}), with:

b(c,r)=(r0−2r1+r2hr0(c0)−2hr1(c1)+hr2(c2)),b′(c,r)=(r1−2r2+r3hr1(c1)−2hr2(c2)+hr3(c3)).\mathbf{b}(\mathbf{c},\mathbf{r})= \begin{pmatrix} r_0-2r_1+r_2\\ h_{r_0}(c_0)-2h_{r_1}(c_1)+h_{r_2}(c_2) \end{pmatrix}, \qquad \mathbf{b}'(\mathbf{c},\mathbf{r})= \begin{pmatrix} r_1-2r_2+r_3\\ h_{r_1}(c_1)-2h_{r_2}(c_2)+h_{r_3}(c_3) \end{pmatrix}.

Thus:

x[q0,q1)⋅x[q1,q2)⋅x[q2,q3) is an additive cube⟺Γu+b(c,r)=Γv+b′(c,r)=0.(2)x[q_0,q_1)\cdot x[q_1,q_2)\cdot x[q_2,q_3)\text{ is an additive cube} \Longleftrightarrow \Gamma\mathbf{u}+\mathbf{b}(\mathbf{c},\mathbf{r}) =\Gamma\mathbf{v}+\mathbf{b}'(\mathbf{c},\mathbf{r})=0. \tag*{(2)}

The terms b,b′\mathbf{b},\mathbf{b}' depend only on the four letters c=(c0,c1,c2,c3)\mathbf{c}=(c_0,c_1,c_2,c_3) and the four offsets r=(r0,r1,r2,r3)\mathbf{r}=(r_0,r_1,r_2,r_3): they take only finitely many values.

Hypothesis (H0) and accepting set

Definition 18 (Local hypothesis (H0)). The morphism τ\tau satisfies (H0) if for every a∈Σa \in\Sigma, τ(a)\tau(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 cccccc. Hence every morphism satisfies hypothesis (H0).

Definition 19 (Accepting set ZτZ_\tau). The set Zτ⊂Σ4×Z4×Z4Z_\tau\subset\Sigma^4 \times\mathbb{Z}^4 \times\mathbb{Z}^4 is the set of triples (c,u,v)(\mathbf{c},\mathbf{u},\mathbf{v}) for which there exist offsets rj∈{0,…,ℓ(cj)−1}r_j \in\{0,\ldots,\ell(c_j)-1\} (j=0,…,3)(j=0,\ldots,3) such that

Γu+b(c,r)=0andΓv+b′(c,r)=0.\Gamma\mathbf{u}+\mathbf{b}(\mathbf{c},\mathbf{r})=\mathbf{0} \quad\text{and}\quad \Gamma\mathbf{v}+\mathbf{b}'(\mathbf{c},\mathbf{r})=\mathbf{0}.

Then, an additive cube of x\mathbf{x} with boundaries (pj,rj)(p_j,r_j) corresponds to a triple (c,u,v)∈Zτ(\mathbf{c},\mathbf{u},\mathbf{v}) \in Z_\tau, where c=(wp0,wp1,wp2,wp3)\mathbf{c}=(w_{p_0},w_{p_1},w_{p_2},w_{p_3}) is the quadruple of letters at the boundaries, while u\mathbf{u} and v\mathbf{v} measure the Parikh imbalances between the consecutive blocks dj=w[pj,pj+1)d_j=w[p_j,p_{j+1}). The offsets rjr_j are only required in this final membership test.

The tree of quadruples and the descent automaton

The tree TT of quadruples, the map gg and the automaton GG

An additive cube is delimited by four positions. We therefore consider quadruples p=(p0,p1,p2,p3)∈N4\mathbf{p}=(p_0,p_1,p_2,p_3)\in\mathbb{N}^4 of positions. A child of p\mathbf{p} is a quadruple p′=(p0′,p1′,p2′,p3′)\mathbf{p}'=(p'_0,p'_1,p'_2,p'_3) where each pj′p'_j is a child of pjp_j. The parent of p\mathbf{p} is par⁡(p):=(par⁡(p0),…,par⁡(p3))\operatorname{par}(\mathbf{p}):=(\operatorname{par}(p_0),\ldots,\operatorname{par}(p_3)). This defines a directed tree TT rooted at (0,0,0,0)(0,0,0,0) with edges from parents to children (see Figure 4 for an example). Each quadruple has at most 24=162^4=16 children. We do not require the quadruples p\mathbf{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).

A fragment of the tree $\mathcal{T}$

Figure 4. A fragment of the tree T\mathcal{T}: the parent quadruple (2,3,5,6)(2,3,5,6) generates (3,6,8,11)(3,6,8,11) with the quadruple of labels (ε,0,ε,4)(\varepsilon,0,\varepsilon,4). The latter has 23=82^3=8 children because three of its positions (those equal to 44, 11 and 00 in ww) have an image of length 22, whereas the position equal to 33 has an image of length 11.

For instance, the following edges exist in TT

(3,3,5,6)→(ε,0,ε,ε)(5,6,8,10)(3,3,5,6)\xrightarrow{(\varepsilon,0,\varepsilon,\varepsilon)}(5,6,8,10)
(3,3,5,6)→(0,ε,ε,ε)(6,5,8,10)(3,3,5,6)\xrightarrow{(0,\varepsilon,\varepsilon,\varepsilon)}(6,5,8,10)
(3,3,5,6)→(0,ε,0,4)(6,5,9,11)(3,3,5,6)\xrightarrow{(0,\varepsilon,0,4)}(6,5,9,11)

Let p∈N4\mathbf{p}\in\mathbb{N}^4 and let p′\mathbf{p}' be a child of p\mathbf{p}. By Lemma 7, for each jj, one has σ(pj′)=Mσ(pj)+ψ(aj)\sigma(p'_j)=M\sigma(p_j)+\psi(a_j), where aj=φ(wpj)[0,pj′−η(pj))∈Aa_j=\varphi(w_{p_j})[0,p'_j-\eta(p_j))\in\mathcal{A} is the label of the edge taken in QQ. Combining these equalities, the imbalances u′=σ(p0′)−2σ(p1′)+σ(p2′)\mathbf{u}'=\sigma(p'_0)-2\sigma(p'_1)+\sigma(p'_2) and v′=σ(p1′)−2σ(p2′)+σ(p3′)\mathbf{v}'=\sigma(p'_1)-2\sigma(p'_2)+\sigma(p'_3) are equal to

u′=Mu+ψ(a0)−2ψ(a1)+ψ(a2),v′=Mv+ψ(a1)−2ψ(a2)+ψ(a3).\mathbf{u}'=M\mathbf{u}+\psi(a_0)-2\psi(a_1)+\psi(a_2),\qquad \mathbf{v}'=M\mathbf{v}+\psi(a_1)-2\psi(a_2)+\psi(a_3).

They therefore depend neither on p\mathbf{p} nor on p′\mathbf{p}', but only on (u,v)(\mathbf{u},\mathbf{v}) and the corresponding labels in QQ. We define the state map gg as follows:

g(p)=((wp0,wp1,wp2,wp3),σ(p0)−2σ(p1)+σ(p2),σ(p1)−2σ(p2)+σ(p3))∈Σ4×Z4×Z4.(3)g(\mathbf{p})=\bigl((w_{p_0},w_{p_1},w_{p_2},w_{p_3}),\sigma(p_0)-2\sigma(p_1)+\sigma(p_2),\sigma(p_1)-2\sigma(p_2)+\sigma(p_3)\bigr)\in\Sigma^4\times\mathbb{Z}^4\times\mathbb{Z}^4. \tag*{(3)}

In particular, a quadruple of positions p\mathbf{p} delimits an additive cube in x=τ(w)\mathbf{x}=\tau(\mathbf{w}) (for some offsets r\mathbf{r}) if and only if g(p)∈Zτg(\mathbf{p})\in Z_\tau.

Instead of storing the positions p=(p0,p1,p2,p3)\mathbf{p}=(p_0,p_1,p_2,p_3), which grow arbitrarily large, we only need to remember the four boundary letters and the pair of imbalance vectors (u,v)(\mathbf{u},\mathbf{v}). The automaton GG (see Definition 20 below) computes their evolution during the descent by multiplying by MM and adding the boundary corrections. Searching for an additive cube thus reduces to a reachability problem in GG.

Definition 20 (The infinite automaton G\mathcal{G}). The vertices of G\mathcal{G} are the states (c,u,v)∈Σ4×Z4×Z4(\mathbf{c},\mathbf{u},\mathbf{v})\in\Sigma^4\times\mathbb{Z}^4\times\mathbb{Z}^4. For each letter cjc_j of the quadruple c\mathbf{c}, let ej=(cj,cj′)e_j=(c_j,c'_j) be an edge of Q\mathcal{Q} with source cjc_j, target cj′c'_j, and label aj∈Aa_j\in A. Then G\mathcal{G} contains a directed edge from (c,u,v)(\mathbf{c},\mathbf{u},\mathbf{v}) to (c′,u′,v′)(\mathbf{c}',\mathbf{u}',\mathbf{v}'), where

u′=Mu+ψ(a0)−2ψ(a1)+ψ(a2),v′=Mv+ψ(a1)−2ψ(a2)+ψ(a3).\mathbf{u}'=M\mathbf{u}+\psi(a_0)-2\psi(a_1)+\psi(a_2),\qquad\mathbf{v}'=M\mathbf{v}+\psi(a_1)-2\psi(a_2)+\psi(a_3).

Hence, a state has as many outgoing transitions as there are combinations of choices for its four letters in Q\mathcal{Q} (at most 24=162^4=16). Figure 5 illustrates three transitions from the state (c,u,v)=((0,0,0,3),0,e0)(\mathbf{c},\mathbf{u},\mathbf{v})=((0,0,0,3),\mathbf{0},\mathbf{e}_0). Since the letter 00 admits two outgoing edges in Q\mathcal{Q} (towards 00 with label ε\varepsilon, or towards 33 with label 00) and the letter 33 has only one (towards 11 with label ε\varepsilon), this state has exactly 23×1=82^3\times1=8 outgoing edges in G\mathcal{G}.

Local transitions in $\mathcal{G}$ from the state $((0,0,0,3),\mathbf{0},\mathbf{e}_0)$

Figure 5. Local transitions in G\mathcal{G} from the state ((0,0,0,3),0,e0)((0,0,0,3),\mathbf{0},\mathbf{e}_0). Each edge corresponds to a 4-tuple of transitions in Q\mathcal{Q} with labels (a0,a1,a2,a3)(a_0,a_1,a_2,a_3), from which u′\mathbf{u}' and v′\mathbf{v}' are computed using MM, u\mathbf{u}, v\mathbf{v}, and the Parikh vectors ψ(a0)\psi(a_0), ψ(a1)\psi(a_1), ψ(a2)\psi(a_2) and ψ(a3)\psi(a_3).

Lemma 21 (Compatibility of G\mathcal{G} with tree descent). Let p∈N4\mathbf{p} \in\mathbb{N}^{4}.

  1. If p′\mathbf{p}' is a child of p\mathbf{p} in T\mathcal{T}, then g(p)→g(p′)g(\mathbf{p}) \to g(\mathbf{p}') is an edge in G\mathcal{G}.

  1. Conversely, every edge in G\mathcal{G} leaving g(p)g(\mathbf{p}) has the form g(p)→g(p′)g(\mathbf{p}) \to g(\mathbf{p}') for some child p′\mathbf{p}' of p\mathbf{p} in T\mathcal{T}.

Consequently, the map gg establishes a label-preserving bijection between paths from p\mathbf{p} in T\mathcal{T} and paths from g(p)g(\mathbf{p}) in G\mathcal{G} (see Figure 6).

Local commutation between tree descent in T and transitions in G

Figure 6. Local commutation between tree descent in T\mathcal{T} and transitions in G\mathcal{G}.

Proof. 1. For each j∈{0,1,2,3}j \in\{0,1,2,3\}, let pj′=η(pj)+ij\mathbf{p}'_j = \eta(p_j)+i_j with 0≤ij<∣φ(wpj)∣0 \leq i_j < |\varphi(w_{p_j})|. By Lemma 6(1), this gives the edge ej=(wpj,ij)e_j=(w_{p_j},i_j) of Q\mathcal{Q} with target wpj′w_{p'_j} and label aja_j. Applying Lemma 7 to each coordinate gives the formulas for u′\mathbf{u}' and v′\mathbf{v}' in Definition 20, so g(p)→g(p′)g(\mathbf{p}) \to g(\mathbf{p}') is an edge of G\mathcal{G}.

  1. Conversely, an edge leaving g(p)=(c,u,v)g(\mathbf{p})=(\mathbf{c},\mathbf{u},\mathbf{v}) corresponds to four edges ej=(cj,ij)e_j=(c_j,i_j) in Q\mathcal{Q}. Setting pj′=η(pj)+ijp'_j=\eta(p_j)+i_j, each pj′p'_j is a child of pjp_j by Lemma 6(1), and part (1) shows that the target in G\mathcal{G} is precisely g(p′)g(\mathbf{p}').

The 9 starting states

Let CC be an additive cube in x=τ(w)\mathbf{x}=\tau(\mathbf{w}) with boundary positions qj=pos⁡(pj,rj)q_j=\operatorname{pos}(p_j,r_j) satisfying p0≤p1≤p2≤p3p_0 \leq p_1 \leq p_2 \leq p_3 and p0<p3p_0 < p_3 (see Proposition 25). Following the ancestral chain of p=(p0,p1,p2,p3)\mathbf{p}=(p_0,p_1,p_2,p_3) in w\mathbf{w}, there exists k≥0k \geq0 such that the four coordinates of par⁡k(p)\operatorname{par}^{k}(\mathbf{p}) fall within the image φ(wt)\varphi(w_t) of a single letter wtw_t. Since ∣φ(a)∣≤2|\varphi(a)| \leq2 for every a∈Σa \in\Sigma, these four positions can only take two consecutive values, say ee and e+1e+1. With p0<p3p_0 < p_3, this forces ∣φ(wt)∣=2|\varphi(w_t)|=2 (so wt∈{0,1,4}w_t \in\{0,1,4\}) and leaves only three possible non-decreasing configurations for par⁡k(p)\operatorname{par}^{k}(\mathbf{p}):

(e,e,e,e+1),(e,e,e+1,e+1),and (e,e+1,e+1,e+1).(e,e,e,e+1), \qquad(e,e,e+1,e+1), \qquad\text{and }(e,e+1,e+1,e+1).

Since the parent letter wtw_t belongs to {0,1,4}\{0,1,4\}, this produces exactly 3×3=93 \times3=9 candidate starting quadruples.

Definition 22 (Seed set XX). We define the set of seeds X⊂N4X \subset\mathbb{N}^{4} by

X:={p∈N4∣p0≤p1≤p2≤p3, p0<p3, and par⁡(p0)=par⁡(p1)=par⁡(p2)=par⁡(p3)}.X := \{\mathbf{p} \in\mathbb{N}^{4} \mid p_0 \leq p_1 \leq p_2 \leq p_3,\ p_0 < p_3,\ \text{and }\operatorname{par}(p_0)=\operatorname{par}(p_1)=\operatorname{par}(p_2)=\operatorname{par}(p_3)\}.

Lemma 23 (The nine starting states). The image set g(X)g(X) consists of the nine vertices given, for each xy∈{03,43,01}xy \in\{03,43,01\}, by:

((x,x,x,y),0,ψ(x)),((x,x,y,y),ψ(x),−ψ(x)),((x,y,y,y),−ψ(x),0).\bigl((x,x,x,y),0,\psi(x)\bigr), \qquad\bigl((x,x,y,y),\psi(x),-\psi(x)\bigr), \qquad\bigl((x,y,y,y),-\psi(x),0\bigr).

Proof. Let p∈X\mathbf{p} \in X. By the discussion above, p\mathbf{p} is one of the three configurations with positions in {e,e+1}\{e,e+1\} (where e=η(t)e=\eta(t)), and its parent letter wt∈{0,1,4}w_t \in\{0,1,4\} satisfies φ(wt)=xy\varphi(w_t)=xy. We compute g(p)=(c,u,v)g(\mathbf{p})=(\mathbf{c},\mathbf{u},v) for each case:

  1. If p=(e,e,e,e+1)\mathbf{p}=(e,e,e,e+1), then (d0,d1,d2)=(ε,ε,x)(d_0,d_1,d_2)=(\varepsilon,\varepsilon,x), which gives c=(x,x,x,y)\mathbf{c}=(x,x,x,y), u=0\mathbf{u}=0, and v=ψ(x)v=\psi(x).

  1. If p=(e,e,e+1,e+1)\mathbf{p}=(e,e,e+1,e+1), then (d0,d1,d2)=(ε,x,ε)(d_0,d_1,d_2)=(\varepsilon,x,\varepsilon), which gives c=(x,x,y,y)\mathbf{c}=(x,x,y,y), u=ψ(x)\mathbf{u}=\psi(x), and v=−ψ(x)v=-\psi(x).

  1. If p=(e,e+1,e+1,e+1)\mathbf{p}=(e,e+1,e+1,e+1), then (d0,d1,d2)=(x,ε,ε)(d_0,d_1,d_2)=(x,\varepsilon,\varepsilon), which gives c=(x,y,y,y)\mathbf{c}=(x,y,y,y), u=−ψ(x)\mathbf{u}=-\psi(x), and v=0v=0.

Running over xy∈{03,43,01}xy \in\{03,43,01\} yields the nine stated triples. □\square

Explicitly, since ψ(0)=e0\psi(0)=\mathbf{e}_0 and ψ(4)=e4\psi(4)=\mathbf{e}_4, the nine starting states of g(X)g(X) are:

  • for φ(0)=03\varphi(0)=03:

((0,0,0,3),0,e0),((0,0,3,3),e0,−e0),((0,3,3,3),−e0,0);((0,0,0,3),\mathbf{0},\mathbf{e}_0),\quad((0,0,3,3),\mathbf{e}_0,-\mathbf{e}_0),\quad((0,3,3,3),-\mathbf{e}_0,\mathbf{0});
  • for φ(1)=43\varphi(1)=43:

((4,4,4,3),0,e4),((4,4,3,3),e4,−e4),((4,3,3,3),−e4,0);((4,4,4,3),\mathbf{0},\mathbf{e}_4),\quad((4,4,3,3),\mathbf{e}_4,-\mathbf{e}_4),\quad((4,3,3,3),-\mathbf{e}_4,\mathbf{0});
  • for φ(4)=01\varphi(4)=01:

((0,0,0,1),0,e0),((0,0,1,1),e0,−e0),((0,1,1,1),−e0,0).((0,0,0,1),\mathbf{0},\mathbf{e}_0),\quad((0,0,1,1),\mathbf{e}_0,-\mathbf{e}_0),\quad((0,1,1,1),-\mathbf{e}_0,\mathbf{0}).

Lemma 24 (Every additive cube “descends” from a starting state). Let p∈N4\mathbf{p} \in\mathbb{N}^{4} with p0≤p1≤p2≤p3p_0 \le p_1 \le p_2 \le p_3 and p0<p3p_0 < p_3. There exists k≥0k \ge0 such that par⁡k(p)∈X\operatorname{par}^{k}(\mathbf{p}) \in X.

Proof. From Lemma 6(3) we know that the function par⁡\operatorname{par} is increasing (not necessarily strictly). Hence, we have par⁡i(p0)≤par⁡i(pj)≤par⁡i(p3)\operatorname{par}^{i}(p_0) \le\operatorname{par}^{i}(p_j) \le\operatorname{par}^{i}(p_3) for every j∈{0,…,3}j \in\{0,\ldots,3\} and every i≥0i \ge0. By Lemma 6(3) again, par⁡i(p0)=par⁡i(p3)=0\operatorname{par}^{i}(p_0)=\operatorname{par}^{i}(p_3)=0 for sufficiently large ii. Since p0<p3p_0 < p_3, then there exists a maximal integer k≥0k \ge0 such that par⁡k(p0)<par⁡k(p3)\operatorname{par}^{k}(p_0) < \operatorname{par}^{k}(p_3). By maximality of kk, we have par⁡k+1(p0)=par⁡k+1(p3)\operatorname{par}^{k+1}(p_0)=\operatorname{par}^{k+1}(p_3). The inequalities then force all four coordinates of par⁡k(p)\operatorname{par}^{k}(\mathbf{p}) to share the same parent, which proves that par⁡k(p)∈X\operatorname{par}^{k}(\mathbf{p}) \in X. □\square

Characterizing additive cubes by reachability in G\mathcal{G}

Proposition 25. Under (H0)(H0):

(a) If xx contains an additive cube with boundaries qj=pos⁡(pj,rj)q_j=\operatorname{pos}(p_j,r_j), then p0≤p1≤p2≤p3p_0 \le p_1 \le p_2 \le p_3, p0<p3p_0 < p_3, and there exists an integer k≥0k \ge0 such that par⁡k(p)∈X\operatorname{par}^{k}(\mathbf{p}) \in X. Moreover,

g(par⁡k(p)), g(par⁡k−1(p)), …, g(p)g(\operatorname{par}^{k}(\mathbf{p})),\ g(\operatorname{par}^{k-1}(\mathbf{p})),\ \ldots,\ g(\mathbf{p})

is a path in G\mathcal{G} from a vertex of g(X)g(X) to a vertex of ZτZ_{\tau}.

(b) Conversely, if a path in G\mathcal{G} leads from a vertex of g(X)g(X) to a vertex of ZτZ_{\tau}, then xx contains an additive cube.

Proof. (a) Since the positions qjq_j are strictly increasing, one has p0≤p1≤p2≤p3p_0 \le p_1 \le p_2 \le p_3 (Lemma 17). If p0=p3p_0=p_3, then all four positions pjp_j are equal, and since r3<ℓ(wp0)r_3<\ell(w_{p_0}), the factor x[q0,q3)x[q_0,q_3) is entirely contained in τ(wp0)\tau(w_{p_0}), which contradicts (H0)(H0). Hence p0<p3p_0<p_3, and from Lemma 24 there exists an index k≥0k \ge0 such that par⁡k(p)∈X\operatorname{par}^{k}(\mathbf{p}) \in X. By Lemma 21(1), descending from par⁡k(p)\operatorname{par}^{k}(\mathbf{p}) to p\mathbf{p} in TT projects via gg onto a valid path in G\mathcal{G}. Finally, the equations (2) characterizing the additive cube ensure that g(p)∈Zτg(\mathbf{p}) \in Z_{\tau}.

(b) Conversely, consider now a path in G\mathcal{G} from g(p′)g(\mathbf{p}') (with p′∈X\mathbf{p}' \in X) to (c,u,v)∈Zτ(\mathbf{c},\mathbf{u},\mathbf{v}) \in Z_\tau. By Lemma 21(2), this path is the image under gg of a path of descendants in T\mathcal{T} from p′\mathbf{p}' to some quadruple p\mathbf{p}, so that g(p)=(c,u,v)g(\mathbf{p})=(\mathbf{c},\mathbf{u},\mathbf{v}). Since p0′<p3′p'_0<p'_3 and η\eta is strictly increasing, the relative order is preserved and p0<p3p_0<p_3.

Let r\mathbf{r} be the offsets given by Definition 19 and let qj=pos⁡(pj,rj)q_j=\operatorname{pos}(p_j,r_j). Since cj=wpjc_j=w_{p_j}, these are valid positions in xx. The equations defining ZτZ_\tau imply q0−2q1+q2=0q_0-2q_1+q_2=0 and q1−2q2+q3=0q_1-2q_2+q_3=0, so the length L:=qj+1−qjL:=q_{j+1}-q_j is constant for j∈{0,1,2}j\in\{0,1,2\}. Furthermore,

q0<ℓ⋅σ(p0)+ℓ(wp0)=ℓ⋅σ(p0+1)≤ℓ⋅σ(p3)≤q3,q_0 < \ell\cdot\sigma(p_0)+\ell(w_{p_0})=\ell\cdot\sigma(p_0+1)\le\ell\cdot\sigma(p_3)\le q_3,

which gives 3L=q3−q0>03L=q_3-q_0>0, hence L>0L>0 and q0<q1<q2<q3q_0<q_1<q_2<q_3. The other two equations give the equality of the sums: x[q0,q3)x[q_0,q_3) is an additive cube.

Thus, searching for an additive cube in x\mathbf{x} is equivalent to searching for a path in the infinite graph G\mathcal{G} from one of the nine vertices of g(X)g(X) to a vertex of ZτZ_\tau. It remains to make this graph finite.

Restricting the graph G\mathcal{G} to a finite subgraph

Level zero and the transversality hypothesis (T)

Constraints at the leaf level. If x\mathbf{x} contains an additive cube, then the imbalance vectors u,v\mathbf{u},\mathbf{v} and their sum u+v=ψ(d2)−ψ(d0)\mathbf{u}+\mathbf{v}=\psi(d_2)-\psi(d_0) (a Parikh difference between two factors of w\mathbf{w}) satisfy

Γu=−b(c,r),Γv=−b′(c,r),Γ(u+v)=−(b(c,r)+b′(c,r)),(4)\Gamma\mathbf{u}=-\mathbf{b}(\mathbf{c},\mathbf{r}),\qquad \Gamma\mathbf{v}=-\mathbf{b}'(\mathbf{c},\mathbf{r}),\qquad \Gamma(\mathbf{u}+\mathbf{v})=-\bigl(\mathbf{b}(\mathbf{c},\mathbf{r})+\mathbf{b}'(\mathbf{c},\mathbf{r})\bigr), \tag*{(4)}

and, by Theorem 14,

∣θ3(u)∣≤C3,∣θ3(v)∣≤C3,∣θ3(u+v)∣≤C3.(5)|\theta_3(\mathbf{u})|\le C_3,\qquad |\theta_3(\mathbf{v})|\le C_3,\qquad |\theta_3(\mathbf{u}+\mathbf{v})|\le C_3. \tag*{(5)}

Let S⊂Z2S\subset\mathbb{Z}^2 be the finite set

S={−b(c,r),−b′(c,r),−(b(c,r)+b′(c,r))∣c∈Σ4, 0≤rj<ℓ(cj)}.S=\{-\mathbf{b}(\mathbf{c},\mathbf{r}),-\mathbf{b}'(\mathbf{c},\mathbf{r}),-(\mathbf{b}(\mathbf{c},\mathbf{r})+\mathbf{b}'(\mathbf{c},\mathbf{r}))\mid\mathbf{c}\in\Sigma^4,\ 0\le r_j<\ell(c_j)\}.

Definition 26 (Initial state of level zero F0F_0). We denote F0={z∈Z4∣Γz∈S and ∣θ3(z)∣≤C3}F_0=\{\mathbf{z}\in\mathbb{Z}^4\mid\Gamma\mathbf{z}\in S\text{ and }|\theta_3(\mathbf{z})|\le C_3\}.

If x\mathbf{x} contains a cube, then u,v,u+v∈F0\mathbf{u},\mathbf{v},\mathbf{u}+\mathbf{v}\in F_0.

Why (T) is necessary: a cylinder cut by a hyperplane For F0F_0 to be finite, an equation Γz=t\Gamma\mathbf{z}=\mathbf{t} (t∈S\mathbf{t}\in S) and the bound ∣θ3(z)∣≤C3|\theta_3(\mathbf{z})|\le C_3 must leave only finitely many integer points. For our eight morphisms, s\mathbf{s} is not collinear with ℓ\boldsymbol{\ell}: Γ\Gamma has rank 2 and the set of real solutions of Γz=t\Gamma\mathbf{z}=\mathbf{t} is an affine plane z0+ker⁡Γ\mathbf{z}_0+\ker\Gamma. This equation alone is not sufficient. On the other hand, the bound on θ3\theta_3 places z\mathbf{z} in the closed cylinder ker⁡θ3+K\ker\theta_3+K, with axis ker⁡θ3=Vect⁡R(q1,q2)⊂R4\ker\theta_3=\operatorname{Vect}_{\mathbb{R}}(q_1,q_2)\subset\mathbb{R}^4 and compact section K=Vect⁡R(Re⁡q3,Im⁡q3)∩{∣θ3∣≤C3}K=\operatorname{Vect}_{\mathbb{R}}(\operatorname{Re}q_3,\operatorname{Im}q_3)\cap\{|\theta_3|\le C_3\}. The intersection of the affine plane and the cylinder is compact if and only if ker⁡Γ∩ker⁡θ3={0}\ker\Gamma\cap\ker\theta_3=\{0\}.

Definition 27 (Transversality hypothesis (T)). The morphism τ\tau satisfies (T) if the real 4×44\times4 matrix

Φ=(ΓRe⁡(θ3)Im⁡(θ3))=(ℓ(0)ℓ(1)ℓ(3)ℓ(4)s(0)s(1)s(3)s(4)−Re⁡(θ3)−−Im⁡(θ3)−)\Phi= \begin{pmatrix} \Gamma\\ \operatorname{Re}(\theta_3)\\ \operatorname{Im}(\theta_3) \end{pmatrix} = \begin{pmatrix} \ell(0)&\ell(1)&\ell(3)&\ell(4)\\ s(0)&s(1)&s(3)&s(4)\\ -&\operatorname{Re}(\theta_3)&-\\ -&\operatorname{Im}(\theta_3)&- \end{pmatrix}

is invertible, that is, det⁡(Φ)≠0\det(\Phi)\ne0 (equivalent to ker⁡Γ∩ker⁡θ3={0}\ker\Gamma\cap\ker\theta_3=\{0\}).

Example 28. (The matrix Φ\Phi for τ1\tau_1.)

Φ≈(231231350.5788−0.3219−0.0690−0.1662−0.57490.21830.6165−0.6810),det⁡(Φ)≈−10.53≠0.\Phi\approx\begin{pmatrix} 2 & 3 & 1 & 2 \\ 3 & 1 & 3 & 5 \\ 0.5788 & -0.3219 & -0.0690 & -0.1662 \\ -0.5749 & 0.2183 & 0.6165 & -0.6810 \end{pmatrix}, \qquad\det(\Phi) \approx-10.53 \ne0.

Lemma 29. (Finiteness of level zero.) Under (T), the set F0F_0 is finite.

Proof. Φ:R4→R4\Phi:\mathbb{R}^4 \to\mathbb{R}^4 is a linear isomorphism. Identifying C\mathbb{C} with R2\mathbb{R}^2: F0=Z4∩Φ−1(S×{ζ∈C:∣ζ∣≤C3})F_0 = \mathbb{Z}^4 \cap\Phi^{-1}\left(S \times\{\zeta\in\mathbb{C}: |\zeta| \le C_3\}\right), and the preimage of a compact set under an isomorphism is compact; its intersection with the lattice Z4\mathbb{Z}^4 is therefore finite.

The box U\mathcal{U}, the state space HH and the finite graph G′G'

Following the reduction strategy introduced in [1], we now bound all coordinates to restrict the exploration of G\mathcal{G} to a finite induced subgraph. In [1], the initial bounds on θ1\theta_1 and θ2\theta_2 were deduced from a fixed two-dimensional integer lattice. Here, since τ\tau and the boundary offsets modify lengths and sums, these initial bounds are instead controlled by the finite set F0F_0, whose finiteness is ensured by the transversality hypothesis (T).

Definition 30. (Constants, box U\mathcal{U}, space HH and graph G′G'.) For j∈{1,2}j \in\{1,2\}, we set

Cj=max⁡(max⁡z∈F0∣θj(z)∣,κj∣λj∣−1),C4=C3,C_j = \max\left(\max_{\mathbf{z}\in F_0} |\theta_j(\mathbf{z})|,\frac{\kappa_j}{|\lambda_j|-1}\right), \qquad C_4=C_3,

then

U={z∈Z4∣∣θj(z)∣≤Cj for 1≤j≤4},H={(c,u,v)∈Σ4×Z4×Z4∣u,v,u+v∈U}.\mathcal{U}=\{\mathbf{z}\in\mathbb{Z}^4\mid|\theta_j(\mathbf{z})|\le C_j\text{ for }1\le j\le4\}, \qquad H=\{(\mathbf{c},\mathbf{u},\mathbf{v})\in\Sigma^4\times\mathbb{Z}^4\times\mathbb{Z}^4\mid\mathbf{u},\mathbf{v},\mathbf{u}+\mathbf{v}\in\mathcal{U}\}.

G′G' is the subgraph of G\mathcal{G} induced on HH, A0=g(X)∩HA_0=g(X)\cap H, and RR is the set of vertices of G′G' reachable from A0A_0. Each θj\theta_j is bounded on U\mathcal{U} and z=Qθ(z)\mathbf{z}=Q\theta(\mathbf{z}) (Definition 12), hence U\mathcal{U} is finite; HH and G′G' are finite too, with at most 44∣U∣24^4|\mathcal{U}|^2 vertices.

Remark 31. (One may always round up.) The rest of the work only uses the fact that U\mathcal{U} contains the vectors that actually occur. One may therefore replace each CjC_j by any upper bound: U\mathcal{U}, HH, G′G', RR grow and Theorem 33 remains valid. This is what the numerical computation does (§ 6).

Proposition 32. (Confinement in HH.) Under the hypotheses of Proposition 25(a), all vertices g(par⁡i(p))g(\operatorname{par}^i(\mathbf{p})), 0≤i≤k0\le i\le k, belong to HH.

Proof. Set dj(i)=w[par⁡i(pj),par⁡i(pj+1))d_j^{(i)}=\mathbf{w}[\operatorname{par}^i(p_j),\operatorname{par}^i(p_{j+1})) for j=0,1,2j=0,1,2. The three vectors u(i)=ψ(d1(i))−ψ(d1(0))\mathbf{u}^{(i)}=\psi(d_1^{(i)})-\psi(d_1^{(0)}), v(i)=ψ(d2(i))−ψ(d2(0))\mathbf{v}^{(i)}=\psi(d_2^{(i)})-\psi(d_2^{(0)}) and u(i)+v(i)=ψ(d2(i))−ψ(d1(0))\mathbf{u}^{(i)}+\mathbf{v}^{(i)}=\psi(d_2^{(i)})-\psi(d_1^{(0)}) are deviations Δi\Delta_i for a pair of factors.

Level 0. By (4) and (5), these three vectors are in F0F_0; hence ∣θj(Δ0)∣≤max⁡F0∣θj∣|\theta_j(\Delta_0)|\le\max_{F_0}|\theta_j| for j=1,2j=1,2.

Levels i≥0i\ge0. For j=1,2j=1,2, Lemma 16 (with B=max⁡F0∣θj∣B=\max_{F_0}|\theta_j|) gives ∣θj(Δi)∣≤Cj|\theta_j(\Delta_i)|\le C_j; for j=3,4j=3,4, Theorem 14 gives ∣θj(Δi)∣≤C3|\theta_j(\Delta_i)|\le C_3. The three vectors are therefore in U\mathcal{U}.

Theorem 33. (Reduction Theorem.) Let τ:Σ∗→{0,1,2,3}∗\tau:\Sigma^*\to\{0,1,2,3\}^* be non-erasing, satisfying (H0) and (T). Then

x=τ(w) is without additive cubes⟺R∩Zτ=∅.\mathbf{x}=\tau(\mathbf{w})\text{ is without additive cubes}\Longleftrightarrow R\cap Z_\tau=\varnothing.

Proof. (⇐) Suppose that x\mathbf{x} contains an additive cube. By Proposition 25(a), there exists a path in GG from a vertex of g(X)g(X) to a vertex of ZτZ_{\tau}. By Proposition 32, all its vertices are in HH: it is a path of G′G' issuing from A0A_0, and its endpoint is in R∩ZτR \cap Z_{\tau}.

(⇒) If R∩Zτ≠∅R \cap Z_{\tau} \ne\emptyset, there exists a path of G′⊂GG' \subset G from A0⊂g(X)A_0 \subset g(X) to ZτZ_{\tau}; Proposition 25(b) provides an additive cube in x\mathbf{x}. □

Theorem 33 shows that the exhaustive search is indeed a proof: if an additive cube exists in x\mathbf{x}, even arbitrarily far away, its genealogy will leave a trace in the finite graph G′G', from one of the 9 seeds to ZτZ_{\tau}. For τ=id⁡\tau= \operatorname{id}, we recover exactly the Theorem of [1].

Computation and results

The C++ program proof.cpp follows the proof:

  1. it reads τ\tau and tests (H0);

  1. it computes MM, its eigenvalues, its eigenvectors of norm 1, the forms θj\theta_j, and tests (T) (det⁡Φ≠0\det\Phi\ne0);

  1. it computes D9D_9 (in integers, via QQ), C∗C_*, C3C_3 and the κj\kappa_j;

  1. it enumerates SS and F0F_0, then computes C1C_1, C2C_2 and enumerates U\mathcal{U};

  1. it constructs g(X)g(X) (Lemma 23);

  1. it performs a breadth-first traversal of G′G' from A0A_0, the edges being generated “on the fly” by Definition 20;

  1. for each vertex reached, it tests membership in ZτZ_{\tau} by running through the offsets r\mathbf{r} (at most 81 cases).

Everything is exact (integers) except steps 2 to 4; the constants computed there are rounded upwards (relative margin 10−910^{-9}), which is permitted by Remark 31.

For τ1:0↦21, 1↦100, 3↦3, 4↦23\tau_1: 0 \mapsto21,\ 1 \mapsto100,\ 3 \mapsto3,\ 4 \mapsto23:

det⁡(Φ)≈−10.53,∣S∣=43,∣F0∣=67,C1≈1.9032,\det(\Phi) \approx-10.53,\quad|S| = 43,\quad|F_0| = 67,\quad C_1 \approx1.9032,
C2≈2.9818,C3≈2.1758,∣U∣=497.C_2 \approx2.9818,\quad C_3 \approx2.1758,\quad|\mathcal{U}| = 497.

The 9 starting states are in HH. The traversal reaches ∣R∣=78340|R| = 78340 vertices, at maximal depth 23, and 4078 patterns (b,b′)(\mathbf{b},\mathbf{b}') are tested; no vertex reached is in ZτZ_{\tau}. Theorem 33 applies: τ1(w)\tau_1(\mathbf{w}) contains no additive cube.

In fact, for all eight morphisms, the computation of F0F_0 gives max⁡z∈F0∣θj(z)∣≤κj/(∣λj∣−1)\max_{z \in F_0} |\theta_j(z)| \le\kappa_j/(|\lambda_j| - 1) for j∈{1,2}j \in\{1,2\}. Consequently, C1C_1 and C2C_2 are entirely determined by the second term of the maximum in Definition 30, which depends only on φ\varphi. Hence the box U\mathcal{U}, the state space HH, the graph G′G', and the set RR are identical for all eight morphisms; only F0F_0 and ZτZ_{\tau} change. The eight morphisms were obtained by an exhaustive search of candidates (images of length ≤3\le3, prefix of 10610^6 letters without additive cubes):

τ1:0↦21,1↦100,3↦3,4↦23,τ2:0↦12,1↦233,3↦0,4↦10,τ3:0↦122,1↦331,3↦0,4↦10,τ4:0↦211,1↦002,3↦3,4↦23,τ5:0↦021,1↦001,3↦323,4↦321,τ6:0↦312,1↦332,3↦010,4↦012,τ7:0↦132,1↦332,3↦101,4↦102,τ8:0↦201,1↦001,3↦232,4↦231.\begin{aligned} \tau_1 &: 0 \mapsto21,\quad1 \mapsto100,\quad3 \mapsto3,\quad4 \mapsto23, \qquad \tau_2 &: 0 \mapsto12,\quad1 \mapsto233,\quad3 \mapsto0,\quad4 \mapsto10,\\ \tau_3 &: 0 \mapsto122,\quad1 \mapsto331,\quad3 \mapsto0,\quad4 \mapsto10, \qquad \tau_4 &: 0 \mapsto211,\quad1 \mapsto002,\quad3 \mapsto3,\quad4 \mapsto23,\\ \tau_5 &: 0 \mapsto021,\quad1 \mapsto001,\quad3 \mapsto323,\quad4 \mapsto321, \qquad \tau_6 &: 0 \mapsto312,\quad1 \mapsto332,\quad3 \mapsto010,\quad4 \mapsto012,\\ \tau_7 &: 0 \mapsto132,\quad1 \mapsto332,\quad3 \mapsto101,\quad4 \mapsto102, \qquad \tau_8 &: 0 \mapsto201,\quad1 \mapsto001,\quad3 \mapsto232,\quad4 \mapsto231. \end{aligned}

Disclaimer

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}\{0,1,2,3\}, it suggested a first candidate morphism, τ1\tau_1, inspired by the morphism in [1], without a proof of correctness. The authors then proved that the infinite word τ1(w)\tau_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. [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. [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. [3]M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1983.
  4. [4]G. Pirillo and S. Varricchio. On uniformly repetitive semigroups. Semigroup Forum, 49:125–129, 1994.DOI
  5. [5]M. Rao. On some generalizations of abelian power avoidability. Theoretical Computer Science, 601:39–46, 2015.DOI

Paper details

vlnc:W_dwxzpb27
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents