Counting what a group cannot tell apart

Every count on this site so far has been a count of groups. Seventeen ways of repeating a pattern across the plane, seven along a strip, thirty-two crystal classes, two hundred and thirty space groups. This one is different: given a group, how many genuinely different arrangements are there on the sites it repeats?

The question is not decorative. An alloy ordering on a superlattice has some number of distinct configurations, and that number decides how much work an enumeration of candidate structures is. How many sublattices counts the repeats available at a given index; the reflections a superlattice adds says what one of them does to a diffraction pattern. This counts the decorations of one, and it is the only one of the three numbers that grows exponentially.

The answer that is wrong, and the reason it is wrong #

The obvious approach divides. There are 2¹⁶ = 65,536 ways of colouring sixteen cells with two species; the group acting on a four-by-four block of p4m has 128 operations; so there are 65,536 / 128 = 512 structures.

That number is not merely inaccurate. It is too small, always, and by an amount nobody can guess in advance.

The reason is that some arrangements are symmetric. An arrangement fixed by half of the group has an orbit of half the group’s size, so it is counted once by the enumeration and half a time by the division. Arrangements with no symmetry at all have full-length orbits and are counted correctly; the symmetric ones are the error, and the more symmetric the group the more of them there are. For p6m on the same block the division gives 341.33, which is not even a whole number and is therefore visibly not a count of anything.

Burnside’s lemma: the average number of arrangements an operation leaves alone #

The correct count is an average over the group rather than a division by it:

$$\text{structures} \;=\; \frac{1}{|G|}\sum_{g \in G} |\mathrm{Fix}(g)|.$$

Each term is the number of arrangements the operation g does not change. That is easy to compute: g permutes the sites, and an arrangement it fixes must be constant along each cycle of that permutation, so it fixes exactly c raised to the number of cycles, where c is how many species there are. Nothing has to be enumerated — a count over 2¹⁶ arrangements becomes a sum over 128 operations, each costing a walk over sixteen sites.

The identity has sixteen cycles and fixes everything, which is why the naive division is nearly right: the identity’s term alone, divided by the order, is the naive answer. Everything else in the sum is the correction the division omits.

The lemma is the orbit-stabiliser relation summed twice over. Count the pairs (g, x) with g fixing x by grouping on g, and the sum above appears; group on x instead and each arrangement contributes the size of its own stabiliser, which by orbit-stabiliser is the group’s order divided by its orbit’s length. Divide by the order and every orbit contributes exactly one. The count is a rearrangement of a double sum, and the two ways of doing it are the whole proof.

That is the same identity the orbit is the pattern uses on a single point and wyckoff positions checks at a hundred and forty-four sample points at once. Here it is being asked about a set of points rather than one.

The sum checks itself #

The lemma carries an unusual property: the sum has to be divisible by the order of the group. It is a sum of integers whose average is a count of orbits, so a remainder means the input was not a group, or an operation was left out, or one was counted twice, or a cycle structure was computed wrongly.

That is a genuine check rather than an assertion tacked on afterwards. Almost any error in constructing the group changes the sum by an amount that is not a multiple of the order, and the division reports a fraction. It fired repeatedly while this was being written: a group built on a block whose size did not admit a glide’s half-translation gave a sum that did not divide, which is exactly the case worth refusing — a glide rounded to the nearest site is a different operation, and the count it produces is a count of nothing.

So the block size is not free. A group with half translations needs an even block, and asking for an odd one throws rather than rounding.

What the counts actually are #

Read across the rows and two things stand out.

p1 already does most of the work. With only translations, the sixteen shifts of the block cut 65,536 arrangements to 4,156 — a factor of about 15.8 rather than the 16 the division would predict, and the difference is the arrangements that are periodic with a shorter repeat than the block.

The reflections earn more than the rotations. p4 has 64 operations and leaves 1,171 structures; pmm has 64 as well and leaves 1,459. The same order, different counts, because the cycle structures differ: a reflection fixes a whole line of sites and so has many cycles of length one, while a four-fold rotation fixes almost nothing. The count is not a function of the group’s order, and any argument that treats it as one is wrong for a reason it will not detect.

p6m is the ceiling here. 192 operations, 528 structures, and a naive division that is not a whole number. Every step down the subgroup lattice raises the count.

