Computability questions in the sphere packing problem
Preprint
Abstract
We consider the sets of dimensions for which there is an optimal sphere packing with special regularity properties (respectively, a lattice, or a periodic set with a given bound on the number of translations, or an arbitrary periodic set). We show that all these sets are oracle-computable, given an oracle that orders an associated set of spherical codes by increasing Kolmogorov complexity.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Computable analysis with applications to dynamic systemsMathematical Structures in Computer Science, 2020
- Locally Optimal 2-Periodic Sphere PackingsDiscrete & Computational Geometry, 2019
- Sphere packing bounds via spherical codesDuke Mathematical Journal, 2014
- Plottable Real Number Functions and the Computable Graph TheoremSIAM Journal on Computing, 2008
- Computability on subsets of metric spacesTheoretical Computer Science, 2003
- Computability on subsets of Euclidean space I: closed and compact subsetsTheoretical Computer Science, 1999
- Asymptotically dense spherical codes. I. Wrapped spherical codesIEEE Transactions on Information Theory, 1997
- Tables of sphere packings and spherical codesIEEE Transactions on Information Theory, 1981
- The rigidity of certain cabled frameworks and the second-order rigidity of arbitrarily triangulated convex surfacesAdvances in Mathematics, 1980
- The Closest Packing of Spherical Caps in n DimensionsProceedings of the Glasgow Mathematical Association, 1955