on Heilbronn triangle problem

Overview

Heilbronn’s triangle problem asks how large the smallest triangle area can be among $n$ points in the unit square. The classical exponent $8/7$ of Komlós, Pintz, and Szemerédi stood for more than forty years, until Cohen, Pohoata, and Zakharov proved the polynomial improvement

$$\Delta (n)\le n^{-8/7-1/2000}$$

for all sufficiently large $n$ (Cohen, Pohoata & Zakharov, 2023). The proof turns the absence of small triangles into an incidence problem between points and thin strips, then uses projection theory and discretized sum-product input to push Roth’s high-low method below the old barrier.

A subsequent incidence theorem by the same authors reaches the high-low benchmark

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

by proving a nearly sharp anchored point-line incidence theorem (Cohen, Pohoata & Zakharov, 2024). See on lower bounds for incidences.

🏷️ The Quantity Being Optimized

For three points $x,y,z\in {\mathbb{R}}^2$, write

$$A(x,y,z)=\frac{1}{2}\left|\det (y-x,z-x)\right|$$

for the area of the triangle they span. For a finite set $P\subset [0,1{]}^2$, define

$$\Delta (P)=\underset{\{x,y,z\}\subset P}{\min }A(x,y,z),$$

with the convention that a collinear triple has area $0$. The extremal function is

$$\Delta (n)=\underset{\begin{array}{c}P\subset [0,1{]}^2\\ |P|=n\end{array}}{\sup }\Delta (P).$$

Thus an upper bound on $\Delta (n)$ says that every $n$-point configuration contains a small triangle, while a lower bound constructs a configuration in which all triangles are relatively large.

Elementary scale checks

The pigeonhole upper bound is $\Delta (n)=O(n^{-1})$. If the points are not all collinear, triangulate their convex hull using the points of $P$ as vertices. The triangulation has at least $n-2$ triangles and total area at most $1$, so one triangle has area at most $1/(n-2)$.

The elementary lower bound is $\Delta (n)=\Omega (n^{-2})$. Erdős’s parabola construction takes lattice points

$$\left(\frac{i}{p},\frac{i^2\mathrm{mod}p}{p}\right)$$

over a prime $p\asymp n$. No three of these points are collinear modulo $p$, and every nonzero lattice triangle in the dilated grid has area at least $1/(2p^2)$.

Heilbronn originally conjectured the upper bound $\Delta (n)=O(n^{-2})$, which would have matched the parabola construction up to constants. Komlós, Pintz, and Szemerédi disproved this by constructing point sets with

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

for an absolute constant $c>0$ (Komlós, Pintz & Szemerédi, 1982). The modern target is therefore closer to $n^{-2+o(1)}$ than to a literal $n^{-2}$ theorem.

🏷️ The Upper-Bound Lineage

The upper-bound side asks for a mechanism that forces three points to be almost collinear at a very fine scale. The progression is:

Result	Bound forced in every $n$-point set
Trivial triangulation	$\Delta (n)\lesssim n^{-1}$
Roth (1951) (Roth, 1951)	$\Delta (n)\lesssim n^{-1}(\log \log n{)}^{-1/2}$
Schmidt (1972) (Schmidt, 1972)	$\Delta (n)\lesssim n^{-1}(\log n{)}^{-1/2}$
Roth’s analytic method (1972) (Roth, 1972)	$\Delta (n)⪅n^{-1-\mu }$, $\mu =(9-\sqrt{65})/8$
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 first post-KPS gain was numerically small, but it was structurally important: the $8/7$ exponent was not a hard endpoint of the incidence method. The later anchored-incidence theorem reaches the natural high-low benchmark $7/6$.

🏷️ Why Strips Appear

Fix two points $x,y\in P$ and let ${\ell }_{xy}$ be the line through them. For any third point $z$,

$$A(x,y,z)=\frac{1}{2}|x-y|\mathrm{dist}(z,{\ell }_{xy}).$$

Consequently, if $P$ has no triangle of area at most $\delta$, then for every pair $x,y\in P$ the strip around ${\ell }_{xy}$ of total width comparable to $\delta /|x-y|$ contains no point of $P\setminus \{x,y\}$. This is the basic dictionary:

Triangle areas as forbidden incidences

Let $L$ be a family of lines generated by pairs of points of $P$ with pair length at most $u$. If a strip of width $w$ around some $\ell \in L$ contains a third point of $P$, then the corresponding triangle has area $\lesssim uw$.

Therefore, to prove $\Delta (P)\lesssim uw$, it is enough to prove that incidences between $P$ and the $w$-neighborhoods of lines in $L$ cannot all be avoided.

This rephrasing explains why the problem is not merely about placing points far apart. A configuration with large $\Delta (P)$ must make many naturally generated strips unusually empty at the precise scales where random-looking point sets would have incidences.

🏷️ Roth’s High-Low Mechanism

Roth’s analytic method compares incidences at two different widths. At a coarse width $w_i$, strips around many generated lines should see roughly the expected number of points. At a much finer width $w_f$, the no-small-triangle hypothesis says that the same strips have unexpectedly few incidences. The method proves that these two behaviors cannot coexist once the scale gap is too large.

One modern way to phrase the method is to smooth the strip indicator at two widths and study a difference function. Quasi-orthogonality, via a Selberg-type inequality, controls the aggregate square function over the line family. The high scale supplies mass, while the low scale is constrained by the forbidden-triangle condition.

High-low incidence philosophy

