Crystallography & Symmetry
patterns derived from their groups
Concept

Decidability — where it appears

Whether a question can be settled by a procedure that always terminates, which for a pattern's symmetry is integer arithmetic in a lattice basis. A pattern either has a symmetry or it does not, and there is no tolerance to choose and no residual to interpret.

Named by 17 essays across 7 fields — each of them below, with the objects they name alongside it.

The round trip, on Pnma. 8 operations were generated from the standard generators of Pnma; the orbit of three points in general position was formed, the group was discarded, and 8 operations were rediscovered from the 24 points alone. The two sets are identical, which is what the figure asserts.

Forgetting a group in three dimensions

For three phases this site said its machinery was two-dimensional and decided nothing about a space group. That was true, and it was a limit rather than a principle — nothing in the decidability argument mentions the number two.

space-groups · Space groups p4g in 4 letters and 8 relations. The presentation of p4g, derived from the group's own operations. The two translations commute; each conjugation relation is read off a column of a matrix; and the point group's relations are corrected by the translation they actually come back as, which is what makes this group an extension rather than a semidirect product. Every relator is evaluated where the group lives and must be the identity, and coset enumeration on the letters alone returns 8, which is the order of the point group.

A group in four letters

Every other essay here describes a symmetry group by what it does to the plane. There is a second description — a handful of letters and the words in them that are required to equal nothing — and it can be counted with no plane anywhere in the computation.

operations · Presentations Every group decided by a window of radius 1. For each of the seventeen, the radius at which a round window on the pattern admits exactly the group's own operations and no others — with the numbers it admits at each smaller radius beside it. Two opposite failures are visible. Most groups under-report at small radii, because an operation carrying points out of the window cannot be tested at all; cm over-reports, admitting operations the pattern does not have. The groups that take longest to settle are the ones distinguished by a glide, which moves a point half a cell before anything can be compared.

How much pattern is enough

Every claim here about a pattern's group is a claim about an infinite pattern. A reader sees a patch. Measuring what a finite window can decide gives a number — about one cell's radius — and two opposite ways of being wrong on the way there.

classification · Seventeen The ball of radius 5 in p6. Every element of p6 reachable in at most 5 multiplications by a generator or its inverse, plotted at its translation part — so each dot is a lattice position and its size says how few steps reach it. The picture is the word metric's unit ball scaled up, and its shape is what fixes the growth: a diamond where the group supplies two short translations, and a hexagon where it supplies three. Every dot here required the word problem to be solved, because the search has to know when two products are the same element.

Telling two words apart

There are finitely presented groups in which no algorithm can decide whether two products of the generators are the same element. The seventeen are not among them, and the procedure that settles it is short enough to state in a sentence — which then makes it possible to measure how fast each group grows.

operations · Presentations In the plane, the lengths do name the lattice. Every reduced binary form with coefficients up to 20 — 1750 lattices — with its theta series computed to 120 terms. No two of them agree. That is Schiemann's theorem for binary forms, which says the theta series determines the lattice in two dimensions and in three, confirmed here as far as the search reaches rather than proved. The closest pair is worth the space: two lattices whose shortest vectors both have squared length twenty agree for 38 terms — because neither has any vector before then — and part at the next one.

The lengths do not name the lattice

Seventeen hundred plane lattices, every one with a theta series shared with no other — the lengths determine the lattice, and an exhaustive search says so. In sixteen dimensions two different lattices have identical counts at every distance, and the example is sixty years old.

lattices · Lengths Every way regular polygons can fill a turn. The seventeen multisets of regular polygons whose interior angles add to exactly 360°, listed with the sum that qualifies each of them. They are found by a search over sizes from three upward: the largest polygon that can appear is the forty-two-gon, which needs a triangle and a heptagon beside it, and the search stops there because the smallest interior angle is a third of a turn so at most six polygons can meet. Nothing here is a table looked up — the list is the output of the search, and every count on the page downstream of it is counted from this one.

Twenty-one vertices, eleven tilings

Regular polygons meeting at a point must fill exactly a turn, which is a Diophantine equation with seventeen answers and twenty-one cyclic arrangements. Ten of the twenty-one tile nothing at all — and the argument that kills them counts places round a polygon rather than measuring anything.

