Royal Society Publishing


A symmetry-extended mobility criterion that incorporates Danzer's concept of bar-and-joint assemblies is derived and applied to the spherical circle-packing problem. The known scalar counting rule for Danzerian freedoms is strengthened in an equation that predicts not only the number, but also the symmetries, of distortion modes that may be used to improve a packing. Relationships between alternative candidates for best packing are consequences of the co-kernel structure of the representation spanned by Danzerian mechanisms, and in several cases lead to new local optima.


1. Introduction

Variants of the packing problem appear in many situations in the natural sciences (e.g. the books by Sadoc & Mosseri (1997), Conway & Sloane (1999), Aste & Weaire (2000) and Lord et al. (2006)). In the best-known version, the problem is to arrange n equal circles (spherical caps), without overlap, on a sphere, so that their angular radius, r, is a maximum (Tammes 1930). Exact solutions have been published for n=1–12 (Fejes Tóth 1943; Schütte & van der Waerden 1951; Danzer 1963) and n=24 (Robinson 1961). Computer-generated putative solutions for many values of n≤90 are given by Kottwitz (1991) and a list of best solutions for n≤130 is maintained by Sloane et al. (2000).

Ideas drawn from engineering have proved useful in improving candidate solutions (Danzer 1963; Tarnai & Gáspár 1983a). Danzer (1963) defined a concept of rigidity which is applicable to the circle-packing problem. In general, a packing (optimal or not) defines a graph, the so-called packing graph, with vertices representing the centre of each spherical cap and edges representing the pairs of circles in contact. In Danzer (1963), the graph is considered as a pin-jointed framework, or truss, with joints (vertices) and bars (edges) embedded in the unit sphere. As in a conventional truss, the bars provide constraints; however, the special feature here is that uniform expansion of all bars simply corresponds to an increase in the radius of the spherical caps that are to be packed, and hence is an allowed degree of freedom. Tarnai & Gáspár (1983a) recognized this feature by adopting a simple Maxwellian counting rule where the number of constraints is reduced by one with respect to a conventional count. Danzer (1963) found that, in many cases, the assignment of a candidate packing as non-rigid on this specialized criterion implied the existence of a pathway to an improved solution. He was able to find improvements to the then best available solutions for n=17, 32. Tarnai & Gáspár (1983a) also exploited this strategy to find improved solutions for n=18, 27. The concept of rigidity defined by Danzer has also been used implicitly by van der Waerden (1952) for n=20, by Leech (1957) for n=32, by Goldberg (1967a) for n=30, 32 and by Goldberg (1967b) for n=33.

Use of Danzer's ideas by groups with an engineering background (Tarnai & Gáspár 1983a) was catalysed by a mention in a classic text by Fejes Tóth (1964). On p. 236 of his book on Regular figures, he states ‘Danzer pointed out that the edge-system of an extremal graph, considered as a joint mechanism, cannot admit motions other than isometries’. This statement makes it clear that packing problems and the theory of bar-and-joint assemblies can be connected, and points the way to the analysis of packing problems with engineering tools. Danzer's rigidity principle was also applied to the packing of 19 circles in a square by Tarnai & Gáspár (1995–1996).

Connelly (1984, 1988, in press) has also used Danzer's rigidity principle and embedded it in his general theory of rigidity of tensegrity frameworks. Such a framework is built up from three types of members: ‘struts’ that are not allowed to shorten; ‘rods’ that have fixed length; and ‘cables’ that are not allowed to lengthen. The packing graph is considered as a tensegrity framework, all of whose members are struts. For a packing of circles in a concave container in a space of constant non-positive curvature, Connelly proves that infinitesimal rigidity of the packing graph must occur for a locally maximal dense packing. Unfortunately, this result does not extend to packing in a space of constant positive curvature, as exemplified by circle packings on a sphere.

Danzer's ideas have thus already proved to be fruitful in this area, but work with similar counting rules such as the Euler formula (Ceulemans & Fowler 1991), Maxwell's rule for the rigidity of frameworks (Fowler & Guest 2000) and the mechanism mobility criterion (Guest & Fowler 2006) has shown that it is often profitable to recast scalar counting rules in the language of point-group symmetry. The present paper applies analogous reasoning to Danzerian rigidity and gives a symmetry extension of Tarnai & Gáspár's treatment. Although, in the cases discussed, the symmetry treatment does not produce improvements in the known largest packing radii, it provides additional insight, typically by revealing the symmetry of the distortion of a candidate structure necessary to achieve improvement, and even, in some cases, showing the existence of improvability not apparent from the scalar count.

