Two structures on a torus, and one Patterson

Two structures, one Patterson settles that two different arrangements of atoms can produce identical diffraction intensities, and settles it the way this collection prefers: by an exhaustive search rather than by an example. Every arrangement of k atoms on a ring of n positions is enumerated, its interatomic vectors counted, and the arrangements that share a vector multiset collected. The smallest case is four atoms on eight sites, where eight arrangements give seven vector sets.

A ring of positions is a crystal in one dimension. Everything this site is about happens in two, and moving the search there is not a formality. The number of vectors a set of k atoms has is k² in either geometry. The number of places those vectors can land is mn rather than n. So a plane Patterson is a far sparser object than a chain Patterson with the same number of atoms, and it is not obvious which way that cuts: sparser bins argue for coincidence being rarer, and a larger group of near-misses argues for its being commoner.

The search settles it, and what it settles is that the question was wrong.

What has to be counted as the same structure #

The whole computation turns on the equivalence, exactly as the count of crystal forms turns on its own, and here the equivalence changes when the dimension does.

A difference multiset is unchanged by sliding a set: every vector between two atoms is the same after both have moved by the same amount. It is also unchanged by turning the set through a half-turn about any point, because inversion sends the vector between two atoms to its own negative, and a difference multiset already contains both. So translation and inversion produce structures that are trivially homometric, and two sets related that way are one structure.

A mirror is different, and this is the one place the plane is not the cycle. On a ring, reflection is inversion — there is only one axis to reverse. In the plane, reflecting in a line sends the vector set to its mirror image, which is a different multiset unless the arrangement happens to be symmetric. So a mirrored copy is a genuinely different structure with a genuinely different Patterson.

That is Friedel’s law stated as an equivalence rather than as a fact about intensities: an experiment cannot see an inversion and can see a reflection. The one-dimensional search folds the two together because it has to, and every count it produces is a count over the wrong group for the plane.

The tori that are cycles wearing different coordinates #

Before any comparison can be made there is an obstacle that turns out to be the best check in the computation.

A torus Zₘ × Zₙ with m and n coprime is not a new object at all. The Chinese remainder theorem makes it isomorphic to Zₘₙ as a group, and a difference multiset is defined by the group and nothing else — so a three-by-five torus is a fifteen-cycle in different coordinates, and every number computed on it must equal the corresponding number for the cycle. Not approximately, and not on average: exactly, row for row.

The two programs share no intermediate. One canonicalises a set over 2mn relabellings of a pair of coordinates; the other over 2n relabellings of a single index. One counts differences into a grid of mn bins addressed by two residues; the other into a line of n. If they agree on the number of structures, the number of distinct Pattersons and the number of homometric groups, over ten independent rows, the plane machinery is doing what it claims.

They agree everywhere. And the consequence is that the interesting comparison is narrower than it looked: only tori whose sides share a factor are genuinely two-dimensional as far as this question is concerned. A two-by-five torus has nothing to say about the plane.

Which is commoner, and why the answer is not a number #

With the coprime rows set aside as a check, twenty-two comparisons remain: a torus with a common factor in its sides, matched against a cycle with the same number of sites and the same number of atoms.

The quantity compared is the fraction of structures that share their Patterson with another one — not the number of homometric groups, because a group of three structures with one Patterson is a single group and three affected structures, and groups of three do occur at these sizes.

Five rows go to the plane, five to the cycle, and twelve are level. The averages are close and slightly favour the cycle. There is no dimensional effect to report, and reporting one would have been easy: taking the two most striking rows and stopping would have produced a confident answer in either direction.

The striking rows are worth having anyway, because they say what does decide it. On a four-by-four torus with four atoms the plane rate is 0.179 against the cycle’s 0.056 — more than three times as prone to coincidence. On a two-by-four torus with four atoms the cycle has a homometric pair and the plane has none at all. Two tori of sixteen and of eight sites, and the effect reverses.

What separates them is the subgroup structure of the site set rather than its dimension. A four-by-four torus has a great many subgroups of order four; a two-by-four torus has few, and its long direction is a cycle of four that a set of four atoms fills entirely. Homometry is a coincidence between convolutions, so what governs it is how many ways the group can be written as a sum of smaller pieces — and that is an arithmetic property of the group, which the number of coordinates does not determine.

