Bounds for spherical codes: The Levenshtein framework lifted

Authors:
P. G. Boyvalenkov, P. D. Dragnev, D. P. Hardin, E. B. Saff and M. M. Stoyanova

Journal:
Math. Comp. **90** (2021), 1323-1356

MSC (2020):
Primary 94B65, 74G65, 52A40

DOI:
https://doi.org/10.1090/mcom/3621

Published electronically:
March 2, 2021

MathSciNet review:
4232226

Full-text PDF

View in AMS MathViewer

Abstract | References | Similar Articles | Additional Information

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.

- 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**0346644** - H. S. M. Coxeter,
*Regular polytopes*, 3rd ed., Dover Publications, Inc., New York, 1973. MR**0370327** - Philip J. Davis,
*Interpolation and approximation*, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1963. MR**0157156** - 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**0514023** - 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**0000077** - 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

Retrieve articles in *Mathematics of Computation*
with MSC (2020):
94B65,
74G65,
52A40

Retrieve articles in all journals with MSC (2020): 94B65, 74G65, 52A40

Additional 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

Keywords:
Levenshtein framework,
minimal energy problems,
linear programming,
bounds for codes

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.

Article copyright:
© Copyright 2021
American Mathematical Society