Counting outwards

Stand at a vertex of a net and count. How many vertices are one edge away, how many are two edges away, three, four? Nothing in the question mentions a length, so it is a question a net can answer: the distances have been thrown away and the incidences are all that is left, and this is a question about incidences.

The sequence of answers is called the coordination sequence, and it is the first thing a structural chemist computes about a net. Its first term is the degree. Its later terms are not obviously anything.

The search is on the infinite graph #

The one thing that has to be right about the computation is that it does not fold.

A breadth-first search run on the quotient graph would answer a different question — distances on a torus, where a walk of three steps can come back to where it started because the cell wraps round. What is wanted is distance in the infinite net, so the search runs there: a vertex is a pair, a quotient vertex and a cell, and stepping along an edge adds that edge’s voltage to the cell. The graph is infinite and the search is finite, because it stops after the requested number of shells.

That is the whole algorithm, and it costs nothing. Twelve terms of the kagome net’s sequence is a few thousand vertices.

The straight line, and where it fails #

For the simplest nets the answer is exactly what a first guess suggests.

The square net gives 4, 8, 12, 16, 20 — four times the distance, for ever. The triangular net gives 6, 12, 18, 24. The honeycomb gives 3, 6, 9, 12. In each case the counts are a linear function of the distance, with no correction term at all, and the reason is not hard to see: the shell at distance n is the boundary of a growing convex region, its length grows in proportion to n, and a straight line is what a growing boundary counts out.

Now the kagome net: 4, 8, 14, 18, 22, 28, 30, 38. Differences of 4, 6, 4, 4, 6, 2, 8 — no line at all. Take only the odd terms, though, and they run 4, 14, 22, 30, 38: a straight line of slope four. Take the even ones and they run 8, 18, 28, 38: another straight line, of slope five, and a different intercept. The sequence is two interleaved arithmetic progressions.

Quasi-polynomial, and the period is measured #

A quasi-polynomial is a function that agrees with a polynomial on each residue class of its argument, with a different polynomial for each class. Its period is how many classes there are. A plain polynomial is the case of period one.

The coordination sequence of a two-dimensional net is eventually a quasi-polynomial of degree one. That is a theorem, and the proof is not short; the periods, though, are a measurement, and they can be taken.

The measurement has to be done carefully, because a fit that is nearly right is exactly the kind of thing that produces a wrong period. So the procedure here is: for each candidate period, fit a line through the first three terms of each residue class in the tail, and then require that line to hit every other term of that class exactly. A period is reported only when the fit is exact on every point it was not fitted to. A period of one that came from a tolerance would be worthless.

The slope carries a meaning the period does not. Averaged over the residue classes, the slope of the linear growth is a measure of how much net there is per unit of graph distance — the quantity that goes by the name topological density, and the closest thing a net has to an area. A larger slope means a net that expands faster in the only metric it possesses, which is the count of edges.

What the sequence is used for #

In practice a coordination sequence is used as a fingerprint. A structure is solved, its net is extracted, its first ten terms are computed, and the result is looked up against a database of known nets. If it matches, the net is probably that one; if it matches nothing, the net is probably new, and somebody writes a paper.

That practice raises exactly the question this collection always asks of an invariant: how much does it actually decide?

The honest way to answer is to look for two different nets with the same sequence. So take the smallest family where the search can be exhaustive — one quotient vertex, three edges, voltages inside a box — enumerate every net in it, throw away the ones that are descriptions of the same net, and group what is left by the first twelve terms.

So the sequence is a good fingerprint and not a proof of identity. Both halves of that sentence are worth having: a chemist’s lookup is sound practice, and a chemist’s lookup is not an identification, and knowing which of those is being relied on is the difference between a claim and a habit.

Why the period is not one #

The reason a period appears at all is worth understanding, because it turns up in three separate places in this collection and is one phenomenon each time.

A shell at distance n is a closed curve in the net, and the number of vertices on it is decided by where that curve crosses the net’s own structure. For the square net the curve is a diamond whose corners land on lattice points at every n, so the count is the same rule at every n and the sequence is a plain line. For the kagome net the curve’s corners land on lattice points only at every second n; in between they land halfway between, and the counting rule is different there. Two rules, alternating: period two.

That is the same phenomenon as a lattice-point count in a polygon whose corners are not lattice points, where the count is a quasi-polynomial with period the denominator the corners are written over. The two subjects are usually taught apart — one in combinatorics, one in structural chemistry — and they are one subject.

