Erdős Problem #101

Erdős Problem 101: four-point lines with no five collinear

1. Statement and scope

Suppose $P$ is a set of $n$ real planar points, no five on one line. Is the number of four-point lines $o(n^2)$? This remains unresolved. We prove the bound \[ t_4\le\frac{n(n-1)-6}{14}\qquad(n\ge5),\tag{1} \] where $t_r$ denotes the number of lines containing exactly $r$ points of $P$. The improvement over direct pair counting comes from the real-projective-plane Euler argument usually called Melchior's inequality. We give that argument rather than treating it as an unexplained input. A simple construction is also supplied, without claiming to match the much stronger known lower bounds.

2. Pair counting and the real-plane constraint

Every pair of distinct points lies on exactly one line. Because there are no five collinear, \[ t_2+3t_3+6t_4=\binom n2.\tag{2} \] For $n\ge5$, the points are not all collinear. Dualize their projective completions to an arrangement of $n$ distinct projective lines, not all concurrent. A vertex where exactly $r$ dual lines meet corresponds to an $r$-point line of the original set, so the arrangement has \[ V=\sum_{r\ge2}t_r,\qquad E=\sum_{r\ge2}r t_r. \] Here each arrangement line is a projective circle cut into as many edges as it has vertices; equivalently, each vertex has degree $2r$ and every edge has two ends. The arrangement gives a cellular decomposition of the real projective plane, whose Euler characteristic is one. Thus $F=1-V+E$.

Every face has at least three edge occurrences on its boundary. There are no one-sided polygon boundaries in the edge-counting sense: such a boundary would require a line with only one intersection vertex, making the whole arrangement concurrent. A two-edge boundary would require two distinct projective lines to meet at two distinct vertices, which is impossible. The nonconcurrent line arrangement has disk faces, as can also be seen by lifting to the sphere and cutting by great circles. Counting face-edge incidences, with both sides of every edge counted, therefore gives $3F\le2E$. Substituting Euler's relation yields \[ 3\le3V-E=\sum_{r\ge2}(3-r)t_r, \quad\text{or}\quad t_2\ge3+\sum_{r\ge4}(r-3)t_r.\tag{3} \] In our case this is $t_2\ge t_4+3$. Combining it with $2$ gives \[ 7t_4+3t_3\le\binom n2-3, \] which proves $1$. The use of real projective geometry is essential in this argument; the same face count is not available for arbitrary abstract incidence systems.

3. A completely controlled lower construction

For every $n$ there is a configuration with no five collinear and at least $\lfloor n/4\rfloor$ four-point lines. Construct successive groups of four points as follows. Choose a new line avoiding all previously chosen points. On it choose four distinct new points, each avoiding the finitely many lines determined by pairs of old points. Such choices exist because the new line is different from all those old pair-lines and meets each in at most one forbidden point.

The new group supplies its own four-point line. A different line contains at most one new point, since two new points already determine the new group line. If it contains a new point and two old ones, that new point would lie on a forbidden old pair-line. Hence no other line gains a third point and no previous four-point line gains a fifth. Repeat for $\lfloor n/4\rfloor$ groups, then add any remaining points one at a time off all lines determined by existing pairs. This preserves every asserted property.

This linear lower bound is merely an explicit checked example. It is far below the known constructions approaching quadratic size cited on the problem page, and no improvement over those constructions is asserted.

4. What the bound does not provide

Inequality $1$ improves the constant in the elementary quadratic upper bound but leaves a positive constant multiplying $n^2$. It therefore does not establish the required little-$o$ estimate. To finish the problem, one must show that $t_4/n^2$ tends to zero uniformly over the permitted configurations, or construct a sequence for which it stays bounded away from zero. Neither conclusion follows from $2$--$3$.

Source: https://www.erdosproblems.com/101. The proof of $3$ is the classical Melchior argument, reconstructed above using the Euler formula for the real projective plane. No stronger incidence theorem is assumed.

