Fabian Arevalo

Erdős problem 193 · combinatorics on words

Seven letters, by way of the dragon curve

An infinite unit-step walk in ℕ⁷ with no three collinear vertices, proved from the Heighway dragon curve. It is not the record: an unpublished draft reaches six, and this session reviewed that draft line by line and found no gap.
9 September 2026 · research session · code and data in the Matematica repository.

Start here — no maths required

Walk on a grid, one step at a time, always in a positive direction along one of a fixed number of axes. Every so often look back at the trail of points you have left. Can you walk forever without three of your points ever falling on a single straight line?

In two or three dimensions you cannot go far. With enough different directions available you can, and the question is how many you need. Erdős asked it, and it was settled only this month: Cambie and Kalviainen gave a walk with sixteen directions in September 2026, Shallit reduced the bookkeeping to a question about words, and the number came down quickly from there.

Here the walk is the dragon curve, the shape you get by folding a strip of paper in half over and over and then opening every fold to a right angle. Each of its steps is labelled by two things: which way the step points, and whether the next turn is left or right. Those labels take eight values, two of which can be merged, and the sequence of labels turns out to have the property the problem needs. Seven directions suffice.

Seven is not the record. A two-page unpublished note by Kalviainen gets six, and part of this session was spent reading it line by line looking for a mistake; none was found. What the dragon curve adds is a second, independent mechanism, and a proof short enough to check over a coffee.

Steps
The walk, and the word it spells. The dragon curve, generated live in your browser from the recursion in section 2, never from stored coordinates. Each step carries a letter: its direction, one of four, together with the turn that follows it, one of two. That is eight letters, and identifying the two that point in opposite directions before a left turn leaves seven. The strip below the curve is the start of that seven-letter word.

What this note adds

  1. An infinite walk in seven dimensions with no three collinear vertices, proved, by a different construction from the ones in the literature: the dragon curve rather than the Gaussian digit walk.
  2. A short proof. Two telescoping indicator sums pin the direction at the three break points, a third functional supplies the displacement, and one 2-adic valuation identity finishes it. That structure is what allows two letters to be merged, which the earlier arguments could not do.
  3. A review of the six-dimensional draft that currently holds the record. Read line by line, every numerical claim reproduced, no gap found. The bound six is not ours and this note does not beat it.
  4. Exhaustive finite facts around the construction: no relabelling of the dragon word onto six or fewer letters survives 3000 letters, and no four-letter cyclic morphism of length at most 16 works either.

Everything below is the technical version. Section 3 is the whole proof; section 5 is where this result sits relative to everyone else's.

AbstractSummary of results

Shallit (arXiv:2609.05780, 5 September 2026) proved that an infinite walk in ℕ16 using only the standard unit steps can avoid three collinear vertices, and asked for the least dimension kmin, known to satisfy 4 ≤ kmin ≤ 16. Equivalently, kmin is the least alphabet size admitting an infinite word with no two adjacent nonempty blocks of equal letter frequencies, a weak abelian square; call such a word 3-free.

This note proves kmin ≤ 7. Let un be the direction of the n-th step of the Heighway dragon curve and δn its n-th turn. The word bn = (un, δn) over eight letters is 3-free (Theorem 1), and stays 3-free after identifying the two letters whose directions are opposite and whose turn is the same (Theorem 2), which leaves seven. Both are proved. The mechanism is a 2-adic valuation identity that the dragon curve satisfies whenever the two endpoint directions are not antipodal, plus two telescoping indicators that force equal endpoint directions on any bad pair.

The note also records an independent review of Kalviainen's unpublished six-dimensional construction, in which no gap was found, and a set of exhaustive finite facts: no coding of the dragon word onto six or fewer letters is 3-free beyond length 3000; within the periodic sign and order family of Gaussian digit walks the coding floor is six; no cyclic uniform morphism of length at most 16 over four letters has a 3-free fixed point beyond length 1500; and the number of 3-free four-letter words keeps growing, so kmin = 4 is not excluded by search.

Section 1Walks and words are the same question

For a finite word x, let ψ(x) be its Parikh vector, the tuple of letter counts, and |x| its length. Two adjacent nonempty blocks x, y form a bad pair when ψ(x)/|x| = ψ(y)/|y|, and a word is 3-free when it has no bad pair. Writing Pn = ψ(b0 ⋯ bn−1), the points P0, P1, … are the vertices of a unit-step walk, and three of them are collinear exactly when the two blocks between them form a bad pair, since the displacements are ψ(x) and ψ(y) with coordinate sums |x| and |y|. So kmin is the least alphabet size carrying an infinite 3-free word.

