Erdős Problem #90

Erdős Problem 90: the negative unit-distance resolution

1) Statement and scope of this reconstruction

2) Exact arithmetic input

We also use the standard Minkowski embedding fact: choosing one embedding from each conjugate pair identifies $D^{-1}\mathcal O_{K_j}$ with a full lattice in $\mathbb C^{f_j}$. The fixed values $D,\gamma$ must be independent of $j$; allowing the denominator to grow arbitrarily would invalidate the argument.

3) Averaging translations inside a cube

Averaging $a$ over a fundamental domain of the lattice, with normalized Lebesgue measure, unfolds the lattice translates to give \[ \mathbb EN_a=\frac{\operatorname{vol}(W)}{\operatorname{covol}(\Lambda)}, \quad \mathbb EE_a=\frac1{\operatorname{covol}(\Lambda)} \sum_{u\in U}\operatorname{vol}(W\cap(W-\Phi(u))). \] Each coordinate interval overlaps its shift in length at least $2R-1$. Consequently \[ \mathbb EE_a\geq |U|\left(1-\frac1{2R}\right)^{2f}\mathbb EN_a \geq e^{\gamma f/2}\mathbb EN_a. \] Some nonempty $X_a$ therefore satisfies $E_a\geq e^{\gamma f/2}N_a$: otherwise integrate the strict reverse inequality, noting that empty translates contribute zero.

4) Projection is injective and preserves the selected distances

Each ordered pair counted by $E_a$ projects to a unit-distance pair, because $|\sigma_1(u)|=1$. Each unordered pair has at most two orientations, irrespective of whether $U$ is closed under negation. Hence \[ u(P)\geq\frac12 e^{\gamma f/2}n. \]

5) Uniform control of the number of points

Given any proposed $C,N_0$, choose a member with $n\geq N_0$ and $\log\log n>C/\delta$. Then $u(P)\geq n^{1+\delta}>n^{1+C/\log\log n}$. This negates the question with its full quantifiers; a subsequence suffices.

Outcome: SOLVED, the known negative resolution reconstructed relative to the stated arithmetic existence input. The geometric argument is supplied above; the field-tower theorem and any Lean formalization are not independently verified here.

6) Sources

• OpenAI, Planar Point Sets with Many Unit Distances, Propositions 2.2 and 3.8 and the geometric construction in Section 2, https://cdn.openai.com/pdf/74c24085-19b0-4534-9c90-465b8e29ad73/unit-distance-proof.pdf.
• T. F. Bloom, Problem 90, https://www.erdosproblems.com/90, checked 23 September 2026.

7) COMPLETION ESTIMATE

FORMAL RESTATEMENT. For $n\ge 2$, let \[ U(n):=\max\left\{\,|\{\{x,y\}: x,y\in A,\ x\ne y,\ |x-y|=1\}| : A\subset\mathbb{R}^2,\ |A|=n\,\right\} \] be the maximum possible number of unit-distance pairs among $n$ points in the Euclidean plane. Question (Erdős unit distance conjecture, asymptotic form): is it true that \[ U(n)\le n^{1+O(1/\log\log n)}\qquad (n\to\infty)? \] Equivalently, does $\log U(n)/\log n\to 1$ as $n\to\infty$ up to a $O(1/\log\log n)$ error?

QUICK LITERATURE/CONTEXT CHECK. The problem statement notes: (a) lattice-point constructions show that an upper bound of the form $n^{1+o(1)}$ would be best possible; (b) an elementary argument gives $U(n)=O(n^{3/2})$; (c) the best known upper bound stated there is $O(n^{4/3})$. I prove the elementary $O(n^{3/2})$ bound and a linear lower bound, without using external incidence theorems.

ATTACK PLAN.

• Lower bound: exhibit explicit $n$-point sets with many unit distances (a square grid).
• Upper bound: model unit distances as incidences between points and unit circles, use the fact two equal circles meet in at most two points, and apply a $K_{2,3}$-free extremal graph bound.

WORK.

Lemma 90.1 (grid lower bound: $\Omega(n)$). Let $k\ge 2$ and let $A$ be the $k\times k$ integer grid \[ A:=\{(i,j): 0\le i,j\le k-1\},\qquad n=|A|=k^2. \] Then the number of unit-distance pairs in $A$ is exactly \[ U_A:=2k(k-1)=2n-2\sqrt n. \] Proof. A unit distance in this grid occurs exactly between horizontally adjacent points or vertically adjacent points. There are $k$ rows, each containing $k-1$ horizontal unit segments, giving $k(k-1)$ horizontal unit pairs. Similarly there are $k$ columns, each containing $k-1$ vertical unit segments, giving another $k(k-1)$. No other pair has Euclidean distance 1 because any other difference vector has squared length at least $2$. Thus $U_A=2k(k-1)=2k^2-2k=2n-2\sqrt n$. $\square$