The same statement, from the construction #

The construction that explains where cycle pairs come from says the same thing more directly, and it says it without any enumeration.

Where the pairs come from shows that a set which factors as a sumset supplies its own partner: if every atom is a sum b + c with b in B and c in C, and every such sum arises exactly once, then B ⊕ (−C) has the same difference multiset and is generally a different arrangement. Reversing one factor reverses its contribution to the vector set and reversing its conjugate reverses it back.

Nothing in that argument mentions dimension. It is a statement about convolution in an abelian group, and Zₘ × Zₙ is an abelian group. So the construction carries over unchanged, and with it the constraint that made it interesting: both factors must be asymmetric, a two-point set is its own reflection up to a translation in any abelian group whatever, and therefore the smallest useful factorisation is three points by three points and the smallest structure it builds has nine atoms.

That bound is why the construction is not drawn here. Nine atoms on a sixteen-site torus is eleven thousand arrangements to canonicalise and three hundred thousand factorisations to try, which is minutes rather than seconds for a picture that would say what the one-dimensional version already says. The point it makes is the point of this section: the mechanism is about the group, and the group is where the dimension went.

What the vector sets actually look like #

A Patterson on a torus is a small array of integers, one per cell, and the array is worth looking at because it is where the counting happens.

Two things about that array are worth stating and only one of them is obvious.

The obvious one: the origin entry is the atom count, the same for every arrangement of that many atoms, so a Patterson has one fewer independent number than it has cells. This is the map that needs no phases at its smallest scale, and it is why an experimental Patterson is always drawn with its origin peak cut off.

The other: the array is symmetric under inversion by construction, since every vector appears with its negative. So on an m × n torus a Patterson has about mn/2 independent entries, while an arrangement of k atoms has k positions in mn places. Once k is large enough that the number of arrangements outgrows the number of possible Pattersons, coincidences are forced by counting alone — and at four atoms on sixteen sites they are not yet forced, which means the seven homometric groups found there are genuine coincidences rather than a pigeonhole.

The rate does not rise with the number of atoms #

One expectation the census refuses is worth stating, because it is the natural one and it is wrong.

More atoms means more vectors, so more chances for two arrangements to agree; and more atoms also means more arrangements, so more pairs to be checked against one another. Both point the same way, and the rate ought to climb with k.

On a four-by-four torus it goes 0.000, 0.179, 0.122 as the atom count goes three, four, five. On a two-by-eight torus it goes 0.000, 0.078, 0.190. On a three-by-six torus it goes 0.000, 0.000, 0.127 — nothing at four atoms, and a rate above a tenth at five.

The three-atom row is easy: three atoms have nine vectors, six of them off the origin and three of them determined by the other three, and there is simply not enough freedom for two arrangements to agree without being the same. Every torus in the census has a rate of exactly zero at three atoms and every cycle does too, which is a small piece of evidence that the searches are looking at the same thing.

Past that the rate does whatever the arithmetic of the particular group tells it to. Four atoms on sixteen sites is the peak on a square torus and a flat zero on a three-by-six one of eighteen — a larger torus with more room. The reason is the same as before: coincidence needs the group to be expressible as a sum of pieces in more than one way, four is a highly composite thing to ask of Z₄ × Z₄ and an awkward one to ask of Z₃ × Z₆, and neither fact has anything to do with how much room there is.

So the useful statement is a negative one and it is the essay’s result. Nothing about the dimension, the number of sites or the number of atoms predicts the rate on its own. What predicts it is the divisor structure of the group, which is why the coprime tori collapse onto their cycles exactly and why two tori of similar size can differ by a factor of three.

What the search costs, and why it is exhaustive #

Every number above is a complete enumeration, and it is worth saying what that costs because the bound on the census is a bound on a machine rather than on an idea.

The walk generates every k-subset of the mn sites in lexicographic order, and each one is reduced to a canonical form by trying all 2mn relabellings — every translation of the torus, with and without a half-turn — and keeping the string that sorts first. That is the whole of the deduplication, and it has the property this collection asks of its methods: it cannot merge two classes that are genuinely different, because two sets with the same canonical form are related by an operation the search actually applied.

