Erdős Problem #959

Erdős Problem 959 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/959.tex.

REUSED SOURCE 1

Erdos Problem 959.

1) FORMAL RESTATEMENT. Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points. For each distance $d>0$, let \[ f(d):=\#\{\{x,y\}\subseteq A: \|x-y\|=d\} \] be the number of unordered pairs at distance $d$. List the distinct distances determined by $A$ as $d_1,\dots,d_k$ in nonincreasing order of multiplicity: $f(d_1)\ge f(d_2)\ge\cdots\ge f(d_k)$. The problem asks for the maximum possible size (as a function of $n$) of the gap \[ \max_{A:|A|=n}\left(f(d_1)-f(d_2)\right). \] More generally, for fixed $r\ge 1$ it asks for the maximum gap $f(d_r)-f(d_{r+1})$.

2) QUICK LITERATURE/CONTEXT CHECK. The problem file reports a lower bound $f(d_1)-f(d_2)\gg n\log n$ due to Clemen, Sheffer, and Zahl (arXiv:2203.06481), but this remains open in general.

3) ATTACK PLAN. (A) Build explicit point configurations (e.g. integer grids) and compute the top multiplicities to get baseline lower bounds. (B) Prove exact formulas for multiplicities of specific distances in these configurations. (C) Compare with known lower bounds stated in the problem file.

4) WORK.

FAST REALITY CHECK (integer grids; computed top two distances for small $m$). For the $m\times m$ integer grid (so $n=m^2$), brute force computations gave:

$m=10$ ($n=100$): top squared distance $d_1^2=5$ with multiplicity $288$; second $d_2^2=25$ with multiplicity $268$; gap $20$.

$m=20$ ($n=400$): top squared distance $d_1^2=65$ with multiplicity $1744$; second $d_2^2=25$ with multiplicity $1688$; gap $56$.

These gaps are far smaller than $n\log n$ at these sizes, suggesting grids are not extremal for the asked gap.

Lemma 959.1 (Exact multiplicity of distance $1$ in an $m\times m$ grid). Let $A:=\{0,1,\dots,m-1\}^2\subseteq\mathbb{R}^2$. Then the number of pairs at Euclidean distance $1$ is \[ f(1)=2m(m-1). \]

Proof. Pairs at distance $1$ correspond exactly to horizontal or vertical nearest neighbours. There are $m$ rows, each containing $m-1$ horizontal adjacent pairs, contributing $m(m-1)$. There are $m$ columns, each containing $m-1$ vertical adjacent pairs, contributing another $m(m-1)$. No other pair has distance $1$ in the integer grid. Thus $f(1)=2m(m-1)$. $\square$

Lemma 959.2 (Exact multiplicity of distance $\sqrt{2}$ in an $m\times m$ grid). With $A$ as in Lemma 959.1, the number of pairs at distance $\sqrt{2}$ is \[ f(\sqrt{2})=2(m-1)^2. \]

Proof. Pairs at distance $\sqrt{2}$ correspond exactly to diagonal neighbours with displacement $(\pm 1,\pm 1)$. There are $(m-1)^2$ unit squares in the grid, and each such square contributes exactly two diagonals of length $\sqrt{2}$. Each diagonal is counted once because it lies in exactly one unit square. Hence $f(\sqrt{2})=2(m-1)^2$. $\square$

Corollary 959.3. For the $m\times m$ grid, \[ f(1)-f(\sqrt{2})=2(m-1). \]

Proof. Subtract the explicit formulas from Lemmas 959.1 and 959.2. $\square$

5) VERIFICATION. • Lemmas 959.1 and 959.2 are simple exact counts; they match the brute force check for $m=3$ (where $f(1)=12$ and $f(\sqrt{2})=8$).

6) FINAL. UNRESOLVED. (i) Strongest proved partial result: For the $m\times m$ grid ($n=m^2$), one can compute explicit multiplicities for specific distances, e.g. $f(1)=2m(m-1)$ and $f(\sqrt{2})=2(m-1)^2$, giving a gap $2(m-1)=2\sqrt{n}-2$. (ii) First gap: construct point sets $A$ for which the top gap $f(d_1)-f(d_2)$ is provably superlinear (e.g. $\gg n\log n$) without importing external results beyond those stated in the problem file. (iii) Top 3 next moves: $1$ Analyze lattices and choose radii with unusually many representations as sums of two squares to inflate a single distance multiplicity. $2$ Compare the top two multiplicities in such constructions: show the second-largest distance class is much smaller. $3$ Perform larger computations for candidate extremal constructions suggested by number theory (products of many primes $\equiv 1\pmod 4$, etc.). (iv) Minimal counterexample structure: a point set $A$ where one distance occurs in extremely many pairs while all other distances occur in significantly fewer pairs; in particular, controlling the second-largest multiplicity is essential.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Erdos Problem 959.

