Every net with one vertex, counted

Every net this collection has drawn was chosen. The honeycomb because graphite and graphene are made of it; the kagome net because of its hexagons; the square net because it is the lattice read as a graph. Each was picked for having something to show, and each duly showed it.

That is a fine way to write essays and a poor way to learn what nets are like, because a chosen example says nothing about the population it came from. The remedy is a census: fix the number of vertices and edges, bound the voltages, and enumerate everything.

What is being enumerated #

A net with one vertex is a quotient graph with a single vertex and some loops on it, each loop carrying a voltage: the pair of integers saying which cell the edge reaches into. Two loops with voltages (1,0) and (0,1) unfold to the square net; three with (1,0), (0,1) and (1,1) unfold to the triangular one.

So a candidate is a multiset of integer pairs, drawn from a box, and the enumeration is over multisets. Two things have to be divided out before the count means anything, and both were established when nets entered this collection.

An edge is unordered. A loop of voltage s and one of voltage −s are one loop, so only one of each ± pair is enumerated.

The translations have no preferred basis. Any integer matrix of determinant ±1 applied to every voltage describes the same net against different translations, so two candidates related by such a matrix are one net.

And what is rejected #

A multiset whose voltages generate only a proper sublattice of ℤ² is rejected outright, and this is the condition worth pausing on because it is where a census can quietly go wrong.

Take the voltages (2, 0) and (0, 1). That is a perfectly good graph, and it unfolds to a perfectly good periodic structure — the square net, described against translations twice as far apart in one direction as they need to be. The description has a supercell for a cell, and every count made against it is wrong by the index: vertices per cell, edges per cell, density.

The test is the one the nets essays built: sum the voltages round the cycles, ask what subgroup of ℤ² they generate, and require it to be the whole of it. At the smallest box, five of ten two-edge candidates fail it; at the largest, two hundred and seventy-one of three hundred.

Two edges: exactly one net #

The first row of the table is a closed answer, and it has a proof rather than a search behind it.

Two voltages that generate ℤ² are a basis of ℤ². The general linear group over the integers acts transitively on bases — carry the first basis to the standard one, then the standard one to the second — so any two such pairs are related by a change of basis, so they describe the same net.

The census agrees, at every bound: one net, from ten candidates, from seventy-eight, from three hundred. That agreement is worth having even though the proof is a sentence. A search that produced two nets here would be a search with a bug in its equivalence test, and a search that produced one where the proof said two would be a proof with a bug in it.

Three edges: the count does not stop #

The second row rises: three, nineteen, a hundred and forty-three. It rises because the family is infinite, and the reason is as short as the reason the first row is closed.

Normalise two of the three voltages to the standard basis — always possible, since some two of them generate the translations. The third is then a free pair of integers (a, b), and different pairs generally give different nets. So the three-edge nets are a two-parameter family, and a box merely says how much of it has been looked at.

An enumeration inside a bound can report either of two situations and it has to say which. Closed: the count stopped rising and the family is finished. Still rising: the count is a fact about the box. This collection’s habit with a bounded search is to state the bound with the answer, and the same applies when the answer is a census rather than a decision.

The rejection test, as arithmetic #

The condition that the voltages generate the whole of ℤ² rather than a proper sublattice is the census’s one substantive filter, and it is worth writing down as a computation, because “generate” is the kind of word that hides an algorithm.

Stack the voltages as the rows of a matrix. A candidate with $k$ edges gives a $k \times 2$ matrix of integers, and the question is whether its rows span ℤ² over the integers — not over the rationals, which is a much weaker demand and the source of the usual mistake. The rows $(2, 0)$ and $(0, 1)$ span the plane over the rationals and generate only the index-two sublattice of points with even first coordinate.

The integer answer is the greatest common divisor of the two-by-two minors. Take every pair of rows, form the determinant, and take the gcd of the results. That gcd is the index of the generated sublattice inside ℤ², so the candidate survives exactly when the gcd is one. For $(2,0)$ and $(0,1)$ the single minor is two, and the rejection is immediate.

