Every superstructure counted once

Counting what a group cannot tell apart put two species on the sixteen sites of a four-by-four cell and asked how many essentially different arrangements there are. There are 65,536 colourings and 805 arrangements up to the symmetry of the square lattice acting on that cell, and the count that gets there is Burnside’s average of fixed points. That number answers a question about a cell. It is often read as answering a question about structures, how many ordered alloys with sixteen atoms in the repeat, and it does not.

The mismatch has two sides. Some of the 805 arrangements repeat in a smaller cell: a checkerboard drawn on the four-by-four cell is one of them, and it is a structure with two atoms in its cell, drawn eight times. And a structure with sixteen atoms in its primitive cell need not have a square four-by-four cell at all. It might repeat every sixteen steps along one direction, or on a sheared cell of the same area, and none of those arrangements fit on the four-by-four torus. Counting structures means counting over every shape of cell at once, keeping each arrangement only on its own true cell. This essay does that for the square lattice. The first thing the count does is reproduce the 805 from a completely different direction, as a sum over the cells that fit inside four-by-four.

Cells first, then colourings #

A structure with $n$ atoms in its primitive cell has, as its lattice of translations, a sublattice of the square lattice of index $n$. How many ways there are to thin a lattice counted those: every such sublattice has a unique basis in Hermite normal form, $(a, 0)$ and $(b, c)$ with $ac = n$ and $0 \le b < a$, and there are $\sigma(n)$ of them, the sum of the divisors of $n$. Two sublattices related by a rotation or reflection of the square lattice carry the same structures turned, so only one sublattice from each such set needs to be kept.

For $n = 8$ there are fifteen sublattices, which the lattice’s eight rotations and reflections sort into seven sets. They range from a strip one site wide and eight long to a two-by-four rectangle, and several sheared cells between. Each kept sublattice $L$ has a stabiliser, the rotations and reflections of the square lattice that carry $L$ onto itself. A strip has two of them, the square two-by-two cell’s relatives more.

A structure on the cell $L$ is a colouring of its $n$ sites by the two species. Two colourings are the same structure when a translation of the parent lattice, which permutes the cell’s sites, or an operation of $L$’s stabiliser maps one onto the other. And a colouring is kept only if its true period is $L$: if some translation of the parent lattice that is not in $L$ leaves it unchanged, the colouring repeats sooner, and it belongs to a larger lattice at a smaller $n$, where it is counted once already. Discarding those superperiodic colourings is the step a fixed-cell count leaves out, and it is what makes each structure appear exactly once in the whole census.

The orbits are counted twice, by two methods that share nothing but the list of colourings. One reduces every colouring to a canonical form, the smallest of its images under the group, and counts distinct forms. The other averages, over the group, the number of kept colourings each element leaves unchanged, which is Burnside’s lemma. For every sublattice of every index up to twelve the two numbers agree, which is a check on the group as much as on the counting, since a wrongly built group could give a Burnside average that was not even a whole number.

Discarding is an inversion #

The discard step has a tidy description that shows why it cannot be skipped. Colour the $n$ cosets of a sublattice $L$ in every way, $2^n$ colourings, and each colouring has some true period lattice $L'$ that contains $L$. So the colourings of $L$ are the disjoint union, over every lattice $L'$ between $L$ and the parent, of the colourings whose exact period is $L'$. Counting all colourings is easy, $2^n$, and counting the exact ones is what the census needs. The relation between the two is a sum over the lattices containing $L$, and recovering the exact counts from the easy ones is a Möbius inversion over those lattices, the same inversion that turns the count of all necklaces into the count of primitive ones.

The census does the inversion by brute force, testing each colouring against every translation of the parent that is not in $L$ and discarding it if any fixes it. The inversion formula would do it by arithmetic. Either way, the quantity removed is not small at small $n$. At four sites, the 16 colourings of each cell shape shrink to 12 exact ones on the strips and sheared cells and to 8 on the two-by-two square, and at two sites to 2 of 4. Skipping the step is what makes a fixed-cell count include the checkerboard among its sixteen-atom arrangements, and every structure with a smaller cell along with it.

