Erdős Problem #89

Erdős Problem 89: distinct distances and the remaining logarithmic gap

1. Statement and scope

2. Two anchors and pinned distances

3. The ordered energy identity and the known theorem

There is a useful caution about trying to close this gap by $3$ alone. Guth--Katz also state that their energy bound $4$ is sharp up to constants for square grids. Consequently a proposed universal improvement $Q(P)=O(n^3\sqrt{\log n})$ would itself be false. The desired distance bound needs additional information about distance multiplicities, or another argument; the failure of this stronger energy estimate is not a counterexample to the distance conjecture.

4. Complete bounds in two structured cases

5. Assessment and sources

Sources: https://www.erdosproblems.com/89; L. Guth and N. H. Katz, On the Erdős distinct distance problem in the plane, Proposition 2.2 and the discussion following it, https://arxiv.org/abs/1011.4105.

Completion rate estimate: 30%.

FORMAL RESTATEMENT. Let $A\subset\mathbb{R}^2$ be a set of $n\ge 2$ distinct points. Let \[ D(A):=\left|\{\,|x-y|:\ x,y\in A,\ x\ne y\,\}\right| \] be the number of distinct Euclidean distances determined by unordered pairs from $A$. Question: does there exist an absolute constant $c>0$ such that for all sufficiently large $n$ and all such $A$, \[ D(A)\ge c\,\frac{n}{\sqrt{\log n}}\ ? \]

QUICK LITERATURE/CONTEXT CHECK. The problem statement notes that a $\sqrt n\times \sqrt n$ integer grid would make the bound $\gg n/\sqrt{\log n}$ best possible, and that Guth--Katz proved the lower bound $\gg n/\log n$. I do not use external results beyond elementary geometry/graph counting.

ATTACK PLAN.

• Proof track: prove a weaker lower bound for $D(A)$ by bounding how many pairs can realise the same distance, and then pigeonholing over distances.
• Disproof track: look for constructions with $o(n/\sqrt{\log n})$ distinct distances; the known grid heuristic suggests this is unlikely.

WORK.

Lemma 89.1 (few pairs at any fixed distance). Fix $r>0$. Let $A\subset\mathbb{R}^2$ with $|A|=n$. Let $U_r(A)$ be the number of unordered pairs $\{x,y\}\subset A$ with $|x-y|=r$. Then \[ U_r(A)\le \frac{\sqrt 2}{2}\,n^{3/2}+\frac14 n. \] Proof. Consider the bipartite graph $G=(L\sqcup R,E)$ where $L$ is a copy of $A$ (viewed as circle centers) and $R$ is another copy of $A$ (viewed as points). Put an edge between $\ell\in L$ (center $x\in A$) and $r\in R$ (point $y\in A$) iff $|x-y|=r$. Then $|L|=|R|=n$ and $|E|$ counts directed distance-$r$ pairs, so \[ |E|=2U_r(A). \]

Claim 1: $G$ is $K_{2,3}$-free. Indeed, take two distinct centers $x_1\ne x_2$ (vertices in $L$). The set of points $y\in A$ that are adjacent to both $x_1$ and $x_2$ are exactly the intersection points of the two circles of radius $r$ centered at $x_1$ and $x_2$. Two distinct circles in the plane intersect in at most two points: subtracting their equations yields a line, which meets a circle in at most two points. Hence $x_1,x_2$ have at most two common neighbors in $R$, so there cannot be three points adjacent to both, i.e. no $K_{2,3}$.

