gpt pro 5.2 attempt on Math-5802

Let $x_1,\ldots,x_n\in \mathbb{R}^3$ be the vertices of a convex polyhedron. Are there at least\[(1-o(1))\frac{n}{2}\]many distinct distances between the $x_i$? For the similar problem in $\mathbb{R}^2$ there are always at least $n/2$ distances, as proved by Altman [Al63] (see [93] ). In [Er75f] Erdős claims that Altman proved that the vertices determine $\gg n$ many distinct distances, but gives no reference. References [Al63] Altman, E., On a problem of P. Erdős . Amer. Math. Monthly $1963$, 148-157. [Er75f] Erdős, Paul, On some problems of elementary and combinatorial geometry . Ann. Mat. Pura Appl. $4$ $1975$, 99-108.

1) FORMAL RESTATEMENT Let $n\ge 4$ and let $x_1,\ldots,x_n\in\mathbb{R}^3$ be the vertices of a convex polyhedron, i.e. each $x_i$ is a vertex (extreme point) of $\mathrm{conv}(\{x_1,\ldots,x_n\})$. Let \[ D:=\left|\left\{|x_i-x_j|:1\le i<j\le n\right\}\right| \] be the number of distinct interpoint distances. Question: must we have \[ D\ \ge\ (1-o(1))\frac{n}{2}\qquad\text{as }n\to\infty\ ? \]

Edge cases: for $n=4$ a regular tetrahedron has $D=1$, so the asymptotic claim is not meant for small $n$.

2) QUICK LITERATURE/CONTEXT CHECK The problem statement mentions that in $\mathbb{R}^2$ the vertices of a convex polygon always determine at least $n/2$ distinct distances (Altman). I do not assume any external theorems beyond what is stated.

3) ATTACK PLAN Proof-track ideas: - Use convexity to get many distinct distances from a well-chosen vertex (analogue of planar convex-position problems). - Use global algebraic methods to show that few distinct distances force $n$ to be small ("few-distance sets" methods).

Disproof-track ideas: - Construct large convex polyhedra with only $o(n)$ distinct distances, e.g. by placing vertices on few spheres/circles with high symmetry.

I cannot reach the conjectured linear bound; I can prove a general lower bound $D=\Omega(n^{1/3})$ valid for all point sets in $\mathbb{R}^3$.

4) WORK

Lemma 1 (equidistant sets in $\mathbb{R}^3$ have size at most $4$). If $P=\{p_1,\ldots,p_m\}\subset\mathbb{R}^3$ satisfies $|p_i-p_j|=\lambda$ for all $i\neq j$, then $m\le 4$.

Proof. Translate so that $p_m=0$. Let $v_i:=p_i$ for $i=1,\ldots,m-1$. Then $|v_i|^2=\lambda^2$ for all $i$ and $|v_i-v_j|^2=\lambda^2$ for $i\neq j$. Expanding gives $|v_i|^2+|v_j|^2-2v_i\cdot v_j=\lambda^2$, hence $2\lambda^2-2v_i\cdot v_j=\lambda^2$, so $v_i\cdot v_j=\lambda^2/2$ for all $i\neq j$. Form the Gram matrix $G=(v_i\cdot v_j)_{1\le i,j\le m-1}$. It has diagonal entries $\lambda^2$ and off-diagonal entries $\lambda^2/2$, so $G=\frac{\lambda^2}{2}(J_{m-1}+I_{m-1})$, where $J$ is the all-ones matrix. The eigenvalues of $J_{m-1}$ are $(m-1)$ (once) and $0$ (multiplicity $m-2$). Therefore the eigenvalues of $G$ are $\frac{\lambda^2}{2}(m)$ (once) and $\frac{\lambda^2}{2}$ (multiplicity $m-2$), all nonzero. Hence $\mathrm{rank}(G)=m-1$. But $\mathrm{rank}(G)\le 3$ because $G$ is the Gram matrix of vectors in $\mathbb{R}^3$. Thus $m-1\le 3$ and $m\le 4$. $\square$

Lemma 2 (a polynomial method bound for distance sets in $\mathbb{R}^3$). Let $P=\{p_1,\ldots,p_n\}\subset\mathbb{R}^3$ and let $D(P)$ be the number of distinct distances among pairs. Then \[ n\ \le\ \binom{2D(P)+3}{3}. \] In particular, $D(P)\ge c\,n^{1/3}$ for an absolute constant $c>0$.

