Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Three-point bounds for energy minimization

Authors: Henry Cohn and Jeechul Woo
Journal: J. Amer. Math. Soc. 25 (2012), 929-958
MSC (2010): Primary 05B40, 52A40, 52C17; Secondary 90C22, 82B05
Published electronically: May 1, 2012
Supplement 1: data1.txt
Supplement 2: data2.txt
Supplement 3: data3.txt
Supplement 4: data4.txt
Supplement 5: data5.txt
Supplement 6: definitions.txt
Supplement 7: optimal.txt
Supplement 8: unique.txt
MathSciNet review: 2947943
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Three-point semidefinite programming bounds are one of the most powerful known tools for bounding the size of spherical codes. In this paper, we use them to prove lower bounds for the potential energy of particles interacting via a pair potential function. We show that our bounds are sharp for seven points in $ \mathbb{R}\mathbb{P}^2$. Specifically, we prove that the seven lines connecting opposite vertices of a cube and of its dual octahedron are universally optimal. (In other words, among all configurations of seven lines through the origin, this one minimizes energy for all potential functions that are completely monotonic functions of squared chordal distance.) This configuration is the only known universal optimum that is not distance regular, and the last remaining universal optimum in $ \mathbb{R}\mathbb{P}^2$. We also give a new derivation of semidefinite programming bounds and present several surprising conjectures about them.

