Erdős Problem #660

Erdős Problem 660 --- 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 with TeX syntax corrections for display.

TeX syntax corrected for display; mathematical content unchanged.

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

REUSED SOURCE 1

Let $x_1,\ldots,x_n\in \mathbb{R}^3$ be the vertices of a convex polyhedron. Are there at least\[(1-o(1))\frac{n}{2}\]many distinct distances between the $x_i$? For the similar problem in $\mathbb{R}^2$ there are always at least $n/2$ distances, as proved by Altman [Al63] (see [93] ). In [Er75f] Erdős claims that Altman proved that the vertices determine $\gg n$ many distinct distances, but gives no reference. References [Al63] Altman, E., On a problem of P. Erdős . Amer. Math. Monthly $1963$, 148-157. [Er75f] Erdős, Paul, On some problems of elementary and combinatorial geometry . Ann. Mat. Pura Appl. $4$ $1975$, 99-108.

1) FORMAL RESTATEMENT Let $n\ge 4$ and let $x_1,\ldots,x_n\in\mathbb{R}^3$ be the vertices of a convex polyhedron, i.e. each $x_i$ is a vertex (extreme point) of $\mathrm{conv}(\{x_1,\ldots,x_n\})$. Let \[ D:=\left|\left\{|x_i-x_j|:1\le i<j\le n\right\}\right| \] be the number of distinct interpoint distances. Question: must we have \[ D\ \ge\ (1-o(1))\frac{n}{2}\qquad\text{as }n\to\infty\ ? \]

Edge cases: for $n=4$ a regular tetrahedron has $D=1$, so the asymptotic claim is not meant for small $n$.

2) QUICK LITERATURE/CONTEXT CHECK The problem statement mentions that in $\mathbb{R}^2$ the vertices of a convex polygon always determine at least $n/2$ distinct distances (Altman). I do not assume any external theorems beyond what is stated.

3) ATTACK PLAN Proof-track ideas: - Use convexity to get many distinct distances from a well-chosen vertex (analogue of planar convex-position problems). - Use global algebraic methods to show that few distinct distances force $n$ to be small ("few-distance sets" methods).

Disproof-track ideas: - Construct large convex polyhedra with only $o(n)$ distinct distances, e.g. by placing vertices on few spheres/circles with high symmetry.

I cannot reach the conjectured linear bound; I can prove a general lower bound $D=\Omega(n^{1/3})$ valid for all point sets in $\mathbb{R}^3$.

4) WORK

Lemma 1 (equidistant sets in $\mathbb{R}^3$ have size at most $4$). If $P=\{p_1,\ldots,p_m\}\subset\mathbb{R}^3$ satisfies $|p_i-p_j|=\lambda$ for all $i\neq j$, then $m\le 4$.

Proof. Translate so that $p_m=0$. Let $v_i:=p_i$ for $i=1,\ldots,m-1$. Then $|v_i|^2=\lambda^2$ for all $i$ and $|v_i-v_j|^2=\lambda^2$ for $i\neq j$. Expanding gives $|v_i|^2+|v_j|^2-2v_i\cdot v_j=\lambda^2$, hence $2\lambda^2-2v_i\cdot v_j=\lambda^2$, so $v_i\cdot v_j=\lambda^2/2$ for all $i\neq j$. Form the Gram matrix $G=(v_i\cdot v_j)_{1\le i,j\le m-1}$. It has diagonal entries $\lambda^2$ and off-diagonal entries $\lambda^2/2$, so $G=\frac{\lambda^2}{2}(J_{m-1}+I_{m-1})$, where $J$ is the all-ones matrix. The eigenvalues of $J_{m-1}$ are $(m-1)$ (once) and $0$ (multiplicity $m-2$). Therefore the eigenvalues of $G$ are $\frac{\lambda^2}{2}(m)$ (once) and $\frac{\lambda^2}{2}$ (multiplicity $m-2$), all nonzero. Hence $\mathrm{rank}(G)=m-1$. But $\mathrm{rank}(G)\le 3$ because $G$ is the Gram matrix of vectors in $\mathbb{R}^3$. Thus $m-1\le 3$ and $m\le 4$. $\square$

