## Abstract

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 1983*a*). 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 (1983*a*) 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 (1983*a*) 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 (1967*a*) for *n*=30, 32 and by Goldberg (1967*b*) for *n*=33.

Use of Danzer's ideas by groups with an engineering background (Tarnai & Gáspár 1983*a*) 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 2*j*−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 (1983*a*) express this net freedom of the truss as(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*≥2*j*+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*≥2*j*−2. This is compatible with (2.1): if the packing is rigid then the Danzerian degree of freedom is not positive, *f*_{D}≤0, and substitution in (2.1) gives *b*≥2*j*−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 1983*a*,*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 1983*a*), 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 *f*_{D} 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 2*j*−3 net freedoms of the joints is(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 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 is(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 *Γ*(*f*_{D}), the representation of the Danzerian freedoms,(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 *Γ*(*f*_{D}) 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 *f*_{D} 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),(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 *m*−*s* is accessible by pure counting. The symmetry equivalent of (2.5) is(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 *Γ*(*f*_{D}), there is an obvious extension of the heuristic reasoning that has been used for *f*_{D}. If any irreducible representation appears with positive weight in *Γ*(*f*_{D}), 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 *f*_{D}, or positive contributions to *Γ*(*f*_{D}), implies improvability, and there can be none in its strongest form, given the exceptional case of the five-circle packing (Tarnai & Gáspár 1983*a*).

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 *D*_{5h} symmetry, illustrated in figure 1*a*. 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′.

Application of the scalar Danzer rigidity criterion (2.5), , 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 1*b*) that has *C*_{2v} symmetry and corresponds to the addition of four edges (shown as dotted lines in figure 1*a*) to Jucovič's arrangement; the graph is now Danzerian rigid, with *f*_{D}=−2. The edge length (Tarnai & Gáspár 1983*a*) 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°).

Comparison with the character table for *D*_{5h} (Atkins *et al*. 1970) shows that *Γ*(*f*_{D}), the representation of the Danzerian freedom of the truss, is the doubly degenerate . In terms of the reducible representations that appear in (2.6),the result 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 *C*_{s} (the *kernel* (McDowell 1965) of in *D*_{5h} is *C*_{s}). However, a distortion within the space can be chosen to preserve a *σ*_{v} mirror plane, reducing the symmetry to the intermediate group *C*_{2v} (a *co-kernel* (McDowell 1965) of in *D*_{5h} is *C*_{2v}). Within *D*_{5h} 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 *C*_{2v}, and has a set of four edges, forming an orbit of *C*_{2v}. The application of (2.6) to the *C*_{2v} Danzer arrangement is given explicitly in tabular form below, with a setting of the group such that the preserved *C*_{2} axis is *z* and the old *C*_{5} axis is *x*.

Comparison with the character table for *C*_{2v} (Atkins *et al*. 1970) shows that *Γ*(*f*_{D}), the representation of the Danzerian freedom of the truss, is −*A*_{2}−*B*_{1}. 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 in *D*_{5h} becomes the reducible representation *A*_{1}+*B*_{2} in *C*_{2v}. The four additional edges in Danzer's improved arrangement are equivalent under the operations in *C*_{2v} and span *A*_{1}+*A*_{2}+*B*_{1}+*B*_{2}, and hence *Γ*(*f*_{D}) for this arrangement is seen to reduce to be −*A*_{2}−*B*_{1}.

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 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 *C*_{2v} symmetry.

Given that in the Danzer *C*_{2v} arrangement, *f*_{D} is negative and *Γ*(*f*_{D}) is a purely negative sum of irreducible representations, there is no indication of a need for further descent in symmetry below *C*_{2v}. In principle, a complete geometric analysis could reveal further ‘hidden’ mechanisms, if there were any, but Danzer (1963) gives a proof that the *C*_{2v} 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 (1967*a*) proposed a solution with *D*_{5h} symmetry, illustrated in figure 2*a*. 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″.

