Source-linked AI summary
An infinite walk in $\mathbb{N}^{16}$, using only unit steps, with no three collinear points
Jeffrey Shallit
TL;DR
The paper asks whether an infinite walk using only standard unit basis steps can avoid three collinear vertices. It constructs a 16-letter word and relates its frequency property to such a walk, proving that the 16-dimensional construction avoids triples.
Problem
The question is whether an infinite standard-basis walk can avoid three collinear vertices.
Source: §1 · p. 1Method
The paper constructs an infinite word over 16 letters and uses its frequency property to characterize collinearity in the associated standard-basis walk.
Source: §1 · p. 2, §1.1 · p. 2, §4 · p. 6Results
The word a is good, and the standard-basis walk in N^16 obtained from ρ(a_n)=4t_n+t_{n+1} has no three collinear vertices.
Source: §4 · p. 6Takeaways & Limitations
The least alphabet size admitting a good infinite word exists and is at most 16.
Source: §5 · p. 8The paper lists candidate cyclic morphisms for improving the bound but reports that it has been unable to prove they work.
Source: §5 · p. 8
Abstract
from arXiv · showhide
Is it possible to walk to infinity, avoiding three collinear points, using as steps only the standard unit basis vectors $(0,0,\ldots, 0, 1, 0, \ldots, 0)$? We prove this is possible in $16$ dimensions.
1 Introduction
The paper asks whether an infinite standard-basis walk can avoid three collinear vertices, and answers yes in 16 dimensions. It reformulates the geometric condition as a restriction on letter frequencies in adjacent blocks.
1 Introduction
1.1 A reformulation
- A sequence is good when no two consecutive nonempty blocks have identical frequencies for every letter, even if their lengths differ.These frequency vectors are normalized Parikh vectors.Source: §1.1 · p. 2
- A sequence is good if and only if its standard-basis walk has no three distinct collinear vertices.The equivalence connects the word formulation directly to the geometric problem.Source: §1.1 · p. 2
2 The construction
The construction builds sequences from binary digit sums and a finite alphabet, then describes them through morphisms. The paper identifies a 2-uniform morphism whose fixed point starts with (0, 1).
2 The construction
- The cited text identifies b as the good sequence generated by the morphism presented in Table 1, shifting the summary from a numeric prefix to the sequence’s generating construction.Source: Table 1 · p. 3
- The construction uses t_n, the number of 1s in n's binary expansion modulo 4, to form letters a_n=(t_n,t_{n+1}) in a sixteen-letter alphabet.The sequence begins (0,1)(1,1)(1,2)(2,1).Source: §2 · p. 3
- The word a is the fixed point starting with (0, 1) of a 2-uniform morphism.Each letter image has two letters, and iterating the morphism produces nested prefixes determining the infinite word.Source: §2 · p. 4
3 The arithmetic ingredient
The arithmetic ingredient shows that consecutive blocks with identical normalized Parikh vectors force equality of their encoded indices. Its proof uses 2-adic valuations to relate Gaussian-integer displacements to index gaps.
3 The arithmetic ingredient
- Lemma 3 says the displacement Z_n − Z_m is nonzero when 0 ≤ m < n and t_m = t_n; its proof sets e = ν2(n − m) and treats even n − m by halving same-parity indices.Source: §3 · p. 5
- Summing the assigned basis-vector differences over a block telescopes to the difference between its endpoint vectors.This identity lets the proof translate letter-count equalities into constraints on encoded indices.Source: §3 · p. 6
- Equal normalized Parikh vectors for consecutive blocks force equality of their three encoded indices.This is Lemma 4, the key link between block frequencies and the index sequence.Source: §3 · p. 6
4 Proof that the sequence is good
The proof establishes that the infinite word is good, so its associated standard-basis walk in N^16 has no three collinear vertices. It rules out repeated normalized block frequencies using 2-adic valuation constraints.
4 Proof that the sequence is good
- The constructed infinite word is good, and its associated standard-basis walk in N^16 has no three collinear vertices.The walk is defined using ρ(a_n) = 4t_n + t_{n+1}.Source: §4 · p. 6
- For consecutive nonempty blocks x,y with identical normalized Parikh vectors and positions [α,β), [β,γ), the proof takes positive lengths p,q and obtains a common complex V = X/p = Y/q.Here X = Zβ − Zα and Y = Zγ − Zβ; by (14), Lemma 3 applies to pairs (α,β), (β,γ), and (α,γ), proving all three displacements nonzero. Thus |V|² is positive rational and its valuation is defined.Source: §4 · pp. 6–7
- The resulting valuation constraints contradict the fact that ν2(p + q) is at least d + 1, so no such blocks exist.The proof obtains p = 2^d p0 and q = 2^d q0 for positive odd p0 and q0, making p + q divisible by 2^(d+1).Source: §4 · p. 7
- Relabeling letters by the bijection ρ preserves frequency equalities, yielding the geometric conclusion for the walk.The word-level result therefore transfers to the standard-basis walk.Source: §4 · p. 7
5 The dimension bound and the proposed smaller morphisms
The construction proves an upper bound of 16 on the least alphabet size admitting a good infinite word, while the exact minimum remains undetermined. Candidate cyclic morphisms are listed but not proved to work.
5 The dimension bound and the proposed smaller morphisms
- The least alphabet size admitting a good infinite word is at most 16, and the paper notes a known lower bound of 4.Determining the exact minimum remains of interest.Source: §5 · p. 8
- The author could not prove that the candidate cyclic morphisms work, so they do not improve the bound kmin ≤ 16 in this paper.The proposals are listed in the hope they may help other researchers improve the bound.Source: §5 · p. 8
- The proposals are organized by alphabet size, image of 0, and image length; other letter images use modular shifts of that displayed image.For letter r, add r modulo k to every letter in the image of 0.Source: §5 · p. 8
6 Declaration of AI usage
The author says the problem was proposed in June 2018 and that the recent construction and GPT-6 Astra release prompted an LLM-assisted attempt. Much of the paper was written by ChatGPT 6 Astra.
6 Declaration of AI usage
- The author proposed the unit-vector walk problem in June 2018 and discussed it with many people.Source: §6 · p. 8
- The recent Cambie and Kalviainen construction and GPT-6 Astra's release prompted the author to try the LLM on the unit-vector version.Source: §6 · p. 8
- The author reports that much of the paper was written by ChatGPT 6 Astra.Source: §6 · p. 8