The Biggest Smallest Triangle Just Got Smaller

Consider a square with a bunch of points inside. Take three of those points, and you can make a triangle. Four points define four different triangles. Ten points define 120 triangles. The numbers grow quickly from there — 100 points define 161,700 different triangles. Each of those triangles, of course, has a particular area.

Hans Heilbronn, a German mathematician who fled his country before World War II and settled in England, thought of these triangles in the late 1940s when he saw a group of soldiers outside his window. The soldiers didn’t appear to be in formation, which got him thinking: If there are n soldiers inside a square, what is the size of the largest possible smallest triangle defined by three of them? Heilbronn wondered how one might go about arranging the soldiers (or, for mathematical simplicity, points) to maximize the size of the smallest triangle.

The problem is simple to state, but progress on the Heilbronn triangle problem, as it came to be called, has been halting, and results dried up entirely in the 1980s. Then this past May, three mathematicians — Alex Cohen, Cosmin Pohoata and Dmitrii Zakharov — announced a new cap on the size of the smallest triangle. “I think it’s a stunning result,” said Anthony Carbery, a mathematician at the University of Edinburgh.

Researchers kept working on the Heilbronn triangle problem over the years, despite the long wait for progress, motivated by its tangle of links to other areas of math. “The things it’s connected to make it come alive,” said Pohoata, a professor at Emory University in Atlanta. It’s closely related to problems about intersecting shapes, which in turn connect to both number theory and Fourier analysis — the study of complicated functions constructed from simple waves.

Cohen, a graduate student at the Massachusetts Institute of Technology, stumbled upon this web of connections last year. He’d been perusing an old survey of the Heilbronn triangle problem by Klaus Roth, another refugee from the Nazis who fled to Britain as a boy. (Roth, who died in 2015, was the first British mathematician to win the Fields Medal.)

Cohen visualized the ideas from Roth’s survey with a simple picture: a square crisscrossed by two thick strips, with a thin line down the middle of each. As he studied his diagram, Cohen realized that it might connect to ideas that his adviser, Larry Guth, had brought up in a recent reading group meeting. But Guth hadn’t been talking about triangles at all.

“I realized very quickly that these two methods were essentially equivalent,” Cohen said. “I got really excited about the triangle problem.”

One day in the common room of MIT’s math department, Cohen unexpectedly discovered that Pohoata, who had come to give a talk, and Zakharov, a fellow graduate student at MIT, had also been working on the Heilbronn triangle problem. What’s more, they had found the same link. The three began collaborating. Seven months later, they made their breakthrough. Their paper brings in even more new areas of mathematics. “They use a huge amount of machinery and different insights,” said Thomas Bloom of the University of Oxford, who said he expects the new paper to “prompt a renaissance” of progress on the triangle problem.

A Hypothesis Felled

By placing three points very close together, you can easily make the smallest triangle in an arrangement arbitrarily small. (In the most extreme case, three points in line with one another form a triangle with zero area.) But trying to keep the smallest triangle big is trickier. As you keep adding in more dots, the smallest triangle is forced to be pretty small — new dots can only be so far from existing ones. It’s relatively easy to show that the smallest triangle can’t have an area any bigger than 1/(n − 2) by splitting the square into nonoverlapping triangles.

But Heilbronn thought that the limit was even tinier than that. He guessed that no matter how the dots were arranged in the square, there couldn’t be a smallest triangle with an area larger than around 1/n², a number which shrinks much faster as n grows.

He was wrong.

In 1980, the Hungarian mathematicians János Komlós, János Pintz and Endre Szemerédi found a pattern of dots whose smallest triangle had an area ever so slightly larger than 1/n². In a separate paper published around the same time, they also showed that it’s impossible to arrange n dots to create a smallest triangle that is bigger than around 1/n^8/7. When n is large, this is much smaller than 1/n, but much bigger than 1/n².

Those results stood for over 40 years. “Improving [the bound] in either direction was remarkably hard and required a lot of technical analysis and ingenuity,” Bloom said.

“You very, very quickly get bogged down by a complete quagmire of stuff,” Carbery added.

While the construction discovered in 1980 remains the one with the biggest known smallest triangle, Cohen, Pohoata and Zakharov have, for the first time in four decades, succeeded in lowering the upper bound.

Convergent Evolution

By the time he met Cohen, Pohoata had already been working on the Heilbronn triangle problem for two years. In the summer of 2020, he put summer research students at Yale University to work on higher-dimensional versions of the problem — for example, narrowing down the largest smallest-volume shapes that appear among dots scattered in a three-dimensional cube.

As part of that project, Pohoata revisited all the prior work on the problem. Back in 1951, Roth had split the search for small triangles into two parts: First find a pair of points to form the triangle’s base, and then find a third point to complete the triangle. The strategy essentially framed the search for a large smallest triangle as the study of intersecting dots and rectangles — an approach that was refined in 1972 by Wolfgang Schmidt.