Lemma 90.2 (elementary upper bound: $O(n^{3/2})$). For every $A\subset\mathbb{R}^2$ with $|A|=n$, \[ |\{\{x,y\}\subset A: |x-y|=1\}|\le \frac{\sqrt 2}{2}\,n^{3/2}+\frac14 n. \] Proof. This is the special case $r=1$ of Lemma 89.1. For completeness: build the bipartite incidence graph between $n$ unit circles centered at points of $A$ and the $n$ points of $A$. Two unit circles intersect in at most two points, so the bipartite graph is $K_{2,3}$-free. The extremal counting argument (Claim 2 in Lemma 89.1) gives at most $\sqrt2\,n^{3/2}+\tfrac12 n$ directed incidences, i.e. at most half as many undirected unit-distance pairs. $\square$

FAST REALITY CHECK (small grids). For the $k\times k$ grid, Lemma 90.1 gives unit-distance pairs $2k(k-1)$. Numerically:

k=2  n=4    unit pairs=4
k=3  n=9    unit pairs=12
k=4  n=16   unit pairs=24
k=5  n=25   unit pairs=40
k=10 n=100  unit pairs=180

VERIFICATION.

• Lemma 90.1: checked that the only integer vectors of squared length 1 are $(\pm1,0),(0,\pm1)$.
• Lemma 90.2: the $K_{2,3}$-free condition hinges only on "two circles meet in at most two points", which is valid for Euclidean circles.
• Scaling: the bound is for distance $1$ but is invariant under rigid motions; scaling would change the distance but not the combinatorics.

FINAL. UNRESOLVED

1. (i) Strongest proved partial result. An elementary incidence/graph argument gives $U(n)=O(n^{3/2})$ with an explicit constant (Lemma 90.2). A $k\times k$ integer grid gives $U(n)\ge 2n-2\sqrt n$ for $n=k^2$ (Lemma 90.1).
2. (ii) First gap (crisp). Improve the upper bound exponent below $3/2$ by an argument that uses a special feature of the Euclidean metric, aiming toward $n^{1+o(1)}$.
3. (iii) Top 3 next moves.
   • Strengthen the extremal-graph step (which only used $K_{2,3}$-freeness) by incorporating geometric restrictions on how many unit circles can pass through many points in structured configurations.
   • Prove sharper bounds for the incidence graph using planar geometry (e.g., crossing number for drawings of the unit-distance graph, or polynomial partitioning).
   • Computational experimentation: for moderate $n$, search for point sets with unusually large unit-distance graphs to guess extremal structure.
4. (iv) Likely structure of a minimal counterexample. A set attaining very large $U(n)$ must have many points lying on many unit circles in a highly correlated way (since random sets have nearly all distances distinct). Any counterexample to $n^{1+o(1)}$ would likely involve arithmetic structure (lattice-like sets) arranged to create many repeated unit distances.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. Given a set $A\subset\mathbb R^2$ of $n$ distinct points, let \[U(A):=\big|\{\{x,y\}\subset A:\ |x-y|=1\}\big|\] be the number of unordered unit-distance pairs in $A$.

Question. Is it true that \[U(A)\ \le\ n^{1+O(1/\log\log n)}\] for every $n$ and every $A$ of size $n$?

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. The statement says: - easy bound $U(A)=O(n^{3/2})$, - best known $U(A)=O(n^{4/3})$ (SST), and conjectured $n^{1+o(1)}$. I will prove the easy $O(n^{3/2})$ bound from scratch.

3) ATTACK PLAN Proof track ideas: 1. Use incidence bounds between points and circles to upper bound the number of unit distances. 2. Improve beyond $n^{4/3}$ requires Euclidean-specific tools (per statement); that is out of reach here.

Disproof track ideas: 1. Construct point sets with many unit distances; lattice points give $\Omega(n)$.

Chosen path in this attempt: (i) prove the classical $O(n^{3/2})$ bound via a Kővári--Sós--Turán argument, and (ii) give an explicit $\Omega(n)$ construction from the integer grid.

4) WORK Lemma 1 (An $O(n^{3/2})$ upper bound for unit distances). For every set $A\subset\mathbb R^2$ of $n$ points, \[U(A)\le n^{3/2}+n.\]

