Two structures, one Patterson

A diffraction experiment measures intensities, and the intensities are the Fourier coefficients of one particular function: the Patterson, which has a peak at every vector between two atoms, weighted by how many pairs share it. A structure determines its Patterson exactly. The whole of structure solution is the attempt to run that arrow backwards.

This essay is about the arrow not being invertible, and about how small the counterexample is.

The smallest case #

Work on a cycle of n positions — a one-dimensional crystal with n sites in its cell — and put k atoms on it. Enumerate every arrangement, compute the multiset of differences, and see which arrangements share one.

At n = 8 with four atoms there are eight arrangements up to translation and reflection, and they produce seven distinct vector sets. The two that collide are {0, 1, 2, 5} and {0, 1, 3, 4}.

They are called homometric, a word Patterson coined in 1939 for exactly this: different structures, same interatomic distances. Their diffraction patterns are identical in every intensity — not similar, not close, identical — so no experiment that measures intensities distinguishes them, at any resolution, with any radiation, for ever.

The object being drawn as a row of bars here is, in a real structure determination, a map in three dimensions: a peak at the end of every interatomic vector, with a large one at the origin carrying a contribution from every atom paired with itself. Working on a ring instead loses none of the argument and buys the one thing a three-dimensional map cannot give, which is exhaustiveness. There are finitely many ways to put k atoms on n sites; every one of them can be built, its vector multiset computed, and the whole list compared with itself. What comes out is not evidence that homometric pairs exist but a complete census of them at that size, and a complete census is what makes the counts below statements rather than reports.

Why a Patterson can lose information at all #

It is worth being precise about what is being thrown away, because the loss is not obvious from the definition.

A structure of k atoms on n sites carries k positions. Its Patterson carries n numbers — one count per vector — and those numbers are heavily constrained: they sum to k², they are symmetric about the origin, and the origin’s value is k. So the Patterson generally has more numbers in it than the structure does, which makes the failure look impossible until the constraint is counted properly.

The right way to see it is through the Fourier transform. The intensity at each reflection is |F|², where F is the structure factor, so measuring intensities gives the magnitudes of the structure factors and not their phases. A structure on n sites has n structure factors; the magnitudes are n numbers and the phases are another n, and the phases are exactly what the measurement discards. Half the information is missing by construction, and it is a piece of luck rather than a theorem that a structure can usually be recovered from the other half.

Homometry is what happens when the luck runs out: two structures whose structure factors have the same magnitudes and different phases.

What has to be quotiented out first #

The question only means something once two uninteresting reasons for agreement are removed, and they are worth naming because both are physics rather than bookkeeping.

Translating a structure changes nothing. Every difference between two atoms is unchanged if both move by the same vector, so the Patterson knows nothing about where the structure sits in its cell. That is the same statement as a diffraction pattern’s intensities being unchanged by a phase shift, and it is why a structure solution has to choose an origin.

Reflecting a structure changes nothing either. Reversing every vector maps the difference multiset onto itself, because for every vector between two atoms the reverse vector is also there. So a structure and its mirror image have the same Patterson — which is Friedel’s law in its simplest possible form, and the reason a Patterson map is always centrosymmetric even when the structure is not.

So arrangements are compared up to translation and reflection, and what survives is genuine indistinguishability rather than a change of coordinates.

How common it is #

Reading down that table, the answer is that homometry is not rare and not pathological. It appears at the smallest size that has room for it — four atoms on eight sites — and becomes commoner as the structures get larger: at twelve sites with six atoms, fifty arrangements produce thirty-five vector sets, so fifteen collisions among fifty.

That trend is the one to take away. A structure determination is not fighting an exotic failure; it is fighting a failure whose frequency grows with the number of atoms, and which the data cannot report.

The pair, examined #

The smallest pair rewards a closer look, because it shows that the two structures are not subtly different.

A puts its four atoms at 0, 1, 2, 5 — three in a row and one across the ring. B puts them at 0, 1, 3, 4 — two pairs, symmetrically placed. Nobody would mistake one drawing for the other.

Their vector counts, from the origin outward, are 4, 2, 1, 2, 2, 2, 1, 2 in both: sixteen vectors, which is four atoms squared, with the four at the origin and the vector across the ring occurring once in each direction. Every one of those eight numbers is the same for the two structures, and there are only eight numbers to be had.

Both members of this particular pair happen to be centrosymmetric, each about a point of its own. That is not general, and the counterexample is not far away: at twelve sites with five atoms, {0, 1, 2, 4, 7} has no centre and {0, 1, 3, 5, 6} does, and the two are homometric. A centric structure and an acentric one can share a diffraction pattern, which defeats an obvious hope — the statistical test for a centre is computed from the intensities, and the intensities are identical, so every statistic computed from them is identical too. That test decides the average case and cannot decide this one.

