An explicit lower bound for the unit distance problem

Abstract. We show that there are sets of n points in the plane with n arbitrarily large that contain more than n1.014 pairs of points separated by a distance exactly 1. This improves on very recent work of a team at OpenAI, who proved the same result with an inexplicit exponent greater than 1, drastically improving on the best previous lower bound and disproving a conjecture of Erd ̋os. The method is number-theoretic, relying on constructing algebraic number fields of large degree and small discriminant with many primes of small norm via a Golod-Shafarevich criterion argument.

Introduction. We prove the following:

Theorem 1. For n arbitrarily large, there exists a set of points U ⊂R2 such that = n and #{(v1, v2) ∈U | |v1 −v2| = 1} ≥n1.014114/C for an absolute constant C.

The best known upper bound is #{(v1, v2) ∈U | |v1 −v2| = 1} = O(n4/3), due to Spencer, Szemer ́edi, and Trotter [14]. Until very recently, the best lower bound known in Theorem 1 was of the form #{(v1, v2) ∈ U | |v1 −v2| = 1} ≥n1+ c log log n for some c > 0, by Erd ̋os [3, Theorem 2], who also conjectured that this was optimal [5, p. 267] (sometimes making the weaker conjecture that #{(v1, v2) ∈ U | |v1 −v2| = 1} ≤n1+o(1) [4, p. 62]). Very recently, both conjectures were disproved [13] by a team at OpenAI, consisting of Lijie Chen using an internal OpenAI model and Mark Sellke and Mehtaab Sawhney verifying correctness. They showed a lower bound of the form n1+δ for some δ > 0 not made explicit. It would be possible to make this explicit, but the value of δ obtained would likely be very small. A team of mathematicians produced a simplified version of this argument [1], and obtained δ ≈6 × 10−38. We provide a bound with an exponent δ that is explicit, and not exorbitantly small (differing from the upper bound by a factor of less than 24), though certainly not optimal. To do this, we make explicit and sharpen every step of the argument. Interestingly, this rarely makes the arguments much more complex: The total length of this paper is essentially the same as the original OpenAI writeup [13], though longer than the simplified version prepared by human authors [1]. The basic strategy is the same as the OpenAI team’s proof: To construct a set of points in R2 with many unit distances, it suffices to construct a lattice, and a projection of the lattice to R2, with many short vectors whose projections to the plane have length 1, as then the projection to R2 of the intersection of the lattice with a suitable ball will have many unit distances. (Erd ̋os’s original argument used a lattice in R2, rather than a higher-dimensional lattice with a projection to R2.) A useful source of lattices is the rings of integers of number fields, and these carry natural projections to the plane coming from the embeddings of the number field into the complex numbers. When the number field is a CM field K, containing a totally real subfield F, the squared length of the projection of a lattice vector to the plane lies in F. Since F has smaller degree than K and thus intuitively has fewer elements, it is possible for the projections of many 1 AN EXPLICIT LOWER BOUND FOR THE UNIT DISTANCE PROBLEM 3 Finally, we discuss two further questions, both suggested by Thomas Bloom: what is the density of the set of n for which a set of points in Theorem 1 exists, and what are the limits to the exponents that can be achieved by this argument? The author was supported by NSF grant DMS-2502029 and was a Sloan Research Fellow while working on this manuscript and would like to thank Noga Alon, Thomas Bloom, Sebastien Bubeck, Timothy Gowers, Daniel Litt, Mehtaab Sawhney, Mark Sellke, Peter Sarnak, Arul Shankar, Kannan Soundararajan, Jacob Tsimerman, Victor Wang, and Melanie Matchett Wood for helpful conversations.

Related work. The best known upper bound is #{(v1, v2) ∈U | |v1 −v2| = 1} = O(n4/3), due to Spencer, Szemer ́edi, and Trotter [14]. Until very recently, the best lower bound known in Theorem 1 was of the form #{(v1, v2) ∈ U | |v1 −v2| = 1} ≥n1+ c log log n for some c > 0, by Erd ̋os [3, Theorem 2], who also conjectured that this was optimal [5, p. 267] (sometimes making the weaker conjecture that #{(v1, v2) ∈ U | |v1 −v2| = 1} ≤n1+o(1) [4, p. 62]). Very recently, both conjectures were disproved [13] by a team at OpenAI, consisting of Lijie Chen using an internal OpenAI model and Mark Sellke and Mehtaab Sawhney verifying correctness. They showed a lower bound of the form n1+δ for some δ > 0 not made explicit. It would be possible to make this explicit, but the value of δ obtained would likely be very small. A team of mathematicians produced a simplified version of this argument [1], and obtained δ ≈6 × 10−38. We provide a bound with an exponent δ that is explicit, and not exorbitantly small (differing from the upper bound by a factor of less than 24), though certainly not optimal. To do this, we make explicit and sharpen every step of the argument. Interestingly, this rarely makes the arguments much more complex: The total length of this paper is essentially the same as the original OpenAI writeup [13], though longer than the simplified version prepared by human authors [1]. The basic strategy is the same as the OpenAI team’s proof: To construct a set of points in R2