The structure of the paper is as follows. We describe the Danzerian counting rule and derive its symmetry counterpart in §2, and then in §3 apply it to the circle-packing problem for certain values of n, in order to describe connections between known candidate solutions, explore neglected regions of the solution space and illustrate the heuristic usefulness of Danzer's approach to rigidity and packing.

2. The Danzerian counting rule

The net freedoms available to a packing under the Danzerian definition of rigidity can be counted as follows. The 2j−3 degrees of freedom of the truss (graph embedded in the sphere) are those of the two-dimensional motion of the j joints (vertices) on the sphere, excluding the three rigid-body rotations. The b−1 constraints are provided by the b bars (edges), with the proviso that uniform expansion of all bars is allowed. Tarnai & Gáspár (1983a) express this net freedom of the truss asEmbedded Image(2.1)

An equivalent counting formula is used by Connelly (in press) for a rigid packing in a finite container. In our notation, his condition for rigidity is b≥2j+1, neglecting ‘rigid congruences of the whole space’, and if the packing is on the sphere, inclusion of these congruences, i.e. the three degrees of freedom for the rigid rotation of the sphere, leads to b≥2j−2. This is compatible with (2.1): if the packing is rigid then the Danzerian degree of freedom is not positive, fD≤0, and substitution in (2.1) gives b≥2j−2.

Danzerian freedoms give the basis for a heuristic for seeking improvements on packing arrangements, which has been used by Danzer (1963) himself and others (e.g. Tarnai & Gáspár 1983a,b; Tarnai et al. 2003). Danzer wrote (as translated by Dreyer; Danzer 1986) ‘I have not succeeded in producing a general proof that every degree of freedom can be used to enlarge the edge-length, and I do not even wish to conjecture the generality of this statement’. In fact, with the exclusion of the pathological five-circle packing (Tarnai & Gáspár 1983a), we do not know of any case where the existence of a Danzerian freedom does not provide a path to an improved solution. We take a positive value of fD as a strong indication that it is worth attempting to find improvements.

Taking into account of the symmetry of the configuration, we can refine the information from the counting argument (2.1). The symmetry extension of the scalar counting rule for Danzerian rigidity can be readily deduced using elementary point-group theory (e.g. Bishop 1973). We have to connect simply the reducible representations with the freedoms and constraints considered in the scalar case.

