Asymptotic bounds for spherical codes
- Authors: Manin Y.I.1, Marcolli M.2
-
Affiliations:
- Max Planck Institute for Mathematics
- California Institute of Technology, Department of Mathematics
- Issue: Vol 83, No 3 (2019)
- Pages: 133-157
- Section: Articles
- URL: https://bakhtiniada.ru/1607-0046/article/view/133785
- DOI: https://doi.org/10.4213/im8739
- ID: 133785
Cite item
Open Access
Access granted
Subscription Access
Abstract
The set of all error-correcting codes $C$ over a fixed finite alphabet$\mathbf{F}$ of cardinality $q$ determines the set of code points in the unit square $[0,1]^2$ with coordinates $(R(C), \delta (C))$:= (relative transmission rate, relative minimal distance). The central problemof the theory of such codes consists in maximising simultaneously the transmission rate of the code and the relative minimum Hamming distance between two different code words. The classical approach to this problem explored in vast literature consists in inventing explicit constructions of “good codes” and comparing new classes of codes with earlier ones.A less classical approach studies the geometry of the whole set of code points $(R,\delta)$ (with $q$ fixed), at first independently of its computability properties, and only afterwards turningto problems of computability, analogies with statistical physics, and so on.The main purpose of this article consists in extending this latter strategy to the domain of spherical codes.
About the authors
Yuri Ivanovich Manin
Max Planck Institute for MathematicsDoctor of physico-mathematical sciences
Matilde Marcolli
California Institute of Technology, Department of Mathematics
Email: matilde@caltech.edu
References
- С. Г. Влэдуц, Д. Ю. Ногин, М. А. Цфасман, Алгеброгеометрические коды. Основные понятия, МЦНМО, М., 2003, 504 с.
- Yu. I. Manin, M. Marcolli, “Error-correcting codes and phase transitions”, Math. Comput. Sci., 5:2 (2011), 133–170
- Yu. I. Manin, “A computability challenge: asymptotic bounds for error-correcting codes”, Computation, physics and beyond, Lecture Notes in Comput. Sci., 7160, Springer, Heidelberg, 2012, 174–182
- Г. А. Кабатянский, В. И. Левенштейн, “О границах для упаковок на сфере и в пространстве”, Пробл. передачи информ., 14:1 (1978), 3–25
- Дж. Конвей, Н. Слоэн, Упаковки шаров, решетки и группы, т. 1, 2, Мир, М., 1990, 792 с.
- H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, M. Viazovska, “The sphere packing problem in dimension 24”, Ann. of Math. (2), 185:3 (2017), 1017–1033
- M. S. Viazovska, “The sphere packing problem in dimension $8$”, Ann. of Math. (2), 185:3 (2017), 991–1015
- H. Cohn, N. Elkies, “New upper bounds on sphere packings. I”, Ann. of Math. (2), 157:2 (2003), 689–714
- Yu. I. Manin, M. Marcolli, “Kolmogorov complexity and the asymptotic bound for error-correcting codes”, J. Differential Geom., 97:1 (2014), 91–108
- R. A. Rankin, “The closest packing of spherical caps in $n$ dimensions”, Proc. Glasgow Math. Assoc., 2:3 (1955), 139–144
- Yu. I. Manin, “What is the maximum number of points on a curve over $mathbf{F}_2$?”, J. Fac. Sci. Univ. Tokyo Sect. IA Math., 28:3 (1981), 715–720
- H. Cohn, Yang Jiao, A. Kumar, S. Torquato, “Rigidity of spherical codes”, Geom. Topol., 15:4 (2011), 2235–2273
- H. Cohn, Yufei Zhao, “Sphere packing bounds via spherical codes”, Duke Math. J., 163:10 (2014), 1965–2002
- J. Hamkins, K. Zeger, “Asymptotically dense spherical codes. I. Wrapped spherical codes”, IEEE Trans. Inform. Theory, 43:6 (1997), 1774–1785
Supplementary files