This is Smith normal form in the smallest case that is not trivial. Any integer matrix can be brought by integer row and column operations of determinant $\pm 1$ to a diagonal matrix whose entries divide one another in turn, and those entries — the elementary divisors — describe the sublattice completely: their product is the index, and their individual values say which finite group the quotient is. A candidate whose divisors are $1, 1$ generates everything; one whose divisors are $1, 3$ generates an index-three sublattice with cyclic quotient; one whose divisors are $2, 2$ generates an index-four sublattice with quotient the Klein four-group, which is a different failure from index four with divisors $1, 4$.

The distinction is not pedantry, because the rejected candidates are not nothing. A candidate generating an index-$n$ sublattice is a perfectly good net; it is a net on the sublattice, already counted elsewhere in the census under a change of basis, and counting it again would report one object twice. Rejection here is deduplication rather than exclusion, and the elementary divisors say precisely which earlier entry the rejected candidate duplicates.

Nothing here says the net can be built #

There is a gap between the objects this census counts and the objects a crystal chemist wants counted, and it is worth stating plainly, because the census is silent about it and a reader is entitled to assume otherwise.

A quotient graph with voltages is a combinatorial object. It records which vertices are joined and by how many cells the join steps, and it records nothing about where anything is. The barycentric placement supplies coordinates afterwards, by a rule — every vertex at the average of its neighbours — and the rule always returns an answer. That answer is what the plane groups above were measured on.

The answer can have edges that cross. Two edges of a net, drawn as straight segments between the placed vertices, may intersect at a point that is not a vertex. Nothing in the enumeration forbids it and the barycentric rule has no way to avoid it. In the abstract that is unremarkable — the net is a graph, and a graph does not know it has been drawn — and in matter it is fatal, since two bonds cannot pass through one another.

So the hundred and forty-three are nets, and some unknown number of them are structures. Deciding which is a question about embeddings rather than about voltages, it is harder than the enumeration by a long way, and it is not answered by looking at one placement: a net whose barycentric drawing has crossings may have some other drawing, with the same topology and different coordinates, that does not.

Three edges at one vertex has a second problem of the same kind, and it is the one a chemist would raise first. A vertex with three edges in the quotient has six edges in the net, since each loop lifts to two — one arriving, one leaving. Six bonds at one atom is a demanding coordination, available to a metal centre and to nothing else in a great deal of chemistry, so the row of the census that grows fastest is also the row least likely to be realised.

This is why a census and a database answer different questions. The database holds nets somebody found in a crystal, so every entry is realisable by construction and the collection is biased towards whatever chemistry is common. The census holds every net the definition permits, realisable or not, so it can say what is typical — and the price of that is that typical includes a great deal that no material will ever be.

What a bounded search is entitled to conclude #

The three-edge row is a good place to state the general rule this collection follows, because the temptation to over-report is strongest where the numbers are largest.

A search inside a box that finds n objects has established that there are at least n. It has established n exactly only if some argument says nothing outside the box could be new — which for the two-edge family is available in a line, and for the three-edge family is false.

The same distinction used to govern the equivalence, and no longer does, which is worth recording because the repair came out of a failure this essay’s own table displayed.

sameNet searches over gauges and over basis matrices with bounded entries, so a negative answer from it is negative within that bound — and a bounded pairwise test is not transitive. Two descriptions can each be within the bound of a third and outside it of one another, because the matrix carrying one to the other is a product of two that were each small enough. The census duly counted one net several times as the box grew, and the symptom was visible in the table: the two-vertex census returns four three-edge nets at a box of one, four at two, five at three and eleven at four, and three of those eleven are the honeycomb.

The repair is a canonical description rather than a larger bound, and it is the same reduction the basis correction needed: fix the basis by reducing the form the net’s own edges make, try the reduced form’s own automorphisms and the relabellings of the quotient vertices, bring every vertex into the home cell of its placement, and take the smallest key. Equal keys, equal nets, and no comparison at all. The counts here are that census, which is why the three-edge row reads a hundred and forty-three rather than the hundred and forty-four this essay first reported.