classification · Tilings Modulo 3 injective on all thirteen, modulo 2 on 5. Minkowski's lemma says the kernel of reduction modulo an integer of at least three is torsion-free, so a finite group of integer matrices is carried faithfully into a finite group of matrices over ℤ/3 — which is why the classification is finite, before any bound is computed. The middle column checks it on every finite subgroup of GL(2,ℤ) there is: thirteen classes, no collapses. The right column is the case the lemma has to exclude. Modulo 2, minus the identity is the identity, and 8 classes lose operations.

Reduction modulo three

A finite group of integer matrices survives being reduced modulo three: no two of its operations collide. That single fact proves the classification finite without computing any bound — and modulo two it is false, refuted by the inversion centre.

restriction · Finiteness The Fibonacci chain: p(n) = n + 1. The number of distinct windows of each length in the Fibonacci chain, measured by sliding a window along 46,368 tiles. Every count is checked against the same count on half the chain, and only lengths where the two agree are drawn — a factor count on a finite word is otherwise a lower bound wearing the clothes of an answer.

n plus one, and no fewer

Slide a window along a chain and count what it can show. A periodic chain runs out of new views; an aperiodic one never does; and the fewest an aperiodic chain can manage is one more than the window's length — which is exactly what the Fibonacci chain manages.

aperiodic · Complexity P2₁/c from 27 marks. The marks of P2₁/c's plan, counted by kind, and what they rebuild to. Each mark is reduced to what a reader can see and handed to a closure with the matrices withheld: an axis gives its direction, its position and how far one turn advances along it; a plane gives its normal, its position and its slide. The lattice supplies the candidate matrices, the closure supplies the rest, and what comes back is the group — 4 operations against 4, with nothing missing and nothing extra.

The plan contains the group

A space-group diagram has always been treated here as a picture of the group. It is more than that: hand back the marks alone — no matrices, no operations, not even the centring — and the group comes out exactly, forty-five times out of forty-five.

space-groups · Space groups 8 tiles over 5 colours. Wang tiles: unit squares with a colour on each edge, which may be laid side by side only where the touching edges agree, and which may never be turned or reflected. That last restriction is what makes them a computational object rather than a jigsaw — an edge colour is a symbol passed from one tile to its neighbour, and turning a tile would let a symbol change direction. The set here was generated from a stated seed.

Nothing decides whether a set of tiles tiles the plane

This collection rests on decidability — generate a pattern, forget the group, rediscover it, compare. One question in the same subject has no procedure at all: given a finite set of tiles, whether they cover the plane cannot be decided by any algorithm whatever. What can be done is two half-searches, and measuring what they leave behind.

classification · Decidability Y-pentomino: A B C D E F, with 6 arcs. The boundary of the Y-pentomino cut into six arcs. A runs from one corner to another and D is the same arc traversed backwards, so D is a translate of A and the translation is (3, 1) cells. Each of B, C, E and F is carried onto itself by the half turn about its own midpoint, and those midpoints are the four marked dots — That is Conway's criterion, and a shape meeting it tiles the plane by translations and half turns.

A tiling of the whole plane, decided on one tile's edge

Whether a shape tiles the plane is a question about an infinite object, and there is no procedure that answers it. There is a procedure that answers it *sometimes*, and it reads nothing but the shape's own boundary — a closed path of a few dozen steps, cut into six arcs. When the cut exists the tiling exists, and the cut names the group that makes it.

classification · Isohedral 7 cells explain the lines; one of them is right. A line list from a face-centred cubic cell of 5.64 Å, with a realistic error added, handed to a sweep over every cubic cell between 2 and 12 Å in all three centrings. 7 distinct cells explain every line within the tolerance, and each is a genuine solution rather than a numerical accident. The true cell comes top by de Wolff's figure of merit — the last Q over twice the mean discrepancy times the number of lines the candidate says should have been visible — which punishes a candidate for predicting lines nobody saw. That is the whole of what makes indexing decidable in practice: not the arithmetic, which has many answers, but a criterion for preferring one.

Indexing a powder pattern

A powder pattern is a list of numbers and a cell is six. Getting the second from the first is the first step of every powder study and the one that fails — because the arithmetic has many answers, and choosing between them is a ranking rather than a deduction.

