Reused writeup on Math-5754 (gpt pro 5.2)

Erdős Problem 588 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/588

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/588.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/588.tex.

FORMAL RESTATEMENT.

Fix an integer $k\ge 2$. For each $n\ge 1$, define $f_k(n)$ to be the smallest integer $M$ such that:

For every set $P$ of $n$ points in $\mathbb{R}^2$ with the property that no $k+1$ points of $P$ are collinear, the number of distinct lines that contain at least $k$ points of $P$ is at most $M$.

Equivalently, \[ f_k(n)=\max\{\#\{\ell: |\ell\cap P|\ge k\}:\ |P|=n,\ P\subset\mathbb{R}^2,\ \text{no }k+1\text{ points collinear}\}. \] Under the "no $k+1$ collinear" assumption, "at least $k$" means exactly $k$.

Question: for fixed $k\ge 4$, is $f_k(n)=o(n^2)$ as $n\to\infty$?

QUICK LITERATURE/CONTEXT CHECK.

I will not use any literature beyond what is explicitly quoted in the problem statement (lower bounds of Kárteszi, Grünbaum, and Solymosi--Stojaković; and the remark about $k=3$).

ATTACK PLAN.

Proof-track ideas. $1$ Convert to an incidence counting problem: each $k$-rich line contributes many point pairs; derive universal $O(n^2)$ upper bounds and see whether any improvement to $o(n^2)$ is possible from the "no $k+1$ collinear" constraint alone. $2$ Try to leverage planar incidence theorems (Szemerédi--Trotter type) to get subquadratic bounds when $k$ is fixed.

Construction track ideas. $1$ Build explicit point sets with many $k$-point lines while avoiding $(k+1)$-point lines. $2$ Use probabilistic "generic position" arguments to realize desired incidence patterns without accidental extra collinearities.

In this write-up I only prove the trivial $O(n^2)$ upper bound and a very weak linear lower bound construction.

WORK.

Lemma 588.1 (pair-counting upper bound). For all integers $n\ge 1$ and $k\ge 2$, \[ f_k(n)\le \frac{\binom{n}{2}}{\binom{k}{2}}. \]

Proof. Let $P$ be any set of $n$ points with no $k+1$ collinear, and let $L$ be the set of lines containing at least $k$ points of $P$. Then each $\ell\in L$ contains exactly $k$ points of $P$, hence contributes exactly $\binom{k}{2}$ unordered pairs of points lying on $\ell$. Two distinct lines cannot share the same unordered pair of points, because any two points determine a unique line. Therefore the sets of point-pairs contributed by different $\ell\in L$ are disjoint subsets of the $\binom{n}{2}$ total point-pairs in $P$. Hence \[ |L|\binom{k}{2}\le \binom{n}{2}, \] so $|L|\le \binom{n}{2}/\binom{k}{2}$. Taking the maximum over $P$ yields the bound on $f_k(n)$. $\square$

Lemma 588.2 (a simple linear lower bound construction). For all integers $n\ge 1$ and $k\ge 2$, \[ f_k(n)\ge \left\lfloor\frac nk\right\rfloor. \] In fact, there exists a set $P$ of $n$ points in $\mathbb{R}^2$ with no $k+1$ collinear such that at least $\lfloor n/k\rfloor$ distinct lines each contain exactly $k$ points of $P$.

Proof. Let $t=\lfloor n/k\rfloor$ and let $r=n-tk$. Choose $t$ distinct lines $\ell_1,\dots,\ell_t$ in the plane. On each $\ell_i$, choose $k$ points independently from a continuous distribution supported on $\ell_i$ (e.g. choose a random real parameter along the line). Finally choose the remaining $r$ points independently from a continuous distribution supported on a region of the plane disjoint from all the $\ell_i$. Let $P$ be the resulting random set of $n$ points.

By construction, each $\ell_i$ contains at least $k$ points of $P$. We show that with probability $1$: (a) no line contains $k+1$ points of $P$, and (b) the only lines containing $k$ points are the designated $\ell_i$. Either conclusion implies $f_k(n)\ge t$.

Fix any specific $(k+1)$-tuple $Q$ of distinct chosen points. The event "$Q$ is collinear" is an algebraic condition of measure $0$ under a continuous distribution unless $Q$ was forced to lie on one of the $\ell_i$. But the only forced collinearities are those among the $k$ points on a single $\ell_i$; a $(k+1)$-tuple cannot be fully contained in a single $\ell_i$ because only $k$ points were placed on each. Thus for each fixed $(k+1)$-tuple $Q$, $\mathbb{P}(Q\text{ collinear})=0$. There are finitely many $(k+1)$-tuples, so by a union bound over finitely many measure-$0$ events, with probability $1$ no $(k+1)$ points are collinear. This proves (a).

Similarly, fix any $k$-tuple $R$ of points that is not exactly the $k$ points chosen on some single designated line $\ell_i$. Then $R$ is not forced to be collinear, so again $\mathbb{P}(R\text{ collinear})=0$. There are finitely many such $k$-tuples, so with probability $1$ none of them is collinear. Hence the only collinear $k$-tuples are the $k$ points on each $\ell_i$, implying (b).

Therefore there exists at least one deterministic outcome of the random choice with the stated properties, giving $f_k(n)\ge t=\lfloor n/k\rfloor$. $\square$

Fast reality check (numerics for the trivial upper bound).

For illustration, the pair-counting bound gives \[f_4(n)\le \binom{n}{2}/6\approx n^2/12,\qquad f_5(n)\le \binom{n}{2}/10\approx n^2/20.\] For example, for $n=10$ it yields $f_4(10)\le 7$ and $f_5(10)\le 4$.

VERIFICATION.

Lemma 588.1. The only nontrivial step is the uniqueness of the line through a pair of points; this is standard Euclidean geometry.

Lemma 588.2. The probabilistic argument uses only that collinearity of a fixed set of randomly chosen points from a continuous distribution has probability $0$ unless forced. The union bound is over finitely many tuples, so there is no measurability subtlety.

FINAL.

UNRESOLVED

(i) Strongest proved partial result: the universal bound $f_k(n)\le \binom{n}{2}/\binom{k}{2}=O(n^2)$ (Lemma 588.1), and a trivial construction giving $f_k(n)\ge\lfloor n/k\rfloor$ (Lemma 588.2).

(ii) First gap (crisp): prove a genuinely subquadratic upper bound $f_k(n)=o(n^2)$ for fixed $k\ge 4$, i.e. improve the pair-counting argument by using additional geometric constraints beyond "two points determine a line".

(iii) Top 3 next moves: 1. Prove an incidence bound of the form "the number of $k$-rich lines in an $n$-point set with no $k+1$ collinear is $O_k(n^{2-\varepsilon_k})$" using a planar incidence theorem. 2. Analyze whether the known near-quadratic lower bound constructions must still be $o(n^2)$ and identify which structural features prevent reaching $\Theta(n^2)$. 3. Computation: for small $n$ and $k=4$, search (by integer coordinates up to some range) for configurations maximizing 4-point lines to get sharper finite-n intuition.

(iv) Minimal counterexample structure: would be a family of point sets $P_n$ with no $k+1$ collinear but with $\Theta(n^2)$ distinct $k$-point lines. By Lemma 588.1 this would require nearly every point-pair to lie on a $k$-point line, i.e. an incidence structure approaching a block design where each line contains exactly $k$ points and pairs are almost perfectly packed into these lines.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.