No three in a line

Mathematics · Discrete geometry Epoch AI

No three in a line

Let $G_n=\{1,\ldots,n\}^2$. Seek subsets $S_n\subseteq G_n$ with no three distinct points on a common Euclidean line. All slopes count; arithmetic is over the integers, not modulo a prime.

The task is to construct an unbounded family with $|S_n|>1.8n$. Give a generator, prove that the available grid sizes are unbounded, and prove both the size bound and exclusion of collinear triples. The row bound is $2n$; classical constructions approach $1.5n$. An improvement by a fixed positive multiple of $n$, even below the target, is useful partial progress. An additive constant does not improve the asymptotic ratio.

The family may use selected grid sizes, provided they are unbounded. A proof that no such unbounded family exists also resolves the target.

Finite examples support a proposed construction but do not establish an infinite family. Include exact point sets, generation code and determinant-based checks where computation is used.

Source: Epoch AI, The No-Three-in-Line Problem, FrontierMath: Open Problems.

Type

closed-ended

Solve status

open

Access

Public