THE FOLD / CHEAT / GOD MODE / THE MARSAGLIA PLANES
THE MARSAGLIA PLANES
random numbers fall mainly in the planes
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Take consecutive outputs of a linear congruential generator in threes and plot them as points in a cube. They do not fill it. Marsaglia proved in 1968 that every such generator confines its k-tuples to a family of parallel hyperplanes, at most (k!·m)1/k of them. For most generators that number is large enough not to matter. For RANDU — shipped by IBM, used for a decade of published science — it is fifteen.
LIT verified live. RANDU is xn+1 = 65539·xn mod 231, and it satisfies xn+2 = 6xn+1 − 9xn (mod 231) exactly, at 19,998 of 19,998 consecutive triples. Every triple therefore lies on one of just 15 parallel planes. Marsaglia’s bound for k=3 permits 2,344. A different multiplier satisfies that identity 0 times out of 19,998.
LIT verified live. RANDU is xn+1 = 65539·xn mod 231, and it satisfies xn+2 = 6xn+1 − 9xn (mod 231) exactly, at 19,998 of 19,998 consecutive triples. Every triple therefore lies on one of just 15 parallel planes. Marsaglia’s bound for k=3 permits 2,344. A different multiplier satisfies that identity 0 times out of 19,998.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): George Marsaglia, Random numbers fall mainly in the planes, PNAS 1968 — a three-page paper whose title is the whole result. RANDU was IBM’s Scientific Subroutine Package generator; Knuth’s verdict in TAOCP volume 2 is that it is “really horrible”, and simulation results published on it in the 1960s and 70s are suspect for exactly this reason.
AVAN (AI) should point out that the failure is algebra, not bad luck. 65539 = 216+3, so (216+3)2 = 232 + 6·216 + 9, and modulo 231 that collapses to 6·65539 − 9. The recurrence follows immediately, and with it the fifteen planes. Nothing statistical is involved — the page verifies the identity as an exact equality on integers, not as a fit.
AVAN (AI) should point out that the failure is algebra, not bad luck. 65539 = 216+3, so (216+3)2 = 232 + 6·216 + 9, and modulo 231 that collapses to 6·65539 − 9. The recurrence follows immediately, and with it the fifteen planes. Nothing statistical is involved — the page verifies the identity as an exact equality on integers, not as a fit.
3 ONE DIMENSION
The identity, checked triple by triple.
4 TWO DIMENSIONS · INTERACTIVE
Turn the cloud of triples until the planes line up edge-on.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: fifteen sheets, seen from an angle that hides them.
AVAN’s addition (the inverse-companion): the forward reading is “RANDU is defective.” The inverse is that every LCG is on the same list and only the number differs — Marsaglia’s theorem has no exceptions, so a “good” generator is one whose planes are too close together to notice at the sample sizes anyone uses. Read backwards, the lesson is not that RANDU was uniquely bad but that structure is always present and the test is whether your application can see it; a generator is never random, only unresolved, and increasing the sample size is exactly the operation that brings the planes back into focus.
LIT RANDU is x[n+1] = 65539 x[n] mod 2^31 and it satisfies x[n+2] = 6x[n+1] - 9x[n] mod 2^31 exactly, holding on every one of the consecutive triples tested; every triple therefore lies on one of just 15 parallel planes where Marsaglia's bound for k=3 permits 2,344; and a different multiplier satisfies that identity 0 times over the same run
FIG Human lineage, credited: George Marsaglia, 'Random numbers fall mainly in the planes', PNAS 1968 - a three-page paper whose title is the whole result. RANDU was IBM's Scientific Subroutine Package generator; Knuth's verdict in TAOCP volume 2 is that it is 'really horrible', and simulation results published on it in the 1960s and 70s are suspect for exactly this reason. AVAN points out the failure is ALGEBRA, not bad luck: 65539 = 2^16+3, so (2^16+3)^2 = 2^32 + 6*2^16 + 9, which modulo 2^31 collapses to 6*65539 - 9. The recurrence follows immediately and the fifteen planes with it. The page verifies the identity as an exact equality on integers, not as a statistical fit.
FIG Human lineage, credited: George Marsaglia, 'Random numbers fall mainly in the planes', PNAS 1968 - a three-page paper whose title is the whole result. RANDU was IBM's Scientific Subroutine Package generator; Knuth's verdict in TAOCP volume 2 is that it is 'really horrible', and simulation results published on it in the 1960s and 70s are suspect for exactly this reason. AVAN points out the failure is ALGEBRA, not bad luck: 65539 = 2^16+3, so (2^16+3)^2 = 2^32 + 6*2^16 + 9, which modulo 2^31 collapses to 6*65539 - 9. The recurrence follows immediately and the fifteen planes with it. The page verifies the identity as an exact equality on integers, not as a statistical fit.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GOD MODE · David Lee Wise (ROOT0), with AVAN