A new lower bound for the kissing number in 19 dimensions

This paper establishes a new lower bound of 11948 for the kissing number in 19 dimensions by combining Cohn and Li's odd-sign construction with an explicit nonlinear binary code of length 19 derived from nested codes within a punctured extended binary Golay code.

The Gist

Imagine you are trying to pack as many identical oranges as possible around a single, central orange in a room. In our normal 3D world, you can fit exactly 12 oranges touching the center one. This is the "kissing number."

Now, imagine doing this in a room with 19 dimensions. It's impossible to visualize, but mathematicians treat it like a giant, multi-layered puzzle. The question is: What is the maximum number of 19-dimensional "oranges" that can touch a central one without overlapping?

For a long time, the best answer anyone could give was 11,692. A new paper by Boon Suan Ho has just pushed that number up to 11,948.

Here is how the author did it, explained without the heavy math jargon.

The Problem: Finding the Perfect Arrangement

Think of the 19-dimensional space as a giant, empty warehouse. We have a central "orange" (the origin). We want to place as many other oranges as possible around it so they all touch the center but don't crash into each other.

To solve this, mathematicians use a trick called the "Odd-Sign Construction."

• Imagine the central orange is a lighthouse.
• The other oranges are like ships.
• To keep the ships from crashing, they need to be spaced out according to a very strict set of rules (mathematical codes).
• The more ships you can fit into this strict pattern, the higher your "kissing number" goes.

Previously, researchers (Cohn and Li) found a way to fit 10,668 ships using a standard, rigid pattern (a linear code). Then, they found a way to add a few more ships (1,024) by using a specific type of "backup plan" (a binary code) hidden inside a special mathematical structure called the Golay Code.

The Breakthrough: The "Nonlinear" Shortcut

The author of this paper realized that the "backup plan" used by the previous researchers was too rigid. It was like using a pre-fabricated Lego set where you can only snap pieces together in one specific way.

The author asked: "What if we stop using the pre-fabricated set and instead build a custom, irregular structure that still fits the rules?"

This is where the Nonlinear Code comes in. Instead of a rigid grid, the author built a flexible, custom arrangement of 1,280 points.

The Construction: A Nested Russian Doll

To build this new arrangement, the author used a "Russian Doll" strategy with three layers of codes:

1. The Inner Core (Code M): A small, tight group of 64 points. Think of this as the foundation of a building.
2. The Middle Layer (Code K): The author took the foundation and expanded it. They found a special group of 16 "neighborhoods" (cosets) that could sit on top of the foundation.
   • The Clebsch Graph: When the author looked at how these neighborhoods connected, they formed a famous shape in math called the Clebsch Graph. It's like a complex map of a city where certain streets connect specific districts.
   • The "Safe Zone": The author found a specific group of 5 districts in this map that are far enough apart from each other (an "independent set"). Because they are far apart, you can put a whole neighborhood of houses in each one without them crashing.
   • Since there are 5 districts and 64 houses in each, this created a middle layer of 320 points.
3. The Outer Shell (Code D): Finally, the author took that 320-point group and copied it 4 times, shifting each copy slightly (like sliding a deck of cards). This created the final, massive group of 1,280 points.

The Result: Packing More Oranges

By using this clever, custom-built 1,280-point structure, the author was able to add 1,280 new "oranges" to the kissing configuration.

• Old Count: 10,668 (base) + 1,024 (old code) = 11,692
• New Count: 10,668 (base) + 1,280 (new code) = 11,948

Why This Matters

In the world of high-dimensional geometry, finding a way to fit just a few more items is a massive victory. It's like finding a new way to fold a shirt that saves you an extra inch of space in a suitcase. Over time, these small improvements help us understand the fundamental limits of space, which has applications in everything from data compression (sending messages efficiently) to error correction (making sure your Wi-Fi doesn't drop when you're streaming a movie).

In short: The author found a smarter, more flexible way to arrange the "oranges" in 19-dimensional space, proving that we can fit at least 256 more than we thought possible before.

(Note: The paper also amusingly mentions that an AI, GPT-5.4 Pro, helped discover this construction, suggesting that even in the most abstract corners of math, artificial intelligence is becoming a powerful partner.)

Technical Summary

Here is a detailed technical summary of the paper "A New Lower Bound for the Kissing Number in 19 Dimensions" by Boon Suan Ho.

1. Problem Statement

The kissing number problem asks for the maximum number of non-overlapping unit spheres that can touch a central unit sphere in $n$-dimensional Euclidean space ($\mathbb{R}^n$). This number is denoted as $k(n)$.

• Specific Context: The paper focuses on dimension $n=19$.
• Previous State of the Art: Prior to this work, the best known lower bound was $k(19) \ge 11,692$, established by Cohn and Li. Their construction utilized a specific "odd-sign" method starting from a 10,668-point configuration and adding vectors derived from a linear binary code of size 1,024.
• Goal: To improve this lower bound by constructing a larger binary code with specific properties within the relevant geometric framework.

