Remarks on the disproof of the unit distance conjecture

Abstract. We present a short, digested, human-verified version of the recent OpenAI-generated counterexample to the Erdős unit distance conjecture, and a sequence of reflections on it. The argument relies crucially on ideas that may, at least in retrospect, be attributed to Ellenberg- Venkatesh, Golod-Shafarevich, and Hajir-Maire-Ramakrishna.

Introduction. The following result is due to an internal model at OpenAI. The proof we give in these remarks is a human-digested, somewhat simplified, and somewhat generalized version of the AI proof.1 Theorem 1.1. There exists ε > 0 such that the following holds. There exists a sequence of point sets Pi in R2 such that |Pi| →∞and the number of unit distances in Pi is at least |Pi|1+ε for all i.

1.1. History of the problem. The unit distance problem was originally raised in work of Erdős [14]. In his original work, he noted that a set of n points may have at most O(n3/2) unit distances via noting that the unit distance graph cannot contain a K2,3 (two unit circles can only intersect in at most 2 points) while using a √n×√n grid to show that a set of n points may have n1+Ω(1/ log log n) unit distances. The best current upper bound, O(n4/3), is due to Spencer, Szemerédi, and Trotter [32]. An upper bound of n1+o(1) was conjectured by Erdős; see [6] for details. For more background, the reader may consult the introduction of Alon, Bucić, and Sauermann [2], a recent paper on the unit distance and distinct distances problems for generic norms, which are shown to behave rather differently than the usual Euclidean norm on R2. Indeed, Alon has remarked that problems in discrete geometry like this one are closely connected to deep questions in real algebraic geometry and number theory, as they deal with common roots of natural sets of real polynomials. A similar insight appears to be part of the Chain-of-Thought (CoT) of the AI proof of Theorem 1.1: “. . . in principle all extremal examples can be taken algebraic. But the degree and height of that algebraic realization can be enormous. . . Maybe that enormous degree is not just an annoyance but a source of possible counterexamples. Number fields deserve a closer look.” The idea of trying to use number fields to construct counterexamples is not altogether new, but there are subtleties to making it work (discussed in some of the reflections in this note), especially considering that perhaps most experts believed the conjecture n1+o(1) to be true.

1.2. Sketch of the proof. One starting point of the proof is to construct a large set U of magnitude-1 algebraic numbers of bounded denominator D in a number field K, in terms of the class number h(K) and the splitting behavior of various prime ideals. This will be done in Lemma 2.2 using the pigeonhole principle, along the lines of an idea of Michel, Soundararajan, Ellenberg, and Venkatesh recorded in [10]. It turns out to be convenient to assume K is a CM field. A key reason for this is that an element of a CM field has absolute value 1 in some embedding if and only if it has absolute value 1 in all embeddings. This will be convenient for ensuring that many elements of U appear as differences x −y of elements x, y ∈W for a nice bounded window W of D−1OK, to be discussed below. The bounded window is constructed using either the geometry of numbers, or an averaging (unfolding) argument. This step requires embedding the ring of algebraic integers OK of K as a lattice inside K ⊗R. Equivalently, for a more analytically-minded reader, it requires working with not just a single absolute value on K, but the sup-norm over all conjugate absolute values on K. The set of unit distance pairs created in W decreases as the root discriminant of K increases, and thus it is advantageous to let K be a finite layer of an infinite class field tower M of Golod- Shafarevich type, with [K : Q] →∞, since such K have bounded root discriminant. The simplest way to make U large in Lemma 2.2 is to ensure that this tower M has at least one split rational prime q. This fixed prime q will split into many primes in K as [K : Q] →∞, and when used appropriately this drowns out the main enemies, the class number h(K) and discriminant Disc K, which are relatively mild thanks to the controlled ramification in M. Fixing an embedding K ,→C, we obtain the desired sequence of point sets PK := W ,→C = R2, indexed by fields K. The AI argument originally required a suitably large finite number of split primes. Construction of such Golod-Shafarevich towers is, however, not the novel part of the argument. The construction of Golod-Shafarevich towers with not just a single split prime, but infinitely many split primes, already appears in the literature [20] and has been used for other applications.

