Available in electronic format
Available in print format		 Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN: 1088-6834(e) ISSN: 0894-0347(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Universally optimal distribution of points on spheres

Author(s): Henry Cohn; Abhinav Kumar
Journal: J. Amer. Math. Soc. 20 (2007), 99-148.
MSC (2000): Primary 52A40, 52C17; Secondary 41A05
Posted: September 5, 2006
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

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:

[An1]
N. N. Andreev, An extremal property of the icosahedron, East J. Approx. 2 (1996), 459-462. MR 1426716 (97m:52022)

[An2]
N. N. Andreev, Location of points on a sphere with minimal energy (Russian), Tr. Mat. Inst. Steklova 219 (1997), 27-31; translation in Proc. Steklov Inst. Math. 219 (1997), 20-24. MR 1642295 (99i:52019)

[An3]
N. N. Andreev, A spherical code (Russian), Uspekhi Mat. Nauk 54 (1999), 255-256; translation in Russian Math. Surveys 54 (1999), 251-253. MR 1706807

[AAR]
G. Andrews, R. Askey, and R. Roy, Special Functions, Encyclopedia of Mathematics and its Applications 71, Cambridge University Press, Cambridge, 1999. MR 1688958 (2000g:33001)

[As]
R. Askey, Orthogonal Polynomials and Special Functions, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1975. MR 0481145 (58:1288)

[Ba]
J. Baez, The octonions, Bull. Amer. Math. Soc. (N.S.) 39 (2002), 145-205, arXiv: math.RA/0105155; see also errata in Bull. Amer. Math. Soc. 42 (2005), 213. MR 1886087 (2003f:17003); MR 2132837

[BMV]
E. Bannai, A. Munemasa, and B. Venkov, The nonexistence of certain tight spherical designs, Algebra i Analiz 16 (2004), 1-23. MR 2090848 (2005e:05022)

[BS]
E. Bannai and N. J. A. Sloane, Uniqueness of certain spherical codes, Canad. J. Math. 33 (1981), no. 2, 437-449. MR 0617634 (83a:94020)

[Bo]
K. Boroczky, Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sci. Hung. 32 (1978), 243-261. MR 0512399 (80h:52014)

[BoJr]
K. Boroczky, Jr., Finite packing and covering, Cambridge Tracts in Mathematics 154, Cambridge University Press, Cambridge, 2004. MR 2078625 (2005g:52045)

[BD]
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 (2002f:05045)

[CGS]
P. J. Cameron, J. M. Goethals, and J. J. Seidel, Strongly regular graphs having strongly regular subconstituents, J. Algebra 55 (1978), 257-280. MR 0523457 (81d:05034)

[Co]
H. Cohn, New upper bounds on sphere packings II, Geom. Topol. 6 (2002), 329-353, arXiv:math.MG/0110010. MR 1914571 (2004b:52032)

[CE]
H. Cohn and N. D. Elkies, New upper bounds on sphere packings I, Ann. of Math. 157 (2003), 689-714, arXiv:math.MG/0110009. MR 1973059 (2004b:11096)

[CK1]
H. Cohn and A. Kumar, Optimality and uniqueness of the Leech lattice among lattices, preprint, 2003, arXiv:math.MG/0403263.

[CK2]
H. Cohn and A. Kumar, The densest lattice in twenty-four dimensions, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 58-67, arXiv:math.MG/0408174. MR 2075897 (2005e:11089)

[CK3]
H. Cohn and A. Kumar, Uniqueness of the $ (22,891,1/4)$ spherical code, preprint, 2004, arXiv:math.MG/0607448.

[CCEK]
H. Cohn, J. H. Conway, N. D. Elkies, and A. Kumar, The $ D_4$ root system is not universally optimal, preprint, 2004, arXiv:math.MG/0607447.

[CHS]
J. Conway, R. Hardin, and N. J. A. Sloane, Packing lines, planes, etc.: packings in Grassmannian spaces, Experiment. Math. 5 (1996), 139-159. MR 1418961 (98a:52029)

[CS]
J. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, third edition, Grundlehren der Mathematischen Wissenschaften 290, Springer-Verlag, New York, 1999. MR 1662447 (2000b:11077)

[Cu]
H. Cuypers, A note on the tight spherical $ 7$-design in $ {\mathbb{R}}^{23}$ and 5-design in $ {\mathbb{R}}^7$, Des. Codes Cryptogr. 34 (2005), 333-337. MR 2128339 (2005k:05058)

[D]
P. J. Davis, Interpolation and Approximation, Blaisdell Publishing Company, New York, 1963. MR 0157156 (28:393)

[DGS]
P. Delsarte, J. Goethals, and J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), 363-388. MR 0485471 (58:5302)

[Eb]
W. Ebeling, Lattices and codes. A course partially based on lectures by F. Hirzebruch, second edition, Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Braunschweig, 2002. MR 1938666 (2003i:11093)

[El]
N. Elkies, Optimal codes in homogeneous spaces, unpublished manuscript, 1995.

[Gan]
R. 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 (35:6172)

[Gas]
G. Gasper, Linearization of the product of Jacobi polynomials I, Canad. J. Math. 22 (1970), 171-175. MR 0257433 (41:2084)

[GR]
C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer-Verlag, New York, 2001. MR 1829620 (2002f:05002)

[GS]
J. Goethals and J. Seidel, The regular two-graph on $ 276$ vertices, Discrete Math. 12 (1975), 143-158. MR 0384597 (52:5471)

[GV]
S. W. Graham and J. D. Vaaler, A class of extremal functions for the Fourier transform, Trans. Amer. Math. Soc. 265 (1981), no. 1, 283-302. MR 0607121 (82i:42008)

[H]
R. Hartshorne, Algebraic Geometry, Graduate Texts in Mathematics 52, Springer-Verlag, New York, 1977. MR 0463157 (57:3116)

[HJ]
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985. MR 0832183 (87e:15001)

[KL]
G. A. Kabatiansky and V. I. Levenshtein, Bounds for packings on a sphere and in space (Russian), Problemy Peredaci Informacii 14 (1978), 3-25; translation in Problems of Information Transmission 14 (1978), no. 1, 1-17. MR 0514023 (58:24018)

[KY1]
A. V. Kolushov and V. A. Yudin, On the Korkin-Zolotarev construction (Russian), Diskret. Mat. 6 (1994), 155-157; translation in Discrete Math. Appl. 4 (1994), 143-146. MR 1273240 (95j:52033)

[KY2]
A. V. Kolushov and V. A. Yudin, Extremal dispositions of points on the sphere, Anal. Math. 23 (1997), 25-34. MR 1630001 (99f:41039)

[Lee]
J. Leech, Equilibrium of sets of particles on a sphere, Math. Gaz. 41 (1957), 81-90. MR 0086325 (19:165b)

[Lev1]
V. I. Levenshtein, On bounds for packings in $ n$-dimensional Euclidean space (Russian), Dokl. Akad. Nauk SSSR 245 (1979), 1299-1303; translation in Soviet Math. Dokl. 20 (1979), 417-421. MR 0529659 (80d:52017)

[Lev2]
V. I. Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math. 29 (1992), 1-82. MR 1192833 (93j:05012)

[Lev3]
V. I. Levenshtein, Universal bounds for codes and designs, in Handbook of Coding Theory, Vol. I, North-Holland, Amsterdam, 1998, pages 499-648. MR 1667942

[Man]
Yu. I. Manin, Cubic Forms: Algebra, Geometry, Arithmetic, second edition, North-Holland Mathematical Library 4, North-Holland, Amsterdam, 1986. MR 0833513 (87d:11037)

[Mar]
J. Martinet, Perfect lattices in Euclidean spaces, Grundlehren der Mathematischen Wissenschaften 327, Springer-Verlag, Berlin, 2003. MR 1957723 (2003m:11099)

[MRRW]
R. J. McEliece, E. R. Rodemich, H. C. Rumsey, Jr., and L. R. Welch, New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Information Theory 23 (1977), 157-166. MR 0439403 (55:12296)

[Mo]
H. Montgomery, Minimal theta functions, Glasgow Math. J. 30 (1988), 75-85. MR 0925561 (89d:11029)

[OS]
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), 210-214. MR 0530296 (81d:52010)

[PS]
G. Pólya and G. Szego, Problems and theorems in analysis, Vol. II, revised and enlarged translation by C. E. Billigheimer of the fourth German edition, Springer-Verlag, New York-Heidelberg, 1976. MR 0465631 (57:5529)

[R]
W. Rudin, Functional Analysis, second edition, McGraw-Hall, New York, 1991. MR 1157815 (92k:46001)

[SS]
P. Sarnak and A. Strömbergsson, Minima of Epstein's zeta function and heights of flat tori, Invent. Math. 165 (2006), 115-151.MR 2221138

[Sch]
I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96-108. MR 0005922 (3:232c)

[SchW]
K. Schütte and B. L. van der Waerden, Auf welcher Kugel haben 5, 6, 7, 8 oder 9 Punkte mit Mindestabstand 1 Platz?, Math. Ann. 123 (1951), 96-124. MR 0042150 (13:61e)

[SZ]
P. D. Seymour and T. Zaslavsky, Averaging sets: a generalization of mean values and spherical designs, Adv. in Math. 52 (1984), 213-240. MR 0744857 (85m:05031)

[SY]
E. Shult and A. Yanushka, Near $ n$-gons and line systems, Geom. Dedicata 9 (1980), 1-72. MR 0566437 (82b:51018)

[Si]
B. Simon, Orthogonal polynomials on the unit circle, Part 1: Classical theory, American Mathematical Society Colloquium Publications 54, American Mathematical Society, Providence, RI, 2005. MR 2105088 (2006a:42002a)

[Sl]
N. J. A. Sloane, with the collaboration of R. H. Hardin, W. D. Smith, and others, Tables of spherical codes, published electronically at http://www.research.att.com/~njas/packings/.

[StW]
E. M. Stein and G. Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton Mathematical Series 32, Princeton University Press, Princeton, New Jersey, 1971. MR 0304972 (46:4102)

[St]
R. Strichartz, A Guide to Distribution Theory and Fourier Transforms, CRC Press, Boca Raton, Florida, 1994. MR 1276724 (95f:42001)

[Sz]
G. Szego, Orthogonal Polynomials, fourth edition, AMS Colloquium Publications 23, American Mathematical Society, Providence, Rhode Island, 1975. MR 0372517 (51:8724)

[T]
J. Tits, Ovoïdes et groupes de Suzuki, Arch. Math. 13 (1962), 187-198. MR 0140572 (25:3990)

[V]
J. D. Vaaler, Some extremal functions in Fourier analysis, Bull. Amer. Math. Soc. (N.S.) 12 (1985), 183-216. MR 0776471 (86g:42005)

[Wa]
H. C. Wang, Two-point homogeneous spaces, Ann. Math. 55 (1952), 177-191. MR 0047345 (13:863a)

[Wid]
D. V. Widder, The Laplace Transform, Princeton University Press, Princeton, New Jersey, 1941. MR 0005923 (3:232d)

[Wil]
R. A. Wilson, Vector stabilizers and subgroups of Leech lattice groups, J. Algebra 127 (1989), 387-408. MR 1028461 (91g:20020)

[Y]
V. A. Yudin, Minimum potential energy of a point system of charges (Russian), Diskret. Mat. 4 (1992), 115-121; translation in Discrete Math. Appl. 3 (1993), 75-81. MR 1181534 (93f:31008)

Similar Articles:

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 52A40, 52C17, 41A05

Retrieve articles in all Journals with MSC (2000): 52A40, 52C17, 41A05

Additional Information:

Henry Cohn
Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052-6399
Email: cohn@microsoft.com

Abhinav Kumar
Affiliation: Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138
Address at time of publication: Microsoft Research, One Microsoft Way, Redmond, Washington 98052-6399
Email: abhinav@math.harvard.edu, abhinavk@microsoft.com

DOI: 10.1090/S0894-0347-06-00546-7
PII: S 0894-0347(06)00546-7
Keywords: Potential energy minimization, spherical codes, spherical designs, sphere packing
Received by editor(s): November 1, 2004
Posted: September 5, 2006
Additional Notes: The second author was supported by a summer internship in the Theory Group at Microsoft Research and a Putnam Fellowship at Harvard University.
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google