Optimality of spherical codes via exact semidefinite programming bounds
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914727992492032 |
|---|---|
| author | Cohn, Henry de Laat, David Leijenhorst, Nando |
| author_facet | Cohn, Henry de Laat, David Leijenhorst, Nando |
| contents | We show that the spectral embeddings of all known triangle-free strongly regular graphs are optimal spherical codes (the new cases are $56$ points in $20$ dimensions, $50$ points in $21$ dimensions, and $77$ points in $21$ dimensions), as are certain mutually unbiased basis arrangements constructed using Kerdock codes in up to $1024$ dimensions (namely, $2^{4k} + 2^{2k+1}$ points in $2^{2k}$ dimensions for $2 \le k \le 5$). As a consequence of the latter, we obtain optimality of the Kerdock binary codes of block length $64$, $256$, and $1024$, as well as uniqueness for block length $64$. We also prove universal optimality for $288$ points on a sphere in $16$ dimensions. To prove these results, we use three-point semidefinite programming bounds, for which only a few sharp cases were known previously. To obtain rigorous results, we develop improved techniques for rounding approximate solutions of semidefinite programs to produce exact optimal solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16874 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimality of spherical codes via exact semidefinite programming bounds Cohn, Henry de Laat, David Leijenhorst, Nando Metric Geometry Information Theory Optimization and Control We show that the spectral embeddings of all known triangle-free strongly regular graphs are optimal spherical codes (the new cases are $56$ points in $20$ dimensions, $50$ points in $21$ dimensions, and $77$ points in $21$ dimensions), as are certain mutually unbiased basis arrangements constructed using Kerdock codes in up to $1024$ dimensions (namely, $2^{4k} + 2^{2k+1}$ points in $2^{2k}$ dimensions for $2 \le k \le 5$). As a consequence of the latter, we obtain optimality of the Kerdock binary codes of block length $64$, $256$, and $1024$, as well as uniqueness for block length $64$. We also prove universal optimality for $288$ points on a sphere in $16$ dimensions. To prove these results, we use three-point semidefinite programming bounds, for which only a few sharp cases were known previously. To obtain rigorous results, we develop improved techniques for rounding approximate solutions of semidefinite programs to produce exact optimal solutions. |
| title | Optimality of spherical codes via exact semidefinite programming bounds |
| topic | Metric Geometry Information Theory Optimization and Control |
| url | https://arxiv.org/abs/2403.16874 |