Must every infinite bounded-step walk in $\mathbb{Z}^3$ contain three collinear points? (Erdős #193)
Statement
Let $S\subseteq\mathbb{Z}^3$ be a finite set of allowed steps, and let $A=\{a_1,a_2,\ldots\}\subset\mathbb{Z}^3$ be an infinite $S$-walk, meaning $a_{i+1}-a_i\in S$ for every $i\ge 1$ (the points $a_i$ are the successive vertices visited). Must every such infinite $S$-walk contain three collinear points? Equivalently: does there exist a finite step-set $S$ and an infinite $S$-walk in $\mathbb{Z}^3$ no three of whose visited points are collinear, or is that impossible?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred) that for every finite step-set $S$ every infinite $S$-walk in $\mathbb{Z}^3$ contains three collinear points — OR a disproof exhibiting an explicit finite step-set $S$ and an explicit infinite $S$-walk in $\mathbb{Z}^3$ with no three collinear visited points, described finitely (e.g. an eventually periodic step-sequence or an explicit generating rule) together with a rigorous, verifiable proof that no three visited points are collinear. ADVANCES (each independently checkable): (a) a construction of an infinite (or record-length finite) $\mathbb{Z}^3$ $S$-walk minimising the maximal collinear subset, improving on the best bound stated in the background, delivered with the step-rule and a machine-checkable certificate; (b) a proof, for a restricted class of step-sets $S$ (for instance $|S|$ small, or $S$ symmetric), that three collinear points are forced; (c) an extension of the associated enumeration (OEIS A231255) to a new range with code and certificate. Deliver the explicit walk plus certificate, the proof file, or the search code plus attained bound.
Background
Originally conjectured by Gerver and Ramsey [GeRa79] and recorded by Erdős and Graham [ErGr79; ErGr80]; tagged 'geometry' (lattice points / collinearity). Known partial results, due to Gerver and Ramsey: in $\mathbb{Z}^2$ the answer is yes — every infinite bounded-step walk must contain three collinear points; in $\mathbb{Z}^3$ they showed instead that the largest number of collinear points among the visited points can be kept bounded, i.e. there are infinite $S$-walks whose maximal collinear subset is finite. Whether one can push this all the way down and avoid three collinear points entirely in $\mathbb{Z}^3$ — the stated question — is open. A related sequence is OEIS A231255 (associated with this problem on the source page; exact definition to be confirmed against OEIS). A Lean formalisation exists in DeepMind's formal-conjectures repository. Listed as open on erdosproblems.com/193 (fetched 2026-07-13, status 'open'); no Erdős prize is attached. Attacker's tool: constructive/greedy and SAT/constraint search for a finite step-set $S$ together with an explicit infinite $\mathbb{Z}^3$-walk (for instance eventually periodic in its step-sequence, or given by an explicit generating rule) whose visited points avoid all collinear triples — where periodicity or algebraic structure can reduce 'no three collinear among infinitely many points' to a finite check — or, conversely, a Ramsey/van der Waerden-flavoured proof that any infinite bounded-step walk is forced to repeat a direction and create a collinear triple.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #193 (T. F. Bloom) | website |
| REF-02 | OEIS A231255 — sequence related to Erdős #193 (Gerver–Ramsey lattice walks) | website |
| REF-03 | Lean formalisation of Erdős #193 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.