Possible Global Minimum Lattice Configurations for Thomson's Problem of Charges on a Sphere

Possible Global Minimum Lattice Configurations for Thomson's Problem of Charges on a Sphere

Eric Lewin Altschuler,1 Timothy J. Williams,2 Edward R. Ratner,3 Robert Tipton,1 Richard Stong,4 Farid Dowla,1 and Frederick Wooten5

1Lawrence Livermore National Laboratory, PO Box 808, Livermore, CA 94551
2Los Alamos National Laboratory, MS B256 Los Alamos, NM 87545
3Department of Applied Physics, Stanford University, Stanford, CA 94305
4Department of Mathematics, Rice University, Houston, TX 77004
5Department of Applied Science, University of California Davis/Livermore, PO Box 808, Livermore CA 94551

(January 10, 1997)

[Published as Phys. Rev. Lett. 78, 2681 (1997)]

Abstract.  What configuration of N point charges on a conducting sphere minimizes the Coulombic energy? J. J. Thomson posed this question in 1904. For N ≤ 112, numerical methods have found apparent global minimum energy configurations; but the number of local minima appears to grow exponentially with N, making many such methods impractical. Here we describe a topological/numerical procedure that we believe gives the global energy minimum lattice configuration for N of the form N = 10(m2+n2+mn)+2 (m, n positive integers). For those N with more than one lattice, we give a rule to choose the minimum one.

PACS numbers: 02.60.Pn

Given N unit point charges on the surface of a unit conducting sphere, what is the configuration of the charges for which the Coulombic energy ∑i,j = 1;j > iN 1/|ri-rj| is minimized? This question was originally asked by J.J. Thomson long ago[1] and has since been investigated by many authors[2,3,4,5,6,7,8,9,10,11,12]. Besides its interest as a physics and mathematical optimization problem, the question posed by Thomson is similar to problems in other fields such as the arrangement of the protein subunits of a protein coat of a spherical virus[13,14,15], and the arrangement of atoms in a spherical molecule[16]. Somewhat surprisingly, it turns out that the configuration of minimum energy for Thomson's problem is not the configuration which places the charges at furthest distance from each other, or the configuration of greatest symmetry. For example, for eight charges, the configuration of minimum energy is not a cube, but a twisted noncubic rectangular parallelepiped[5]. For 2 ≤ N ≤ 100 by means of extensive trials utilizing a number of methods it appears that the minimum energy configurations may have been found[1,2,3,4,5,6,7,8,9,10,11,12]. However, as the number of closely spaced local minima seems to grow tremendously with N[11], for an arbitrary large N it may be extremely difficult to find the global minimum configuration. Generalizing from topological properties of the apparent local minimum energy configurations for N ≤ 100 , we have noted a topological/numerical procedure described here to generate ``lattice'' configurations which we think are global minima for Thomson's problem for numbers of charges of the form N = 10(m2 + n2 + mn) +2 with m and n positive integers.

We can consider the charges on the sphere as vertices of a convex polytope. It had been noted that for 12 ≤ N ≤ 60, N = 72, N = 78, N = 100 the minimum energy configuration usually has 12 vertices with five nearest neighbors (pentamers) and N-12 vertices with six nearest neighbors (hexamers)[7,9]. We have confirmed this for the other 61 &le N &le 100 (Table I, refs. [7], [9] and refs. therein). This observation can be appreciated from a topological point of view with reference to Euler's formula relating faces (F), vertices (V), and edges (E) of a convex polytope (F+V = E+2). Indeed, if all the faces of our polytope are triangles and we consider the polytope to consist only of tetramers (vertices with four nearest neighbors) (V4) , pentamers (V5) , hexamers (V6) , and heptamers (vertices with seven nearest neighbors) (V7), then
V5+2V4-V7 = 12  ,
(1)
with all the rest of the vertices being hexamers[17]. From Table I we see that in general the apparent minimum energy configuration has exactly 12 pentamers and N-12 hexamers. Many of the exceptions occur for numbers of charges such as 33, 70, 71 and 73 which are very close to N = 32, and N = 72 which have extremely stable supposed global minimum configurations (see below).



  Table I:  Most apparent minimum energy configurations for 12 ≤ N ≤ 100 have 12 pentamers and N-12 hexamers. Exceptions are given in the table. N is the number of charges. If the polytope contains Q quadrilateral faces, V5 pentamers, V4 tetramers, and V7 heptamers, then it can be shown that V5+2V4-V7-2Q = 12 with all the rest of the vertices being hexamers. To decide if two vertices, v and w, are nearest neighbors we look at the triangles with vertices v, w, and x, where x ranges over all other vertices. If the angle at the vertex x is 90 degrees or more (for any x) then v and w are not nearest neighbors. We join vertices determined to be nearest neighbors by an edge. The resulting polytopes have mainly triangular faces with an occasional quadrilateral face. (Especially for polytopes with quadrilateral faces, there can be some ambiguity in assignment of nearest neighbors. Another method for doing so with less ambiguity is given in Ref. [22].)
