Erdős Problem #670

Erdős Problem 670 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/670

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/670.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/670.tex.

FORMAL RESTATEMENT. Fix $d\ge 1$. For a finite set $A\subseteq\mathbb{R}^d$ of size $n$, define its diameter \[\operatorname{diam}(A):=\max\{\|x-y\|: x,y\in A\}. \] Assume that for any two distinct unordered pairs $\{x,y\}\ne\{x',y'\}$ with $x\ne y$ and $x'\ne y'$, the corresponding distances satisfy \[\big|\|x-y\| - \|x'-y'\|\big|\ge 1. \] (Equivalently: the multiset of $\binom{n}{2}$ pairwise distances is $1$-separated.) The conjecture asks whether necessarily \[ \operatorname{diam}(A) \ge (1+o(1))\, n^2\quad\text{as } n\to\infty. \]

Potential ambiguity. The phrase "all pairwise distances differ by at least $1$" is interpreted above as a separation condition between distances of distinct pairs. This is consistent with the statement that the trivial diameter lower bound is $\binom n2$ (see Lemma 670.2).

QUICK LITERATURE/CONTEXT CHECK. The prompt states that the lower bound $\binom n2$ is trivial and that Erdős proved the $(1+o(1))n^2$ lower bound for $d=1$. Per project rules, I do not use external sources beyond this.

ATTACK PLAN.

• Prove the "trivial" lower bound $\operatorname{diam}(A)\ge \binom n2$ carefully, including the necessary preliminary fact that the minimum distance is at least $1$ when $n\ge 3$.
• Do small-$n$ checks and a computation in $d=1$ (Golomb ruler search) to see the gap between $\binom n2$ and the known/expected $\Theta(n^2)$ behavior.
• No general improvement beyond $\binom n2$ is proved here for $d\ge 2$; conclude unresolved.

WORK.

Fast reality check (tiny $n$). For $n=2$, there is only one distance, so the separation condition is vacuous; the diameter can be any positive number. For $n=3$, one can realize distances $\{1,2,3\}$ by collinear points at $0,1,3$ in $\mathbb{R}$, giving diameter $3=\binom 32$. For $n=4$, collinear points at $0,1,4,6$ realize all distances $1,2,3,4,5,6$, giving diameter $6=\binom 42$. So the trivial bound can be tight for small $n$.

Lemma 670.1 (Minimum distance is at least $1$ for $n\ge 3$). Let $A\subseteq\mathbb{R}^d$ be a set of $n\ge 3$ points satisfying the distance-separation condition. Then the minimum pairwise distance in $A$ is at least $1$.

Proof. Let $\delta$ be the minimum distance between distinct points of $A$, and choose distinct points $P,Q\in A$ with $\|P-Q\|=\delta$. Since $n\ge 3$, choose a third point $R\in A\setminus\{P,Q\}$. The distances $\|P-R\|$ and $\|Q-R\|$ correspond to distinct unordered pairs from $\{P,Q\}$, so each must differ from $\delta$ by at least $1$. Also, by minimality of $\delta$, both are at least $\delta$. Therefore \[ \|P-R\|\ge \delta+1,\qquad \|Q-R\|\ge \delta+1. \] Moreover, since the unordered pairs $\{P,R\}$ and $\{Q,R\}$ are distinct, the separation condition gives $|\|P-R\|-\|Q-R\||\ge 1$. Thus one of these two distances is at least the other plus $1$. Without loss of generality assume $\|Q-R\|\ge \|P-R\|+1$. Then combining with $\|P-R\|\ge \delta+1$ yields \[\|Q-R\|\ge (\delta+1)+1 = \delta+2. \] Now apply the triangle inequality in $\mathbb{R}^d$ to the triangle $PQR$: \[ \|Q-R\| \le \|Q-P\| + \|P-R\| = \delta + \|P-R\|. \] Using $\|Q-R\|\ge \|P-R\|+1$ gives \[ \|P-R\|+1 \le \delta + \|P-R\|, \] so $1\le \delta$. Therefore the minimum distance $\delta\ge 1$. $\square$

Lemma 670.2 (Trivial diameter lower bound). Let $A\subseteq\mathbb{R}^d$ be a set of $n\ge 3$ points satisfying the distance-separation condition. Then \[ \operatorname{diam}(A)\ge \binom{n}{2}. \]

