Erdoes #669 - working report - Erdős Problem a Day

Erdős problem #669 — wave w046

Access/research date: 2026-07-31 UTC Standalone checker: runs/erdos669_wavew046_reverify.py

Outcome

This does not determine either requested limit for $k\ge 4$. It does give three verifiable pieces of progress:

[A: elementary-rigorous] Projective duality and a from-scratch proof of

Melchior's inequality improve the live page's pair-count bound to \[ \limsup_{n\to\infty}\frac{F_k(n)}{n^2} \leq \frac1{(k+3)(k-2)}\qquad(k\geq4). \]

[B: rigorous modulo the named Bojanowski inequality] For $k\geq6$

this improves further to \[ \limsup_{n\to\infty}\frac{F_k(n)}{n^2} \leq \frac{2}{3k(k-2)}. \] The same bounds hold for $f_k$.

[A: elementary-rigorous] A $k\times m$ integer rectangle has an exact

closed form for both relevant line counts. After generic padding, for every fixed $k\geq3$, \[ \liminf_{n\to\infty}\frac{f_k(n)}{n^2} \geq \frac1{k^2(k-1)}. \] This is the rectangular construction already suggested (without its exact count) in Erdős's original source.

Here and below the labels required by the task mean:

[A] elementary-rigorous;
[B] rigorous modulo an explicitly named theorem;
[C] plausible/structural-unverified;
[D] computational-only.

Step 0: authoritative live-page check

[D: direct page observation] I fetched <https://www.erdosproblems.com/669> through the Bright Data browser path, not datacenter curl. The live page said:

status: OPEN;
0 comments;
0 claimed proofs;
“Interested in collaborating”: None;
“Currently working on this problem”: None;
last edited 27 December 2025.

Thus the mandatory no-collision gate passed.

Verbatim live statement

Let $F_k(n)$ be minimal such that for any $n$ points in $\mathbb{R}^2$ there exist at most $F_k(n)$ many distinct lines passing through at least $k$ of the points, and $f_k(n)$ similarly but with lines passing through exactly $k$ points.
Estimate $f_k(n)$ and $F_k(n)$ - in particular, determine $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$.

Verbatim live-page known results

Trivially $f_k(n)\leq F_k(n)$ and $f_2(n)=F_2(n)=\binom{n}{2}$. The problem with $k=3$ is the classical 'Orchard problem' of Sylvester. Burr, Gr\"{u}nbaum, and Sloane \cite{BGS74} have proved that\[f_3(n)=\frac{n^2}{6}-O(n)\]and\[F_3(n)=\frac{n^2}{6}-O(n).\]There is a trivial upper bound of $F_k(n) \leq \binom{n}{2}/\binom{k}{2}$, and hence\[\lim F_k(n)/n^2 \leq \frac{1}{k(k-1)}.\]See also [101].

The sole bibliography entry exposed in the LaTeX view was:

[BGS74] Burr, Stefan A. and Gr\"{u}nbaum, Branko and Sloane, N. J. A., The orchard problem. Geometriae Dedicata (1974), 397-424.

The problem citation shown after opening the page's bibliography widget was: Paul Erdős, Some unsolved problems, in Combinatorics, Geometry and Probability (1997), pp. 1–10, MR 1476428.

The linked problem #101 currently lists rubicon as a current worker. I used that page only to locate its already-published Solymosi–Stojaković reference; I did not attempt its different, no-five-collinear conjecture.

Notation

For a particular $n$-point set $P$, let

t_r(P)=\#\{\ell:|\ell\cap P|=r\}.

Then

f_k(n)=\max_{|P|=n}t_k(P),\qquad F_k(n)=\max_{|P|=n}\sum_{r\geq k}t_r(P).

The “minimal universal upper bound” wording on the page is equivalent to these maxima because only finitely many pair-incidence patterns can occur.

Every pair of points determines one line, so

\tag{1}\binom n2=\sum_{r\geq2}\binom r2t_r(P).

