Three-point bounds for energy minimization

Cohn, Henry¹ ; Woo, Jeechul²

¹ Microsoft Research New England, One Memorial Drive, Cambridge, Massachuetts 02142
² Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138

Journal of the American Mathematical Society, Tome 25 (2012) no. 4, pp. 929-958

Résumé

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.

Détail

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

Bibliographie

[1] Andreev, N. N. A spherical code Uspekhi Mat. Nauk 1999 255 256

[2] Andrews, George E., Askey, Richard, Roy, Ranjan Special functions 1999

[3] Bachoc, Christine Linear programming bounds for codes in Grassmannian spaces IEEE Trans. Inform. Theory 2006 2111 2125

[4] Bachoc, Christine, Vallentin, Frank New upper bounds for kissing numbers from semidefinite programming J. Amer. Math. Soc. 2008 909 924

[5] Bachoc, Christine, Vallentin, Frank Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps European J. Combin. 2009 625 637

[6] Bachoc, Christine, Vallentin, Frank Optimality and uniqueness of the (4,10,1/6) spherical code J. Combin. Theory Ser. A 2009 195 204

[7] Ballinger, Brandon, Blekherman, Grigoriy, Cohn, Henry, Giansiracusa, Noah, Kelly, Elizabeth, Schã¼Rmann, Achill Experimental study of energy-minimizing point configurations on spheres Experiment. Math. 2009 257 283

[8] Bochner, S. Hilbert distances and positive definite functions Ann. of Math. (2) 1941 647 656

[9] Borchers, Brian CSDP, a C library for semidefinite programming Optim. Methods Softw. 1999 613 623

[10] Bã¶Rã¶Czky, Kã¡Roly, Jr. Finite packing and covering 2004

[11] Cohn, Henry Order and disorder in energy minimization 2010 2416 2443

[12] Cohn, Henry, Conway, John H., Elkies, Noam D., Kumar, Abhinav The 𝐷₄ root system is not universally optimal Experiment. Math. 2007 313 320

[13] Cohn, Henry, Elkies, Noam D., Kumar, Abhinav, Schã¼Rmann, Achill Point configurations that are asymmetric yet balanced Proc. Amer. Math. Soc. 2010 2863 2872

[14] Cohn, Henry, Kumar, Abhinav Universally optimal distribution of points on spheres J. Amer. Math. Soc. 2007 99 148

[15] Conway, John H., Hardin, Ronald H., Sloane, Neil J. A. Packing lines, planes, etc.: packings in Grassmannian spaces Experiment. Math. 1996 139 159

[16] Conway, J. H., Sloane, N. J. A. Sphere packings, lattices and groups 1999

[17] Delsarte, P. Bounds for unrestricted codes, by linear programming Philips Res. Rep. 1972 272 289

[18] Hardin, R. H., Sloane, N. J. A. McLaren’s improved snub cube and other new spherical designs in three dimensions Discrete Comput. Geom. 1996 429 441

[19] Lang, Serge 𝑆𝐿₂(𝑅) 1985

[20] Leech, John Equilibrium of sets of particles on a sphere Math. Gaz. 1957 81 90

[21] Levenshteä­N, V. I. Bounds of the maximal capacity of a code with a limited scalar product modulus Dokl. Akad. Nauk SSSR 1982 1303 1308

[22] Levenshteä­N, V. I. Designs as maximum codes in polynomial metric spaces Acta Appl. Math. 1992 1 82

[23] Marshall, Murray Positive polynomials and sums of squares 2008

[24] Pfender, Florian Improved Delsarte bounds for spherical codes in small dimensions J. Combin. Theory Ser. A 2007 1133 1147

[25] Putinar, Mihai Positive polynomials on compact semi-algebraic sets Indiana Univ. Math. J. 1993 969 984

[26] Rankin, R. A. The closest packing of spherical caps in 𝑛 dimensions Proc. Glasgow Math. Assoc. 1955 139 144

[27] Schoenberg, I. J. Positive definite functions on spheres Duke Math. J. 1942 96 108

[28] Schrijver, Alexander New code upper bounds from the Terwilliger algebra and semidefinite programming IEEE Trans. Inform. Theory 2005 2859 2866

[29] Schã¼Tte, K., Van Der Waerden, B. L. Auf welcher Kugel haben 5, 6, 7, 8 oder 9 Punkte mit Mindestabstand Eins Platz? Math. Ann. 1951 96 124

[30] Widder, David Vernon The Laplace Transform 1941

[31] Yudin, V. A. Minimum potential energy of a point system of charges Diskret. Mat. 1992 115 121