Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Upper bounds for energies of spherical codes of given cardinality and separation

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

We introduce a linear programming framework for obtaining upper bounds for the potential energy of spherical codes of fixed cardinality and minimum distance. Using Hermite interpolation we construct polynomials to derive corresponding bounds. These bounds are universal in the sense that they are valid for all absolutely monotone potential functions and the required interpolation nodes do not depend on the potentials.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Similar results for codes in Hamming spaces are obtained in [10, 12, 14].

References

  1. Bachoc C., Vallentin F.: New upper bounds for kissing numbers from semidefinite programming. J. Am. Math. Soc. 21, 909–924 (2008).

    Article  MathSciNet  Google Scholar 

  2. Bannai E., Okuda T., Tagami M.: Spherical designs of harmonic index \(t\). J. Approx. Theory 195, 1–18 (2015).

    Article  MathSciNet  Google Scholar 

  3. Ballinger B., Blekherman G., Cohn H., Giansiracusa N., Kelly E., Shűrmann A.: Experimental study of energy-minimizing point configurations on spheres. Exp. Math. 18, 257–283 (2009).

    Article  MathSciNet  Google Scholar 

  4. Bétermin L., Sandier E.: Renormalized energy and asymptotic expansion of optimal logarithmic energy on the sphere. Constr. Approx. 47, 39–74 (2018).

    Article  MathSciNet  Google Scholar 

  5. Bondarenko A., Radchenko D., Viazovska M.: Well-separated spherical designs. Constr. Approx. 41, 93–112 (2015).

    Article  MathSciNet  Google Scholar 

  6. Borodachov S.V., Hardin D.P., Saff E.B.: Discrete Energy on Rectifiable Sets. Springer, New York (2019).

    Book  Google Scholar 

  7. Boyvalenkov P., Dodunekov S., Musin O.: A survey on the kissing numbers. Serdica Math. J. 38, 507–522 (2012).

    MathSciNet  MATH  Google Scholar 

  8. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: Universal upper and lower bounds on energy of spherical designs. Dolomites Res. Notes Approx. 8, 51–65 (2015).

    MathSciNet  MATH  Google Scholar 

  9. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: Universal lower bounds for potential energy of spherical codes. Constr. Approx. 44, 385–415 (2016).

    Article  MathSciNet  Google Scholar 

  10. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: Energy bounds for codes and designs in Hamming spaces. Des. Codes Cryptogr. 82(1), 411–43 (2017).

    Article  MathSciNet  Google Scholar 

  11. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: On spherical codes with inner products in prescribed interval. Des. Codes Cryptogr. 87, 299–315 (2019).

    Article  MathSciNet  Google Scholar 

  12. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: Energy bounds for codes in polynomial metric spaces. Anal. Math. Phys. 9(2), 781–808 (2019).

    Article  MathSciNet  Google Scholar 

  13. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: Next levels universal bounds for spherical codes: the Levenshtein framework lifted, submitted. arXiv:1906.03062.

  14. Boyvalenkov P., Dragnev P., Hardin D., Saff E., Stoyanova M.: Universal bounds for size and energy of codes of given minimum and maximum distances, submitted. arXiv:1910.07274.

  15. Cohn H., Kumar A.: Universally optimal distribution of points on spheres. J. Am. Math. Soc. 20, 99–148 (2006).

    Article  MathSciNet  Google Scholar 

  16. Conte S.D., de Boor C.: Elementary Numerical Analysis: An Algorithmic Approach. SIAM, Philadelphia (2017).

    Book  Google Scholar 

  17. Delsarte P., Goethals J.-M., Seidel J.J.: Spherical codes and designs. Geom. Dedicata 6, 363–388 (1977).

    Article  MathSciNet  Google Scholar 

  18. Ericson Th, Zinoviev V.: Codes on Euclidean Spheres. North-Holland Mathematical LibraryElsevier, Amsterdam (2001).

    MATH  Google Scholar 

  19. Grabner P., Stepanyuk T.: Comparison of probabilistic and deterministic point sets. J. Approx. Theory 239, 128–143 (2019).

    Article  MathSciNet  Google Scholar 

  20. Hesse K.: The \(s\)-energy of spherical designs on \(\mathbb{S}^2\). Adv. Comput. Math. 30, 37–59 (2009).

    Article  MathSciNet  Google Scholar 

  21. Hesse K., Leopardi P.: The Coulomb energy of spherical designs on \(\mathbb{S}^2\). Adv. Comput. Math. 28, 331–354 (2008).

    Article  MathSciNet  Google Scholar 

  22. Koorwinder T.H.: The addition formula for Jacobi polynomials and spherical harmonics. SIAM J. Appl. Math. 25, 236–246 (1973).

    Article  MathSciNet  Google Scholar 

  23. Leopardi P.: Discrepancy, separation and Riesz energy of finite point sets on the unit sphere. Adv. Comput. Math. 39, 27–43 (2013).

    Article  MathSciNet  Google Scholar 

  24. Levenshtein V.I.: On bounds for packings in \(n\)-dimensional Euclidean space. Sov. Math. Dokl. 20, 417–421 (1979).

    MATH  Google Scholar 

  25. Levenshtein V.I.: Designs as maximum codes in polynomial metric spaces. Acta Appl. Math. 25, 1–82 (1992).

    Article  MathSciNet  Google Scholar 

  26. Levenshtein V.I.: Universal bounds for codes and designs, Ch. 6. In: Pless V.S., Huffman W.C. (eds.) Handbook of Coding Theory, pp. 499–648. Elsevier, Amsterdam (1998).

    Google Scholar 

  27. Machado F.C., de Oliveira Filho F.M.: Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry. Exp. Math. 27, 362–369 (2018).

    Article  MathSciNet  Google Scholar 

  28. Mittelmann H.D., Vallentin F.: High-accuracy semidefinite programming bounds for kissing numbers. Exp. Math. 19, 175–179 (2010).

    Article  MathSciNet  Google Scholar 

  29. Musin O.: The kissing number in four dimensions. Ann. Math. 168, 1–32 (2008).

    Article  MathSciNet  Google Scholar 

  30. Odlyzko A.M., Sloane N.J.A.: New bounds on the number of unit spheres that can touch a unit sphere in \(n\) dimensions. J. Comb. Theory Ser. A 26, 210–214 (1979).

    Article  MathSciNet  Google Scholar 

  31. Schoenberg I.J.: Positive definite functions on spheres. Duke Math. J. 9, 96–108 (1942).

    Article  MathSciNet  Google Scholar 

  32. Schütte K., van der Waerden B.L.: Auf welcher Kugel haben 5, 6, 7, oder 8 Punkte mit Mindestabstand Eins Platz? Math. Ann. 123, 96–124 (1951).

    Article  MathSciNet  Google Scholar 

  33. Schütte K., van der Waerden B.L.: Das Problem der dreizehn Kugeln. Math. Ann. 125, 325–334 (1952).

    Article  MathSciNet  Google Scholar 

  34. Stepanyuk T.: Estimates for logarithmic and Riesz energies for spherical \(t\)-designs. arXiv:1901.00437.

  35. Szegő G.: Orthogonal Polynomials, vol. 23. American Mathematical Society Colloquium Publications, Providence (1939).

    MATH  Google Scholar 

  36. Wagner G.: On means of distances on the surface of a sphere (upper bounds). Pac. J. Math. 154, 381–396 (1992).

    Article  MathSciNet  Google Scholar 

  37. Yudin V.A.: Minimum potential energy of a point system of charges. Diskret. Mat. 4(2), 115–121 (1992).

    MATH  Google Scholar 

  38. Zinoviev D., Zinoviev V.: On the spherical code \((4,\rho ,9)\). In: Proceedings of the Eighth International Workshop on Optimal Codes and Related Topics, pp. 142–148, Sofia, Bulgaria, 10–14 July (2017).