Application of (2.1), , implies that this graph is not rigid. Tarnai & Gáspár (1983*a*) found such an improved solution (figure 2*b*), which has *C*_{2v} symmetry, and corresponds to the addition of two edges (shown as dotted lines in figure 2*a*) to Goldberg's arrangement; the graph is now Danzerian rigid, with *f*_{D}=0. The edge length (Tarnai & Gáspár 1983*a*) 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 (1983*a*) remains the best-known solution (Sloane *et al*. 2000).

The application of (2.6) to the Goldberg arrangement gives , 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 *C*_{2v}, by the addition of a pair of edges. These edges span the symmetry *A*_{1}+*B*_{2} that exactly cancels the symmetry of the mechanisms on the descent from *D*_{5h} to *C*_{2v}. Thus *Γ*(*f*_{D})=0 for Tarnai & Gáspár's solution.

In both the cases *j*=17 and 27, the initial value of *f*_{D}=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 *D*_{6h} 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″.

From the point of view of predicting whether this arrangement is improvable, application of the scalar counting rule (2.5) is uninformative: 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 , showing that the count *m*−*s*=−2 is made up of a mechanism (of symmetry *B*_{1u}) and three states of self-stress (one of symmetry *B*_{2u} and a pair of symmetry *E*_{1g}). Distortion along the *B*_{1u} pathway lowers the symmetry to the kernel group, *D*_{3h}. 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 *D*_{3h} 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 *D*_{3h} arrangement can be carried out by modifying the above tabulation (columns corresponding to symmetries lost in *D*_{3h} are struck out and the entry for *Γ*(*b*) is changed). More directly, we note that *B*_{1u}, *B*_{2u} and *E*_{1g} in *D*_{6h} descend to , and *E*″ in *D*_{3h}, respectively. The orbit of three additional edges spans . The application of (2.6) to van der Waerden's arrangement gives , *f*_{D}=−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 (*I*_{h}) 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 *f*_{D}=2. As there is no irreducible representation of dimension 2 in *I*_{h}, 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.

Comparison with the calculation tabulated above reveals that , and thus that there is a fivefold degenerate mechanism of symmetry *H*_{u}. Given the existence of a mechanism, the arrangement should be improvable. If we analyse the subgroup structure of the *I*_{h} group, we find that *H*_{u} has co-kernels *D*_{5}, *D*_{3}, *C*_{5}, *D*_{2}, *C*_{2v}, *C*_{3} and *C*_{2} and kernel *C*_{1}. The existence of multiple co-kernels offers several possible directions for the optimization search to take, and among the co-kernels, *D*_{5}, *D*_{3}, *D*_{2} and *C*_{2v} 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 *C*_{5} axis, and Goldberg (1967*a*) obtained a locally optimal solution with *D*_{5} symmetry, in which five extra edges appear (alternate equatorial edges of the underlying dodecahedron), as shown by dashed lines in figure 4*a*. The edge length is 37°25′50.9″. The application of (2.6) to the Goldberg arrangement, withgives , *f*_{D}=−3. Symmetry detects no further mechanisms and gives no reason to proceed to subgroups of *D*_{5}. It can be shown that the *D*_{5} 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 *D*_{5} arrangement.

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