Proof. There are $N:=\binom{n}{2}$ unordered pairs of distinct points in $A$, hence $N$ pairwise distances. Let these distances be listed in increasing order: \[d_1<d_2<\cdots<d_N. \] The separation condition says that for any two distinct distances in this list, their difference is at least $1$. In particular, consecutive distances satisfy $d_{i+1}-d_i\ge 1$ for each $i$. Summing these inequalities yields \[ d_N - d_1 = \sum_{i=1}^{N-1} (d_{i+1}-d_i) \ge N-1. \] By Lemma 670.1, $d_1\ge 1$. Therefore $d_N\ge 1+(N-1)=N=\binom n2$. Since $d_N$ is one of the pairwise distances, it is at most the diameter, i.e. $d_N\le \operatorname{diam}(A)$. Hence $\operatorname{diam}(A)\ge \binom n2$. $\square$

Computation in $d=1$ (optimal integer Golomb rulers for $n\le 7$). In one dimension, taking integer points $0=x_1<\dots<x_n=L$ with all pairwise differences distinct automatically satisfies the "distance differences $\ge 1$" condition. I brute-forced the smallest possible $L$ for $n\le 7$ (optimal Golomb rulers), obtaining:

n=2: L=1,  marks (0,1)
n=3: L=3,  marks (0,1,3)
n=4: L=6,  marks (0,1,4,6)
n=5: L=11, marks (0,1,4,9,11)
n=6: L=17, marks (0,1,4,10,12,17)
n=7: L=25, marks (0,1,4,10,18,23,25)

These illustrate that the diameter can equal $\binom n2$ for $n\le 4$ but must exceed it for $n\ge 5$ in $d=1$.

VERIFICATION.

• Lemma 670.1: checked that it uses $n\ge 3$ essentially (to pick a third point $R$). For $n=2$ the claim is false since there is no constraint.
• Lemma 670.2: verified that the ordering argument uses only the pairwise distance separation and Lemma 670.1.
• Small-$n$ examples: $\{0,1,3\}$ gives distances $\{1,2,3\}$ and separation $\ge 1$; $\{0,1,4,6\}$ gives distances $\{1,2,3,4,5,6\}$.

FINAL. UNRESOLVED.

(i) Strongest proved partial results.

• For any $d$ and any $n\ge 3$, the minimum pairwise distance is at least $1$ (Lemma 670.1).
• Consequently, for any $d$ and any $n\ge 3$, the diameter satisfies $\operatorname{diam}(A)\ge \binom n2$ (Lemma 670.2), matching the "trivial" bound stated in the prompt.
• In $d=1$, small-$n$ computations show the optimal diameter equals $\binom n2$ for $n\le 4$ and exceeds it for $n\ge 5$.

(ii) First gap (crisp statement). For fixed $d\ge 2$, prove or disprove the asymptotic lower bound \[ \operatorname{diam}(A) \ge (1+o(1))\,n^2 \] for every $n$-point set $A\subseteq\mathbb{R}^d$ whose pairwise distances are $1$-separated.

(iii) Top 3 next moves.

1. Dimension reduction attempt: prove that any such $A$ contains a large subset whose points are "almost collinear" in a quantitative sense, reducing to the $d=1$ phenomenon.
2. Geometric constraints on distance sets: exploit triangle inequalities across many triples to show that the $\binom n2$ distances cannot be packed into an interval of length $\approx \binom n2$, forcing diameter strictly larger by a linear factor.
3. Construction search in $d\ge 2$: attempt to build explicit families in $\mathbb{R}^2$ or $\mathbb{R}^3$ with diameter close to the trivial lower bound $\binom n2$, which would refute the conjectured $(1+o(1))n^2$ bound.

(iv) What a minimal counterexample would likely look like. A counterexample (if the conjecture is false) would be a sequence of point sets $A_n\subset\mathbb{R}^d$ with $|A_n|=n$ such that:

• the $\binom n2$ pairwise distances are all distinct and $1$-separated, but
• the diameter satisfies $\operatorname{diam}(A_n) \le (c+o(1))n^2$ with some constant $c<1$ (ideally $c\approx 1/2$, matching the trivial lower bound up to lower order).

Such a construction would have to realize the distance multiset with unusually "tight packing" compatible with triangle inequalities in fixed dimension.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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