What saves a real structure determination #

If homometry is common, why does anybody solve structures?

Because intensities are not the only information. Four things break the tie, and all four are outside the diffraction pattern.

Chemistry. A homometric partner is generally not a chemically sensible structure — bond lengths wrong, atoms too close, coordination absurd. That is the constraint doing most of the work in practice, and it is why structure solution software is full of chemistry rather than only of Fourier transforms. It is also why the ambiguity is rarer in three dimensions than the counts here suggest: a partner has to be simultaneously homometric and chemically possible, and the second condition is very restrictive.

Positivity and atomicity. The electron density is non-negative everywhere and concentrated into sharp lumps at the atoms, neither of which the measurement enforces. Those are constraints on the solution rather than on the data, and direct methods are the machinery for exploiting them; they are what makes the phase problem soluble at all.

Resolution. The homometric pairs here are exact at every reflection, and there are only finitely many reflections for a structure on n sites, so there is no “higher resolution” left to collect. Resolution does not help against them — but real ambiguities are often only approximate, and more data separates those.

Anomalous scattering. Friedel’s law breaks when absorption is significant, and then a structure and its mirror image do differ in the measured intensities. That is how absolute configuration is determined, and it removes exactly one of the two ambiguities quotiented out above — not the homometric one.

None of them is the diffraction pattern. The pattern really does not contain the answer; something else supplies it.

That list is worth reading a second time for what is not on it, because the omissions are the useful part. A better detector is not on it. The two Pattersons agree in every one of their finitely many numbers, so counting statistics, dynamic range and detector noise are irrelevant: the ambiguity survives a perfect measurement. A better algorithm is not on it either. Every phasing method that reads only the intensities is a function of the same input, and a function returns one value; if it returns A for the pair it returns A for both members, and it has not solved the structure so much as picked one. And symmetry is not on it. The pair at twelve sites has one centrosymmetric member and one acentric one, so even the space group cannot be settled from the data — which is the strongest form of the difficulty, since a space group is usually thought of as being read off the pattern before any structure is proposed at all.

What all four of the rescues above have in common is that they are statements about what a structure may be, not about what a measurement said. The measurement narrows the field to a set of candidates; the chemistry, the positivity, the resolution and the anomalous signal pick from within it. Structure determination is therefore not inversion of a map, and the language of “solving” hides that: it is a search constrained from two directions at once, and homometry is the case where one of the two directions contributes nothing.

What the search is, exactly #

The procedure has four steps and none of them chooses anything.

Enumerate. Every k-subset of the n sites, which is a binomial number of them and a few thousand at the sizes here.

Canonicalise. Each subset is reduced to the lexicographically least of its n translates and n reflected translates, so a class is one entry and the count of arrangements is a count of structures rather than of placements.

Count vectors. For each arrangement, the multiset of all k² ordered differences, as an array of n integers. That array is the Patterson, sampled at the sites.

Group. Arrangements with identical arrays are collected, and a group of more than one is a homometric family.

Every comparison is of integers and nothing is approximate anywhere, which is what makes “these two are indistinguishable” a statement rather than an estimate. The contrast with a real experiment is total: there, two structures are indistinguishable when their calculated patterns differ by less than the noise, and the threshold is a judgement.

And the families are not always pairs. At sixteen sites with six atoms there is a family of three arrangements sharing one vector set — {0,1,2,4,6,9}, {0,1,2,4,9,14} and {0,1,3,5,7,8}. The word “pair” is the traditional one and the phenomenon is not restricted to two, which matters for a structure solver: knowing that a solution has an unseen partner is bad, and not knowing how many is worse.

What the round trip checked, and how #

A translated copy is not a second structure, and the canonical form has to identify them.

Nor is a reflected one. If reflection were not quotiented out, every asymmetric structure would appear to have a homometric partner and the count would be meaningless.

Two sets with different vectors must not be reported as a pair, which is the positive control: the comparison is of exact integer multisets, so it cannot be passed by two structures that merely look similar.

And the origin peak carries no information. Every arrangement of k atoms has exactly k vectors of length zero, so the origin’s height is the atom count, and a procedure that leaned on it would be leaning on something it already knew. In a real Patterson map that peak is the tallest feature by a wide margin and is routinely subtracted before anything else is looked at.

The same failure, in the language of the intensities #

The account above is in terms of vectors. The same statement in terms of what a diffractometer records is shorter and sharper.

Write the structure as an indicator sequence — one where there is an atom, zero where there is not — and take its discrete Fourier transform. That is the structure factor F(h), a complex number for each reflection. The intensity is |F(h)|², and the vector counts are the inverse transform of the intensities: the Patterson is the autocorrelation, and the intensities are its transform.

