Erdős Problem #669

Erdős Problem 669 --- collection record

PROVENANCE AND STATUS

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

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/669.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT. Fix an integer $k\ge 2$. For a finite set $P\subset\mathbb{R}^2$ with $|P|=n$, let \begin{align*} L_{\ge k}(P) &:= \{ \ell : \ell \text{ is a line in }\mathbb{R}^2 \text{ and } |\ell\cap P|\ge k\},\\ L_{=k}(P) &:= \{ \ell : \ell \text{ is a line in }\mathbb{R}^2 \text{ and } |\ell\cap P|= k\}. \end{align*} Define extremal quantities \[ F_k(n) := \max_{|P|=n} |L_{\ge k}(P)|, \qquad f_k(n) := \max_{|P|=n} |L_{=k}(P)|. \] (These are equivalent to the "minimal such that for any $P$ there exist at most $F_k(n)$ lines" phrasing.)

The problem asks for asymptotics of $F_k(n)$ and $f_k(n)$ as $n\to\infty$ for fixed $k$, in particular the limits (if they exist) \[\lim_{n\to\infty} F_k(n)/n^2,\qquad \lim_{n\to\infty} f_k(n)/n^2.\]

QUICK LITERATURE/CONTEXT CHECK. The supplied statement records:

• $f_2(n)=F_2(n)=\binom n2$ (trivial).
• For $k=3$ (Orchard problem), Burr--Grünbaum--Sloane proved $f_3(n)=\frac{n^2}{6}-O(n)$ and $F_3(n)=\frac{n^2}{6}-O(n)$.
• A trivial upper bound $F_k(n)\le \binom n2/\binom k2$, hence $\limsup F_k(n)/n^2\le 1/(k(k-1))$.

Per project rules, I do not use external sources beyond these statements.

ATTACK PLAN.

• Prove the trivial pair-counting upper bound carefully (it is the main unconditional tool available from the prompt).
• For $k=3$, use the stated asymptotic to deduce the actual limit $\lim F_3(n)/n^2=\lim f_3(n)/n^2=1/6$.
• Give computational sanity checks on concrete configurations (e.g. integer grids) to understand magnitudes, though these do not claim optimality.

WORK.

Fast reality check (tiny $n$). For any $n<k$, $F_k(n)=f_k(n)=0$. For $n=k$, $F_k(k)\ge 1$ (take $k$ collinear points) and clearly $F_k(k)\le 1$, so $F_k(k)=f_k(k)=1$.

Lemma 669.1 (Exact-to-at-least relation). For every $n$ and $k$, \[ F_k(n) = \max_{|P|=n} |L_{\ge k}(P)| = \max_{|P|=n} \sum_{j\ge k} |\{\ell: |\ell\cap P|=j\}|. \] In particular, for a fixed point set $P$ one has the identity \[ |L_{\ge k}(P)| = \sum_{j\ge k} |\{\ell: |\ell\cap P|=j\}|. \]

Proof. For a fixed $P$, each line $\ell$ with $|\ell\cap P|\ge k$ has a well-defined integer $j=|\ell\cap P|\ge k$. The families $\{\ell:|\ell\cap P|=j\}$ for different $j$ are disjoint and their union over $j\ge k$ equals $L_{\ge k}(P)$. Taking cardinalities yields the displayed identity for $P$. Maximizing over $P$ preserves equality. $\square$

Lemma 669.2 (Trivial pair-counting upper bound). For all integers $n\ge k\ge 2$, \[ F_k(n) \le \frac{\binom n2}{\binom k2}. \] Consequently, \[ \limsup_{n\to\infty} \frac{F_k(n)}{n^2} \le \frac{1}{k(k-1)}. \]

Proof. Fix a set $P$ of $n$ points. Each line $\ell\in L_{\ge k}(P)$ contains at least $k$ points of $P$, hence contains at least $\binom{k}{2}$ unordered pairs of points from $P$. On the other hand, any unordered pair of distinct points of $P$ lies on exactly one line (the unique line through them), so the sets of pairs contributed by distinct lines are disjoint. Therefore the total number of unordered pairs in $P$, namely $\binom n2$, is at least the sum over $\ell\in L_{\ge k}(P)$ of $\binom{k}{2}$. That is, \[ \binom n2 \ge |L_{\ge k}(P)|\,\binom k2. \] Rearranging gives $|L_{\ge k}(P)|\le \binom n2/\binom k2$. Maximizing over $P$ yields the same bound for $F_k(n)$. Dividing by $n^2$ and taking $\limsup$ gives the stated constant upper bound. $\square$

