we-solve (beta)

Math-6138 · mathematics · Mathematics

Erdős Problem #1084

Status Open · erdosproblems.comLLM status Open unverified

Statement

For an integer $d\ge 1$ and $n\in\mathbb{N}$, let $f_d(n)$ be the minimum integer such that for every set $P\subset\mathbb{R}^d$ of size $|P|=n$ with $\|x-y\|\ge 1$ for all distinct $x,y\in P$, the number of unordered pairs $\{x,y\}\subset P$ with $\|x-y\|=1$ is at most $f_d(n)$. The problem asks for estimates of $f_d(n)$ (as $n\to\infty$ with $d$ fixed).

Restatement from Math-6138-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-6138-A1 · No claim recorded · LLM-generated · gpt pro 5.2 ·

Reused writeup on Math-6138 (gpt pro 5.2)

Erdős Problem 1084 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1084

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1084.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1084.tex.

Erdős Problem 1084 (unit distances under separation)

FORMAL RESTATEMENT

For an integer $d\ge 1$ and $n\in\mathbb{N}$, let $f_d(n)$ be the minimum integer such that for every set $P\subset\mathbb{R}^d$ of size $|P|=n$ with $\|x-y\|\ge 1$ for all distinct $x,y\in P$, the number of unordered pairs $\{x,y\}\subset P$ with $\|x-y\|=1$ is at most $f_d(n)$. The problem asks for estimates of $f_d(n)$ (as $n\to\infty$ with $d$ fixed).

QUICK LITERATURE/CONTEXT CHECK

The problem statement records: $f_1(n)=n-1$, $f_2(n)<3n$ by a degree argument, and a refined planar bound $f_2(n)<3n-c n^{1/2}$ due to Erdős. It also records a conjectural exact planar value for certain $n$, and a claimed asymptotic refinement in $d=3$. I do not add external results here.

ATTACK PLAN

  • Proof track (partial). Relate $f_d(n)$ to the kissing number in $\mathbb{R}^d$ to get a clean linear upper bound. In $d=2$, exhibit a triangular-lattice construction giving $3n-O(\sqrt n)$ unit pairs and compute its exact unit-pair count.
  • Disproof track. Not applicable (estimation problem).

WORK