Claim 2 (a concrete Kővári--Sós--Turán bound for $K_{2,3}$-free graphs): If a bipartite graph has parts of size $n$ and is $K_{2,3}$-free, then \[ |E|\le \sqrt 2\,n^{3/2}+\frac12 n. \] Proof of Claim 2. Let the degrees of vertices on the right side be $d_1,\dots,d_n$ so that $\sum_{i=1}^n d_i=|E|$. For a right vertex with degree $d_i$, the number of unordered pairs of its left neighbors is $\binom{d_i}{2}$. Summing over $R$ counts, for each unordered left pair $\{u,v\}$, the number of common right neighbors. Since the graph is $K_{2,3}$-free, any left pair has at most $2$ common right neighbors, so \[ \sum_{i=1}^n \binom{d_i}{2} \le 2\binom{n}{2}=n(n-1). \] Rewrite the left-hand side as \[ \sum_{i=1}^n \binom{d_i}{2}= \frac12\sum_{i=1}^n(d_i^2-d_i) = \frac12\left(\sum_{i=1}^n d_i^2\right)-\frac12|E|. \] By Cauchy--Schwarz, \[ \sum_{i=1}^n d_i^2 \ge \frac1n\left(\sum_{i=1}^n d_i\right)^2 = \frac{|E|^2}{n}. \] Therefore \[ \frac12\left(\frac{|E|^2}{n}\right)-\frac12|E| \le n(n-1) \le n^2, \] which implies $|E|^2 - n|E| -2n^3\le 0$. Solving this quadratic inequality in $|E|$ gives \[ |E|\le \frac{n+\sqrt{n^2+8n^3}}{2}\le \frac{n+\sqrt{8}\,n^{3/2}}{2}=\sqrt 2\,n^{3/2}+\frac12 n. \] This proves Claim 2.

Combining Claim 1 and Claim 2 yields $|E|\le \sqrt 2\,n^{3/2}+\tfrac12 n$, hence \[ U_r(A)=\frac{|E|}{2}\le \frac{\sqrt 2}{2}\,n^{3/2}+\frac14 n. \] $\square$

Lemma 89.2 (a weak distinct-distance lower bound). For every finite $A\subset\mathbb{R}^2$ with $|A|=n\ge 2$, \[ D(A)\ge \frac{n-1}{\sqrt 2\,\sqrt n+\tfrac12}\,\sqrt n \ge \frac{1}{2\sqrt 2}\,\sqrt n\quad\text{for }n\ge 4. \] In particular $D(A)=\Omega(\sqrt n)$. Proof. Let the distinct distance values determined by $A$ be $r_1,\dots,r_m$ where $m=D(A)$. Then every unordered pair of distinct points contributes to exactly one $U_{r_i}(A)$, so \[ \binom{n}{2} = \sum_{i=1}^m U_{r_i}(A). \] By Lemma 89.1, each $U_{r_i}(A)\le \tfrac{\sqrt2}{2}n^{3/2}+\tfrac14 n$. Hence \[ \binom{n}{2}\le m\left(\frac{\sqrt2}{2}n^{3/2}+\frac14 n\right), \] so \[ D(A)=m\ge \frac{n(n-1)/2}{(\sqrt2/2)n^{3/2}+n/4} =\frac{n-1}{\sqrt2\,\sqrt n+1/2}\,\sqrt n. \] For $n\ge 4$, the denominator satisfies $\sqrt2\,\sqrt n+1/2\le 2\sqrt2\,\sqrt n$, giving $m\ge \tfrac1{2\sqrt2}\sqrt n$. $\square$

FAST REALITY CHECK (integer grids). For an $N\times N$ integer grid ($n=N^2$ points), the distinct squared distances are exactly the distinct values of $a^2+b^2$ with $0\le a,b\le N-1$ not both zero. A quick computation gave:

N=2  n=4     D=2
N=3  n=9     D=5
N=4  n=16    D=9
N=5  n=25    D=14
N=10 n=100   D=50
N=20 n=400   D=179
N=50 n=2500  D=992
N=100 n=10000 D=3663

VERIFICATION.

• Circle intersection: two radius-$r$ circles are either disjoint, tangent, or meet in exactly two points; never three.
• $K_{2,3}$-free implication: a $K_{2,3}$ in the incidence graph would force two circles to share three points, contradicting the previous fact.
• Algebra in Claim 2: checked the quadratic inequality and the step $n(n-1)\le n^2$.
• Distinct-distance pigeonhole: the decomposition $\binom{n}{2}=\sum U_{r_i}$ holds because each pair has exactly one distance.

FINAL. UNRESOLVED

