Maximum two-distance sets in Euclidean spaces of dimension up to twenty-one

Abstract

A two-distance set is a finite set of points in ℝᵈ whose pairwise distances take exactly two values; g(d) denotes the largest cardinality of such a set. The values g(d) were known for d ≤ 8 (Einhorn–Schoenberg, Lisoněk) and, since a recent computer-assisted classification, for 9 ≤ d ≤ 12, where g(d) = C(d+1, 2) is attained by the midpoints of the edges of a regular simplex. We prove that g(d) = C(d+1, 2) for every d with 10 ≤ d ≤ 21, and that the simplex-midpoint set J(d + 1, 2) is the only two-distance set of that size up to similarity. The underlying statement, valid in every dimension d ≥ 10, is that a set in ℝᵈ whose squared distances are 2 and 4 has at most C(d+1, 2) points, with equality only for J(d + 1, 2). The proof replaces the exhaustive clique searches that were used in dimensions 9 to 12 by a combinatorial argument. Each component of such a set under its short distances is, up to translation, a subset of a root lattice; in the lattice Aₙ it becomes a uniform family of subsets with two intersection sizes, so that the Ray-Chaudhuri–Wilson bound C(n+1, 2) applies and the Ahlswede–Khachatrian theorem identifies the extremal families; in Dₙ it becomes a binary code with distances 2 and 4, for which the bound 1 + C(n, 2) of Barg and Musin applies; and root lattices with several irreducible components are handled by a slicing lemma whose only numerical inputs are a few invariants of E₆, E₇ and E₈, computed by a small clique search. For 13 ≤ d ≤ 21 the remaining distance ratios allowed by the Larman–Rogers–Seidel theorem are excluded by the recent bounds of Chen and Yu. All computations are reproduced by a second, independently written program, and the method recovers the previously known values g(10), g(11), g(12) and the bound 45 for the root lattices of rank 9. The authors are listed in alphabetical order and contributed equally.