Fabian Arevalo

Additive squares (PVHH) · combinatorics on words

The singular relation

A quotient lemma reducing additive-square-freeness to an alphabet's integer relations · Freedman's bound re-derived in three lines and shown attained · the first exact table for four-letter alphabets · of eleven relations tried, one keeps words short and ten do not.
August 1, 2026 · one research session · code, data and certificates in the Matematica repository (conjectures/additive-squares).

Start here · no maths required

Take a list of numbers, say 2, 5, 3, 4. Split it into two neighbouring, equal-length pieces: 2 5 and 3 4. Add each piece up: 7 and 7. Same total. That coincidence has a name: an additive square, sitting right there in a four-number list.

Now the game. Pick a fixed set of numbers you are allowed to use, say {0, 1, 5, 6}, and try to write as long a list as you can, using only those numbers, so that no two neighbouring equal-length pieces anywhere in the list ever add up to the same total. You can always manage a fairly short list. Can you manage an infinite one, for some fixed set of numbers? Nobody knows. It has been open since the 1990s: the Pirillo–Varricchio / Halbeisen–Hungerbühler problem.

This session did not answer that. It found a shortcut that handles infinitely many number-sets at once, used it to reconstruct the one theorem already known here in three lines, showed that theorem's limit is actually reached, and built the first table of exact answers for small four-number sets. Along the way it found something it cannot explain: of eleven natural variations tried, only one keeps the lists short. The figure below is that finding.

hover a point
A wall at 60, and a cloud rising above it. Every four-number alphabet {0, a, b, c} with c ≤ 18, one point per alphabet: how long a list you can build (y) against how spread out the numbers are (x). Filled squares: exact answers for alphabets where one number is the sum of two others (381 alphabets swept, 50 of this kind, all solved exactly). Filled diamond: the one other alphabet solved exactly, {0,1,2,4} at 62. Open marks: every other alphabet, where the search ran out of budget before finishing, so the true answer is only known to be at least this large (arrows where it already exceeds the chart). If one number is the sum of two others, the list can never pass 60, and plenty of alphabets sit exactly on that line. Every other alphabet has already climbed past it.

What this note adds

The problem is open for every finite alphabet; the only general theorem on record covers one narrow family. From one session:

  1. A shortcut for infinitely many alphabets at once. Whether a word avoids additive squares turns out to depend on its alphabet only through which integer combinations of the numbers happen to vanish. Forgetting some of those coincidences can only make the problem easier, so one finite computation, done once, bounds every alphabet sharing a given coincidence ― an infinite family in a single search (§3).
  2. A calibration. Every three-number alphabet allows a list of exactly 7 numbers and no more, proved by a 354-step search plus a seven-number witness that works for every alphabet at once (§4).
  3. The one known theorem, rebuilt and pushed further. If one of your four numbers equals the sum of two others, your list can never pass 60. That bound was already known (Freedman, 1970s or 2010s depending on which source you believe); this session reconstructs it from a single three-line argument instead of a bespoke one, and additionally shows the bound is actually reached: {0,1,5,6} allows a list of exactly 60, the longest possible (§5).
  4. The first table. Exact longest-list lengths for 51 small four-number alphabets, apparently never published before (§6).
  5. An unexplained singularity. Eleven natural "one-number-is-a-combination-of-others" rules were tried. Ten of them let the list run at least fifty times longer than 60 with no end in sight. Exactly one keeps it short. Nobody knows why (§8).

Everything below is the technical version. The fastest route through it: the figure above, then §5 and §8.

AbstractSummary of results

