The planes a recurrence cannot leave

The operation set is two arithmetic steps: multiply by a fixed number, add another, and take the remainder on division by a third. Iterate. The question is the one this field always asks, and the answer is unexpectedly sharp.

One value at a time, the sequence is unimpeachable: it visits every one of the two hundred and fifty-six residues exactly once before repeating, so any test that counts how often each value appears finds a perfectly flat answer — flatter, in fact, than genuine randomness would produce, which leaves gaps and repeats. Two values at a time, the structure is unmistakable.

Where the lines come from #

The recurrence is $x_{n+1} \equiv a x_n + c \pmod m$, and everything follows from it being linear.

Suppose whole numbers $q_0$ and $q_1$ can be found with $q_0 + q_1 a \equiv 0 \pmod m$. Then for every $n$,

$$q_0 x_n + q_1 (x_{n+1} - c) \equiv (q_0 + q_1 a) x_n \equiv 0 \pmod m,$$

so the quantity on the left is an exact multiple of $m$ at every step of the sequence. That is the equation of a family of parallel lines, spaced by $m$ along the direction $q$, and every point of the sequence lies on one of them.

There is always such a vector — take $q_1 = 1$ and $q_0 = -a$ — and the interesting question is how short one can be made. A short vector means widely spaced lines, few of them, and an obvious lattice; a long one means the lines are so close together and so numerous that the points look scattered. Finding the shortest such vector is the spectral test, and it is what the figures perform.

The contrast is the whole argument. A generator with a small multiplier has a very short relation — for a multiplier of five, the vector $(-5, 1)$ works immediately — and the points collapse onto a handful of lines. Nothing about the sequence’s one-at-a-time behaviour changes; the failure is entirely in the pairs.

Full period says nothing about this #

There is a clean criterion for the sequence visiting every residue before repeating, and it is worth having because it is what most people check.

The conditions are Hull and Dobell’s: the increment must be coprime to the modulus, the multiplier minus one must be divisible by every prime factor of the modulus, and if four divides the modulus then four must divide the multiplier minus one. Meet all three and the sequence has the full period; miss one and it does not.

That criterion is about divisibility, and the lattice is about the size of a short vector. They are independent. Both multipliers in the comparison above have the full period, and one of them is useless in two dimensions. Passing the period test is a necessary condition that carries no information about the structure the sequence has.

Three at a time #

Two dimensions is generous. The relation exists in every dimension, and in three it is the classic disaster.

The generator is RANDU, with multiplier $65539 = 2^{16} + 3$ and modulus $2^{31}$. Squaring the multiplier gives $2^{32} + 6\cdot 2^{16} + 9$, and modulo $2^{31}$ the first term vanishes, leaving $6 \cdot 2^{16} + 9 = 6a - 9$. So

$$x_{n+2} \equiv 6x_{n+1} - 9x_n \pmod{2^{31}},$$

which is a relation with coefficients nine, six and one — extremely short. Every triple of consecutive outputs lies on one of fifteen parallel planes in the unit cube, and any simulation that used three consecutive values as a point in space was sampling from fifteen sheets of paper.

The angle in the figure is not a lucky viewpoint. A plane is seen as a line exactly when the line of sight lies inside it, so the camera is aimed by solving for the direction that puts the relation’s normal vector in the screen — three lines of trigonometry, checked by requiring the rotated normal to have no depth component. From a generic angle the same fifteen hundred points look like a cube full of dots and prove nothing.

The same relation at a different modulus #

The structure is not an artefact of the particular numbers, and the quickest way to see that is to change all of them.

Raising the modulus makes the lattice finer, which makes the lines closer together and more numerous, which makes the picture look more like a scatter. It does not remove the lines, and the count of them is exactly what the spectral test reports.

Between those two is every generator anybody has ever used. The visibility of the structure is a matter of how large the modulus is relative to how many points are drawn; the presence of it is a matter of the recurrence being linear, and that does not vary.

Why the failure is structural #

It is tempting to read this as a badly chosen multiplier, and to conclude that a better one would fix it. A better one improves it and cannot fix it, and the reason is a counting argument.

The full sequence of pairs, over one period, is $m$ points in a grid of $m^2$ cells — a fraction $1/m$ of the available positions. Those points form a lattice, because the recurrence is linear, and a lattice of $m$ points in the unit square has a shortest vector whose length is bounded: no lattice can be more evenly spread than a triangular one, and that bound puts a ceiling on how many lines the points can be spread over.

So the number of lines is bounded above by something like $\sqrt{m}$, no matter what the multiplier is, and the number of planes in three dimensions by something like $m^{1/3}$. For a modulus of $2^{31}$ that is about two thousand planes at the very best, and RANDU achieved fifteen. Choosing the multiplier well buys two orders of magnitude and does not change the shape of the answer.

The bound is a statement about lattices rather than about generators, and it is the same kind of statement that decides which integers are sums of two squares: both count lattice points against an area, and both are settled by the shortest vector rather than by anything about the numbers that produced the lattice.

That is the honest statement of what this operation set can and cannot build. It can build a sequence with a long period and a flat distribution of single values. It cannot build one whose consecutive tuples avoid lying on a bounded number of hyperplanes, because linearity forces a lattice and a lattice has a shortest vector.

What the period criterion is really about #

