🔢 mathematics

A dual linear programming bound for sphere packing in dimension 36

This paper constructs an explicit dual-feasible point for the Cohn-Elkies linear program in dimension 36, proving that the theoretical upper bound for sphere packing density exceeds the best known packing (Kschischang-Pasupathy) by a factor of at least 32.91, thereby demonstrating that the current best-known packing is not optimal and extending dual bounds to dimensions above 32 for the first time.

Original authors: Rifat Jumagulov

Published 2026-07-14

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Rifat Jumagulov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to pack as many identical, invisible balloons as possible into a giant, 36-dimensional room without any of them overlapping. This is the "sphere packing" problem. For decades, mathematicians have been trying to find the absolute densest way to do this, but in most dimensions, they only have a "best guess" (the current record) and a "theoretical ceiling" (the absolute limit allowed by math).

In dimensions 8 and 24, we know the ceiling and the floor touch; the best guess is proven to be perfect. But in dimension 36, a gap has always existed. The paper by Rifat Jumagulov acts like a super-precise ruler that measures this gap and proves something surprising: the current best guess is nowhere near the theoretical limit.

The "Magic Mirror" Test

To find the theoretical limit, mathematicians use a tool called the Cohn–Elkies linear program. Think of this program as a "magic mirror" that reflects a proposed packing arrangement. If the arrangement is truly the best possible, the mirror should show a perfect reflection. If the mirror shows a flaw, the arrangement isn't the best.

For a long time, the best-known packing in 36 dimensions (called the Kschischang–Pasupathy packing) was thought to be a strong contender. The paper constructs a specific "dual" object—a complex mathematical shape built from modular forms (which are like intricate, repeating patterns in the complex number world)—to act as this mirror.

The Big Reveal

When the author shines this new mirror on the Kschischang–Pasupathy packing, the reflection is not just a little off; it's wildly different. The math proves that the theoretical limit for 36 dimensions is at least 32.91 times denser than the current best-known packing.

To put that in perspective: if the current best packing were a sparse scattering of marbles on a floor, the theoretical limit suggests you could fit over 32 times that many marbles in the same space without them touching. The paper explicitly rules out the idea that the Cohn–Elkies method could ever prove the current record is optimal. The gap is simply too wide.

How They Did It: The "Cut-and-Run" Strategy

Building this mirror wasn't easy. The author had to solve a massive puzzle involving 72 different mathematical ingredients.

The Trap: When they tried to solve the puzzle using standard computer math (floating-point numbers), the computer got confused and gave a "ghost" answer that looked good but was actually broken.
The Fix: The author used "exact rational arithmetic," which is like doing math with perfect fractions instead of messy decimals. They used a "cutting-plane" method: they solved a small version of the puzzle, found where the answer broke the rules, cut out that bad part, and solved it again. It took just one round of cutting to find the perfect, exact solution.

The "Tail" Problem