Let A be a finite subset of a field of characteristic 0. A word w over A contains an additive square if it has a factor uv with |u| = |v| and Σu = Σv; it is additive-square-free otherwise. Write L(A) for the supremum of the lengths of additive-square-free words over A. Whether an infinite additive-square-free word exists over some finite A ⊂ ℤ is the Pirillo–Varricchio / Halbeisen–Hungerbühler problem, open since the 1990s. This is a session note, not a solution: PVHH is not resolved and nothing here claims otherwise. We record an elementary reduction, the Quotient Lemma: the additive-square structure of A depends on A only through its relation lattice Λ(A) ⊂ ℤ|A|−1, the integer vectors of count-differences that make two blocks' sums agree; quotienting by any sublattice of Λ(A) can only increase L, so a single finite computation over a universal alphabet of integer vectors bounds L for every alphabet realising a given relation (PROVED). Consequences: L(A) = 7 for every three-element alphabet in characteristic 0 (PROVED, a uniform seven-letter witness plus a 354-node search); L(A) ≤ 60 for every four-element alphabet with a+d = b+c (PROVED reduction + CERTIFIED constant), which is Freedman's published bound, re-derived here in three lines from the single relation (1,1,−1) and confirmed by three independent unimodular completions agreeing on both value and node count; the bound is attained, at A = {0,1,5,6} (CERTIFIED, independently verified by a from-scratch checker); and exact L(A) for 51 four-element integer alphabets with largest letter ≤ 18, apparently the first such table (CERTIFIED). Across the 50 alphabets in that table satisfying a+d = b+c, L takes only the values 50, 55, 58, 60, and the underlying search-tree size saturates at exactly 7,707,828 nodes from {0,1,8,9} onward: past a certain spread, a concrete integer alphabet's search tree is identical to the abstract universal one. Testing all 11 primitive relations of sup-norm ≤ 2, exactly one — (1,1,−1), Freedman's — gives a finite bound; the other ten reach ≥ 418 to ≥ 3000 letters without closing, two hitting a depth cap rather than a node budget, the signature of a plausibly infinite family. Which relations force finiteness, and why (1,1,−1) is special, are left open. No primary source was read this session (sandbox network blocked); every citation below is marked (secondary) and none should be repeated without checking the paper.

Section 1Definitions

Let K have characteristic 0 and let A ⊂ K be finite with |A| = m. For a word w = w1⋯wn over A, an additive square is a pair of indices (i, k) with k ≥ 1, i + 2k − 1 ≤ n, and

Σj=ii+k−1 wj = Σj=i+ki+2k−1 wj

w is additive-square-free (afsf) if it admits none. Set L(A) = sup{|w| : w afsf over A} ∈ ℕ ∪ {∞}. An abelian square (two adjacent blocks that are permutations of one another) is always an additive square, so afsf is a strictly stronger condition than abelian-square-free.

The PVHH problem · open

Is L(A) = ∞ for some finite A ⊂ ℤ? Open since the 1990s (secondary; §7).

Section 2Affine invariance and the relation lattice (PROVED)

Lemma 1 · affine invariance

For α ∈ K×, β ∈ K: L(αA + β) = L(A).

Proof. The bijection x ↦ αx + β carries a word w over A to a word w′ over αA + β of the same length. A block of length k with sum σ becomes a block with sum ασ + kβ. Two blocks of equal length k have equal sums in w iff their images do in w′, since α ≠ 0. So w is afsf iff w′ is. ∎

By Lemma 1 we may always normalise so that 0 ∈ A. Write A = {x0, x1, …, xm−1} with x0 = 0. Given a factor uv of a word over A with |u| = |v| = k, let δ(u,v) ∈ ℤm−1 be the vector of count-differences of the letters x1,…,xm−1 between u and v. (The count-difference of x0 is determined by the others because |u| = |v|, and contributes nothing to sums since x0 = 0.) Then Σu − Σv = Σi=1m−1 δi xi.

Definition. The relation lattice of A is Λ(A) = {δ ∈ ℤm−1 : Σi=1m−1 δi xi = 0}.

Observation. uv is an additive square ⟺ δ(u,v) ∈ Λ(A). So additive-square-freeness of a word depends on the alphabet only through Λ(A). For A ⊂ ℤ with m = 4, Λ(A) has rank 2.

Section 3The Quotient Lemma (PROVED)

Let M ⊆ Λ(A) be a subgroup, Q = ℤm−1/M, and π : ℤm−1 → Q the quotient map. Put AM = {0, π(e1), …, π(em−1)} ⊆ Q, an alphabet of m elements provided these are pairwise distinct ― which holds precisely when M contains no ei and no ei − ej. Additive squares over AM are defined exactly as in §1, with sums taken in the abelian group Q.