What each kind of operation contributes #

The terms of the sum sort themselves into a small number of values, and which values appear is a fact about the operation’s cycle structure rather than about its name.

A translation of order k makes cycles of length k, so it fixes c^(sites/k) arrangements — a large number when k is small and a small one when k is large. On an n × n block a translation by one cell along an axis has order n and therefore n cycles of length n, so it fixes only c^n of the c^(n²) arrangements. That is why the identity dominates the sum and the translations contribute a rounding error to it.

A reflection fixes a line of sites, and every site on that line is a cycle of length one, so a reflection’s contribution is much larger than a rotation’s of the same order. That is the whole of why pmm beats p4 in the table above at equal order.

A rotation of order four fixes at most one site, the centre, and pairs everything else into cycles of four; its contribution is roughly the fourth root of the total. Rotations are efficient at identifying arrangements and reflections are not, and the counts follow.

Three species, and why the exponent is the only thing that matters #

Changing the number of species changes the base of every term and nothing else in the argument. The lemma is indifferent to it: an operation with f cycles fixes c^f arrangements whatever c is, and the sum divides by the group order for the same reason.

What changes is the balance. With two species the identity’s term is 2^(n²) and a reflection’s is 2^(n²/2 + line/2); with ten species the identity’s term is 10^(n²) and the reflection’s is smaller by a much larger factor, so the corrections matter less and the naive division gets relatively closer. The group identifies a smaller fraction of a larger set. Symmetry buys the most when there is the least to arrange.

Where the exactness stops #

Three statements, each with a different status.

The count is exact and is a count of arrangements on a torus. The block is periodic — site (n, 0) is site (0, 0) — so what is counted is the number of distinct crystals with that repeat, which is what a structure enumeration wants. A count of arrangements on a bounded patch with edges is a different number and this one says nothing about it.

Two arrangements counted as one are related by a symmetry of the parent pattern, not by anything physical. Whether they are the same material is a question about energies, and no part of this decides it. Two configurations in one orbit have identical energies for symmetry reasons; two in different orbits may have identical energies for reasons that have nothing to do with symmetry, and this count cannot see them.

The species are labels and nothing else. Colouring with two species counts arrangements of A and B as distinct from arrangements of B and A. Identifying those as well means a larger group — the plane group times the swap — and a different, smaller count, which is exactly the two-colour classification with the colours as part of the symmetry rather than as decoration.

The same arithmetic, renamed three times #

This lemma is a small piece of mathematics with an unusually tangled attribution, and the tangle is instructive.

It is stated in Burnside’s Theory of Groups of Finite Order of 1897, where he attributes it to Frobenius; Frobenius published it in 1887; and Cauchy had the essential case in 1845. Burnside himself did not claim it, which is why it is sometimes called the lemma that is not Burnside’s. It is also, in its weighted form, Pólya’s enumeration theorem of 1937 — which is how chemistry knows it, as the count of distinct substituted benzenes.

Materials science met it again in the 1980s under a different description entirely. Enumerating derivative superstructures — the distinct ways of decorating a superlattice — is exactly this count, and the standard algorithms for it are Burnside’s lemma with the group generated by the parent’s symmetry and the superlattice’s translations. The literature on it does not usually mention Burnside, and the literature on Burnside does not usually mention alloys.

Every configuration this count reaches is an ordered arrangement on a superlattice, and it is worth being clear about what the number is a number of. It is not a number of materials. Two arrangements in the same orbit are the same structure and will have the same energy for reasons of symmetry alone; two in different orbits are genuinely different structures and may still have the same energy, for reasons that have nothing to do with symmetry and that no count can see. What the number bounds is the size of the search — how many candidates a total-energy calculation would have to visit before it could claim to have looked at all of them — and that is the use it gets in practice.

Where it stops being computable, and what to do then #

The lemma turns an exponential problem into a linear one only in the number of arrangements. The group is still walked in full, and for a large block that group is large: on an n × n block a plane group of order k has k·n² operations, so the sum grows quadratically in n while the number of arrangements grows as 2^(n²).

That trade is the whole reason the lemma is used in practice. A six-by-six block has 6.9 × 10¹⁰ arrangements and a group of a few thousand operations; the enumeration is impossible and the sum is instant. What the sum does not give is a list — it counts the structures without producing one of them — and every enumeration algorithm in the alloy literature is about closing that gap, usually by walking canonical representatives and using the count as a check on having found them all.