1. Elementary upper bound from Melchior

1.1 A self-contained proof of the needed inequality

[A] Dualize the $n$ points of a non-collinear $P$ to $n$ lines in the real projective plane. A line containing exactly $r$ original points becomes a vertex where exactly $r$ dual lines meet, so the same $t_r$'s count the dual intersection multiplicities.

Let $V,E,R$ be the numbers of vertices, edges, and regions in this projective line arrangement. Then

V=\sum_{r\geq2}t_r,\qquad E=\sum_{r\geq2}r\,t_r.

Indeed, a projective line is a circle; if it contains $s$ vertices, they cut it into $s$ edges. Euler's relation for $\mathbb{RP}^2$ is

\[ V-E+R=1. \]

Every region has at least three boundary edges and every edge borders two regions, so $3R\leq2E$. Consequently

1=V-E+R\leq V-\frac E3,

\sum_{r\geq2}(r-3)t_r\leq-3.

Equivalently,

\tag{2}t_2\geq3+\sum_{r\geq4}(r-3)t_r.

This is Melchior's inequality, derived here rather than assumed.

1.2 Consequence for $F_k$

[A] Insert (2) into the pair identity (1):

\begin{aligned} \binom n2 &=t_2+3t_3+\sum_{r\geq4}\binom r2t_r\\ &\geq3+3t_3+ \sum_{r\geq4}\left(\binom r2+r-3\right)t_r. \end{aligned}

For $r\geq4$, the weight

w_r:=\binom r2+r-3=\frac{(r+3)(r-2)}2

is strictly increasing. Therefore, for every $k\geq4$,

\tag{3} F_k(P)\leq \frac{\binom n2-3}{w_k} =\frac{n(n-1)-6}{(k+3)(k-2)}

whenever $P$ is non-collinear. If $P$ is collinear, $F_k(P)\leq1$, so including a harmless maximum with 1 makes (3) valid for all finite edge cases. It follows that

\tag{4} \boxed{\displaystyle \limsup_{n\to\infty}\frac{F_k(n)}{n^2} \leq\frac1{(k+3)(k-2)}}\qquad(k\geq4).

Since $f_k(n)\leq F_k(n)$, (4) also bounds $f_k$.

This strictly improves the page's $1/[k(k-1)]$, because

\[ (k+3)(k-2)-k(k-1)=2(k-3)>0. \]

2. Stronger upper bound from Bojanowski's inequality

2.1 Named input

[B] Bojanowski's line-arrangement inequality, in the dual point-set form stated as Theorem 2.1 of Pokora (2019), says:

If no line contains at least $2n/3$ of the $n$ points, then \[ > \tag{5} > t_2+\frac34t_3\geq > n+\sum_{r\geq5}\left(\frac{r^2}{4}-r\right)t_r. > \]

This theorem is proved through the orbifold Bogomolov–Miyaoka–Yau inequality, so the result below is not classified as elementary. Real arrangements are a special case of the theorem over $\mathbb C$.

2.2 Light-line case

[B] Combining (5) with (1) gives

\binom n2 \geq n+\frac94t_3+6t_4+ \sum_{r\geq5} \left[\binom r2+\frac{r^2}{4}-r\right]t_r.

The bracket is

\tag{6} w'_r=\frac{3r(r-2)}4,

which increases with $r$. Hence, for $k\geq5$,

\tag{7} F_k(P)\leq \frac{4(\binom n2-n)}{3k(k-2)} =\frac{2n(n-3)}{3k(k-2)}

in the light-line case.

2.3 Heavy-line case, from scratch

[A] Suppose instead that one line $L$ contains $h\geq2n/3$ points, and put $m=n-h\leq n/3$. Every other $k$-rich line meets $L$ in at most one point and therefore contains at least $k-1$ of the $m$ off-line points. Different such lines use disjoint pairs of off-line points. Thus

\tag{8} F_k(P)\leq1+\frac{\binom m2}{\binom{k-1}{2}},

