Erdős problem #1084 — wave 8d report

Access/research date: 2026-07-28 (UTC).

Claim labels used throughout:

• (a) elementary-rigorous: proved here from elementary linear algebra or directly checked exact constructions.
• (b) rigorous-modulo-named-theorem: depends on the cited published theorem or primary source.
• (c) plausible/structural-unverified: interpretation, literature-search miss, or claim not promoted to a theorem.
• (d) computational-only: browser observation or finite computation, never used alone as a uniform proof.

Step 0: mandatory live-page check

(d) I fetched the live page through the Bright Data browser, not datacenter curl. I also opened its LaTeX-source page and its discussion thread. The live page was last edited 2026-02-08 and showed OPEN, 0 claimed proofs, Currently working on this problem: None, and Interested in collaborating: None. Thus the required stop condition was not triggered. URLs:

• https://www.erdosproblems.com/1084
• https://www.erdosproblems.com/latex/1084
• https://www.erdosproblems.com/forum/discuss/1084

Verbatim current statement

(d, verbatim live-page transcription)

> Let $f_d(n)$ be minimal such that in any collection of $n$ points in $\mathbb{R}^d$, all of distance at least $1$ apart, there are at most $f_d(n)$ many pairs of points which are distance $1$ apart. Estimate $f_d(n)$.

Results listed on the live page

(b) The page identifies this as the contact-number problem and lists:

1. $f_1(n)=n-1$.

2. Erdős's planar estimate $f_2(n)<3n-cn^{1/2}$ for some $c>0$.

3. Harborth's exact planar theorem

\[ f_2(n)=\left\lfloor3n-\sqrt{12n-3}\right\rfloor\qquad(n\ge2), \]

including

\[ f_2(3m^2+3m+1)=9m^2+3m. \]

4. Erdős's claimed three-dimensional order

