Can a robot walk forever with a finite menu of moves—and never visit three points on one line? Yes.
Erdős Problem 193 asks whether every such walk on the 3D integer grid must eventually contain three collinear points. This construction gives an explicit counterexample, published as arXiv:2609.01766.
GPT-5.6 Sol
Pi
Oh My Pi
PaseoSimple rule · unexpected geometry
Pass any \(n\) to obtain the first \(n\) exact lattice points. There is no fixed maximum: the same rule defines the walk for every natural-number index, so arbitrarily long prefixes expose more of the infinite structure.
def gaussian_walk(n):
z = 0j
points = []
for k in range(n):
s2 = k.bit_count()
u = 1j**s2
c = 1j * (1 - u) / (1 - 1j)
W = 2 * z + c
H = 4 * k + s2 % 4
P = int(W.real), int(W.imag), H
points.append(P)
z += u
return pointsA binary counter becomes a self-similar spatial walk.
This recurrence generates the fractal walk for every \(n\).
Every chord has the same binary fingerprint as its height.
If \(u_m=u_n\) and \(n-m\) is even, the binary recurrence halves both indices and factors the planar chord by \(1+i\). Each halving adds one to the valuation of the squared norm. After \(\nu_2(n-m)\) halvings, the remaining gap is odd and the remaining squared norm is odd:
The matching square and height tags remove the equal-state restriction. Adjacent corners make both sides odd; opposite corners give valuation one. Thus every pair satisfies
Multiplying a planar chord by \(k\) adds \(2\nu_2(k)\) because its squared norm scales by \(k^2\). A height gap gains only \(\nu_2(k)\). That mismatch makes a straight line impossible. See the full derivation.
The pair law rules out collinearity.
Let \(A,B>0\) be the adjacent height gaps and \(X,Y\) the matching planar chords. Collinearity gives \(X/A=Y/B=(X+Y)/(A+B)\).
Equal order + equal order has larger order.
The three pair laws force \(\nu_2(A)=\nu_2(B)=\nu_2(A+B)\). But after removing their common power of two, \(A\) and \(B\) are both odd, so their sum is even.
A four-state automaton turns each indexed ± sign rule into a striking self-similar walk. Explore compact, branching, woven, and reflective forms.
Explore the rule family →New follow-up: the joint d*/s* minimum problem → The proved floor is four; dimensions and step counts four and five remain open; g85 supplies a proposed ceiling of six pending independent review.
A Hilbert-curve walk first exposed the four-state tag geometry.
Before the compact Gaussian formula, an earlier construction followed a discrete Hilbert curve—a recursive path through square grids—and tracked four possible orientations. Those orientations suggested the cyclic corner tags. This background is optional: the code and proof above are self-contained.
See the earlier construction’s development →
