Erdős Problem #188

Erdős Problem 188: unit-step progressions and the unrestricted-step distinction

1. Statement and scope

What is the smallest $k$ for which the plane admits a red-blue colouring with no red pair at distance one and no blue collinear $k$-term progression of step length one? The minimum remains unresolved in this attempt. We prove directly that $k\ge4$ and prove the impossibility of any finite $k$ if the blue step length is unrestricted. We also distinguish our proved lower bound from the stronger established lower bound $k\ge6$.

2. A complete obstruction to avoiding blue triples

Suppose a colouring has neither a red unit-distance pair nor a blue unit-step triple. If there are no red points, any three points in a unit-step progression contradict the second condition, so choose a red point and translate it to the origin. Every point on the unit circle is blue.

Choose unit vectors $u,v$ with $|u-v|=1$, equivalently $u\cdot v=1/2$. The points $2u-v,u,v$ form a unit-step collinear triple. Its latter two points are blue, so $2u-v$ must be red. Its squared norm is \[ |2u-v|^2=4+1-4(u\cdot v)=3. \] Rotating the chosen pair about the origin shows that every point on the circle of radius $\sqrt3$ must be red: every point of that circle is a rotation of $2u-v$. But this circle contains the two points \[ (-1/2,\sqrt{11}/2),\qquad(1/2,\sqrt{11}/2), \] which are at distance one. This contradiction proves that every colouring with no red unit pair has a blue unit-step triple. Thus the sought minimum, if it exists, is at least four. This argument includes no regularity or measurability assumption on the colouring.

The stronger known theorem of Tsaturian states that such a colouring always has a blue unit-step progression of length five, and therefore the known lower bound is $k\ge6$. That theorem is explicit external context; its proof is not supplied by the shorter radius-$\sqrt3$ argument above. The primary paper's statement has been checked, and the older draft's unsupported stronger unpublished claim is not adopted.

3. Why the step-length qualification changes the question

Assume only that there is no red unit pair and restrict to the integer lattice points on any fixed unit-spaced line. For each integer $n$, at least one of $n,n+1$ is blue. Choose $j(n)\in\{0,1\}$ with $n+j(n)$ blue, choosing zero if both choices work.

For any desired length $r$, van der Waerden's theorem, the explicit standard input here, supplies an arithmetic progression \[ a,a+d,\ldots,a+(r-1)d \] on which $j(n)$ is constant, say equal to $j$. Translating the progression by $j$ gives a blue progression of length $r$. Its step $d$ is a positive integer, but need not equal one. Since $r$ was arbitrary, forbidding blue progressions of arbitrary step length is impossible for every finite $k$.

This proves the observation attributed to Alon on the problem page. It does not prove that arbitrarily long unit-step blue progressions must occur: that would discard the step restriction on which the actual problem depends.

4. Assessment and sources

The radius argument and the unrestricted-step conclusion are fully proved. No colouring avoiding both a red unit pair and a sufficiently long unit-step blue progression has been constructed here, and the exact minimum is not determined.

Sources: https://www.erdosproblems.com/188; S. Tsaturian, A Euclidean Ramsey result in the plane, https://arxiv.org/abs/1703.10723, for the stronger stated five-point theorem. Van der Waerden's theorem is used only in Section 3.

Completion rate estimate: 25%.

Erdős problem 188

1) FORMAL RESTATEMENT

A 2-colouring of $\mathbb{R}^2$ assigns each point red or blue. We seek the smallest integer $k$ such that there exists a colouring with: (A) no two red points at Euclidean distance $1$; and (B) no $k$-term unit-step collinear arithmetic progression of blue points, i.e. no set \[ \{x, x+v, x+2v,\dots,x+(k-1)v\}\subset \mathbb{R}^2 \] with $\|v\|=1$ all coloured blue.

2) QUICK LITERATURE/CONTEXT CHECK