\[ 6n-c_1n^{2/3}

for positive constants, and Bezdek--Reid's explicit upper bound

\[ f_3(n)<6n-0.926n^{2/3}\qquad(n\ge2). \]

5. The general bounds

\[ (d-o(1))n\le f_d(n)\le2^{O(d)}n, \]

with the grid and kissing-number explanations.

6. Bezdek--Khan's survey on contact numbers, and problem #223 as the analogous maximum-distance problem.

(d) The page also marks the statement as formalised and lists OEIS A045945 as a possible related sequence.

All five live comments

(d) No comment claims a proof of the full problem.

1. Moritz Firsching (2026-02-02) flagged that an earlier displayed planar specialization had $9m^2+6m$ where $9m^2+3m$ was intended; the former already fails at $m=1$. The comment links OEIS A045945. The page says it was updated.

2. BorisAlexeev (2026-02-02) observed that $9m^2+3m$ is consistent with Harborth's exact formula.

3. Alfaiz (2026-02-01) reported a broken [BeKa18] reference. The page says it was updated; the current key is [BeKh18].

4. Neel Somani (2026-01-21) linked a shared ChatGPT answer said to contain tighter literature bounds. The page says it was updated.

5. Nat Sothanaphan (2026-01-21) said that answer mostly confirms and cleans up results from the referenced paper.

(d) All other collaboration/difficulty/formalisation reaction rows on the page displayed None.

Primary-source literature check

(b) The following primary records exist and contain the claims attributed to them:

• K. Bezdek and S. Reid, Contact graphs of unit sphere packings revisited, arXiv:1210.5756, J. Geom. 104 (2013), 57--83: Theorem 1(i) gives

\[ f_3(n)<6n-0.926n^{2/3}. \]

Primary record: https://arxiv.org/abs/1210.5756

• K. Bezdek, Contact numbers for congruent sphere packings in Euclidean 3-space, arXiv:1102.1198, Discrete Comput. Geom. 48 (2012), 298--309: for

\[ n_k=\frac{k(2k^2+1)}3 \]

an explicit face-centred-cubic octahedral cluster has

\[ 2k(2k^2-3k+1)=6n_k-6k^2 >6n_k-\sqrt[3]{486}\,n_k^{2/3}. \]

Primary record: https://arxiv.org/abs/1102.1198

• K. Bezdek and M. A. Khan, Contact numbers for sphere packings, arXiv:1601.00145, published in New Trends in Intuitive Geometry (2018), 25--48: the corollary labelled d-sphere in its TeX records the 2002 Bezdek bound

\[ f_d(n)<\frac{k(d)}2n-\frac1{2^d}\delta_d^{-(d-1)/d}n^{(d-1)/d} \quad(d\ge3,\ n>1), \]

where $k(d)$ is the kissing number and $\delta_d$ the optimal infinite packing density. This is more explicit than the live page's displayed general upper bound. Primary record: https://arxiv.org/abs/1601.00145; original 2002 paper DOI: https://doi.org/10.1006/jcta.2001.3204

(d) The standalone checker fetched all three arXiv records and the TeX source of arXiv:1601.00145. It found the titles and the displayed $0.926$ and general $k(d),\delta_d$ formulas. It independently recomputed

and the density-corollary coefficient in dimension three as $0.152721764\ldots$.

(c) A search also found Samuel Reid's arXiv:1603.08201, whose abstract claims $C(6)=12,C(7)=15,C(8)=18$. Its body explicitly says the asserted $C(9),\ldots,C(13)$ proofs had not been transcribed. I do not use any of those untranscribed assertions as theorems. The new proof below independently establishes $C(6)=12$ as the $d=3$ instance of a uniform result. Primary record: https://arxiv.org/abs/1603.08201

(c) Searches by the exact $0.926$ expression, “contact number problem”, “largest contact number”, and recent arXiv year filters found later work on separable, locally separable, lattice, generic-radius, and non-congruent variants, but no post-2013 improvement to the unrestricted three-dimensional upper bound. This is an honest search miss, not a claim that no such paper exists.

New exact result

The theorem

(a) For all $d\ge1$,

and

Moreover, for every $d\ge3$ and every $3\le k\le d$,

Equivalently, this determines $f_d(n)$ for the entire near-simplex band $1\le n\le2d$.

(a) The endpoint

also holds for $d=1,2$, hence for every positive dimension.

(a) A useful upper bound obtained on the way is

even when $k>d$; it is only asserted to be sharp in the ranges for which constructions are supplied above.

Lemma 1: equidistant sets

(a) At most $d+1$ points in $\mathbb R^d$ can be pairwise at distance $1$. Indeed, for scalars $\lambda_i$ with $\sum_i\lambda_i=0$,

If all off-diagonal distances are $1$, the left side is $-\sum_i\lambda_i^2$. Thus no nonzero affine dependence exists, so $N$ equidistant points require affine dimension $N-1$.

Lemma 2: a combinatorial reduction to a matching

(a) Put $N=d+k$, and let $q$ be the number of noncontacts (pairs at distance strictly greater than $1$). Choose one endpoint from each noncontact pair. Removing those at most $q$ selected vertices leaves a contact clique, so Lemma 1 gives

(a) If equality $q=k-1$ holds and two noncontact edges share a vertex, those two edges can be covered by their common vertex and every remaining noncontact edge by one endpoint. That gives a cover of size at most $q-1$, leaving a contact clique of size at least

contrary to Lemma 1. Therefore equality in (2) forces the noncontact graph to be a matching of $m=k-1$ edges.

Lemma 3: the matching is one affine-nullity dimension short

(a) Suppose, for contradiction, that the noncontacts are the matching pairs $(u_i,v_i)$ for $1\le i\le m$, with

Let

and define the symmetric matrix

Equation (1) gives, for every $x\in H$,

Thus $A$ restricted to $H$ is positive semidefinite.

(a) The affine-dependence space

has dimension at least

By (3), $L$ lies in the radical of $A|_H$: for a positive-semidefinite form, a zero quadratic value forces zero pairing with every vector (apply the discriminant test to $x+ty$).

(a) If $x$ is in that radical, then $Ax=t\mathbf1$ for some scalar $t$. Subtracting the two equations on matching edge $i$ gives

so $x_{u_i}=x_{v_i}=a_i$. Every isolated vertex of the matching has coordinate $t$. With $r=N-2m$ isolated vertices, the remaining system is

(a) The coefficient matrix in the $m+1$ unknowns $a_1,\ldots,a_m,t$ has rank at least $2$ when $m\ge2$. If some $\delta_i\ne1$, take any $j\ne i$: rows $i,j$ and columns $a_i,t$ have determinant $\delta_i-1\ne0$. If all $\delta_i=1$, a matching row and the last row, in columns $a_i,t$, have determinant $2$. Hence the solution space of (5), and therefore the radical, has dimension at most

This contradicts (4). Consequently $q=k-1$ is impossible for $k\ge3$, and $q\ge k$.

Sharp constructions

(a) For $n\le d+1$, use a regular $(n-1)$-simplex of side $1$.

(a) For $n=d+2$, take a centred regular $(d-1)$-simplex $q_1,\ldots,q_d$ of side $1$, with

and add the two apices $(0,\pm h)$ orthogonal to its span, where

Every base--apex distance is $1$, while the apex distance has square

Thus exactly one pair is a noncontact.

(a) For $3\le k\le d$, take the following $d+k$ points:

python3 runs/erdos1084_wave8d_reverify.py --online

from fractions import Fraction as F

def choose2(n):
    return n * (n - 1) // 2

def crosspoly_subset_dist2(d, k):
    vectors = []
    for i in range(k):
        vectors += [
            tuple(1 if j == i else 0 for j in range(d)),
            tuple(-1 if j == i else 0 for j in range(d)),
        ]
    for i in range(k, d):
        vectors.append(tuple(1 if j == i else 0 for j in range(d)))
    return [[
        F(sum((vectors[i][t] - vectors[j][t])**2 for t in range(d)), 2)
        for j in range(d + k)
    ] for i in range(d + k)]

for d in range(3, 13):
    for k in range(3, d + 1):
        D = crosspoly_subset_dist2(d, k)
        values = [D[i][j] for i in range(d+k) for j in range(i+1, d+k)]
        assert min(values) == 1
        assert sum(x == 1 for x in values) == choose2(d+k) - k