N Pentamers Hexamers Heptamers Tetramers Quadrilateral Faces

13

10 2 1
18 8 8 2
21 10 10 1
33 15 17 1 1
53 16 37 2
59 14 43 2
70 20 50 4
71 16 55 2
73 16 57 2
79 15 63 1 1
83 14 67 2


 

For


N = 10(m2 + n2 + mn) + 2
(2)

with m and n positive integers and m ≥ n, a particularly symmetric icosahedral lattice configuration can be formed with exactly 12 pentamers (and no tetramers or heptamers) with the vertices of the pentamers at the vertices of an icosahedron (Fig. 1). The procedure for generating the lattice is given in detail in the Fig. 1. In outline: We first put points on an icosahedron, then we project these points radially onto a sphere, then a conjugate gradient minimization routine[18] is used to obtain the final positions of the charges. For N = 32 (m = 1, n = 1) and N = 72 (m = 2, n = 1) this procedure generates the previously known apparent minimum energy configurations. The next lattice numbers are N = 122 (m = 2, n = 2) and N = 132 (m = 3, n = 1). It has been noted that for 70 ≤ N ≤ 112 the number of local minima increases as 0.382exp(0.0497N)[11]. In accordance with this we used a conjugate gradient[18] starting from 200 and 300 random configurations for N = 122 and 132 respectively, and did not find an energy lower than the lattice energy for either value of N. We also ran from some configurations slightly perturbed from the lattice loading. Without an analytical proof we cannot be sure that the lattice configurations are the ones of minimum energy for N = 122 and N = 132. We believe that the lattice configurations are the ones of minimum energy for N = {122,132}, and in general we believe that the lattice configurations are the ones of minimum energy for N of the form of equation (2). (However, if the ratio of m to n is too large, then the lattice configuration may not be the one of minimum energy. See below.) For potential energies of the form {1/ra|a = 2,3} (where r is the Euclidean distance between charges) we have found that lattice configurations also appear to be the minimum energy configurations, with the exact location of the charges depending on the potential (E. L. A. et al. unpublished data). For N ≤  312, a number of groups using various methods have also found icosahedral lattices to be minimum-energy configurations[6,7,9,19,20,21,22].



  132.gif1032.gif
Figure 1:  Lattice configurations for 132 (a) and 1032 (b) charges. To go from one vertex of a pentamer to another vertex of a pentamer for 132 charges (a) one goes up three edges and over one edge, while for 1032 charges one goes up nine edges and over two edges. Vertices of hexamers are indicated by a small black circle, vertices of pentamers by a small red circles, and edges by black lines. The other points on the sphere are colored as follows: The potential energy ∑j = 1;j ≠ iN [1/(|ri-rj|)] (self-energy term omitted) is computed at the locations ri of each of the charges. The potential at other points is estimated using a linear finite element triangular function. The color scale is shown at the right with blue being lower potential and red being higher potential. To obtain lattice configurations we begin by placing points on the faces of an icosahedron. Essentially, we want to place (N-12)/20 points on each of the 20 faces of the icosahedron, taking care not to double count points on the edge between two faces. The other 12 points are the vertices of the icosahedron. For example, if one joins any three of the vertices of the pentamers in (a) there are (132-12)/20 = 6 points contained within each resulting equilateral triangle. Specifically, we identify one face of an icosahedron with an equilateral triangle in the complex plane having vertices at (0,(m+nη ),(mη+nη2)) with η = exp(πi/3). Points are placed on this first triangle by including all points from the lattice k+lη (k,l integers) which are contained in or on the boundary of the triangle. Points on the other faces of the icosahedron can be obtained by 180 degree rotation about the midpoint of the edge common to two triangles. We project the points from the icosahedron radially out to a circumscribed unit sphere. We then use a conjugate gradient minimization[18] using E = ∑i,j = 1;j > iN1/|ri-rj| to obtain the final location of the charges.

 