The three conditions deserve a paragraph of their own, because the reason they work is a piece of arithmetic worth having and it is not obvious from the statement.

The sequence visits every residue exactly when the map $x \mapsto ax + c$ is a single cycle on all $m$ residues. Suppose first that $m$ is a power of a prime $p$. Then $c$ must be coprime to $m$, or the sequence never leaves the multiples of $p$; and the multiplier condition says $a \equiv 1$ modulo $p$, which makes the map a translation-like shift at the top level and forces it to work its way through the residues rather than settling into a shorter orbit.

The extra clause about four is the exception that always turns up when the prime is two. Modulo four, $a \equiv 1 \pmod 2$ leaves two possibilities, and one of them — $a \equiv 3$ — gives a map whose square is the identity plus a shift, halving the period. Requiring $a \equiv 1 \pmod 4$ rules it out.

For a general modulus the sequence decomposes into its prime-power parts by the Chinese remainder theorem, and the full period is the product of the parts’ periods only when they are pairwise coprime — which is why the criterion is stated prime by prime.

None of that touches the lattice. The criterion is a statement about the orbit of the map and the lattice is a statement about its linearity, and a map can have a perfect orbit and a terrible linear structure. The figure that draws both is drawing two independent facts about the same three numbers.

Where it fails, and what it needs #

The exact arithmetic matters. Every claim above is that a certain quantity is exactly a multiple of the modulus, and the figures keep the products inside the range where whole-number arithmetic is exact, checking that they do rather than assuming it. A generator whose products overflow silently is a different generator.

The period is the count of states, not a measure of quality. A modulus of $2^{31}$ gives a period of about two billion, which sounds ample and is the wrong quantity: the sequence of pairs has the same period, and those two billion pairs sit on a few tens of thousands of lines. The number worth quoting is the spacing of the lattice, not the length of the walk. This is an instance of a habit worth resisting generally — quoting the size of a state space when the question is about the shape of what fills it.

A short vector is found by search, and the search has a bound. The figures look for vectors with entries up to a fixed size; a generator whose shortest relation had larger entries would be reported as having no relation within the range searched, which is a statement about the search. For the moduli drawn here the shortest vectors are small and the bound is comfortable.

The increment shifts the lattice and does not change it. Adding $c$ at each step translates the whole family of lines and leaves their number and spacing alone, which is why the relation above is stated for the differences. A generator with a non-zero increment and one with zero have the same lattice structure and different offsets.

And the lines are a property of the whole period. The figures draw a full period, so the lattice is complete. A short run from a long-period generator shows a scattering of points on a subset of the lines, and the structure is present without being visible — which is the situation everybody who has ever used one of these has actually been in.

Where it came from #

Lehmer proposed the multiplicative version in 1949, as a way of producing numbers for computation on machines with very little memory: the whole state is one number, and the step is one multiplication. It is hard to overstate how well suited that is to a machine of the time, and the method is still the fastest thing available if the state must be a single word.

The lattice structure was found by Marsaglia in 1968, in a three-page paper titled Random numbers fall mainly in the planes, and the effect on the field was immediate — the paper is one of the few in the subject that changed practice within a year. RANDU had by then been in use for a decade, and an unknown quantity of published simulation work had sampled three-dimensional points from fifteen planes.

The spectral test itself, as the standard way of grading a generator, is Coveyou and Macpherson’s from 1967, refined by Knuth. It is worth noticing what kind of test it is: not a statistical test run on output, but an exact computation on the multiplier and modulus, performed before any number is generated. That is the difference between asking whether a sequence looks random and asking what the operation set can build. The first question is answered by a test that can only ever fail to reject; the second is answered by exact arithmetic on three numbers, and settles the matter before a single output exists. It is the same distinction the constructibility arguments rest on — a search that finds nothing is evidence, and a degree computation is a proof.

What the pictures cannot show #

The two-dimensional figures use a modulus of two hundred and fifty-six so that a full period fits on a page as visible dots. Real generators have moduli in the billions, their lattices are correspondingly fine, and the same structure is invisible at any drawable scale — which is exactly why it went unnoticed for twenty years.

The three-dimensional figure is drawn from the one angle that reveals the planes, and says so. From every other angle the picture is a cube of dots, and a reader who rotated it would conclude there was nothing to see.

And no figure here demonstrates that a generator is good. Everything above is a way of showing structure, and the absence of structure is not something a picture can establish — the best available statement is that the shortest relation is long, which is a bound found by a bounded search.

The ladder from here #

Below: numbers that wrap, where modular arithmetic is set up, and what two points can build, where an operation set’s reach is first asked about. Sideways: every fraction exactly once, another sequence that visits everything and is nothing like random, and how long until every one turns up, which is what a genuinely random sequence would do instead of visiting each value once. Above: lattice reduction, the spectral test in higher dimensions, and the non-linear generators built to escape this.

What is worth carrying away #

A sequence can pass every test of a kind and fail comprehensively at the next kind up. Counting how often each value appears is a one-dimensional test; the failure here is two-dimensional and invisible to every one-dimensional test there is.

The reason is worth generalising past this example. A rule that is linear has consequences that survive iteration, because linear relations compose into linear relations. Anything built from a linear rule inherits a lattice, and a lattice is the most structured thing a set of points can be. Escaping that requires a non-linear step, and paying for it — which is the trade every generator written since has had to make.