Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 1084

claims/: The 3 claim pages of Problem 1084, one per claimant's result; the problem's standing derives from them.

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)$ many pairs of points which are distance $1$ apart. Estimate $f_d(n)$ .

Status. Open, in the site's label (OPEN; page last edited 8 February 2026). The site's remarks credit exact values for $d=1$ and $d=2$ and an upper bound for $d=3$ , recorded as partial claims in claims/; the problem asks for $f_d(n)$ in every dimension, so the standing in the frontmatter, derived from the claim pages, is open.

Source. erdosproblems.com/1084, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1084, https://www.erdosproblems.com/1084.

References.

[BeKh18] Bezdek, Károly and Khan, Muhammad A., Contact numbers for sphere packings. (2018), 25-47.
[BeRe13] Bezdek, Károly and Reid, Samuel, Contact graphs of unit sphere packings revisited. J. Geom. (2013), 57-83.
[Er46b] Erdős, P., On sets of distances of $n$ points. Amer. Math. Monthly (1946), 248-250.
[Er75f] Erdős, Paul, On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. (4) (1975), 99-108.
[Ha74b] Harborth, Heiko, Lösung zu Problem 664A. Elem. Math. (1974), 14-15.

Formalization. The formal-conjectures file defines $f_d(n)$ for every $d$ and states variants but no main theorem: $f_1(n)=n-1$ , the planar bounds $f_2(n)<3n$ and $f_2(n)<3n-cn^{1/2}$ , Harborth's value at $n=3m^2+3m+1$ , and Erdős's two-sided estimate for $d=3$ , each marked solved. Only the one-dimensional variant carries a proof, held on a contributor's fork and recorded on [[problems/distance_problems/E1084/claims/2026_06_11_sanexxxx777|its claim page]].

Current assessment

The site's formulation (page last edited 8 February 2026) asks for an estimate of $f_d(n)$ , the largest number of pairs at distance exactly $1$ among $n$ points of $\mathbb{R}^d$ at mutual distance at least $1$ ; this is the contact number problem for packings of congruent balls. The answer is exact in dimensions one and two and open from dimension three on.

Dimensions one and two. For $d=1$ consecutive points give $f_1(n)=n-1$ , an easy fact whose Lean proof, not built by this corpus, is on [[problems/distance_problems/E1084/claims/2026_06_11_sanexxxx777|its claim page]]. For $d=2$ every point has at most six others at distance $1$ , so $f_2(n)<3n$ , and Erdős [Er46b] sharpened this to $f_2(n)<3n-cn^{1/2}$ for a constant $c>0$ , which the triangular lattice shows to be sharp up to the constant. Harborth [Ha74b] determined $f_2(n)=\lfloor 3n-\sqrt{12n-3}\rfloor$ for every $n\ge2$ , which implies the bound of [Er46b] and confirms Erdős's speculation in [Er75f] that the triangular lattice is exactly optimal (claim page, accepted on its journal publication).

Dimension three and above. In [Er75f] Erdős claims constants $c_1,c_2>0$ with $6n-c_1n^{2/3}<f_3(n)<6n-c_2n^{2/3}$ . Bezdek and Reid [BeRe13] proved the upper half, $f_3(n)<6n-0.926\,n^{2/3}$ for every $n\ge2$ ([[problems/distance_problems/E1084/claims/2013_04_01_bezdek_reid|claim page]], accepted on its journal publication). On the lower side, Bezdek and Reid recall packings with more than $6n-7.862\,n^{2/3}$ touching pairs for the sizes $n=(2k^3+k)/3$ ; $f_3(n)$ is not determined. In general $(d-o(1))n\le f_d(n)\le2^{O(d)}n$ , the lower bound from points of the integer grid and the upper bound from the kissing number, which bounds how many disjoint congruent balls can touch a fixed one; these bounds settle no case and have no claim page. The survey of Bezdek and Khan [BeKh18] collects the known results. Problem 223 is the analogous problem for the maximal distance.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (19)

Harborth's exact planar contact number Bezdek and Reid's upper bound for contact numbers in space A Lean proof of the one-dimensional case problems/distance_problems/E1084/claims Distance Problems distance_problems/bezdek_2013_contact_graphs_unit_sphere_packings_revisited Theorem 1: fewer than 6n - 0.926 n^(2/3) touching pairs among n unit balls in 3-space Theorem 2: touching triplets and quadruples in packings of n unit balls in 3-space distance_problems/bezdek_2018_contact_numbers_sphere_packings Corollary 7.2 (p. 11): c(n,d) < k(d)n/2 - 2^{-d} delta_d^{-(d-1)/d} n^{(d-1)/d} for n > 1, d >= 3 Proposition 5.1 (p. 6): c(n,3) = 3n - 6 for n = 4, ..., 9, assuming the Arkus-Manoharan-Brenner lists are complete Theorem 3.1 (p. 3): c(n,2) = floor(3n - sqrt(12n-3)) for all n >= 2 Theorem 4.1 (p. 5): bounds on c(n,3) and on the fcc contact number c_fcc(n)Theorem 7.1 (p. 10): upper bound for the contact number c(K,n,d) of n translates of a convex body, d >= 3 Theorem 7.8 (p. 13): c_Z(n,d) <= floor(dn - dn^{(d-1)/d}) for n > 1, d >= 2 distance_problems/erdos_1946_sets_distances_points Theorem 3 (p. 250): among n planar points the diameter occurs at most n times and the minimum distance at most 3n - 6 times distance_problems/erdos_1975_problems_elementary_combinatorial_geometry Section 2 (p. 102): the most unit distances among n points with minimum distance 1, and conjecture (2)

Graph