Every colour count at once

Sixty-five thousand ways of putting two species on sixteen sites; eight hundred and five structures. The difference between those numbers is not a division, and Burnside’s lemma is the correction: the number of distinct arrangements is the average number an operation leaves alone, not the total divided by the size of the group.

It is a good answer to one question. It is also an answer that has to be computed again from scratch for three species, and again for four, and again for the alloy with a vacancy as a third species on the same sites. Each is a separate sum over sixty-five thousand or a million or sixteen million arrangements’ worth of fixed-point counting.

There is a version of the same average that answers all of them at once, and the change is small enough to state in a sentence: stop counting fixed arrangements and start counting cycles.

Why the sum has to be a sum at all #

It is worth a paragraph on why the division fails, because the reason is the same one that runs through this whole field and it has a name here.

The orbit of an arrangement is the set of arrangements the group carries it to, and two arrangements are the same structure exactly when they share an orbit. If every orbit had exactly |G| members then the count would be the total divided by |G| and there would be nothing to discuss. But an arrangement that some operation leaves alone has a stabiliser, and orbit-stabiliser says its orbit is correspondingly shorter — the chequerboard on a four-by-four block is carried onto itself by half of p4m’s operations, so its orbit has sixty-four members rather than a hundred and twenty-eight, and dividing counts it as half a structure.

That is exactly the arithmetic Wyckoff positions are about, applied to arrangements instead of to points. A special position is a point with a stabiliser; a symmetric arrangement is a colouring with one; and in both cases the correction is not a small refinement but the difference between an integer and a fraction.

An operation fixes an arrangement along its cycles #

An operation of the group permutes the sites. Sixteen sites, some permutation of them, and the permutation falls into cycles — a four-fold rotation on a four-by-four block sends a site round a cycle of four and comes back, and the whole permutation is a collection of such cycles.

An arrangement survives that operation exactly when it is constant along every cycle. There is nothing else to check: if two sites are in the same cycle they must carry the same species, and if they are in different cycles they need not.

So the number of arrangements an operation fixes is k raised to its number of cycles, where k is the number of species available. The exponent is a property of the operation and the base is the palette, which is the entire trick: separate the two and the palette becomes a variable.

That table is the cycle index. Seven terms rather than a hundred and twenty-eight, because operations with the same cycle type are interchangeable for this purpose. The identity makes sixteen cycles of one; a four-fold rotation about a cell corner makes four cycles of four; the operations of order eight make two cycles of eight.

A cycle is a fact about the operation and the block together. The same four-fold rotation makes four cycles of four on a four-by-four block and a quite different pattern of cycles on a six-by-six one, where the block’s own size is not a multiple of the operation’s order in the same way. That is why the polynomial is indexed by a block as well as by a group, and why enlarging the block is not a matter of scaling the answer.

There is also a constraint on which blocks a group may be asked about at all, and this collection’s machinery enforces it rather than assuming it. A group whose operations carry translations of a third of a cell — p3, p6 and their relatives — cannot act on a block whose side is not a multiple of three, because a third of a cell is not a whole number of sites. Asked anyway, the machinery says which multiple would work instead of quietly rounding.

The answer becomes a polynomial #

Averaging k^(cycles) over the group gives

$$N(k) \;=\; \frac{1}{|G|}\sum_{g} k^{\,c(g)},$$

which is a polynomial in k, of degree equal to the number of sites. Evaluate it at 2 and out comes 805. Evaluate it at 3 and out comes 359,955, at no additional cost, because the polynomial was written down once.

Two things about that polynomial are worth pausing over.

Its coefficients are fractions and its values are whole numbers. Every coefficient has the group’s order underneath it — p4m’s leading term is k¹⁶/128 — and yet N(k) is an integer at every integer k, because it is counting things. That is the divisibility which makes Burnside’s lemma self-checking, generalised: it now has to hold at every k rather than at one, which is a great many more chances for an error in the group to show itself as a fraction where a count should be.

Its leading term is the naive division. k¹⁶/|G| is the answer somebody gets by dividing all arrangements by all operations, and every other term is a correction for the arrangements that some operation fixes. The corrections matter most when the palette is small.