Proof. Let $\Delta$ be the set of distinct squared distances determined by $P$: $\Delta:=\{|p_i-p_j|^2:1\le i<j\le n\}$, so $|\Delta|=D(P)$. For each $i$, define a polynomial in three variables \[ F_i(x):=\prod_{t\in\Delta}\left(\|x-p_i\|^2-t\right),\qquad x\in\mathbb{R}^3. \] Each factor has degree $2$, so $\deg(F_i)\le 2|\Delta|=2D(P)$. Evaluate at the points $p_j$: if $j\neq i$, then $\|p_j-p_i\|^2\in\Delta$, so one factor vanishes and hence $F_i(p_j)=0$. On the other hand, $F_i(p_i)=\prod_{t\in\Delta}(-t)\neq 0$ because all $t\in\Delta$ are positive. Thus the $n\times n$ matrix $M=(F_i(p_j))_{i,j}$ is diagonal with nonzero diagonal entries, so $\mathrm{rank}(M)=n$. Let $V$ be the real vector space of polynomials in $(x_1,x_2,x_3)$ of total degree at most $2D(P)$. The rows of $M$ lie in the image of the evaluation map $\mathrm{ev}:V\to\mathbb{R}^n$, $F\mapsto (F(p_1),\ldots,F(p_n))$. Therefore $n=\dim(\mathrm{span}\{\text{rows of }M\})\le \dim(\mathrm{im}(\mathrm{ev}))\le \dim(V)$. It remains to compute $\dim(V)$. A monomial $x_1^{a}x_2^{b}x_3^{c}$ has total degree $a+b+c\le 2D(P)$. The number of triples $(a,b,c)\in\mathbb{Z}_{\ge 0}^3$ with $a+b+c\le m$ equals $\binom{m+3}{3}$ (stars-and-bars, summing over $a+b+c=r$). With $m=2D(P)$ this gives $\dim(V)=\binom{2D(P)+3}{3}$, proving the bound. The final asymptotic $D(P)\ge c\,n^{1/3}$ follows because $\binom{2D+3}{3}=O(D^3)$. $\square$

Corollary 3 (applies to the convex-polyhedron case). If $x_1,\ldots,x_n$ are vertices of a convex polyhedron in $\mathbb{R}^3$, then $D\ge c\,n^{1/3}$. (This is immediate from Lemma 2 because it assumes no convexity.)

FAST REALITY CHECK (small cases on the integer grid). I searched subsets of the $3\times 3\times 3$ grid $\{0,1,2\}^3$ and required that all points be vertices of their convex hull. Minimized the number of distinct squared distances (this equals the number of distinct distances). Witnesses: - $n=4$: minimum found $D=1$, achieved by $\{(0,0,0), (0,1,1), (1,0,1), (1,1,0)\}$ (a regular tetrahedron of edge length $\sqrt 2$). - $n=5$: minimum found $D=2$, achieved by $\{(0,0,1), (0,1,0), (0,1,2), (0,2,1), (1,1,1)\}$. Random search in $\{0,1,2,3\}^3$ (30k samples each) found: - $n=6$: $D=3$ with $\{(2,1,0), (1,2,0), (1,1,1), (0,2,1), (1,2,2), (2,2,1)\}$. - $n=7$: $D=5$ with $\{(3,1,0), (2,1,0), (2,0,1), (1,2,1), (2,1,1), (3,2,0), (2,0,0)\}$. - $n=8$: $D=5$ with $\{(2,1,2), (0,0,1), (1,2,0), (2,1,0), (1,1,3), (1,0,2), (1,2,2), (1,0,0)\}$. These computations only probe a tiny discrete search space but confirm that $D$ can be far below $n/2$ for small $n$.

5) VERIFICATION - Lemma 1: I checked the Gram-matrix computation and the rank bound $\mathrm{rank}(G)\le 3$ (vectors in $\mathbb{R}^3$) carefully; all eigenvalues are nonzero, so $\mathrm{rank}(G)=m-1$. - Lemma 2: the diagonal-matrix argument uses that $\Delta$ contains all squared distances among the points, guaranteeing $F_i(p_j)=0$ for $j\neq i$ and $F_i(p_i)\neq 0$. - The dimension count $\binom{m+3}{3}$ is justified by stars-and-bars: for each $r\le m$, the number of solutions to $a+b+c=r$ is $\binom{r+2}{2}$, and $\sum_{r=0}^m \binom{r+2}{2}=\binom{m+3}{3}$.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: for any $n$ points in $\mathbb{R}^3$ (hence also for vertices of a convex polyhedron), the number of distinct distances satisfies $D=\Omega(n^{1/3})$ (Lemma 2). (ii) First gap (crisp): upgrade the general lower bound from $n^{1/3}$ to $(1-o(1))n/2$ under the additional hypothesis that the points are vertices of a convex polyhedron. (iii) Top 3 next moves (concrete): 1. Prove that some vertex of a convex polyhedron determines $\ge (1-o(1))n/2$ distinct distances to the other vertices; then $D$ is at least that. 2. Use convexity to bound the number of repeated distances from a vertex (e.g. via spherical geometry of directions / antipodal pairs) and sum over vertices. 3. Computational search: optimize convex polyhedra with small distance sets (e.g. via integer-coordinate convex hulls) to guess extremal families and then attempt a stability theorem. (iv) Minimal counterexample structure (if the conjecture is true): a sequence of convex polyhedra with $D=o(n)$ would have to realize most edges (and many non-edges) using a very small set of radii, i.e. behave like a large "few-distance" set in $\mathbb{R}^3$; Lemma 2 suggests that such a set would need strong algebraic structure beyond generic convexity.