The representation spanned by the 2j−3 net freedoms of the joints isEmbedded Image(2.2)where Γ(j) is the permutation representation of the set of vertices; ΓT is the representation of translations along the three Cartesian directions; ΓR is the representation of rotations about the three Cartesian directions; and Γ0 is the totally symmetric representation, all in the point group G of the packing. The form of Γfree expresses the facts that each vertex is in principle free to move in two independent directions on the sphere, but is forbidden to move in the third (radial) direction, off the spherical surface, and that rigid rotations of the set of vertices as a whole do not change the packing. Equation (2.2) can thus be constructed by initially considering the representation of the j vertices free to move in three dimensions (Γ(jΓT), removing the representation of the j vertices forced to move in a radial direction Embedded Image and further removing the representation of all vertices moving in a concerted rigid-body rotation (ΓR).

The representation spanned by the b−1 constraints imposed by the bars isEmbedded Image(2.3)where Γ(b) is the permutation representation of the set of edges. The form of Γcontraint expresses the fact that every edge is of the same length (twice the radius of the contacting spherical caps), and hence would impose an independent constraint, except that, by Danzer's reasoning, a uniform (and hence totally symmetric) expansion of all edges does not constitute a constraint and hence the total number of edge-related constraints is only b−1. Note that total symmetry implies an expansion described by a single value for each orbit of symmetry-equivalent edges in the structure. In fact, here these values are equal for all orbits of edges.

Thus the symmetry equivalent of (2.1) gives Γ(fD), the representation of the Danzerian freedoms,Embedded Image(2.4)More details on the group-theoretical background are given in Fowler & Guest (2000) and references therein. Here we simply note that all the intermediate quantities required to construct Γ(fD) are easily accessible once the point-group symmetry of the packing is given. The permutation representation of a set of structural components has character Χ(R) under symmetry operation R that is equal to the number of components unshifted by that operation, Γ0 has Χ(R)=1 for all R and both ΓT and ΓR can be read off from standard character tables (e.g. Atkins et al. 1970; Altmann & Herzig 1994).

The discussion of Danzerian rigidity has so far been cast in terms of kinematics. However, in the spirit of Calladine's (1978) extension of Maxwell's Rule, it is also helpful to consider the statics perspective. In general, corresponding to each kinematic constraint is an internal force (Pellegrino & Calladine 1986; Tarnai & Szabó 2002). However, as in the Danzer formulation we exclude the uniform expansion of all bars from the set of kinematic constraints. In the statics treatment, we require that any allowed vector of internal forces is orthogonal to the main, or ‘all-ones’ vector, i.e. the vector of uniform forces in all bars. Considering only counting, we express the net freedom fD as a difference between the number of infinitesimal mechanisms m (uniform expansion of all bars being in principle allowed) and the number of possible states of self-stress, s (all orthogonal to the main vector),Embedded Image(2.5)Evaluation of m and s as separate quantities requires, in general, full knowledge of the current geometric configuration and the calculation of the rank of a constraint matrix, whereas the difference ms is accessible by pure counting. The symmetry equivalent of (2.5) isEmbedded Image(2.6)where Γ(m) and Γ(s) are, respectively, the representation spanned by the infinitesimal mechanisms, and that by the states of self-stress, of the truss that models the packing. Equation (2.6) is the full, symmetry-adapted, version of the Danzer rigidity criterion and will be the main equation that we will use in this paper.

A simple consequence of the statics-based restriction is that every allowed set of forces, and hence every allowed state of self-stress, must include both tension and compression, since the sum of forces taken over all bars must be zero. The dual, kinematic statement is that the only unconstrained expansion can be the one that is equal in all bars.

Given a method of calculating Γ(fD), there is an obvious extension of the heuristic reasoning that has been used for fD. If any irreducible representation appears with positive weight in Γ(fD), it can be taken as an indication of the symmetry of a (distortive) mode that will lead to the improvement of the packing. The same caveats apply: there is no formal proof that positive fD, or positive contributions to Γ(fD), implies improvability, and there can be none in its strongest form, given the exceptional case of the five-circle packing (Tarnai & Gáspár 1983a).

The scalar rule (2.5) gives information about the difference between the global counts m and s; (2.6) gives more detailed information on the match between m and s, irreducible representation by irreducible representation or, equivalently, class of symmetry operations by class of symmetry operations. The scalar counting rule is simply the projection of (2.6) under the identity operation. In many cases, the more detailed breakdown of net freedoms given by (2.6) can yield useful information on strategies for improving a given packing. In the remainder of the paper, we consider examples taken from the history of attempts to find optimum packings, chosen to illustrate various advantages of the symmetry treatment.

3. Applications

Examples of circle packings are now discussed, in an order that reflects increasing complexity of the symmetry treatment. In each case listed, the symmetry treatment gives a unifying perspective on the history and a practical strategy for the improvement of larger examples of the same type.

(a) Packing of 17 circles

Our first example is the packing of 17 circles, which we choose as a good illustration of the usefulness of Danzer's approach to rigidity: it shows the association between the improvement of the packing and the breaking of an assumed symmetry.

Jucovič (1959) proposed a solution with D5h symmetry, illustrated in figure 1a. The packing graphs have b=30 edges and all faces are (spherical) rhombi. The j=17 vertices are arranged in three orbits: an antipodal pair on the fivefold axis; a set of 5 on the equator; and a set of 10 on the vertices of a pentagonal prism. The edge length in the graph (the angular diameter of the circles) is 51°2′.

Figure 1

Packing graphs for 17 circles. (a) The suboptimal D5h arrangement found by Jucovič (1959) and (b) the improved C2v found by Danzer (1963). The dashed lines in (a) represent the edges that form as the arrangement is deformed to that of (b). For depictions of the spherical graphs on a plane surface, stereographic projections are used, and the centre of the projection lies on the principal axis of the symmetry of the graph. For the sake of simplicity, the edges of the graph are replaced by straight line segments.

Application of the scalar Danzer rigidity criterion (2.5), Embedded Image, implies that this graph is not rigid, and suggests that there may be improved solutions in which additional circles come into contact and hence additional edges are added to the packing graph. Danzer (1963) found such a solution (figure 1b) that has C2v symmetry and corresponds to the addition of four edges (shown as dotted lines in figure 1a) to Jucovič's arrangement; the graph is now Danzerian rigid, with fD=−2. The edge length (Tarnai & Gáspár 1983a) is 51°5′25.2″. This is probably the same solution reported by Karabinta (1973) and remains the best-known solution (Kottwitz 1991; Sloane et al. 2000).

The application of the full symmetry-adapted Danzer rigidity criterion (2.6) to the Jucovič parrangement is set out in tabular form below, which follows the format used in Fowler & Guest (2000; c=cos 72°, c′=cos 144°).

Embedded Image

View this table:

Comparison with the character table for D5h (Atkins et al. 1970) shows that Γ(fD), the representation of the Danzerian freedom of the truss, is the doubly degenerate Embedded Image. In terms of the reducible representations that appear in (2.6),Embedded Imagethe result Embedded Image follows from substitution in (2.6) and application of the rules for symmetry products.

Hence there is at least a two-parameter mechanism. A general distortion within this space of mechanisms will reduce the symmetry of the truss to Cs (the kernel (McDowell 1965) of Embedded Image in D5h is Cs). However, a distortion within the space can be chosen to preserve a σv mirror plane, reducing the symmetry to the intermediate group C2v (a co-kernel (McDowell 1965) of Embedded Image in D5h is C2v). Within D5h symmetry, it is not possible to improve the Jucovič solution by adding sets of (symmetry-equivalent) edges. Danzer's solution makes the minimum reduction in symmetry, to C2v, and has a set of four edges, forming an orbit of C2v. The application of (2.6) to the C2v Danzer arrangement is given explicitly in tabular form below, with a setting of the group such that the preserved C2 axis is z and the old C5 axis is x.

Embedded Image

View this table:

Comparison with the character table for C2v (Atkins et al. 1970) shows that Γ(fD), the representation of the Danzerian freedom of the truss, is −A2B1. The scalar rule has shown that the final arrangement has at least two states of self-stress and the symmetry rule now shows that neither is totally symmetric.

This result could have been obtained more elegantly by considering descent in symmetry. We observe that Embedded Image in D5h becomes the reducible representation A1+B2 in C2v. The four additional edges in Danzer's improved arrangement are equivalent under the operations in C2v and span A1+A2+B1+B2, and hence Γ(fD) for this arrangement is seen to reduce to be −A2B1.

This case has the simplifying feature that there is only one co-kernel in the space of mechanisms, i.e. there is a single high-symmetry path away from the initial configuration. The mechanism distortion space is defined by two parameters, and the Embedded Image symmetry of the mechanisms is the same as that of a pair of translations that can be chosen to be along the two directions in, and perpendicular to, a given σv mirror plane. If we choose to follow only the ‘in-plane’ pathway, the arrangement retains C2v symmetry.

Given that in the Danzer C2v arrangement, fD is negative and Γ(fD) is a purely negative sum of irreducible representations, there is no indication of a need for further descent in symmetry below C2v. In principle, a complete geometric analysis could reveal further ‘hidden’ mechanisms, if there were any, but Danzer (1963) gives a proof that the C2v arrangement is a true local optimum.

(b) Packing of 27 circles

The packing of 27 circles has features in common with the 17-circle case. Goldberg (1967a) proposed a solution with D5h symmetry, illustrated in figure 2a. The packing graph has b=50 edges and all faces are again (spherical) rhombi. The j=27 vertices are arranged in four orbits: an antipodal pair on the fivefold axis; a set of 5 on the equator; and two sets of 10, where each set lies on the vertices of a different pentagonal prism. The edge length in the graph is 40°40′39.2″.

Figure 2

Packing graphs for 27 circles. (a) The suboptimal D5h arrangement found by Goldberg (1967a) and (b) the improved C2v arrangement found by Tarnai & Gáspár (1983a). The dashed lines in (a) represent the edges that form as the arrangement is deformed to that of (b).

Application of (2.1), Embedded Image, implies that this graph is not rigid. Tarnai & Gáspár (1983a) found such an improved solution (figure 2b), which has C2v symmetry, and corresponds to the addition of two edges (shown as dotted lines in figure 2a) to Goldberg's arrangement; the graph is now Danzerian rigid, with fD=0. The edge length (Tarnai & Gáspár 1983a) is 40°40′39.4″. Coxeter (letter of 20 July 1983 to T.T.) described this change of one-fifth of a second of arc as ‘surely the smallest angle that ever played a significant role in geometry!’. The solution found by Tarnai & Gáspár (1983a) remains the best-known solution (Sloane et al. 2000).

The application of (2.6) to the Goldberg arrangement gives Embedded Image, and hence there is at least a two-parameter mechanism. Tarnai & Gáspár's solution makes the minimum reduction in symmetry, to the co-kernel C2v, by the addition of a pair of edges. These edges span the symmetry A1+B2 that exactly cancels the Embedded Image symmetry of the mechanisms on the descent from D5h to C2v. Thus Γ(fD)=0 for Tarnai & Gáspár's solution.

In both the cases j=17 and 27, the initial value of fD=2 leads to the expectation that two additional bars will appear in the improved solution. The symmetry viewpoint leads us to expect additional bars to appear in whole orbits, which here must be of size two or four. The cases j=17 and 27 provide an example of each.

(c) Packing of 20 circles

Rutishauser (1945) proposed a solution for 20 circles illustrated in figure 3. A subset, consisting of 18 of the circles and their 36 contacts, defines a D6h packing graph—the remaining two circles are ‘rattlers’ in hexagonal holes at the poles of the unit sphere. The rattling circles make no contribution to the rigidity analysis and so j is effectively reduced to 18. The edge length in the graph can be calculated as 46.67462°=46°40′29″.

Embedded Image

Figure 3

Schematic (non-stereographic) Schlegel representations of packings of 20 circles. Solid lines show edges common to D6h (Rutishauser 1945) and D3h (van der Waerden 1952) packings and dashed lines indicate the three extra edges of the D3h arrangement. The two isolated filled circles represent rattlers.

View this table:

From the point of view of predicting whether this arrangement is improvable, application of the scalar counting rule (2.5) is uninformative: Embedded Image simply tells us that any mechanisms of this truss, if any, are outnumbered by states of self-stress. Counting alone cannot decide whether such mechanisms exist. Symmetry can tell us more. The analysis set out in tabular form above yields Embedded Image, showing that the count ms=−2 is made up of a mechanism (of symmetry B1u) and three states of self-stress (one of symmetry B2u and a pair of symmetry E1g). Distortion along the B1u pathway lowers the symmetry to the kernel group, D3h. This mechanism is finite, as in the lower group it is not blocked by an equisymmetric state of self-stress (Guest & Fowler 2007).

van der Waerden (1952) found an improved arrangement for 20 circles, of D3h symmetry. It includes three extra edges (dashed lines in figure 3) and retains the two rattling circles of Rutishauser's solution. The edge length is 47°25′51.7″. The analysis of the rigidity in the D3h arrangement can be carried out by modifying the above tabulation (columns corresponding to symmetries lost in D3h are struck out and the entry for Γ(b) is changed). More directly, we note that B1u, B2u and E1g in D6h descend to Embedded Image, Embedded Image and E″ in D3h, respectively. The orbit of three additional edges spans Embedded Image. The application of (2.6) to van der Waerden's arrangement gives Embedded Image, fD=−5, and symmetry detects no further mechanisms. The solution found by van der Waerden (1952) remains the best so far (Sloane et al. 2000).

In general, counting arguments alone can never predict improvability of an overconstrained arrangement, but, as the case of 20 circles shows, symmetry can reveal the presence of hidden mechanisms, and hence give a direction for the exploration of possible improvements.

(d) Packing of 32 circles

A symmetry-based approach, naturally enough, is likely to give most information for the arrangements of high symmetry. In this respect, the case of 32 circles provides a good example, with a rich structure of candidate solutions, which are investigated in detail in the present section.

Schütte & van der Waerden (1951) proposed an arrangement of 32 circles with full icosahedral (Ih) symmetry and edge length 37°22′38.5″. The packing graph is the skeleton of the rhombic triacontahedron (illustrated in figure 4) with two orbits of vertices (12 at the vertices of an icosahedron and 20 at the vertices of a dodecahedron) and a single orbit of 60 edges. The 30 faces are all spherical rhombi centred on the edge mid-points of the icosahedron/dodecahedron. Scalar counting gives fD=2. As there is no irreducible representation of dimension 2 in Ih, and as the positions of the vertices are fixed if icosahedral symmetry is retained, this count of +2 immediately indicates that the arrangement must support both mechanisms and states of self-stress.

Embedded Image

Figure 4

Packing graphs for 32 circles, shown as modifications of stereographic projections of the Ih-symmetric Schütte & van der Waerden (1951) arrangement, as viewed along: (a) a fivefold axis with the five extra edges in the D5 arrangement (Goldberg 1967a), (b) a threefold axis with the six extra edges of the Danzer (1963) arrangement, and (c,d) a twofold axis with the extra edges of the D2 and C2v locally optimal arrangements identified in the present work indicated by dashed lines.

View this table:

Comparison with the calculation tabulated above reveals that Embedded Image, and thus that there is a fivefold degenerate mechanism of symmetry Hu. Given the existence of a mechanism, the arrangement should be improvable. If we analyse the subgroup structure of the Ih group, we find that Hu has co-kernels D5, D3, C5, D2, C2v, C3 and C2 and kernel C1. The existence of multiple co-kernels offers several possible directions for the optimization search to take, and among the co-kernels, D5, D3, D2 and C2v have a special status, in that they are not subgroups of other co-kernels. A reasonable heuristic would be to consider possible arrangements of 32 circles with one of these four point-group symmetries.

Leech (1957) noted that the fully icosahedral arrangement could be improved by twisting about a C5 axis, and Goldberg (1967a) obtained a locally optimal solution with D5 symmetry, in which five extra edges appear (alternate equatorial edges of the underlying dodecahedron), as shown by dashed lines in figure 4a. The edge length is 37°25′50.9″. The application of (2.6) to the Goldberg arrangement, withEmbedded Imagegives Embedded Image, fD=−3. Symmetry detects no further mechanisms and gives no reason to proceed to subgroups of D5. It can be shown that the D5 structure is indeed a local optimum. Following Tarnai & Gáspár (1991), we model the packing as a structure that consists of straight bars and frictionless pin joints, lying on the surface of a sphere. Explicit structural calculations at the packing geometry confirm the absence of mechanisms; there is a state of self-stress in which all edges of the packing graph are in compression, and this confirms the local optimum character of the D5 arrangement.

Danzer (1963, 1986) improved the icosahedral arrangement by twisting about a C3 axis, and obtained a locally optimal solution with D3 symmetry, in which six additional edges appear, as shown by dashed lines in figure 4b. The edge length in the improved arrangement is 37°28′30.8″. Application of (2.6) to Danzer's arrangement, withEmbedded Imagegives Embedded Image, fD=−4, and symmetry detects no further mechanisms and hence gives no reason to proceed to subgroups of D3. As in the D5 case, structural calculations confirm the local optimum nature of this D3 arrangement.

However, our group-theoretical analysis indicates two other descent-in-symmetry branches that are potentially interesting. Of the four maximal co-kernels of Hu in Ih, the Goldberg solution preserves the D5 co-kernel and the Danzer solution preserves D3. The two unexplored branches, D2 and C2v involve co-kernel groups where the maximum order of a rotational axis is 2. In D2 symmetry, the 60-edge arrangement proposed by Schütte & van der Waerden (1951) hasEmbedded Imageobtained from the E and C2 columns of the Ih table 4. Equation (2.6) gives Γ(fD)=2A. Thus there are two mechanisms, and two orbits of edges (sets of symmetry-equivalent edges) are required to reduce fD to zero and to make the packing Danzerian rigid. Explicit optimization of packings within D2 symmetry constraints, using the technique described in Tarnai et al. (2003), finds an optimum packing in which eight edges have been added to give a total of 68. The extra edges fall into two sets of four, each of which spans the regular orbit (Fowler & Quinn 1986); all eight are shown by dashed lines in figure 4c. The edge length is 37°27′52.6″. When the additional edges are included in the computation, the Danzerian representation becomes Embedded Image, guaranteeing the presence of at least six states of self-stress, indicating a highly overconstrained packing. We note that the edge length in this packing is intermediate between those of Goldberg's and Danzer's arrangements, and the packing itself satisfies both the scalar and symmetry-adapted criteria of Danzerian rigidity. As in the D5 and D3 cases, structural calculations confirm the D3 local optimum. Interestingly, this arrangement has more edges (68) than Danzer's better, 66-edge arrangement (and, as an aside, suggests an alternative formulation of the packing problem: find the maximally overconstrained, locally optimal, packing of n spherical caps on a sphere).

The second alternative branch preserves C2v symmetry. Direct descent in symmetry from the Ih arrangement gives Γ(fD)=2A2. Thus here, there is no internal evidence from the symmetry treatment that distortion along a C2v-symmetric coordinate will improve the icosahedral arrangement. At most we can say that, if there is a distortion mode that is totally symmetric in C2v, it is balanced by an equisymmetric state of self-stress. Nonetheless, an explicit optimization of packings within C2v symmetry constraints does yield a new arrangement, with edge length 37°24′34.8″, also intermediate between those of Schütte & van der Waerden (1951) and Goldberg (1967a). The single additional edge is shown by dashed line in figure 4d. As only one extra edge has been added, the scalar count (2.5) gives fD=1, implying that the arrangement is improvable. Structural calculations at the C2v packing geometry confirm the presence of the four mechanisms predicted by symmetry, and no more. Structural computations show that, for any combination of states of self-stress that leave all contact edges in compression, the (infinitesimal) mechanisms have negative geometric stiffness and hence the configuration is unstable. Thus the C2v arrangement is an optimum only under the constraints of C2v symmetry; when these are removed, better solutions can be found. The symmetry extension (2.6) would suggest descent to the C2 subgroup. In fact, optimization with C2 constraints returns the arrangement to that found by Danzer (1963), which is of D3 symmetry (and hence has C2 as a subgroup symmetry).

In summary: of the four descent-in-symmetry branches leading to maximal co-kernels of Hu in Ih, three have terminated in locally optimal packing arrangements, only two of which have been identified previously in the literature.

(e) Packing of 18 circles

Strohmajer (1963) reported that Kólya had constructed a packing arrangement of 18 circles with D4d symmetry: the same arrangement with edge length 49°33′5.7″ was independently reported by Goldberg (1965) and is shown in figure 5. Analysis using (2.6) gives Γ(fD)=E1, fD=2, suggesting that this arrangement is improvable. Tarnai & Gáspár (1983a), motivated by physical arguments, found a better arrangement (figure 5c) with C2 symmetry and an edge length of 49°33′24.0″. The effect of the additional edges is to change Γ(fD) to the null representation and fD to zero.

Figure 5

Packing graphs for 18 circles. (a,b) A stereographic projection of the D4d Kólya–Goldberg arrangement (Strohmajer 1963; Goldberg 1965), with dashed lines indicating, respectively, the additional edges of the C2 arrangement found by Tarnai & Gáspár (1983a) and that found in the present work. (c) A stereographic projection of the Tarnai & Gáspár (1983a) arrangement, viewed along the C2 axis.

C2 is one of two co-kernels of E1 in D4d. The other is Cs. Exploration of this branch gives rise to an interesting confirmation of the ‘almost conjecture’ of Danzer. Optimization of packings within Cs symmetry constraints finds an arrangement with a single edge additional to those of the Kólya–Goldberg arrangement, shown in figure 4c. The edge length is 49°33′21.2″, intermediate between the Kólya–Goldberg and Tarnai–Gáspár arrangements. With 32 edges, the Kólya–Goldberg arrangement, considered in the Cs subgroup, has Embedded Image, fD=2; addition of the edge changes this to Γ(fD)=A″, fD=1. Prima facie, the non-zero value of fD would indicate an arrangement that is locally improvable by a symmetry-breaking distortion. A structural calculation of the type used above for the case of 32 circles confirms here that the Cs arrangement is unstable against distortion to C1; under the Danzerian state of self-stress, in which all contact edges are in compression, the single mechanism predicted by counting has negative geometric stiffness (Guest 2006), showing the arrangement to be unstable.

(f) Packing of 80 circles

A packing arrangement for 80 circles was suggested by R. M. Robinson (1966, unpublished manuscript). It has Ih symmetry, and its graph can be derived from that of the truncated icosahedron by adding an isolated point on each hexagonal face. The edge length is 23°16′53.2″. Tarnai & Gáspár (1983a) noted that this could easily be improved by connecting each of Robinson's rattlers to three neighbours by making a concerted rotation of all hexagon–hexagon edges of the underlying truncated icosahedron and simultaneously increasing the circle diameter. This distortion, of Au symmetry in the parent Ih group, reduces the symmetry of the arrangement to I and gives a packing with edge length 23°17′48.6″.

What can symmetry arguments tell us about the prospects for improving yet further on this solution? There are 150 edges in the packing graph that therefore has fD=8. Use of (2.6) gives Embedded Image. All the axial subgroups of I (C5, C3, C2) are co-kernels of T2, and all the dihedral subgroups (D5, D3, D2) are co-kernels of H, leading to an embarrassingly large choice of directions for exploration. An improvement of the I-symmetric solution, with six additional edges, and edge length 23°18′7.3″ was subsequently found (Tarnai & Gáspár 1983b). This arrangement has D3 symmetry, with Γ(fD)=E, fD=2. Both the Danzer count and its symmetry extension suggest that this can be further improved. However, it turns out that a better solution, the best obtained so far for 80 circles, cannot be derived from the I solution (or, therefore, the D3 solution) by the addition of edges. The current best solution has 164 edges, edge length 23°33′11.0″, and is listed in Sloane's catalogue (Sloane et al. 2000), where it is attributed to J. Buddenhagen. This graph has D2 symmetry, fD=−6 and Embedded Image, so that from the point of view of Danzerian rigidity, this overconstrained graph gives no indication of further improvability.

In summary, at least in the present state of knowledge of this problem, the best solution is the one that could not have been predicted starting from the earliest proposed solution by the use of the Danzerian heuristic alone. (The fact that the Buddenhagen graph cannot be derived from the I solution by edge addition alone is easily checked: the I-symmetric solution has 15 C2 axes, each one passing through the mid-points of two edges; the D2-symmetric solution has three C2 axes, each one passing through a pair of face centres.) This is not a criticism of the heuristic itself, merely a salutary reminder that when using a method based on local optimization, it may be impossible to reach a global minimum that belongs to another region of the solution space.

(g) Packing of five circles

The packing of five circles was discussed in Tarnai & Gáspár (1983a). Its packing can be derived from the octahedral six-circle packing without the change of radius by removal of one equatorial circle, to leave fixed circles at the North and South Poles, and three circles that are free to move along the Equator. The arrangement is non-rigid, but it cannot be improved, even though the generic packing graph has only six longitudinal edges, and hence fD=2. In the maximal D3h symmetry, Γ(fD)=E′, representing the symmetric and anti-symmetric motions of the triplet of equatorial circles. Geometric symmetry can be lowered to C2v and Cs by these motions, but the circles cannot be enlarged.

This is the special case that blocks any very general version of the Danzer almost conjecture, and implies that there must be difficulties in extending Connelly's (1984, 1988, in press) theorem for the packing of circles in a concave container to spaces of constant positive curvature: there is at least one case where the packing graph is not (infinitesimally) rigid for a locally maximal dense packing.

4. Conclusion

The present paper has shown the usefulness, and also some of the limitations, of combining symmetry-based analysis with Danzer's concept of rigidity, and using these tools to study circle packings. The symmetry-adapted analysis has given new insight into the historical development of improved circle packings that were found through symmetry breaking from an initial high-symmetry arrangement—in each of these cases, the symmetry-adapted Danzerian rigidity criterion has shown the initial high-symmetry arrangement not to be rigid. In the particular case of the packing of 32 circles on the sphere, the analysis has also found a new, locally optimal packing that, although not globally optimal, is more overconstrained than the current best-known arrangement.


P.W.F. acknowledges the support from the Royal Society/Wolfson Research Merit Award Scheme. T.T. is grateful for the financial support under OTKA grant T046846.


    • Received April 20, 2008.
    • Accepted July 16, 2008.


View Abstract