Completion rate estimate: 25%.

Erdős Problem #101

FORMAL RESTATEMENT

Verbatim problem statement (from file). "Given $n$ points in $\R^2$, no five of which are on a line, the number of lines containing four points is $o(n^2)$."

Definitions and conventions. Let $P\subset\R^2$ with $|P|=n$. Assume: \[\text{(No-5-collinear)}\qquad \text{every line in }\R^2\text{ contains at most 4 points of }P. \] Let $L_4(P)$ be the number of distinct (geometric) lines $\ell$ such that $|\ell\cap P|=4$. (The "no five collinear" hypothesis implies "containing four points" is the same as "containing at least four points".)

Claim to prove (asymptotic). \[\frac{L_4(P)}{n^2}\to 0\quad\text{as }n\to\infty,\] uniformly over all such $P$. Equivalently: for every $\varepsilon>0$ there exists $N(\varepsilon)$ such that if $n\ge N(\varepsilon)$ then $L_4(P)\le \varepsilon n^2$.

QUICK LITERATURE/CONTEXT CHECK

No external browsing was used. The file states that there are constructions with $L_4(P)\ge n^{2-O(1/\sqrt{\log n})}$, so any $o(n^2)$ upper bound would have to be very close to sharp. I do not attempt to reproduce those constructions.

ATTACK PLAN

• Upper bound track: Use double counting (pairs, incidences) and possibly the Szemerédi--Trotter theorem to bound the number of 4-rich lines.
• Reduction track: Relate 4-point lines to counts of collinear triples or to rich-line incidence graphs.
• Disproof track: Try to construct a configuration with $\Theta(n^2)$ many 4-point lines while keeping no five collinear; this would disprove the conjectured $o(n^2)$ bound.

WORK

FAST REALITY CHECK (very small $n$).

• $n\le 3$: $L_4(P)=0$.
• $n=4$: if all 4 points are collinear then $L_4(P)=1$; if not, $L_4(P)=0$.
• $n=5$: one can have $L_4(P)=1$ (four collinear, fifth off the line).
• $n=7$: one can realize $L_4(P)=2$ by taking two 4-point lines meeting in one point (uses $1+3+3=7$ points).

VERIFICATION

• The pair-counting lemma is a direct double count of unordered point pairs on 4-point lines; it uses only that distinct point pairs determine unique lines.
• The proposition bounds the number of 4-point lines through a fixed point by noting that distinct lines through that point use disjoint sets of the remaining points; no external theorems are invoked.
• Both bounds are $\Theta(n^2)$, so they do not approach the conjectured $o(n^2)$; they are consistent with the near-quadratic constructions mentioned in the file.

FINAL

UNRESOLVED.

1. Strongest proved partial result here: For any such $P$, $L_4(P)\le n(n-1)/12$ by pair counting.
2. First gap (crisp): Prove that for every $\varepsilon>0$ and all sufficiently large $n$, every $n$-point set in $\R^2$ with no five collinear has $L_4(P)\le \varepsilon n^2$.
3. Top 3 next moves (concrete):
   1. Try to strengthen Szemerédi--Trotter-type bounds using the additional constraint "no five collinear" to get a saving over the trivial $\Theta(n^2)$.
   2. Convert 4-point lines into a 4-uniform hypergraph on $P$ (edges = 4-tuples on a line) and attempt to exploit geometric restrictions to bound the number of edges.
   3. Computational experiment: for moderate $n$ (say $n\le 50$), search over known high-incidence constructions (grids, projected grids, algebraic curves) and measure $L_4(P)/n^2$ to see decay rates.
4. What a minimal counterexample would likely look like: A family $P_n$ with no five collinear and with $L_4(P_n)\ge c n^2$ for some fixed $c>0$ (i.e. a positive density of all $\binom{n}{2}$ pairs lie in 4-point lines). Such a configuration would resemble a near-Steiner system of 4-point lines geometrically realizable in $\R^2$.