Moment methods in energy minimization: New bounds for Riesz minimal energy problems

de Laat, David

doi:10.1090/tran/7976

Moment methods in energy minimization: New bounds for Riesz minimal energy problems
HTML articles powered by AMS MathViewer

by David de Laat PDF

Trans. Amer. Math. Soc. 373 (2020), 1407-1453 Request permission

Abstract:

We use moment techniques to construct a converging hierarchy of optimization problems to lower bound the ground state energy of interacting particle systems. We approximate (from below) the infinite-dimensional optimization problems in this hierarchy by block diagonal semidefinite programs. For this we develop the necessary harmonic analysis for spaces consisting of subsets of another space, and we develop symmetric sum-of-squares techniques. We numerically compute the second step of our hierarchy for Riesz $s$-energy problems with five particles on the two-dimensional unit sphere, where the $s=1$ case is the Thomson problem. This yields new numerically sharp bounds (up to high precision) and suggests that the second step of our hierarchy may be sharp throughout a phase transition and may be universally sharp for five particles on the unit sphere. This is the first time a four-point bound has been computed for a problem in discrete geometry.

References

Nikolay N. Andreev, An extremal property of the icosahedron, East J. Approx. 2 (1996), no. 4, 459–462. MR 1426716
José M. Ansemil and Klaus Floret, The symmetric tensor product of a direct sum of locally convex spaces, Studia Math. 129 (1998), no. 3, 285–295. MR 1609655
C. Bachoc, Semidefinite programming, harmonic analysis and coding theory, arXiv:0909.4767v2 (2010). Available at https://hal.inria.fr/file/index/docid/515969/filename/CIMPA.pdf.
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
Alexander Barvinok, A course in convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002. MR 1940576, DOI 10.1090/gsm/054
Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B. Shah, Julia: a fresh approach to numerical computing, SIAM Rev. 59 (2017), no. 1, 65–98. MR 3605826, DOI 10.1137/141000671
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
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
Jaka Cimprič, Salma Kuhlmann, and Claus Scheiderer, Sums of squares and moment problems in equivariant situations, Trans. Amer. Math. Soc. 361 (2009), no. 2, 735–765. MR 2452823, DOI 10.1090/S0002-9947-08-04588-1
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
H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, and M. S. Viazovska, The sphere packing problem in dimension $24$, arXiv:1603.06518 (2016).
Henry Cohn and Jeechul Woo, Three-point bounds for energy minimization, J. Amer. Math. Soc. 25 (2012), no. 4, 929–958. MR 2947943, DOI 10.1090/S0894-0347-2012-00737-1
Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain, Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1254–1279. MR 2447451, DOI 10.1137/060661569
P. E. B. DeCorte, The eigenvalue method for extremal problems on infinite vertex-transitive graphs, 2015. Thesis (Ph.D.)–Delft University of Technology, Delft.
P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
Jean Dieudonné, Sur la séparation des ensembles convexes, Math. Ann. 163 (1966), 1–3 (French). MR 194865, DOI 10.1007/BF02052480
L. Föppl, Stabile Anordnungen von Elektronen im Atom, J. Reine Angew. Math. 141 (1912), 251–302 (German). MR 1580854, DOI 10.1515/crll.1912.141.251
Gerald B. Folland, A course in abstract harmonic analysis, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1995. MR 1397028
Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann, MPFR: A multiple-precision binary floating-point library with correct rounding, ACM Trans. Math. Software 33 (2007), no. 2., DOI 10.1145/1236463.1236468
K. Fujisawa, M. Fukuda, K. Kobayashi, M. Kojima, K. Nakata, M. Nakata, and M. Yamashita, SDPA $($SemiDefinite Programming Algorithm$)$ users manual, version 7.0.5, Technical Report B-448, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, 2008.
GAP Group, GAP—Groups, Algorithms, and Programming, version $4.8.5$, 2016.
Karin Gatermann and Pablo A. Parrilo, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra 192 (2004), no. 1-3, 95–128. MR 2067190, DOI 10.1016/j.jpaa.2003.12.011
I. M. Gel′fand, R. A. Minlos, and Z. Ja. Šapiro, Predstavleniya gruppy vrashcheni i gruppy Lorentsa, ikh primeneniya, Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1958 (Russian). MR 0114876
G. D. James, The representation theory of the symmetric groups, Lecture Notes in Mathematics, vol. 682, Springer, Berlin, 1978. MR 513828, DOI 10.1007/BFb0067708
V. L. Klee Jr., Separation properties of convex cones, Proc. Amer. Math. Soc. 6 (1955), 313–318. MR 68113, DOI 10.1090/S0002-9939-1955-0068113-7
H. Kraft and C. Procesi, Classical invariant theory: A primer, 1996, www.math.iitb.ac.in/~shripad/Wilberd/KP-Primer.
A. B. J. Kuijlaars, E. B. Saff, and X. Sun, On separation of minimal Riesz energy points on spheres in Euclidean spaces, J. Comput. Appl. Math. 199 (2007), no. 1, 172–180. MR 2267541, DOI 10.1016/j.cam.2005.04.074
David de Laat, Moment methods in extremal geometry, 2016. Thesis (Ph.D.)–Delft University of Technology, Delft.
David de Laat, Fernando Mário de Oliveira Filho, and Frank Vallentin, Upper bounds for packings of spheres of several radii, Forum Math. Sigma 2 (2014), Paper No. e23, 42. MR 3264261, DOI 10.1017/fms.2014.24
David de Laat and Frank Vallentin, A semidefinite programming hierarchy for packing problems in discrete geometry, Math. Program. 151 (2015), no. 2, Ser. B, 529–553. MR 3348162, DOI 10.1007/s10107-014-0843-4
Jean B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), no. 3, 796–817. MR 1814045, DOI 10.1137/S1052623400366802
Jean B. Lasserre, An explicit equivalent positive semidefinite program for nonlinear $0$-$1$ programs, SIAM J. Optim. 12 (2002), no. 3, 756–769. MR 1884916, DOI 10.1137/S1052623400380079
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
Hassler Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), no. 1, 150–168. MR 1506881, DOI 10.2307/2371086
Theodor William Melnyk, Osvald Knop, and William Robert Smith, Extremal arrangements of points and unit charges on a sphere: equilibrium configurations revisited, Canad. J. Chem. 55 (1977), no. 10, 1745–1761 (English, with French summary). MR 0444497, DOI 10.1139/v77-246
H. D. Mittelman, The SDP problem (2016). Available at http://plato.asu.edu/ftp/sdpa_format.txt.
T. Molien, Uber die Invarianten der linearen Substitutionsgruppe, Sitzungsber. Kónig. Preuss. Akad. Wiss. (1897), 1152–1156.
Oleg R. Musin, Multivariate positive definite functions on spheres, Discrete geometry and algebraic combinatorics, Contemp. Math., vol. 625, Amer. Math. Soc., Providence, RI, 2014, pp. 177–190. MR 3289412, DOI 10.1090/conm/625/12498
Jiawang Nie and Markus Schweighofer, On the complexity of Putinar’s Positivstellensatz, J. Complexity 23 (2007), no. 1, 135–150. MR 2297019, DOI 10.1016/j.jco.2006.07.002
Pablo A. Parrilo, Semidefinite optimization, Semidefinite optimization and convex algebraic geometry, MOS-SIAM Ser. Optim., vol. 13, SIAM, Philadelphia, PA, 2013, pp. 3–46. MR 3050241
George Pólya and Gabor Szegő, Problems and theorems in analysis. II, Classics in Mathematics, Springer-Verlag, Berlin, 1998. Theory of functions, zeros, polynomials, determinants, number theory, geometry; Translated from the German by C. E. Billigheimer; Reprint of the 1976 English translation. MR 1492448, DOI 10.1007/978-3-642-61905-2_{7}
Victoria Powers and Bruce Reznick, Polynomials that are positive on an interval, Trans. Amer. Math. Soc. 352 (2000), no. 10, 4677–4692. MR 1707203, DOI 10.1090/S0002-9947-00-02595-2
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
Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, and Jean B. Lasserre, Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res. 38 (2013), no. 1, 122–141. MR 3029481, DOI 10.1287/moor.1120.0558
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
Richard Evan Schwartz, The five-electron case of Thomson’s problem, Exp. Math. 22 (2013), no. 2, 157–186. MR 3047910, DOI 10.1080/10586458.2013.766570
Richard Evan Schwartz, The triangular bi-pyramid minimizes a range of power law potentials, arXiv:1512.04628 (2015).
Richard Evan Schwartz, The phase transition in five point energy minimization, arXiv:1610.03303 (2016).
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380, DOI 10.1007/978-1-4684-9458-7
K. Fujisawa, M. Fukuda, K. Kobayashi, M. Kojima, K. Nakata, M. Nakata, and M. Yamashita, SDPA $($SemiDefinite Programming Algorithm$)$ users manual, version $7.0.5$, Technical Report B-448, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, 2008.
A. Tumanov, Minimal biquadratic energy of $5$ particles on $2$-sphere, Indiana Univ. Math. J. 62 (2013), 1717–1731., DOI 10.1512/iumj.2013.62.5148
Maryna S. Viazovska, The sphere packing problem in dimension 8, Ann. of Math. (2) 185 (2017), no. 3, 991–1015. MR 3664816, DOI 10.4007/annals.2017.185.3.7
Frank Vallentin, Lecture notes: Semidefinite programs and harmonic analysis, arXiv:0809.2017 (2008).
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., DOI 10.1515/dma.1993.3.1.75