2. Methodology

The author employs a combinatorial construction based on binary linear codes and graph theory, specifically leveraging the structure of the 5-punctured extended binary Golay code.

A. The Framework

The construction relies on the "odd-sign" framework introduced by Cohn and Li. In dimension 19, the orthogonal complement of a shortened Steiner system $S(5, 8, 24)$ corresponds to a 5-punctured extended binary Golay code (denoted here as $D$).

• Any binary code $A \subseteq D$ with a minimum Hamming distance of at least 5 contributes exactly $|A|$ additional kissing vectors to the configuration.
• The objective is to find a code $A \subseteq D$ such that $|A| > 1024$ and $\text{min\_dist}(A) \ge 5$.

B. Code Construction Strategy

The paper constructs a nonlinear code $A$ of size 1,280 using a nested sequence of linear codes:
$$M \le K \le D$$
where:

• $M$: A linear code of dimension 6 ($|M| = 64$).
• $K$: A linear code of dimension 10 ($|K| = 1024$).
• $D$: The ambient 5-punctured Golay code of dimension 12 ($|D| = 4096$).

Step-by-Step Construction:

1. Generator Selection: The author defines explicit generators for $M$, $K$, and $D$ using specific binary vectors of length 19.
   • $M$ is generated by 6 vectors ($m_1, \dots, m_6$).
   • $K$ is generated by $M$ plus 4 additional vectors ($s_1, \dots, s_4$).
   • $D$ is generated by $K$ plus 2 additional vectors ($r_1, r_2$).
2. Graph Theoretic Analysis:
   • A graph $\Gamma$ is defined on the vertices of $D$, where two vertices are adjacent if their Hamming distance is 3 or 4.
   • An independent set in $\Gamma$ corresponds to a code with minimum distance $\ge 5$.
   • The set $S$ of vectors in $D$ with weight 3 or 4 is identified. There are exactly 21 such vectors.
3. Quotient Graph (The Clebsch Graph):
   • The set $S$ is partitioned into cosets of $M$ within $K$.
   • The quotient graph $\Gamma|_K / M$ is shown to be isomorphic to the Clebsch graph (a strongly regular graph on 16 vertices).
   • The set $T$ representing the cosets containing $S$ forms a 5-coclique (an independent set of size 5) in the Clebsch graph.
4. Lifting to the Code:
   • The preimage of this 5-coclique in $K$ forms a code $B$ of size $5 \times |M| = 320$. This code$B$has minimum distance$\ge 5$.
   • The full code $A$ is constructed by taking the union of $B$ and its three cosets in $D$ (generated by $r_1$ and $r_2$).
   • Since distinct cosets of $K$ in $D$ are never adjacent in $\Gamma$ (differences between cosets are not in $S$), the union $A = B \cup (B+r_1) \cup (B+r_2) \cup (B+r_1+r_2)$ remains an independent set in $\Gamma$.

3. Key Contributions

• Explicit Nonlinear Code: The paper provides an explicit construction of a nonlinear binary code $A \subset \mathbb{F}_2^{19}$ with size 1,280 and minimum distance 5. This improves upon the previous best linear code of size 1,024 used by Cohn and Li.
• Structural Insight: The work demonstrates how the Clebsch graph can be utilized to lift independent sets from a quotient space ($K/M$) back to the code space ($K$), effectively maximizing the code size within the constraints of the Golay code structure.
• Computational Verification: The author provides a rigorous computational verification (enumerating 4,096 codewords) to confirm the weight distribution and independence properties, with data and scripts made available publicly.

4. Results

• New Lower Bound: By applying the new code $A$ (size 1,280) to the Cohn-Li odd-sign construction, the kissing number in 19 dimensions is improved to:
  $$k(19) \ge 10,668 + 1,280 = \mathbf{11,948}$$
• Improvement Magnitude: This represents an increase of 256 over the previous bound of 11,692.
• Theorem: The paper formally proves Theorem 1: $k(19) \ge 11,948$.

5. Significance

• Advancement in Discrete Geometry: This result pushes the known limits of sphere packing in high dimensions, a field with deep connections to coding theory, lattice theory, and optimization.
• Methodological Innovation: The use of the Clebsch graph and the specific lifting technique from quotient codes offers a new template for constructing large codes in high-dimensional spaces, potentially applicable to other dimensions or packing problems.
• AI-Assisted Discovery: Notably, the "Acknowledgements" section reveals that GPT-5.4 Pro was used to discover the construction and assist with exposition. This highlights a growing trend where AI tools are not just for verification but are actively participating in the creative discovery of complex mathematical structures.
• Reproducibility: The paper emphasizes the elementary nature of the proofs (finite checks) and provides open-source resources, ensuring the result is verifiable and reproducible by the mathematical community.