Unit Distance

Claim: AI can make scientific breakthroughs.

Proof: An internal OpenAI model resolved the most famous conjecture in discrete geometry, namely the optimality (or lack thereof) of the grid for the unit distance problem. This conjecture had seen no progress, despite a lot of interest, since its inception 80 years ago. (There was a lot of activity and progress AROUND it though!)

Let me use this thread to explain concretely what happened. You can also find explanations at varying levels of complexity in our blogpost, in the companion paper written by world leading mathematicians (to appear on arxiv later today), in the report with the original AI proof, and in the (rewritten) chain of thought of the model solving the problem.

Okay so what are we talking about: the question is stupidly simple; if I put n points in the plane how many distances between those points can be the same? (By rescaling you can also just ask how many of those distances can be equal to 1, hence the name “unit” distance problem). Well, certainly you could put one point in the center of a circle and all the other ones on a circle centered at this point, which would result in n-1 distances being the same. And obviously there are at most n^2/2 distances. So what is the truth, is the best one can do of order n or of order n^2?

When Erdos introduced the problem in 1946 he analyzed the most natural construction for this problem: putting points on a simple grid. Okay so a point now has 4 neighbors on this grid, so certainly there are at least of order 2*n distances that are the same (2n and not 4n because of double counting). But let’s be a tiny bit more clever, instead of looking at distance 1 vertices (say the grid has unit length edges) we could look at vertices that are at distance sqrt(5) = sqrt(1+2^2). Just draw a little picture and you will see that there are 8 points at that distance! Indeed, you basically move along a L shape turned any way you want (and there 8 ways to do that). What Erdos proved (and I will give the proof below) is that you can keep going like this in powers of 2, up to about u(n) = 2^{log(n)/loglog(n)}. So it means the grid has at least about u(n)*n distances that are the same, and in fact this calculation is optimal for the grid. Note that u(n)*n = n^{1+o(1)} (specifically, n^{1+cst/loglog(n)}).

What Erdos conjectured is that the grid is essentially optimal: any configuration of points should have at most n^{1+o(1)} equal distances. This is the problem that saw zero progress in the past 80 years, again despite a lot of interest given how basic and natural this question is. My understanding is that Erdos strongly believed that the grid is optimal, and in fact in the closely related problem (introduced in the same 1946 paper!) of distinct distances he was vindicated. The distinct distances problem is simply the opposite version of the question, where one asks what is the minimal number of distinct distances that n points can form? The grid gives you n/sqrt(log(n)) distinct distances, and a breakthrough paper by Guth and Katz 10 years ago showed that this is indeed essentially optimal with a lower bound of n/log(n). In other words: everything was pointing to the grid being also an optimal candidate for the unit distance problem.

This is where the OpenAI internal comes in. It actually STRONGLY disproved this long-held belief and found a new (mind blowing) construction with a number of equal distances of order n^{1+delta} for some delta>0. To say a few words about how this breakthrough was achieved by the model I first need to tell you a little bit more about Erdos’ proof and where the 2^{log(n)/loglog(n)} comes from. Turns out the primes are lurking around!

We will assume two things about prime numbers: first the prime number theorem that says that there are about n/log(n) primes below n (well actually we need a slightly more refined version but it doesn’t matter for the level of this exposition). Second, that if a prime is equal to 1 modulo 4, then it factorizes over the Gaussian integers (which are integers of the form a+ib with a and b integers), namely in this case p = z bar{z}. For example 5=(1+2i)(1-2i), and this should remind you above when we counted 8 vertices at distance sqrt(5) = sqrt(1+2^2). Okay so now take the first k primes that equal to 1 modulo 4, p_1, …, p_k, and consider the number R=p_1…p_k = z_1 bar{z_1} … z_k \bar{z_k}. The key point is that we get 2^k Gaussian integers out of this with modulus equal to sqrt{R}, by selecting for each prime p_i to take either take z_i or bar{z_i} and then take their product (crucially we use that the modulus is multiplicative and that conjugation preserves the modulus). In other words we have found 2^k points at distance sqrt{R} from the origin on the grid! (To be precise we also have to prove that these points are distinct, which is where unique factorization in Z[i] becomes important, and something that will be key in the new proof, but let’s ignore that here.) So now we just need to see how big we can take k while keeping sqrt{R}<sqrt{n} (the latter being the side length of a grid with n points). We have log(R) = sum_{i=1}^k log(p_i) which by the prime number theorem is roughly sum_{i=1}^k log(ilog(i)) which is basically klog(k). So we need klog(k) less than log(n), so k should be like log(n)/loglog(n), and we get the claimed 2^k = 2^{log(n)/loglog(n)}.

The above one paragraph argument (clever one I will give you that) has remained SOTA for 80 years. Now what AI did is pretty crazy in my opinion. First of all, as can be seen in the CoT, it almost immediately decided to try to improve the grid construction, which is the opposite of what most mathematicians had been trying to do so far. In my limited understanding the strategy it came to (and which it executed perfectly) is roughly like this: wouldn’t it be great if there was more ways to the split the primes? Maybe if we were to consider another field than Q, one of higher degree, then this could work with the integers Z replaced by the ring of integers of that field? Maybe instead of 2^k we could get 2^{f k} where f is the degree of the field? First guess would be to look at cyclotomic extensions but the model does that first in its CoT and quickly realizes that this won’t work. It keeps working hard and eventually brings in the language of ideals where there can be non-unique factorization that are handled by a class group. Now you need to start thinking about how you will construct high degree fields with all the parameters controlled (first the class number, but also this will be a higher dimensional lattice, so it will need to be projected back to the complex plane, and this projection will induce some collapsing that needs to be controlled, and on and on). That’s where the model uses a hammer from class field theory, the infinite towers from Golod-Shafarevich. At this point it’s probably better for you to head to the companion paper by actual experts on the subject for further details!

Okay let me take a step back: basically what the AI did is that it was able to use its vast knowledge of all of mathematics, to see a connection between discrete geometry and algebraic number theory, and then crucially it was able to masterfully chain together the argument, with expert level calculations at every step. It is truly a breakthrough result, yet at the same time it is also true that the model didn’t “invent” any “new mathematics” (say it didn’t invent some alternative class field theory, whatever that would mean). But this is the crucial point: merely being able to know deeply all the results in a scientific field, and being able to use all known arguments expertly and with just the right choice of parameters, that alone can lead to a ton of breakthroughs, and this is not just limited to mathematics, this type of (extremely) solid expert execution is the bread and butter of many many scientific advances.

Finally a word about what this means for mathematics going forward. The companion paper has a lot of reflections on that from leading mathematicians, so better to just read what THEY have to say. But one thing interesting to note is that we are NOT submitting the model’s proof to arxiv. Indeed no human author can claim to have contributed in the traditional sense (although of course it’s really the fruit of all human researchers in OpenAI who have created this amazing model, as well as humanity in general developing mathematics for millennia …). On the other hand the companion paper by humans goes beyond just reflections on the significance of the moment, it also digests the proof, puts it into broader context, and even simplifies it a bit. While the community still has a lot of work to do to fully adapt to these new developments, we believe that this principle of separating the AI proof from the human’s understanding of it will be an important piece of the puzzle.