A structure with the distances thrown away

Every pattern this collection has drawn so far has been a set of points. A motif, an orbit, a lattice of copies — and the symmetry of a point set is decided by asking which motions of the plane carry it onto itself. That is a question about geometry. It needs coordinates, a basis and a metric, and the answer changes the moment a point moves.

Underneath the points there is a coarser object, and most of modern structural chemistry is written in terms of it. Keep which atoms are bonded to which; throw away where they are. What is left has no lengths and no angles. It is a graph — infinite, because a crystal is infinite, and periodic, because a crystal is.

The remarkable thing is not that the object exists. It is how much survives the loss.

Those nine numbers are worth reading out once, because everything below is arithmetic on numbers of that kind. The honeycomb’s quotient has two vertices, call them 0 and 1, and three edges between them, carrying the voltages (0, 0), (0, −1) and (−1, −1). The first says that vertex 0 of a cell is joined to vertex 1 of the same cell. The second says it is also joined to vertex 1 of the cell one step back along the second translation, and the third to vertex 1 of the cell one step back along both. Three edges leave every vertex, which is the honeycomb’s degree; go out along one edge and back along another and the voltages subtract, giving the translation that closed walk lifted to — (0, 1) for the first pair, (1, 1) for the first and third, and those two generate ℤ². There is no picture in any of that, and nothing in it that could be measured slightly wrong.

What a periodic graph is, exactly #

A periodic graph in the plane is an infinite graph together with an action of ℤ² on it — a pair of commuting translations — that is free, so no translation fixes a vertex, and whose quotient is finite. The last condition is what says the crystal has a repeating unit at all.

That definition mentions no distances, and it is the definition. A net is not a drawing with the drawing rubbed out; it is a combinatorial object in its own right, and a drawing is something added to it afterwards.

The finite description follows from the definition. Take the quotient: the vertices are the ℤ²-orbits of vertices, of which there are finitely many, and each edge of the quotient remembers one integer pair — the cell offset by which its two ends differ. That pair is called the edge’s voltage, a word borrowed from topological graph theory, where the sum of voltages round a cycle is the object of interest for the same reason it is here.

So { u: 0, v: 1, s: (−1, −1) } says: vertex 0 of the home cell is joined to vertex 1 of the cell one step back along each basis translation. Three such lines are a honeycomb.

The two freedoms #

A quotient graph is a description, and descriptions have slack. There are exactly two kinds here, and recognising them is the whole of deciding when two nets are the same net.

Gauge. Which vertex of an orbit gets called the home one is arbitrary. Move quotient vertex 1 into the cell one step along, and every voltage on an edge leaving it gains that offset while every voltage arriving loses it. The description changes; the infinite graph does not move at all.

Basis. The translations form ℤ², and ℤ² has no preferred basis. Any integer matrix of determinant ±1 applied to every voltage describes the same net against a different pair of translations. This is the graph-theoretic twin of the warning that the cell is a choice and the lattice is not — and it bites harder here, because a quotient graph looks so much like a finished answer that the arbitrariness in it is easy to forget.

Two quotient graphs describe the same net exactly when some relabelling of vertices, some gauge and some basis change carry one to the other. That is a search, and it is the search sameNet performs — over all relabellings, over gauges within a bounded range, over basis matrices with entries up to four. A negative answer from a bounded search is a negative answer within the bound, and every count in these essays that rests on one says so rather than pretending to a theorem.

The condition that makes a description honest #

There is one way to write down a quotient graph that is not wrong and is not right either, and it has to be checked for.

The cycles of the quotient graph carry voltages: sum the voltages along a closed walk and the result is the translation that walk lifts to. The set of all such sums is a subgroup of ℤ², and for the description to mean what it appears to mean it must be the whole of ℤ².

If the cycles generate only a sublattice of index two, the net’s actual translation group is that sublattice. The quotient graph has twice as many vertices as it needs; the “cell” is a supercell; and every count made against it — vertices per cell, edges per cell, density — is wrong by a factor of two, silently, with the picture looking entirely normal.

The check costs a spanning tree and a determinant, and it is the difference between a description of a net and a description of a net written on the wrong cell.

The mechanics are short enough to state. Take any spanning tree of the quotient graph; every edge left out of it closes exactly one cycle, and there are e − n + 1 such edges. Sum the voltages round each of those cycles, with a sign for the direction each edge is traversed, and the results are a generating set for the whole subgroup — because every cycle in the graph is a sum of those ones. Stack them as the rows of an integer matrix. If the matrix has fewer than two independent rows the net is not two-periodic at all; otherwise the index is the absolute value of the determinant of any two independent rows chosen so that the others are integer combinations of them, which is the greatest common divisor of the two-by-two minors. All of it is integer arithmetic, so the answer is 1 or it is not, with nothing in between and nothing to round.