That is the honest use of a count like this one: not as an answer, but as the number a slower enumeration has to reproduce.

What the sum looks like when the group is large #

The identity dominates the fixed-point sum, and how completely it dominates says which regime the count is in.

When the arrangements greatly outnumber the group, as at four-by-four with two species, the identity supplies 65,536 of a total of about 103,000 for p4m — nearly two thirds, with the remaining 127 operations sharing the rest. The count is then close to the naive division, corrected upwards by the symmetric arrangements.

When the group is comparable with the arrangements, which happens on small blocks or with few species, the corrections dominate and the naive division is badly wrong. On a two-by-two block with two species there are sixteen arrangements and p4m acts with thirty-two operations, so the division gives half an arrangement and the true count is six.

The crossover is worth knowing because it says when the lemma is needed. For a large block the answer is close to the division and the lemma is a refinement; for a small one the division is not even the right order of magnitude, and every structure enumeration a materials calculation runs is in the second regime, since the blocks that fit in a total-energy calculation are small.

The count as a check on an enumeration #

The most useful thing this number does is not to be an answer. It is to be a check on a slower calculation that produces a list.

A structure enumeration walks candidate arrangements, discards the ones equivalent to something already seen, and returns representatives. That is what an alloy study needs, since a count cannot be fed to a total-energy calculation and a list can. The walk is delicate: the test for “equivalent to something already seen” has to apply every operation of the group, and an operation left out means duplicates in the output while an operation invented means structures silently dropped.

Burnside’s number is what catches both. The enumeration must return exactly as many representatives as the sum predicts. Too many means duplicates; too few means something was dropped. Neither failure is visible in the output itself — a list of structures looks like a list of structures — and the count is available in milliseconds while the enumeration takes hours.

That is the same relationship this site keeps everywhere between a closed-form claim and a construction: the theorem gates the machinery that illustrates it, and the machinery is what a reader actually gets.

The check only works in exact arithmetic #

The lemma’s self-check is that the fixed-point sum is divisible by the order of the group, and it is a real check — a miscounted cycle structure almost always breaks it. It is also a check that quietly stops working the moment the numbers get large enough to matter.

The identity’s term is c to the power of the number of sites, and on the six-by-six block with two species that is 2³⁶, about 6.9 × 10¹⁰. That is still exact in a double-precision float, which holds integers up to 2⁵³. A seven-by-seven block is 2⁴⁹, still exact. An eight-by-eight block is 2⁶⁴ and is not, and neither is a three-dimensional block of side four with three species.

What happens then is the worst available failure. The sum is computed as a float, the division by the group order returns something within rounding of an integer, and a divisibility test written as is the remainder zero either passes on a wrong number or fails on a right one depending on which way the last bits fell. Neither outcome says anything about the cycle structures the check was meant to police.

So the arithmetic here is exact integer arithmetic throughout, and the divisibility is tested on integers. That is not a precaution; it is what makes the check a check. The same requirement runs through every count on this site that has a closed form to compare against — the sublattice counts are integer sums for the same reason, and a colouring count inherits it, since a larger group only makes the identity’s term larger.

The general shape is worth naming, because it is not about this lemma. A self-check that consists of an integer identity is only as strong as the arithmetic it is evaluated in, and floating point degrades it silently — the assertion still runs, still passes, and no longer tests anything. That is a worse position than having no check at all, because the passing check is what stops anybody looking.

Where the ladder goes next #

This rung establishes the count for a block of cells and two species. Three directions lead off it.

Weights. Pólya’s version tracks how many sites carry each species, so the count splits by composition — how many structures have exactly five A atoms among sixteen sites — which is what an alloy enumeration actually wants, since composition is fixed by the experiment.

Three dimensions. The same lemma with a space group and a three-dimensional block, where the group is the point group times n³ translations and the arrangements are 2^(n³). Nothing in the argument changes and everything in the arithmetic gets larger.

Colour groups. Counting arrangements up to a permutation of the species is the same lemma applied to a larger group, and the classification of those larger groups is the counterchange story — where the answer is not a count of arrangements but a count of groups, and this site is back on its usual ground.