Lemma 2 (a polynomial method bound for distance sets in $\mathbb{R}^3$). Let $P=\{p_1,\ldots,p_n\}\subset\mathbb{R}^3$ and let $D(P)$ be the number of distinct distances among pairs. Then \[ n\ \le\ \binom{2D(P)+3}{3}. \] In particular, $D(P)\ge c\,n^{1/3}$ for an absolute constant $c>0$.

Proof. Let $\Delta$ be the set of distinct squared distances determined by $P$: $\Delta:=\{|p_i-p_j|^2:1\le i<j\le n\}$, so $|\Delta|=D(P)$. For each $i$, define a polynomial in three variables \[ F_i(x):=\prod_{t\in\Delta}\left(\|x-p_i\|^2-t\right),\qquad x\in\mathbb{R}^3. \] Each factor has degree $2$, so $\deg(F_i)\le 2|\Delta|=2D(P)$. Evaluate at the points $p_j$: if $j\neq i$, then $\|p_j-p_i\|^2\in\Delta$, so one factor vanishes and hence $F_i(p_j)=0$. On the other hand, $F_i(p_i)=\prod_{t\in\Delta}(-t)\neq 0$ because all $t\in\Delta$ are positive. Thus the $n\times n$ matrix $M=(F_i(p_j))_{i,j}$ is diagonal with nonzero diagonal entries, so $\mathrm{rank}(M)=n$. Let $V$ be the real vector space of polynomials in $(x_1,x_2,x_3)$ of total degree at most $2D(P)$. The rows of $M$ lie in the image of the evaluation map $\mathrm{ev}:V\to\mathbb{R}^n$, $F\mapsto (F(p_1),\ldots,F(p_n))$. Therefore $n=\dim(\mathrm{span}\{\text{rows of }M\})\le \dim(\mathrm{im}(\mathrm{ev}))\le \dim(V)$. It remains to compute $\dim(V)$. A monomial $x_1^{a}x_2^{b}x_3^{c}$ has total degree $a+b+c\le 2D(P)$. The number of triples $(a,b,c)\in\mathbb{Z}_{\ge 0}^3$ with $a+b+c\le m$ equals $\binom{m+3}{3}$ (stars-and-bars, summing over $a+b+c=r$). With $m=2D(P)$ this gives $\dim(V)=\binom{2D(P)+3}{3}$, proving the bound. The final asymptotic $D(P)\ge c\,n^{1/3}$ follows because $\binom{2D+3}{3}=O(D^3)$. $\square$

Corollary 3 (applies to the convex-polyhedron case). If $x_1,\ldots,x_n$ are vertices of a convex polyhedron in $\mathbb{R}^3$, then $D\ge c\,n^{1/3}$. (This is immediate from Lemma 2 because it assumes no convexity.)

FAST REALITY CHECK (small cases on the integer grid). I searched subsets of the $3\times 3\times 3$ grid $\{0,1,2\}^3$ and required that all points be vertices of their convex hull. Minimized the number of distinct squared distances (this equals the number of distinct distances). Witnesses: - $n=4$: minimum found $D=1$, achieved by $\{(0,0,0), (0,1,1), (1,0,1), (1,1,0)\}$ (a regular tetrahedron of edge length $\sqrt 2$). - $n=5$: minimum found $D=2$, achieved by $\{(0,0,1), (0,1,0), (0,1,2), (0,2,1), (1,1,1)\}$. Random search in $\{0,1,2,3\}^3$ (30k samples each) found: - $n=6$: $D=3$ with $\{(2,1,0), (1,2,0), (1,1,1), (0,2,1), (1,2,2), (2,2,1)\}$. - $n=7$: $D=5$ with $\{(3,1,0), (2,1,0), (2,0,1), (1,2,1), (2,1,1), (3,2,0), (2,0,0)\}$. - $n=8$: $D=5$ with $\{(2,1,2), (0,0,1), (1,2,0), (2,1,0), (1,1,3), (1,0,2), (1,2,2), (1,0,0)\}$. These computations only probe a tiny discrete search space but confirm that $D$ can be far below $n/2$ for small $n$.