One case still carries a bound, and it is stated where it bites. An unstable net — one whose placement puts two vertices at a point — has no placement to reduce and therefore no canonical key, so those are still compared pairwise and a count of them is a count at a bound. A one-vertex net cannot be unstable, so nothing on this page is affected; the two-vertex census is, and says so.

That is not a weakness peculiar to nets. It is the same shape as the tiling essays’ unknown column, where a bounded search cannot turn a failure to find into a proof of absence, and the same shape as sameNet’s own warning when it was built. What makes it liveable is stating it every time rather than in a footnote.

The question the census answers instead #

A census that does not close is usually a disappointment. This one is not, because it makes a different question available and that question has a sharp answer.

Not how many nets there are, which for three edges is “infinitely many”. But what a net is like when nobody chose it: of the hundred and forty-three one-vertex three-edge nets inside a box of three, how many have any symmetry?

The answer is seventeen, and the number was one until the instrument that produced it was checked.

A hundred and twenty-six of the hundred and forty-three have the group p2 and nothing more. Nine have pmm, seven have cmm, and one — the triangular net, which is the only member of this family anybody has ever named — has p6m. That is one net in eight with something beyond the floor, which is still a minority and is not the near-absence this essay reported when it was written.

Why p2 is the floor #

The uniformity of that answer is itself worth explaining, and the explanation is a small piece of arithmetic about the barycentric placement.

A one-vertex net has its single vertex at the origin in the placement that puts every vertex at the average of its neighbours — there is nowhere else for it to go. Its edges leave in ± pairs, because a loop of voltage s is also a loop of voltage −s. So the placement is symmetric under the inversion x ↦ −x, always, for every one-vertex net there is.

p2 is therefore not a symmetry these nets happen to have. It is a symmetry they cannot avoid, and the census is a measurement of how rarely anything is added to it.

That is the same shape of statement as the one the motif essay makes about a single dot: a lone point cannot illustrate the group with no symmetry at all, because the midpoint construction supplies an inversion centre nobody asked for. A one-vertex net has the same problem in a different language, and the honest way to build a p1 net is to use more than one vertex.

The seventeen that are not p2, and the sixteen that were hidden #

A hundred and twenty-six to seventeen is a ratio worth looking at from the other end.

Every exception is symmetric for a legible reason, and it is always the same reason: its three voltages are closed, as a set, under something. The clearest is the triangular net, whose voltages (1,0), (0,1) and (1,1) are permuted by every operation of a hexagon, which is why it alone reaches p6m. The nine with pmm have voltage sets closed under reflection in two perpendicular directions; the seven with cmm have theirs closed under reflection in two diagonals. Everything about the higher symmetry of a net is of that kind, which is why the nets a chemist finds interesting are the ones whose voltage sets are closed under something.

Sixteen of those seventeen were invisible when this essay was first written, and the reason is worth stating here because it is the reason the number in the previous section moved. The detector this collection uses tests, for each of the five lattice types, the operations that type’s holohedry contains in standard position — a fixed list of integer matrices. A symmetry written against some other basis of ℤ² is a different matrix, which is not in the list and is never tried. And a description produced by an enumeration is written in whatever basis the enumeration reached it in, which is nobody’s choice at all.

So the census was reporting how many of its members the enumeration had happened to write down in a convenient basis. The repair is to give each net the basis its own edges ask for before anything is detected, and it is an essay of its own, because the correction applies to every net on this site and not only to these hundred and forty-three.

What survives the repair is the shape of the answer. Symmetry is still the exception; the floor is still a floor; and the census still says something no database can, because a database contains the nets somebody thought worth entering. What does not survive is the ratio, and a ratio quoted from an instrument nobody checked is the thing this collection exists to avoid.

And it is a reminder of what “almost none” means quantitatively. A census with a hundred and forty-three members and seventeen exceptions is not the same claim as a census with a thousand and none; both get reported as “symmetry is rare”, and only the first can name its exceptions.

Four edges, and how fast the count grows #

