Can a walk on the 3D grid avoid every three-in-a-line, forever?

Erdős Problem #193 asks whether an infinite walk with steps from a finite set can visit lattice points with no three ever collinear. Open since 1979. This project attacks it with exact computation: a construction that builds record walks, and a certificate programme that tries to prove they can run forever.

28,271steps in the record walk — built by 6 rounds of the construction, exactly verified (no 3 of its 28,272 points collinear), and SHA-256 certified so anyone can re-check it in 30 seconds
1.2 Bexact integer transitions computed to map every arithmetic situation a walk can reach — proving each one keeps an escape route in all 13 direction classes, with zero exceptions
124moves in the fixed menu (every integer vector with coordinates in ±2) — fixed forever, as the problem demands; rich enough that stitching never runs out of options

Two equations that carry the project

$$\text{collinear}(x,y,z)\;\Longleftrightarrow\;(y-x)\times(z-x)=\mathbf{0}$$

The rule, exactly. Three grid points line up precisely when this cross product of integer vectors is the zero vector — so every check in the project is exact integer arithmetic, never a floating-point approximation. The record walk passes this test for all 3.8 trillion of its triples.

$$e\cdot \bar q^{\,H}\cdot\bigl(3(H{+}1)\,L+1\bigr)\;\le\;1$$ $$\bar q=0.181,\quad L=6.5\times10^{7}\quad\Rightarrow\quad H=14$$

The target, quantified. The Lovász Local Lemma condition: each danger’s H-round failure probability (measured worst case $\bar q = 0.181$ per round) against the number of constraints entangled with it. The inequality first holds at $H=14$ (left side $\approx 0.33$) — watching each newborn danger for 14 rounds suffices, in the model, for every danger in an infinite walk to be dodged simultaneously.

The geometry

x +2 y +2 z +2

The menu. All 124 moves — every nonzero integer vector with coordinates in ±2, inside their ±1 and ±2 cube frames (view turned slightly so every move stays distinct). Large dots: the 26 inner (±1) moves; small: the radius-2 shell. Every step of every walk is one of these.

One real generation. The record run's actual level-1 walk (62 steps): 21 enlarged anchors (blue) joined by the dashed skeleton, reconnected through 42 newborn stitch points (green). Repeat this 5 more times → 28,271 steps.

Origin story

bowls in the rack: same shape, each one offset and tilted from the last the walk: same shape, enlarged + twisted — nested at every scale, never aligned (schematic)

This project got unstuck because of a dishwasher. Every early attempt built self-copying patterns that stacked like plates — each scale aligned with the last, and alignment is exactly what this problem punishes (we eventually proved all such stacked constructions must fail). Then Amanie shared a Reddit post about loading bowls in a dishwasher, and Erik noticed the bowls do something plates don’t: they nest at a tilt — the same shape repeated, each one offset and rotated from the last. Translated into mathematics, that became the whole construction: enlarge the walk by a matrix that also twists it by an angle that never repeats, so no two scales can ever line up. That one idea — imbrication — is the backbone of the record walks and of the entire proof strategy on this site.

The project is built and run by Erik Kalviainen (ekalvi), a software engineer in Canada, on an always-on Mac in his homelab. The mathematics, code and computations are driven by Claude Fable 5 (Anthropic’s research-grade AI) working autonomously under Erik’s direction, with strategy review from a second AI (GPT 5.6) — and every result is verified by exact integer arithmetic that anyone can re-run. Idea credit where it’s due: to Amanie, and to whoever loaded that dishwasher.

Explore

The proof strategy, in six diagrams

From the rule of the game to the Local Lemma closure — every number real.

Interactive demo of the construction

Real coordinates from a verified run. Click any three points to test them live.

Research log

Timeline of every milestone, measurement and honest dead end — updated live.

Code, data & certificates

Every search, table, walk and SHA-256 certificate — independently verifiable.

Background

The problem statement

Problem #193 at erdosproblems.com, with the Gerver–Ramsey history.

Every number on this site is exhaustively computed and independently verifiable.