The proof does not try to locate the small triangle directly. It assumes that no such triangle exists, translates this into a low-scale incidence deficit, and then proves that the deficit contradicts a high-scale lower bound. Guth, Solomon, and Wang’s work on well-spaced tubes is a useful modern model for this kind of multi-scale incidence comparison (Guth, Solomon & Wang, 2019).

The obstruction is concentration. If many points lie in a narrow region, or if many generated lines have nearly the same direction, the initial high-scale incidence estimate may be too weak. Much of the technical work in the Heilbronn problem is devoted to separating this concentration from genuine pseudorandomness.

🏷️ Breaking the KPS Barrier

Cohen, Pohoata, and Zakharov kept the strip-incidence strategy but replaced part of the old initial estimate with a projection-theoretic argument. The relevant local picture is this: partition the unit square into $u\times u$ cells, look at points of $P$ inside one cell, and study the directions determined by local pairs. If those directions spread, the associated strips produce many incidences. If they do not spread, the point set has geometric structure that can be exploited separately.

The new ingredient is a discretized radial projection theorem of Orponen, Shmerkin, and Wang (Orponen, Shmerkin & Wang, 2022). In the background is the same expansion principle that appears in discretized sum-product theory: a set cannot be simultaneously too structured in all projected directions unless it has a strong algebraic or geometric reason.

Cohen--Pohoata--Zakharov

For all sufficiently large $n$, every set of $n$ points in $[0,1{]}^2$ contains three points spanning a triangle of area at most

$$n^{-8/7-1/2000}.$$

The proof can be read as a self-improvement scheme. Starting from the KPS exponent, the authors analyze a candidate extremal configuration at scale $u$. If the local direction sets behave well, projection theory strengthens the incidence lower bound and forces a smaller triangle. If the local geometry is concentrated, the configuration can be rescaled inside a rectangle and the already-known exponent can be applied inductively. Balancing these alternatives produces the extra $1/2000$ in the exponent.

🏷️ Homogeneous Sets and the Natural Benchmark

The same work also proves a stronger statement under a spacing hypothesis. A set $P\subset [0,1{]}^2$ is homogeneous if every square of side length comparable to $n^{-1/2}$ contains only $O(1)$ points. For such sets,

$$\Delta (P){\lesssim }_{\epsilon }{n}^{-7/6+\epsilon }$$

for every $\epsilon >0$ (Cohen, Pohoata & Zakharov, 2023).

The exponent $7/6$ is the clean benchmark predicted by the high-low setup in the well-distributed case. One can take the pair scale $u\approx n^{-1/2}$, so the relevant line family has size about $n$, and the high-low method can reach a final strip width near

$$(|P||L|{)}^{-1/3}\approx n^{-2/3}.$$

Multiplying the pair scale and strip width gives

$$u{w}_f\approx n^{-1/2}{n}^{-2/3}=n^{-7/6}.$$

Why this is still far from the conjectural scale

To reach a bound near $n^{-3/2}$ by the same strip-incidence template, one would need nontrivial incidences down to width about $n^{-1}$ for roughly $n$ generated lines. This runs into the same kind of obstruction that makes Szemerédi—Trotter-type incidence bounds sharp (Szemerédi & Trotter, 1983). Reaching the $n^{-2+o(1)}$ scale would require ideas beyond the current high-low incidence framework.

The subsequent anchored-incidence theorem shows that this $7/6$ benchmark is not limited to homogeneous sets: it holds for arbitrary configurations (Cohen, Pohoata & Zakharov, 2024).

🏷️ Current Picture

Before the Cohen—Pohoata—Zakharov work, the best known bounds left the gap

$$c\frac{\log n}{n^2}\lesssim \Delta (n)\lesssim n^{-8/7}.$$

Their first paper moved the upper endpoint to

$$\Delta (n)\le n^{-8/7-1/2000},$$

and introduced projection-theoretic input into the high-low method. Their later incidence theorem gives the current general bound

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

The conceptual progress is clearer than the decimal exponents. Concentration is no longer treated only as an obstruction: in the incidence theorem, anchored point-line pairs are regularized in phase space, so concentrated configurations can be rescaled and fed back into the argument.

🏷️ Links

• on lower bounds for incidences --- The anchored-incidence theorem that improves the general Heilbronn upper bound to $n^{-7/6+o(1)}$.
• on sum-product in finite fields via entropy --- The Heilbronn argument uses a real-variable, projection-theoretic cousin of the same expansion philosophy: structured sets cannot avoid growth in all directions.
• on the sum-product conjecture’s falsity --- This is a useful contrast point: the Heilbronn proof needs sum-product-type expansion, while the counterexamples there show how hidden algebraic structure can defeat naive expansion heuristics.
• on Dudley’s Theorem --- Both notes are organized around multi-scale control. Dudley controls Gaussian processes by chaining metric entropy across scales; Roth’s method controls strip incidences by comparing high and low widths.

📚 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.

🐻  Orponen, T., Shmerkin, P. & Wang, H. 2022. Kaufman and Falconer estimates for radial projections and a continuum version of Beck’s theorem.

🐻  Roth, K.F. 1951. On a problem of Heilbronn. Journal of the London Mathematical Society 26(3), 198–204.

🐻  Roth, K.F. 1972. On a problem of Heilbronn, II. Proceedings of the London Mathematical Society 25(2), 193–212.

🐻  Schmidt, W.M. 1972. On a problem of Heilbronn. Journal of the London Mathematical Society 5(3), 545–550.

🐻  Szemerédi, E. & Trotter, W.T. 1983. Extremal problems in discrete geometry. Combinatorica 3(3–4), 381–392.