TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The power-of-two mixed LCG has full period but dependent adjacent states

Statement

For the LCG of Linear congruential generator modulo a power of two, assume $w \geq 2$ , $a \equiv 1 (m o d 4)$ , and $c$ odd. For every seed the state sequence has exact period $2^{w}$ . If the seed is chosen uniformly from ${0, \dots, 2^{w} - 1}$ , every $x_{n}$ is uniform on that finite set, but $(x_{n}, x_{n + 1})$ is not an independent uniform pair.

Facts & Assumptions

Given: The LCG recurrence, $M = 2^{w}$ , $w \geq 2$ , $a \equiv 1 (m o d 4)$ , and odd $c$ .

[F1]

The update is $x_{n + 1} = [a x_{n} + c]_{M}$ and the output state is a residue modulo $M$ . Linear congruential generator modulo a power of two

[F2]

The uniform probability law on a finite set assigns equal mass to every point. The uniform probability space on a nonempty finite set

[F3]

Every positive integer factors into primes uniquely up to order. The only positive divisors of $2$ are $1$ and $2$ , so $2$ is prime. The fundamental theorem of arithmetic: every integer $n \geq 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ with every $p_{i}$ and $q_{j}$ prime, then $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ , Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$

Proof

1.1givenF1algebra

For $m \geq 1$ , let $S_{m} = \sum_{j = 0}^{m - 1} a^{j}$ . Induction on $m$ in the affine recurrence gives $x_{m} \equiv a^{m} x_{0} + c S_{m} (m o d 2^{w})$ , and the same formula holds from any starting state.

2.1givenstep 1.1algebra

For every $k \geq 0$ , $a^{2^{k}} \equiv 1 (m o d 2^{k + 2})$ . The base case is $a \equiv 1 (m o d 4)$ . If $a^{2^{k}} = 1 + q 2^{k + 2}$ , then squaring gives $a^{2^{k + 1}} = 1 + q 2^{k + 3} + q^{2} 2^{2 k + 4}$ , whose difference from $1$ is divisible by $2^{k + 3}$ .

3.1givenstep 2.1algebra

Write $S_{2^{k}} = 2^{k} q_{k}$ . For $k = 0$ , $q_{0} = 1$ is odd. The identity $S_{2^{k + 1}} = S_{2^{k}} (1 + a^{2^{k}})$ and $a^{2^{k}} \equiv 1 (m o d 4)$ show that $(1 + a^{2^{k}}) / 2$ is odd; hence $q_{k + 1} = q_{k} (1 + a^{2^{k}}) / 2$ is odd.

4.1F1step 1.1step 2.1step 3.1algebra

For every $0 \leq k < w$ , the affine iterate in step 1.1 and facts from steps 2.1 and 3.1 give $x_{2^{k}} - x_{0} \equiv (a^{2^{k}} - 1) x_{0} + c S_{2^{k}} \equiv 2^{k} (m o d 2^{k + 1})$ . Indeed, the first summand is divisible by $2^{k + 2}$ , while $S_{2^{k}} = 2^{k} q_{k}$ with $q_{k}$ odd and $c$ odd; thus a return at $2^{k}$ is impossible modulo $2^{k + 1}$ .

4.2F1step 1.1step 2.1step 3.1algebra

Taking $k = w$ in the affine iterate from step 1.1 shows $x_{2^{w}} \equiv x_{0} (m o d 2^{w})$ : the first summand $(a^{2^{w}} - 1) x_{0}$ is divisible by $2^{w + 2}$ and $c S_{2^{w}}$ by $2^{w}$ . Thus a least positive return time $d$ exists.

5.1F3step 4.1step 4.2algebra

This least return time divides $2^{w}$ . Indeed, write $2^{w} = q d + r$ with $0 \leq r < d$ . Determinism and $x_{d} = x_{0}$ imply $x_{n + d} = x_{n}$ for all $n \geq 0$ , so $x_{2^{w}} = x_{r}$ . Since $x_{2^{w}} = x_{0}$ , minimality of $d$ forces $r = 0$ , hence $2^{w} = d h$ for some positive integer $h$ . By [F3], factor $d$ and $h$ into primes; their combined list is a prime factorization of $2^{w}$ , whose prime list consists of $w$ copies of the prime $2$ . Uniqueness in [F3] implies every prime factor of $d$ is 2, so $d = 2^{j}$ for some $0 \leq j \leq w$ . If $j < w$ , step 4.1 shows $x_{2^{j}} \neq x_{0}$ modulo $2^{j + 1}$ and therefore modulo $2^{w}$ , contradiction. Hence $d = 2^{w}$ , for every seed.

6.1givenF1F2algebra∎

The map $x \mapsto [a x + c]_{2^{w}}$ is injective: if two outputs agree then $2^{w} ∣ a (x - y)$ . Since $a$ is odd, $2 ∣ a d$ implies $2 ∣ d$ ; canceling a factor $2$ and repeating $w$ times gives $2^{w} ∣ x - y$ . Thus the map is a permutation of the finite state set. By [F2], a uniform seed therefore remains uniform at every time. The adjacent-pair law is supported on exactly the $2^{w}$ pairs $(x, [a x + c]_{2^{w}})$ , while the product of two uniform marginals assigns positive mass to all $2^{2 w}$ pairs. Since $w \geq 2$ , $2^{w} < 2^{2 w}$ , so the adjacent states are dependent.

Depends on

Used by

A full-period LCG can alternate its low bit Example

Dependency tree · two levels

34 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

J. Jung, Monte-Carlo Methods lecture notes, Theorem 3.6 (Hull-Dobell) (standard reference, not scraped)