on lower bounds for incidences

Overview

In Lower bounds for incidences, Cohen, Pohoata, and Zakharov prove an anchored point-line incidence theorem with a direct consequence for Heilbronn’s triangle problem (Cohen, Pohoata & Zakharov, 2024). If $p_1,\dots ,p_n\in [0,1{]}^2$ and each line ${\ell }_j$ passes through $p_j$, then some off-diagonal pair satisfies

$$d(p_j,{\ell }_k)\lesssim n^{-2/3+o(1)},j\ne k.$$

Applying this to short pairs in an arbitrary $n$-point set gives

$$\Delta (n)\le n^{-7/6+o(1)}.$$

The theorem reaches the high-low benchmark that was already visible in the homogeneous case, but it does so without assuming the original point set is evenly distributed.

🏷️ Anchored Incidences

The statement needed for Heilbronn is naturally phrased with anchored lines. Let

$$p_1,\dots ,p_n\in [0,1{]}^2,$$

and for each $j$ let ${\ell }_j$ be a line passing through $p_j$. The incidence $p_j\in {\ell }_j$ is built in. The question is whether some other point must lie close to some other anchored line.

Anchored point-line incidence

For every $\epsilon >0$, every configuration of points $p_1,\dots ,p_n\in [0,1{]}^2$ and lines ${\ell }_j\ni p_j$ contains indices $j\ne k$ such that

$$d(p_j,{\ell }_k){\lesssim }_{\epsilon }{n}^{-2/3+\epsilon }.$$

Equivalently, if each line is thickened to a tube of width

$$\delta {\gtrsim }_{\epsilon }{n}^{-2/3+\epsilon },$$

then one of the tubes contains an anchor point other than its own. The full paper proves a more general tube-incidence theorem, but this anchored corollary is the part that feeds directly into Heilbronn’s problem.

The anchoring condition is essential. Without it, one could put all points in one region and all lines in another, producing no incidences for trivial geometric reasons. Requiring $p_j\in {\ell }_j$ forces the point set and tube family to be spatially coupled.

🏷️ From Incidences to Heilbronn

Recall

$$\Delta (n)=\underset{\begin{array}{c}P\subset [0,1{]}^2\\ |P|=n\end{array}}{\sup }\underset{\{x,y,z\}\subset P}{\min }\frac{1}{2}|\det (y-x,z-x)|.$$

Start with an arbitrary set $P$ of $n$ points. Repeatedly use the pigeonhole principle to find disjoint close pairs. After removing previously selected points, any remaining set of $m$ points in the unit square contains two points at distance $O(m^{-1/2})$. Iterating until a positive proportion of the points has been paired gives

$$(p_1,p_1^{\prime }),\dots ,(p_N,p_N^{\prime }),N\asymp n,$$

with

$$|p_j-p_j^{\prime }|\lesssim n^{-1/2}.$$

Let ${\ell }_j$ be the line through $p_j$ and $p_j^{\prime }$. The anchored incidence theorem gives $j\ne k$ such that

$$d(p_j,{\ell }_k)\lesssim n^{-2/3+o(1)}.$$

The triangle with vertices $p_j,p_k,p_k^{\prime }$ then has area

$$\frac{1}{2}|p_k-p_k^{\prime }|d(p_j,{\ell }_k)\lesssim n^{-1/2}{n}^{-2/3+o(1)}=n^{-7/6+o(1)}.$$

Thus every $n$-point set in the unit square contains a triangle of area at most $n^{-7/6+o(1)}$.

Exponent bookkeeping

The short-pair scale is $n^{-1/2}$. The forced off-diagonal incidence scale is $n^{-2/3+o(1)}$. Multiplying base by height gives

$$\frac{1}{2}+\frac{2}{3}=\frac{7}{6}.$$

🏷️ Why Well-Spaced Tubes Matter

The well-spaced tube estimates of Guth, Solomon, and Wang are not simply plugged into the Heilbronn problem as a black box (Guth, Solomon & Wang, 2019). Their role is more structural: they identify the incidence scale one should expect once concentration has been removed.

A family of thin tubes is well spaced if no small spatial region and no small direction interval carries too many tubes. Under such hypotheses, point-tube incidences behave like the Szemerédi—Trotter heuristic: for about $n$ points and about $n$ tubes, one should be able to force an incidence at tube width roughly

$$n^{-2/3+o(1)}.$$

