Maximality of the added-vector codes in the Cohn-Li kissing constructions
Abstract
Cohn and Li (arXiv:2411.04916) improved the known lower bounds for the kissing number in
dimensions 17 through 21. Each of their configurations fixes a large family of vectors and then
adjoins further points indexed by a binary code, here called the added-vector code; the
improvement over Leech's records is exactly the size of that code. Cohn and Li prove their choice
is largest possible only in dimension 17, and remark that it is unclear what the limits of such
constructions might be. Ho subsequently improved dimension 19 by enlarging that code from 1024 to
1280 words.
This note determines the maximum size of the added-vector code in the remaining dimensions. In
each case the maximum is the independence number of an explicit finite graph.
Dimension 18: the constraints imposed by the fixed vectors force the admissible indices to be
exactly the 8-dimensional code C8 that Cohn and Li use, so their code is not a choice but a
consequence; and since the two sign options for a given index are always incompatible, each index
supplies at most one point. The maximum is therefore 256, which they attain, so tau(18) >= 7654
cannot be improved by enlarging the added-vector code.
Dimensions 20 and 21: the relevant Cayley graph on the 4096 words of the (24-n)-punctured extended
Golay code is a disjoint union of 128 copies of the 5-cube when n = 20, and is bipartite when
n = 21. Both give independence number exactly 2048, the value Cohn and Li already achieve, so
tau(20) >= 19448 and tau(21) >= 29768 are likewise maximal for this construction.
Dimension 19: the graph is neither, which is precisely why Ho's improvement was possible there. We
prove 1280 <= max <= 1536, improving the ratio bound of 1566, and show this is the limit of the
standard relaxations: for a Cayley graph on an abelian group the semidefinite bound reduces to the
Delsarte linear program, and the graph's odd girth of 5 makes odd-cycle inequalities weaker still.
We conjecture the maximum is 1280, supported by iterated local search (1602 restarts), simulated
annealing (152 runs) and a search over 370000 subgroups, none of which ever exceeded it.
Together with Cohn and Li's Lemma 3.1 for dimension 17, this settles four of the five dimensions
and brackets the fifth. All the structure is traced to the Steiner system S(5,8,24) or to explicit
small codes, and every certificate is small enough to check by hand.
Scope. These results bound the Cohn-Li constructions, not the kissing numbers. They do not assert
that tau(18) = 7654, tau(20) = 19448 or tau(21) = 29768; all remain open, and improvements from
other constructions are not excluded. Cohn and Li's remark that optimality is "particularly
unlikely in 18 dimensions" concerns the whole configuration rather than the added-vector code
considered here, so the dimension-18 result is consistent with it. The ingredients are standard:
the Steiner system S(5,8,24) and its intersection numbers, the duality of shortening and
puncturing, the existence of a perfect matching in a regular bipartite graph, and the Delsarte
bound. The contribution is the reduction of each added-vector problem to an independence number,
the forcing of the admissible indices in dimension 18, the identification of the dimension-20
components as 5-cubes, the parity certificate in dimension 21, and the improved bound in
dimension 19. Verification code accompanies the note.
Cite it
Gonzalez, V. (2026). Maximality of the added-vector codes in the Cohn-Li kissing constructions. Zenodo. https://doi.org/10.5281/zenodo.21729367