1.3. Context for the proof. The original grid construction can be thought of as an application of Lemma 2.2 to the CM field K = Q(i). Counting magnitude-1 algebraic numbers of bounded Weil height in a fixed CM field K has also been done before; see, for instance, [1,4]. A novel ingredient of the AI argument is to take [K : Q] →∞. In classical Diophantine terms, if 1.4. Organization of the paper. In Section 2 we give a complete proof of Theorem 1.1. After Section 2, we collect a sequence of reflections on the proof and comments on the AI solution.

Method. 2.1. Statements of Main Lemmas. We state here two lemmas, and motivate the entire argument around these lemmas. The lemmas are the key novelty. We also prove Theorem 1.1 from the lemmas. First, we give the geometry-of-numbers lemma. In Cf, let BR := {(x1, . . . , xf) | |xi| ≤R for all i}, a polydisc of “radius” R. For a subset S ⊂Cf, let US := {(x1, . . . , xf) ∈S | |xi| = 1 for all i}, the outermost points on the boundary of the region B1 ⊂Cf. If we have a lattice Λ where UΛ is large, then we can form a point-set in the plane with many unit distances by taking UΛ ∩BR for some R, and then projecting to any coordinate of C. Since every lattice point in BR−1 translated by any point in UΛ is in BR, if the projection is injective, we obtain at least 1 2|UΛ||Λ ∩BR−1| unit distance pairs among at most |Λ ∩BR| points. The following lemma quantifies the size of these sets.

Lemma 2.1. Let f be a positive integer, and 0 < δ ≤1. Let Λ be a full rank lattice in Cf, such that for all non-zero x ∈Λ, at least one coordinate xi of x has |xi| ≥δ. Further assume that the projection of Λ onto one of the coordinates of Cf is injective. Let v ≥δ−2 covol(Λ)1/f. Suppose that |UΛ| ≥uf for some u > 0. Then for every R ≥2, there exists a translate a + Λ of Λ such that the set (a + Λ) ∩BR projected onto a coordinate gives a point set P in the plane with 2ν(P) ≥ uπR2 4vδ2 f and |P| ≤ 9R2 f .

Observe that 9R2δ−2 > 1, since R ≥2 and δ ≤1. Thus given v, if we can make u > 36v π , we can choose any R ≥2 and then log(2ν(P)) log |P| ≥log uπR2 4vδ2 log 9R2 δ2 > 1. (2.1) If we can make u > 36v π and keep u, v, δ constant while letting f →∞and still finding lattices satisfying Lemma 2.1, then we have |P| →∞(since |ν(P)| →∞), while log(2ν(P)) log |P| stays bounded below by a number larger than 1, proving Theorem 1.1.

Remark. Note the above argument does not require making u large in terms of δ. This is important, as the argument here does not have the flexibility to do that, and indeed produces δ−1 quite large in terms of u.

The parameter v bounds the “skewness” of the lattice Λ. Taking constant size scalings of Minkowski lattices of algebraic integers in (totally imaginary) number fields of growing degree but bounded root discriminant, which are well-known to exist by work of Golod-Shafarevich, will keep δ, v constant while f →∞. So the remaining challenge is to produce many elements of these fields with complex absolute value 1 in every embedding, so that we can make u large compared to v. This will be done by Lemma 2.2. Let e(P) denote the ramification index of a prime ideal P in a number field K. For the sake of exposition the following result is more general than necessary, which may also be useful to readers interested in modifying or optimizing the overall method.

Lemma 2.2. Let K be a number field embedded in C. Assume K = K, where K denotes the complex conjugate of K. Let P1, . . . , Ps be pairwise distinct prime ideals of OK such that Pi ̸= P j for all 1 ≤i, j ≤s. Let k1, . . . , ks be positive integers. Let Q := s Y j=1 (PjP j)kj ⊆OK be an ideal. Let U := {u ∈Q−2 : |u| = 1}. Then |U| ≥ Qs j=1(kj + 1) h(K) .

Moreover, Q−2 ⊆D−1OK, where D := Y p|N(P1P2···Ps) pmaxj:p|N(Pj)⌈2kj/e(Pj)⌉∈Z.