However, our group-theoretical analysis indicates two other descent-in-symmetry branches that are potentially interesting. Of the four maximal co-kernels of *H*_{u} in *I*_{h}, the Goldberg solution preserves the *D*_{5} co-kernel and the Danzer solution preserves *D*_{3}. The two unexplored branches, *D*_{2} and *C*_{2v} involve co-kernel groups where the maximum order of a rotational axis is 2. In *D*_{2} symmetry, the 60-edge arrangement proposed by Schütte & van der Waerden (1951) hasobtained from the *E* and *C*_{2} columns of the *I*_{h} table 4. Equation (2.6) gives *Γ*(*f*_{D})=2*A*. Thus there are two mechanisms, and two orbits of edges (sets of symmetry-equivalent edges) are required to reduce *f*_{D} to zero and to make the packing Danzerian rigid. Explicit optimization of packings within *D*_{2} 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 4*c*. The edge length is 37°27′52.6″. When the additional edges are included in the computation, the Danzerian representation becomes , 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 *D*_{5} and *D*_{3} cases, structural calculations confirm the *D*_{3} 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 *C*_{2v} symmetry. Direct descent in symmetry from the *I*_{h} arrangement gives *Γ*(*f*_{D})=2*A*_{2}. Thus here, there is no internal evidence from the symmetry treatment that distortion along a *C*_{2v}-symmetric coordinate will improve the icosahedral arrangement. At most we can say that, if there is a distortion mode that is totally symmetric in *C*_{2v}, it is balanced by an equisymmetric state of self-stress. Nonetheless, an explicit optimization of packings within *C*_{2v} 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 (1967*a*). The single additional edge is shown by dashed line in figure 4*d*. As only one extra edge has been added, the scalar count (2.5) gives *f*_{D}=1, implying that the arrangement is improvable. Structural calculations at the *C*_{2v} 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 *C*_{2v} arrangement is an optimum only under the constraints of *C*_{2v} symmetry; when these are removed, better solutions can be found. The symmetry extension (2.6) would suggest descent to the *C*_{2} subgroup. In fact, optimization with *C*_{2} constraints returns the arrangement to that found by Danzer (1963), which is of *D*_{3} symmetry (and hence has *C*_{2} as a subgroup symmetry).

In summary: of the four descent-in-symmetry branches leading to maximal co-kernels of *H*_{u} in *I*_{h}, 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 *D*_{4d} 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 *Γ*(*f*_{D})=*E*_{1}, *f*_{D}=2, suggesting that this arrangement is improvable. Tarnai & Gáspár (1983*a*), motivated by physical arguments, found a better arrangement (figure 5*c*) with *C*_{2} symmetry and an edge length of 49°33′24.0″. The effect of the additional edges is to change *Γ*(*f*_{D}) to the null representation and *f*_{D} to zero.

*C*_{2} is one of two co-kernels of *E*_{1} in *D*_{4d}. The other is *C*_{s}. Exploration of this branch gives rise to an interesting confirmation of the ‘almost conjecture’ of Danzer. Optimization of packings within *C*_{s} symmetry constraints finds an arrangement with a single edge additional to those of the Kólya–Goldberg arrangement, shown in figure 4*c*. 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 *C*_{s} subgroup, has , *f*_{D}=2; addition of the edge changes this to *Γ*(*f*_{D})=*A*″, *f*_{D}=1. *Prima facie*, the non-zero value of *f*_{D} 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 *C*_{s} arrangement is unstable against distortion to *C*_{1}; 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 *I*_{h} 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 (1983*a*) 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 *A*_{u} symmetry in the parent *I*_{h} 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 *f*_{D}=8. Use of (2.6) gives . All the axial subgroups of *I* (*C*_{5}, *C*_{3}, *C*_{2}) are co-kernels of *T*_{2}, and all the dihedral subgroups (*D*_{5}, *D*_{3}, *D*_{2}) 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 1983*b*). This arrangement has *D*_{3} symmetry, with *Γ*(*f*_{D})=*E*, *f*_{D}=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 *D*_{3} 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 *D*_{2} symmetry, *f*_{D}=−6 and , 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 *C*_{2} axes, each one passing through the mid-points of two edges; the *D*_{2}-symmetric solution has three *C*_{2} 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 (1983*a*). 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 *f*_{D}=2. In the maximal *D*_{3h} symmetry, *Γ*(*f*_{D})=*E*′, representing the symmetric and anti-symmetric motions of the triplet of equatorial circles. Geometric symmetry can be lowered to *C*_{2v} and *C*_{s} 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.

## Acknowledgments

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.

## Footnotes

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

- © 2008 The Royal Society