5) VERIFICATION - Lemma 1: I checked the Gram-matrix computation and the rank bound $\mathrm{rank}(G)\le 3$ (vectors in $\mathbb{R}^3$) carefully; all eigenvalues are nonzero, so $\mathrm{rank}(G)=m-1$. - Lemma 2: the diagonal-matrix argument uses that $\Delta$ contains all squared distances among the points, guaranteeing $F_i(p_j)=0$ for $j\neq i$ and $F_i(p_i)\neq 0$. - The dimension count $\binom{m+3}{3}$ is justified by stars-and-bars: for each $r\le m$, the number of solutions to $a+b+c=r$ is $\binom{r+2}{2}$, and $\sum_{r=0}^m \binom{r+2}{2}=\binom{m+3}{3}$.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: for any $n$ points in $\mathbb{R}^3$ (hence also for vertices of a convex polyhedron), the number of distinct distances satisfies $D=\Omega(n^{1/3})$ (Lemma 2). (ii) First gap (crisp): upgrade the general lower bound from $n^{1/3}$ to $(1-o(1))n/2$ under the additional hypothesis that the points are vertices of a convex polyhedron. (iii) Top 3 next moves (concrete): 1. Prove that some vertex of a convex polyhedron determines $\ge (1-o(1))n/2$ distinct distances to the other vertices; then $D$ is at least that. 2. Use convexity to bound the number of repeated distances from a vertex (e.g. via spherical geometry of directions / antipodal pairs) and sum over vertices. 3. Computational search: optimize convex polyhedra with small distance sets (e.g. via integer-coordinate convex hulls) to guess extremal families and then attempt a stability theorem. (iv) Minimal counterexample structure (if the conjecture is true): a sequence of convex polyhedra with $D=o(n)$ would have to realize most edges (and many non-edges) using a very small set of radii, i.e. behave like a large "few-distance" set in $\mathbb{R}^3$; Lemma 2 suggests that such a set would need strong algebraic structure beyond generic convexity.

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.

Let $x_1,\ldots,x_n\in \mathbb{R}^3$ be the vertices of a convex polyhedron. Are there at least\[(1-o(1))\frac{n}{2}\]many distinct distances between the $x_i$? For the similar problem in $\mathbb{R}^2$ there are always at least $n/2$ distances, as proved by Altman [Al63] (see [93] ). In [Er75f] Erdős claims that Altman proved that the vertices determine $\gg n$ many distinct distances, but gives no reference. References [Al63] Altman, E., On a problem of P. Erdős . Amer. Math. Monthly $1963$, 148-157. [Er75f] Erdős, Paul, On some problems of elementary and combinatorial geometry . Ann. Mat. Pura Appl. $4$ $1975$, 99-108.

1) FORMAL RESTATEMENT Let $n\ge 4$ and let $x_1,\ldots,x_n\in\mathbb{R}^3$ be the vertices of a convex polyhedron, i.e. each $x_i$ is a vertex (extreme point) of $\mathrm{conv}(\{x_1,\ldots,x_n\})$. Let \[ D:=\left|\left\{|x_i-x_j|:1\le i<j\le n\right\}\right| \] be the number of distinct interpoint distances. Question: must we have \[ D\ \ge\ (1-o(1))\frac{n}{2}\qquad\text{as }n\to\infty\ ? \]

Edge cases: for $n=4$ a regular tetrahedron has $D=1$, so the asymptotic claim is not meant for small $n$.

2) QUICK LITERATURE/CONTEXT CHECK The problem statement mentions that in $\mathbb{R}^2$ the vertices of a convex polygon always determine at least $n/2$ distinct distances (Altman). I do not assume any external theorems beyond what is stated.

3) ATTACK PLAN Proof-track ideas: - Use convexity to get many distinct distances from a well-chosen vertex (analogue of planar convex-position problems). - Use global algebraic methods to show that few distinct distances force $n$ to be small ("few-distance sets" methods).