and consequently

\tag{9} \limsup\frac{F_k(P)}{n^2} \leq\frac1{9(k-1)(k-2)}.

For every $k\geq5$, the constant in (9) is no larger than the constant $2/[3k(k-2)]$ from (7). Thus the two cases combine without losing the light-case bound.

2.4 Best combined upper constants

[B] Taking the better of Melchior (4) and Bojanowski (7) gives

\tag{10} \boxed{ U_k:= \begin{cases} \dfrac1{14},&k=4,\\[4pt] \dfrac1{24},&k=5,\\[4pt] \dfrac{2}{3k(k-2)},&k\geq6, \end{cases} \qquad \limsup_{n\to\infty}\frac{F_k(n)}{n^2}\leq U_k.}

At $k=6$, the two methods both give $1/36$. Again, the same upper bound applies to $f_k$.

The exact arithmetic is independently recomputed in the checker. For the first few values:

| $k$ | page pair bound | Melchior | Bojanowski | best $U_k$ | |---:|---:|---:|---:|---:| | 4 | $1/12$ | $1/14$ | not used | $1/14$ | | 5 | $1/20$ | $1/24$ | $2/45$ | $1/24$ | | 6 | $1/30$ | $1/36$ | $1/36$ | $1/36$ | | 7 | $1/42$ | $1/50$ | $2/105$ | $2/105$ | | 8 | $1/56$ | $1/66$ | $1/72$ | $1/72$ |

3. Exact rectangular construction and uniform lower bound

Fix $k\geq3$, choose $m>k$, and take

\tag{11} P_{k,m}=\{0,1,\ldots,k-1\}\times\{0,1,\ldots,m-1\}.

3.1 Closed form

[A] A nonvertical line contains at most one point in each of the $k$ columns. It has exactly $k$ grid points if and only if it meets every column. If its left and right endpoint heights are $u,v\in\{0,\ldots,m-1\}$, this happens exactly when

u\equiv v\pmod{k-1}.

The intermediate heights are then the integral linear interpolation between $u$ and $v$, and remain in the allowed interval.

Write

\tag{12}m=q(k-1)+s,\qquad0\leq s<k-1.

There are $s$ residue classes of size $q+1$ and $k-1-s$ of size $q$. Therefore the number of nonvertical $k$-point lines is exactly

\begin{aligned} \tag{13} Q_k(m) &=s(q+1)^2+(k-1-s)q^2\\ &=\frac{m^2+s(k-1-s)}{k-1}. \end{aligned}

The $k$ vertical lines have $m>k$ points, so they are counted by $F_k$ but not $f_k$. There are no other $k$-rich lines. Hence this particular configuration satisfies the exact identities

\tag{14} t_k(P_{k,m})=Q_k(m),\qquad \sum_{r\geq k}t_r(P_{k,m})=Q_k(m)+k.

3.2 Padding to every sufficiently large $n$

[A] Given any finite point set, a new point can be chosen outside the finite union of all lines determined by its pairs. Repeating this operation does not add a point to any old line and never creates a new line containing three points. Thus all $t_r$ with $r\geq3$ are preserved.

For arbitrary $n\geq k(k+1)$, take

m=\left\lfloor\frac nk\right\rfloor>k,

use $P_{k,m}$, and pad by the remaining $n-km<k$ generic points. Equations (13)–(14) give

\tag{15} f_k(n)\geq Q_k(m)\geq\frac{m^2}{k-1} \geq\frac{(n/k-1)^2}{k-1}.

Therefore

\tag{16} \boxed{\displaystyle \liminf_{n\to\infty}\frac{f_k(n)}{n^2} \geq\frac1{k^2(k-1)}}

and the same lower bound holds for $F_k$.

3.3 Exact general rectangle formula

[A] There is also an exact formula for every

R_{W,H}=\{0,\ldots,W-1\}\times\{0,\ldots,H-1\}.

For a primitive nonvertical direction $(a,b)$, with $a>0$, put