A symmetric arrangement is a rare arrangement, and rarer the more colours there are. With two species a chequerboard is easy to draw by accident; with nine, an arrangement that survives a four-fold rotation has to repeat its choices in fours, and almost nothing does. That is the whole shape of the correction, and it is why chemistry’s own rule of thumb — divide by the symmetry number — works better for messy compositions than for tidy ones.

The refinement that is actually wanted #

The count so far answers how many structures are there, which is a question nobody asks. What a phase diagram is indexed by is composition, and what an enumeration of candidate structures needs is the count at a stated stoichiometry: how many distinct ways are there to put four atoms of one kind and twelve of another on these sixteen sites?

The same average answers it, with one substitution. Instead of counting each cycle as a factor of k, give each cycle of length ℓ the factor

$$x^{\ell} + y^{\ell},$$

which says that the cycle is either all of the first species — contributing ℓ sites of it — or all of the second. Multiply over the cycles, average over the group, and the result is a polynomial in two variables whose coefficient of xᵐ is the number of distinct structures with exactly m sites of the first species.

That is Pólya’s pattern inventory, and it is the version of the count with an application. The distribution has the shape a search actually faces: the extremes are trivial and the middle is where the work is. One structure at AB₀, five at A₂B₁₄, thirty-three at A₄B₁₂, and a hundred and fifty-three at AB.

The chart is symmetric, and the symmetry is not a fact about the group. Swapping the two species is a relabelling of the answer rather than a new structure, so the count at m and at 16 − m must agree — and the fact that it does is a check on the arithmetic, since the two coefficients come from different parts of the same product.

Each bar of that chart is a population of orderings on a sublattice, and it is worth keeping in view what one member of a population looks like: a decoration of the sites with two species, which either shows up in a diffraction pattern as a set of extra reflections or does not. Whether it does is a separate question with an answer of its own; how many of them there are at a stated composition is this one, and the two are independent in both directions. An ordering can be numerous and invisible, and it can be unique and loud.

At most j colours, and exactly j #

There is one more distinction the polynomial makes and the number does not.

N(3) counts every arrangement drawn from a palette of three species — including the ones that use only two of them, and the three that use only one. A chemist offered three elements and asked how many ternary structures there are usually means the ones with all three present.

Subtracting one from the other is inclusion and exclusion: an arrangement leaving one colour unused is an arrangement from a smaller palette, and the alternating binomial sum removes them. Both numbers are legitimate and they answer different questions. A palette is what a synthesis offers; a species count is what a formula reports. Running them together is the same category error as reading a permission as a prediction.

The two variables can be more than two. Nothing in the substitution needs the palette to have two members: three species give each cycle the factor x^ℓ + y^ℓ + z^ℓ, and the coefficients of the product are counts at each ternary composition. The number of coefficients grows as the number of compositions does, which is the reason the two-species case is the one printed — it fits on a line — rather than the reason it is the one computed.

And the substitution explains the polynomial rather than merely refining it. Setting x = y = 1 in the pattern inventory turns every factor x^ℓ + y^ℓ into 2 and recovers N(2); setting all k variables to one recovers N(k). The counting polynomial is the inventory with the compositions forgotten, which is the usual relationship between a generating function and the number it generates, arrived at here from the direction of the group.

Counting up to a permutation of the species as well #

The essay separates this count from the two-colour groups on the ground that one admits the colour swap as an operation and the other does not. There is a single machine that does both, and having it makes the boundary between them a choice rather than a difference in kind.

The pattern inventory averages over the group acting on sites. Averaging as well over a group acting on species — a second cycle index, in the second set of variables — counts arrangements up to both actions at once. That is de Bruijn’s extension of Pólya’s theorem, and it is the same average with one more sum in it.

The two extremes are the two computations the essay has been keeping apart. Take the species group to be trivial and the answer is the count on this page: an arrangement of A and B is different from the arrangement with the labels exchanged. Take it to be the full symmetric group on the species and arrangements differing only by a relabelling are one, which is the count a classification of coloured patterns is after.

And the intermediate cases are real. In a ternary alloy where two of the three species are chemically similar and the third is not, the meaningful group on the species is the one exchanging the first two — neither trivial nor full — and the count that answers the chemistry is neither of the two the literature usually reports.

That is the useful thing about having the general machine. The question which arrangements are the same has an answer that depends on what is being asked, and the answer is supplied as a group rather than as a convention. Both counts on this page are one computation with a different second argument, and the difference between them was never about colours.