Disproof-track ideas: - Construct large convex polyhedra with only $o(n)$ distinct distances, e.g. by placing vertices on few spheres/circles with high symmetry.

I cannot reach the conjectured linear bound; I can prove a general lower bound $D=\Omega(n^{1/3})$ valid for all point sets in $\mathbb{R}^3$.

4) WORK

Lemma 1 (equidistant sets in $\mathbb{R}^3$ have size at most $4$). If $P=\{p_1,\ldots,p_m\}\subset\mathbb{R}^3$ satisfies $|p_i-p_j|=\lambda$ for all $i\neq j$, then $m\le 4$.

Proof. Translate so that $p_m=0$. Let $v_i:=p_i$ for $i=1,\ldots,m-1$. Then $|v_i|^2=\lambda^2$ for all $i$ and $|v_i-v_j|^2=\lambda^2$ for $i\neq j$. Expanding gives $|v_i|^2+|v_j|^2-2v_i\cdot v_j=\lambda^2$, hence $2\lambda^2-2v_i\cdot v_j=\lambda^2$, so $v_i\cdot v_j=\lambda^2/2$ for all $i\neq j$. Form the Gram matrix $G=(v_i\cdot v_j)_{1\le i,j\le m-1}$. It has diagonal entries $\lambda^2$ and off-diagonal entries $\lambda^2/2$, so $G=\frac{\lambda^2}{2}(J_{m-1}+I_{m-1})$, where $J$ is the all-ones matrix. The eigenvalues of $J_{m-1}$ are $(m-1)$ (once) and $0$ (multiplicity $m-2$). Therefore the eigenvalues of $G$ are $\frac{\lambda^2}{2}(m)$ (once) and $\frac{\lambda^2}{2}$ (multiplicity $m-2$), all nonzero. Hence $\mathrm{rank}(G)=m-1$. But $\mathrm{rank}(G)\le 3$ because $G$ is the Gram matrix of vectors in $\mathbb{R}^3$. Thus $m-1\le 3$ and $m\le 4$. $\square$

Lemma 2 (a polynomial method bound for distance sets in $\mathbb{R}^3$). Let $P=\{p_1,\ldots,p_n\}\subset\mathbb{R}^3$ and let $D(P)$ be the number of distinct distances among pairs. Then \[ n\ \le\ \binom{2D(P)+3}{3}. \] In particular, $D(P)\ge c\,n^{1/3}$ for an absolute constant $c>0$.

Proof. Let $\Delta$ be the set of distinct squared distances determined by $P$: $\Delta:=\{|p_i-p_j|^2:1\le i<j\le n\}$, so $|\Delta|=D(P)$. For each $i$, define a polynomial in three variables \[ F_i(x):=\prod_{t\in\Delta}\left(\|x-p_i\|^2-t\right),\qquad x\in\mathbb{R}^3. \] Each factor has degree $2$, so $\deg(F_i)\le 2|\Delta|=2D(P)$. Evaluate at the points $p_j$: if $j\neq i$, then $\|p_j-p_i\|^2\in\Delta$, so one factor vanishes and hence $F_i(p_j)=0$. On the other hand, $F_i(p_i)=\prod_{t\in\Delta}(-t)\neq 0$ because all $t\in\Delta$ are positive. Thus the $n\times n$ matrix $M=(F_i(p_j))_{i,j}$ is diagonal with nonzero diagonal entries, so $\mathrm{rank}(M)=n$. Let $V$ be the real vector space of polynomials in $(x_1,x_2,x_3)$ of total degree at most $2D(P)$. The rows of $M$ lie in the image of the evaluation map $\mathrm{ev}:V\to\mathbb{R}^n$, $F\mapsto (F(p_1),\ldots,F(p_n))$. Therefore $n=\dim(\mathrm{span}\{\text{rows of }M\})\le \dim(\mathrm{im}(\mathrm{ev}))\le \dim(V)$. It remains to compute $\dim(V)$. A monomial $x_1^{a}x_2^{b}x_3^{c}$ has total degree $a+b+c\le 2D(P)$. The number of triples $(a,b,c)\in\mathbb{Z}_{\ge 0}^3$ with $a+b+c\le m$ equals $\binom{m+3}{3}$ (stars-and-bars, summing over $a+b+c=r$). With $m=2D(P)$ this gives $\dim(V)=\binom{2D(P)+3}{3}$, proving the bound. The final asymptotic $D(P)\ge c\,n^{1/3}$ follows because $\binom{2D+3}{3}=O(D^3)$. $\square$