Two structures are homometric exactly when |F(h)| agrees at every h. So a homometric partner is what one gets by keeping every magnitude and changing some phases in a way that keeps the result a set of atoms. That last clause is the whole difficulty: almost every reassignment of phases produces something that is not a structure at all — negative densities, atoms at fractional positions — and the rare ones that do not are the homometric partners.

That reframing explains why homometry gets commoner with more atoms. More atoms means more reflections, more phases to reassign, and more chances that one of the reassignments lands on a legal structure.

Where the exactness stops #

This is one dimension and a cyclic group. A structure on a ring of n sites is a genuine crystallographic object — a one-dimensional crystal with n positions in its cell — and the search is exhaustive within it. It is not three dimensions, and the frequency of homometry there is not measured here.

The atoms are identical and the sites are discrete. Two atoms of different scattering power at the same positions give a different Patterson, so the search is over structures of one element on a lattice of sites. Real homometry in real structures is subtler and rarer for exactly that reason: the extra parameters give the pairs more ways to fail to coincide.

Homometry is exact here and approximate in practice. The pairs found are equal at every vector, so they are indistinguishable in principle. Most real ambiguities are near-misses that better data resolves, and the two situations are usually confused. This essay is about the exact kind, which no data resolves.

“Indistinguishable” means indistinguishable by intensities. A real experiment also measures where the sample is, how it absorbs, how it responds to a change of wavelength, and what it is made of. The claim proved here is narrow and exact — one function does not determine the structure — and the broad claim it is often mistaken for, that the structure cannot be found, is false and is refuted daily.

And nothing here is about symmetry. These structures have no symmetry to speak of; the ambiguity is not a symmetry of the pattern being mistaken for a symmetry of the structure, which is a different failure this collection treats elsewhere.

Who found them, and when #

A. L. Patterson introduced the function in 1934 and asked the uniqueness question almost immediately. His 1939 paper Homometric structures named the phenomenon and gave one-dimensional examples; his 1944 sequel gave the construction that produces them, which is the subject of the next essay.

The question had already been asked in another language. The one-dimensional case is the problem of reconstructing a set of integers from its difference multiset, and combinatorialists know it as the turnpike problem — given the distances between milestones on a road, where are the milestones? It is not known to be NP-hard and no polynomial algorithm is known either, which is an unusual and long-standing position for a problem this concrete.

Rosenblatt and Seymour gave the complete answer in 1982: every homometric pair arises from a factorisation of the associated polynomial, so the construction Patterson found is not merely a source of examples but the source. That is the theorem the next essay’s machinery is a special case of.

The crystallographic literature’s interest in the question has never been large, and the reason is the one above: chemistry breaks the tie in practice, so the ambiguity is a curiosity rather than an obstacle. It is a curiosity that says something exact about what a measurement contains, which is why it is here.

What it says about the phase problem #

The phase problem is usually stated as a practical difficulty: the phases are not measured, and recovering them takes work. Homometry says something stronger and less comfortable.

The phases are not merely unmeasured; they are sometimes not determined. For most structures the constraints of positivity and atomicity pin the phases down and the difficulty is computational. For a homometric family they do not, and the missing information is genuinely missing — there is no cleverer algorithm, no better detector and no longer exposure that recovers it.

That is a useful boundary to have, because it separates the two kinds of hard. Solving a structure is usually hard the way a puzzle is hard. Distinguishing a homometric pair is hard the way dividing by zero is hard.

The same problem, in a subject with no crystals in it #

The question this essay asks — recover a set of points from the multiset of distances between them — has a name and a literature outside crystallography, and knowing that it is one problem rather than two is worth a paragraph.

It is the turnpike problem: given the distances between every pair of exits on a road, reconstruct where the exits are. It arrived independently in molecular biology as the partial digest problem, where the points are the sites at which an enzyme cuts a strand and the measurements are the lengths of the fragments produced. In both settings the practical question is the same as here — is the reconstruction unique, and how is it found?

The answers transfer both ways. Non-uniqueness is homometry, and the pairs enumerated on this page are turnpike instances with more than one solution. And the algorithmic status is a genuine open question rather than a difficulty of implementation: no polynomial-time algorithm for the turnpike problem is known, and it is not known to be NP-hard either, which is an unusual position for a problem this old and this simply stated.

That is worth carrying back into the crystallographic reading. The phase problem is often described as though its difficulty were experimental — the detector records intensities and discards phases — and the turnpike framing says otherwise. Even with the vector set known exactly and completely, recovering the structure is a combinatorial problem nobody has solved efficiently, quite apart from whether the answer is unique.

Where the ladder goes next #

An exhaustive search finds pairs and does not say where they come from. They are not accidents: there is a construction that produces them on demand, it is Patterson’s own, and it explains why a structure that factors has a partner.