Three-point bounds for energy minimization
HTML articles powered by AMS MathViewer
- by Henry Cohn and Jeechul Woo
- J. Amer. Math. Soc. 25 (2012), 929-958
- DOI: https://doi.org/10.1090/S0894-0347-2012-00737-1
- Published electronically: May 1, 2012
- PDF | Request permission
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
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
- 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
- George E. Andrews, Richard Askey, and Ranjan Roy, Special functions, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, Cambridge, 1999. MR 1688958, DOI 10.1017/CBO9781107325937
- Christine Bachoc, Linear programming bounds for codes in Grassmannian spaces, IEEE Trans. Inform. Theory 52 (2006), no. 5, 2111–2125. MR 2234468, DOI 10.1109/TIT.2006.872973
- Christine Bachoc and Frank Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc. 21 (2008), no. 3, 909–924. MR 2393433, DOI 10.1090/S0894-0347-07-00589-9
- Christine Bachoc and Frank Vallentin, Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps, European J. Combin. 30 (2009), no. 3, 625–637. MR 2494437, DOI 10.1016/j.ejc.2008.07.017
- Christine Bachoc and Frank Vallentin, Optimality and uniqueness of the $(4,10,1/6)$ spherical code, J. Combin. Theory Ser. A 116 (2009), no. 1, 195–204. MR 2469257, DOI 10.1016/j.jcta.2008.05.001
- 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, DOI 10.1080/10586458.2009.10129052
- S. Bochner, Hilbert distances and positive definite functions, Ann. of Math. (2) 42 (1941), 647–656. MR 5782, DOI 10.2307/1969252
- Brian Borchers, CSDP, a C library for semidefinite programming, Optim. Methods Softw. 11/12 (1999), no. 1-4, 613–623. Interior point methods. MR 1778432, DOI 10.1080/10556789908805765
- 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
- M. Bowick and L. Giomi, Two-dimensional matter: order, curvature and defects, Advances in Physics 58 (2009), 449–563, arXiv:0812.3064.
- Henry Cohn, Order and disorder in energy minimization, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2416–2443. MR 2827978
- 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, DOI 10.1080/10586458.2007.10129008
- Henry Cohn, Noam D. Elkies, Abhinav Kumar, and Achill Schürmann, Point configurations that are asymmetric yet balanced, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2863–2872. MR 2644899, DOI 10.1090/S0002-9939-10-10284-6
- 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
- John H. Conway, Ronald H. Hardin, and Neil J. A. Sloane, Packing lines, planes, etc.: packings in Grassmannian spaces, Experiment. Math. 5 (1996), no. 2, 139–159. MR 1418961, DOI 10.1080/10586458.1996.10504585
- J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups, 3rd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1999. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. MR 1662447, DOI 10.1007/978-1-4757-6568-7
- P. Delsarte, Bounds for unrestricted codes, by linear programming, Philips Res. Rep. 27 (1972), 272–289. MR 314545
- 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.
- 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), no. 4, 429–441. MR 1384885, DOI 10.1007/BF02711518
- Serge Lang, $\textrm {SL}_2(\textbf {R})$, Graduate Texts in Mathematics, vol. 105, Springer-Verlag, New York, 1985. Reprint of the 1975 edition. MR 803508
- John Leech, Equilibrium of sets of particles on a sphere, Math. Gaz. 41 (1957), 81–90. MR 86325, DOI 10.2307/3610579
- V. I. Levenshteĭn, Bounds of the maximal capacity of a code with a limited scalar product modulus, Dokl. Akad. Nauk SSSR 263 (1982), no. 6, 1303–1308 (Russian). MR 653223
- 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
- Murray Marshall, Positive polynomials and sums of squares, Mathematical Surveys and Monographs, vol. 146, American Mathematical Society, Providence, RI, 2008. MR 2383959, DOI 10.1090/surv/146
- O. Musin, Multivariate positive definite functions on spheres, preprint, 2007, arXiv:math/0701083.
- 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/GP, version 2.3.4, Bordeaux, 2008, http://pari.math.u-bordeaux.fr/.
- A. L. Patterson, Ambiguities in the X-ray analysis of crystal structures, Phys. Rev. 65 (1944), 195–201.
- Florian Pfender, Improved Delsarte bounds for spherical codes in small dimensions, J. Combin. Theory Ser. A 114 (2007), no. 6, 1133–1147. MR 2337242, DOI 10.1016/j.jcta.2006.12.001
- Mihai Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969–984. MR 1254128, DOI 10.1512/iumj.1993.42.42045
- R. A. Rankin, The closest packing of spherical caps in $n$ dimensions, Proc. Glasgow Math. Assoc. 2 (1955), 139–144. MR 74013, DOI 10.1017/S2040618500033219
- I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96–108. MR 5922, DOI 10.1215/S0012-7094-42-00908-6
- Alexander Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005), no. 8, 2859–2866. MR 2236252, DOI 10.1109/TIT.2005.851748
- 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 (German). MR 42150, DOI 10.1007/BF02054944
- David Vernon Widder, The Laplace Transform, Princeton Mathematical Series, vol. 6, Princeton University Press, Princeton, N. J., 1941. MR 0005923
- 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
- Henry Cohn
- Affiliation: Microsoft Research New England, One Memorial Drive, Cambridge, Massachuetts 02142
- MR Author ID: 606578
- ORCID: 0000-0001-9261-4656
- Email: cohn@microsoft.com
- Jeechul Woo
- Affiliation: Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138
- Email: woo@math.harvard.edu
- 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.
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc. 25 (2012), 929-958
- MSC (2010): Primary 05B40, 52A40, 52C17; Secondary 90C22, 82B05
- DOI: https://doi.org/10.1090/S0894-0347-2012-00737-1
- MathSciNet review: 2947943