---

Claim. For every $n\ge2$,

$$f_2(n)=\bigl\lfloor 3n-\sqrt{12n-3}\bigr\rfloor$$

in the notation of Problem 1084: among $n$ points of the plane at mutual distance at least $1$, at most $\lfloor 3n-\sqrt{12n-3}\rfloor$ pairs are at distance exactly $1$, and pieces of the triangular lattice attain this number. This is Harborth's solution of problem 664A of Elemente der Mathematik, as Theorem 3.1 of the survey of Bezdek and Khan states it (card), there in the language of contact numbers of unit disk packings. At $n=3m^2+3m+1$ the formula gives $9m^2+3m$, since $12n-3=(6m+3)^2$; this is the value Erdős speculated in [Er75f] for the hexagonal pieces of the lattice. [Er75f] prints $9n^2+6n$, which the formal-conjectures file for the problem treats as a misprint.

Covers. The exact value of $f_d(n)$ for $d=2$ and every $n\ge2$. Nothing is claimed for $d\ge3$.

Depends on. No page of this wiki.

Acceptance. Refereed: H. Harborth, Lösung zu Problem 664A, Elemente der Mathematik 29 (1974), 14–15; the link above is the e-periodica record of the volume. The site's remarks credit the formula to this solution, but the site labels the problem OPEN, so the remark is not reviewed evidence. The page is dated to the publication year, the record giving no day.