Carson Crocker

math.CO — Combinatorics

Bounds for Erdős Problem #188: $7\le k\le 60$

Contributed by Carson Crocker

Let $\ell_k$ denote $k$ collinear points with consecutive distances $1$. Erdős Problem #188 asks for the least $k$ such that the plane can be colored red and blue with no two red points at distance $1$ and no blue copy of $\ell_k$. Previous work gives $6\le k\le 6330$, with the lower bound due to Tsaturian and the upper bound due to Currier, Mody, Xie and Zhang. We prove $7\le k\le 60$. For the lower bound we show that every red/blue coloring of the plane contains two red points at distance $1$ or a blue $\ell_6$, following the skeleton of Arman and Tsaturian's proof in three dimensions; four distance lemmas are reduced to explicit unsatisfiable propositional formulas, certified by DRAT proofs. For the upper bound we give an explicit periodic coloring whose red set consists of $90$ closed regular $24$-gons of $48$ different sizes, all of diameter less than $0.999$, in each period, with rational centers and sizes. Any two cells are either far apart (all distances between their points exceed $1$) or close together (all distances are less than $1$), which is checked in exact arithmetic for all periodic translates and rules out red unit pairs. That every $\ell_{60}$ contains a red point is proved by a computer-assisted verification: for every unit direction $u$, the sets $R-ju$, $j=0,\dots,59$, cover the period torus, with every inclusion checked in rigorous ball arithmetic. A second, separately written program, based on a reduction to one-dimensional covering problems solved in outward-rounded interval arithmetic, confirms this. The computations, the verification code and drafts of the text were produced with AI tools under the author's direction; all proof certificates and verification programs are public (doi:10.5281/zenodo.23405962).