The kagome case is concrete enough to follow all the way down. Its three vertices per cell sit at the midpoints of the cell’s edges, which in fractional coordinates are (½, 0), (0, ½) and (½, ½) — halves, not integers, and that is the whole of it. A shell of the net is a hexagon whose corners run out along the three lattice directions, and a corner at graph distance n lands on a vertex of the net when n is even and between two of them when n is odd, because the step from one kagome vertex to the next along a direction is half a cell. So there are two counting rules, one for each parity, and the counts alternate between two lines: slope four on the odd shells and slope five on the even ones. The period is the denominator the vertices are written over, exactly as it is for a polygon whose corners sit at halves, and it has nothing to do with how complicated the net looks.

The tail, and what “eventually” is hiding #

The theorem says eventually quasi-polynomial, and the word is doing real work. A coordination sequence has a beginning that obeys no rule, and how long that beginning lasts is not decided by anything visible in the net.

For the square net there is no beginning at all: the first term already lies on the line. For the star net the first several terms are the search finding its way out of the triangles the vertices have been opened into, and the pattern that eventually holds is not yet visible. The fits in the table above are therefore made on the tail — the last stretch of a sequence run to forty terms — and checked against every term in that stretch. Fitting the head would have produced periods that are artefacts of the head.

This matters practically. A chemist who computes ten terms and looks for a pattern is looking at the head, and the head of a complicated net is noise. Ten terms is enough to identify a net against a table and not enough to say what kind of function its counts are, and confusing the two is how a wrong period gets published.

The same caution applies to the slope. The slope reported in the table is the average of the lines fitted on the tail. Computing it as a difference of two early terms would give a number that varies with which two terms were chosen, and any such number is a property of the head rather than of the net.

What a shell looks like, and why the answer is a line #

There is a way of seeing the linear growth that makes it obvious, and it is worth putting down because it also explains the exceptions.

Take the square net and mark the vertices at distance n from the origin. They form a diamond — the set of integer points with |x| + |y| = n — and a diamond of that size has exactly 4n points on it. The growth is linear because the shell is a curve, and a curve in the plane at scale n has a length proportional to n. Nothing about that argument is special to the square net: any two-dimensional net’s shells are curves, so any two-dimensional net’s counts grow linearly.

What the argument does not say is that the counts are exactly linear, and that is where the wobble comes in. The shell is a polygon whose corners are determined by the net’s own directions, and its corners land on vertices only when n is right. The number of vertices on it is therefore the length of the polygon plus a correction that depends on where the corners fell — which is a periodic function of n, and which is precisely the extra term a quasi-polynomial has.

In three dimensions the same argument gives shells that are surfaces, growing like n², and coordination sequences that are quasi-polynomials of degree two. The pattern is the dimension, arrived at by counting, which is the same fact the growth of a wallpaper group reports from the algebraic side.

Two things the counting cannot see #

It cannot see the metric. The lengths went when the distances were thrown away, and no amount of counting brings them back. The sequence of the honeycomb is 3, 6, 9, 12 whether the honeycomb is drawn regular, stretched or crumpled, because none of those is a change to the graph. That is a strength when the question is which net is this and a weakness when the question is what does this substance look like.

It cannot see the starting vertex, unless it is asked to. A net whose vertices are not all alike has a coordination sequence per vertex, and quoting one of them as the net’s sequence is a mistake with a long history in the literature. The ladder net has vertices of degree three and of degree four; the sequence from a degree-three vertex begins 3, and from a degree-four vertex it begins 4, and no amount of care about later terms rescues a comparison made between the wrong pair.

The practical form of that caution is a property with a name. A net is vertex-transitive when its own symmetry group carries any vertex to any other, and only then does “the coordination sequence of this net” mean anything without a qualifier. The square, triangular, honeycomb and kagome nets are all vertex-transitive and have one sequence each; the ladder net is not and has two; the star net is vertex-transitive despite having six vertices in its quotient, because the group permutes all six. So the number of quotient vertices is no guide at all to how many sequences a net has — that is decided by the group, which is a thing computed rather than counted, and it is the subject of the next rung. A database that quotes one sequence per net is quoting a fact about vertex-transitive nets and a convention about everything else.

Where it was worked out #