Lemma 2 · the Quotient Lemma

If the m elements above are pairwise distinct, then L(A) ≤ L(AM).

Proof. Let w be afsf over A, |w| = n. Define ŵ over AM by replacing each letter xi by π(ei) (and x0 = 0 by 0 ∈ Q); this is well defined since the letters are distinct on both sides, and |ŵ| = n. Suppose ŵ had an additive square at (i,k), and let u,v be the corresponding factor of w. Summing in Q, ΣQû − ΣQv̂ = π(Σi≥1 δiei) = π(δ(u,v)), so the supposed square says π(δ(u,v)) = 0, i.e. δ(u,v) ∈ M ⊆ Λ(A). By the Observation of §2, uv is then an additive square in w, contradicting that w is afsf. Hence ŵ is afsf over AM and L(AM) ≥ n. Taking the supremum over w gives the claim. ∎

The content: forgetting relations can only make life easier, since AM has fewer additive squares than A, hence longer afsf words. The lemma is useful in the direction one wants: a computation over the finite, canonical alphabet AM bounds L for the whole infinite family of alphabets realising the relations M.

Corollary 3 · the free bound

Taking M = 0: L(A) ≤ λ(m), where λ(m) is the length of the longest abelian-square-free word over m letters. Known values (secondary, §7; independently recomputed here): λ(2) = 3, λ(3) = 7, and λ(4) = ∞ by Keränen's 85-uniform morphism.

That λ(4) = ∞ is exactly why four letters is the hard case: the free bound is vacuous, and one must use a nonzero M ― a genuine integer relation among the letters.

Section 4Three letters (PROVED)

Theorem 4

For every three-element A in a field of characteristic 0: L(A) = 7.

Upper bound. Corollary 3 with m = 3 gives L(A) ≤ λ(3) = 7. This is recomputed here rather than cited: exhaustive search over the free alphabet {(0,0),(1,0),(0,1)} ⊂ ℤ² closes the whole tree in 354 nodes and returns 7. Equivalently: every ternary word of length 8 contains an abelian square, a 38 = 6561-case check small enough to audit by hand.

Lower bound. By Lemma 1 normalise A = {0, 1, t} with t ∉ {0, 1}. The single word

w = 0, 1, 0, t, 0, 1, 0

is afsf for every such t. Since |w| = 7, only k ≤ 3 occurs:

So L(A) ≥ 7. ∎ The uniform witness needs no case analysis over t, because all twelve inequalities degenerate only at t ∈ {0,1}, which |A| = 3 already forbids.

This is very likely folklore. The upper bound is the classical unavoidability of abelian squares on three letters; the lower bound is a seven-letter word. No published statement of exactly "L(A) = 7 for every three-element alphabet" was located (§7, item 5), but absence of a citation under a blocked network is not evidence of novelty, and none is claimed. Included because it calibrates the method, not as a contribution.

Section 5Four letters: the relation (1,1,−1), and Freedman's constant

Call A = {a,b,c,d} degenerate if a + d = b + c (equivalently, after normalising, A ~ {0,x,y,x+y}).

Theorem 5

Let A be a four-element degenerate alphabet in a field of characteristic 0. Then L(A) ≤ 60. The bound is attained: L({0,1,5,6}) = 60.

Proof of the bound (PROVED). Normalise A = {0, 1, t, 1+t} (Lemma 1), letters ordered x0=0, x1=1, x2=t, x3=1+t. Then (1,1,−1) ∈ Λ(A) for every t, since 1·1 + 1·t − 1·(1+t) = 0. Take M = ⟨(1,1,−1)⟩. Then ℤ³/M ≅ ℤ², and the four images 0, π(e1), π(e2), π(e3) are distinct because M contains no ei and no ei − ej. Lemma 2 gives L(A) ≤ L(AM), and L(AM) = 60 by exhaustive search. ∎

The constant (CERTIFIED, not a hand proof). L(AM) = 60 closes an exhaustive tree of 7,707,828 nodes (0.03 s), exact integer arithmetic, no floating point anywhere. Computed twice more through independent bases:

