Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909706992222208 |
|---|---|
| author | Li, Rupert |
| author_facet | Li, Rupert |
| contents | The Cohn-Elkies linear program for sphere packing, which was used to solve the 8 and 24 dimensional cases, is conjectured to not be sharp in any other dimension $d>2$. By mapping feasible points of this infinite-dimensional linear program into a finite-dimensional problem via discrete reduction, we provide a general method to obtain dual bounds on the Cohn-Elkies linear program. This reduces the number of variables to be finite, enabling computer optimization techniques to be applied. Using this method, we prove that the Cohn-Elkies bound cannot come close to the best packing densities known in dimensions $3 \leq d \leq 13$ except for the solved case $d=8$. In particular, our dual bounds show the Cohn-Elkies bound is unable to solve the 3, 4, and 5 dimensional sphere packing problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_09876 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions Li, Rupert Metric Geometry Information Theory Combinatorics 52C17 (Primary), 05B40, 90C05 (Secondary) The Cohn-Elkies linear program for sphere packing, which was used to solve the 8 and 24 dimensional cases, is conjectured to not be sharp in any other dimension $d>2$. By mapping feasible points of this infinite-dimensional linear program into a finite-dimensional problem via discrete reduction, we provide a general method to obtain dual bounds on the Cohn-Elkies linear program. This reduces the number of variables to be finite, enabling computer optimization techniques to be applied. Using this method, we prove that the Cohn-Elkies bound cannot come close to the best packing densities known in dimensions $3 \leq d \leq 13$ except for the solved case $d=8$. In particular, our dual bounds show the Cohn-Elkies bound is unable to solve the 3, 4, and 5 dimensional sphere packing problems. |
| title | Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions |
| topic | Metric Geometry Information Theory Combinatorics 52C17 (Primary), 05B40, 90C05 (Secondary) |
| url | https://arxiv.org/abs/2206.09876 |