A grid of bits whose rank stops at the state

Square it and keep the middle closed on a warning that Donald Knuth tells against himself: complexity is not randomness, and a rule that looks complicated can fail a simple test immediately. The converse is also true and more useful. A rule can look simple — a few shifts and exclusive-ors on a word of memory — and pass dozens of statistical tests, because its weakness is invisible to every test that asks about frequencies. Such a rule fails one particular test absolutely, and the reason is a fact about linear algebra. No sample size is needed to see it.

The test is the binary matrix rank test. Take a square grid of $L$ rows and $L$ columns, fill each row with the next $L$ bits from a source of random-looking bits, and compute the grid’s rank over the field with two elements, where $1 + 1 = 0$. That is the number of rows that cannot be written as sums of other rows. George Marsaglia put the test into his DIEHARD battery in 1995 with grids of 31 and 32, and it remains in the standard batteries because it catches a large family of fast generators that pass nearly everything else.

The rank of a random grid #

The first thing the test needs is what a random grid looks like. A grid of independent fair bits has full rank with a definite probability, and so does each shortfall. For a large grid the chances are

$$\Pr(\text{rank} = L - k) \to 2^{-k^2}\, \frac{\prod_{i > k}(1 - 2^{-i})}{\prod_{i=1}^{k}(1 - 2^{-i})},$$

which gives $0.2888$ for full rank, $0.5776$ for one short, $0.1284$ for two short and $0.0053$ for three. The formula comes from building the grid one row at a time. A new row raises the rank unless it falls in the span of the rows already there, and a span of dimension $d$ catches a random row with chance $2^{d - L}$. The last few rows are the ones at risk.

The law has a feature that surprises people meeting it for the first time: a random square grid of bits is more often one short of full rank than full. Independent rows are linearly dependent with probability near three-quarters. That is a property of the two-element field, where there are few enough vectors that a span of dimension $L - 1$ holds half of all possible rows. Over the real numbers a random square matrix is singular with probability zero.

The test itself is simple. Fill many grids, count how often each shortfall occurs, and compare the counts with the law by a chi-square statistic. A generator that produces genuinely mixed bits gives counts within sampling error of the law, as the one with multiplications does here.

Full rank, one row at a time #

The constant $0.2888$ can be built by hand, and building it shows where the test’s sensitivity lies. Add the grid’s rows one at a time and ask, at each step, whether the new row raises the rank. The first row does unless it is all zeros, which has chance $2^{-L}$. If the first $i$ rows are independent, they span $2^i$ of the $2^L$ possible rows, and a new random row falls among them with chance $2^{i - L}$. So all $L$ rows are independent with chance

$$\Bigl(1 - 2^{-L}\Bigr)\Bigl(1 - 2^{-L+1}\Bigr)\cdots\Bigl(1 - \tfrac14\Bigr)\Bigl(1 - \tfrac12\Bigr).$$

The early factors are all but one. The last row survives with chance a half and the one before with three-quarters, and the infinite product of all of them is $0.2888$. Nearly all of the test’s information comes from the last few rows, the ones that land in a space already almost full. A generator whose bits are subtly correlated will show it there first, as an excess or a shortage of grids that end one or two short.

That is also why the test is cheap and why Marsaglia used grids of only 31 and 32. A modest grid already puts the generator’s late rows under maximum pressure. Testing a linear generator above its state is a different matter, because the grid must then be larger than the state, and for the twister that means hundreds of millions of bits per grid.

Every linear generator stops at its state #

Now fill grids from generators whose every step is linear over the two-element field. A shift register keeps $k$ bits and makes each new bit the exclusive-or of some earlier ones, which is the machine a memory of four bits ran by hand. An xorshift keeps a 32- or 64-bit word and updates it by shifting copies of it left and right and combining them with exclusive-or. The Mersenne twister of nineteen thousand bits of state keeps 19,937 bits and updates them the same way. Each step of each of these is a linear map on its state, a $k$-by-$k$ matrix over the two-element field.