routealphabet AM ⊂ ℤ²nodesL
hand-chosen basis(0,0), (1,0), (0,1), (1,1)7,707,82860
unimodular completion of (1,1,−1)(0,0), (−1,0), (1,1), (0,1)7,707,82860
sign-flipped class rep. (−1,−1,1)(0,0), (−1,0), (1,1), (0,1)7,707,82860

Three routes through three different unimodular completions agree on both the value and the node count ― a sharper check than agreeing on the value alone: the trees are isomorphic, exactly as Lemma 2 predicts.

Attainment (CERTIFIED). L({0,1,5,6}) = 60 by exhaustive search directly on this alphabet: 6,595,124 nodes, tree closed ― smaller than the universal alphabet's 7,707,828, because {0,1,5,6} has not yet reached the saturation regime of §6. And 0 + 6 = 1 + 5, so the alphabet is degenerate. The extremal word (below) is independently re-checked here: no adjacent equal-length blocks share a sum, and none of the four letters extends it.

hover a letter
The longest word that exists over {0,1,5,6}. All 60 letters, each cell one of 0 (outline), 1 (solid), 5 (hatched), 6 (grey fill). No fifth letter, and no other word over this alphabet, is longer ― every one of the four possible one-letter extensions creates an additive square (checked independently for this page, not only in the repository). Source: data/extremal_words.txt.

Relationship to the literature ― read this before citing. The bound L ≤ 60 for a+d=b+c is Freedman's theorem (secondary; quoted in Cassaigne–Currie–Schaeffer–Shallit, §7). Theorem 5 is therefore a clean-room reproduction, not a new bound. What this session adds is (i) a three-line derivation from a single relation vector via the Quotient Lemma, in place of a bespoke argument, and (ii) the attainment, which could not be confirmed as published (search returned an unsupported assertion that the bound is tight and nothing behind it, §7 item 3). Attainment is claimed only as "not found in the literature reachable this session", which under a blocked network is a weak claim. Freedman's paper is Sequences on sets of four numbers (possibly with Tom C. Brown); its venue is reported inconsistently by search as INTEGERS 16 (2016) and as Math. Magazine 49 (1976) ― unresolved, and neither is printed here as fact.

Section 6The certified table (CERTIFIED)

Alphabets normalised to {0,a,b,c} with 0 < a < b < c, gcd(a,b,c) = 1, up to the reflection x ↦ c − x (Lemma 1, α = −1). Exhaustive search, exact integer arithmetic; a value is exact only when the tree closed inside the node budget. The sweep covered all 381 normalised alphabets with c ≤ 18 and returned 51 exact values.