Corollary 3 (applies to the convex-polyhedron case). If $x_1,\ldots,x_n$ are vertices of a convex polyhedron in $\mathbb{R}^3$, then $D\ge c\,n^{1/3}$. (This is immediate from Lemma 2 because it assumes no convexity.)

FAST REALITY CHECK (small cases on the integer grid). I searched subsets of the $3\times 3\times 3$ grid $\{0,1,2\}^3$ and required that all points be vertices of their convex hull. Minimized the number of distinct squared distances (this equals the number of distinct distances). Witnesses: - $n=4$: minimum found $D=1$, achieved by $\{(0,0,0), (0,1,1), (1,0,1), (1,1,0)\}$ (a regular tetrahedron of edge length $\sqrt 2$). - $n=5$: minimum found $D=2$, achieved by $\{(0,0,1), (0,1,0), (0,1,2), (0,2,1), (1,1,1)\}$. Random search in $\{0,1,2,3\}^3$ (30k samples each) found: - $n=6$: $D=3$ with $\{(2,1,0), (1,2,0), (1,1,1), (0,2,1), (1,2,2), (2,2,1)\}$. - $n=7$: $D=5$ with $\{(3,1,0), (2,1,0), (2,0,1), (1,2,1), (2,1,1), (3,2,0), (2,0,0)\}$. - $n=8$: $D=5$ with $\{(2,1,2), (0,0,1), (1,2,0), (2,1,0), (1,1,3), (1,0,2), (1,2,2), (1,0,0)\}$. These computations only probe a tiny discrete search space but confirm that $D$ can be far below $n/2$ for small $n$.

5) VERIFICATION - Lemma 1: I checked the Gram-matrix computation and the rank bound $\mathrm{rank}(G)\le 3$ (vectors in $\mathbb{R}^3$) carefully; all eigenvalues are nonzero, so $\mathrm{rank}(G)=m-1$. - Lemma 2: the diagonal-matrix argument uses that $\Delta$ contains all squared distances among the points, guaranteeing $F_i(p_j)=0$ for $j\neq i$ and $F_i(p_i)\neq 0$. - The dimension count $\binom{m+3}{3}$ is justified by stars-and-bars: for each $r\le m$, the number of solutions to $a+b+c=r$ is $\binom{r+2}{2}$, and $\sum_{r=0}^m \binom{r+2}{2}=\binom{m+3}{3}$.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: for any $n$ points in $\mathbb{R}^3$ (hence also for vertices of a convex polyhedron), the number of distinct distances satisfies $D=\Omega(n^{1/3})$ (Lemma 2). (ii) First gap (crisp): upgrade the general lower bound from $n^{1/3}$ to $(1-o(1))n/2$ under the additional hypothesis that the points are vertices of a convex polyhedron. (iii) Top 3 next moves (concrete): 1. Prove that some vertex of a convex polyhedron determines $\ge (1-o(1))n/2$ distinct distances to the other vertices; then $D$ is at least that. 2. Use convexity to bound the number of repeated distances from a vertex (e.g. via spherical geometry of directions / antipodal pairs) and sum over vertices. 3. Computational search: optimize convex polyhedra with small distance sets (e.g. via integer-coordinate convex hulls) to guess extremal families and then attempt a stability theorem. (iv) Minimal counterexample structure (if the conjecture is true): a sequence of convex polyhedra with $D=o(n)$ would have to realize most edges (and many non-edges) using a very small set of radii, i.e. behave like a large "few-distance" set in $\mathbb{R}^3$; Lemma 2 suggests that such a set would need strong algebraic structure beyond generic convexity.