Erdős problem 193 · combinatorics on words
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.
Everything below is the technical version. Section 3 is the whole proof; section 5 is where this result sits relative to everyone else's.
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.
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.
Define Gaussian units un and the walk Zn by u0 = 1, Z0 = 0 and, for every n,
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²).
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.
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.
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.
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.
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:
| Letters | Who | Status | Evidence |
|---|---|---|---|
| 16 | Shallit, arXiv:2609.05780 (after Cambie and Kalviainen, arXiv:2609.01766) | proved | published preprint, read in full |
| 14 | Cambie, repository draft, 5 Sep 2026 | draft | not on arXiv, author's own label: review pending |
| 8 | this note, Theorem 1 | proved | section 3 |
| 7 | this note, Theorem 2 | proved | section 3; word checked 3-free to 100,000 |
| 6 | Kalviainen, repository draft, 5 Sep 2026 | draft, reviewed here | read line by line, numerics reproduced, no gap found |
| 5 | Shallit's candidate morphism | unproved | 3-free to 20,000 in this session's check |
| 4 | lower bound, Brown 1971 | open | L(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.
| Statement | Range | Label |
|---|---|---|
| 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) | exhaustive | certified |
| 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 proved | first 3000 letters | certified |
| 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 letters | lengths 1200 to 1500 | certified |
| 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 them | fixed point to length 1500 | certified |
| 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.271 | length ≤ 46 | certified 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,000 | prefixes as stated | certified 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).