The formula that has the answer already

A triplet’s phase sum is near zero when its three amplitudes are large. A structure with a few hundred strong reflections has tens of thousands of such near-determinations, which is far more constraints than unknowns. Turning that surplus into a structure sounds like arithmetic.

It is not, and this essay is about why.

The formula #

Write the relation the other way round. If $\varphi_k + \varphi_{h-k}$ is approximately φ_h for every k, then a sensible estimate of φ_h is a weighted average of those sums — weighted by how much each is to be believed, which is by κ. Averaging angles means averaging their unit vectors, so:

$$\tan \varphi_{\mathbf{h}} \;=\; \frac{\sum_{\mathbf{k}} \kappa \sin(\varphi_{\mathbf{k}} + \varphi_{\mathbf{h}-\mathbf{k}})}{\sum_{\mathbf{k}} \kappa \cos(\varphi_{\mathbf{k}} + \varphi_{\mathbf{h}-\mathbf{k}})}$$

That is the tangent formula, from Karle and Hauptman in 1956, and it is the engine of every direct-methods program written since. Iterate it over all the strong reflections until nothing moves.

The gap between those two rows is the whole problem. A formula with the answer as a fixed point is not a procedure for finding it. There are other fixed points, some of them stronger attractors, and the iteration finds those.

The attractor that is not a structure #

The strongest of the wrong fixed points is easy to identify and it is the reason the whole subject is harder than it looks.

Set every phase to the same value — zero, say. Then every triplet is exactly zero, every relation is satisfied perfectly, and the formula returns what it was given. It is a fixed point with perfect self-consistency, and it corresponds to a density that is a single sharp peak at the origin: every wave in phase at one point and cancelling everywhere else.

That is a legitimate non-negative density and a terrible structure. Nothing in the triplet relations excludes it, because it satisfies all of them.

What a procedure does instead #

Since the iteration cannot be trusted to arrive, the procedure is not an iteration. It is a search, and it has three parts.

Fix the origin. A few reflections are chosen and their phases assigned arbitrarily, which is allowed because a phase is a property of the description. Not any few will do: the chosen reflections must have index parities that between them pin down every half-cell shift, or the assignment fixes nothing. In two dimensions there are four possible origins for a centrosymmetric structure — the shifts by half a cell in each direction — and two reflections of independent odd parity are enough. The count of origins is the same one a normaliser reports for the group.

Try many starts. The remaining phases are set to values chosen at random or from a small enumerated set, and the formula is iterated to a fixed point. Different starts reach different fixed points. Sixty starts, a few hundred, a few thousand: the number is a resource decision.

Rank the results by something that does not know the answer. This is the part that matters, and it is called a figure of merit. It plays the part a stated refusal plays elsewhere in this collection: a test the machinery can fail on its own.

Figures of merit, and the first one anybody writes down #

The obvious figure is self-consistency: how well the relations are satisfied by the answer the run produced. It is computed from the phases and the amplitudes, and the true structure is nowhere in it.

On the larger cell it fails, and the failure is not marginal: the top three runs by consistency are the uniform solution, and the run that is ninety per cent right is not near the top. The figure is doing exactly what it was asked to do and what it was asked for was wrong.

That is the honest state of this computation, and it matches the history. Direct methods needed not one figure of merit but a battery of them, developed over two decades, each catching a different kind of wrong answer:

• rejecting the uniform solution, by requiring the phases to be spread;
• negative quartets, which say not zero for four-phase invariants whose cross terms are weak, and which the uniform solution violates badly;
• the Ψ₀ figure, which asks that reflections known to be weak come out weak from the phase set — a structure predicts its own zeros, and a false solution does not.

Only the first of those is computed here, and what it recovers is worth measuring rather than assuming.

Necessary and nowhere near sufficient is the honest verdict on it. Rejecting the uniform solution removes the answer that is obviously wrong and leaves the ranking almost as bad as it was, because the runs immediately below the uniform one are not the good runs either — they are other consistent nonsense. The other two figures are named here because without them the picture above would suggest that direct methods do not work, and they do: the missing ingredients are the ones that took the twenty years.

Why the search is over starts rather than over phases #

A reader who has met optimisation will ask why nobody simply minimises something. The reason is worth stating.

The quantity to be minimised — disagreement with the triplet relations — is a function on a torus of a few hundred dimensions with an enormous number of local minima, of which the deepest is the single peak. Gradient descent from a random start is precisely the tangent-formula iteration, and it is what the figures above show.

So the search is combinatorial rather than continuous, and its unit is a starting set rather than a step. The classical version enumerates a handful of phases over a coarse grid — magic integers, a compression trick that samples a handful of phase angles with one parameter — and iterates from each. Modern programs do something closer to simulated annealing in real space, alternating between a density map and a phase set.