Problem text states: if one drops the unit-step condition in (B), then no such $k$ exists (Alon’s observation). For the unit-step version, the text records lower bounds $k\ge 6$ (Graham) and $k\ge 9$ (Exoo, unpublished).

3) ATTACK PLAN

$1$ Prove a baseline lower bound $k\ge 3$ (since $k=2$ would forbid blue unit-distance pairs too, impossible). $2$ Give a full proof of Alon’s "no finite $k$" for the unrestricted-step interpretation. These are rigorous partial results; the intended unit-step problem remains open.

4) WORK

Lemma 4.1 ($k\ge 3$).

There is no 2-colouring of $\mathbb{R}^2$ with both colours avoiding unit-distance pairs. In particular, a colouring satisfying (A) and additionally forbidding blue 2-term unit-step progressions cannot exist; hence $k\ne 2$ and $k\ge 3$. Proof. Assume for contradiction that no two red points are at distance $1$ and no two blue points are at distance $1$. Consider an equilateral triangle of side $1$ in $\mathbb{R}^2$ with vertices $p,q,r$. By pigeonhole, two vertices share a colour; those two are at distance $1$, contradicting the assumption. Therefore at least one colour must contain a unit-distance pair, so $k=2$ is impossible. $\square$

Lemma 4.2 (Alon’s observation for unrestricted progressions).

If condition (B) is interpreted as "no $k$-term arithmetic progression of blue points on a line" with no restriction on step length, then no finite $k$ exists: every colouring with (A) forces arbitrarily long blue arithmetic progressions along some unit-spaced line. Proof. Fix a line $L$ in $\mathbb{R}^2$ and identify its integer lattice points $\{m\in\mathbb{Z}\}$ spaced by distance $1$. Restrict the plane-colouring to these points, giving a 2-colouring of $\mathbb{Z}$. If there are two red points at distance $1$ on $L$, then (A) fails, so assume not. Thus no two consecutive integers are red, so for every $n\in\mathbb{Z}$, either $n$ is blue or $n-1$ is blue. Let $B$ be the blue set. Then $B\cup (B+1)=\mathbb{Z}$.

Define a genuine 2-colouring $c$ of $\mathbb{Z}$ by: $c(n)=0$ if $n\in B$, and $c(n)=1$ otherwise (so if $c(n)=1$ then $n-1\in B$). By van der Waerden’s theorem (for 2 colours), $c$ contains arbitrarily long monochromatic arithmetic progressions. If such a progression is in colour $0$, it lies in $B$ and is a blue progression. If it is in colour $1$, then shifting the progression by $-1$ yields a progression in $B$ (since $c(n)=1\Rightarrow n-1\in B$). Hence $B$ contains arbitrarily long arithmetic progressions (with some step size), so no finite $k$ can forbid them. $\square$

5) VERIFICATION

Lemma 4.1 is a one-triangle obstruction; it uses only the existence of an equilateral unit triangle. Lemma 4.2 uses only the restriction to a unit-spaced line and van der Waerden’s theorem as stated in the problem text.

6) FINAL

UNRESOLVED (for the intended unit-step version)

(i) Strongest proved partial results: $k\ge 3$ (Lemma 4.1). Also, if step-length is not fixed, then no finite $k$ exists (Lemma 4.2).

(ii) First gap: construct any colouring satisfying (A) and (B) for some explicit finite $k$, or prove impossibility below the best-known lower bounds.

(iii) Top 3 next moves: 1. Encode unit-distance constraints as a graph/hypergraph colouring problem on discretizations (lattices / tilings). 2. Study whether blue set must contain long unit-step collinear progressions given red is a distance-1 avoiding set. 3. Attempt computational / SAT search on periodic colourings (fundamental domain) to get explicit upper bounds.

(iv) Minimal counterexample structure: a periodic or quasi-periodic colouring with red as a distance-1 avoiding set of positive density and blue engineered to avoid long collinear unit-step runs in every direction.