The question arises as to the configuration of minimum energy for those N which can be obtained by substituting more than one pair of m and n into equation (2). For example, for N = 912, two icosahedral lattice configurations can be constructed: one with m = 6 and n = 5, and another with m = 9 and n = 1. Now, for N = 42 and N = 92 which would correspond to (m = 2, n = 0) and (m = 3, n = 0), respectively, in equation (2) it is known that the minimum energy configuration is not the lattice configuration. We have shown that for N = 162 (m = 4, n = 0) the lattice configuration is also not the minimum energy configuration (E.L.A. et al. unpublished data, [19,20,21]). In general we think that for N = 10m2+2 (except for the very special case of N = 12, (m = 1, n = 0)) the lattice configuration is not the minimum energy configuration. From the result that the cases of equation (2) with n = 0 appear not to be global minima, we hypothesized that for those N that can be obtained by substituting more than one pair of m and n into equation 2, the lattice configuration with a smaller ratio of m to n has lower energy than the configuration with a larger ratio, which might more closely resemble a configuration with n = 0 (m/n = ∞). (Table II, Fig, 2). For example, for N = 912 the lattice configuration with m = 6, n = 5 has a lower energy than the lattice configuration with m = 9, n = 1 (Fig. 2). As well, we have verified this hypothesis for the other four examples of such N which are less than 2500 (Table II). A smaller ratio of m to n may lower the energy by permitting more twisting of the high energy pentamers with respect to each other than for a larger ratio of m to n. Given that N of the form of equation (2) with n = 0 the lattice configurations are not local minima, it may be that for a sufficiently large ratio of m to n the lattice configuration is not the global energy minimum configuration. (Icosahedral lattice configurations have been discussed in relation to the Tammes problem-maximization the minimum distance between N points on the surface of a unit sphere[24]. However, it has been shown that in many cases including N = 72 an icosahedral lattice and other configurations of high symmetry are not necessarily the best ones for the Tammes problem[25,26].) We note that the trend toward smaller energy spacing between the pairs of states in Table II is consistent with the bunching of local minima closer to the global minimum described in Ref. [22]. Our values of the energy for N = 122, 132,&hellip,912,… agree well with empirical formulas[8,19] for the energy of the minimum energy configuration for a given N. Though, not surprisingly, the energies of the lattice configurations are somewhat lower than predicted as the lattices are such good configurations.



 

Table II:  For N < 2500 when two lattice configurations have the same number of charges , the configuration with a smaller ratio of m to n has a lower energy. For construction of the lattices see Fig. 1.
N m n Energy
912 6 5 400 660.1320
9 1 400 662.3832
1332 9 4 860 260.5582
11 1 860 264.5477
1472 7 7 1 052 197.474
11 2 1 052 200.022
2172 9 8 2 302 877.842
13 3 2 302 880.777
2472 11 7 2 987 501.183
14 3 2 987 505.566




  912.gif912.gif
Figure 2:  Lattice configurations for N = 912 (a) m = 6, n = 5, (b) m = 9, n = 1. The configuration in (a) has a smaller ratio of m to n than the configuration in (b) and also a lower energy. For construction of the lattices see Fig. 1.

 

(Using algebraic number theory[23] it can be shown that those N for which more than one icosahedral lattice can be constructed are of the form N = 10k23jp1m1p2m2… pnmn+2 where k is an integer greater > 0 with no prime factors ≡  1 mod 6; j is an integer ≥ 0; p1,…,pn are distinct prime numbers ≡  1 mod 6; m1,…, mn are integers ≥ 0; and at least one of n or m1 is ≥ 2. The number of icosahedral lattices which can be constructed for such an N is equal to 0.5(m1+1)(m2+1)…(mn+1), rounding up if this expression is not an integer. For example; for N = 912, k = 1, j = 0, n = 2, p1 = 7, m1 = 1, p2 = 13, m2 = 1, and the number of icosahedral lattices is two.)

As mentioned, many examples of apparent minimum energy configurations which do not have exactly 12 pentamers-N = {33,70,71,73}-have numbers of charges close to the apparent lattice global energy minimum configurations for N = 32 and N = 72. This may result because the lattice configurations are so symmetric that it be difficult to add or subtract one or two charges and still have a good minimum with exactly 12 pentamers. (For N = 13 there exists no configuration of charges with 12 pentamers and 1 hexamer[27].)

