Where the pairs come from

An exhaustive search finds homometric structures at the smallest size that has room for them and finds more of them as the structures grow. What it does not say is why they exist — whether they are coincidences of small numbers or instances of something.

They are instances of something, and the something is a factorisation.

A structure as a polynomial #

Write a structure on n sites as a polynomial: a term xᵃ for every site a that carries an atom. So {0, 1, 3, 4} becomes 1 + x + x³ + x⁴, and multiplication of polynomials is addition of positions.

In that language the interatomic vectors are one product. Writing f*(x) for the polynomial with every exponent negated,

$$f(x)\,f^*(x) = \sum_{a,b} x^{a-b},$$

which is a term for every ordered pair of atoms — the Patterson, exactly. Two structures are homometric precisely when their polynomials give the same product.

That reframing is the whole essay, because a product is something that can be rearranged.

Reversing a factor #

Suppose f factors: f = g·h, meaning every atom’s position is a sum b + c with b from g’s positions and c from h’s, each sum arising exactly once. Now build a second structure from g and the reverse of h:

$$f_2 = g \cdot h^* .$$

Its Patterson is

$$f_2 f_2^* = (g h^*)(g^* h) = (g g^*)(h h^*) = f f^* ,$$

because reversing a factor and reversing its conjugate cancel. The two structures have the same interatomic vectors, and there is nothing subtle about the argument once the polynomials are on the page.

Why the smallest one has nine atoms #

The construction looks as though it should produce pairs immediately, and at small sizes it produces nothing. The reason is a constraint worth stating carefully, because it was met here as a search that returned zero.

A two-point set is its own reflection. The set {0, b} reversed is {0, −b}, which is the original translated by b. So if either factor has two points, reversing it changes the sumset by a translation and a reflection — and a structure translated and reflected is the same structure as far as any Patterson is concerned.

So both factors must be asymmetric: not carried onto themselves by any reflection. The smallest asymmetric set has three points — {0, 1, 3} is one, and its reflection {0, 2, 3} is a different set — so the smallest useful factorisation is three by three, and the smallest structure the construction builds has nine atoms.

That is why a search over factorisations returned nothing at four, five and six atoms while the exhaustive search was finding pairs there. The construction was not failing; it does not apply.

The example, in full #

The pair drawn above is worth writing out, because every step of the construction is visible in it.

The factors. B = {0, 1, 4} and C = {0, 2, 7}, on a ring of thirteen sites. Neither is symmetric: B reversed is {0, 9, 12}, which is {0, 3, 4} after translation, and that is not B.

The sumset. Every b + c, modulo thirteen: 0, 2, 7 from b = 0; 1, 3, 8 from b = 1; 4, 6, 11 from b = 4. Nine sums, all different, so

$$A = \{0, 1, 2, 3, 4, 6, 7, 8, 11\}.$$

The reversal. −C = {0, 11, 6}, and the sums with B are 0, 11, 6; 1, 12, 7; 4, 2, 10 — again nine different values, so

$$A' = \{0, 1, 2, 4, 6, 7, 10, 11, 12\}.$$

The check. A and A’ are not related by any rotation of the ring or any reflection — the canonical forms differ — and their vector counts are identical at all thirteen positions.

Nine atoms, two arrangements, and the only thing that changed was which way round one of the two factors was written.

The same thing as a convolution #

A crystallographer meets the construction in a more familiar form, and it is worth translating.

A sumset is a convolution. Putting a copy of the pattern C at every point of B is exactly what “every atom is a sum b + c” means, and it is how a structure with a repeated motif is described: a lattice convolved with a motif is the standard way to build a crystal on paper, and the transform of a convolution is a product.

So the construction says: take a structure made of a motif repeated at a set of positions, and reverse the motif. The lattice of positions is unchanged, every copy of the motif is turned back to front, and the interatomic vectors are the same because the vectors within a motif are unchanged by reversal and the vectors between motifs are the same set of differences either way.

Stated like that it sounds as though it should be visible to the eye, and it is not. The two structures above have different arrangements of gaps, and nothing about them announces that one is the other with a motif flipped.

How much it explains #

Running both at nine atoms on thirteen sites: the exhaustive search finds one homometric pair, and the construction builds two — one of which is that pair.

At fourteen sites the search finds six pairs and the construction accounts for three of them.

So the construction is sufficient and not necessary, at least in the form used here, and that is not a defect in it. The general theorem — Rosenblatt and Seymour, 1982 — says every homometric pair comes from a factorisation of the Patterson polynomial, but the factors are allowed to be polynomials with negative coefficients, so long as their product has coefficients that are zero and one. Those factorisations are not sumsets of sets and cannot be drawn as two smaller structures.

The pairs at four and five atoms are of that kind. They exist, they are exact, and the picture of “one structure built two ways from the same pieces” does not apply to them.

What has to be true for a set to factor #