Download references

Acknowledgements

The authors thank the anonymous referees for helpful suggestions and comments.

Author information

Authors and Affiliations

  1. Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 8 G Bonchev Str., 1113, Sofia, Bulgaria

    P. G. Boyvalenkov

  2. Technical Faculty, South-Western University, Blagoevgrad, Bulgaria

    P. G. Boyvalenkov

  3. Department of Mathematical Sciences, Purdue University Fort Wayne, Fort Wayne, IN, 46805, USA

    P. D. Dragnev

  4. Department of Mathematics, Center for Constructive Approximation, Vanderbilt University, Nashville, TN, 37240, USA

    D. P. Hardin & E. B. Saff

  5. Faculty of Mathematics and Informatics, Sofia University, 5 James Bourchier Blvd., 1164, Sofia, Bulgaria

    M. M. Stoyanova

Authors
  1. P. G. Boyvalenkov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. D. Dragnev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D. P. Hardin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. E. B. Saff
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. M. M. Stoyanova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. G. Boyvalenkov.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The research of P. G. Boyvalenkov was partially supported by the National Scientific Program “Information and Communication Technologies for a Single Digital Market in Science, Education and Security (ICTinSES)”, financed by the Bulgarian Ministry of Education and Science. The research of P. D. Dragnev was supported, in part, by a Simons Foundation Grant No. 282207. The research of D. P. Hardin and E. B. Saff was supported, in part, by the U. S. National Science Foundation under Grant DMS-1516400. The research of M. M. Stoyanova was supported by a Bulgarian NSF contract DN2/02-2016. Research for this article was started while the authors were in residence at the Institute for Computational and Experimental Research in Mathematics in Providence, RI, during the “Point Configurations in Geometry, Physics and Computer Science” program supported by the National Science Foundation under Grant No. DMS-1439786.

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Boyvalenkov, P.G., Dragnev, P.D., Hardin, D.P. et al. Upper bounds for energies of spherical codes of given cardinality and separation. Des. Codes Cryptogr. 88, 1811–1826 (2020). https://doi.org/10.1007/s10623-020-00733-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-020-00733-y

Keywords

Mathematics Subject Classification

Search

Navigation