Where this description came from #

The word net in this sense is A. F. Wells’s, who spent the nineteen-fifties and sixties enumerating the ways atoms can be joined in three dimensions and publishing the results as Three-dimensional Nets and Polyhedra. His question was not the crystallographer’s. A crystallographer asks what the symmetry of a structure is; Wells asked what structures are available — which patterns of connection can exist at all, before any particular substance is proposed for them.

That reframing turned out to matter enormously once chemists began building frameworks to order. A metal-organic framework is designed by choosing a net first and then finding molecules the right shape to realise it, which is only a sensible way to work if nets are objects one can enumerate and name independently of any structure. The Reticular Chemistry Structure Resource, which does the naming, carries three-letter symbols for thousands of them; the ones in this collection are sql, hxl, hcb, kgm and their relatives, and the symbols are theirs.

The quotient-graph-with-voltages description is later and comes from topological graph theory by way of Chung, Sarah, Delgado-Friedrichs and others. It is the description that makes the computations in the next three essays possible, because it turns questions about an infinite object into linear algebra on a few integers.

What a description cannot be asked #

Two things are worth stating plainly, because both are places where a reader could reasonably expect more than a net can give.

A net has no metric, and therefore no shape. The honeycomb’s vertices are equally spaced only in a drawing of it. As a graph, hcb says which vertices are joined and nothing whatever about how far apart they are, so a honeycomb, a brick wall and a badly squashed mesh are one net. The next essay but one is about the one drawing that can be singled out without choosing anything, and about why its symmetry is the net’s.

A net is not a structure. Real atoms have sizes, real bonds have lengths and angles, and a net that is combinatorially perfect may be geometrically impossible to build with any actual chemistry. Wells knew this and said so; the nets he enumerated are a catalogue of what is not forbidden by connectivity, which is a weaker and more useful thing than a catalogue of what exists.

Why the voltages are integers, and what that buys #

It is worth pausing on the one arithmetic fact the whole description rests on, because it is the same fact the rest of this collection rests on and it arrives here by a different road.

A voltage is an element of ℤ², and it is an element of ℤ² because the translation group of the net is ℤ² — that is what the definition asked for. Nothing was measured to obtain it and nothing was rounded. Compare the situation for a point set: deciding whether a pattern has a symmetry is exact only because the work is done in the lattice basis, where the operations are integer matrices and the translations are rationals with small denominators, and choosing that basis is a step somebody has to take. Here there is no step. The integers are the object.

The consequence runs through everything below. A question about a net is a question about a few small integers, so it is decidable in the strict sense — a finite computation with an exactly right answer, no tolerance and no residual. The round trip this collection performs on patterns has an analogue for nets that is if anything cleaner, because the forgetting and the rediscovering are both integer arithmetic.

It is also the reason the counts in the next essay can be exhaustive. Enumerating every net with one quotient vertex and three edges whose voltages lie in a box is a loop over integers; enumerating every pattern with some geometric property is not a loop over anything.

Two nets that are not the same net #

The freedoms are freedoms, and it matters that they are not everything. A machinery that answered yes, the same net to any pair would satisfy the gauge and basis tests perfectly and be worthless.

So the check runs in both directions. The square net has one vertex and two edges; the triangular net has one vertex and three. No relabelling, no gauge and no change of basis can turn two edges into three, and the search says so immediately. Less trivially, two nets with the same number of vertices and edges and the same degrees can still be different — and the machinery has to find that out by searching rather than by counting.

What is left when the distances go #

The rest of this ladder is an accounting of what survives.

The counting outwards survives: how many vertices lie at each graph distance from a starting vertex is a question about incidences only, and its answer turns out to be a quasi-polynomial with a period that is not always one. The symmetry group survives, which is the surprising one, because a group of motions of the plane is exactly the kind of thing that ought to need a plane. And what does not survive is anything about the actual arrangement of matter — the net is compatible with an infinity of structures, and choosing which of them is meant is the subject of the fourth rung.

The counting is worth a sentence in advance, because it is the plainest demonstration that a graph with no lengths in it still has a shape. Start at a vertex and ask how many vertices lie exactly one edge away, then two, then three. For the square net the answer is 4, 8, 12, 16 — four more at every step. For the honeycomb it is 3, 6, 9, 12. For the kagome net it is 4, 8, 14, 18, and the differences are 4, 6, 4, which do not settle into one number and never will: the counts follow one straight line on odd distances and a different one on even, for ever. That is a quasi-polynomial, the counting is done with no coordinates anywhere, and the next essay is about how much such a count decides and how much it does not.