Remark. Assume s ≥1. Then Lemma 2.2 is vacuous if K is totally real, and otherwise Dirichlet’s unit theorem shows that |U| = ∞unless K is CM. So in its current form, without including bounds on u in other embeddings of K, Lemma 2.2 is useful only if K is CM.

We will apply Lemma 2.2 with K a CM field, with complex conjugation automorphism c : K →K. Thus all prime ideals P of OK above a rational prime that splits completely in K satisfy P ̸= cP. Also, above such a rational prime there are many Pi in K. Moreover, an element of K has absolute value 1 in some embedding if and only if it has absolute value 1 in all embeddings, so when K is CM Lemma 2.2 produces elements in UΛ as needed for Lemma 2.1. To keep δ−1, which will be the D from Lemma 2.2, bounded, we should only take primes Pi above some fixed set of rational primes. How many and which rational primes should we use? It turns out not to matter much.

Discussion. 3. Noga Alon The Erdős unit distance problem [14] raised in 1946 is among the best known open problems in Combinatorics. It is also arguably the best known problem in Discrete Geometry. Indeed, its description in the book of Brass, Moser and Pach on Research Problems in Discrete Geometry ([9], Chapter 5) is: “The following problem of Erdős [14] is possibly the best known (and simplest to explain) problem in combinatorial geometry: How often can the same distance occur among n points in the plane?” Let U(n) denote the maximum possible number of unit distances determined by n points in the Euclidean plane. Erdős proved that U(n) ≥n1+Ω(1/ log log n), and the best known upper bound is U(n) ≤O(n4/3). This was first proved by Spencer, Szemerédi and Trotter [32] in 1984. Several simpler proofs of the same bound up to a constant factor have been given over the years, the shortest and most elegant one is due to Székely [33]. More on the rich history of this problem can be found in [9]. The common belief, conjectured by Erdős, has been that U(n) ≤n1+o(1). This has been one of Erdős’ favorite problems, I have heard him myself mentioning the problem multiple times in his lectures. I believe it would be fair to say that every mathematician working in Combinatorial Geometry thought about this problem, and lots of mathematicians working in other areas spent at least some time thinking about it. Let me also add that although this problem may look at first as a recreational one this is not the case, it is in fact closely related to other mathematical areas including Number Theory and Algebraic Geometry. The solution of the problem by the internal model of Open AI is, in my opinion, an outstanding achievement, settling a long-standing open problem. The fact that the correct answer is not n1+o(1) is surprising, and the construction and its analysis apply fairly sophisticated tools from algebraic number theory in an elegant and clever way. As explained by the remarks of some of my colleagues here there are several reasons that explain why AI tools can be better than humans in finding such a construction. With or without a full agreement with these reasons, the fact is that the AI was able to do here what lots of excellent human researchers tried and failed to do. Like other mathematicians who had the opportunity to experiment, even if only briefly in my case, with ChatGPT Pro 5.5, my impression has been that AI tools are capable of changing research in mathematics in a dramatic way. The new spectacular solution of the Erdős unit distance problem convinces me that it is hard to overestimate the full potential impact of this change.

4. Thomas Bloom This was one of Erdős’ favourite problems – he first asked it in 1946 [14] and returned to it many times. (The site www.erdosproblems.com, on which it is Problem #90, currently lists 14 separate references, and there are no doubt more.) The influential collection of ‘Research Problems in Discrete Geometry’ by Brass, Moser, and Pach [8] describes it as ‘possibly the best known (and simplest to explain) problem in combinatorial geometry’. For an AI to produce a solution to a problem of this calibre is both surprising and impressive.

One rough way to quantify the interest which Erdős himself had in his problems is by the prize value attached to them. He first offered a monetary reward in 1982 [11], of $300, for a proof or disproof of the upper bound n1+o(1). Interestingly, he wrote in [12] that the upper bound of n1+o(1) would be ‘very difficult to prove’ if true; certainly Erdős had seen many surprising constructions that he had missed at this point, and perhaps saw the possibility that he was also missing something here. The first time the higher prize of $500 was offered in print appears to be 1995 [13].