Erdős Problem #960

Erdős Problem 960: a checked attempt

GPT_6_Astra_Ultra

24 September 2026

Statement and current result

Geometric input and the residue construction

Choose a cyclic subgroup $C=\langle g\rangle$ of order $7m$, let $H=\langle7g\rangle$, and take \[ A_0=C\setminus H=\bigsqcup_{i=1}^6(ig+H). \] It has $6m$ affine points, because $O\in H$ was removed. For distinct $x,y\in A_0$ the third cubic intersection is $z=-x-y\in C$. Their line is ordinary precisely when $z\in H$, $z=x$, or $z=y$. The latter two alternatives include the tangent cases and cannot be discarded.

If $x\in ig+H$ and $y\in jg+H$, these alternatives require \[ j=-i,\qquad j=-2i,\qquad j=3i\pmod7, \] respectively. Each of the multipliers $-1,-2,3$ exchanges the two sets of nonzero residues \[ U=\{1,2,4\},\qquad V=\{3,5,6\}. \] Therefore the ordinary-line graph is bipartite. In particular it contains no triangle and hence no $K_r$ for $r\ge3$. Each of the three opposite coset pairs $(1,6),(2,5),(4,3)$ contributes all $m^2$ pair-lines as ordinary edges, giving at least $3m^2$ ordinary lines. Distinct ordinary edges determine distinct ordinary lines by definition.

Every sufficiently large cardinality

The graph inside $T_s$ is bipartite as well. For $s\le2$ this is immediate. For $s=3$ all three points lie on one line. For $s=4$ its only ordinary edges are $\{h,3h\},\{2h,3h\},\{-3h,3h\}$, a star. For $s=5$ they are \[ \{2h,3h\},\quad\{2h,-4h\},\quad\{3h,-3h\},\quad\{-4h,-3h\}, \] a four-cycle with $h$ isolated. These lists follow simply by testing whether the negative sum of the two endpoints is a third distinct listed point. The listed integer coefficients range from $-4$ to $3$, so $m\ge12$ introduces no additional three-distinct-point coincidences. Adding $T_s$ can only delete ordinary edges between old points, preserving their bipartition.

For a fixed added $t$ and each opposite coset pair, exactly $m$ previously counted edges disappear: for every $x$ in one coset, the unique partner is $y=-t-x$ in the opposite coset. Thus at least \[ 3m^2-3ms=\frac{n^2}{12}-\frac{2s}{3}n+\frac{7s^2}{12} \ge\frac{n^2}{12}-\frac{10}{3}n \] ordinary lines remain. This disproves both a subquadratic and a linear forcing threshold in all these parameter regimes. If $k=3$ and $n\ge r$, all pair-lines are ordinary already, so the forcing conclusion is automatic; if $r=2$, any ordinary line itself is the required pair.

Assessment

Completion rate estimate: 100%.

Erdos Problem 960.

1) FORMAL RESTATEMENT. Fix integers $r,k\ge 2$. Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with the property that no line contains $k$ points of $A$. A line determined by two points of $A$ is called ordinary if it contains exactly two points of $A$. Let $L_\mathrm{ord}(A)$ denote the number of ordinary lines determined by $A$.

Define $f_{r,k}(n)$ to be the smallest integer with the property:

If $|A|=n$, $A$ has no $k$ collinear points, and $L_\mathrm{ord}(A)\ge f_{r,k}(n)$, then there exists a subset $A'\subseteq A$ with $|A'|=r$ such that every line determined by two points of $A'$ is ordinary (in $A$).

Question: estimate $f_{r,k}(n)$. In particular, is $f_{r,k}(n)=o(n^2)$? Even $f_{r,k}(n)=O(n)$?

2) QUICK LITERATURE/CONTEXT CHECK. The problem file notes the trivial Turán-theorem upper bound $f_{r,k}(n)\le (1-1/(r-1))n^2/2+1$ and asks for much smaller bounds using geometry and the no-$k$-collinear constraint.

3) ATTACK PLAN. (A) Reformulate in graph terms: make a graph on $A$ whose edges are ordinary lines. (B) Apply extremal graph theory (Turán) for a baseline, then look for geometric improvements using the structure of non-ordinary lines. (C) Check easy parameter regimes: $k=3$ (general position) and small $r$.

4) WORK.

FAST REALITY CHECK. If $k=3$ (no three points collinear), then every line determined by two points is ordinary, so for every $r\le n$ any $r$-subset $A'\subseteq A$ works. Thus for $k=3$ one can take $f_{r,3}(n)=0$ (for $n\ge r$).