Eleven with four atoms #

At four atoms the whole list fits on a page. There are seven sublattices of index four, which fall into four sets: the one-by-four strip, the two-by-two square, the two-by-two cell with a sheared edge, and the four-by-one cell sheared by one. The census finds 3, 2, 3 and 3 structures on them, eleven in all. On the strip they are the three ways to colour four sites along a line that do not repeat every two or every one: one site of one species and three of the other, two adjacent sites of each, and three and one again seen from the other species. On the square cell they are the two arrangements with one site of the four different from the other three, one for each species. Two of each species cannot be arranged on that cell without repeating sooner: side by side they make a stripe and across the diagonal a checkerboard, both with two-site cells, and both are absent here for that reason.

The drawing is the check a reader can make by eye. Every patch repeats with the cell stated above it and with no smaller one, and no two patches are the same structure turned or shifted. Eleven is not a count of anything a four-by-four cell could show. A two-by-two torus holds the arrangements with lattices containing twice the parent. Those number 2 at one site, 2 at two and 2 on the two-by-two cell, six in all, and the other nine four-atom structures need cells of other shapes.

The 805, decomposed #

The fixed-cell count and the structure count describe the same objects from two ends, and the relation between them can be stated exactly. An arrangement on the four-by-four torus is a structure whose lattice contains four times the parent lattice. Two arrangements are the same up to the torus’s symmetry exactly when they are the same structure. So the 805 must be the sum, over every kept sublattice that contains $4\mathbb{Z}^2$, of the structures whose exact period is that sublattice.

It is: two pure crystals with a one-site cell, one stripe and one checkerboard with two, eleven arrangements with a four-site cell that fits, thirty-four with eight sites on the two eight-site cells that fit, and 756 genuine sixteen-site structures on the square four-by-four cell. They add to 805. The two computations share nothing but the definition of a colouring. One takes orbits of 65,536 colourings under the symmetry of a torus. The other enumerates sublattices, discards superperiodic colourings and takes orbits cell by cell. That they agree to the last structure is the strongest check the census has.

The decomposition also shows how misleading the fixed-cell number is as a count of sixteen-atom structures, in both directions. Forty-nine of the 805 are smaller structures drawn several times over. And the census finds 22,413 structures with exactly sixteen atoms in their primitive cell, over all twelve shapes of sixteen-site cell. The four-by-four square holds 756 of them, about one in thirty. A search for ordered alloys with sixteen atoms in the cell that enumerates the four-by-four cell sees one structure in thirty of the ones it is looking for. The square cell is also the poorest of the twelve shapes. The twelve sixteen-site shapes carry 1,868 structures each on average, and the four-by-four square, whose stabiliser is the whole of the square lattice’s point group, carries 756 of them, less than half the average. That is the pattern of the next section but one, seen at a larger size: the most symmetric cell shape identifies the most arrangements with one another, so it holds the fewest distinct structures, and a census confined to it undercounts by more than its share of the shapes. The spread is wide. Seven of the twelve shapes carry exactly 2,220 structures each, one carries 2,217, three carry about thirteen hundred, and the square carries 756. The shapes cluster by how much symmetry their cell has, and within each cluster the counts are equal or nearly so, which is the prime-size pattern of the next sections appearing, approximately, at a size with many divisors.

Growth, and how far the naive estimate falls short #

The picture at the head of this essay is the census up to twelve atoms: 2, 2, 4, 11, 16, 40, 48, 148, 188, 452, 496 and 2,012. The count at one site is the two pure crystals. At two there is the stripe and the checkerboard, and at three there are four: one site of three different from the rest, in either species, on each of the two shapes of three-site cell. The growth is roughly exponential, as it must be with $2^n$ colourings per cell, but it is uneven. Sizes with many divisors, such as eight and twelve, have many shapes of cell and jump. Prime sizes have only a few: seven has three shapes and forty-eight structures, and eleven has four shapes and 496.

