The Heilbronn Triangle Problem

by radimentary

I recently gave a talk (here is an outline) about the work of K. F. Roth on the famous triangle problem of Heilbronn, and was shocked and saddened to discover that Roth passed away that same day. Terry Tao wrote a great post about some of Roth’s most important results in analytic number theory.

Today I will discuss the general approach of Roth, later refined by Komlos, Pintz, and Szemeredi, in proving upper bounds for the Heilbronn Triangle Problem. At the end of the day, the most interesting step comes from a quasi-orthogonality property between indicator functions of bounded strips in the plane. Let \tau be a pair of points in the plane and let \phi_{\tau}(w,X) be the indicator function of the strip of points at most w away from the line through \tau. We cut off these functions outside some convex region, say the unit circle – call this the cutoff region. Then, it is natural to consider the “expansion function”

\Phi_{\tau}(w,w',X) = \frac{1}{w}\phi_{\tau}(w,X) - \frac{1}{w'}\phi_{\tau}(w',X),

which measures the weighted difference between two strips of different widths w, w' around the same line. The point is that if we integrate this expansion function against the indicator function f of a given set of points in the plane, then (\Phi_{\tau}, f) counts the change in the density of points when we expand from a strip of width w to a strip of width w'.

Lemma. Two expansion functions \Phi_{\tau_1}(w_1,w'_1,X) and \Phi_{\tau_2}(w_2,w'_2,X) are orthogonal unless the corresponding strips are parallel or intersect on the boundary of the cutoff region.

Proof. The intersection of two strips is a parallelogram whose area is proportional to the widths of each strip. \Box

Thus, the set of functions \Phi_{\tau}(w,w',X) form a quasi-orthogonal set, to which we can apply a generalization of Bessel’s inequality. One option is the generalization of Bombieri:

\sum_{\tau} (\Phi_{\tau}(w,w',X),f)^2 \le \|f\|_2 ^2 \cdot \max_{\tau} \Big(\sum_{\tau'} |(\Phi_{\tau}, \Phi_{\tau'})|\Big)

The point is that the left side must be small because they are all Fourier coefficients of f with respect to an essentially orthogonal set. But the left side can be thought of as the “mean square expansion” of the strips in question, that is to say we have found a bound telling us that on average, no strips acquire too many more points than expected when we expand them from width w to a much wider width w'.

To finish the proof, one may simply observe that there are few points in very narrow strips – otherwise any three such points will form a triangle of tiny area. Then, apply the “mean square expansion” bound above and we see that there are also few points in wide strips, which contradicts something like the pigeonhole principle since there are many wide strips and many points in total.