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.