AL(A)degenerate?nodes
{0,1,2,3}50yes751,156
{0,1,3,4}, {0,2,3,5}, {0,1,4,5}55yes2.6–4.5 M
{0,3,4,7}58yes7,012,884
{0,1,5,6} and 44 further degenerate alphabets60yes6.6–7.7 M
{0,1,2,4}62no76,391,112
{0,1,2,5}86no1,198,387,276 (deeper rerun, not the c≤18 sweep's own budget)
{0,1,3,5}88no937,940,596 (ditto)

{0,1,2,5} and {0,1,3,5} did not close inside the c≤18 sweep's own 4×10⁸-node budget (the sweep alone gives only "≥ 86" and "≥ 88"); a separate, deeper, targeted rerun on just these two alphabets closed both trees exactly, and it is that run's node counts shown above. Everything else in this table closed inside the main sweep. Full machine-readable table: data/sweep4_c18.csv.

The degenerate family takes only four values

Over all 50 degenerate alphabets with c ≤ 18, L is one of 50 (×1), 55 (×3), 58 (×1), 60 (×45). This is the cell decomposition of §3 seen from the integer side: writing A = {0,1,t,1+t}, the parameter t falls below the generic value 60 only at a handful of small-height rationals where an extra low-coefficient relation happens to vanish. Every other alphabet sits in the generic cell and returns 60.

The search trees become the same tree

Among degenerate alphabets the node count saturates at exactly 7,707,828 ― the node count of the generic ℤ² alphabet AM of §5 ― for every alphabet from {0,1,8,9} onward in the sweep. Once the letters are spread far enough apart, the search tree of the concrete integer alphabet is literally identical to the tree of the universal quotient alphabet: no extra relation with small coefficients survives to create additional squares.

hover a point
Every one of these trees closed exactly; the flat line is not a fit. Node count at closure, one point per degenerate alphabet with c ≤ 18 (50 points, all exact=1 in data/sweep4_c18.csv), against the largest letter c. Rises from 751,156 at {0,1,2,3} and flattens onto 7,707,828 by c = 9. Past that spread the computer is doing exactly the same search for the concrete alphabet as for the abstract one ― which is why the bound 60 is reached, not merely approached.

Rows in data/sweep4_c18.csv marked inexact record only how deep a fixed node budget reached before stopping. They are certified lower bounds, real and independently verifiable words, but the depth reached is an artifact of the budget, not a measurement of L(A), and must not be read as growth data ― that is why the plain-language figure above draws them as open marks, not solid points.

Section 7Prior work

Everything in this section is (secondary). Page fetches to arXiv, OEIS, erdosproblems.com and MathOverflow were blocked (HTTP 403 at the sandbox's egress proxy) the day this session ran; these entries come from web search synthesis only, not from reading the papers. Each should be re-checked from an unblocked network before being repeated anywhere else.

  1. PVHH problem. Pirillo–Varricchio (On uniformly repetitive semigroups, Semigroup Forum, 1994) and independently Halbeisen–Hungerbühler. Asks whether an infinite additive-square-free word exists over a finite subset of ℤ. Still open as of 2026 (secondary). Sources disagree on 1992 vs 1994 for the date; not resolved here.
  2. Additive cubes. Cassaigne–Currie–Schaeffer–Shallit, Avoiding three consecutive blocks of the same size and same sum, arXiv:1106.5204, J. ACM 61(2) (2014) art. 10: an infinite additive-cube-free word over {0,1,3,4}. Lietard–Rosenfeld (DLT 2020) classify: additive cubes are avoidable over every four-element subset of ℤ except possibly {0,1,2,3}. This is the exact cube analogue of the square classification this note starts on, and is where this work would be cited.
  3. Freedman's bound. If a+d=b+c then every word of length 61 over {a,b,c,d} contains an additive square, i.e. L ≤ 60; stated for any field of characteristic 0. Attributed to Freedman, Sequences on sets of four numbers (possibly Freedman & Brown; venue reported inconsistently as INTEGERS vol. 16 (2016) and as Math. Magazine 49 (1976) ― unresolved). Quoted in [2]. Whether the bound is attained could not be determined from search.
  4. ℤ². Rao–Rosenfeld, arXiv:1511.05875, SIAM J. Discrete Math. (2018): additive squares are avoidable over a finite subset of ℤ². Consistent with, and a warning about, Lemma 2: for vector alphabets L can be infinite, so a relation M that is too small yields no bound at all.
  5. Three letters. No published statement of "L(A) = 7 for every three-element alphabet" was located. The ingredients are classical: abelian squares are unavoidable on three letters, and every ternary word of length 8 contains one (secondary).
  6. Abelian squares. Keränen (ICALP 1992), abelian squares avoidable on four letters via an 85-uniform morphism; Entringer–Jackson–Schatz (JCTA 16, 1974) for the binary theory; Dekking (1979).
  7. A heuristic pointing the other way. Ochem's page (lirmm.fr/~ochem/additive_square.htm) reportedly gives a growth-rate heuristic suggesting additive squares are unavoidable over {1,…,k}, i.e. that PVHH has a negative answer (secondary, single search snippet). This note's finite L values are consistent with it. Unverified.

Section 8Which relations keep words finite?

For a primitive v ∈ ℤ³, let Av be the universal alphabet of §3 with M = ⟨v⟩. Freedman's theorem is the single instance v = (1,1,−1), where L(Av) = 60. For which v is L(Av) finite? Each finite answer is a Freedman-type theorem for an infinite family of integer alphabets, from one computation. All 11 primitive classes of sup-norm ≤ 2 were run to a 6×10⁸-node budget with a depth cap of 3000. Exactly one closed.

relation vmeaningL(Av)
(1,1,−1)one letter is the sum of two others= 60, tree closed, 7,707,828 nodes
(2,0,−1)≥ 418
(2,−1,−1)≥ 439
(1,1,0)alphabet contains a 3-term AP {0,x,2x}≥ 440
(1,1,1)a+b+c = 0≥ 996
(2,1,−2)≥ 1795
(2,2,−1)≥ 1816
(2,1,−1)≥ 1836
(2,1,1)≥ 1479
(2,1,0)≥ 3000 (hit the depth cap)
(2,2,1)≥ 3000 (hit the depth cap)

Every word in that table was re-verified by an independent O(n²) checker written from the definition, including both 3000-letter words. Freedman's relation is singular, and by two orders of magnitude: 60 against ≥ 3000. Two classes hit the depth cap rather than the node budget, meaning the search descended 3000 letters without being forced to backtrack out ― the signature of an infinite class, and consistent with Rao–Rosenfeld [4], who prove additive squares are avoidable over a finite subset of ℤ². Why (1,1,−1) alone forces finiteness is the sharpest open question this session leaves; a proof of it, in place of a 7.7-million-node tree closure, would likely generalise.

The ten open classes are not alike. A second, independent randomised-restart probe (seed 11, depth cap 200,000, 4×10⁹ nodes) separates them. v = (1,1,0), the 3-term-AP class, plateaus: 440 from the exhaustive budget-limited run above, 437 from the independent randomised run. Two different searches, different seeds, a 66× larger depth cap, agreeing to within three letters ― what a finite L looks like from below, and the best candidate for a second Freedman-type theorem. By contrast v = (2,1,0) and v = (2,2,1) ran straight to the depth cap both times, what an infinite L looks like from below. The distinction matters: if even one admissible relation class truly has L(Av) = ∞, then alphabets whose only small relations are of that type escape this method entirely, and the Quotient Lemma cannot reach PVHH for four letters by itself.

Two questions follow directly. First: since every four-element A ⊂ ℤ has Λ(A) of rank 2, A satisfies some primitive relation v; if L(Av) < ∞ for every admissible v, PVHH would follow for four-letter integer alphabets. Is there a v with L(Av) = ∞? By [4] above the analogous phenomenon does occur for larger ℤ² alphabets, so the expectation is yes; locating one explicitly is the sharpest next computational step. Second: is {0,1,2,3} ― the one alphabet Lietard–Rosenfeld leave open for cubes ― also distinguished for squares? It has the smallest L of any four-letter integer alphabet found here (50).

Section 9Reproducibility

Hardware: 4 cores, 15 GB RAM, Linux 6.18.5, gcc 13.3 -O2, Python 3.11.15. No floating point in any critical path; all searches are exact integer depth-first search. Randomised runs record their seed; every reported search records its node count.

artifactcontents
afsf.cexhaustive / randomised DFS for the longest afsf word over an integer alphabet
afsfv.cthe same over an alphabet of integer vectors in ℤᵈ ― this is what makes the uniform theorems possible
verify_word.pyindependent O(n²) checker, from the definition, of any word against any alphabet
sweep4.pythe c≤18 sweep over normalised four-letter integer alphabets
relation_quotient.pythe 11-relation-class sweep of §8, plus unimodular completions

Reproduce (from conjectures/additive-squares/):

gcc -O2 -o afsf afsf.c && gcc -O2 -o afsfv afsfv.c
python3 verify_word.py --selftest
./afsfv exhaust 2 "0,0|1,0|0,1" 500 1000000000 # λ(3)=7, 354 nodes
./afsfv exhaust 2 "0,0|1,0|0,1|1,1" 500 20000000000 # L(A_M)=60, 7,707,828 nodes
./afsf exhaust "0,1,5,6" 500 20000000000 # attained: L=60
./afsf exhaust "0,1,2,4" 500 20000000000 # L=62
python3 sweep4.py 18 400000000 4000 3 data/sweep4_c18.csv
python3 relation_quotient.py 2 600000000 3000 1 data/relations_n2.csv
python3 verify_word.py --file data/extremal_words.txt