Erdős Problem #193

Erdős Problem #193

1. FORMAL RESTATEMENT

Must every infinite set of lattice points visited by a walk in $\mathbb Z^3$, with increments from a fixed finite set, contain three distinct collinear points?

2. LITERATURE AND SCOPE

The answer is negative. We reconstruct the short Gaussian-lattice construction in Cambie and Kalviainen, An infinite small-step $\mathbb Z^3$-walk with no collinear triple $2026$. The previous local attempt predates this resolution. All the needed identities and the collinearity obstruction are proved below. This is a known counterexample, not a new discovery or a claim that this document itself has been formally verified.

3. CONSTRUCTION AND A VALUATION IDENTITY

Let $s_2(n)$ count binary ones, and put \[ u_n=i^{s_2(n)},\qquad z_n=\sum_{r=0}^{n-1}u_r,\qquad \alpha_n\in\{0,1,2,3\},\quad u_n=i^{\alpha_n}. \] For $\epsilon\in\{0,1\}$, \[ u_{2n+\epsilon}=i^\epsilon u_n,\qquad z_{2n+\epsilon}=(1+i)z_n+\epsilon u_n. \tag{1} \] Write $v_2$ for the exponent of two in a nonzero integer. If $m<n$ and $u_m=u_n$, then \[ v_2(|z_n-z_m|^2)=v_2(n-m). \tag{2} \] Indeed, when $n-m$ is even, write $m=2a+\epsilon,n=2b+\epsilon$. Equation $1$ gives $u_a=u_b$ and $z_n-z_m=(1+i)(z_b-z_a)$. Repeat exactly $v_2(n-m)$ times. The remaining chord is a sum of an odd number of Gaussian units, so the sum of its two integer coordinates is odd. Its squared norm is therefore odd. Each removed factor $1+i$ multiplies the squared norm by two, proving $2$ and also showing the chord is nonzero.

Set \[ c_0=0,\quad c_1=i,\quad c_2=-1+i,\quad c_3=-1, \qquad w_n=2z_n+c_{\alpha_n},\qquad h_n=4n+\alpha_n, \qquad P_n=(\Re w_n,\Im w_n,h_n). \] For every $m<n$ we claim \[ v_2(|w_n-w_m|^2)=v_2(h_n-h_m). \tag{3} \] Put $a=\alpha_m,b=\alpha_n,d=n-m$. If $a=b$, the two sides of $3$ equal $2+v_2(d)$ by $2$. If $b-a$ is odd, the corner difference has exactly one odd coordinate, so both $|w_n-w_m|^2$ and $4d+b-a$ are odd. If $b-a=\pm2$, both planar coordinates are odd, whose squared sum is $2\pmod4$, and $4d+b-a$ also has valuation one. These cases exhaust all possibilities, and ensure all squared norms in $3$ are positive.

4. FINITELY MANY BOUNDED STEPS

For $a=\alpha_n,b=\alpha_{n+1}$, \[ P_{n+1}-P_n= \left(\Re(2i^a+c_b-c_a),\Im(2i^a+c_b-c_a),4+b-a\right). \tag{4} \] There are at most sixteen possibilities. The last coordinate is between one and seven, so the vertices are distinct. To check the planar bound, $i^a$ points outwards from corner $c_a$ of the unit square. The component of $c_b-c_a$ along that direction is $0$ or $-1$, and the perpendicular component is $0$ or $\pm1$. Thus both planar step coordinates lie in $\{-2,-1,0,1,2\}$. In particular $4$ defines a fixed finite allowed step set.

5. EXCLUDING ALL COLLINEAR TRIPLES

Suppose $P_a,P_b,P_c$ were collinear with $a<b<c$. Write \[ A=h_b-h_a>0,\quad B=h_c-h_b>0,\quad X=w_b-w_a,\quad Y=w_c-w_b. \] The strict increase of height and collinearity give \[ X/A=Y/B=(X+Y)/(A+B). \] Their common squared norm is a positive rational number. Extending $v_2$ to nonzero rationals, $3$ gives respectively $-v_2(A),-v_2(B),-v_2(A+B)$ for the valuations of these equal squared norms. Thus all three integer valuations are equal. But if $v_2(A)=v_2(B)=t$, then $(A+B)/2^t$ is even, so $v_2(A+B)>t$, a contradiction.

6. VERIFICATION AND FINAL

