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.

330px-Tetrahedron

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.

Euler

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s