Lemma 669.3 (Consequences for $k=3$ using the stated asymptotic). Assuming the statement in the prompt that $F_3(n)=\frac{n^2}{6}-O(n)$ and $f_3(n)=\frac{n^2}{6}-O(n)$, one has \[ \lim_{n\to\infty} \frac{F_3(n)}{n^2} = \frac16, \qquad \lim_{n\to\infty} \frac{f_3(n)}{n^2} = \frac16. \]

Proof. If $F_3(n)=\frac{n^2}{6}-O(n)$ then there is a constant $C>0$ with $|F_3(n)-n^2/6|\le Cn$ for all large $n$. Dividing by $n^2$ gives \[ \left|\frac{F_3(n)}{n^2}-\frac16\right| \le \frac{C}{n}, \] which tends to $0$ as $n\to\infty$. Therefore $F_3(n)/n^2\to 1/6$. The same argument applies to $f_3(n)$. $\square$

Computational sanity check (not claiming optimality). For an $m\times m$ integer grid $P=\{0,1,\dots,m-1\}^2$ (so $n=m^2$), I computed the number of lines containing at least $k$ grid points for small $m$. The exact counts found were:

3x3 grid (n=9):  lines with >=3 points = 8
4x4 grid (n=16): lines with >=3 points = 14, lines with >=4 points = 10
5x5 grid (n=25): lines with >=3 points = 32, lines with >=4 points = 16, lines with >=5 points = 12
6x6 grid (n=36): lines with >=3 points = 58, lines with >=4 points = 22, lines with >=5 points = 18
7x7 grid (n=49): lines with >=3 points = 108, lines with >=4 points = 44, lines with >=5 points = 24

These grow much more slowly than the quadratic upper bound from Lemma 669.2, illustrating that achieving $\Theta(n^2)$ many $k$-rich lines requires much more structured configurations than a square grid.

VERIFICATION.

• Lemma 669.2: checked that pair-sets from distinct lines are disjoint because a pair of points determines a unique line.
• For $k=3$, Lemma 669.2 gives $F_3(n)\le \binom n2/3 = \frac{n^2}{6}-\frac{n}{6}$, matching the stated asymptotic order and consistent with Lemma 669.3.
• The grid computation was rechecked by recomputing line keys via normalized integer coefficients; it is intended only as a sanity check.

FINAL. UNRESOLVED.

(i) Strongest proved partial results.

• For all fixed $k\ge 2$, $F_k(n)\le \binom n2/\binom k2$, hence $\limsup F_k(n)/n^2\le 1/(k(k-1))$ (Lemma 669.2).
• For $k=3$, using the asymptotics stated in the prompt, one gets the exact limits $\lim F_3(n)/n^2=\lim f_3(n)/n^2=1/6$ (Lemma 669.3).

(ii) First gap (crisp statement). For each fixed $k\ge 4$, determine whether the limits $\lim_{n\to\infty} F_k(n)/n^2$ and $\lim_{n\to\infty} f_k(n)/n^2$ exist, and if so compute them. In particular, decide whether the trivial upper bound constant $1/(k(k-1))$ is sharp.

(iii) Top 3 next moves.

1. Constructions: search for algebraic or finite-geometry inspired point sets in $\mathbb{R}^2$ producing $\Theta(n^2)$ many lines with exactly $k$ points for fixed $k\ge 4$.
2. Upper bounds beyond pair-counting: prove stronger restrictions on the number of $k$-rich lines using incidence geometry (e.g. inequalities relating $k$-rich lines to point-line incidences), aiming to show the constant is strictly smaller than $1/(k(k-1))$ when $k\ge 4$.
3. Computer search for small $k$: for $k=4$, do exhaustive/heuristic searches over integer/rational point sets to estimate $F_4(n)$ and guess the correct asymptotic constant.

(iv) What a minimal counterexample would likely look like. If the upper bound constant $1/(k(k-1))$ is not sharp for some $k\ge 4$, then any near-extremal configuration would have to use many lines each contributing close to the minimum $\binom{k}{2}$ pairs, with few (ideally no) lines containing more than $k$ points, because higher multiplicity lines "waste" pairs. Thus a minimal counterexample to sharpness would likely consist of a configuration where unavoidable geometric constraints force many points to lie on some lines with $>k$ points, depressing the total count of distinct $k$-rich lines below the pair-counting maximum.

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.