The hardest part was proving that the mathematical shape stays positive (doesn't turn negative) all the way out to infinity. The shape is made of two parts: a predictable "main body" and a wiggly "tail."

The main body is huge and positive.
The tail is tiny and wiggly.
The author had to prove the main body is so strong that it always swamps the wiggly tail.

Usually, mathematicians use a standard safety margin to prove this. But in dimension 36, the standard margin was too loose; it would have failed by a hair's breadth. The author invented a "lift-aware" safety margin—a smarter way to measure the wiggly tail that accounts for how the mathematical pieces are stacked. This new margin was 10 billion times more precise than the old one, allowing the proof to close the gap with a massive safety buffer.

What This Means (and What It Doesn't)

The paper is a rigorous proof, not a simulation or a guess. Every number was checked with exact arithmetic, and the code is available for anyone to verify.

However, the paper also clarifies what it hasn't done. It does not find the new, denser packing that fits in that 32.91 times gap. It only proves that the current record is far from the limit. Finding the actual denser packing remains a mystery. The author notes that while the gap is huge, proving that the theoretical limit is strictly higher than the true optimal density (strict non-sharpness) is currently impossible because we lack the tools to calculate an upper bound that low.

In short: The paper pulls back the curtain to show that the "best known" packing in 36 dimensions is a long way from the finish line, and no amount of tweaking the current method can prove it's the winner. The race is wide open, and the finish line is much further away than anyone thought.

Technical Summary: A Dual Linear Programming Bound for Sphere Packing in Dimension 36

Problem Statement
The paper addresses the sphere packing problem in dimension $d=36$ , specifically focusing on the Cohn–Elkies linear programming (LP) bound. While the LP bound is known to be sharp in dimensions 8 and 24, its sharpness remains an open question in all other dimensions. The author investigates whether the Cohn–Elkies bound, denoted $\delta_{LP}(d)$ , can certify the optimality of the best currently known packing, $\delta^*(d)$ . In dimension 36, the best known packing is the Kschischang–Pasupathy configuration with a center density of $2^{18}/3^{10}$ . The goal is to construct a "dual-feasible point" (a specific auxiliary function) that yields a lower bound for $\delta_{LP}(36)$ strictly greater than the density of the Kschischang–Pasupathy packing. If successful, this proves that no Cohn–Elkies function can certify the known packing as optimal.

Methodology
The construction follows the method of Cohn and Triantafillou, utilizing the space of weight-18 modular forms for the congruence subgroup $\Gamma_0(24)$ . The core of the method involves finding a pair of modular forms $(g, \tilde{g})$ of weight $k=18$ (where $k=d/2$ ) that satisfy specific coefficient constraints to generate a valid distribution for the LP bound.

The paper details two critical methodological innovations required to solve this problem in dimension 36, where previous methods (successful in dimensions up to 32) faced numerical and theoretical obstacles:

Constraint Generation (Cutting-Plane Formulation):
A naive linear programming relaxation, enforcing non-negativity of coefficients only up to a finite $n$ , produced an optimum that became negative immediately after the enforced range (specifically for $n \equiv 3, 9, 15, 21 \pmod{24}$ ). Conversely, a fully constrained problem with hundreds of rows was numerically singular for floating-point solvers and too large for exact dense simplex methods.
- Solution: The author employs a constraint-generation approach. An exact rational LP is solved on a small working set. Violated rows (where coefficients are negative) are identified exactly, added to the constraint set, and the LP is re-solved. In dimension 36, this process converged in a single round, yielding an exact rational vertex whose $q$ -expansions remained non-negative far beyond the enforced range.
Lift-Aware Deligne Constant:
Proving "eventual positivity" (that coefficients remain non-negative for all $n > n_0$ ) requires bounding the cuspidal part of the modular forms. The standard Deligne bound uses an $\ell_1$ -norm of the coordinates in the newform-lift basis.
- Solution: The author identifies that the naive $\ell_1$ -norm is "lossy" in this context because the certificate is dominated by a single deep oldform lift (the level-one newform shifted by $e=24$ ). The naive constant failed the verification threshold marginally. The author introduces a "lift-aware" constant, $C_w = \sum_{f,e} |\lambda_{f,e}| e^{-(k-1)/2}$ , which suppresses the contribution of deep lifts by the factor $e^{-(k-1)/2}$ . This refined constant is smaller by ten orders of magnitude, allowing the verification to close with a significant margin.

Key Results
The paper constructs an explicit dual-feasible point $(g, \tilde{g})$ and derives the following results:

Dual Bound: The constructed certificate establishes that the Cohn–Elkies linear programming bound in dimension 36 satisfies:
$\delta_{LP}(36) \geq 146.1036\dots = 32.9104\dots \times \frac{2^{18}}{3^{10}}$
Comparison to Known Packing: This lower bound exceeds the density of the Kschischang–Pasupathy packing ( $2^{18}/3^{10}$ ) by a factor of at least 32.91.
Implication: Consequently, no Cohn–Elkies auxiliary function can certify the Kschischang–Pasupathy packing as optimal in dimension 36. The LP bound is strictly higher than the best known packing density.
Verification Rigor: The certificate is exact. The dual point is a rational vector with $\approx 128$ -digit numerators. Coefficient non-negativity is verified by exact arithmetic up to $n=800$ . For $n > 800$ , eventual positivity is proved using the lift-aware Deligne constant and explicit tail bounds, with all constants certified via outward-rounded interval arithmetic.

Significance and Claims
The paper claims several significant contributions to the field of sphere packing and modular forms:

Extension of Known Bounds: This is the first dual bound constructed in any dimension above 32. It extends the existing table of Cohn–Triantafillou (which covered $d=12, 16, 20, 28, 32$ ), Li ( $3 \le d \le 13$ ), and de Courcy-Ireland et al. ( $d=6$ ).
Methodological Advancement: The paper highlights that the constraint-generation formulation is essential for reaching the tail-safe optimum in high dimensions where exact dense LP is intractable. Furthermore, it demonstrates that the lift-aware Deligne constant is necessary for rigorous verification in cases dominated by deep oldform lifts, a scenario where standard bounds fail.
Nature of the Result: The author notes that while the dual statement is strong (the gap is large), the "strict non-sharpness" (proving $\delta_{LP}(36) > \delta_{max}(36)$ where $\delta_{max}$ is the true optimal density) remains out of reach. Strict non-sharpness would require an independent upper bound below $32.91 \times \delta^*$ , a threshold currently unattainable by existing three-point bound techniques.
Reproducibility: The work emphasizes that the verification relies solely on exact rational linear algebra and interval arithmetic, independent of computer algebra systems with modular form machinery. All code, receipts, and exact data are provided as ancillary files.

The paper concludes that dimension 36 represents a qualitatively different regime where the known record packing is weak relative to the LP bound, making the dual statement strong but the strict optimality question harder to resolve.