Eighty years ago, the mathematician Paul Erdős proposed a conjecture that was neither proved nor disproved. That is, until AI arrived: a generative artificial intelligence model from OpenAI, tasked with addressing the claim, succeeded in disproving it!

Advertisement

In 1946, the mathematician Paul Erdős published a short paper containing a seemingly simple question [1], yet it has occupied generations of mathematicians ever since. According to the mathematician and computer scientist Noga Alon, it was one of Erdős’s own favorite questions [2].

The question can be phrased as follows: suppose we are free to place N points on a plane, and our goal is to create as many pairs of points as possible whose distance from one another is exactly 1. What is the maximum possible number of such pairs? And how does that number behave as N grows?

Let us illustrate the question with a simple example. You can follow along with pen and paper, or by arranging small objects on a table:
Place 3 points on a straight line so that the distance between each consecutive pair is the same, and say, equals to 1: * — * — *.
This configuration contains 2 pairs of points at distance 1. The middle point belongs to both pairs, which is perfectly fine.

Illustration: three collinear points yield two pairs (top), while the three vertices of an equilateral triangle yield three pairs (bottom).

If we add one more point on the line (for a total of 4 points), we obtain 3 pairs of points at distance 1. And so on: each additional point on the line contributes one more pair. In general, if we have N points arranged in this way on a straight line:
* — * — * — * — ….. — * — *
this structure produces N−1 pairs of points whose distance is 1.

Note that the structure in our example is not necessarily the one that achieves the greatest number of pairs: for N=3, taking an equilateral triangle with side length 1 improves the count to 3. Can you draw configurations that improve the number of pairs for 4 or 5 points?

Mathematicians are concerned with the overall behavior: how does the quantity in question change as N grows? Does the maximum number of pairs grow at the same rate as N? Perhaps quadratically, i.e., on the order of N squared? Exponentially (say, like 2 to the power of N)? Or might it even decay like 1/N?

The simple construction we presented shows that for N points we can always build a configuration on the order of N pairs (specifically, N−1 pairs). This is called linear growth (N is raised to the power of 1). But could there be a cleverer example with more pairs and a different growth rate?

We also emphasize that we care about the order of magnitude: whether there are N pairs, N−1 pairs, or 2N pairs, those are all considered growth on the order of N to the power of 1.

In addition, Erdős observed that it is impossible to achieve a growth rate exceeding N to the power 1½; that is, the best possible growth lies somewhere between the the power of 1 (linear growth, which we have already reached) and the the power of 1½. Specifically, Erdős showed that one can improve slightly beyond the power of 1, but the power in his improvement approaches 1 (tends to 1) as N grows. He conjectured that this could not be improved further: among other things, his conjecture states that there cannot be a growth rate with a power that remains above 1 by a fixed constant independent of N (for instance, 1 + one-millionth).

And this is precisely the conjecture that has now been disproved by a generative artificial-intelligence model, to the surprise of many mathematicians [3, 4]: the model generated a proof showing that one can construct configurations whose growth is N to the power 1 + a small constant (the addition to 1 is a fixed number, not one that decays to 0). The proof was checked by leading experts in the field, who wrote a paper explaining the result [2], which relied on earlier (human!) mathematical work. The model did not supply an explicit value for that small constant, but since the announcement the mathematician Will Sawin has built on the breakthrough and provided a proof with a specific constant in a pre-print [5] (0.014114, in case you were wondering). In other words, the machine advanced our understanding of a well-known mathematical problem, and human mathematicians immediately took that advance a step further.

According to OpenAI’s announcement, the model that generated the mathematical result is a new internal general-purpose reasoning model, not one trained specifically for this problem or even for mathematics in general (although it is important to note that, as far as we know, models of this kind are indeed trained on mathematical-reasoning tasks during development). Thus, the company claims, this is a model of the same type as the publicly available ChatGPT, though it is unclear whether the new model’s capabilities match those of its predecessors.

Furthermore, the model used mathematical tools from algebraic number theory—a field distinct from the combinatorics to which the original problem belongs. Such cross-disciplinary tool-mixing happens often in mathematics, being one of its beauties, and frequently leads to the solution of hard problems.

Certain mathematicians, prominently Terence Tao [6], have already begun using AI tools in their work, but the present result is a major breakthrough. It raises questions and hopes about future AI use across different areas of mathematics and about similar collaborations between humans and machines, in which human mathematicians further refine an AI’s output. We shall await developments! Or try and see for yourselves.

Many thanks to Dr. Adva Mond for her professional comments and assistance in preparing this article, and to the Little, Big Science team.

Hebrew editing: Shir Rosenblum-Man
English editing: Elee Shimshoni

References:

1. Erdős’s original paper, “On set of distances of n points,” in which he poses the question and establishes bounds on the growth rate
2. Paper by leading mathematicians confirming the model’s proof and providing context: “REMARKS ON THE DISPROOF OF THE UNIT DISTANCE CONJECTURE”
3. OpenAI’s announcement regarding the model’s breakthrough
4. The model’s own document presenting the proof: “Planar Point Sets with Many Unit Distances”
5. Will Sawin’s pre-print supplying a proof with a specific constant
6. Conversation with mathematician Terence Tao about the use of AI in mathematics
7. Further reading: Gil Kalai’s blog post on the topic, including discussion and additional references