Why the alternation helps is that the constraints live in different spaces. Positivity and atomicity are statements about the map: the density is never negative and it is concentrated in small blobs. The amplitudes are statements about the transform: each one is a measured number. Imposing a real-space constraint on a phase set means transforming, editing the map, and transforming back, and imposing an amplitude constraint means overwriting the moduli and keeping the phases. Each is one line where it is cheap and a nightmare where it is not, so a procedure that alternates between the two spaces does each in the space that suits it. That is charge flipping, and it is what every modern solver does under one name or another.

Why fixing the origin is not optional #

It would be reasonable to think that origin fixing is a tidying-up step — that the phases come out determined up to a shift and the shift can be sorted out afterwards. It cannot, and the reason is a good one.

Without the origin fixed there is no unique answer for the iteration to converge to. Every shift of the origin gives a phase set that satisfies the relations equally well, so the iteration has a continuum of fixed points related by shifts, and a run may wander among them. Worse, the comparison between runs becomes meaningless: two runs that found the same structure at different origins look completely different in their phase lists.

And measuring the error becomes meaningless too. Comparing a computed phase set with the true one without allowing for a shift measures the arbitrariness of the origin and calls it an error. Every error figure in this essay is therefore minimised over all origins and over both enantiomorphs before it is reported, which is not generosity: it is the only comparison that means anything.

For a centrosymmetric structure in the plane, the origins are the four half-cell shifts, and shifting by half a cell in one direction flips the sign of every reflection with an odd index in that direction. So a reflection’s parity class — whether each index is odd or even — says which shifts can change its sign, and two reflections from two different odd classes fix the origin completely. That is the choice the procedure here makes, and it makes it before any relation is used.

The shape of a modern solver #

Direct methods as described here — triplets, tangent formula, multisolution, figures of merit — is the 1970s form, and it is worth saying what replaced it, because the replacement is the same idea with the search rearranged.

Shake-and-Bake, from the 1990s, alternates a phase-refinement step with a real-space step in which the map is peak-picked and rebuilt from the peaks alone. The real-space step is where atomicity enters directly rather than through a statistical relation, and it is far stronger. Structures of a thousand atoms became routine.

Charge flipping, from 2004, is simpler still: compute a map, reverse the sign of everything below a small threshold, transform back, keep the new phases and the measured amplitudes, repeat. It has no triplets in it at all, requires almost no symmetry information, and works.

Both are the same lever. Local information about the density, imposed where it is cheap; global information about the amplitudes, imposed where it is cheap; and an alternation between the two. What the tangent formula does in one space, they do by moving between two.

What the procedure is really exploiting #

Standing back from the machinery, the constraint being used is the same one throughout, and it is worth naming.

Positivity and atomicity are local facts. They are statements about what the density looks like near a point: never negative, and concentrated in small blobs. Neither says anything about where the blobs are.

The phases are global. A phase is a property of a wave that spans the crystal, and no local inspection produces one.

Direct methods are the lever between them. The lever exists, its mechanical advantage is √N and shrinks as the structure grows, and using it requires a search whose difficulty is not in the physics at all but in telling a plausible answer from a true one without being told.

Where it stops working #

Three limits, all arithmetic.

Size. The concentration goes as $N^{-1/2}$, so a structure of a thousand atoms has relations a fifth as strong as one of forty. Direct methods handle a few hundred atoms comfortably and a few thousand with effort, and the effort is in the search rather than in the formula.

That is the whole of the size limit, stated as a number rather than as a warning. Nothing about the relations changes as a structure grows; there are more of them, and each is weaker, and the two effects do not cancel. A cell of a thousand atoms has perhaps a hundred times as many strong triplets as a cell of forty and each is a fifth as trustworthy, so what has to be searched grows and what each constraint contributes shrinks. That is why the effort moved into the search and stayed there.

Resolution. The relations need E values, and E values need a well-determined mean intensity at each resolution — so data that stop before atomic resolution give amplitudes that cannot be normalised meaningfully. A structure whose atoms are not resolved from each other is not, at that resolution, a sum of sharp peaks — the map is the structure convolved with the transform of the sphere, and the premise fails rather than the arithmetic.

Equal atoms. A structure with one very heavy atom has a strong relation between every triplet and can be solved by Patterson methods instead. A structure of atoms of similar weight is the hard and the ordinary case, and direct methods were built for it.

And the competitor for those cases is the Patterson map, which estimates no phase anywhere and answers a different question: the vector set rather than the structure. For a crystal with one atom much heavier than the rest that is enough on its own, because the strongest non-origin peak is the heavy–heavy vector and the phases follow from the heavy atom’s position. Direct methods are for the case where no atom stands out, which is the ordinary case in organic chemistry and the reason they were built at all.