A natural estimate of the count divides the total number of colourings, $\sigma(n)\,2^n$ over all sublattices, by the size of the group that identifies them: $n$ translations times eight rotations and reflections. It would be exact if every structure’s orbit had the full size of the group. The true count is always larger, eight times larger at one site, about three times at four, and 1.7 times at twelve. The reason is the one the fixed-cell count found: an arrangement with symmetry of its own has a shorter orbit, and the naive division gives it only a fraction of a count where it deserves a whole one. The superperiodic colourings pull the other way, since the naive estimate counts them and the census discards them, but they are the smaller effect at every size. Symmetric arrangements grow rarer as cells grow, so the ratio falls towards one. It is still well above one at twelve sites, which is why an estimate from the naive division is a poor guide to the size of a real enumeration.

Symmetric cells carry fewer structures #

Within one size the counts differ from cell to cell, and the pattern is the stabiliser. At eight sites, five of the seven cell shapes carry 24 structures, or close to it, and they are the strips and sheared cells whose stabiliser has two or four operations. The two-by-four rectangle carries 21. The cell with basis $(4, 0)$ and $(2, 2)$, which is a square rotated by forty-five degrees and has all eight operations of the square lattice in its stabiliser, carries 13. A cell with more symmetry of its own has more ways to identify two colourings as one structure, since each of its operations is an extra way of turning one arrangement into another. The most symmetric cell shape therefore holds the fewest distinct structures, although it holds exactly as many colourings as every other shape of the same area.

At a prime size every cell carries the same number #

At seven sites the three shapes of cell carry 16 structures each, and at eleven the four shapes carry 124 each. The stabilisers differ, four operations for some shapes and two for others, and the counts do not. The reason is that when $n$ is prime the $n$ sites of a cell, as a group under the parent’s translations, form a cyclic group of prime order, and any rotation or reflection of the square lattice that keeps the cell acts on that cyclic group either as the identity or as reversal. So on every shape the group acting on the colourings is the same: $n$ cyclic shifts and a reversal. The structures are the arrangements of two colours round a cycle of $n$ beads up to rotation and reflection, the binary bracelets, less the two with one colour only. There are 18 bracelets of seven beads and 126 of eleven, which give 16 and 124. At a prime number of atoms, the shape of the cell stops mattering, and the count of structures is a count from combinatorics that knows nothing about lattices.

What the census has to refuse #

The refused reading is the one this essay began with. The 805 is a correct count of arrangements of a cell. As a count of sixteen-atom structures it is wrong in both directions: forty-nine of its arrangements are smaller structures, and more than twenty-one thousand sixteen-atom structures are not among it. The third test checks the step that makes the census complete: every one of the $\sigma(n)$ sublattices must lie in exactly one of the kept sets, so that no cell shape is counted twice and none is missed.

A convention sits under every number and should be named. The two species are labelled: a structure and the same structure with the species exchanged are counted as two, unless an operation of the lattice already relates them. Swapping the species does not halve the count computed what treating the species as interchangeable does to a fixed-cell count, and the same correction applies cell by cell here. The pure crystals are counted at one site. And the census is of the square lattice with its full symmetry; a rectangular parent with less symmetry would identify fewer cells and fewer colourings, and would have more structures at every size.

Still open: other lattices, more species, and the superlattice reflections #

The method runs unchanged on any two-dimensional lattice and any number of species: the Hermite normal forms, the parent’s point group, and a colouring with $k$ colours in place of two. On the hexagonal lattice, whose point group has twelve operations, the counts would be smaller at every size. With three species they would be far larger, and an alloy designer’s real question usually has three. In three dimensions the sublattices are counted by a longer divisor sum and the colourings by the same census. The published enumerations for the face-centred cubic lattice, which the alloy literature uses, are exactly this computation in one more dimension, and matching them would be a direct test.

There is also the question that connects the census back to diffraction. Each structure found here has superlattice reflections that the reflections a superlattice adds computes from its cell and colouring, and two structures with the same cell can have different sets of them. How many of the 2,012 twelve-site structures could be told apart by the positions of their superlattice reflections alone, before any intensities are measured, is a count the census makes possible and has not made.