we-solve (beta)

Math-5427-A2 · revision r1 · on Math-5427

gpt pro 5.2 attempt on Math-5427

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #102
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. VERIFICATION
  7. FINAL

Erdős Problem #102

FORMAL RESTATEMENT

Verbatim problem statement (from file). "Let $c>0$ and $h_c(n)$ be such that for any $n$ points in $\R^2$ such that there are $\ge cn^2$ lines each containing more than three points, there must be some line containing $h_c(n)$ many points. Estimate $h_c(n)$. Is it true that, for fixed $c>0$, we have $h_c(n)\to\infty$?"

Definitions and conventions. Fix $c>0$. For each $n\ge 1$, define $h_c(n)$ to be the smallest integer $m$ with the property:

For every point set $P\subset\R^2$ with $|P|=n$, if the number of distinct lines $\ell$ with $|\ell\cap P|\ge 4$ is at least $c n^2$, then there exists a line $\ell$ with $|\ell\cap P|\ge m$.
The question is to estimate the growth of $h_c(n)$, and in particular whether for each fixed $c>0$ one necessarily has $h_c(n)\to\infty$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

No external browsing was used. The file notes:
  • "It is not even known if $h_c(n)\ge 5$".
  • A proposed lower bound $\gg_c n^{1/2}$ was suggested at some point but is false.
  • A (higher-dimensional) grid construction, after random projection into $\R^2$, shows that $h_c(n)\ll n^{1/\log(1/c)}$.
Below I prove only elementary constraints that follow directly from double counting in $\R^2$.

ATTACK PLAN

  • Upper-bound (construction) track: Try to explicitly build planar point sets with $\ge c n^2$ rich lines but with small maximum collinearity, giving an upper bound on $h_c(n)$.
  • Lower-bound (forcing) track: From $\ge c n^2$ rich lines, use incidence counting to force a line with many points.
  • Bridge track: Relate this problem to Problem #101 about 4-point lines with no 5 collinear: if Problem #101 is true, then for any fixed $c>0$ and large $n$, the $cn^2$ rich lines cannot all be 4-point lines, so some line must contain at least 5 points.

WORK

FAST REALITY CHECK. The definition implies trivially $4\le h_c(n)\le n$ whenever the hypothesis "$\ge cn^2$ rich lines" can hold. Also, since the total number of distinct lines determined by $n$ points is at most $\binom{n}{2}$, the condition forces $c\le 1/2$. A sharper constraint appears in Lemma lem:c-upper.
Lemma (A necessary constraint on $c$): Let $P\subset\R^2$ be a set of $n$ points, and let $L_{\ge 4}(P)$ be the number of distinct lines $\ell$ with $|\ell\cap P|\ge 4$. Then \[L_{\ge 4}(P)\le \frac{\binom{n}{2}}{\binom{4}{2}}=\frac{n(n-1)}{12}. \] In particular, if $L_{\ge 4}(P)\ge c n^2$ for some fixed $c>0$ and infinitely many $n$, then necessarily $c\le 1/12$.
Proof: Each line $\ell$ with $|\ell\cap P|\ge 4$ contains at least $\binom{4}{2}=6$ distinct unordered pairs of points from $P$. Different lines contribute disjoint sets of pairs (a pair of points determines a unique line). Therefore \[6\,L_{\ge 4}(P)\le \binom{n}{2}, \] which implies the first inequality. If $L_{\ge 4}(P)\ge c n^2$ then $c n^2\le n(n-1)/12$, hence $c\le (n-1)/(12n)\to 1/12$ as $n\to\infty$. So for infinitely many $n$ we must have $c\le 1/12$. ∎
Proposition (Many rich lines force a point on linearly many rich lines): Let $P\subset\R^2$ have $n$ points and let $L_{\ge 4}(P)$ be as above. Let $I$ be the number of incidences between points of $P$ and rich lines (lines meeting $P$ in at least 4 points): \[I=\sum_{\ell:\ |\ell\cap P|\ge 4} |\ell\cap P|. \] Then $I\ge 4\,L_{\ge 4}(P)$. In particular, if $L_{\ge 4}(P)\ge c n^2$ then there exists a point $p\in P$ that lies on at least $4c n$ rich lines.
Proof: Every rich line contains at least 4 points of $P$, so summing $|\ell\cap P|$ over rich lines gives $I\ge 4 L_{\ge 4}(P)$. Now write $I$ also as a sum over points: \[I=\sum_{p\in P} r(p),\] where $r(p)$ is the number of rich lines containing $p$. Thus the average value of $r(p)$ over $p\in P$ is $I/n$. If $L_{\ge 4}(P)\ge c n^2$, then $I\ge 4c n^2$, so average $r(p)\ge 4c n$. Hence there exists $p$ with $r(p)\ge 4c n$. ∎
Corollary (A second derivation of $c\le 1/12$): If $L_{\ge 4}(P)\ge c n^2$ then necessarily $c\le (n-1)/(12n)$.
Proof: From the proposition, there is a point $p\in P$ on $r(p)\ge 4c n$ rich lines. Distinct lines through $p$ intersect only at $p$. Since each such line contains at least 3 additional points besides $p$, the union of these $r(p)$ lines contains at least $1+3r(p)$ distinct points. Therefore $1+3r(p)\le n$, so $r(p)\le (n-1)/3$. Combine with $r(p)\ge 4c n$ to get $4c n\le (n-1)/3$, i.e. $c\le (n-1)/(12n)$. ∎

VERIFICATION

  • All arguments are purely combinatorial and use only basic geometry facts: (i) a pair of points determines a unique line, (ii) two distinct lines through the same point intersect only at that point.
  • The proposition does not by itself force a line with many points; it forces a point on many rich lines, which is much weaker than the desired conclusion $h_c(n)\to\infty$.

FINAL

UNRESOLVED.
  1. Strongest proved partial result here: If a set of $n$ points determines at least $c n^2$ lines with $\ge 4$ points, then necessarily $c\le 1/12$ (Lemma lem:c-upper), and some point lies on at least $4c n$ such rich lines (Proposition).
  2. First gap (crisp): Prove (or disprove) that for each fixed $c\in(0,1/12]$, one must have $h_c(n)\to\infty$ as $n\to\infty$.
  3. Top 3 next moves (concrete):
    1. Attempt to show a strengthening of the "many rich lines through one point" conclusion: e.g. from $r(p)\gg n$ rich lines through $p$, force a line with $\gg \log n$ points by repeated intersection/energy arguments.
    2. Build explicit planar constructions with $L_{\ge 4}(P)\ge c n^2$ for some absolute $c>0$ and with bounded collinearity (to disprove $h_c(n)\to\infty$).
    3. Explore whether polynomial partitioning or incidence geometry can give a dichotomy: either many 4-point lines (relating to Problem #101) or existence of a 5-point (or larger) line.
  4. What a minimal counterexample would likely look like: Fix $c>0$ and construct arbitrarily large $n$ point sets $P_n$ with $L_{\ge 4}(P_n)\ge c n^2$ but with a uniform bound $\max_{\ell}|\ell\cap P_n|\le M$ for some constant $M$ (or slowly growing $M$). Such a counterexample would behave like a geometric realization of a dense block design with small block size.