Universally optimal distribution of points on spheres

Cohn, Henry; Kumar, Abhinav

doi:10.1090/S0894-0347-06-00546-7

Universally optimal distribution of points on spheres
HTML articles powered by AMS MathViewer

by Henry Cohn and Abhinav Kumar

J. Amer. Math. Soc. 20 (2007), 99-148

DOI: https://doi.org/10.1090/S0894-0347-06-00546-7

Published electronically: September 5, 2006

PDF | Request permission

Abstract:

We study configurations of points on the unit sphere that minimize potential energy for a broad class of potential functions (viewed as functions of the squared Euclidean distance between points). Call a configuration sharp if there are $m$ distances between distinct points in it and it is a spherical $(2m-1)$-design. We prove that every sharp configuration minimizes potential energy for all completely monotonic potential functions. Examples include the minimal vectors of the $E_8$ and Leech lattices. We also prove the same result for the vertices of the $600$-cell, which do not form a sharp configuration. For most known cases, we prove that they are the unique global minima for energy, as long as the potential function is strictly completely monotonic. For certain potential functions, some of these configurations were previously analyzed by Yudin, Kolushov, and Andreev; we build on their techniques. We also generalize our results to other compact two-point homogeneous spaces, and we conclude with an extension to Euclidean space.

References

Nikolay N. Andreev, An extremal property of the icosahedron, East J. Approx. 2 (1996), no. 4, 459–462. MR 1426716
N. N. Andreev, Location of points on a sphere with minimal energy, Tr. Mat. Inst. Steklova 219 (1997), no. Teor. Priblizh. Garmon. Anal., 27–31 (Russian); English transl., Proc. Steklov Inst. Math. 4(219) (1997), 20–24. MR 1642295
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
Richard Askey, Orthogonal polynomials and special functions, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1975. MR 0481145, DOI 10.1137/1.9781611970470
John C. Baez, The octonions, Bull. Amer. Math. Soc. (N.S.) 39 (2002), no. 2, 145–205. MR 1886087, DOI 10.1090/S0273-0979-01-00934-X
E. Bannai, A. Munemasa, and B. Venkov, The nonexistence of certain tight spherical designs, Algebra i Analiz 16 (2004), no. 4, 1–23; English transl., St. Petersburg Math. J. 16 (2005), no. 4, 609–625. MR 2090848, DOI 10.1090/S1061-0022-05-00868-X
Eiichi Bannai and N. J. A. Sloane, Uniqueness of certain spherical codes, Canadian J. Math. 33 (1981), no. 2, 437–449. MR 617634, DOI 10.4153/CJM-1981-038-7
K. Böröczky, Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sci. Hungar. 32 (1978), no. 3-4, 243–261. MR 512399, DOI 10.1007/BF01902361
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
P. Boyvalenkov and D. Danev, Uniqueness of the 120-point spherical 11-design in four dimensions, Arch. Math. (Basel) 77 (2001), no. 4, 360–368. MR 1853553, DOI 10.1007/PL00000504
P. J. Cameron, J.-M. Goethals, and J. J. Seidel, Strongly regular graphs having strongly regular subconstituents, J. Algebra 55 (1978), no. 2, 257–280. MR 523457, DOI 10.1016/0021-8693(78)90220-X
Henry Cohn, New upper bounds on sphere packings. II, Geom. Topol. 6 (2002), 329–353. MR 1914571, DOI 10.2140/gt.2002.6.329
Henry Cohn and Noam Elkies, New upper bounds on sphere packings. I, Ann. of Math. (2) 157 (2003), no. 2, 689–714. MR 1973059, DOI 10.4007/annals.2003.157.689

Optimality and uniqueness of the Leech lattice among lattices

arXiv:math.MG/0403263

Henry Cohn and Abhinav Kumar, The densest lattice in twenty-four dimensions, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 58–67. MR 2075897, DOI 10.1090/S1079-6762-04-00130-1

Uniqueness of the $(22,891,1/4)$ spherical code

arXiv:math.MG/0607448

The $D_4$ root system is not universally optimal

arXiv:math.MG/0607447

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
Hans Cuypers, A note on the tight spherical 7-design in $\Bbb R^{23}$ and 5-design in $\Bbb R^7$, Des. Codes Cryptogr. 34 (2005), no. 2-3, 333–337. MR 2128339, DOI 10.1007/s10623-004-4863-6
Philip J. Davis, Interpolation and approximation, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1963. MR 0157156
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
Wolfgang Ebeling, Lattices and codes, Second revised edition, Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Braunschweig, 2002. A course partially based on lectures by F. Hirzebruch. MR 1938666, DOI 10.1007/978-3-322-90014-2

Optimal codes in homogeneous spaces

Ramesh Gangolli, Positive definite kernels on homogeneous spaces and certain stochastic processes related to Lévy’s Brownian motion of several parameters, Ann. Inst. H. Poincaré Sect. B (N.S.) 3 (1967), 121–226. MR 0215331
George Gasper, Linearization of the product of Jacobi polynomials. I, Canadian J. Math. 22 (1970), 171–175. MR 257433, DOI 10.4153/CJM-1970-020-2
Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620, DOI 10.1007/978-1-4613-0163-9
J.-M. Goethals and J. J. Seidel, The regular two-graph on $276$ vertices, Discrete Math. 12 (1975), 143–158. MR 384597, DOI 10.1016/0012-365X(75)90029-1
S. W. Graham and Jeffrey D. Vaaler, A class of extremal functions for the Fourier transform, Trans. Amer. Math. Soc. 265 (1981), no. 1, 283–302. MR 607121, DOI 10.1090/S0002-9947-1981-0607121-1
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157, DOI 10.1007/978-1-4757-3849-0
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
G. A. Kabatjanskiĭ and V. I. Levenšteĭn, Bounds for packings on the sphere and in space, Problemy Peredači Informacii 14 (1978), no. 1, 3–25 (Russian). MR 0514023
A. V. Kolushov and V. A. Yudin, On the Korkin-Zolotarev construction, Diskret. Mat. 6 (1994), no. 1, 155–157 (Russian, with Russian summary); English transl., Discrete Math. Appl. 4 (1994), no. 2, 143–146. MR 1273240, DOI 10.1515/dma.1994.4.2.143
A. V. Kolushov and V. A. Yudin, Extremal dispositions of points on the sphere, Anal. Math. 23 (1997), no. 1, 25–34 (English, with Russian summary). MR 1630001, DOI 10.1007/BF02789828
John Leech, Equilibrium of sets of particles on a sphere, Math. Gaz. 41 (1957), 81–90. MR 86325, DOI 10.2307/3610579
V. I. Levenšteĭn, Boundaries for packings in $n$-dimensional Euclidean space, Dokl. Akad. Nauk SSSR 245 (1979), no. 6, 1299–1303 (Russian). MR 529659
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
Vladimir I. Levenshtein, Universal bounds for codes and designs, Handbook of coding theory, Vol. I, II, North-Holland, Amsterdam, 1998, pp. 499–648. MR 1667942
Yu. I. Manin, Cubic forms, 2nd ed., North-Holland Mathematical Library, vol. 4, North-Holland Publishing Co., Amsterdam, 1986. Algebra, geometry, arithmetic; Translated from the Russian by M. Hazewinkel. MR 833513
Jacques Martinet, Perfect lattices in Euclidean spaces, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 327, Springer-Verlag, Berlin, 2003. MR 1957723, DOI 10.1007/978-3-662-05167-2
Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey Jr., and Lloyd R. Welch, New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Inform. Theory IT-23 (1977), no. 2, 157–166. MR 439403, DOI 10.1109/tit.1977.1055688
Hugh L. Montgomery, Minimal theta functions, Glasgow Math. J. 30 (1988), no. 1, 75–85. MR 925561, DOI 10.1017/S0017089500007047
A. M. Odlyzko and N. J. A. Sloane, New bounds on the number of unit spheres that can touch a unit sphere in $n$ dimensions, J. Combin. Theory Ser. A 26 (1979), no. 2, 210–214. MR 530296, DOI 10.1016/0097-3165(79)90074-8
G. Pólya and G. Szegő, Problems and theorems in analysis. Vol. II, Revised and enlarged translation by C. E. Billigheimer of the fourth German edition, Springer Study Edition, Springer-Verlag, New York-Heidelberg, 1976. Theory of functions, zeros, polynomials, determinants, number theory, geometry. MR 0465631, DOI 10.1007/978-1-4757-6292-1
Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. MR 1157815
Peter Sarnak and Andreas Strömbergsson, Minima of Epstein’s zeta function and heights of flat tori, Invent. Math. 165 (2006), no. 1, 115–151. MR 2221138, DOI 10.1007/s00222-005-0488-2
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
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
P. D. Seymour and Thomas Zaslavsky, Averaging sets: a generalization of mean values and spherical designs, Adv. in Math. 52 (1984), no. 3, 213–240. MR 744857, DOI 10.1016/0001-8708(84)90022-7
Ernest Shult and Arthur Yanushka, Near $n$-gons and line systems, Geom. Dedicata 9 (1980), no. 1, 1–72. MR 566437, DOI 10.1007/BF00156473
Barry Simon, Orthogonal polynomials on the unit circle. Part 1, American Mathematical Society Colloquium Publications, vol. 54, American Mathematical Society, Providence, RI, 2005. Classical theory. MR 2105088, DOI 10.1090/coll054.1

Tables of spherical codes

http://www.research.att.com/~njas/

packings/

Elias M. Stein and Guido Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton Mathematical Series, No. 32, Princeton University Press, Princeton, N.J., 1971. MR 0304972
Robert S. Strichartz, A guide to distribution theory and Fourier transforms, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1994. MR 1276724
Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR 0372517
J. Tits, Ovoïdes et groupes de Suzuki, Arch. Math. 13 (1962), 187–198. MR 140572, DOI 10.1007/BF01650065
Jeffrey D. Vaaler, Some extremal functions in Fourier analysis, Bull. Amer. Math. Soc. (N.S.) 12 (1985), no. 2, 183–216. MR 776471, DOI 10.1090/S0273-0979-1985-15349-2
Hsien-Chung Wang, Two-point homogeneous spaces, Ann. of Math. (2) 55 (1952), 177–191. MR 47345, DOI 10.2307/1969427
David Vernon Widder, The Laplace Transform, Princeton Mathematical Series, vol. 6, Princeton University Press, Princeton, N. J., 1941. MR 0005923
Robert A. Wilson, Vector stabilizers and subgroups of Leech lattice groups, J. Algebra 127 (1989), no. 2, 387–408. MR 1028461, DOI 10.1016/0021-8693(89)90260-3
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