What was known before this session, from the primary sources, read on 9 September 2026: Brown (1971) gives L(3) = 7, the longest 3-free ternary word, hence kmin ≥ 4; Korsky (arXiv:2608.07906) bounds L(d) from below by a doubly exponential function; Cambie and Kalviainen (arXiv:2609.01766) settle Erdős Problem 193 with sixteen step vectors, using the Gaussian walk zn = Σj<n is₂(j) and the identity ν₂(|zn − zm|²) = ν₂(n − m) at equal endpoint states; and Shallit gets kmin ≤ 16 with the letters (tn, tn+1), plus four unproved candidate morphisms for k = 5, 6, 7, 8.

Section 2The dragon walk and its valuation identity

Define Gaussian units un and the walk Zn by u0 = 1, Z0 = 0 and, for every n,

u2n = un, u2n+1 = i·un  (n even);   u2n = i·un, u2n+1 = un  (n odd);   Zn = Σj<n uj
so that Z2n+ε = (1+i)Zn + ε·u2n for ε ∈ {0, 1}
Lemma 1 · turns · proved

un+1 = iδnun with δn ∈ {+1, −1}, and δ2m = (−1)m, δ2m+1 = δm.

So every turn is a quarter turn, (δn) is the regular paperfolding sequence, and Zn is the Heighway dragon curve: un is its direction and δn its turn. Nothing below uses any other property of it.

For w = x + iy ∈ ℤ[i] write ν(w) = ν₂(x² + y²).

Lemma 2 · proved

If 0 ≤ m < n and um = un then Zn ≠ Zm and ν(Zn − Zm) = ν₂(n − m). More generally (Lemma 2′) the identity holds whenever un ≠ −um: only antipodal endpoint directions escape it.

The proof is a strong induction on n − m. An odd difference makes Zn − Zm a sum of an odd number of units, which has odd norm. An even difference halves both indices through the displayed identity; when the halved indices differ by an even number the correction term cancels and the induction applies, and when they differ by an odd number the correction is (1−i) times a unit, which has even parity, so adding it to an odd-parity sum leaves odd parity and the valuation is exactly 1.

Pairs up to n =
Where the identity holds, and where it fails. For every pair m < n in range, the bar chart counts the defect ν(Zn − Zm) − ν₂(n − m), split by the angle between the two endpoint directions. Equal and perpendicular endpoints give defect 0 without exception, which is Lemma 2′; antipodal endpoints scatter, and that scatter is why the proof has to force the endpoints to agree before it can use the identity. Every bar is a count from live computation over all pairs in range, not a model.

Section 3Seven letters

Let Γ = ℤ₄ × {+1, −1} and bn = (tn, δn), where un = itn. Writing the letter (r, δ) as the digit 2r + [δ = −1], the word begins 0 2 5 2 4 7 5 2 4 6 1 7 4 7 5 2 4 6 1 6 0 3 1 7 …, and it is the fixed point of the 2-uniform morphism 0 ↦ 02, 1 ↦ 03, 2 ↦ 52, 3 ↦ 53, 4 ↦ 46, 5 ↦ 47, 6 ↦ 16, 7 ↦ 17.

Theorem 2 · proved

Let τ identify the two letters (0, +1) and (2, +1) and be injective otherwise. The word τ(b) over seven letters is 3-free. Hence kmin ≤ 7: there is an infinite unit-step walk in ℕ7 with no three collinear vertices. (Theorem 1, that the eight-letter word itself is 3-free, follows, since τ acts linearly on Parikh vectors.)

Proof. Suppose x = bα ⋯ bβ−1 and y = bβ ⋯ bγ−1 form a bad pair, with p = β − α and q = γ − β. For any function g on the seven letters, q·g(x) = p·g(y), where g(x) means the sum of g over the block. Three choices of g finish the argument, and each is well defined after the identification because it takes the same value on the two merged letters.

  1. Parity. g₁(r, δ) = (−1)r. Because consecutive directions differ by one quarter turn, this sum telescopes to an indicator difference, and a two-valued telescoping lemma forces tα, tβ, tγ to have the same parity.
  2. Half-plane. g₂(r, δ) = [r ∈ H] − [r + δ ∈ H] with H = {0, 1}, which vanishes on both merged letters. It telescopes the same way and forces the three directions into the same half. Parity and half together pin an element of ℤ₄, so uα = uβ = uγ.
  3. Displacement. g₃ is the step of the walk Wn = Zn + ((1+i)/2)un, which moves only on right turns and is therefore zero on both merged letters. With the directions now equal, g₃ over the two blocks is exactly X = Zβ − Zα and Y = Zγ − Zβ, so qX = pY.

