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 such that the distance between every two points of the set is 1?

By taking the vertices of a -dimensional simplex with side length 1 in , we obtain points that span only the distance 1. It is not difficult to show that a set of points in cannot span a single distance.

**The two-distance sets problem.**A point set is a

*two-distance set*if there exist such that the distance between every pair of points of is either or . What is the maximum size of a two-distance set in ?

There is a simple trick for constructing a two-distance set of size in . 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 that have two coordinates with value 1 and the other coordinates with value 0. There are 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 has size at most .*

**Proof.**Let be a two-distance set in , and denote the two distances as . Given points , we denote the distance between them as . We refer to a point in as . For , define the polynomial as

That is, is a polynomial of degree four in that vanishes on points at distance or from . Every such polynomial is a linear combination of the polynomials

for every . Since every is a linear combination of polynomials, we can represent as a vector in . In particular, the vector corresponds to the polynomial

For , let denote the vector corresponding to . Consider such that . Let . By definition, the polynomial is identically zero. For some fixed , note that for every and that . Combining the above implies

Since , we have that . That is, the only solution is . This implies that the vectors are linearly independent. Since these vectors are in , we conclude that .

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

Advertisements

Pingback: Linear Algebra Riddle – Some Plane Truths