FORMAL RESTATEMENT. Fix an integer $k\ge 2$. For a finite set $P\subset\mathbb{R}^2$ with $|P|=n$, let \begin{align*} L_{\ge k}(P) &:= \{ \ell : \ell \text{ is a line in }\mathbb{R}^2 \text{ and } |\ell\cap P|\ge k\},\\ L_{=k}(P) &:= \{ \ell : \ell \text{ is a line in }\mathbb{R}^2 \text{ and } |\ell\cap P|= k\}. \end{align*} Define extremal quantities \[ F_k(n) := \max_{|P|=n} |L_{\ge k}(P)|, \qquad f_k(n) := \max_{|P|=n} |L_{=k}(P)|. \] (These are equivalent to the "minimal such that for any $P$ there exist at most $F_k(n)$ lines" phrasing.)

The problem asks for asymptotics of $F_k(n)$ and $f_k(n)$ as $n\to\infty$ for fixed $k$, in particular the limits (if they exist) \[\lim_{n\to\infty} F_k(n)/n^2,\qquad \lim_{n\to\infty} f_k(n)/n^2.\]

QUICK LITERATURE/CONTEXT CHECK. The supplied statement records:

• $f_2(n)=F_2(n)=\binom n2$ (trivial).
• For $k=3$ (Orchard problem), Burr--Grünbaum--Sloane proved $f_3(n)=\frac{n^2}{6}-O(n)$ and $F_3(n)=\frac{n^2}{6}-O(n)$.
• A trivial upper bound $F_k(n)\le \binom n2/\binom k2$, hence $\limsup F_k(n)/n^2\le 1/(k(k-1))$.

Per project rules, I do not use external sources beyond these statements.

ATTACK PLAN.

• Prove the trivial pair-counting upper bound carefully (it is the main unconditional tool available from the prompt).
• For $k=3$, use the stated asymptotic to deduce the actual limit $\lim F_3(n)/n^2=\lim f_3(n)/n^2=1/6$.
• Give computational sanity checks on concrete configurations (e.g. integer grids) to understand magnitudes, though these do not claim optimality.

WORK.

Fast reality check (tiny $n$). For any $n<k$, $F_k(n)=f_k(n)=0$. For $n=k$, $F_k(k)\ge 1$ (take $k$ collinear points) and clearly $F_k(k)\le 1$, so $F_k(k)=f_k(k)=1$.

Lemma 669.1 (Exact-to-at-least relation). For every $n$ and $k$, \[ F_k(n) = \max_{|P|=n} |L_{\ge k}(P)| = \max_{|P|=n} \sum_{j\ge k} |\{\ell: |\ell\cap P|=j\}|. \] In particular, for a fixed point set $P$ one has the identity \[ |L_{\ge k}(P)| = \sum_{j\ge k} |\{\ell: |\ell\cap P|=j\}|. \]

Proof. For a fixed $P$, each line $\ell$ with $|\ell\cap P|\ge k$ has a well-defined integer $j=|\ell\cap P|\ge k$. The families $\{\ell:|\ell\cap P|=j\}$ for different $j$ are disjoint and their union over $j\ge k$ equals $L_{\ge k}(P)$. Taking cardinalities yields the displayed identity for $P$. Maximizing over $P$ preserves equality. $\square$

Lemma 669.2 (Trivial pair-counting upper bound). For all integers $n\ge k\ge 2$, \[ F_k(n) \le \frac{\binom n2}{\binom k2}. \] Consequently, \[ \limsup_{n\to\infty} \frac{F_k(n)}{n^2} \le \frac{1}{k(k-1)}. \]

Proof. Fix a set $P$ of $n$ points. Each line $\ell\in L_{\ge k}(P)$ contains at least $k$ points of $P$, hence contains at least $\binom{k}{2}$ unordered pairs of points from $P$. On the other hand, any unordered pair of distinct points of $P$ lies on exactly one line (the unique line through them), so the sets of pairs contributed by distinct lines are disjoint. Therefore the total number of unordered pairs in $P$, namely $\binom n2$, is at least the sum over $\ell\in L_{\ge k}(P)$ of $\binom{k}{2}$. That is, \[ \binom n2 \ge |L_{\ge k}(P)|\,\binom k2. \] Rearranging gives $|L_{\ge k}(P)|\le \binom n2/\binom k2$. Maximizing over $P$ yields the same bound for $F_k(n)$. Dividing by $n^2$ and taking $\limsup$ gives the stated constant upper bound. $\square$