1) FORMAL RESTATEMENT. Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points. For each distance $d>0$, let \[ f(d):=\#\{\{x,y\}\subseteq A: \|x-y\|=d\} \] be the number of unordered pairs at distance $d$. List the distinct distances determined by $A$ as $d_1,\dots,d_k$ in nonincreasing order of multiplicity: $f(d_1)\ge f(d_2)\ge\cdots\ge f(d_k)$. The problem asks for the maximum possible size (as a function of $n$) of the gap \[ \max_{A:|A|=n}\left(f(d_1)-f(d_2)\right). \] More generally, for fixed $r\ge 1$ it asks for the maximum gap $f(d_r)-f(d_{r+1})$.

2) QUICK LITERATURE/CONTEXT CHECK. The problem file reports a lower bound $f(d_1)-f(d_2)\gg n\log n$ due to Clemen, Sheffer, and Zahl (arXiv:2203.06481), but this remains open in general.

3) ATTACK PLAN. (A) Build explicit point configurations (e.g. integer grids) and compute the top multiplicities to get baseline lower bounds. (B) Prove exact formulas for multiplicities of specific distances in these configurations. (C) Compare with known lower bounds stated in the problem file.

4) WORK.

FAST REALITY CHECK (integer grids; computed top two distances for small $m$). For the $m\times m$ integer grid (so $n=m^2$), brute force computations gave:

$m=10$ ($n=100$): top squared distance $d_1^2=5$ with multiplicity $288$; second $d_2^2=25$ with multiplicity $268$; gap $20$.

$m=20$ ($n=400$): top squared distance $d_1^2=65$ with multiplicity $1744$; second $d_2^2=25$ with multiplicity $1688$; gap $56$.

These gaps are far smaller than $n\log n$ at these sizes, suggesting grids are not extremal for the asked gap.

Lemma 959.1 (Exact multiplicity of distance $1$ in an $m\times m$ grid). Let $A:=\{0,1,\dots,m-1\}^2\subseteq\mathbb{R}^2$. Then the number of pairs at Euclidean distance $1$ is \[ f(1)=2m(m-1). \]

Proof. Pairs at distance $1$ correspond exactly to horizontal or vertical nearest neighbours. There are $m$ rows, each containing $m-1$ horizontal adjacent pairs, contributing $m(m-1)$. There are $m$ columns, each containing $m-1$ vertical adjacent pairs, contributing another $m(m-1)$. No other pair has distance $1$ in the integer grid. Thus $f(1)=2m(m-1)$. $\square$

Lemma 959.2 (Exact multiplicity of distance $\sqrt{2}$ in an $m\times m$ grid). With $A$ as in Lemma 959.1, the number of pairs at distance $\sqrt{2}$ is \[ f(\sqrt{2})=2(m-1)^2. \]

Proof. Pairs at distance $\sqrt{2}$ correspond exactly to diagonal neighbours with displacement $(\pm 1,\pm 1)$. There are $(m-1)^2$ unit squares in the grid, and each such square contributes exactly two diagonals of length $\sqrt{2}$. Each diagonal is counted once because it lies in exactly one unit square. Hence $f(\sqrt{2})=2(m-1)^2$. $\square$

Corollary 959.3. For the $m\times m$ grid, \[ f(1)-f(\sqrt{2})=2(m-1). \]

Proof. Subtract the explicit formulas from Lemmas 959.1 and 959.2. $\square$

5) VERIFICATION. • Lemmas 959.1 and 959.2 are simple exact counts; they match the brute force check for $m=3$ (where $f(1)=12$ and $f(\sqrt{2})=8$).

6) FINAL. UNRESOLVED. (i) Strongest proved partial result: For the $m\times m$ grid ($n=m^2$), one can compute explicit multiplicities for specific distances, e.g. $f(1)=2m(m-1)$ and $f(\sqrt{2})=2(m-1)^2$, giving a gap $2(m-1)=2\sqrt{n}-2$. (ii) First gap: construct point sets $A$ for which the top gap $f(d_1)-f(d_2)$ is provably superlinear (e.g. $\gg n\log n$) without importing external results beyond those stated in the problem file. (iii) Top 3 next moves: $1$ Analyze lattices and choose radii with unusually many representations as sums of two squares to inflate a single distance multiplicity. $2$ Compare the top two multiplicities in such constructions: show the second-largest distance class is much smaller. $3$ Perform larger computations for candidate extremal constructions suggested by number theory (products of many primes $\equiv 1\pmod 4$, etc.). (iv) Minimal counterexample structure: a point set $A$ where one distance occurs in extremely many pairs while all other distances occur in significantly fewer pairs; in particular, controlling the second-largest multiplicity is essential.