Each source tracks the diagonal, up to the usual one or two short, until the grid size reaches its number of state bits. Then it stops, exactly, and stays there. A 17-bit register gives rank 17 for every grid from 24 to 160. A 32-bit xorshift gives 32 for every grid from 40 up, an 89-bit register 89, and the lowest bit of xorshift128+ 128. Above the state size the rank test does not merely fail these generators; it fails them with certainty, on every grid, and no amount of statistics is needed to say so.

The argument is a single line. Suppose the generator’s state is $k$ bits and every step is linear. Then each output bit is a linear function of the state at the start of the row, and the whole row of $L$ bits is a fixed linear map $M$, the same for every row, applied to that starting state. Every row therefore lies in the image of $M$. The image of a map from a $k$-dimensional space has dimension at most $k$, so the rows span at most $k$ dimensions, and the grid’s rank is at most $k$, whatever $L$ is.

That is rank and nullity applied to a generator, and its force is that it says nothing about any particular grid. It holds for every seed, every grid and every size above $k$ at once. Below $k$ the map $M$ can be onto, and for a well-designed generator it is, so small grids look exactly as random as they should.

The recurrence inside every row #

The same fact can be watched in the bits themselves.

In a shift register with five bits of state and the rule $x_{n+5} = x_n + x_{n+3}$, every bit from the sixth on is the sum of the bits five places and two places before it. The rule holds everywhere in the stream, so it holds inside every row of the grid. The sixth column is the first plus the fourth, the seventh is the second plus the fifth, and so on across, and only the first five columns can contribute anything new. The grid has rank five, and it would have rank five at any size.

This is the same mechanism as the general argument, seen from the other side. A linear generator’s output satisfies a linear recurrence whose length is at most the state size, and the recurrence ties every column beyond the first $k$ to earlier ones. The length of the shortest such recurrence is the stream’s linear complexity. The Berlekamp–Massey algorithm finds it from twice that many bits of output, as a memory of four bits described. So the rank test and the linear-complexity test measure one quantity. One reads it from the columns of a grid, the other from the stream directly.

A test passed for nineteen thousand bits #

The Mersenne twister is linear, so it fails the rank test — but only on grids of more than 19,937 rows and columns, about four hundred million bits each. Smaller grids, including every grid in Marsaglia’s original battery, it passes perfectly, because its linear map is onto at every size up to its state. That is not a flaw in the test. It is the same property that makes the twister equidistributed in 623 dimensions, seen from the other side: equidistribution is the statement that $M$ is onto at small sizes, and the rank ceiling is the statement that it cannot be onto at large ones.

The statistical batteries that came after DIEHARD added larger sizes precisely to catch this. Pierre L’Ecuyer and Richard Simard’s TestU01 includes rank tests on grids thousands of bits wide and a linear-complexity test on long streams. Every random-number source built entirely from shifts and exclusive-ors fails them once the size passes its state, and the twister, whose state is too large for the grids, is caught by the linear-complexity test instead. The twister’s final scrambling step, the tempering, does not help, because tempering is itself linear and composes with $M$ into another linear map of the same rank.

For most simulations this failure rarely matters, and it is worth being clear about why. Few simulations depend on linear relations among twenty thousand bits, and a quantity that is not itself a linear function of the bits averages over the structure rather than amplifying it. But it matters in exactly the computations that are themselves linear over the two-element field — random matrices modulo 2, error-correcting codes, certain lattice models — where a generator’s structure and the computation’s structure can line up and produce answers that are confidently wrong.

The bit that an addition leaves linear #

The cure for linearity is a nonlinear operation, and the cheapest one a processor offers is ordinary addition. Sebastiano Vigna’s xorshift128+ keeps two 64-bit words, updates them by shifts and exclusive-ors, and outputs their sum. The sum is not linear over the two-element field, because carries are products — the carry out of the lowest bit is $a_0 b_0$, the bitwise AND — and products are not sums.

Every bit position passes except one. The lowest bit of a sum receives no carry. It is simply the exclusive-or of the two lowest bits, so it is still a linear function of the 128-bit state, and grids built from it have rank exactly 128. Bit 1 receives a single carry, the product of the two lowest state bits. That one product is enough to make its grids nearly full rank. Every higher bit accumulates carries from all the bits below it and passes easily.