The count gives no representatives #

There is a limitation this page shares with every essay in this anchor, and it is worth stating plainly because the numbers are so satisfying.

The average produces a count and produces nothing to look at. Knowing that a four-by-four block under p4m admits eight hundred and five structures, of which some number have exactly six atoms of one species, says nothing about what any of them is — and a materials calculation needs the arrangements themselves, one at a time, to compute anything with.

Producing them is a different algorithm and a harder one. The naive route is to enumerate all k to the power of the site count arrangements and discard the ones equivalent to something already seen, which costs the full exponential and is exactly what the counting was supposed to avoid. The efficient routes — orderly generation, canonical augmentation — build arrangements incrementally and reject any that is not the canonical member of its own orbit, so each orbit is produced once and nothing is stored.

What the count is for, in that setting, is a check. An enumeration that returns a different number of representatives than the average predicts has either produced a duplicate or missed an orbit, and the average is the only thing available that knows the right answer without doing the enumeration. That is the same relationship this collection keeps everywhere between a closed form and a construction, and it is the reason both are worth having.

Where the count sits among the site’s other counts #

Three numbers describe an ordered alloy on a superlattice and this collection now has all three, computed by machinery that shares nothing.

How many sublattices of index n counts the lattices available, which in the plane is the sum of the divisors of n. The reflections a superlattice adds says what an ordering does to a diffraction pattern — exactly n − 1 new reflections per parent cell, with an intensity that is a difference rather than a sum. And the polynomial above counts the decorations of one such lattice, which is the only one of the three that grows exponentially.

The distinction between this count and the two-colour groups is worth making explicitly, because both involve colours and a group and they are not the same computation. A colour group is a symmetry — an operation that permutes the colours as it moves the pattern, so that the coloured pattern is invariant. The count here is of objects, with the colours carried along passively and no operation permuting them.

The classification those groups produce is a classification of patterns, and the count on this page is a count of objects. Forty-six two-colour groups in the plane is a statement about which symmetries a coloured pattern can have; eight hundred and five structures on a four-by-four block is a statement about how many decorations of a set of sites there are. The two questions share almost all of their words — colour, group, orbit, pattern — and share none of their arithmetic, and the surest way to keep them apart is to notice which object is being counted rather than which words are being used.

What the polynomial does not know #

It counts arrangements, not structures anybody can make. Every one of the eight hundred and five is a distinct decoration of the sites and most of them are chemically absurd — species that do not tolerate one another as neighbours, compositions no phase adopts. The count is the size of a search space and not a prediction about its contents, which is the same disclaimer every symmetry permission on this site carries.

It counts colourings of sites, not of a pattern. The sites here are a block of cells with one position each, which is the model an alloy calculation uses. A real structure has several distinct positions per cell, each with its own site symmetry, and the sites are then not interchangeable — an operation permutes them within orbits and never across. The cycle index handles that without modification, since it never assumed the sites were alike; what changes is which permutations there are.

It counts on a fixed block. The four-by-four block is a choice, and the answer depends on it: a bigger block admits every ordering the smaller one did and more. What the group supplies is which arrangements on that block are the same arrangement, and the block itself comes from somewhere else — usually from the largest superlattice a calculation can afford.

It says nothing about which of them are stable. The distribution above has its maximum at the equal composition because there are more ways to arrange equal numbers, and that is a statement about combinatorics rather than about energy. Which of the hundred and fifty-three the material adopts is decided by something this collection does not compute and does not claim to; what the count supplies is the list that decision has to be made over.

And it is blind to the thing an experiment measures. Two of these eight hundred and five arrangements can have identical diffraction patterns, for reasons that have nothing to do with the group: homometry is a property of the vector sets and not of the symmetry, and the count above cannot see it. Counting distinct structures and counting distinguishable structures are different problems, and only the first one has a polynomial.

What the refinement buys, in the end, is a change in what the answer is for. A single number — eight hundred and five — is a fact to be quoted. A polynomial is a function to be evaluated, at whatever palette the chemistry offers, and its coefficients sorted by composition are a work plan: this many candidates at AB, this many at A₃B, and the extremes free. That is the difference a structure search actually cares about, and it cost one substitution in a sum that was already being computed.