Proof. Build a bipartite graph $B$ with left part $L=A$ (centers) and right part $R=A$ (points), and connect $x\in L$ to $y\in R$ iff $|x-y|=1$. Then each unordered unit-distance pair $\{x,y\}$ contributes two directed edges $(x,y)$ and $(y,x)$, so \[e(B)=2U(A).\tag{1}\]

Two circles in the plane intersect in at most two points. Therefore, for two distinct centers $x\ne x'$, the unit circles around them have at most two common points, meaning $x$ and $x'$ have at most two common neighbors in $R$. Equivalently, $B$ is $K_{2,3}$-free with the two-vertex side in $L$.

We now bound $e(B)$ directly. Let $d(r)$ be the degree of a right vertex $r\in R$. Count length-2 paths $\ell-r-\ell'$ with $\ell\ne \ell'$ and $r\in R$: \[P:=\sum_{r\in R}\binom{d(r)}{2}.\] For a fixed unordered pair $\{\ell,\ell'\}\subseteq L$, the number of common neighbors of $\ell$ and $\ell'$ in $R$ is at most $2$ (else we would have three points lying on the intersection of two unit circles). Thus $P\le 2\binom{n}{2}<n^2$.

On the other hand, \[P=\sum_{r}\binom{d(r)}{2}=\frac12\sum_r d(r)^2-\frac12\sum_r d(r)\ge \frac12\cdot\frac{e(B)^2}{n}-\frac12 e(B)\] by Cauchy--Schwarz ($\sum_r d(r)^2\ge e(B)^2/n$) and $\sum_r d(r)=e(B)$. Hence \[\frac{e(B)^2}{2n}-\frac{e(B)}{2}\le n^2.\] Solving this quadratic inequality gives $e(B)\le 2n^{3/2}+2n$ (for instance, $(e(B)-n/2)^2\le 2n^3+n^2/4\le (2n^{3/2}+n)^2$). Combine with $1$ to get $U(A)=e(B)/2\le n^{3/2}+n$. $\square$

Lemma 2 (Grid lower bound $\Omega(n)$). Let $m\ge 2$ and let $A$ be the $m\times m$ integer grid \[A:=\{(i,j): i,j\in\{1,2,\dots,m\}\},\] so $|A|=n=m^2$. Then \[U(A)=2m(m-1)=2n-2\sqrt n.\]

Proof. Unit distances in the integer grid occur exactly between horizontally adjacent points and vertically adjacent points. There are $m$ rows, each with $m-1$ horizontal unit edges, giving $m(m-1)$ pairs. There are $m$ columns, each with $m-1$ vertical unit edges, giving another $m(m-1)$ pairs. No other pairs are at Euclidean distance $1$ since the squared distance between two distinct integer lattice points is an integer and equals $1$ only for these axis-adjacent pairs. Thus $U(A)=2m(m-1)=2m^2-2m=2n-2\sqrt n$. $\square$

FAST REALITY CHECK Lemma 1 matches the "easy" $O(n^{3/2})$ bound stated in the problem text. Lemma 2 shows $U(A)=\Theta(n)$ is achievable, so any upper bound of the form $n^{1+o(1)}$ would be asymptotically tight up to subpolynomial factors.

5) VERIFICATION - Lemma 1 reduces unit distances to incidences between points and unit circles and uses only the geometric fact "two circles meet in at most 2 points" plus KST. - Lemma 2 counts unit edges explicitly and checks there are no diagonal unit distances in the integer grid.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved the classical easy bound $U(A)\le n^{3/2}+n$ (Lemma 1) and the grid construction with $U(A)=2n-2\sqrt n$ (Lemma 2).

(ii) First gap: Improve the exponent $3/2$ toward $1+o(1)$, i.e. exploit Euclidean-specific structure beyond the circle intersection bound.

(iii) Top 3 next moves (concrete): 1. Replace the $K_{2,3}$-free extremal argument by a stronger incidence theorem (Szemerédi--Trotter) for point-circle incidences to reach exponents below $3/2$. 2. Identify which step in the SST84 proof uses Euclidean geometry in an essential way and see whether it can be pushed below $4/3$. 3. Explore additional restrictions (e.g. convex position, no three collinear) that yield better bounds (see Problem #96 and #92).

(iv) What a minimal counterexample would likely look like (structure/parameters): A family of point sets $A_n$ with $|A_n|=n$ such that $U(A_n)\ge n^{1+\delta}$ for some fixed $\delta>0$, which would disprove the conjectured $n^{1+o(1)}$ upper bound.