we-solve (beta)

Math-6139-A2 · revision r1 · on Math-6139

gpt pro 5.2 attempt on Math-6139

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem 1085 (unit distances without separation)
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. Fast reality check.
  7. VERIFICATION
  8. FINAL

Erdős Problem 1085 (unit distances without separation)

FORMAL RESTATEMENT

For integers $d\ge 1$ and $n\in\mathbb{N}$, let $f_d(n)$ be the minimum integer such that every set $P\subset\mathbb{R}^d$ with $|P|=n$ determines at most $f_d(n)$ unordered pairs $\{x,y\}\subset P$ with $\|x-y\|=1$. Equivalently, $f_d(n)=\max\{\#\{\{x,y\}\subset P:\|x-y\|=1\}: P\subset\mathbb{R}^d,\ |P|=n\}$. The problem asks for estimates of $f_d(n)$, especially for $d=2,3$.

QUICK LITERATURE/CONTEXT CHECK

The problem statement records the best-known bounds in $d=2$ and $d=3$ and the asymptotically tight quadratic behaviour for $d\ge 4$ (including the Lenz construction and an Erdős-Stone based upper bound for $d\ge 4$). I do not add other literature.

ATTACK PLAN

  • Proof track (partial). Give a completely self-contained quadratic lower bound construction in $d\ge 4$ (Lenz-type: points on mutually orthogonal circles), and a general upper bound from forbidding large equidistant cliques plus Turán.
  • Disproof track. Not applicable (estimation problem).

WORK

Fast reality check.
For $d=4$, taking two circles in orthogonal planes of radius $1/\sqrt2$ and placing $m$ points on each gives $n=2m$ points with exactly $m^2$ cross pairs at distance $1$. Choosing $m=3$ equally spaced points on each circle, a brute-force check gives $9$ cross pairs and the set of cross squared distances is exactly $\{1\}$ (within-circle squared distances are $\{3/2\}$).
Lemma (Maximum size of an equidistant set): In $\mathbb{R}^d$, there do not exist $d+2$ points with all pairwise distances equal to $1$. Equivalently, any clique in a unit-distance graph in $\mathbb{R}^d$ has size at most $d+1$.
Proof: Suppose for contradiction that $p_1,\dots,p_{d+2}\in\mathbb{R}^d$ satisfy $\|p_i-p_j\|=1$ for all $i\ne j$. Translate so that $p_{d+2}=0$. Then $\|p_i\|=1$ for $i\le d+1$, and for $1\le i<j\le d+1$, \[ 1=\|p_i-p_j\|^2=\|p_i\|^2+\|p_j\|^2-2p_i\cdot p_j=1+1-2p_i\cdot p_j, \] so $p_i\cdot p_j=1/2$. Let $G$ be the $(d+1)\times(d+1)$ Gram matrix $G=(p_i\cdot p_j)_{1\le i,j\le d+1}$. Then $G$ has diagonal entries $1$ and off-diagonal entries $1/2$, so \[ G=\frac12 I_{d+1}+\frac12 J_{d+1}, \] where $J_{d+1}$ is the all-ones matrix. The eigenvalues of $J_{d+1}$ are $d+1$ (once) and $0$ (multiplicity $d$), hence the eigenvalues of $G$ are $\tfrac12+\tfrac12(d+1)=\tfrac{d+2}{2}$ (once) and $\tfrac12$ (multiplicity $d$). Thus $\mathrm{rank}(G)=d+1$. But $\mathrm{rank}(G)\le d$ because $G$ is the Gram matrix of $d+1$ vectors in $\mathbb{R}^d$. Contradiction. Therefore no such $d+2$ points exist. ∎
Lemma (A general Turán-type upper bound): For any $d\ge 1$ and $n$, \[ f_d(n)\le \left(1-\frac{1}{d+1}\right)\frac{n^2}{2}. \]
Proof: Given $P\subset\mathbb{R}^d$ of size $n$, let $G$ be its unit-distance graph. By the previous lemma, $G$ is $K_{d+2}$-free. Turán's theorem for $K_{r}$-free graphs states that a $K_r$-free graph on $n$ vertices has at most $\left(1-\frac{1}{r-1}\right)\frac{n^2}{2}$ edges. Taking $r=d+2$ yields $|E(G)|\le \left(1-\frac{1}{d+1}\right)\frac{n^2}{2}$. Since $f_d(n)$ is the maximum possible $|E(G)|$, the same bound holds for $f_d(n)$. ∎
Lemma (Lenz-type construction for $d\ge 4$): Let $d\ge 4$, and set $p:=\lfloor d/2\rfloor\ge 2$. Then for all $n$ there exists a set $P\subset\mathbb{R}^d$ of $|P|=n$ points with \[ \#\{\{x,y\}\subset P: \|x-y\|=1\}\ \ge\ \frac{p-1}{2p}n^2 - O(p). \] In particular, $f_d(n)\ge \frac{p-1}{2p}n^2-O(1)$.
Proof: Embed $p$ pairwise orthogonal 2-dimensional linear subspaces $V_1,\dots,V_p\subset\mathbb{R}^d$ (possible since $2p\le d$). In each $V_i$, consider the circle $C_i:=\{x\in V_i: \|x\|=1/\sqrt2\}$, centered at the origin. For any $x\in C_i$ and $y\in C_j$ with $i\ne j$, orthogonality gives $x\cdot y=0$, hence \[ \|x-y\|^2=\|x\|^2+\|y\|^2-2x\cdot y = \frac12+\frac12-0=1. \] Thus every pair of points chosen from two different circles is at unit distance.

Now distribute $n$ points among the circles: choose integers $n_1,\dots,n_p\ge 0$ with $\sum_i n_i=n$, and pick any $n_i$ distinct points on each $C_i$. The number of unit-distance pairs between different circles equals $\sum_{1\le i<j\le p} n_i n_j = \frac12\left(n^2-\sum_{i=1}^p n_i^2\right)$. This is maximized when the $n_i$ are as equal as possible, giving $\sum_i n_i^2\le \lceil n/p\rceil^2+(p-1)\lfloor n/p\rfloor^2\le n^2/p + O(p)$. Therefore \[ \sum_{i<j}n_i n_j \ge \frac12\left(n^2-\frac{n^2}{p}\right)-O(p)=\frac{p-1}{2p}n^2-O(p). \] Any additional unit pairs within a single circle can only increase the count, so this lower bound holds for the full unit-distance count. ∎

VERIFICATION

  • The equidistant-set lemma is a standard rank/Gram-matrix argument; all eigenvalues computed explicitly.
  • The Lenz construction uses only orthogonality of subspaces and radii $1/\sqrt2$; the distance computation is exact.
  • The Turán bound is not sharp for $d\ge 4$ compared to the conjectured/recorded asymptotic $(p-1)/(2p)$, but it is rigorous and self-contained.

FINAL

UNRESOLVED.
  1. (i) Strongest proved partial result here: for $d\ge 4$ with $p=\lfloor d/2\rfloor$, $\frac{p-1}{2p}n^2-O(1)\le f_d(n)\le \left(1-\frac{1}{d+1}\right)\frac{n^2}{2}$.
  2. (ii) First gap: for $d=2,3$, close the gap between known lower and upper bounds (as recorded in the problem statement). For $d\ge 4$, prove the sharp asymptotic upper constant $(p-1)/(2p)$ without appealing to results not already in the file.
  3. (iii) Top 3 next moves: $1$ understand which complete multipartite graphs are forbidden in unit-distance graphs in $\mathbb{R}^d$; $2$ attempt to show near-extremal graphs must be approximately $p$-partite, matching the Lenz construction; $3$ computational experiments in $d=4$ to see extremal configurations for moderate $n$ beyond the circle construction.
  4. (iv) Minimal counterexample structure (to the sharp quadratic constant in $d\ge 4$): a unit-distance graph on $n$ vertices with edge density exceeding $(p-1)/(2p)+\varepsilon$, which would necessarily force a rich family of geometric constraints (many large cliques/near-cliques) contradicting Euclidean realizability.