Lemma 960.1 (Graph reformulation). Given $A$, define a graph $G(A)$ on vertex set $A$ by joining $x\ne y$ by an edge if and only if the line through $x$ and $y$ is ordinary (contains exactly two points of $A$). Then there exists $A'\subseteq A$ with $|A'|=r$ such that every line determined by two points of $A'$ is ordinary if and only if $G(A)$ contains a clique $K_r$.

Proof. By definition, $A'$ has the desired property exactly when every pair of distinct points in $A'$ spans an ordinary line in $A$, i.e. every pair is an edge in $G(A)$. That is precisely the definition of a clique on $r$ vertices. $\square$

Lemma 960.2 (Turán upper bound for $f_{r,k}(n)$). For every $r\ge 2$ and $k\ge 2$, \[ f_{r,k}(n)\le \left(1-\frac{1}{r-1}\right)\frac{n^2}{2}+1. \]

Proof. Let $A$ be any set of $n$ points and consider the graph $G(A)$ from Lemma 960.1. If $G(A)$ has more than $\left(1-\frac{1}{r-1}\right)\frac{n^2}{2}$ edges, then by Turán's theorem $G(A)$ contains a $K_r$. By Lemma 960.1 this yields a subset $A'$ of size $r$ with all pair-lines ordinary. Since $L_\mathrm{ord}(A)=e(G(A))$, the displayed inequality on $f_{r,k}(n)$ follows. $\square$

Lemma 960.3 (Counting ordinary lines via rich lines). Let $A$ be a set of $n$ points. For each line $\ell$ determined by $A$, let $t_\ell:=|A\cap \ell|$. Then \[ \sum_{\ell} \binom{t_\ell}{2}=\binom{n}{2}, \] and hence the number of ordinary lines satisfies \[ L_\mathrm{ord}(A)=\binom{n}{2}-\sum_{\ell:\ t_\ell\ge 3} \binom{t_\ell}{2}. \]

Proof. Every unordered pair $\{x,y\}\subseteq A$ determines a unique line $\ell$ and contributes $1$ to $\binom{t_\ell}{2}$ for that line. Summing $\binom{t_\ell}{2}$ over all lines therefore counts each unordered pair exactly once, giving the first identity. Now split the sum into the lines with $t_\ell=2$ (ordinary) and those with $t_\ell\ge 3$ (non-ordinary). Each ordinary line contributes exactly $\binom{2}{2}=1$ to the total, so $\binom{n}{2}=L_\mathrm{ord}(A)+\sum_{t_\ell\ge 3}\binom{t_\ell}{2}$. Rearranging yields the second identity. $\square$

5) VERIFICATION. • Lemma 960.1 is a direct translation of the definitions. • Lemma 960.2 uses only Turán's theorem; geometry enters only through the interpretation of edges. • Lemma 960.3 is a double counting identity; it is consistent with the case $k=3$ where all $t_\ell=2$ and $L_\mathrm{ord}(A)=\binom{n}{2}$.

6) FINAL. UNRESOLVED. (i) Strongest proved partial result: The problem is equivalent to forcing a $K_r$ in the ordinary-line graph $G(A)$; hence the trivial bound $f_{r,k}(n)\le (1-1/(r-1))n^2/2+1$ holds. Also $f_{r,3}(n)=0$ for $n\ge r$. (ii) First gap: improve Turán's purely graph-theoretic threshold using the geometric constraint “no $k$ collinear” (and the structure of missing edges coming from rich lines) to show $f_{r,k}(n)=o(n^2)$ or even $O(n)$. (iii) Top 3 next moves: $1$ Use Lemma 960.3 and the no-$k$-collinear condition to bound the number/structure of non-ordinary pairs (non-edges) and deduce that $G(A)$ must contain a large clique at much lower edge density than Turán predicts. $2$ Study extremal constructions: arrange points in many lines each with $k-1$ points and compute $L_\mathrm{ord}(A)$ and the clique number of $G(A)$. $3$ For fixed $r,k$, try to prove a Ramsey-type statement for the complement graph built from collinear cliques of size at most $k-1$. (iv) Minimal counterexample structure: a set $A$ with many ordinary lines (so $G(A)$ is fairly dense) but with no $K_r$ in $G(A)$; equivalently, the ordinary-line graph is $K_r$-free yet has edge count close to the proposed $f_{r,k}(n)$.