SOLVED: negative answer, by a fully proved known construction. The argument handles arbitrary collinearity ratios, not only equally spaced triples. Exact checks of the sixteen step formulas and many chord identities supplement the proof; finite prefixes alone are not used to infer the infinite result. No mathematical input beyond binary arithmetic, parity and rational valuations remains external.

7. SOURCES

Current statement: https://www.erdosproblems.com/193. S. Cambie and E. Kalviainen, https://arxiv.org/abs/2609.01766, Theorem 1 and its proof; author material: https://github.com/ekalvi/erdos-193.

COMPLETION ESTIMATE

COMPLETION: 100%

Erdős problem 193

1) FORMAL RESTATEMENT

Let $S\subset\mathbb{Z}^3$ be finite. An $S$-walk is an infinite sequence $(a_n)_{n\ge 0}\subset\mathbb{Z}^3$ such that $a_{n+1}-a_n\in S$ for all $n$. Question: Must the set $\{a_n:n\ge 0\}$ contain three distinct collinear points?

2) QUICK LITERATURE/CONTEXT CHECK

Problem text states: in $\mathbb{Z}^2$ the answer is yes (Gerver--Ramsey [GR79]). In $\mathbb{Z}^3$ the question is open; the text notes bounds on the maximum number of collinear points can be controlled.

3) ATTACK PLAN

Provide reductions: $1$ the walk lies in a coset of the lattice generated by $S$, $2$ if $\mathrm{rank}\langle S\rangle_{\mathbb{Z}}\le 2$, the walk is planar (reducing to $\mathbb{Z}^2$ case). Also provide a computational sanity check for a sample $S$.

4) WORK

Lemma 4.1 (Lattice-coset containment).

Let $L=\mathrm{span}_{\mathbb{Z}}(S)\le \mathbb{Z}^3$. Then every $S$-walk $(a_n)$ satisfies \[ a_n\in a_0+L\quad \text{for all }n\ge 0. \] Proof. By induction: $a_0\in a_0+L$. If $a_n\in a_0+L$, then $a_{n+1}=a_n+s$ for some $s\in S\subset L$, hence $a_{n+1}\in a_0+L$. $\square$

Lemma 4.2 (Rank reduction).

If $\mathrm{rank}(L)=1$, then every $S$-walk lies on an affine line in $\mathbb{Z}^3$ (hence trivially contains infinitely many collinear points). If $\mathrm{rank}(L)=2$, then every $S$-walk lies in an affine plane $a_0+P$ where $P$ is a rank-2 sublattice of $\mathbb{Z}^3$. Proof. If $\mathrm{rank}(L)=1$ then $L=\mathbb{Z}v$ for some nonzero $v\in\mathbb{Z}^3$, and Lemma 4.1 gives $a_n\in a_0+\mathbb{Z}v$, an affine line. If $\mathrm{rank}(L)=2$, then $L$ is a rank-2 subgroup of $\mathbb{Z}^3$, hence contained in some 2D real subspace $P_{\mathbb{R}}\subset\mathbb{R}^3$; then $a_0+L\subset a_0+P_{\mathbb{R}}$, an affine plane. $\square$

FAST REALITY CHECK (computed)

For the sample step set $S=\{e_1,e_2,e_3\}$ (positive axis steps), an exhaustive backtrack search from $a_0=(0,0,0)$ found no $S$-walk longer than 7 steps without creating 3 collinear points; the longest found had 8 visited points and still avoided collinearity. This is only evidence for this particular $S$ (not a proof for infinite).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: every $S$-walk lies in a coset of $\mathrm{span}_{\mathbb{Z}}(S)$ (Lemma 4.1), so only the rank-3 case is genuinely 3D.

(ii) First gap: handle $\mathrm{rank}(L)=3$ without relying on known $\mathbb{Z}^2$ theorem.

(iii) Top 3 next moves: 1. Prove a 3D analogue of Gerver--Ramsey for special classes of $S$ (e.g. symmetric generating sets). 2. Attempt a density-in-lines argument: show infinitely many points force 3 collinear via pigeonhole on directions. 3. Systematically search for long finite $S$-walks with no 3 collinear to guess counterexample structures.

(iv) Minimal counterexample structure: a rank-3 step set $S$ and an infinite walk whose point set behaves like a discrete space curve avoiding repeated directions and avoiding long arithmetic structure in any line.