Recently, OpenAI announced an LLM-automated proof refuting the conjectured bound in the unit distance problem. This was a long-standing open problem in combinatorics, and the proof elegantly invokes constructions via infinite class field towers, exploiting rigid structures from algebraic integers related to their canonical embeddings. There is also a companion paper, written by mathematicians, that explains the technical details as well as commenting on, among other things, the implications for the mathematical community and several sources in existing literature that clearly influence the proof strategy, which are not included in the LLM-automated proof paper. In this post, I’m going to walk through the main construction ideas.
In a previous post, I talked about how one uses convex geometry to constrain algebraic structures to recover classical results, such as the class number formula, and hinted at connections to cryptography. This turns out to be timely given the specific arguments. Hopefully, the results should provoke more interest among cryptographers and coding theorists. There is a long debate on whether claimed security levels for common lattice-based cryptosystems — built up from the rings of integers of cyclotomic extensions — hold up. In practice, people pretend that no exploitable algebraic structures exist. We won’t address the issue in this post, but the unit distance problem proof suggests previously unnoticed structures from algebraic lattices. And the probabilistic argument that sufficiently many field elements (of a certain type) with norm one exist is particularly interesting.
As a topologist and geometer, I find the Golod–Shafarevich theory part the most intriguing, which involves algebraic topology flavours. But I will present the relevant arguments mostly in a black-box way. I will save stuff like this and connections between Cohen–Lenstra heuristics over function fields and homological stability for future posts.
High-level proof strategy
The unit distance problem asks the following question: given a finite set 
, equipped with the standard Euclidean metric, let 
be the number of unordered pairs with pairwise distance 1. Define 
. The unit distance problem asks how 
grows as 
. Specifically, Erdős conjectured that there exists a constant 
such that the following inequality holds:
which turned out to be false. The proof requires constructing a series of planar sets, whose cardinality tends to infinity, such that the numbers of unordered pairs with pairwise distance 1 remain sufficiently large.
Construction
The construction goes through embedding number fields into the Euclidean space 
via the canonical embedding. For instance, if one takes a cyclotomic extension 
that is not totally real — meaning that one cannot embed it into the real numbers, e.g. the field 
— then each coordinate of the canonical embedding corresponds to mapping the generator into an 
-th primitive root of unity on the unit circle. We notice that we can reformulate the problem this way: instead of constructing planar sets 
, we construct subsets of a number field, with only complex embeddings, such that there exist many unordered pairs where each coordinate of the pairwise distance has absolute value 1. This works because projection to the first complex coordinate is injective, so we can construct planar sets with many unordered pairs with pairwise distance 1.
Specifically, the construction follows three steps:
- Construct a number field
as the quadratic extension 
of a totally real field 
adjoined by a root of 
, so in particular has only complex embeddings.
- Construct a sufficiently large subset
of , such that each coordinate of an element in the canonical embedding of has absolute value 1.
- Construct a set
, such that sufficiently many elements in have pairwise distances in the set .
For technical details, see the OpenAI technical paper. Here, we briefly mention the constructions of and in the last two steps, whose existence involves non-constructive arguments.
Construction of
For the construction of , the key idea is that one can construct the set as a subset of elements with relative norm 1 from to . These elements, when viewed as vectors in the Euclidean space, are a subset of vectors with norm 1. Moreover, one constructs elements in as normalised generators of principal fractional ideals with prescribed orders at Archimedean places from a set of primes totally split in . One shows that contains sufficiently many elements using Minkowski’s bound, which will come in handy for the asymptotic bound argument.
Construction of
The proof constructs as the translate 
of the lattice 
of 
— the ring of integers of divided by a bounded denominator — by an element 
in the fundamental domain of . This way, one obtains a lower bound on the ratio of the number of pairs of elements in whose differences lie in against the cardinality of , which follows from a standard probabilistic pigeonhole argument via standard unfolding identity formulas relating counting formulas to the lattice covolume.
Infinite class field towers
The most technically interesting part of the proof relates to the construction of the totally real field in step 1. The basic idea is that one considers an extension of number fields with Galois group a direct sum of copies of 
and then takes its everywhere-unramified pro-3 extension. Then, one can cut out a specific subextension satisfying all compatible conditions, such as making sure all relevant primes split completely, while feeding various controls into Golod–Shafarevich theory to show that the field tower is infinite, where the extension at each level provides constructions for step 1.
Leave a Reply