on Heilbronn triangle problem

Overview

Heilbronn’s triangle problem asks for the smallest maximum area of a triangle formed by any three points in a set of $n$ points in a unit square. We discuss the recent breakthrough by Cohen, Pohoata, and Zakharov (Cohen, Pohoata & Zakharov, 2023), who established a new upper bound of $n^{-8/7-1/2000}$, breaking a 40-year-old barrier.

🏷️ History and Background

Heilbronn’s triangle problem, posed by Hans Heilbronn in the late 1940s, is a classic question in discrete geometry. Given $n$ points in the unit square $[0,1{]}^2$, let $\Delta (n)$ be the minimum area of a triangle formed by three of these points. The goal is to find the maximum possible value of $\Delta (n)$ over all configurations of $n$ points.

Heilbronn originally conjectured that $\Delta (n)=O(n^{-2})$. However, this was disproved by Komlós, Pintz, and Szemerédi in 1982 (Koml{\’o}s, Pintz & Szemer{\’e}di, 1982), who showed that there exists a configuration where every triangle has area at least $c\frac{\log n}{n^2}$.

🏷️ Key Milestones in Upper Bounds

• 1951 (Roth): The first non-trivial bound $\Delta (n)=O(n^{-1}(\log \log n{)}^{-1/2})$ (Roth, 1951).
• 1972 (Roth): Introduced a novel analytic method providing the first polynomial improvement: $\Delta (n)⪅n^{-1-\mu }$ with $\mu =1/8(9-\sqrt{65})\approx 0.117$.
• 1982 (KPS): Komlós, Pintz, and Szemerédi improved the exponent to $8/7\approx 1.1428$ (Koml{\’o}s, Pintz & Szemer{\’e}di, 1982).

🏷️ The Breakthrough: Breaking the 8/7 Barrier

For over 40 years, the exponent $8/7$ remained the best known upper bound. Cohen, Pohoata, and Zakharov (Cohen, Pohoata & Zakharov, 2023) finally broke this barrier using tools from incidence geometry and projection theory. Their main result states:

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

🏷️ Connection to Sum-Product and Projection Theory

The novelty of their approach lies in connecting the triangle problem to the discretized sum-product phenomenon and Marstrand-type projection theorems.

The High-Low Method

The proof utilizes the high-low method (introduced by Guth, Solomon, and Wang), which is a modern take on Roth’s analytic method. It analyzes incidences between points and strips (representing potential small-area triangles) at different scales. If the points and lines (strips) are not too concentrated, the normalized number of incidences remains stable across scales.

The “low” part of the argument relies on a discretized version of a theorem by Orponen, Shmerkin, and Wang regarding the Hausdorff dimension of direction sets. This allows the authors to access finer scales than previously possible, bypassing the KPS threshold.

🏷️ Potential Impact and Applications

The improvement, while quantitatively small ($1/2000$), is qualitatively significant as it demonstrates that the KPS bound was not the natural limit of the problem.

1. Incidence Geometry: The work strengthens the link between classical discrete geometry problems and modern additive combinatorics.
2. Projection Theory: It provides a concrete application for recent advances in radial projections and the discretized sum-product theorem.
3. Homogeneous Sets: The authors also show that for homogeneous sets (points well-distributed in the square), the bound can be further improved to $n^{-7/6+\epsilon }$.

🏷️ Links

• on improved Nyström bounds — Spectral decay in kernel matrices shares similar analytic techniques with the high-low method.
• on sum-product in finite fields via entropy — The discrete sum-product phenomenon discussed here is the “finite field” analog of the tools used by Cohen et al.

📚 References

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

🐻  Koml{\’o}s, J., Pintz, J. & Szemer{\’e}di, E. 1982. Upper bound for the {Heilbronn} triangle problem. Journal of the London Mathematical Society 2(3), 383–390.

🐻  Roth, K.F. 1951. On {Heilbronn’s} triangle problem. Annals of Mathematics, 102–111.