ERDŐS/DAILY ▸

← back to the ledger

ERDőS #660 · PARTIAL

Erdős problem 660 — live-page audit, exact small cases, and a sharp family

Date of run: 2026-07-28 (UTC)

Claim labels

elementary facts.

only on the precisely cited published theorem.

proposed direction that is not asserted as a theorem.

reproducible checker identified, but not promoted to a proof unless the finite enumeration and its prerequisites are themselves justified.

0. Mandatory live-page check

I fetched both the live problem page and its discussion through the Bright Data browser route on 2026-07-28; direct datacenter HTTP was not used as the source of truth.

[A, directly observed] The live page <https://www.erdosproblems.com/660> says OPEN. It has zero claimed proofs. “Interested in collaborating” is None, and “Currently working” is None. The page says it was last edited on 2026-01-01. Thus neither stop condition in the task is present.

The current statement, copied verbatim from the live page, is:

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 n2 > \] many distinct distances between the \(x_i\)?

[A, directly observed] The page lists the following known-result context. For the analogous problem in \(\mathbb R^2\), Altman proved the sharp half-\(n\) lower bound (with the inevitable integer rounding). It also says that Erdős claimed in [Er75f] that Altman had proved a lower bound \(\gg n\) for vertices in \(\mathbb R^3\), but supplied no reference. The page also warns: “The original source is ambiguous as to what the problem is.”

[A, directly observed] The three comments on <https://www.erdosproblems.com/forum/discuss/660> are:

  1. On 2025-10-23, kiwomuc questioned the historical formulation, noted that a

regular-polygon pyramid gives roughly \(n/2\) distances, and observed that the then displayed existential upper-bound reading would be trivial.

  1. On 2025-10-24, Thomas Bloom reproduced the wording of the original source

and explained the ambiguity; the site statement was changed to the present lower-bound question.

  1. Later on 2025-10-24, kiwomuc noted an odd-\(n\) double-pyramid construction

with \((n-1)/2\) distances, mentioned the one-distance tetrahedron, and asked about a higher-dimensional analogue.

No comment is marked as a proof, and no commenter is marked as currently working. I therefore proceeded.

Throughout the mathematics below, “vertices of a convex polyhedron” means a full-dimensional finite set in convex position in \(\mathbb R^3\). Every construction below is full-dimensional, so the conclusions do not depend on a lower-dimensional edge case.

1. Primary-source check

[A, bibliographic/direct-source check] The page's [Er75f] is Paul Erdős, “On some problems of elementary and combinatorial geometry,” Annali di Matematica Pura ed Applicata (4) 103 (1975), 99–108. In the official Erdős archive scan, p. 101, Erdős says that for \(k=3\), Altman proved \(D_3(x_1,\ldots,x_n)>\varepsilon n\) when the points are vertices of a convex polyhedron: <https://users.renyi.hu/~p_erdos/1975-25.pdf>. The references in that paper identify only Altman's planar papers; they do not provide a source for this three-dimensional assertion.

[A, bibliographic/direct-source check] The relevant Altman papers I verified are:

(1963), 148–157, <https://doi.org/10.1080/00029890.1963.11990057>.

Bulletin* 15 (1972), 329–340, <https://doi.org/10.4153/CMB-1972-060-0>.

Both are planar. I found no primary source containing the alleged Altman three-dimensional proof. This agrees with, but does not go beyond, the live page's warning.

[B] The exact few-distance results used below are:

few-distance sets in Euclidean spaces,” Electronic Journal of Combinatorics 27(1) (2020), #P1.23, <https://doi.org/10.37236/8565>. Their Theorems 13 and 15 give, in \(\mathbb R^3\), the maximum four-distance size \(13\), with exactly the two stated configurations, and the maximum three-distance size \(12\), attained uniquely by the regular icosahedron. The final paper is also available at <https://www.combinatorics.org/ojs/index.php/eljc/article/download/v27i1p23/pdf/>.

for Distance Sets,” Graphs and Combinatorics 37 (2021), 1585–1603, <https://doi.org/10.1007/s00373-021-02318-5>, author manuscript <https://arxiv.org/abs/2009.13111>. Theorem 1.2 proves that a five-distance set in \(\mathbb R^3\) has at most \(20\) points and that equality is uniquely the regular dodecahedron. Its Theorem 1.1 also records the three- and four-distance classifications above, and the proof explicitly uses \(g_3(2)=6\).

three-dimensional Euclidean space,” <https://arxiv.org/abs/1309.2047>, independently supplies the twelve-point/icosahedron classification.

[C] Searches by the live statement, the historical wording, the Erdős paper, “convex polyhedron distinct distances,” and the cited few-distance literature did not locate a primary paper that proves or refutes the live asymptotic question. This is a search miss, not a theorem of nonexistence. The live page remains the authority for the OPEN status.

2. Exact small cases: a gap at four distances

Let

\[ f_{\rm cvx}(n)=\min_X |\{\lVert x-y\rVert:x,y\in X,\ x\ne y\}|, \]

where \(X\) ranges over \(n\)-vertex convex three-dimensional polyhedra. Let

\[ G_{\rm cvx}(s)=\max\{|X|:X\subset\mathbb R^3 \text{ is in convex position and has at most }s\text{ distances}\}. \]

Theorem

[B]

\[ \boxed{G_{\rm cvx}(1),G_{\rm cvx}(2),G_{\rm cvx}(3), G_{\rm cvx}(4),G_{\rm cvx}(5)=4,6,12,12,20.} \]

Consequently,

\[ \boxed{ f_{\rm cvx}(n)= \begin{cases} 1,&n=4,\\ 2,&5\le n\le6,\\ 3,&7\le n\le12,\\ 5,&13\le n\le20. \end{cases}} \]

In particular, no \(n\) in this whole range has minimum equal to four.

Proof

[A] An equidistant set in \(\mathbb R^3\) has at most four points (center the Gram matrix, whose rank is one less than the number of equidistant points), and a regular tetrahedron attains four. Hence \(G_{\rm cvx}(1)=4\).

[B] The general, not-necessarily-convex maxima for at most two, three, four, and five distances in \(\mathbb R^3\) are respectively

\[ 6,\quad12,\quad13,\quad20 \]

by the named results above (the two-distance value is the classical \(g_3(2)=6\)). The regular octahedron, icosahedron, and dodecahedron are in convex position and attain \(6,12,20\), respectively.

[B] The only thirteen-point four-distance configurations in \(\mathbb R^3\) are:

  1. the twelve vertices of a regular icosahedron together with its center;
  2. the twelve vertices of a cuboctahedron together with its center.

In each case the center is the equal-weight average of the twelve outer vertices, hence is strictly inside their convex hull and is not a vertex. Thus no convex-position thirteen-point set has at most four distances. The icosahedron has twelve vertices and only three distances, so \(G_{\rm cvx}(4)=12\). This proves the displayed \(G_{\rm cvx}\) values.

[A] Since

\[ f_{\rm cvx}(n)=\min\{s:G_{\rm cvx}(s)\ge n\}, \]

the claimed table follows, provided there are full-dimensional convex witnesses of every intermediate size. Such witnesses can be taken as the first \(n\) points, in the order used by the checker, from:

Their exact coordinate families, with \(\phi=(1+\sqrt5)/2\), are

\[ \begin{aligned} I={}&\{(0,\pm1,\pm\phi),(\pm1,\pm\phi,0), (\pm\phi,0,\pm1)\},\\ D={}&\{(\pm1,\pm1,\pm1)\}\\ &{}\cup\{(0,\pm\phi^{-1},\pm\phi), (\pm\phi^{-1},\pm\phi,0),(\pm\phi,0,\pm\phi^{-1})\}. \end{aligned} \]

The standalone checker verifies exact affine rank, exact exposedness, and the exact distance count for every one of these subsets. This completes the proof modulo the cited maximum/classification theorems.

Independent arithmetic checks

[D] The checker recomputes over \(\mathbb Q(\sqrt5)\), without floating point, the following squared-distance sets:

| polyhedron | vertices | squared distances | |---|---:|---| | tetrahedron | 4 | \(\{8\}\) | | octahedron | 6 | \(\{2,4\}\) | | icosahedron | 12 | \(\{4,6+2\sqrt5,10+2\sqrt5\}\) | | cuboctahedron | 12 | \(\{2,4,6,8\}\) | | dodecahedron | 20 | \(\{6-2\sqrt5,4,8,6+2\sqrt5,12\}\) |

For every point \(p\) in each spherical configuration, it checks

\[ p\mathbin{\cdot}p>p\mathbin{\cdot}q\qquad(q\ne p), \]

so \(x\mapsto p\mathbin{\cdot}x\) uniquely exposes \(p\). It separately checks affine rank three. It also verifies that the center in each classified thirteen-point configuration is the average of the outer points.

[D] As a redundant audit of \(g_3(2)=6\), the program checks all 1,044 unlabeled seven-vertex graphs in NetworkX's complete Graph Atlas. If the two squared distances are scaled to \(t<1\) and \(1\), and \(A\) is the graph of the longer pairs, the centered Gram matrix is

\[ B=\frac12\bigl(tH-(1-t)HAH\bigr),\qquad H=I-\frac17J. \]

An embedding in \(\mathbb R^3\) would force \(HAH\) on \(\mathbf1^\perp\) to have the positive eigenvalue \(t/(1-t)\) with multiplicity at least three. Exact characteristic-polynomial factorization and exact Sturm root counting find no graph satisfying this necessary condition. This audit relies on the packaged completeness of Graph Atlas, so the published \(g_3(2)=6\) theorem—not this computation—is the formal dependency of the table.

3. A sharp construction for every \(n\)

Proposition

[A] For every \(n\ge4\), there is an \(n\)-vertex convex polyhedron in \(\mathbb R^3\) determining exactly

\[ \boxed{\left\lfloor\frac{n-1}{2}\right\rfloor} \]

distinct distances.

Construction and proof

Put \(m=n-1\). Let the base be the regular unit-circumradius \(m\)-gon

\[ p_j=(\cos(2\pi j/m),\sin(2\pi j/m),0), \qquad 0\le j<m. \]

Its squared chord lengths are

\[ c_k=2-2\cos(2\pi k/m),\qquad 1\le k\le\lfloor m/2\rfloor, \]

and these are strictly increasing in that range. Hence the base determines exactly \(\lfloor m/2\rfloor\) distances.

Let its largest squared chord be

\[ \delta_m= \begin{cases} 4,&m\text{ even},\\ 2+2\cos(\pi/m),&m\text{ odd}, \end{cases} \]

and add the apex

\[ a=(0,0,\sqrt{\delta_m-1}). \]

For every base point,

\[ \lVert a-p_j\rVert^2=1+(\delta_m-1)=\delta_m. \]

Thus all apex-to-base distances coincide with the already present largest base chord; no distance is added. The total is exactly \(\lfloor m/2\rfloor=\lfloor(n-1)/2\rfloor\).

The apex is uniquely exposed by the \(z\)-coordinate. Each base point \(p_j\) is uniquely exposed by the linear functional

\[ (x,y,z)\longmapsto p_{j,x}x+p_{j,y}y: \]

its value is \(1\) at \(p_j\), less than \(1\) at every other base point, and \(0\) at the apex. Since the apex has positive height, the hull is three-dimensional. Every listed point is therefore a vertex.

[D] The checker directly rebuilds this family at 100 decimal digits for every \(4\le n\le40\), reclusters all pairwise squared distances at tolerance \(10^{-70}\), verifies the claimed count, and checks all exposing functionals. The symbolic proof above, not this finite numerical check, establishes the proposition for every \(n\).

[A] For \(n=2s+2\), the construction has exactly \(s\) distances. Thus

\[ G_{\rm cvx}(s)\ge2s+2, \]

and the coefficient \(1/2\) in the live question is best possible even up to an additive constant.

4. Exact reformulation of what remains

[A] The usual interpolation polynomials show that \(G_{\rm cvx}(s)\) is finite. If the allowed positive squared distances are \(r_1^2,\ldots,r_s^2\), associate to each \(x_i\) the polynomial

\[ P_i(y)=\prod_{\nu=1}^s\bigl(\lVert y-x_i\rVert^2-r_\nu^2\bigr). \]

On the point set, \(P_i(x_j)=0\) for \(j\ne i\), while \(P_i(x_i)=\prod_\nu(-r_\nu^2)\ne0\). The \(P_i\) are linearly independent. They are polynomials in three variables of degree at most \(2s\), so

\[ G_{\rm cvx}(s)\le {2s+3\choose3}=O(s^3). \]

[A] By monotone inversion, the live problem is exactly equivalent to

\[ \boxed{G_{\rm cvx}(s)\le(2+o(1))s.} \]

The construction proves the matching lower bound \(G_{\rm cvx}(s)\ge2s+2\). Thus the entire remaining problem is the gap between a cubic elementary upper bound and an asymptotically sharp linear upper bound.

5. Why the direct perpendicular-bisector argument stalls

Let \(X\) have \(n\) vertices and \(q\) distinct distances, and let \(M\) be the maximum number of points of \(X\) in one plane.

[B] Any coplanar subset of vertices is in planar convex position: otherwise one of its points would be in the convex hull of other vertices of the three-dimensional polyhedron. Altman's planar theorem therefore gives

\[ q\ge\left\lfloor\frac M2\right\rfloor. \]

[A] For a fixed center \(x\), place the other \(n-1\) points into its at most \(q\) distance shells, of sizes \(a_1,\ldots,a_q\) (allowing empty shells). The number of unordered isosceles triples centered at \(x\) is

\[ \sum_{r=1}^q {a_r\choose2} \ge \frac12\left(\frac{(n-1)^2}{q}-(n-1)\right) \]

by Cauchy--Schwarz. Summing over centers gives at least

\[ \frac n2\left(\frac{(n-1)^2}{q}-(n-1)\right) \]

centered isosceles triples.

For a fixed unordered base pair \(\{y,z\}\), every possible center lies in the perpendicular-bisector plane of \(yz\), which contains at most \(M\) points of \(X\). Hence there are at most \(M{n\choose2}\) such triples. Comparing the two bounds gives

\[ \frac{n-1}{q}-1\le M,\qquad q\ge\frac{n-1}{M+1}. \]

Together,

\[ \boxed{q\ge \max\left\{\left\lfloor\frac M2\right\rfloor, \frac{n-1}{M+1}\right\}.} \]

Optimizing over \(M\) yields only order \(\sqrt{n/2}\), far short of the required linear bound. The exact loss is visible: a perpendicular-bisector plane is allowed to contain \(M\) vertices, while the planar theorem controls only the number of global distances once \(M\) is large. These two inequalities balance at \(M\asymp\sqrt{2n}\), not at a linear value of \(q\).

6. The next finite boundary and computation cost

[A] The exact table leaves \(G_{\rm cvx}(6)\) as the first unknown few-distance boundary. It is at least \(20\), because the dodecahedron has five distances. Adding its center produces a general twenty-one-point six-distance set, but it is not in convex position. Ruling out a convex twenty-one-point six-distance set would force \(G_{\rm cvx}(6)=20\): any larger convex set has a full-dimensional convex twenty-one-point subset.

[C] A useful next project would therefore be an isomorph-free classification of six-colorings of \(K_{21}\) compatible with a squared Euclidean distance matrix of embedding dimension three, with convexity certificates added after algebraic realizability. The methods in the cited few-distance papers—hereditary subcolorings, rank conditions, Gröbner bases, and graph augmentation—are the appropriate machinery, but their published classifications stop before this case.

[A] A raw coloring search is impossible here: \(K_{21}\) has \(210\) edges, so it has

\[ 6^{210}\approx2.6\cdot10^{163} \]

labeled six-colorings. Even at an unrealistic \(10^9\) colorings per second, this is about \(8.2\cdot10^{146}\) core-years. Symmetry and algebraic pruning would reduce this enormously, but no defensible core-hour estimate is available without first implementing and benchmarking that specialized augmentation. I did not launch such a computation.

[C] More importantly, even a complete value of \(G_{\rm cvx}(6)\) would not settle the live problem. The precise missing uniform lemma is

\[ \text{every convex-position \(s\)-distance set in \(\mathbb R^3\) has at most \((2+o(1))s\) points.} \]

The fixed-\(s\) classifications verify the beginning of this assertion but provide no uniform control as \(s\to\infty\); the elementary interpolation argument loses two powers of \(s\), and the perpendicular-bisector count loses a factor through \(M\). This is the verified wall, not a claim that no other method can succeed.

7. Reproduction

The standalone checker is:

runs/erdos660_wavew006_reverify.py

Run from the repository root with:

python3 runs/erdos660_wavew006_reverify.py

Dependencies are Python 3, SymPy, NetworkX, and mpmath. On this VM it completed in about 18 seconds with approximately 80 MB peak resident memory and ended:

SHA-256 of the checked script: 66f346220ba6125763f87dbdaaa34f77ac24a7d812d4c950757c578970046df6.

Exact full-polyhedron checks
  tetrahedron   : vertices= 4, distances=1, squared=[8]
  octahedron    : vertices= 6, distances=2, squared=[2, 4]
  icosahedron   : vertices=12, distances=3, squared=[4, 2*sqrt(5) + 6, 2*sqrt(5) + 10]
  cuboctahedron : vertices=12, distances=4, squared=[2, 4, 6, 8]
  dodecahedron  : vertices=20, distances=5, squared=[6 - 2*sqrt(5), 4, 8, 2*sqrt(5) + 6, 12]
Exact convex witness table f_cvx(n), 4 <= n <= 20
  n=4    : 1
  n=5-6  : 2
  n=7-12 : 3
  n=13-20: 5
  icosahedron+center: 13 points, 4 distances, center = average(outer), so not convex position
  cuboctahedron+center: 13 points, 4 distances, center = average(outer), so not convex position
  dodecahedron+center: 21 points, 6 distances, center = average(outer), so not convex position
Two-distance cutoff: checked 1,044 unlabeled graphs on 7 vertices; 0 pass the necessary exact spectral condition.
Regular-pyramid family: direct 100-digit checks passed for 4 <= n <= 40; q=floor((n-1)/2).
Raw K_21 six-coloring space: 6^210=2.580849e+163; at 10^9/s, 8.178217e+146 years.
ALL CHECKS PASSED

PARTIAL: Published few-distance classifications plus exact witnesses determine \(f_{\rm cvx}(n)\) for every \(4\le n\le20\) (with a jump from 3 to 5), and an elementary regular-pyramid family attains \(\lfloor(n-1)/2\rfloor\) distances for every \(n\); the open asymptotic is exactly the missing uniform bound \(G_{\rm cvx}(s)\le(2+o(1))s\).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger