TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Every deterministic finite-state stream is eventually periodic

Statement

Let $S$ be a nonempty finite set with $N$ elements, let $T : S \to S$ be a deterministic transition, let $s_{0} \in S$ , and let $g : S \to Y$ be any output map. The state sequence $s_{n + 1} = T (s_{n})$ has integers $μ \geq 0$ and $p \geq 1$ with $μ + p \leq N$ such that $s_{n + p} = s_{n}$ for all $n \geq μ$ . Hence the output sequence $g (s_{n})$ is eventually periodic with period $p$ . If $T$ is bijective, then $μ = 0$ can be used.

Facts & Assumptions

Given: The finite state set, deterministic transition, initial state, and output map in the Statement.

[A1]

The state space has exactly $N < \infty$ elements, and each next state is uniquely determined by the current one.

Proof

1.1givenA1choose

Among the $N + 1$ states $s_{0}, \dots, s_{N}$ , two must be equal, so choose $0 \leq i < j \leq N$ with $s_{i} = s_{j}$ . Put $μ = i$ and $p = j - i$ . Applying the same transition to equal states repeatedly gives $s_{n + p} = s_{n}$ for every $n \geq i$ , and $μ + p = j \leq N$ .

2.1A1step 1.1algebra∎

If $T$ is bijective, its $i$ -fold iterate is injective. Applying that injectivity to $T^{i} (s_{0}) = T^{j} (s_{0})$ gives $s_{0} = T^{j - i} (s_{0}) = s_{p}$ . Repeated application of $T$ yields $s_{n + p} = s_{n}$ from $n = 0$ , and applying $g$ gives the same output period.

Used by

Nothing in the library uses this result yet.

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Pierre L’Ecuyer, Pseudorandom Number Generators (2007) (standard reference, not scraped)