Lemma 669.3 (Consequences for $k=3$ using the stated asymptotic). Assuming the statement in the prompt that $F_3(n)=\frac{n^2}{6}-O(n)$ and $f_3(n)=\frac{n^2}{6}-O(n)$, one has \[ \lim_{n\to\infty} \frac{F_3(n)}{n^2} = \frac16, \qquad \lim_{n\to\infty} \frac{f_3(n)}{n^2} = \frac16. \]

Proof. If $F_3(n)=\frac{n^2}{6}-O(n)$ then there is a constant $C>0$ with $|F_3(n)-n^2/6|\le Cn$ for all large $n$. Dividing by $n^2$ gives \[ \left|\frac{F_3(n)}{n^2}-\frac16\right| \le \frac{C}{n}, \] which tends to $0$ as $n\to\infty$. Therefore $F_3(n)/n^2\to 1/6$. The same argument applies to $f_3(n)$. $\square$

Computational sanity check (not claiming optimality). For an $m\times m$ integer grid $P=\{0,1,\dots,m-1\}^2$ (so $n=m^2$), I computed the number of lines containing at least $k$ grid points for small $m$. The exact counts found were:

3x3 grid (n=9):  lines with >=3 points = 8
4x4 grid (n=16): lines with >=3 points = 14, lines with >=4 points = 10
5x5 grid (n=25): lines with >=3 points = 32, lines with >=4 points = 16, lines with >=5 points = 12
6x6 grid (n=36): lines with >=3 points = 58, lines with >=4 points = 22, lines with >=5 points = 18
7x7 grid (n=49): lines with >=3 points = 108, lines with >=4 points = 44, lines with >=5 points = 24

These grow much more slowly than the quadratic upper bound from Lemma 669.2, illustrating that achieving $\Theta(n^2)$ many $k$-rich lines requires much more structured configurations than a square grid.

VERIFICATION.

• Lemma 669.2: checked that pair-sets from distinct lines are disjoint because a pair of points determines a unique line.
• For $k=3$, Lemma 669.2 gives $F_3(n)\le \binom n2/3 = \frac{n^2}{6}-\frac{n}{6}$, matching the stated asymptotic order and consistent with Lemma 669.3.
• The grid computation was rechecked by recomputing line keys via normalized integer coefficients; it is intended only as a sanity check.

FINAL. UNRESOLVED.

(i) Strongest proved partial results.

• For all fixed $k\ge 2$, $F_k(n)\le \binom n2/\binom k2$, hence $\limsup F_k(n)/n^2\le 1/(k(k-1))$ (Lemma 669.2).
• For $k=3$, using the asymptotics stated in the prompt, one gets the exact limits $\lim F_3(n)/n^2=\lim f_3(n)/n^2=1/6$ (Lemma 669.3).

(ii) First gap (crisp statement). For each fixed $k\ge 4$, determine whether the limits $\lim_{n\to\infty} F_k(n)/n^2$ and $\lim_{n\to\infty} f_k(n)/n^2$ exist, and if so compute them. In particular, decide whether the trivial upper bound constant $1/(k(k-1))$ is sharp.

(iii) Top 3 next moves.

1. Constructions: search for algebraic or finite-geometry inspired point sets in $\mathbb{R}^2$ producing $\Theta(n^2)$ many lines with exactly $k$ points for fixed $k\ge 4$.
2. Upper bounds beyond pair-counting: prove stronger restrictions on the number of $k$-rich lines using incidence geometry (e.g. inequalities relating $k$-rich lines to point-line incidences), aiming to show the constant is strictly smaller than $1/(k(k-1))$ when $k\ge 4$.
3. Computer search for small $k$: for $k=4$, do exhaustive/heuristic searches over integer/rational point sets to estimate $F_4(n)$ and guess the correct asymptotic constant.

(iv) What a minimal counterexample would likely look like. If the upper bound constant $1/(k(k-1))$ is not sharp for some $k\ge 4$, then any near-extremal configuration would have to use many lines each contributing close to the minimum $\binom{k}{2}$ pairs, with few (ideally no) lines containing more than $k$ points, because higher multiplicity lines "waste" pairs. Thus a minimal counterexample to sharpness would likely consist of a configuration where unavoidable geometric constraints force many points to lie on some lines with $>k$ points, depressing the total count of distinct $k$-rich lines below the pair-counting maximum.