Coordination sequences were introduced by Brunner and Laves in 1971 as a way of telling zeolite frameworks apart, at a moment when the frameworks were multiplying faster than anybody could keep them straight. For twenty years the sequences were computed and tabulated and nobody knew what kind of function they were.

The answer — eventually quasi-polynomial, degree one less than the dimension — came in stages through the nineteen-nineties and 2000s, with contributions from Grosse-Kunstleve, Brunner and Sloane on the crystallographic side and from work on growth in groups on the other. The two-dimensional case is the one this collection can compute exhaustively, and it is also the case where the theorem is easiest to believe: a shell is a closed curve, its length grows with its radius, and the wobble is what happens when the curve’s corners meet the lattice differently at different radii.

The reason the two literatures met is that they were counting the same thing. Take a group, choose a generating set, and count how many elements can be written as a word of length one, two, three in those generators: that is the growth function of the group, and it is an object combinatorial group theory has studied since the nineteen-sixties. Now draw the group’s Cayley graph — one vertex per element, one edge per generator — and the count of words of length n is the count of vertices at graph distance n from the identity. For a wallpaper group that Cayley graph is a periodic plane graph, which is to say a net, and its growth function is that net’s coordination sequence. The growth of a wallpaper group is the same measurement this essay is making, taken on the other side of the same object, and the quasi-polynomial periods turn up there too and were explained there first.

The one number that is not a measurement #

Everything above is measured, with a stated window and a stated bound. One thing is not, and it is the degree.

The first term of a coordination sequence is the number of edges at the starting vertex, and that is read straight off the quotient graph with no search at all. It is also the term that carries most of the chemistry: a four-coordinated framework and a three-coordinated one are different kinds of material, and no later term of the sequence changes that. The sequence’s later terms are where the topology lives, and they are where two nets of the same degree — the triangular net and the skew net, both of degree six — part company.

The cumulative version, which is what a database prints #

The sequence itself is used as a fingerprint, and the number the zeolite literature actually quotes is not the sequence but a running total of it.

Topological density is the cumulative count out to a fixed distance, divided by that distance — most often taken to ten shells, and written TD10. It is a single number per vertex rather than a list, it compresses the fingerprint to something sortable, and it is what a framework database prints beside each structure.

Two properties make it a better index than the raw sequence. It is stable: a shell whose count wobbles by one because of the periodicity moves the total by one part in a few hundred, so nets whose sequences interleave are still separated. And it is monotone in the obvious way: a more densely connected framework has a larger topological density, so the number sorts frameworks along an axis that means something.

What it loses is exactly the wobble this essay is about. Summing over ten shells averages the residue classes together, so the period is invisible in TD10 and two nets with the same slope and different periods have nearly the same number. The compression is deliberate and it is worth knowing which direction it compresses in: for telling frameworks apart in a database, the average is what is wanted; for saying what kind of quasi-polynomial the growth is, only the sequence will do.

The generating function, and where the period hides #

There is a compact way to hold the whole sequence, and it puts the period somewhere visible instead of leaving it to be measured.

Form the series whose coefficients are the shell counts. For every net whose sequence is eventually quasi-polynomial that series is a rational function — a polynomial over a product of factors of the form 1 − x^k — and the growth and the period are both readable off the denominator. A factor of (1 − x)² gives linear growth. A factor of (1 − x²) gives period two, (1 − x³) period three, and so on.

So the period is not an empirical feature of a list of numbers; it is the order of a root of unity in a denominator. Computing it that way replaces the fitting procedure with an exact algebraic statement, and it removes the hazard the essay names — that a fit which is nearly right produces a wrong period, because a fit has no way to distinguish a genuine period from a long transient.

The catch is that the rational function has to be obtained, and obtaining it means either summing enough terms to identify it or deriving it from the net’s structure. The first is the same measurement with an extra step and inherits the same caution about the tail. The second is available for nets built by a rule and not in general. So the algebra says what kind of object the answer is, and the counting is still how it is found — which is the ordinary relation between a theorem and a computation, and worth stating rather than implying.

Where this ladder goes next #

The counting has taken a net as far as a fingerprint. The next rung does something stronger: it gives the net coordinates — the only coordinates it can be given without choosing anything — and recovers the plane group from them. And the rung after that goes back to the beginning and asks where a net comes from in the first place, given that a list of atomic positions does not contain one.

The relation to how many lattice vectors have each length is worth carrying forward as well: that count is a shell count too, in a metric, and it is a quasi-polynomial for the same reason.