A structure that factors is special, and it is worth asking how special, because that measures how much of the phase problem’s freedom homometry actually uses.

The sizes must multiply. A set of nine points can factor as three by three; a set of five cannot factor at all, since five is prime and a one-point factor changes nothing. So structures with a prime number of atoms are safe from this construction — though not, as the search shows, from homometry.

The sums must be distinct. Two different pairs (b, c) giving the same total collapse the sumset, and the result has two atoms on one site rather than nine on nine. In the search here roughly two of every five candidate splits are rejected for exactly that, and the rejection is not a technicality: a structure with a doubled site is a different chemical object and its Patterson is different too.

And both factors must be asymmetric, which is the condition above.

Three conditions, and the third is the one that pushes the smallest example to nine atoms. A reader who wanted to construct a homometric pair to order would start there.

What the construction says about the phase problem #

Read through the Fourier transform, the construction is a statement about phases and a short one.

The structure factor of f = g·h is the product of the transforms of g and h. Reversing h conjugates its transform, which leaves the magnitude alone and negates the phase. So

$$|F_2(h)| = |G(h)| \cdot |H^*(h)| = |G(h)| \cdot |H(h)| = |F(h)|$$

at every reflection, while the phases differ by twice the phase of H.

Homometry is a phase flip on one factor. That is the sharpest statement of what the phase problem loses: not a random assortment of information, but exactly the freedom to conjugate any factor of the structure independently. A structure that does not factor has no such freedom and no partner from this construction; a structure that factors several ways has several partners.

Who worked it out, and when #

Patterson gave the construction in 1944, in the second of his two papers on the subject, and the polynomial framing is his. He had introduced the function ten years earlier, asked the uniqueness question in 1939, and produced the mechanism five years after that — which is a reasonable pace for a question nobody else was asking.

Rosenblatt and Seymour completed it in 1982. Their theorem says the converse: every homometric pair in one dimension arises from a factorisation of the Patterson polynomial into a product of two factors, each taken in one of its two orientations. So Patterson’s construction is not one source of examples among many; it is the source, provided “factor” is read in the general sense that allows negative coefficients.

The problem has an independent life outside crystallography as the turnpike problem — reconstruct the positions of milestones from the multiset of distances between them — and the two literatures were largely unaware of one another for decades. That is why the same result has two names and two sets of examples, and why the crystallographic account tends to stop at “it can happen” while the combinatorial one asks how hard reconstruction is. It is a striking open question: the turnpike problem is not known to be NP-hard, and no polynomial algorithm for it is known either.

What a structure solver does about it #

The practical answer is short and worth having, because the theory above could be read as more alarming than it is.

Direct methods do not solve for a Patterson. They solve for phases, using positivity and atomicity and the statistical relationships between reflections, and a homometric pair is two solutions of the same phase problem rather than one solution that is ambiguous. Software will find one of them, refine it, and report a perfectly good structure.

The refinement will not warn. Both members of a homometric pair fit the data equally well at every reflection, so the residual is the same and no statistic of fit distinguishes them. What distinguishes them is chemistry — bond lengths, coordination, sensible packing — which is applied afterwards and by a person.

And genuine cases in three dimensions are rare. The construction needs a structure that factors as a sumset, which for real atoms means a motif repeated at exact positions with no other atoms in the way. Ordered alloys and some superstructures are the natural candidates, and the ambiguity is real enough there to be worth a check.

What the round trip checked, and how #

A construction that returns a translate is not a construction. Every pair the builder proposes is checked against the canonical form: if the partner is a translate or a reflection of the original it is discarded, and with two-point factors that is what happens every time.

A sumset that overlaps is not a structure. If two different pairs (b, c) give the same sum, the polynomial has a coefficient of two and the result is not a set of atoms. The builder rejects those rather than rounding them down, and roughly two in five of the splits tried are rejected for it.

The partner must actually be homometric, which is checked directly rather than trusted to the algebra: the difference multisets are computed for both and compared as integers.

And the found pairs and the built pairs must be compared. Reporting “the construction explains homometry” without measuring how many pairs it accounts for would be the interesting half of a claim with the checkable half left off.

Where the exactness stops #

Sumset factorisation is a special case. The complete theorem allows factors with negative coefficients, and this collection does not search for those. So “three of six pairs explained” is a statement about the construction implemented here and not about the theorem.

The polynomial identity is exact and the arithmetic is integer. Every step above is a multiplication of polynomials with integer coefficients, so “these two structures have the same Patterson” is settled the way this collection settles everything else — by comparing integers, with no tolerance anywhere and no appeal to how similar two computed patterns look.