applied · Indexing heesch-two: surrounded 2 times. A shape that tiles nothing, with the rings of copies it does accept: the seed in the first colour and 2 coronas of 7 and 16 copies round it. The search that built this finished, so the shape's Heesch number inside this box is exactly 2, and it cost 3,097 placements. Every cell touching a tile of one ring, corners included, is covered by the next.

Surrounded twice over, and covering nothing

A shape that tiles the plane can be surrounded by copies of itself for ever. A shape that tiles nothing cannot be surrounded for ever — but it can be surrounded once, and sometimes twice, and the number of times is a measurement of how much local success a global impossibility permits.

classification · Decidability The whole space of plane lattices, and its corner. Every plane lattice appears exactly once in this picture. Scaling changes no density, so the leading coefficient is fixed at one; reduction then confines the other two to 0 ≤ b ≤ 1 ≤ c, and every lattice has exactly one reduced form. The curves are the levels of constant density, which are parabolas — a density d needs 4c − b² to equal (π/2d)². They crowd toward the corner b = c = 1, which is the hexagonal lattice at π/√12 ≈ 0.9069; the square lattice sits on the left edge at π/4 ≈ 0.7854. The picture is a search over a region rather than over a list, which is what makes the answer a decision: there is nowhere else for a lattice to be.

The densest lattice in the plane

Which arrangement of equal discs covers the most floor is a question about infinitely many lattices, and reduction turns it into a question about a two-parameter region with a corner. The answer is at the corner, and the argument finishes.

applied · Packing The hat: eight kites, thirteen sides. The shape a search over the eight-kite polykites returns, drawn on the kite grid it lives in — the Laves tiling [3.4.6.4], in which every hexagon is cut into six kites. The eight kites of the shape are tinted and its outline is drawn heavy. Thirteen sides result, of two lengths only: a half and root three over two, in units of the hexagon's circumradius, with one side of twice the shorter length where two kite edges lie in a line. Its interior angles are 90, 120, 240 and 270 degrees. Nothing about the shape was chosen: it is the one octakite that clears every filter in the search.

One tile, and no period

Every aperiodic pattern in this collection so far needs two shapes. A search over the eight-hundred-and-seventy-three ways of gluing eight kites together, filtered by nothing but whether a shape tiles and whether it repeats, returns exactly one — and it is the shape announced in 2023.

aperiodic · Monotile 656 sets, every one decided. Every set of one, two, three and four tiles over two colours — sixteen tiles exist in all, so these are complete lists rather than samples — reduced by relabelling the two colour alphabets, and each set decided by the two half-searches. The last column is the one that matters: it is empty. At these sizes there is no room for a set that tiles the plane and admits no periodic tiling, which is the residue undecidability lives in. The smallest aperiodic set is known to have eleven tiles and four colours.

How much room a hard question needs

No algorithm decides whether a set of tiles covers the plane. Every set of four or fewer tiles over two colours is nevertheless decided here, exhaustively, in under a second — because the sets that defeat the two half-searches have nowhere small to live.

classification · Decidability p2's symmetries, sorted into classes by the group itself. A pattern with the symmetry of p2 over 2 by 2 cells, with its rotation centres and mirror lines marked in the International Tables' shapes and coloured by conjugacy class in the infinite group: two marks share a colour exactly when some operation of the group carries one element onto the other. Where rotations of several orders share a centre, the mark is the highest order's and so is its colour. Glides are not drawn. Classes counted: half-turns: 1 in the quotient, 4 in the group.

Two mirrors a coset cannot tell apart

Taken modulo its lattice a wallpaper group is finite, and its conjugacy classes are easy to list. But a coset holds every mirror of one direction at once, and the group itself keeps apart mirrors the list merges: pm has two classes of mirror, p2 four classes of half-turn, p3 six classes of rotation. Deciding which is which is Dehn's conjugacy problem, and for these groups it comes down to whether one vector lies in one lattice.

operations · What symmetry is

Named alongside it

The objects these essays reach for when they reach for this one.

AperiodicityEnumerationLocal rulesTiling by a groupRound tripAccidental symmetryAperiodic tile setBasis reductionCase analysisCertificateForcingGlide reflection

All concepts