Method. In Lemma 2, we describe, in quantitative form, how a lattice with many short vectors that have the same length on projection to R2 gives a set of points in R2 with many unit distances. To construct such a lattice, it suffices to choose an ideal in the ring of integers of a CM number field K over a totally real field F which contains many elements that have the same norm from K to F. This is done in Lemma 4, resulting in Lemma 5 which gives a simple bound for unit distances in terms of how many elements of an ideal of K have a given norm. We can always find a suitable ideal when F has many small primes that split in K. This is shown in Lemma 7. Lemma 8 specializes Lemma 7 to the case when K is Galois. Lemma 9 gives a bound for the relative class number. Combining all these, Proposition 10 gives a version of Theorem 1 with an explicit value of δ if there exist infinitely many number fields satisfying certain criteria depending on a set of primes SQ. Lemma 12 constructs infinitely many such fields given another set of primes T, and we finally prove Theorem 1 by finding explicit suitable sets SQ and T.

The next two lemmas will produce suitable fields F and K to apply Proposition 10. The strategy is to start with a quadratic field Q and choose K and F to be extensions of Q unramified at all finite places. We will choose f(p) = 2 for all p in SQ, so that to apply Proposition 10, we need to check that there are infinitely many totally real fields F that are everywhere unramified extensions of Q such that for each prime p in SQ, the inertia degree of p in F is at most 2. This is done in Lemma 12 using Galois-group calculations in Lemma 11.

Proof of Theorem 1. By Lemma 12, we see that if T is a finite set of odd primes such that the number of elements of T which are congruent to 3 modulo 4 is odd and SQ is a finite set of primes of Q, such that each prime of SQ is either inert in Q(√q) for some q ∈T or congruent to 1 mod 4, and satisfying (9), we can take

Discussion. We first explain in more detail how our arguments differ from those [13] obtained by Lijie Chen using an internal OpenAI model, with a simplification suggested by Victor Wang: In Lemma 2, we apply the probabilistic method to bound the ratio #{(v1, v2) ∈U 2 | |v1 −v2| = 1}/#U instead of the value #{(v1, v2) ∈U 2 | |v1 −v2| = 1}. Note that the improvement here is proportional to the ratio between the average value of and the upper Remark 13. We explain how it is possible to prove a version of Theorem 1 which shows that a set U exists with = n and #{(v1, v2) ∈U | |v1 −v2| = 1} ≥n1+δ/O(1) for many n ≤N. To do this, observe that the construction of Proposition 10 produces, for some X > 1, for d the degree of a suitable field F, a set with Next observe that we can adapt Lemma 12 to produce fields whose degree is any fixed sufficiently large power of 2, since Gal(F/Q) is a 2-group, 2-groups always contain central elements of order two in any nontrivial subgroup, and taking the fixed field of a central element of order 2 in Gal(F/Q) that lies in the kernel of the natural map to Gal(Q({√q | q ∈T})/Q) produces a field of degree smaller by a factor of 2 that has all the same properties. Thus for N sufficiently large we can take Remark 14. We discuss a final question: What are the limits for the exponents that can be obtained by this argument? To make this into a precise question, set aside the question of improvements to Lemmas 5 and 7. Combining Lemmas 5 and 7, one obtains an exponent of

Limitations. Remark 13. We explain how it is possible to prove a version of Theorem 1 which shows that a set U exists with = n and #{(v1, v2) ∈U | |v1 −v2| = 1} ≥n1+δ/O(1) for many n ≤N. To do this, observe that the construction of Proposition 10 produces, for some X > 1, for d the degree of a suitable field F, a set with Next observe that we can adapt Lemma 12 to produce fields whose degree is any fixed sufficiently large power of 2, since Gal(F/Q) is a 2-group, 2-groups always contain central elements of order two in any nontrivial subgroup, and taking the fixed field of a central element of order 2 in Gal(F/Q) that lies in the kernel of the natural map to Gal(Q({√q | q ∈T})/Q) produces a field of degree smaller by a factor of 2 that has all the same properties. Thus for N sufficiently large we can take Remark 14. We discuss a final question: What are the limits for the exponents that can be obtained by this argument? To make this into a precise question, set aside the question of improvements to Lemmas 5 and 7. Combining Lemmas 5 and 7, one obtains an exponent of