References [Enhancements On Off] (What's this?)

  • [A99] N. N. Andreev, A spherical code, Russian Math. Surveys 54 (1999), no. 1, 251-253. MR 1706807
  • [AAR99] G. Andrews, R. Askey, and R. Roy, Special Functions, Encyclopedia Math. Appl. 71, Cambridge University Press, Cambridge, 1999. MR 1688958 (2000g:33001)
  • [B06] C. Bachoc, Linear programming bounds for codes in Grassmannian spaces, IEEE Trans.Inform. Theory 52 (2006), 2111-2125, arXiv:math.CO/0610812. MR 2234468 (2007h:94095)
  • [BV08] C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc. 21 (2008), 909-924, arXiv:math/0608426. MR 2393433 (2009c:52029)
  • [BV09a] C. Bachoc and F. Vallentin, Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps, Europ. J. Comb. 30 (2009), 625-637, arXiv:math/0610856. MR 2494437 (2010d:90065)
  • [BV09b] C. Bachoc and F. Vallentin, Optimality and uniqueness of the $ (4,10,1/6)$ spherical code, J. Comb. Theory Ser. A 116 (2009), 195-204, arXiv:0708.3947. MR 2469257 (2010f:94337)
  • [B+09] B. Ballinger, G. Blekherman, H. Cohn, N. Giansiracusa, E. Kelly, and A. Schürmann, Experimental study of energy-minimizing point configurations on spheres, Experiment. Math. 18 (2009), 257-283, arXiv:math.MG/0611451. MR 2555698 (2010j:52037)
  • [B41] S. Bochner, Hilbert distances and positive definite functions, Ann. of Math. (2) 42 (1941), 647-656. MR 0005782 (3:206d)
  • [B99] B. Borchers, CSDP, a C library for semidefinite programming, Optim. Methods Softw. 11 (1999), 613-623. MR 1778432
  • [B04] K. Böröczky, Jr., Finite packing and covering, Cambridge Tracts in Mathematics 154, Cambridge University Press, Cambridge, 2004. MR 2078625 (2005g:52045)
  • [BG09] M. Bowick and L. Giomi, Two-dimensional matter: order, curvature and defects, Advances in Physics 58 (2009), 449-563, arXiv:0812.3064.
  • [C10] H. Cohn, Order and disorder in energy minimization, Proceedings of the International Congress of Mathematicians, Hyderabad, August 19-27, 2010, Volume IV, pages 2416-2443, Hindustan Book Agency, New Delhi, 2010, arXiv:1003.3053. MR 2827978
  • [CCEK07] H. Cohn, J. H. Conway, N. D. Elkies, and A. Kumar, The $ D_4$ root system is not universally optimal, Experiment. Math. 16 (2007), 313-320, arXiv:math.MG/0607447. MR 2367321 (2008m:52041)
  • [CEKS10] H. Cohn, N. D. Elkies, A. Kumar, and A. Schürmann, Point configurations that are asymmetric yet balanced, Proc. Amer. Math. Soc. 138 (2010), 2863-2872, arXiv:0812.2579. MR 2644899 (2011d:52021)
  • [CK07] H. Cohn and A. Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc.20 (2007), 99-148, arXiv:math.MG/0607446. MR 2257398 (2007h:52009)
  • [CHS96] J. H. Conway, R. H. Hardin, and N. J. A. Sloane, Packing lines, planes, etc.: packings in Grassmannian spaces, Experiment. Math. 5 (1996), 139-159. MR 1418961 (98a:52029)
  • [CS99] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, third edition, Grundlehren Math. Wiss. 290, Springer-Verlag, New York, 1999. MR 1662447 (2000b:11077)
  • [D72] P. Delsarte, Bounds for unrestricted codes, by linear programming, Philips Res. Reports 27 (1972), 272-289. MR 0314545 (47:3096)
  • [GMS10] D. C. Gijswijt, H. D. Mittelmann, and A. Schrijver, Semidefinite code bounds based on quadruple distances, to appear in IEEE Trans.Inform. Theory, arXiv:1005.4959.
  • [HS96] R. H. Hardin and N. J. A. Sloane, McLaren's improved snub cube and other new spherical designs in three dimensions, Discrete Comput. Geom. 15 (1996), 429-441. MR 1384885 (97b:52013)
  • [L85] S. Lang, $ {\mathop {\textup {SL}}}_2(\mathbb{R})$, Graduate Texts in Mathematics 105, Springer-Verlag, New York, 1985. MR 803508 (86j:22018)
  • [L57] J. Leech, Equilibrium of sets of particles on a sphere, Math. Gaz. 41 (1957), 81-90. MR 0086325 (19:165b)
  • [L82] V. I. Levenshtein, Bounds for the maximal cardinality of a code with bounded modulus of the inner product (Russian), Dokl. Akad. Nauk SSSR 263 (1982), 1303-1308; translation in Soviet Math. Doklady 25 (1982), 526-531. MR 653223 (83j:94025)
  • [L92] V. I. Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math. 29 (1992), 1-82. MR 1192833 (93j:05012)
  • [M08] M. Marshall, Positive polynomials and sums of squares, Math. Surveys Monogr. 146, American Mathematical Society, Providence, RI, 2008. MR 2383959 (2009a:13044)
  • [M07] O. Musin, Multivariate positive definite functions on spheres, preprint, 2007, arXiv:math/0701083.
  • [N+08] M. Nakata, B. J. Braams, K. Fujisawa, M. Fukuda, J. K. Percus, M. Yamashita, and Z. Zhao, Variational calculation of second-order reduced density matrices by strong $ N$-representability conditions and an accurate semidefinite programming solver, J. Chem. Phys. 128 (2008), 164113:1-14.
  • [PARI] PARI/GP, version 2.3.4, Bordeaux, 2008,
  • [P44] A. L. Patterson, Ambiguities in the X-ray analysis of crystal structures, Phys. Rev. 65 (1944), 195-201.
  • [P07] F. Pfender, Improved Delsarte bounds for spherical codes in small dimensions, J. Combin. Theory Ser.A 114 (2007), 1133-1147, arXiv:math/0501493. MR 2337242 (2009g:94144)
  • [P93] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J.42 (1993), 969-984. MR 1254128 (95h:47014)
  • [R55] R. A. Rankin, The closest packing of spherical caps in $ n$ dimensions, Proc. Glasgow Math. Assoc. 2 (1955), 139-144. MR 0074013 (17:523c)
  • [S42] I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96-108. MR 0005922 (3:232c)
  • [S05] A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans.Inform. Theory 51 (2005), 2859-2866. MR 2236252 (2007a:94147)
  • [SW51] K. Schütte and B. L. van der Waerden, Auf welcher Kugel haben $ 5$, $ 6$, $ 7$, $ 8$ oder $ 9$ Punkte mit Mindestabstand Eins Platz?, Math.Ann. 123 (1951), 96-124. MR 0042150 (13:61e)
  • [W41] D. V. Widder, The Laplace Transform, Princeton Math. Ser. 6, Princeton University Press, Princeton, NJ, 1941. MR 0005923 (3:232d)
  • [Y92] V. A. Yudin, Minimum potential energy of a point system of charges (Russian), Diskret. Mat. 4 (1992), 115-121; translation in Discrete Math. Appl. 3 (1993), 75-81. MR 1181534 (93f:31008)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 05B40, 52A40, 52C17, 90C22, 82B05

Retrieve articles in all journals with MSC (2010): 05B40, 52A40, 52C17, 90C22, 82B05

Additional Information

Henry Cohn
Affiliation: Microsoft Research New England, One Memorial Drive, Cambridge, Massachuetts 02142

Jeechul Woo
Affiliation: Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138

Received by editor(s): March 2, 2011
Received by editor(s) in revised form: February 24, 2012
Published electronically: May 1, 2012
Additional Notes: The second author was supported in part by an internship at Microsoft Research New England and by a Samsung Scholarship.
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society