Three-point bounds for energy minimization

Cohn, Henry; Woo, Jeechul

doi:10.1090/S0894-0347-2012-00737-1

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