FORMAL RESTATEMENT. Fix $d\ge 1$. For a finite set $A\subseteq\mathbb{R}^d$ of size $n$, define its diameter \[\operatorname{diam}(A):=\max\{\|x-y\|: x,y\in A\}. \] Assume that for any two distinct unordered pairs $\{x,y\}\ne\{x',y'\}$ with $x\ne y$ and $x'\ne y'$, the corresponding distances satisfy \[\big|\|x-y\| - \|x'-y'\|\big|\ge 1. \] (Equivalently: the multiset of $\binom{n}{2}$ pairwise distances is $1$-separated.) The conjecture asks whether necessarily \[ \operatorname{diam}(A) \ge (1+o(1))\, n^2\quad\text{as } n\to\infty. \]

Potential ambiguity. The phrase "all pairwise distances differ by at least $1$" is interpreted above as a separation condition between distances of distinct pairs. This is consistent with the statement that the trivial diameter lower bound is $\binom n2$ (see Lemma 670.2).

QUICK LITERATURE/CONTEXT CHECK. The prompt states that the lower bound $\binom n2$ is trivial and that Erdős proved the $(1+o(1))n^2$ lower bound for $d=1$. Per project rules, I do not use external sources beyond this.

ATTACK PLAN.

• Prove the "trivial" lower bound $\operatorname{diam}(A)\ge \binom n2$ carefully, including the necessary preliminary fact that the minimum distance is at least $1$ when $n\ge 3$.
• Do small-$n$ checks and a computation in $d=1$ (Golomb ruler search) to see the gap between $\binom n2$ and the known/expected $\Theta(n^2)$ behavior.
• No general improvement beyond $\binom n2$ is proved here for $d\ge 2$; conclude unresolved.

WORK.

Fast reality check (tiny $n$). For $n=2$, there is only one distance, so the separation condition is vacuous; the diameter can be any positive number. For $n=3$, one can realize distances $\{1,2,3\}$ by collinear points at $0,1,3$ in $\mathbb{R}$, giving diameter $3=\binom 32$. For $n=4$, collinear points at $0,1,4,6$ realize all distances $1,2,3,4,5,6$, giving diameter $6=\binom 42$. So the trivial bound can be tight for small $n$.

Lemma 670.1 (Minimum distance is at least $1$ for $n\ge 3$). Let $A\subseteq\mathbb{R}^d$ be a set of $n\ge 3$ points satisfying the distance-separation condition. Then the minimum pairwise distance in $A$ is at least $1$.

Proof. Let $\delta$ be the minimum distance between distinct points of $A$, and choose distinct points $P,Q\in A$ with $\|P-Q\|=\delta$. Since $n\ge 3$, choose a third point $R\in A\setminus\{P,Q\}$. The distances $\|P-R\|$ and $\|Q-R\|$ correspond to distinct unordered pairs from $\{P,Q\}$, so each must differ from $\delta$ by at least $1$. Also, by minimality of $\delta$, both are at least $\delta$. Therefore \[ \|P-R\|\ge \delta+1,\qquad \|Q-R\|\ge \delta+1. \] Moreover, since the unordered pairs $\{P,R\}$ and $\{Q,R\}$ are distinct, the separation condition gives $|\|P-R\|-\|Q-R\||\ge 1$. Thus one of these two distances is at least the other plus $1$. Without loss of generality assume $\|Q-R\|\ge \|P-R\|+1$. Then combining with $\|P-R\|\ge \delta+1$ yields \[\|Q-R\|\ge (\delta+1)+1 = \delta+2. \] Now apply the triangle inequality in $\mathbb{R}^d$ to the triangle $PQR$: \[ \|Q-R\| \le \|Q-P\| + \|P-R\| = \delta + \|P-R\|. \] Using $\|Q-R\|\ge \|P-R\|+1$ gives \[ \|P-R\|+1 \le \delta + \|P-R\|, \] so $1\le \delta$. Therefore the minimum distance $\delta\ge 1$. $\square$

Lemma 670.2 (Trivial diameter lower bound). Let $A\subseteq\mathbb{R}^d$ be a set of $n\ge 3$ points satisfying the distance-separation condition. Then \[ \operatorname{diam}(A)\ge \binom{n}{2}. \]