The census runs one row further, and the growth is worth seeing because it says something about how large the space of nets is.

One vertex and four edges gives six nets inside the smallest box, a hundred and twenty-seven inside the next and eighteen hundred and fifty-one inside the one after. That is faster than the three-edge row by roughly the same factor at each step, which is what a family with more free parameters looks like: two voltages fixed as a basis, two free pairs of integers rather than one.

The symmetry statistic moves in the other direction and stays a minority. Of the eighteen hundred and fifty-one, a hundred and thirty-four have more than p2 — seven per cent against the three-edge row’s twelve. A four-edge net has more voltages that must all fall into the closed set, which is a harder condition to meet by accident than the three-edge one, so the larger family is the less symmetric of the two. Nineteen of the four-edge nets reach p4 and eleven reach p4m, orders no three-edge net can have: a four-fold rotation permutes the voltages in a four-cycle and there are not enough of them at three.

Neither number is a fact anybody needs. What they are together is a shape: the space of nets is large, its symmetric members are rare, and the rarity does not vanish as the nets get bigger.

What made the count feasible #

The equivalence being divided by is sameNet, which searches over relabellings, gauges and basis matrices — a bounded search that is not cheap. Running it on every pair of the seventeen thousand candidates at the largest box would be several million searches.

The census does not. It buckets the candidates first on an invariant that no change of basis can alter: the multiset of pairwise determinants of the voltages, taken in absolute value. A change of basis multiplies every determinant by ±1, and flipping an edge’s sign flips some of them, so the absolute values survive both freedoms. Two candidates in different buckets cannot be the same net, so the expensive comparison runs only inside a bucket.

The invariant decides nothing on its own — everything inside a bucket is still compared properly — and the effect is a census that runs in seconds rather than minutes. That is a small piece of engineering and it is recorded because the alternative was not running the census at all.

The equivalence, once more, in the form the census needs #

Everything above rests on sameNet, and it is worth restating what that routine decides, because a census is only as good as its notion of “the same”.

Two quotient graphs describe one net when some relabelling of vertices, some gauge — moving a vertex into a different cell, which changes voltages and moves nothing — and some change of basis carry one to the other. All three freedoms were established when nets entered the collection, and all three are searched.

For one-vertex nets the first two are trivial: there is nothing to relabel, and moving the only vertex changes no voltage on a loop. So the whole equivalence here is the change of basis, which is why the two-edge answer has a one-line proof and why the fingerprint used to bucket candidates is a basis invariant.

That simplification is the reason one vertex was chosen for the census. With two vertices the gauge freedom re-enters, the search is genuinely three-dimensional, and the counts would be dominated by the cost of the equivalence rather than by the enumeration.

What a census is for, when a database exists #

Wells spent two decades enumerating nets by hand and the modern databases hold thousands of them, all found rather than derived. A census inside a bound cannot compete with that and is not trying to.

What it can do is two things a collection of examples cannot. It can close a family — one vertex and two edges is one net, full stop — which no amount of collecting establishes. And it can describe the typical member of a family that does not close, which is the statement that “almost every net has only an inversion centre” and which no database supports, because a database contains the nets somebody thought worth entering.

Both are statements about the population rather than about any member of it, and both are what a reader who has met only the honeycomb and the kagome net is missing.

Where this goes #

The obvious extension is two vertices, where the honeycomb lives, where the count is larger, and where the same question about typical symmetry gets a different answer — because the argument that makes p2 a floor here uses the fact that there is only one vertex to place, and with two there is no floor at all. That census also has to refuse a kind of description this one never met: a quotient graph whose cycles generate the whole of ℤ² and whose net has one vertex per cell rather than two.

Beyond it is the more interesting version, which the plan still records: sorting a census by where in reciprocal space its frameworks’ mechanisms live, which would say how unusual the kagome net’s line of modes is.

The nearer relative is the sublattice count, which is the same kind of arithmetic one level down — enumerate the ways of thinning a lattice, divide by the equivalences, and count — and which closes where this one does not, because a sublattice of a given index is a finite thing to be.