The thing that does not survive is worth naming precisely, because it is easy to overstate the loss. A net does not remember distances — but it does remember a great deal that feels geometric. It remembers how many neighbours each vertex has. It remembers whether a cycle of length five exists. It remembers, through the voltages, which walks close up in the plane and which run away to infinity. What it has given up is the metric, and a metric is a smaller thing than it looks: five plane lattices differ from one another in exactly that way and no other, and the classification into five is a classification of metrics laid over one graph.

There is one more thing to say about the description, and it belongs here rather than later. A quotient graph is small. The honeycomb is nine integers; the kagome net is twenty-one. An infinite object with an infinite symmetry group has been reduced to something that fits in a line of code, and every question the next essays ask is asked of those integers and of nothing else. That compression is not a convenience. It is what makes the questions decidable at all.

A description that is also a program #

One last property of the quotient graph deserves its own paragraph, because it is what separates this description from the diagrams in an older textbook.

A picture of a net communicates it to a reader and to nothing else. A quotient graph communicates it to a computation. Every question in the four essays that follow — how many vertices at distance six, what group does the equilibrium drawing have, how many independent mechanisms does the framework of bars have — is answered by a procedure that takes those few integers as input and returns a number, with no drawing made at any point. The drawings in these essays are made afterwards, for the reader, from the answers.

That is why the descriptions in this collection are stored the way they are, and it is worth stating as a general principle: a description that a program can consume is a description that can be checked. The net that appears in the figure above went through the same voltage-lattice test as every other, and if its cycles had generated a sublattice the machinery would have said so before a single line was drawn. A diagram cannot be tested that way, which is exactly why a wrong pattern is beautiful and a wrong net looks like a net.

Deciding when two descriptions are the same net #

The two freedoms make comparison a problem: two quotient graphs describing one net can look entirely different, and checking every relabelling, every gauge and every basis change is a search with no obvious bound. There is a canonical form, it is computable, and it is what turns a description into an identifier.

The construction goes through the net’s own most symmetric placement. Put every vertex at the average of its neighbours’ positions — the barycentric placement — and the result is determined by the net alone, up to an affine map. That placement has a symmetry group, which is the net’s largest possible symmetry, and from it a canonical basis and a canonical vertex ordering can be chosen by rules that mention nothing arbitrary.

Writing the quotient graph in that basis and that order gives a string of integers depending on the net and on nothing else. Two nets are the same exactly when their strings agree, which is a comparison rather than a search.

That is what a structural database of nets is built on. Each entry carries such a key, a newly proposed net is reduced to its key and looked up, and a duplicate is caught immediately rather than by anybody recognising the picture. The algorithm and the naming scheme it supports — three-letter symbols for the common nets, with the honeycomb as hcb and the kagome as kgm — are Delgado-Friedrichs and O’Keeffe’s, and every net name in this collection comes from it.

The canonical form also settles the negative direction, which is the harder one. Two descriptions that reduce to different keys are provably different nets, and a check that merely failed to find a transformation between them would establish nothing.

When the voltages do not span #

The index check has a failure the essay states and a second one worth naming, because it is the case where the description is not merely on the wrong cell but describes a different kind of object.

If the cycle voltages generate a subgroup of rank one rather than a finite-index sublattice, the net’s translation group is a single infinite cyclic group — so the object is periodic in one direction and not in two. It is a chain, or a stack of unconnected chains, drawn as though it were a plane net.

The determinant catches that as a zero rather than as a large index, and the two failures deserve different responses. A large index means the cell is too small and the repair is to enlarge it. A zero determinant means the net is not two-periodic at all, and no cell repairs it — which is a statement about the structure rather than about the description of it.

That distinction matters more in three dimensions than in the plane, because a proposed framework whose connectivity is genuinely two-periodic — sheets, stacked but not linked — is a real and common mistake, and it looks exactly like a three-periodic net until the rank is computed.

Where this ladder goes next #

Counting outwards takes the cheapest invariant a net has — the number of vertices at each graph distance — and measures how much it decides and how much it does not. The placement nobody chose puts every vertex at the average of its neighbours, and recovers the group. And the fourth rung asks the question this essay has quietly assumed away: given a list of atomic positions, which pairs are joined?

Two rungs further on, the same nets are read as frameworks of rigid bars, and the question becomes whether they can move.