This is a known weakness. The lowest bits of xorshift128+ fail the large rank and linear-complexity tests, and Vigna’s documentation says so and recommends using the upper bits. It is also a precise one: the failure is in one bit out of sixty-four, at one size, for one reason. A generator that multiplies instead of adds is affected in a similar way, since the lowest bit of a product of an odd constant and $x$ is the lowest bit of $x$. That is why the multiplied xorshift in the hero figure reads its bit from the middle of the product, where every bit of the state has had a chance to mix.

The verdict at one size #

A single test at a single size shows the whole pattern.

At $L = 40$ the 32-bit xorshift fails on every grid, since forty exceeds its thirty-two bits of state. The 89-bit register and the lowest bit of xorshift128+ pass, with chi-square statistics of 6.0 and 3.7 on three degrees of freedom, because forty is less than their states. The multiplied xorshift and bit 40 of xorshift128+ pass because they are not linear at all.

The verdict therefore says less than it seems to. A pass at $L = 40$ certifies nothing about the 89-bit register at $L = 90$, where it would fail every grid. A rank test at one size is a test of whether the state is larger than that size, and for a linear generator the outcome is known before the test is run. Where the test earns its place is against generators of unknown structure, where a failure is news and a pass at many sizes is evidence that the structure is not linear.

What the grids cannot show #

The grids show linearity, and only linearity. A generator can pass the rank test at every size and still be weak. The planes a recurrence cannot leave showed a multiplicative congruential generator whose output lies on a few planes in three dimensions, a structure the rank test cannot see because it is linear over the integers rather than over the two-element field. A generator can also be predictable without being linear. The middle-square rule fails long before any rank test could be run, and the generators rebuilt from four of their outputs are recovered from a handful of outputs whatever their rank.

Nor does a pass make a generator safe for cryptography, which asks a much stronger question than any statistical battery. Every one of these sources, linear or not, is predictable by someone who knows its rule and can solve for its state. The multiplied xorshift passes the rank test and is still a 32-bit state that anyone can recover from a few outputs by trying all four billion possibilities. Unpredictability needs a computation believed hard to undo, a different kind of claim altogether.

Still open: how little nonlinearity suffices #

The rank test settles linear generators completely. The questions that remain are about how much nonlinearity is needed, and the answers are mostly empirical. Bit 1 of xorshift128+ passes the rank test with a single carry, a single product of two bits, but whether that bit passes every other test that probes low-degree polynomial structure — tests that would catch a bit that is quadratic in the state — is a separate question, and tests aimed at quadratic structure need far more output than the linear ones.

The general version is a question with no answer yet: for a generator whose output bits are polynomials of low degree in its state, which statistical tests detect the low degree, and at what sample size? For degree one the answer is this essay — rank and linear complexity, at a size equal to the state. For degree two the corresponding tests exist and need samples growing like the square of the state size. Whether some cheap test always detects low degree, at any degree, is tied to questions about pseudorandom generators against low-degree polynomials that are open in complexity theory.

Linear algebra as a statistical test #

Most statistical tests of random numbers are inexact by design. They compare counts with expectations, and a failure is a matter of degree, a p-value smaller than some threshold. The binary rank test against a linear generator is not like that. Below the state size the generator passes as well as random bits do. Above it the generator fails every grid with certainty. The boundary is exactly the number of bits the generator remembers, and the reason is that every row of the grid is the same linear map applied to a different state.

The weakness is deliberate in a sense. Linearity is what makes these generators fast, what makes their periods provable, and what gives the twister its equidistribution. The rank ceiling is the price of the same structure, visible as soon as a grid is larger than the memory. A single addition removes it from every bit but the one where no carry arrives. The practical rule that follows is short. Know the generator’s state size and whether its output is linear. If it is, never feed it to a computation that is itself linear over the two-element field at a size beyond that state, and never read its lowest bit alone. If it is not, the rank test is one more piece of evidence among many, and a pass says only that no linear structure showed at the sizes tried.