1. (i) Strongest proved partial result. For every $A\subset\mathbb{R}^2$ with $|A|=n$, one has $D(A)=\Omega(\sqrt n)$ (Lemma 89.2), via the concrete bound $U_r(A)=O(n^{3/2})$ for pairs at any fixed distance $r$ (Lemma 89.1).
2. (ii) First gap (crisp). Improve the exponent from $1/2$ to $1$ up to logarithmic factors: prove that $D(A)\ge c\,n/\sqrt{\log n}$ for all sufficiently large $n$.
3. (iii) Top 3 next moves.
   • Strengthen Lemma 89.1 to an upper bound $U_r(A)=O(n^{4/3})$ (or better) using incidence geometry beyond the $K_{2,3}$ extremal graph argument.
   • Prove a multi-distance energy inequality: bound $\sum_r U_r(A)^2$ (or related additive energy) to control distance multiplicities more sharply.
   • Compute/experiment with candidate near-extremal sets (integer grids, "perturbed" grids, circular arcs) to identify structural features that force many repeated distances.
4. (iv) Likely structure of a minimal counterexample. A hypothetical set $A$ with unusually small $D(A)$ must have many repeated distances, i.e. large $U_r(A)$ for many radii $r$. This suggests a highly structured configuration with many integer-like constraints (e.g. many points in approximate lattice position), rather than a generic or random configuration where almost all distances are distinct.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. Let $A\subset\mathbb R^2$ be a set of $n$ distinct points. Let \[D(A):=\big|\{|x-y|: x,y\in A,\ x\ne y\}\big|\] be the number of distinct Euclidean distances determined by unordered pairs of points of $A$.

Question. Is it true that for all $n$ and all $|A|=n$ one has \[D(A)\ \gg\ \frac{n}{\sqrt{\log n}}?\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the statement only: - Guth--Katz proved $D(A)\gg n/\log n$. I do not re-prove that deep result here.

3) ATTACK PLAN Proof track ideas: 1. Use the standard energy/Cauchy--Schwarz reduction: distinct distances are large if no distance occurs too many times. 2. Bound the number of repeated distances via incidence geometry (point-circle incidences); the full problem uses sophisticated polynomial methods.

Disproof track ideas: 1. Try to build configurations with very few distinct distances; the integer grid is the classical near-extremizer.

Chosen path in this attempt: provide a fully proved warm-up bound $D(A)\gg \sqrt n$ using a Kővári--Sós--Turán argument for repeated distances at a fixed radius.

4) WORK Lemma 1 (Kővári--Sós--Turán for $K_{2,3}$-free bipartite graphs; a usable form). Let $B$ be a bipartite graph with left part $L$ and right part $R$, where $|L|=|R|=n$. Assume $B$ contains no copy of $K_{2,3}$ with the two-vertex side in $L$ and the three-vertex side in $R$ (equivalently, any two vertices in $L$ have at most $2$ common neighbors in $R$). Then \[e(B)\le 2n^{3/2}+2n.\]

Proof. Let the degrees of left vertices be $d(\ell)$ for $\ell\in L$. Count length-2 paths $\ell-r-\ell'$ with $\ell\ne \ell'$ and $r\in R$. For a fixed $r\in R$, the number of unordered pairs of distinct neighbors of $r$ in $L$ is $\binom{d(r)}{2}$, so the total number of such 2-paths equals \[P:=\sum_{r\in R}\binom{d(r)}{2}.\tag{1}\] On the other hand, for each unordered pair $\{\ell,\ell'\}\subseteq L$, the number of common neighbors in $R$ is at most $2$ by the $K_{2,3}$-free assumption. Thus each pair $\{\ell,\ell'\}$ contributes at most $2$ to $P$, so \[P\le 2\binom{n}{2} < n^2.\tag{2}\]

Now relate $P$ to the total edge count $e=e(B)$. By convexity (or Cauchy--Schwarz), $\sum_{r\in R} d(r)^2 \ge e^2/n$ since $\sum_{r} d(r)=e$. Also $\binom{d}{2}=\frac{d^2-d}{2}$, so \[P=\sum_{r}\binom{d(r)}{2}=\frac12\sum_r d(r)^2 - \frac12\sum_r d(r)\ge \frac12\cdot \frac{e^2}{n}-\frac12 e.\tag{3}\] Combine $2$ and $3$: \[\frac{e^2}{2n}-\frac{e}{2} \le n^2.\] Multiply by $2n$: \[e^2 - en \le 2n^3.\] Complete the square: $(e-\tfrac{n}{2})^2 \le 2n^3 + \tfrac{n^2}{4} \le (2n^{3/2}+n)^2$ for $n\ge 1$. Thus $e-\tfrac{n}{2}\le 2n^{3/2}+n$, i.e. $e\le 2n^{3/2}+\tfrac{3n}{2}<2n^{3/2}+2n$. $\square$

