No-Three-in-Line Problem

Definitions and mathematical statement

For a positive integer $n$, define $[n]=\{1,2,\ldots,n\}$ and regard $[n]^2=[n]\times[n]$ as a set of points in the real affine plane ${\mathbb{R}}^2$. A subset $S\subseteq[n]^2$ has no three collinear points if every affine line in ${\mathbb{R}}^2$ contains at most two elements of $S$. Equivalently, for every three pairwise distinct points $(x_1,y_1),(x_2,y_2),(x_3,y_3)\in S$, \[ \det\begin{pmatrix} x_1&y_1&1\\ x_2&y_2&1\\ x_3&y_3&1 \end{pmatrix}\ne0. \] The supplied question asks whether \[ \forall n\in{\mathbb{Z}}_{\ge1}\quad\exists S\subseteq[n]^2\quad \left(|S|=2n\ \text{ and }\ \forall\text{ affine lines }\ell\subseteq{\mathbb{R}}^2,\ |S\cap\ell|\le2\right). \] Unresolved boundary qualification. The supplied positive-integer range includes $n=1$, for which $[1]^2$ has only one point and cannot contain a subset of cardinality $2$. Thus the literal formulation has a boundary inconsistency with its presentation as an open conjecture. Restricting the question to integers $n\ge2$ would remove this particular obstruction, but that restriction is not explicitly supplied and requires source confirmation. The displayed formula preserves the supplied quantifier rather than silently changing it.

The original excerpt also contains fragmented material concerning quantities denoted $\alpha_{d,k}(n)$, a bound attributed to Lefmann, and a theorem labelled Suk--Zeng [15]. Definitions, hypotheses, and exponents in that material are incomplete or corrupted; no additional higher-dimensional statement can be specified reliably from it.

Short English statement

The question asks whether every $n\times n$ integer grid admits a selection of exactly $2n$ distinct points with at most two on any straight line. The supplied range includes $n=1$, where the requested selection is impossible; the intended lower bound on $n$ therefore needs confirmation. The source labels the problem open, subject to its supplied dated literature assessment.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005806$, source problem code catalogue entry; registry: data/unsolvedmath/problems.json, with catalog/problems.json as the supplementary project catalog. This draft uses the supplied complete record and does not assert independent inspection of either file.
• Discrete Geometry (2024), Oberwolfach Reports, DOI 10.4171/owr/2024/3, pp. 137--202. https://doi.org/10.4171/owr/2024/3. The supplied excerpt identifies the talk Variation of no-three-in-line problem, Ji Zeng, joint work with Andrew Suk, Yaobin Chen, Xizhi Liu, and Jiaxi Nie, and includes a page marker 188. It attributes the original no-three-in-line problem to Dudeney in 1917, using reference label [6]; the corresponding bibliographic entry is not supplied. The registry year 2024 identifies the report context, not the historical origin of the problem.
• Constraint Satisfaction Programming for the No-three-in-line Problem. https://arxiv.org/abs/2602.07751. Supplied literature-review reference; its contents have not been independently verified for this draft.
• Permutations minimizing the number of collinear triples. https://doi.org/10.1007/s10623-025-01632-w. Supplied literature-review reference; its contents have not been independently verified for this draft.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and reports that existing primary work provides finite-range constructions and improved bounds, without establishing the requested $2n$-point configurations for every grid size. This is supplied dated curation derived from the Oberwolfach material, not an independently verified literature assessment. The registry also labels the statement corrected_verified and says it was reconstructed and checked against the official report; these are supplied verification claims, not verification performed for this draft.