Fast reality check.
For $d=2$, the configuration of one point and a regular hexagon around it gives $n=7$ and $12$ unit pairs. A brute-force check on the triangular lattice within radius $2$ shows this is best possible among 7-point subsets of that lattice.
Definition (Kissing number constant): Let $\tau_d$ be the maximum size of a set $S\subset \mathbb{S}^{d-1}$ with $\|u-v\|\ge 1$ for all distinct $u,v\in S$. Equivalently, $\tau_d$ is the maximum number of points on the unit sphere such that mutual distances are at least $1$. (Geometrically, $\tau_d$ equals the maximum number of disjoint radius-$1/2$ balls that can simultaneously touch a central radius-$1/2$ ball.)
Lemma (Degree bound via kissing number): Let $P\subset\mathbb{R}^d$ have all pairwise distances $\ge 1$. Form the graph $G$ on vertex set $P$ with an edge between $x\ne y$ iff $\|x-y\|=1$. Then every vertex has degree at most $\tau_d$, and hence \[ \#E(G)\le \frac{\tau_d}{2}\,|P|. \] In particular, $f_d(n)\le \frac{\tau_d}{2}n$ for all $n$.
Proof: Fix $p\in P$. Let $N(p)=\{q\in P: \|q-p\|=1\}$ be its unit neighbors. For any distinct $q,r\in N(p)$, we have $\|q-r\|\ge 1$ by the separation assumption. Map each $q\in N(p)$ to the unit vector $u_q=(q-p)/\|q-p\|\in\mathbb{S}^{d-1}$. Then $\|u_q-u_r\|=\|q-r\|$ (since $\|q-p\|=\|r-p\|=1$), so $\|u_q-u_r\|\ge 1$. Thus $\{u_q: q\in N(p)\}\subset\mathbb{S}^{d-1}$ is a set of size $|N(p)|$ with pairwise distances at least $1$, so $|N(p)|\le \tau_d$ by definition. The edge bound follows by summing degrees and dividing by $2$. ∎
Lemma (Planar triangular-lattice construction): Let $m\ge 0$. Consider the triangular lattice in axial coordinates $\Lambda=\{(a,b): a,b\in\mathbb{Z}\}$ with unit-distance edges between points whose differences are $(\pm1,0),(0,\pm1),(\pm1,\mp1)$. Let \[ H_m:=\{(a,b)\in\Lambda: \max(|a|,|b|,|a+b|)\le m\} \] (the "centered hexagon" of radius $m$). Then \[ |H_m|=3m^2+3m+1,\qquad \#\{\{x,y\}\subset H_m: \|x-y\|=1\}=9m^2+3m. \] In particular, this gives a configuration with $n=3m^2+3m+1$ points and $3n-(6m+3)=3n-O(\sqrt n)$ unit pairs.
Proof: The count $|H_m|=3m^2+3m+1$ is standard for a centered hexagon: there is a central point and $6k$ points on the "ring" at lattice distance $k$ for each $1\le k\le m$, so $|H_m|=1+\sum_{k=1}^m 6k=1+3m(m+1)=3m^2+3m+1$.

Now count unit edges in the induced unit-distance graph on $H_m$. Every interior vertex has degree $6$. The boundary of $H_m$ is a hexagon with $6m$ boundary vertices: it has $6$ corner vertices and $6(m-1)$ non-corner boundary vertices. A direct neighbor check in axial coordinates shows:

  • each corner boundary vertex has exactly $3$ neighbors within $H_m$,
  • each non-corner boundary vertex has exactly $4$ neighbors within $H_m$.
Thus the total degree deficit from $6$ is \[ \mathrm{def}:=\sum_{v\in H_m} (6-\deg(v)) = 6\cdot(6-3) + 6(m-1)\cdot(6-4) =18+12(m-1)=12m+6. \] Therefore \[ 2|E|=\sum_{v\in H_m}\deg(v)=6|H_m|-\mathrm{def}. \] Plugging $|H_m|=3m^2+3m+1$ and $\mathrm{def}=12m+6$ gives \[ 2|E|=6(3m^2+3m+1)-(12m+6)=18m^2+18m+6-12m-6=18m^2+6m, \] so $|E|=9m^2+3m$.

Finally, since $m\asymp \sqrt n$ when $n=3m^2+3m+1$, the error term $6m+3$ is $O(\sqrt n)$, yielding $|E|=3n-O(\sqrt n)$. ∎

VERIFICATION

  • The kissing-number lemma is purely geometric and uses only the separation hypothesis.
  • In the planar construction, I checked the edge counts computationally for $m=0,1,2,3,4$: $(|H_m|,|E|)=(1,0),(7,12),(19,42),(37,90),(61,156)$, matching $3m^2+3m+1$ and $9m^2+3m$.
  • Note: the problem statement contains a conjectural exact formula $f_2(3n^2+3n+1)=9n^2+6n$. The natural centered-hexagon triangular-lattice patch above gives $9n^2+3n$ unit pairs for that number of points; I did not resolve the discrepancy.

FINAL

UNRESOLVED.
  1. (i) Strongest proved partial result here: for all $d$, $f_d(n)\le (\tau_d/2)n$; and in $d=2$ there exist configurations with $3n-O(\sqrt n)$ unit pairs.
  2. (ii) First gap: determine the correct second-order term in $d=2$ (and in particular the exact value at the "hexagonal numbers"), and in $d=3$ prove or disprove the claimed $6n-\Theta(n^{2/3})$ behaviour.
  3. (iii) Top 3 next moves: $1$ for $d=2$, formulate the extremal problem as maximizing edges in a planar unit-distance graph with minimum separation and analyze boundary effects rigorously; $2$ attempt a discrete isoperimetric inequality on the hexagonal/triangular lattice to show optimality of near-hexagonal patches; $3$ computationally optimize for small $n$ to test the conjectured exact values.
  4. (iv) Minimal counterexample structure (to "triangular lattice is extremal" in $d=2$): a planar packing close to hexagonal but with local defects that increase the unit-edge count without violating separation, likely concentrated near the boundary.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Go to contribution →

Math-6138-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-6138

Erdős Problem 1084 (unit distances under separation)

FORMAL RESTATEMENT

For an integer $d\ge 1$ and $n\in\mathbb{N}$, let $f_d(n)$ be the minimum integer such that for every set $P\subset\mathbb{R}^d$ of size $|P|=n$ with $\|x-y\|\ge 1$ for all distinct $x,y\in P$, the number of unordered pairs $\{x,y\}\subset P$ with $\|x-y\|=1$ is at most $f_d(n)$. The problem asks for estimates of $f_d(n)$ (as $n\to\infty$ with $d$ fixed).

QUICK LITERATURE/CONTEXT CHECK

The problem statement records: $f_1(n)=n-1$, $f_2(n)<3n$ by a degree argument, and a refined planar bound $f_2(n)<3n-c n^{1/2}$ due to Erdős. It also records a conjectural exact planar value for certain $n$, and a claimed asymptotic refinement in $d=3$. I do not add external results here.

ATTACK PLAN

  • Proof track (partial). Relate $f_d(n)$ to the kissing number in $\mathbb{R}^d$ to get a clean linear upper bound. In $d=2$, exhibit a triangular-lattice construction giving $3n-O(\sqrt n)$ unit pairs and compute its exact unit-pair count.
  • Disproof track. Not applicable (estimation problem).

WORK

Fast reality check.
For $d=2$, the configuration of one point and a regular hexagon around it gives $n=7$ and $12$ unit pairs. A brute-force check on the triangular lattice within radius $2$ shows this is best possible among 7-point subsets of that lattice.
Definition (Kissing number constant): Let $\tau_d$ be the maximum size of a set $S\subset \mathbb{S}^{d-1}$ with $\|u-v\|\ge 1$ for all distinct $u,v\in S$. Equivalently, $\tau_d$ is the maximum number of points on the unit sphere such that mutual distances are at least $1$. (Geometrically, $\tau_d$ equals the maximum number of disjoint radius-$1/2$ balls that can simultaneously touch a central radius-$1/2$ ball.)
Lemma (Degree bound via kissing number): Let $P\subset\mathbb{R}^d$ have all pairwise distances $\ge 1$. Form the graph $G$ on vertex set $P$ with an edge between $x\ne y$ iff $\|x-y\|=1$. Then every vertex has degree at most $\tau_d$, and hence \[ \#E(G)\le \frac{\tau_d}{2}\,|P|. \] In particular, $f_d(n)\le \frac{\tau_d}{2}n$ for all $n$.
Proof: Fix $p\in P$. Let $N(p)=\{q\in P: \|q-p\|=1\}$ be its unit neighbors. For any distinct $q,r\in N(p)$, we have $\|q-r\|\ge 1$ by the separation assumption. Map each $q\in N(p)$ to the unit vector $u_q=(q-p)/\|q-p\|\in\mathbb{S}^{d-1}$. Then $\|u_q-u_r\|=\|q-r\|$ (since $\|q-p\|=\|r-p\|=1$), so $\|u_q-u_r\|\ge 1$. Thus $\{u_q: q\in N(p)\}\subset\mathbb{S}^{d-1}$ is a set of size $|N(p)|$ with pairwise distances at least $1$, so $|N(p)|\le \tau_d$ by definition. The edge bound follows by summing degrees and dividing by $2$. ∎
Lemma (Planar triangular-lattice construction): Let $m\ge 0$. Consider the triangular lattice in axial coordinates $\Lambda=\{(a,b): a,b\in\mathbb{Z}\}$ with unit-distance edges between points whose differences are $(\pm1,0),(0,\pm1),(\pm1,\mp1)$. Let \[ H_m:=\{(a,b)\in\Lambda: \max(|a|,|b|,|a+b|)\le m\} \] (the "centered hexagon" of radius $m$). Then \[ |H_m|=3m^2+3m+1,\qquad \#\{\{x,y\}\subset H_m: \|x-y\|=1\}=9m^2+3m. \] In particular, this gives a configuration with $n=3m^2+3m+1$ points and $3n-(6m+3)=3n-O(\sqrt n)$ unit pairs.
Proof: The count $|H_m|=3m^2+3m+1$ is standard for a centered hexagon: there is a central point and $6k$ points on the "ring" at lattice distance $k$ for each $1\le k\le m$, so $|H_m|=1+\sum_{k=1}^m 6k=1+3m(m+1)=3m^2+3m+1$.

Now count unit edges in the induced unit-distance graph on $H_m$. Every interior vertex has degree $6$. The boundary of $H_m$ is a hexagon with $6m$ boundary vertices: it has $6$ corner vertices and $6(m-1)$ non-corner boundary vertices. A direct neighbor check in axial coordinates shows:

  • each corner boundary vertex has exactly $3$ neighbors within $H_m$,
  • each non-corner boundary vertex has exactly $4$ neighbors within $H_m$.
Thus the total degree deficit from $6$ is \[ \mathrm{def}:=\sum_{v\in H_m} (6-\deg(v)) = 6\cdot(6-3) + 6(m-1)\cdot(6-4) =18+12(m-1)=12m+6. \] Therefore \[ 2|E|=\sum_{v\in H_m}\deg(v)=6|H_m|-\mathrm{def}. \] Plugging $|H_m|=3m^2+3m+1$ and $\mathrm{def}=12m+6$ gives \[ 2|E|=6(3m^2+3m+1)-(12m+6)=18m^2+18m+6-12m-6=18m^2+6m, \] so $|E|=9m^2+3m$.

Finally, since $m\asymp \sqrt n$ when $n=3m^2+3m+1$, the error term $6m+3$ is $O(\sqrt n)$, yielding $|E|=3n-O(\sqrt n)$. ∎

VERIFICATION

  • The kissing-number lemma is purely geometric and uses only the separation hypothesis.
  • In the planar construction, I checked the edge counts computationally for $m=0,1,2,3,4$: $(|H_m|,|E|)=(1,0),(7,12),(19,42),(37,90),(61,156)$, matching $3m^2+3m+1$ and $9m^2+3m$.
  • Note: the problem statement contains a conjectural exact formula $f_2(3n^2+3n+1)=9n^2+6n$. The natural centered-hexagon triangular-lattice patch above gives $9n^2+3n$ unit pairs for that number of points; I did not resolve the discrepancy.

FINAL

UNRESOLVED.
  1. (i) Strongest proved partial result here: for all $d$, $f_d(n)\le (\tau_d/2)n$; and in $d=2$ there exist configurations with $3n-O(\sqrt n)$ unit pairs.
  2. (ii) First gap: determine the correct second-order term in $d=2$ (and in particular the exact value at the "hexagonal numbers"), and in $d=3$ prove or disprove the claimed $6n-\Theta(n^{2/3})$ behaviour.
  3. (iii) Top 3 next moves: $1$ for $d=2$, formulate the extremal problem as maximizing edges in a planar unit-distance graph with minimum separation and analyze boundary effects rigorously; $2$ attempt a discrete isoperimetric inequality on the hexagonal/triangular lattice to show optimality of near-hexagonal patches; $3$ computationally optimize for small $n$ to test the conjectured exact values.
  4. (iv) Minimal counterexample structure (to "triangular lattice is extremal" in $d=2$): a planar packing close to hexagonal but with local defects that increase the unit-edge count without violating separation, likely concentrated near the boundary.

Go to contribution →