On reading Schmidt’s paper, Pohoata identified a connection to the high-low method — a technique that Guth and collaborators had developed in 2017 for estimating the overlap between a collection of rectangular strips and a collection of disks. “That was an important psychological moment for me,” he said.

In 2021, Pohoata brought up his ideas with Zakharov. The two had begun publishing together when Zakharov was still an undergraduate in Moscow. “[Zakharov] was doing remarkable things as if he was a senior researcher at a young age,” said Jacob Fox, a mathematician at Stanford University.

Zakharov was initially pessimistic about the Heilbronn triangle problem. “I thought that, well, this 8/7 stayed up there for 40 years, so who am I to crack it?” he said. “I mostly wanted to understand how it works.”

After running into one another in October 2022, Cohen, Pohoata and Zakharov soon pinpointed the obstacle that Komlós, Pintz and Szemerédi had unknowingly faced. “There’s a very specific arrangement of the points that leads to this worst-case scenario where they can’t do better than 8/7,” Cohen said. “The points can either be concentrated or spread out. The worst case is when it’s some combination.” That arrangement had points spread out on a large scale, but if you zoomed in on tiny sub-squares within the unit square, you’d see orderly patterns.

Cohen, Pohoata and Zakharov realized they could make headway by studying the dimension of the small clusters of points. To nonmathematicians, dimensions are always whole numbers: A sheet of paper is two-dimensional; a clay brick has three dimensions.

Things can get weird when you consider the dimension of a set of points. A single point is normally considered zero-dimensional. But two finite sets of points can have completely different structures. One might have 10 points marching obediently in a ramrod-straight line, while the other has 10 points sprinkled across the entire unit square.

To capture the structure of even the weirdest sets of points, the early 20th-century mathematician Felix Hausdorff came up with a new notion of dimension. According to this definition, 10 points in a line are one-dimensional, while 10 points spread evenly over a square are two-dimensional. But in this world, dimensions don’t have to be integers, and a one-dimensional set can be not linear but fractal, sporting infinite layers of intricate patterns. Depending on the details of these patterns, collections of points can even have a dimension that is bigger than 0 but less than 1.

Cohen, Pohoata and Zakharov uncovered a 1953 theorem by John Marstrand that rephrased Komlós, Pintz and Szemerédi’s estimate in terms of the Hausdorff dimension — but only for dimensions greater than 1. In order to improve the estimate, Cohen, Pohoata and Zakharov would need to find some way to generalize Marstrand’s result to sets whose dimension was smaller than 1.

Making Connections

Cohen, Pohoata and Zakharov didn’t have to think for long. As it happened, a paper by Tuomas Orponen, Pablo Shmerkin and Hong Wang that had just been posted online extended Marstrand’s 70-year-old theorem to sets whose dimension was less than 1.

Cohen didn’t learn about the paper until February. Once he did, he quickly relayed it to Pohoata and Zakharov. By late May, they’d posted their paper online, proving that the smallest triangle among n points in a unit square can’t ever be bigger than 1/n^{8/7 + 1/2000}.

Shmerkin read the triangle paper on a whim after seeing it announced on Twitter. He hadn’t even been aware of the Heilbronn triangle problem before then, so he was surprised when he spotted the reference to his proof. “This is not a direct application of what we do. There is a lot of insightful, creative and technical work in it,” he said. “For me, it was a great feeling.”

Bloom, too, was impressed. “I could have looked at that paper for a long time and never thought, oh, this applies to the triangle problem.”

While the new result improves Komlós, Pintz and Szemerédi’s exponent by only a tiny fraction, it has revived the long-languishing Heilbronn triangle problem. “You might take a look at it and say, yawn, yawn, yawn, it doesn’t look so different from what was known in 1982. But an awful lot of time has passed since 1982,” Carbery said.

By incorporating the high-low method and Orponen, Shmerkin and Wang’s work, Cohen, Pohoata and Zakharov have unmasked a new set of ties between the Heilbronn triangle problem and the rest of mathematics. As Bloom put it, the triangle problem was thought of as “a really nice, really hard problem that we don’t know what to do. But they’ve said it’s connected to a huge amount of other stuff.”

Some believe the true answer to Heilbronn’s triangle problem won’t be a whole lot bigger than his original guess of 1/n². “If I put points in a structured way, I fail; if I put points in a random way, then I fail. It can’t be too structured, it can’t be too random, therefore it probably doesn’t exist,” Bloom said. But Zakharov is hoping for a different answer. The intuitions that support an answer of 1/n² are “kind of boring,” he said. “I would very much prefer if it was n^3/2.”