A_j(a,b)=[W-ja]_+[H-j|b|]_+,\qquad[x]_+=\max(x,0).

A line containing $r$ grid points contributes $r-k+1$ length-$k$ consecutive segments and $r-k$ length-$(k+1)$ segments. It follows that the number of lines in this direction containing at least $k$ points is

A_{k-1}-A_k,

and the number containing exactly $k$ is

A_{k-1}-2A_k+A_{k+1}.

Summing over

1\leq a<W,\quad -(H-1)\leq b\leq H-1,\quad\gcd(a,|b|)=1

and adding the $W$ vertical lines when appropriate gives exact $f_k$ and $F_k$ for the rectangle. The checker implements this formula independently of its pair-based brute-force counter.

4. Combined verified interval

[A+B] For each fixed $k\geq4$, without assuming either limit exists,

\tag{17} \boxed{\displaystyle \frac1{k^2(k-1)} \leq\liminf_{n\to\infty}\frac{f_k(n)}{n^2} \leq\limsup_{n\to\infty}\frac{f_k(n)}{n^2} \leq\limsup_{n\to\infty}\frac{F_k(n)}{n^2} \leq U_k,}

where $U_k$ is (10). In particular:

| $k$ | verified lower constant | verified upper constant | |---:|---:|---:| | 4 | $1/48$ | $1/14$ | | 5 | $1/100$ | $1/24$ | | 6 | $1/180$ | $1/36$ | | 7 | $1/294$ | $2/105$ | | 8 | $1/448$ | $1/72$ |

No equality between a liminf and limsup has been inferred.

5. Independent computation

[D] The standalone checker uses only Python's standard library. It does not trust formula (13): it enumerates every pair of integer points, normalizes the line $Ax+By+C=0$, and infers a line's multiplicity from the number $\binom r2$ of pairs producing that normalized line.

Run:

python runs/erdos669_wavew046_reverify.py

Observed output:

PASS exact rectangle direction formula: 250 (W,H,k) cases
PASS thin-grid closed form and rich-line counts: 74 grids
  k    m    n    exact-k    at-least-k
  4    5   20          9            13
  4    8   32         22            26
  4   20   80        134           138
  4  101  404       3401          3405
  5   11   55         31            36
  6   13   78         35            41
PASS generic padding: 4x20 grid padded from 80 to 83 points
  k      lower       Melchior     Bojanowski   best named upper
  4        1/48            1/14               -               1/14
  5       1/100            1/24            2/45               1/24
  6       1/180            1/36            1/36               1/36
  7       1/294            1/50           2/105              2/105
  8       1/448            1/66            1/72               1/72
  9       1/648            1/84           2/189              2/189
 10       1/900           1/104           1/120              1/120
 11      1/1210           1/126           2/297              2/297
 12      1/1584           1/150           1/180              1/180
PASS upper-bound coefficient identities and branch comparisons
ALL CHECKS PASSED

The 250-case test compares two independently implemented methods: the primitive-direction formula and the normalized-line pair enumeration. The generic-padding test constructs integer points on a parabola, rejecting every candidate on any currently determined line, and then recounts all multiplicities.

6. Primary-source literature audit

[B: source verified] Erdős's original chapter is

Some Unsolved Problems, pp. 1–10 in Combinatorics, Geometry and Probability (1997). Problem 16 defines these same $F_k,f_k$, asks whether the limits exist, explicitly mentions the $k\times(n/k)$ rectangle as a lower bound, and asks whether lattice points attain the limits. This confirms that the broad rectangular construction is known; (13)–(16) supply its exact count and uniform padding.

[B: source verified] Burr, Grünbaum, and Sloane,

The Orchard Problem, Geometriae Dedicata 2 (1974), 397–424, proves the stated $n^2/6-O(n)$ behavior for $k=3$.

[B: source verified] Green and Tao,