Proof. There are $N:=\binom{n}{2}$ unordered pairs of distinct points in $A$, hence $N$ pairwise distances. Let these distances be listed in increasing order: \[d_1<d_2<\cdots<d_N. \] The separation condition says that for any two distinct distances in this list, their difference is at least $1$. In particular, consecutive distances satisfy $d_{i+1}-d_i\ge 1$ for each $i$. Summing these inequalities yields \[ d_N - d_1 = \sum_{i=1}^{N-1} (d_{i+1}-d_i) \ge N-1. \] By Lemma 670.1, $d_1\ge 1$. Therefore $d_N\ge 1+(N-1)=N=\binom n2$. Since $d_N$ is one of the pairwise distances, it is at most the diameter, i.e. $d_N\le \operatorname{diam}(A)$. Hence $\operatorname{diam}(A)\ge \binom n2$. $\square$

Computation in $d=1$ (optimal integer Golomb rulers for $n\le 7$). In one dimension, taking integer points $0=x_1<\dots<x_n=L$ with all pairwise differences distinct automatically satisfies the "distance differences $\ge 1$" condition. I brute-forced the smallest possible $L$ for $n\le 7$ (optimal Golomb rulers), obtaining:

n=2: L=1,  marks (0,1)
n=3: L=3,  marks (0,1,3)
n=4: L=6,  marks (0,1,4,6)
n=5: L=11, marks (0,1,4,9,11)
n=6: L=17, marks (0,1,4,10,12,17)
n=7: L=25, marks (0,1,4,10,18,23,25)

These illustrate that the diameter can equal $\binom n2$ for $n\le 4$ but must exceed it for $n\ge 5$ in $d=1$.

VERIFICATION.

• Lemma 670.1: checked that it uses $n\ge 3$ essentially (to pick a third point $R$). For $n=2$ the claim is false since there is no constraint.
• Lemma 670.2: verified that the ordering argument uses only the pairwise distance separation and Lemma 670.1.
• Small-$n$ examples: $\{0,1,3\}$ gives distances $\{1,2,3\}$ and separation $\ge 1$; $\{0,1,4,6\}$ gives distances $\{1,2,3,4,5,6\}$.

FINAL. UNRESOLVED.

(i) Strongest proved partial results.

• For any $d$ and any $n\ge 3$, the minimum pairwise distance is at least $1$ (Lemma 670.1).
• Consequently, for any $d$ and any $n\ge 3$, the diameter satisfies $\operatorname{diam}(A)\ge \binom n2$ (Lemma 670.2), matching the "trivial" bound stated in the prompt.
• In $d=1$, small-$n$ computations show the optimal diameter equals $\binom n2$ for $n\le 4$ and exceeds it for $n\ge 5$.

(ii) First gap (crisp statement). For fixed $d\ge 2$, prove or disprove the asymptotic lower bound \[ \operatorname{diam}(A) \ge (1+o(1))\,n^2 \] for every $n$-point set $A\subseteq\mathbb{R}^d$ whose pairwise distances are $1$-separated.

(iii) Top 3 next moves.

1. Dimension reduction attempt: prove that any such $A$ contains a large subset whose points are "almost collinear" in a quantitative sense, reducing to the $d=1$ phenomenon.
2. Geometric constraints on distance sets: exploit triangle inequalities across many triples to show that the $\binom n2$ distances cannot be packed into an interval of length $\approx \binom n2$, forcing diameter strictly larger by a linear factor.
3. Construction search in $d\ge 2$: attempt to build explicit families in $\mathbb{R}^2$ or $\mathbb{R}^3$ with diameter close to the trivial lower bound $\binom n2$, which would refute the conjectured $(1+o(1))n^2$ bound.

(iv) What a minimal counterexample would likely look like. A counterexample (if the conjecture is false) would be a sequence of point sets $A_n\subset\mathbb{R}^d$ with $|A_n|=n$ such that:

• the $\binom n2$ pairwise distances are all distinct and $1$-separated, but
• the diameter satisfies $\operatorname{diam}(A_n) \le (c+o(1))n^2$ with some constant $c<1$ (ideally $c\approx 1/2$, matching the trivial lower bound up to lower order).

Such a construction would have to realize the distance multiset with unusually "tight packing" compatible with triangle inequalities in fixed dimension.