Lemma 2 applies to all three pairs (α, β), (β, γ), (α, γ), whose endpoint directions are now equal, giving ν(X) = ν₂(p), ν(Y) = ν₂(q) and ν(X + Y) = ν₂(p + q). But qX = pY makes X/p = Y/q = (X + Y)/(p + q), so ν₂(p) = ν₂(q) = ν₂(p + q), which is impossible: if p and q have the same 2-adic valuation then p + q has a larger one. ∎

The argument is Shallit's with three substitutions: the dragon walk in place of the Gaussian digit walk, two indicator functionals in place of the full direction vector, and the right-turn walk in place of the plain displacement. The second substitution is what makes the merge possible, and the third is what keeps the merged letters invisible to it. The same works for each of the four identifications (r, δ) ~ (r+2, δ), with H and the mirror walk chosen to match.

Section 4Where this sits

This is a fast-moving problem, and the honest summary is that the seven proved here is not the best bound known. The state of play on 9 September 2026:

LettersWhoStatusEvidence
16Shallit, arXiv:2609.05780 (after Cambie and Kalviainen, arXiv:2609.01766)provedpublished preprint, read in full
14Cambie, repository draft, 5 Sep 2026draftnot on arXiv, author's own label: review pending
8this note, Theorem 1provedsection 3
7this note, Theorem 2provedsection 3; word checked 3-free to 100,000
6Kalviainen, repository draft, 5 Sep 2026draft, reviewed hereread line by line, numerics reproduced, no gap found
5Shallit's candidate morphismunproved3-free to 20,000 in this session's check
4lower bound, Brown 1971openL(3) = 7, so four letters are necessary; whether they suffice is open

The review of the six-letter draft was a deliberate part of the session, and it is worth saying what it did and did not establish. The draft builds its word from the alternating binary digit sum σ(n) = Σj(−1)jbj(n) mod 4, applies Cambie's offsets, and identifies two pairs among its eight transitions. Each of its six steps was re-derived here by hand, its valuation identity was checked on all 3,123,750 pairs below 2500, and its six-letter word was checked 3-free to 30,000. No gap was found. That is a reading, not a referee report, and the author's own status label stands.

Two mechanisms therefore now exist for this problem, and they are genuinely different: the alternating-sign rule that the draft uses, and the alternating-order rule of the dragon curve. Both give eight-letter transition words; the codings available to them differ, six for one and seven for the other, and section 5 shows that difference is not an oversight.

Section 5What exhaustion says

StatementRangeLabel
L(1) = 1, L(2) = 3, L(3) = 7, with three canonical ternary words of length 7 and none of length 8 (Brown 1971 reproduced)exhaustivecertified
Every coding of the dragon word onto at most 6 letters has a bad pair. Of all 4011 partitions of the 8 letters into 3 to 7 classes, exactly 8 survive, all with 7 classes: the four proved antipodal merges and four mixed merges that are only checked, not provedfirst 3000 letterscertified
In the periodic sign and order family of Gaussian digit walks with period at most 4, eight-transition words occur only for the all-alternating patterns (coding floor above 6) and the fixed-order alternating-sign pattern (floor 6); no member codes onto 5 letterslengths 1200 to 1500certified
No cyclic uniform morphism of length at most 16 over four letters has a 3-free fixed point; over five letters none of length at most 13, and exactly 12 of the 16,470,816 candidates of length 14, Shallit's among themfixed point to length 1500certified
Canonical 3-free words over four letters number 640, 41,349, 583,081, 7,020,567 and 28,861,282 at lengths 10, 20, 30, 40 and 46; the ratio of consecutive counts falls slowly, 1.303 then 1.283 then 1.271length ≤ 46certified counts, numerical extrapolation
The seven-letter word τ(b) is 3-free to 100,000; the eight-letter word to 30,000; Kalviainen's six-letter word to 30,000; Shallit's four candidates to 20,000prefixes as statedcertified for those prefixes

The growth counts are the reason to stop searching for a four-letter construction by machine: a language whose count multiplies by about 1.27 per letter at length 46 will not be exhausted, and a slowly falling ratio is equally consistent with a language that dies out much later. The counts are exact; the extrapolation is not a theorem, and it does not exclude a finite L(4).

Section 6Open questions

  1. Is kmin = 4? Search will not decide it, and a four-letter construction would need a mechanism outside the Gaussian family, where four states already force eight transitions.
  2. Prove one of the mixed merges (r, −1) ~ (r+1, +1) of the dragon word, or Shallit's five-letter candidate. Either needs an invariant that is not the 2-adic valuation of a Gaussian displacement.
  3. A lower bound kmin ≥ 5 would need a structural obstruction over four letters. Nothing here points to one.