arXiv:1208.4714, Theorem 1.3, later sharpened the exact-$3$ result for all sufficiently large $n$ to \[ f_3(n)=\left\lfloor\frac{n(n-3)}6\right\rfloor+1. \] This updates the $k=3$ literature but does not settle $k\geq4$.

[B: source verified] Szemerédi and Trotter,

Extremal Problems in Discrete Geometry, Combinatorica 3 (1983), 381–392, prove that the number of $k$-rich lines is \[ O\!\left(\frac{n^2}{k^3}+\frac nk\right). \] Together with the rectangle, this fixes the order $1/k^3$ of the normalized extremal constant up to an absolute factor as $k$ varies, but gives neither the exact constants nor limit existence.

[B: source verified] Solymosi and Stojaković,

arXiv:1107.0327, DOI 10.1007/s00454-013-9526-9, prove that for fixed $k>3$ there are $n$-point sets with no $(k+1)$-point line and at least \[ n^{\,2-c(k)/\sqrt{\log n}} \] exact $k$-point lines. This is the key current lower bound for the more restrictive linked problem. Its normalization by $n^2$ still tends to zero, while construction (11) has $m$-point vertical lines and therefore does not satisfy that restriction.

[B: source verified] Pokora,

Extremal Properties of Line Arrangements in the Complex Projective Plane, Analytic and Algebraic Geometry 3 (2019), 191–200, states the exact Bojanowski inequality used in (5), both in line-arrangement form (Theorem 1.1) and dual point-set form (Theorem 2.1). Pokora identifies the original source as Radosław Bojanowski's 2003 master's thesis, Zastosowania uogólnionej nierówności Bogomolova–Miyaoka–Yau.

[A: source and proof verified] Melchior's original result is E. Melchior,

Über Vielseite der projektiven Ebene, Deutsche Mathematik 5 (1941), 461–475. No dependency on that paper is needed here because §1.1 proves the precise inequality from Euler's formula.

[C: search limitation] Exact-function searches, the original source and its bibliography, the directly relevant cited papers, and citation-index checks did not reveal a paper resolving the constants or existence of the limits for $k\geq4$. This is an honest search miss, not a proof that no such paper exists. I also found no primary source explicitly recording the combined upper constants (10), so I do not claim they are new.

7. Exact remaining wall

[A] The numerical gap is real. For example,

\[ \frac1{48}\leq \liminf\frac{f_4(n)}{n^2} \leq\limsup\frac{F_4(n)}{n^2} \leq\frac1{14}. \] Neither argument identifies the true constant.

[A] The pair identity plus Melchior alone cannot improve (4) as a

linear-programming relaxation: formally putting $t_2=(k-3)T$ and $t_k=T$, with other $t_r=0$, saturates its leading coefficient. Likewise, the Bojanowski relaxation is saturated at the coefficient $3k(k-2)/4$.

[C] Those formal multiplicity vectors need not be realizable by real

line arrangements. The missing geometric input is therefore a stability/realizability lemma forcing additional low-multiplicity intersections when $t_k=\Theta(n^2)$, beyond Melchior/Bojanowski.

[C] Even existence of the normalized limits needs an amplification or

interpolation theorem. Monotonicity under generic padding is insufficient: a monotone $O(n^2)$ sequence can still have oscillating normalized values. A sufficient missing lemma would be a density-preserving geometric blow-up taking an $N$-point incidence pattern to $qN+o(q)$ points and $q^2-o(q^2)$ copies of each relevant rich line. Such blow-ups amount to simultaneously realizing many finite nets, and no such lemma was found.

[D] Brute-force enumeration of more finite rectangles will not supply

that uniformity step. A global search would have to enumerate and test realizability of rank-3 incidence structures/oriented matroids, whose search space grows superexponentially; no few-CPU-minute computation on this VM can plausibly settle the asymptotic question. I therefore did not launch a heavy search.

PARTIAL: proved a strict Melchior/Bojanowski upper-bound improvement, exact grid formulas with a checker, and uniform lower bounds; the constants and limit existence for k>=4 remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger