ERDŐS/DAILY ▸

← back to the ledger

ERDőS #670 · PARTIAL

Erdős problem #670 — wave 7f

Access date: 2026-07-27 (UTC).

Claim labels

Step 0: live-page gate

I fetched both the live problem page and its discussion thread through the Bright Data browser on 2026-07-27. Direct datacenter fetching was not used as authority.

The live page's verbatim statement is:

> Let \(A\subseteq\mathbb R^d\) be a set of \(n\) points such that all pairwise distances differ by at least \(1\). Is the diameter of \(A\) at least \((1+o(1))n^2\)?

Live gate facts:

\[ \left(1-\frac1{\pi^2}+o(1)\right)n^2\approx0.898n^2. \]

Decision: proceed.

Primary-source/literature check

New exact finite result

For \(n\ge3\), let \(\Delta_{n,d}\) be the infimum of the diameter over \(n\)-point subsets of \(\mathbb R^d\) satisfying #670's separation condition.

Define

\[ \begin{aligned} P(t)={}&5t^7+215t^6+2991t^5+18789t^4\\ &+56520t^3+74424t^2+30804t-3780, \end{aligned} \]

and let \(t_*\) be its unique positive root. Exact rational sign checks give

\[ 0.0978and bisection for display gives

\[ t_*=0.097819085934546011324952555284183619\ldots. \]

Theorem (d, with elementary-rigorous reduction (a)). For every \(d\ge3\),

\[ \boxed{\Delta_{5,d}=10+t_* =10.09781908593454601132495255528418\ldots.} \]

Thus the elementary counting lower bound \(10=\binom52\) is not attainable. For context, the exact initial table for \(d\ge3\) is

| \(n\) | \(\Delta_{n,d}\) | attaining distance set |

|---:|---:|---|

| 3 | \(3\) | \(\{1,2,3\}\), from marks \(0,1,3\) |

| 4 | \(6\) | \(\{1,\ldots,6\}\), from marks \(0,1,4,6\) |

| 5 | \(10+t_*\) | \(\{1+t_*,\ldots,10+t_*\}\), in \(\mathbb R^3\) |

The \(n=3,4\) rows are (a); the \(n=5\) row uses the exact finite enumeration described below and is therefore conservatively labelled (d).

The construction

(a) Label the ten edges of \(K_5\) by the following ranks:

\[ \begin{array}{c|ccccc} &0&1&2&3&4\\ \hline 0&-&1&2&6&9\\ 1& &-&3&7&10\\ 2& & &-&5&8\\ 3& & & &-&4\\ 4& & & & &- \end{array} \]

Put \(d_{ij}=t_*+\rho_{ij}\), where \(\rho_{ij}\) is the displayed rank. Based at vertex \(0\), form the \(4\times4\) Gram matrix

\[ G_{ab}(t)=\frac{(t+\rho_{0a})^2+(t+\rho_{0b})^2 -(t+\rho_{ab})^2}{2}\qquad(1\le a,b\le4), \]

with the last term interpreted as \(0\) when \(a=b\). Direct expansion gives

\[ \det G(t)=\frac{(t+1)P(t)}{16}. \]

(a) Every proper principal minor of \(G(t_*)\) is positive, while its determinant is zero. A compact exact check is as follows: after expansion, every nonconstant coefficient of each of the 14 proper principal minors is nonnegative, and every minor is already positive at \(t=0.0978\). Since \(P\) is strictly increasing for \(t\ge0\), its sign change between \(0.0978\) and \(0.0979\) isolates \(t_*\). Hence \(G(t_*)\) is positive semidefinite of rank \(3\).

Consequently it is the Gram matrix of four vectors in \(\mathbb R^3\), together with the origin. This is also a closed-form coordinate construction: if \(B\) is the leading \(3\times3\) block of \(G(t_*)\), \(g\) is the first three entries of its fourth column, and \(Y=B^{1/2}\) is the positive square root, take

\[ x_0=0,\qquad (x_1\ x_2\ x_3)=Y,\qquad x_4=Y^{-1}g. \]

The zero Schur complement gives \(\lVert x_4\rVert^2=G_{44}\), and the Gram identities give all ten required distances.

For visual checking only, one triangular realization is approximately

\[ \begin{array}{c|rrr} 0&0&0&0\\ 1& 1.097819085935&0&0\\ 2&-1.817435804111& 1.047746159739&0\\ 3&-5.461023396318&-2.029898065667& 1.800037475346\\ 4&-8.193714090474&-3.906774340364&-0.608667214026 \end{array} \]

and its sorted distances are \(1+t_*,2+t_*,\ldots,10+t_*\). The exact construction is the Gram definition, not these rounded coordinates.

The lower bound

1. Rank-offset normal form

(a) For any configuration of at least three points, its smallest distance is at least \(1\). Indeed, if \(p,q\) are a closest pair and \(z\) is a third point, then

\[ 1\le\bigl|\,|p-z|-|q-z|\,\bigr|\le |p-q|. \]

Order the ten distances as \(r_1<\cdots \[ r_k=k+x_k,\qquad 0\le x_1\le x_2\le\cdots\le x_{10}. \]

Thus the diameter is \(10+x_{10}\).

Suppose for contradiction that \(x_{10}a+b\), then \(c\ge a+b+1\), while its actual lengths would satisfy

\[ r_c\ge c>a+b+0.2>r_a+r_b, \]

a triangle-inequality contradiction. Therefore the integer edge ranks themselves form a metric on every triangle.

2. The 69 edge-order orbits

(d) Relabel the endpoints of the shortest edge as \(0,1\), so rank \(1\) lies on edge \(01\). Exhausting the remaining \(9!\) assignments and applying the ten integer triangle tests leaves exactly 828 labelled orders. Quotienting by all \(5!\) vertex relabellings leaves exactly 69 orbits.

This is small enough for an exact certificate, but it is not asserted from an unverified list: the standalone checker regenerates both counts from scratch.

3. Sixty-eight rational separation certificates

Fix an edge order \(\rho\) and base the Gram matrix at vertex \(0\). For an integer vector \(v=(v_1,\ldots,v_4)\), define

\[ c_{0j}=v_j\sum_{\ell=1}^4v_\ell,\qquad c_{ij}=-v_iv_j\quad(1\le iand transfer these coefficients to ranks by \(c_k=c_{ij}\) when

\(\rho_{ij}=k\). Then

\[ v^TG(x)v=\sum_{k=1}^{10}c_k(k+x_k)^2. \]

Write

\[ q_0=\sum_{k=1}^{10}c_k k^2,\quad L=\max\left(0,\max_{1\le j\le10}\sum_{k=j}^{10}2kc_k\right),\quad A=\sum_{k=1}^{10}\max(c_k,0). \]

(a) Monotonicity of the offsets gives the rigorous bound

\[ v^TG(x)v\le q_0+\delta L+\delta^2A \quad\text{whenever}\quad 0\le x_1\le\cdots\le x_{10}\le\delta. \]

To see the linear part, write \(x_k=\sum_{j\le k}y_j\), where

\(y_j\ge0\) and \(\sum y_j=x_{10}\le\delta\); the suffix sums above are

then the coefficients of the \(y_j\). For the quadratic part, discard

negative terms and use \(x_k^2\le\delta^2\).

(d) For each of 68 nonexceptional orbits, the checker finds a primitive

integer \(v\), with \(\lVert v\rVert_\infty\le12\), such that

\[ 100q_0+10L+A<0. \]

Therefore \(v^TG(x)v<0\) for \(x_{10}<0.1\), contradicting positive

semidefiniteness of a Euclidean Gram matrix. The checker searches all

primitive vectors shell-by-shell rather than trusting a stored certificate

list; 171,839 candidate vectors suffice for all 68 orbits.

4. The exceptional orbit

The remaining orbit is precisely the rank matrix used in the construction.

For an indeterminate \(t\), the following vector is a nonzero scalar multiple

of the first adjugate column of \(G(t)\):

\[ \begin{aligned} w_1={}&4(t+1)(t^4+32t^3+324t^2+1308t+1783),\\ w_2={}&-(t^5+47t^4+453t^3+1219t^2-618t-2198),\\ w_3={}&-(t+1)(t^4+14t^3+39t^2-84t-150),\\ w_4={}&-(t^5+3t^4-79t^3-525t^2-954t-414). \end{aligned} \]

(a) All four entries are positive at \(t=t_*\), and

\(G(t_*)w(t_*)=0\). Define \(c_k\) from this \(w(t_*)\) as in the preceding

subsection, and put

\[ h_k=2c_k(k+t_*)-t_*\max(c_k,0),\qquad H_j=\sum_{k=1}^j h_k. \]

The positive \(c_k\) are exactly the incident-edge ranks

\(\{1,2,6,9\}\).

(d) Exact rational interval evaluation on

\([0.0978,0.0979]\) verifies all ten strict inequalities

\[ H_1,H_2,\ldots,H_{10}>0. \]

The checker obtains these by expanding the polynomial expressions and

bounding every monomial with rational endpoints; no floating-point sign is

used.

Now let \(y_k=t_*-x_k\). If \(x_{10} \[ y_1\ge y_2\ge\cdots\ge y_{10}>0. \]

Since \(w^TG(t_*)w=0\), \(0\le y_k\le t_*\), and

\(c_ky_k^2\le t_*\max(c_k,0)y_k\),

\[ \begin{aligned} w^TG(x)w &=\sum_k c_k\bigl((k+t_*-y_k)^2-(k+t_*)^2\bigr)\\ &\le-\sum_k h_ky_k\\ &=-\left(\sum_{j=1}^9H_j(y_j-y_{j+1})+H_{10}y_{10}\right)<0. \end{aligned} \]

This again contradicts positive semidefiniteness. Hence

\(x_{10}\ge t_*\), completing the lower bound.

Reproduction

Standalone verifier:

erdos670_wave7f_reverify.py

It uses only the Python standard library. All proof decisions use integers or

fractions.Fraction; Decimal is used only to print the isolated root.

Run from the repository root:

$ python runs/erdos670_wave7f_reverify.py
triangle-metric labelled orders with rank(01)=1: 828
vertex-relabeling orbits: 69
nonexceptional exact certificates: 68 (primitive-vector shells through 12, 171839 vectors tested)
exceptional prefix inequalities verified exactly: 10/10
proper Gram principal minors verified exactly: 14/14
t_* = 0.097819085934546011324952555284183619046712494784010753790809
minimum five-point diameter = 10.0978190859345460113249525552841836190467124947840107537908
preceding exact diameters (n=3,4): 3, 6
PASS

Measured on this VM: about 3.5 seconds and 13 MB maximum resident memory.

Verifier SHA-256:

1b6723f47e786aef0652e530226fec660519d4b6653732739ee60148ba7bd3b7

What this does and does not settle

  • (d) It exactly settles the five-point problem for every \(d\ge3\), and

supplies a checked three-dimensional construction. It is genuine finite

progress, not an asymptotic resolution.

  • (a) In the rank-offset notation for general

\(m=\binom n2\), #670 asks for

\(x_m\ge(\tfrac12+o(1))n^2\), because the elementary part only gives

\(r_m=m+x_m\) and \(m=(\tfrac12+o(1))n^2\).

  • (c) The exact missing ingredient is an aggregate fixed-rank lemma:

for every fixed \(d\), a rank-\(\le d\) positive-semidefinite Euclidean

distance Gram matrix whose edge lengths are

\(k+x_k\), \(0\le x_1\le\cdots\le x_m\), must have

\(x_m\ge(\tfrac12-o(1))n^2\). The five-point proof replaces such a lemma by

exhaustive edge-order certificates; it gives no uniform mechanism as

\(n\to\infty\).

  • (d/c) Naively moving only to \(n=6\) already exposes

\(14!=87,178,291,200\) rank assignments after fixing the shortest edge

(about \(15!/6!\approx1.82\times10^9\) before triangle pruning modulo

vertices). A bare optimized triangle filter would plausibly cost roughly

2–25 core-hours at \(10^6\)–\(10^7\) assignments/second, and producing

semialgebraic Gram certificates would cost substantially more. I did not

run that computation. Orderly generation or a structural lemma is needed

before \(n=6\) is a sensible exact target.

PARTIAL: Exact finite progress—proved by a standalone exact certificate that for every d>=3 the minimum five-point diameter is 10+t_*=10.097819085934546..., with an explicit R^3 Gram construction; the fixed-d asymptotic problem remains open.

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