There may be other families of solutions besides the icosahedral lattices. For example, the apparent minimum energy configuration for N = 78 has a T4 (tetrahedral) symmetry[9]. We have constructed an analog of this T4 solution for N = 78 with N = 306 (E.L.A. et al. unpublished data) which we suspect is the minimum energy configuration for N = 306; however, the number of random trials necessary to get confidence that this T4 configuration for N = 306 is the global minimum seems prohibitive. Perhaps, similar to N = {33,70,71,73}, the reason that the apparent global minimum configuration for N = 79 does not have exactly 12 pentamers may be because it is difficult to add one charge to the very symmetric T4 configuration for N = 78 and still obtain a good minimum with exactly 12 pentamers. Recently, very good low energy configurations have been found for N = {137,146} [19].

For N = 10(m2+n2+mn)+2 with m, n positive integers we have given a method for generating configurations which we think are global minima for Thomson's problem, and tested these configurations extensively for N = 122 and 132. We have hypothesized that in cases in which more than one pair of m and n give a lattice configuration with the same N the configuration with the smaller ratio of m to n have a lower energy and verified this hypothesis for the five such N < 2500. Given that for n = 0 the icosahedral lattices are not the minimum energy configurations, there is an interesting open question as to whether the lattices remain minimum-energy configurations as the ratio of m to n grows large. The topological patterns and symmetries manifest in the lattice configurations for Thomson's problem also appear in a diverse array of other physical and biological systems[13,14,15,16]. These configurations may be useful for benchmarking optimization methods.

We thank Vincent Caccese, Frank Graziani, the staff of the Harvard University Physics Research Library, and Andrew Gleason. E. R. R. was partially supported by the Fannie and John Hertz Foundation. This work was performed by the Lawrence Livermore National Laboratory under the auspices of the U. S. Department of Energy under Contract W-7405-Eng-48.

References

[1]
J. J. Thomson, Phil. Mag. 7 237 (1904).

[2]
L. L. Whyte, Am. Math. Monthly 59 606 (1952).

[3]
H. A. Munera, Nature 320 597 (1986).

[4]
S. C. Webb, Nature 323 20 (1986).

[5]
L. T. Wille, Nature 324 46 (1986).

[6]
T. Erber and G. M. Hockney, J. Phys. A 24 L1369 (1991).

[7]
J. R. Edmunsen, Acta Cryst. A 48 60 (1992).

[8]
L. Glasser and A. G. Avery, J. Phys. A 25 2473 (1992).

[9]
J. R. Edmunsen, Acta Cryst. A 49 648 (1993).

[10]
E. L. Altschuler et al., Phys. Rev. Lett. 72 2671 (1994).

[11]
T. Erber and G. M. Hockney, Phys. Rev. Lett. 74 1482 (1995).

[12]
E. L. Altschuler et al., Phys. Rev. Lett. 74 1483 (1995).

[13]
D. L. D. Caspar and A. Klug, Cold Spring Harbor Sym. Quant. Biol. 27, 1 (1962).

[14]
C. J. Marzec and L. A. Dat, Biophys. J. 65 2559 (1993).

[15]
B. Berger et al., Proc. natn. Acad. Sci. USA 91 7732 (1994).

[16]
H. W. Kroto et al., Nature 318 162 (1985).

[17]
D'Arcy W. Thompson, On Growth and Form (Cambridge Univ. Press, 1942).

[18]
W. H. Press et al., Numerical Recipes (Cambridge, New York, 1990).

[19]
J. R. Morris, D. M. Deavan, and K. M. Ho, Phys. Rev. B 53 146 (1996).

[20]
N. J. A. Sloane, R. H. Hardin, and W. D. Smith, unpublished. See Ref. [19].

[21]
N. J. A. Sloane et al., Discrete Computational Geometry, in press.

[22]
T. Erber and G. M. Hockney, Advances in Chemical Physics 98 495 (1996).

[23]
D. Marcus, Number Fields (Springer-Verlag, 1977).

[24]
T. Tarnai and Zs. Gaspar, Acta Cryst. A 43 612 (1987); T. Tarnai and M. J. Wenniger, Structural Topology 16 5 (1990); T. Tarnai and Zs. Gaspar, Math. Proc. Camb. Phil. Soc. 110 71 (1991); Zs. Gaspar, Acta Cryst. B 45 452 (1989).

[25]
B. W. Clare and D. L. Kepert, J. Math. Chem. 6 325 (1991).

[26]
D. A. Kottwitz, Acta Cryst. A 47 158 (1991).

[27]
B. Grünbaum and T. S.  Motzkin, Can. J. Math. 14 744 (1963).

File translated from TEX by TTH, version 2.60.
On 17 Dec 1999, 10:57.