What is owned here #

The tangent formula, implemented and iterated; the measurement of its behaviour at the true phases and from random starts; sign propagation with origin fixing; the multisolution run and the self-consistency figure of merit; and the demonstration that the figure ranks correctly on a small cell and not on a larger one.

Not owned: quartet figures of merit, the Ψ₀ figure, magic integers, charge flipping, or any real structure determination. This is the arithmetic of a procedure, run on structures whose answers were known in advance so that its failures could be seen.

Why the trivial solution is not a bug #

The uniform phase set is usually described as something to be excluded, which makes it sound like a defect in the formulation. It is not.

A single sharp peak is a perfectly good non-negative density made of one atom, and every constraint direct methods use is satisfied by it exactly. Nothing has gone wrong: the constraints simply do not distinguish a structure of forty atoms from a structure of one, because both are non-negative and both are atomic.

What distinguishes them is a fact nobody has used yet: how many atoms there are. The scattering says so — the mean intensity in a shell is the sum over the content — and a phase set corresponding to one peak predicts intensities that fall off far more slowly than the measured ones do. That is the observation the Ψ₀ figure of merit turns into a number, and it is why the exclusion is a measurement rather than a stipulation.

How many reflections the origin costs, and why it is a small number #

Origin fixing is stated above as a step and not as a quantity, and the quantity is worth having, because it says how much of the answer is being assumed.

The origins a group permits form a finite set — the shifts that carry the symmetry elements onto themselves — and choosing one is choosing enough phases to pin the rest. In the plane with a primitive lattice and a centre, the allowed shifts are the four half-cell translations, so two reflections with suitable index parities fix the origin completely and every other phase is then determined relative to them.

Two out of a few hundred is a small assumption, and that is the point. It is not that the procedure is given part of the answer; it is that part of the answer does not exist until a coordinate system does, and the two phases assigned are the coordinate system. Assigning them wrongly is impossible — any consistent choice is a legal origin — which is exactly what distinguishes this step from a guess.

What can go wrong is choosing reflections that do not fix it. A pair whose parities coincide leaves a shift undetermined, so the iteration retains a degree of freedom and its self-consistency figure improves for a reason that has nothing to do with the structure. Programs choose the origin-fixing set by an explicit rule on index parities for that reason, rather than by taking the strongest reflections available.

The centrosymmetric case is a decoding problem #

There is a reformulation of the small case that makes the difficulty recognisable, and it is worth having because it names the shape of the search rather than describing it.

In a centrosymmetric structure every phase is 0 or π, so each reflection carries a sign. The triplet relation says the product of three signs is probably +1, with a probability that rises with the three amplitudes. So the problem is: given several thousand noisy assertions of the form these three bits multiply to one, recover the bits.

That is a decoding problem. Noisy parity constraints over a sparse set of variables are what a low-density parity-check code is made of, and the standard method for solving them — passing probabilistic messages back and forth along the constraints until they agree — is very nearly what the tangent formula does when it is run with proper weights. The formula’s sin and cos sums are a circular mean of the estimates each triplet supplies, and the amplitudes are the confidences.

The framing explains two things the ad-hoc account leaves mysterious. Why iteration works at all — because message passing on a sparse constraint graph usually converges when the constraints are individually weak and collectively numerous, which is exactly the regime $N^{-1/2}$ puts a small structure in. And why it stops working with size — because the constraints weaken as the structure grows while their number grows only linearly with the reflections, so the code’s rate rises past what its noise permits.

It also says what the multisolution search is: a decoder that has no guarantee of finding the codeword, restarted from many points, with a figure of merit standing in for the check that a decoder would ordinarily have. Naming it that way makes the missing ingredient obvious — a real decoder verifies its answer against a checksum the sender computed, and a structure determination has no sender.

One more thing follows from reading it that way, and it is about what a figure of merit can be. A decoder’s checksum is external — it was computed from the message before the noise was added, and agreeing with it is evidence of nothing but correctness. Every figure of merit available to a structure determination is internal: it is computed from the same amplitudes the phases were derived from, so a phase set can score well by satisfying the relations it was built to satisfy. That is why the self-consistency figure fails on the larger cell rather than merely becoming noisier, and it is why the figures that work in practice — negative quartets, the entropy of the map, the flatness of its background — are the ones drawing on something the tangent formula did not use.

Where the ladder goes next #

Down, to the quantity that needs no phases at all and is computed before any of this: the average intensity in a resolution shell, which knows what the atoms are and not where they are, and which supplies the normalisation every E value in this essay depends on.

Across, to the other route out of the phase problem. The Patterson function uses intensities and no phases whatever, gives the vector set rather than the structure, and was solving structures thirty years before anybody believed a phase could be estimated at all.