# Discrete Geometry Classic: Two-distance Sets

This post presents another simple and elegant argument in Discrete Geometry. This classic is based on the so-called “Linear Algebra method”.

Warm-up problem. What is the maximum size of a set ${\cal P} \subset {\mathbb R}^d$ such that the distance between every two points of the set is 1?

By taking the vertices of a $d$-dimensional simplex with side length 1 in ${\mathbb R}^d$, we obtain $d+1$ points that span only the distance 1. It is not difficult to show that a set of $d+2$ points in ${\mathbb R}^d$ cannot span a single distance.

The two-distance sets problem. A point set $\cal P$ is a two-distance set if there exist $r,s\in {\mathbb R}$ such that the distance between every pair of points of $\cal P$ is either $r$ or $s$. What is the maximum size of a two-distance set in ${\mathbb R}^d$?

There is a simple trick for constructing a two-distance set of size $\binom{d}{2}$ in ${\mathbb R}^d$. You might like to spend a minute or two thinking about it. Here is a picture of Euler to prevent you from seeing the answer before you wish to.

Consider the set of all points in ${\mathbb R}^d$ that have two coordinates with value 1 and the other $d-2$ coordinates with value 0. There are $\binom{d}{2}$ such points, and the distance between every pair of those is either 1 or 2.

Larman, Rogers, and Seidel showed that the above example is not far from being tight.

Theorem. Every two-distance set in ${\mathbb R}^d$ has size at most $\binom{d}{2}+3d+2$.

Proof. Let ${\cal P} = \{p_1,p_2,\ldots, p_m\}$ be a two-distance set in ${\mathbb R}^d$, and denote the two distances as $r,s\in {\mathbb R}$. Given points $a,b\in {\mathbb R}^d$, we denote the distance between them as $D(a,b)$. We refer to a point in ${\mathbb R}^d$ as $x=(x_1,\ldots,x_d)$. For $1\le j \le m$, define the polynomial $f_j\in {\mathbb R}[x_1,\ldots,x_d]$ as

$f_j(x) = \left(D(x,p_j)^2 - r^2\right) \cdot \left(D(x,p_j)^2 - s^2\right).$

That is, $f_j$ is a polynomial of degree four in $x_1,\ldots,x_d$ that vanishes on points at distance $r$ or $s$ from $p_j$. Every such polynomial is a linear combination of the polynomials

$\left(\sum_{j=1}^d x_j^2\right)^2,\qquad x_k \sum_{j=1}^d x_j^2,\qquad x_k,\qquad x_\ell x_k,\qquad 1,$

for every $1\le \ell, k\le d$. Since every $f_j$ is a linear combination of $t = \binom{d}{2}+3d+2$ polynomials, we can represent $f_j$ as a vector in ${\mathbb R}^t$. In particular, the vector $V = (v_1,\ldots,v_t)$ corresponds to the polynomial

$v_1 \cdot \left(\sum_{j=1}^d x_j^2\right)^2 + v_2\cdot x_1 \sum_{j=1}^d x_j^2 + v_3\cdot x_2 \sum_{j=1}^d x_j^2 + \cdots + v_{t} \cdot 1.$

For $1\le j \le m$, let $V_j$ denote the vector corresponding to $f_j$. Consider $\alpha_1,\ldots,\alpha_m\in {\mathbb R}$ such that $\sum_{j=1}^m \alpha_j V_j = 0$. Let $g(x) = \sum_{j=1}^m \alpha_j f_j(x)$. By definition, the polynomial $g(x)$ is identically zero. For some fixed $p_k\in {\cal P}$, note that $f_j(p_k)=0$ for every $j\neq k$ and that $f_j(p_j) = r^2s^2$. Combining the above implies

$g(p_k) = \sum_{j=1}^m \alpha_j f_j(p_k) = \alpha_kr^2s^2.$

Since $g(x)=0$, we have that $\alpha_k=0$. That is, the only solution $\sum_{j=1}^m \alpha_j V_j = 0$ is $\alpha_1=\cdots = \alpha_m = 0$. This implies that the vectors $V_1,\ldots,V_m$ are linearly independent. Since these vectors are in ${\mathbb R}^t$, we conclude that $m \le t = \binom{d}{2}+3d+2$. $\Box$

One can improve the above bound by showing that the polynomials $f_j$ are contained in a smaller vector space. This is left as an exercise of your googling capabilities.