The cost is the binomial coefficient times 2mn times k, and it is the binomial that decides everything. Twenty-four sites with four atoms is ten thousand subsets and a fraction of a second. Sixteen sites with nine atoms is eleven thousand subsets, which is also fine — but the sumset construction over the same torus needs every ordered pair of three-point sets, which is three hundred thousand factorisations each carrying its own canonicalisation, and that is minutes.

Nothing here is sampled and nothing is estimated. Where the census is silent it is silent because the enumeration was not run, not because it was run and reported an average.

Where the exactness stops #

Computed here: every arrangement of k atoms on an m × n torus for the tori and atom counts in the census, reduced to one representative per class under translation and inversion; the difference multiset of each; the classes that share one; and the same three quantities on the cycle with mn sites.

Exhaustive, and small. The largest case enumerated is twenty-four sites with four atoms, and the largest number of structures compared in one row is a few hundred. Everything above is a statement about tori of at most twenty-four cells, and a crystal is not a torus of twenty-four cells. What the enumeration establishes is that homometry occurs, that it is not rare, and that its rate is governed by the arithmetic of the site set — not what the rate is for any real structure.

A torus is not a plane. The wraparound is what makes the count finite and it is also a physical assumption: it says the structure is periodic with exactly that cell, which is the assumption crystallography makes anyway. A finite cluster in the plane, with no periodicity, is a different question, and its difference multiset is not the same object.

And homometry is not the phase problem. Two structures with the same intensities are indistinguishable by intensities, which is stronger than saying the phases are unknown: the phases are not merely unmeasured, they are not determined. The phase problem is about recovering something that exists; homometry is about the cases where the thing to be recovered is not unique. The two are related and they are not the same difficulty.

Who asked it, and when #

Patterson posed the question in 1944, in a paper titled “Ambiguities in the X-ray analysis of crystal structures”, and posed it in exactly the form used here: are there different sets of points with the same set of interpoint vectors? He found examples, in one dimension, by hand.

The one-dimensional case was settled properly by Rosenblatt and Seymour in the 1980s, who characterised the cyclotomic factorisations that produce homometric pairs on a cycle — which is the sumset construction above, stated as an algebraic identity. The two-dimensional case has no such characterisation, and the census here is a small instance of why: the answer depends on the factorisations available in the particular group, and there are more groups of order N to consider than there are divisors of N.

The question came back in the 2000s from an unexpected direction. Sequencing a genome by the lengths of fragments, mapping restriction sites, and the “turnpike problem” of computer science are all the same question — recover a set from its difference multiset — and the fact that it does not always have a unique answer is a fact about all of them.

Where the ladder goes next #

Back, to the one-dimensional case and its exhaustive search: two structures, one Patterson, where the smallest example is four atoms on eight sites.

Sideways, to the construction that explains most of the cyclic pairs and carries over to the torus unchanged: where the pairs come from.

And to the reason any of it matters for an experiment: the map that needs no phases is what a Patterson is for, and whether there is a centre is a statistic is the other thing an intensity distribution can be asked, with the same limitation on what it can decide.

Which ambiguities an experiment can break #

The census treats four operations as invisible to a Patterson, and it is worth separating the ones that are permanently invisible from the one that is only invisible to this measurement.

Translation is permanent. A crystal has no origin, so a structure and its shifted copy are the same structure and no experiment can or should distinguish them.

Inversion is not permanent. It is invisible here because the calculation assumes every scatterer contributes in phase — which is Friedel’s law, and Friedel’s law is an approximation rather than a symmetry. Tune the radiation near an absorption edge of one of the elements present and that element scatters with a phase lag of its own. The two members of a Friedel pair then differ measurably, and the handedness the Patterson could not see is recovered from the difference.

So the ambiguities in this census are of two kinds, and only the sets that remain distinct after inversion is broken are homometric in the sense a crystallographer has to live with. That is the reading to carry away from the twenty-two rows: the enumeration counts what the function cannot separate, and an experiment is not restricted to one function.