That is exactly the width needed for the Heilbronn exponent $7/6$ after multiplying by the short-pair length $n^{-1/2}$.

The difficulty is that the tubes coming from an arbitrary point set are not obviously well spaced. Many points can lie in a narrow rectangle, and many generated lines can have nearly the same direction. The new result can be viewed as a way of manufacturing the useful part of well-spacedness from the anchored structure itself: if too many anchored lines concentrate in one position-direction box, rescale that box and continue the argument at a smaller scale.

The useful analogy

Well-spaced tubes explain the target scale. Phase-space regularization explains why an arbitrary Heilbronn configuration can be reduced to that scale.

🏷️ Phase-Space Regularization

An anchored line has both position and direction. The natural phase space is therefore three-dimensional: two coordinates for the anchor point $p_j$ and one coordinate for the direction of ${\ell }_j$.

The proof analyzes concentration in anisotropic boxes. A typical phase-space box corresponds to a spatial rectangle of dimensions

$$u\times uw$$

and a direction interval of length $w$. If many particles $(p_j,{\ell }_j)$ lie in such a box, an affine rescaling turns that box into a smaller copy of the original anchored-incidence problem. This gives a self-improvement mechanism:

Rescaling principle

Excess concentration in position and direction can be blown up into a smaller anchored-incidence configuration. A minimal counterexample must therefore satisfy multiscale non-concentration estimates.

Once this regularity is extracted, the high-low incidence comparison reaches the $n^{-2/3+o(1)}$ tube width. This is why the result attains the high-low limit rather than merely improving the old exponent by a small polynomial factor.

🏷️ Updated Heilbronn Lineage

Result	Bound forced in every $n$-point set
Komlós—Pintz—Szemerédi (1981) (Komlós, Pintz & Szemerédi, 1981)	$\Delta (n)\lesssim n^{-8/7}$
Cohen—Pohoata—Zakharov (2023) (Cohen, Pohoata & Zakharov, 2023)	$\Delta (n)\le n^{-8/7-1/2000}$
Cohen—Pohoata—Zakharov (2024) (Cohen, Pohoata & Zakharov, 2024)	$\Delta (n)\le n^{-7/6+o(1)}$

The improvement from $8/7+1/2000$ to $7/6$ is substantial on the upper-bound side. It is still far from the best constructions, which give point sets with

$$\Delta (P)\gtrsim \frac{\log n}{n^2}$$

(Komlós, Pintz & Szemerédi, 1982). The new theorem should therefore be read as a sharp result for the high-low incidence framework, not as evidence that Heilbronn’s problem is close to resolved.

🏷️ Conceptual Point

The main lesson is that the right object is not just a point set or a line set. It is the anchored pair $(p,\ell )$. Once position and direction are regularized together, concentration becomes something the proof can rescale and exploit rather than something that must be discarded.

This distinction is useful beyond Heilbronn’s problem: whenever an incidence problem comes with a distinguished base point or generating point, the phase-space viewpoint may be more natural than treating the two projections separately.

🏷️ Links

• on Heilbronn triangle problem --- Background on the problem, Roth’s high-low method, and the first Cohen—Pohoata—Zakharov improvement past the KPS exponent.
• on sum-product in finite fields via entropy --- Both arguments use the principle that structured sets cannot avoid expansion across too many directions.
• on the sum-product conjecture’s falsity --- A contrast point: arithmetic structure can defeat naive expansion heuristics, so concentration has to be isolated rather than ignored.
• on Dudley’s Theorem --- The high-low comparison has the same multiscale flavor as chaining: coarse-scale information and fine-scale constraints must be reconciled.

📚 References

🐻  Cohen, A., Pohoata, C. & Zakharov, D. 2023. A new upper bound for the Heilbronn triangle problem.

🐻  Cohen, A., Pohoata, C. & Zakharov, D. 2024. Lower bounds for incidences. arXiv preprint arXiv:2409.07658.

🐻  Guth, L., Solomon, N. & Wang, H. 2019. Incidence estimates for well-spaced tubes. Geometric and Functional Analysis 29(6), 1844–1863.

🐻  Komlós, J., Pintz, J. & Szemerédi, E. 1981. On Heilbronn’s triangle problem. Journal of the London Mathematical Society 2(3), 385–396.

🐻  Komlós, J., Pintz, J. & Szemerédi, E. 1982. A lower bound for Heilbronn’s problem. Journal of the London Mathematical Society 25(1), 13–24.