Lemma 2 (Warm-up distinct-distance bound $D(A)\gg \sqrt n$). For any set $A$ of $n$ points in $\mathbb R^2$, \[D(A)\ \ge\ c\,\sqrt n\] for an absolute constant $c>0$.

Proof. For a distance value $r>0$, let $m_r$ be the number of unordered pairs $\{x,y\}\subset A$ with $|x-y|=r$. Then \[\sum_r m_r = \binom{n}{2}.\tag{4}\] It suffices to show that every $m_r\ll n^{3/2}$, because then \[\binom{n}{2}=\sum_r m_r \le D(A)\cdot \max_r m_r \ll D(A)\,n^{3/2},\] giving $D(A)\gg n^2/n^{3/2}=\sqrt n$.

Fix $r>0$. Build a bipartite graph $B_r$ with left part $L=A$ (centers) and right part $R=A$ (points), and draw an edge from $x\in L$ to $y\in R$ iff $|x-y|=r$. Then $e(B_r)=2m_r$ (each unordered pair contributes two directed edges).

Key geometric fact: any two circles in the plane intersect in at most $2$ points. Thus for two distinct centers $x\ne x'$, the circles of radius $r$ around $x$ and $x'$ have at most two intersection points, meaning $x$ and $x'$ have at most $2$ common neighbors in $R$. Equivalently, $B_r$ is $K_{2,3}$-free in the sense of Lemma 1. Therefore Lemma 1 gives \[2m_r=e(B_r)\le 2n^{3/2}+2n,\] so $m_r\le n^{3/2}+n$ for every $r$. Substitute into $4$ to conclude $D(A)\ge \binom{n}{2}/(n^{3/2}+n)\gg \sqrt n$. $\square$

FAST REALITY CHECK The desired bound is $D(A)\gg n/\sqrt{\log n}$, much stronger than the $\Omega(\sqrt n)$ bound proved here. The $\Omega(\sqrt n)$ bound matches what one would get from the "easy" $O(n^{3/2})$ unit-distance bound; improving beyond that requires deep incidence geometry.

5) VERIFICATION - Lemma 1: the only structural assumption used is "any two left vertices have at most 2 common neighbors," which is exactly the $K_{2,3}$-free condition. - Lemma 2: the geometric input "two circles meet in at most 2 points" is correct, and the translation to the bipartite graph $B_r$ is explicit.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved the warm-up bound $D(A)\gg \sqrt n$ for all $n$-point sets in the plane (Lemma 2).

(ii) First gap: Bound the number of repeated distances more sharply than $O(n^{3/2})$ per distance, or control the sum of squared multiplicities $\sum_r m_r^2$ well enough to upgrade Cauchy--Schwarz to $n/\sqrt{\log n}$.

(iii) Top 3 next moves (concrete): 1. Use the Cauchy--Schwarz framework $D(A)\ge \binom{n}{2}^2 / \sum_r m_r^2$ and attempt to bound $\sum_r m_r^2$ via incidence bounds between points and circles. 2. Specialize to structured candidate extremizers (integer grids) and understand their distance multiplicities; attempt to prove the $n/\sqrt{\log n}$ upper behavior for grids (number theory of sums of two squares). 3. Explore whether stronger forbidden-subgraph conditions (e.g. no three collinear, no four concyclic) allow sharper incidence bounds as a stepping stone (cf. Problem #98).

(iv) What a minimal counterexample would likely look like (structure/parameters): A family of point sets $A_n$ with $|A_n|=n$ such that the number of distinct distances $D(A_n)$ is $o\!\left(n/\sqrt{\log n}\right)$, meaning that many distances are repeated with unusually high multiplicity across $\Theta(n^2)$ pairs.