Contact number problem: max unit-distance pairs among $n$ points pairwise $\geq 1$ apart (Erdős #1084)
Statement
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)$ pairs of points which are distance exactly $1$ apart. Estimate $f_d(n)$. Equivalently: in a packing of $n$ non-overlapping balls of diameter $1$ in $\mathbb{R}^d$, how many touching pairs can there be? The genuinely open cases are $d\geq 3$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof) determining the asymptotics of $f_3(n)$ to second order — i.e. $f_3(n)=6n-(c+o(1))n^{2/3}$ with an explicit constant $c$ — or an exact formula for $f_3(n)$ valid for all $n$ (Harborth-style); an analogous determination for another fixed $d\geq 4$ also fully resolves that case. ADVANCES: (a) a proven explicit lower bound $f_3(n)>6n-c_1n^{2/3}$ with stated $c_1$, or an upper bound with constant strictly better than the best bound stated in the background; (b) new exact values of $f_3(n)$ for specific $n$ beyond those known in the literature, with reproducible enumeration/optimization code and an optimality certificate; (c) record-contact configurations for concrete $(d,n)$ strictly beating the best construction stated in the background or in the cited survey, certified by explicit coordinates and exact/interval-arithmetic distance verification; (d) an improvement of the general-$d$ gap between $(d-o(1))n$ and $2^{O(d)}n$. Deliver the proof file, or the coordinates/enumeration code plus verification certificates and the attained values.
Background
Posed by Erdős [Er75f, p.102] and known as the contact number problem; listed as open on erdosproblems.com/1084 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Dimension 1 is trivial ($f_1(n)=n-1$) and dimension 2 is completely solved: Erdős [Er46b] proved $f_2(n)<3n-cn^{1/2}$, speculated in [Er75f] that the triangular (penny) lattice is exactly optimal with $f_2(3n^2+3n+1)=9n^2+3n$ (the values $9n^2+3n$ are OEIS A045945, the hexagonal matchstick numbers), and Harborth [Ha74b] proved the exact formula $f_2(n)=\lfloor 3n-\sqrt{12n-3}\rfloor$ for all $n\geq 2$. For $d=3$ Erdős [Er75f] asserted there are constants $c_1,c_2>0$ with $$6n-c_1n^{2/3}<f_3(n)<6n-c_2n^{2/3},$$ the lower bound coming from chunks of the face-centred-cubic packing; Bezdek and Reid [BeRe13] proved the explicit upper bound $f_3(n)<6n-0.926\,n^{2/3}$ for all $n\geq 2$, and no matching explicit constant on the lower side is recorded — determining the true second-order constant (or an exact Harborth-style formula) is open. In general dimension $(d-o(1))n\leq f_d(n)\leq 2^{O(d)}n$: the lower bound from integer-grid configurations, the upper because at most kissing-number-many (which is $2^{O(d)}$) unit-separated points can be at distance 1 from a given point — the venue's kissing-number problems in dimensions 5 and 10 are close relatives. Bezdek and Khan [BeKh18] survey contact numbers for sphere packings, including the exact values known for small $n$ in $\mathbb{R}^3$. Erdős #223 (erdosproblems.com/223) is the analogous problem with maximum distance 1. A Lean formalisation of the statement exists in the formal-conjectures repository. The attacker's tool: explicit construction search — record contact counts for concrete $(d,n)$ certify by coordinates plus exact distance checks (FCC chunks and their optimizations), enumeration of contact graphs with rigidity/optimality certification for small $n$, and constant-chasing in the $6n-cn^{2/3}$ window.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1084 (T. F. Bloom) | website |
| REF-02 | OEIS A045945 — hexagonal matchstick numbers a(n)=3n(3n+1) (planar contact counts of hexagonal penny packings) | website |
| REF-03 | Lean formalisation of Erdős #1084 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.