One dimension again. The polynomial argument works verbatim in three dimensions with three variables, and nothing here runs it there. The reason is the search rather than the algebra: enumerating three-dimensional arrangements is a much larger problem, and a construction with no exhaustive search to compare against would be an assertion. What would be lost is not the construction but the denominator — the number of pairs there are to find — and every statement in this essay comparing built against found needs both halves. A construction that produces partners in three dimensions with nothing to compare it against would establish that homometry occurs there, which nobody doubts, and nothing about how often.

Factorisation is not unique, and neither is the partner. A structure factoring two different ways has two partners, which need not be homometric with each other in an interesting way — they are, but by the same argument rather than by a new one.

The count of built pairs is a count of constructions, not of distinct partners. Two different factorisations of the same structure can lead to the same partner, and the builder reports each construction. Where the essay compares built pairs with found pairs it is the covered number that answers the question, and it is smaller.

And a homometric partner may be chemically impossible. The construction knows nothing about atoms except their positions. It is a statement about what a Patterson determines, not a claim that both members of every pair are structures anybody would find.

The nine-atom floor is a floor for this construction and not for homometry. The smallest pair on any ring has four atoms, and it is not built here at all: four is too few to factor into two asymmetric pieces, so that pair arrives by the general mechanism instead. What the nine says is that the sumset route to a partner cannot begin sooner, because each factor must be asymmetric and the smallest asymmetric set of points has three of them. Read the other way round, that is a small piece of good news for anybody solving a structure: the tidiest way of manufacturing an ambiguity needs a structure that splits cleanly into two smaller ones, and most structures do not.

The construction as a statement about symmetry #

There is one more reading of the same identity, and it connects this to the rest of the collection.

Reversing a factor is applying an inversion to part of a structure. So the construction says: a structure built as a motif repeated at positions has a partner got by inverting the motif and leaving the positions, and the two are indistinguishable by intensities.

That is Friedel’s law applied to a piece of a structure rather than to the whole of it. Friedel’s law says a structure and its complete inversion are indistinguishable; the construction says that when the structure factors, the inversion can be applied to one factor only and the indistinguishability survives.

Whole-structure inversion is always available; partial inversion needs a factorisation. The first is a theorem about every structure and produces nothing new, since a structure and its mirror image are the same structure up to handedness. The second produces a genuinely different structure, and it is available only sometimes.

Seen that way homometry stops being an oddity and becomes the natural extension of a law every crystallographer knows. The surprise is not that it happens; it is that whole-structure inversion was ever thought to be the end of the story.

Where the ladder goes next #

Homometry is the diffraction pattern failing to determine the structure while remaining perfectly sharp. The other way a diffraction measurement can be uninformative is statistical rather than exact — the intensity distribution decides whether a structure has a centre without any single reflection deciding anything — and it is the one place on this site where a claim is settled by a distribution rather than by an integer.

Every factorisation, not just the ones with two factors #

The construction reverses one factor of a product of two, and a polynomial of any size factors into more than two pieces. Following that through gives the complete answer for a chain, and it is larger than this essay’s examples suggest.

Factor the polynomial into irreducibles. Over the complex numbers a polynomial of degree $n$ factors into $n$ linear pieces, one per root, and reversing a factor means replacing a root by the reciprocal of its conjugate — reflecting it across the unit circle.

The Patterson does not see the reflection. The product $f f^*$ is unchanged when any root is exchanged for its reflected partner, because the reflection moves a factor from $f$ into $f^*$ and moves the corresponding factor the other way.

So the ambiguity is a choice per root. A structure with $n$ roots off the unit circle has up to $2^n$ different structures sharing its Patterson — an enormous number, most of which are discarded because they fail to have the coefficients a structure needs. The pairs this essay constructs are the smallest surviving instances of a much larger ambiguity.

That is the phase problem in one dimension, stated exactly. Knowing $|f|$ on the unit circle is knowing $ff^*$, and the roots can be flipped freely, so the phases are not determined by the amplitudes at all — not approximately, not up to a symmetry, but genuinely underdetermined by an exponential factor.

Why two dimensions is not like this #

The situation in the plane and in space is completely different, and the reason is a fact about polynomials rather than about crystals.

A structure in two dimensions is a polynomial in two variables. The same argument would run if such a polynomial factored, and generically it does not: a polynomial in one variable always factors into linear pieces, and a polynomial in several variables is almost always irreducible.

An irreducible polynomial has nothing to flip. With no non-trivial factorisation, the only ambiguities left are the trivial ones — a translation, and reversing the whole structure, which is the inversion the Patterson always adds.

So phase retrieval is essentially unique in two dimensions and hopeless in one. That is the standing result of the subject, and it is why an image can be recovered from the modulus of its transform while a signal cannot, and why the homometric structures this collection enumerates are exotic curiosities rather than the normal state of affairs.

The chains on this page are therefore the exceptional case made concrete. They are the structures whose polynomials happen to factor, in a setting where factoring is the rule rather than the exception — which is precisely why the smallest of them has to be assembled from two three-point sets and cannot be smaller.