Bounds for spherical codes: The Levenshtein framework lifted
HTML articles powered by AMS MathViewer
- by P. G. Boyvalenkov, P. D. Dragnev, D. P. Hardin, E. B. Saff and M. M. Stoyanova;
- Math. Comp. 90 (2021), 1323-1356
- DOI: https://doi.org/10.1090/mcom/3621
- Published electronically: March 2, 2021
- HTML | PDF | Request permission
Abstract:
Based on the Delsarte-Yudin linear programming approach, we extend Levenshtein’s framework to obtain lower bounds for the minimum $h$-energy of spherical codes of prescribed dimension and cardinality, and upper bounds on the maximal cardinality of spherical codes of prescribed dimension and minimum separation. These bounds are universal in the sense that they hold for a large class of potentials $h$ and in the sense of Levenshtein. Moreover, codes attaining the bounds are universally optimal in the sense of Cohn-Kumar. Referring to Levenshtein bounds and the energy bounds of the authors as “first level”, our results can be considered as “next level” universal bounds as they have the same general nature and imply necessary and sufficient conditions for their local and global optimality. For this purpose, we introduce the notion of Universal Lower Bound space (ULB-space), a space that satisfies certain quadrature and interpolation properties. While there are numerous cases for which our method applies, we will emphasize the model examples of $24$ points ($24$-cell) and $120$ points ($600$-cell) on $\mathbb {S}^3$. In particular, we provide a new proof that the $600$-cell is universally optimal, and in so doing, we derive optimality of the $600$-cell on a class larger than the absolutely monotone potentials considered by Cohn-Kumar.References
- N. N. Andreev, A spherical code, Uspekhi Mat. Nauk 54 (1999), no. 1(325), 255–256 (Russian); English transl., Russian Math. Surveys 54 (1999), no. 1, 251–253. MR 1706807, DOI 10.1070/rm1999v054n01ABEH000123
- N. N. Andreev, A minimal design of order 11 on the three-dimensional sphere, Mat. Zametki 67 (2000), no. 4, 489–497 (Russian, with Russian summary); English transl., Math. Notes 67 (2000), no. 3-4, 417–424. MR 1769895, DOI 10.1007/BF02676396
- N. N. Andreev and V. A. Yudin, Polynomials of least deviation from zero, and Chebyshev-type cubature formulas, Tr. Mat. Inst. Steklova 232 (2001), no. Funkts. Prostran., Garmon. Anal., Differ. Uravn., 45–57 (Russian, with Russian summary); English transl., Proc. Steklov Inst. Math. 1(232) (2001), 39–51. MR 1851439
- V. V. Arestov and A. G. Babenko, Estimates for the maximal value of the angular code distance for 24 and 25 points on the unit sphere in $\Bbb R^4$, Mat. Zametki 68 (2000), no. 4, 483–503 (Russian, with Russian summary); English transl., Math. Notes 68 (2000), no. 3-4, 419–435. MR 1823136, DOI 10.1007/BF02676721
- Brandon Ballinger, Grigoriy Blekherman, Henry Cohn, Noah Giansiracusa, Elizabeth Kelly, and Achill Schürmann, Experimental study of energy-minimizing point configurations on spheres, Experiment. Math. 18 (2009), no. 3, 257–283. MR 2555698
- Sergiy V. Borodachov, Douglas P. Hardin, and Edward B. Saff, Discrete energy on rectifiable sets, Springer Monographs in Mathematics, Springer, New York, [2019] ©2019. MR 3970999, DOI 10.1007/978-0-387-84808-2
- K. Böröczky, Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sci. Hungar. 32 (1978), no. 3-4, 243–261. MR 512399, DOI 10.1007/BF01902361
- Károly Böröczky Jr., Finite packing and covering, Cambridge Tracts in Mathematics, vol. 154, Cambridge University Press, Cambridge, 2004. MR 2078625, DOI 10.1017/CBO9780511546587
- P. Boyvalenkov, Extremal polynomials for obtaining bounds for spherical codes and designs, Discrete Comput. Geom. 14 (1995), no. 2, 167–183. MR 1331925, DOI 10.1007/BF02570701
- Peter G. Boyvalenkov, Danyo P. Danev, and Silvya P. Bumova, Upper bounds on the minimum distance of spherical codes, IEEE Trans. Inform. Theory 42 (1996), no. 5, 1576–1581. MR 1426229, DOI 10.1109/18.532903
- Peter Boyvalenkov, Danyo Danev, and Peter Kazakov, Indexes of spherical codes, Codes and association schemes (Piscataway, NJ, 1999) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 56, Amer. Math. Soc., Providence, RI, 2001, pp. 47–57. MR 1816387, DOI 10.1090/dimacs/056/04
- P. G. Boyvalenkov, P. D. Dragnev, D. P. Hardin, E. B. Saff, and M. M. Stoyanova, Universal lower bounds for potential energy of spherical codes, Constr. Approx. 44 (2016), no. 3, 385–415. MR 3562402, DOI 10.1007/s00365-016-9327-5
- Henry Cohn, John H. Conway, Noam D. Elkies, and Abhinav Kumar, The $D_4$ root system is not universally optimal, Experiment. Math. 16 (2007), no. 3, 313–320. MR 2367321
- Henry Cohn and Abhinav Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (2007), no. 1, 99–148. MR 2257398, DOI 10.1090/S0894-0347-06-00546-7
- Henry Cohn and Jeechul Woo, Three-point bounds for energy minimization, J. Amer. Math. Soc. 25 (2012), no. 4, 929–958. MR 2947943, DOI 10.1090/S0894-0347-2012-00737-1
- H. S. M. Coxeter, Introduction to geometry, 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR 346644
- H. S. M. Coxeter, Regular polytopes, 3rd ed., Dover Publications, Inc., New York, 1973. MR 370327
- Philip J. Davis, Interpolation and approximation, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1963. MR 157156
- P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
- Philippe Delsarte and Vladimir I. Levenshtein, Association schemes and coding theory, IEEE Trans. Inform. Theory 44 (1998), no. 6, 2477–2504. Information theory: 1948–1998. MR 1658771, DOI 10.1109/18.720545
- George Gasper, Linearization of the product of Jacobi polynomials. II, Canadian J. Math. 22 (1970), 582–593. MR 264136, DOI 10.4153/CJM-1970-065-4
- Werner Haußmann, Differentiable Tchebycheff subspaces and Hermite interpolation, Ann. Acad. Sci. Fenn. Ser. A I Math. 4 (1979), no. 1, 75–83. MR 538090, DOI 10.5186/aasfm.1978-79.0408
- Yasuhiko Ikebe, Hermite-Birkhoff interpolation problems in Haar subspaces, J. Approximation Theory 8 (1973), 142–149. MR 342903, DOI 10.1016/0021-9045(73)90023-3
- G. A. Kabatjanskiĭ and V. I. Levenšteĭn, Bounds for packings on the sphere and in space, Problemy Peredači Informacii 14 (1978), no. 1, 3–25 (Russian). MR 514023
- V. I. Levenšteĭn, Boundaries for packings in $n$-dimensional Euclidean space, Dokl. Akad. Nauk SSSR 245 (1979), no. 6, 1299–1303 (Russian). MR 529659
- V. I. Levenshteĭn, Bounds for packings of metric spaces and some of their applications, Problemy Kibernet. 40 (1983), 43–110 (Russian). MR 717357
- V. I. Levenshteĭn, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math. 29 (1992), no. 1-2, 1–82. Interactions between algebra and combinatorics. MR 1192833, DOI 10.1007/BF00053379
- Vladimir I. Levenshtein, Universal bounds for codes and designs, Handbook of coding theory, Vol. I, II, North-Holland, Amsterdam, 1998, pp. 499–648. MR 1667942
- Hrushikesh N. Mhaskar and Devidas V. Pai, Fundamentals of approximation theory, CRC Press, Boca Raton, FL; Narosa Publishing House, New Delhi, 2000. MR 1887338
- Oleg R. Musin, The kissing number in four dimensions, Ann. of Math. (2) 168 (2008), no. 1, 1–32. MR 2415397, DOI 10.4007/annals.2008.168.1
- S. Nikova, V. Nikov, Extremal polynomials for codes in polynomial metric spaces, in Proceedings of IEEE International Symposium on Information Theory (ISIT2000), Sorrento, Italy, June 25-30, 2000, 60.
- A. M. Odlyzko and N. J. A. Sloane, New bounds on the number of unit spheres that can touch a unit sphere in $n$ dimensions, J. Combin. Theory Ser. A 26 (1979), no. 2, 210–214. MR 530296, DOI 10.1016/0097-3165(79)90074-8
- Barry Simon, Orthogonal polynomials on the unit circle. Part 1, American Mathematical Society Colloquium Publications, vol. 54, American Mathematical Society, Providence, RI, 2005. Classical theory. MR 2105088, DOI 10.1090/coll054.1
- Gabor Szegö, Orthogonal Polynomials, American Mathematical Society Colloquium Publications, Vol. 23, American Mathematical Society, New York, 1939. MR 77
- V. A. Yudin, Minimum potential energy of a point system of charges, Diskret. Mat. 4 (1992), no. 2, 115–121 (Russian, with Russian summary); English transl., Discrete Math. Appl. 3 (1993), no. 1, 75–81. MR 1181534, DOI 10.1515/dma.1993.3.1.75
Bibliographic Information
- P. G. Boyvalenkov
- Affiliation: Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 8 G Bonchev Str., 1113 Sofia, Bulgaria; and Technical Faculty, South-Western University, Blagoevgrad, Bulgaria
- MR Author ID: 331674
- Email: peter@math.bas.bg
- P. D. Dragnev
- Affiliation: Department of Mathematical Sciences, Purdue University, Fort Wayne, Indiana 46805
- MR Author ID: 623970
- Email: dragnevp@pfw.edu
- D. P. Hardin
- Affiliation: Department of Mathematics, Center for Constructive Approximation, Vanderbilt University, Nashville, Tennessee 37240
- MR Author ID: 81245
- ORCID: 0000-0003-0867-2146
- Email: doug.hardin@vanderbilt.edu
- E. B. Saff
- Affiliation: Department of Mathematics, Center for Constructive Approximation, Vanderbilt University, Nashville, Tennessee 37240
- MR Author ID: 152845
- Email: edward.b.saff@vanderbilt.edu
- M. M. Stoyanova
- Affiliation: Faculty of Mathematics and Informatics, Sofia University, 5 James Bourchier Blvd., 1164 Sofia, Bulgaria
- MR Author ID: 758227
- ORCID: 0000-0002-8813-3398
- Email: stoyanova@fmi.uni-sofia.bg
- Received by editor(s): August 19, 2019
- Received by editor(s) in revised form: September 15, 2020
- Published electronically: March 2, 2021
- Additional Notes: The research of the first and fifth authors was supported, in part, by a Bulgarian NSF contract DN02/2-2016. The research of the second author was supported, in part, by a Simons Foundation grant no. 282207. The research of the third and fourth authors was supported, in part, by the U. S. National Science Foundation under grant DMS-1516400.
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 1323-1356
- MSC (2020): Primary 94B65, 74G65, 52A40
- DOI: https://doi.org/10.1090/mcom/3621
- MathSciNet review: 4232226