The order-`L` family is exponentially large.
ProvedCatalog.Probability.SeedRec.card_lfsrWords_geaether-catalogprobability
The order-L family is exponentially large. Already the zero-tap
registers contribute |K|^L distinct files, so seed compression really does
cover exponentially many files — the counting bounds above are not vacuous.
theorem Catalog.Probability.SeedRec.card_lfsrWords_ge(h : L ≤ n) :
Fintype.card K ^ L ≤ (lfsrWords K L n).card := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Probability/PRNGComplexityHierarchy.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Probability/PRNGComplexityHierarchy.lean
import Mathlib
import Definitions.Def_Probability_PRNGBerlekampMassey
import Definitions.Def_Probability_PRNGComplexityHierarchy
import Definitions.Def_Probability_PRNGLFSRDetection
import Definitions.Def_Probability_PRNGLinearComplexity
/-!
# The linear complexity hierarchy and its saturation at `n = 2L`
Two facts about the family `lfsrWords K L n` of length-`n` files generated by an
order-`L` LFSR, both first observed numerically (see `ComputationalEvidence.md`)
and proved here.
* **Nesting.** `lfsrWords_subset_succ`: an order-`L` file is also an
order-`(L+1)` file (pad the taps with a leading zero). Hence
`lowComplexityWords_eq_lfsrWords`: the union over all orders `≤ M` is just the
order-`M` family — the classifier hierarchy is a genuine filtration, and the
quantitative bound `q^{2M+1}` of `PRNGLinearComplexity` can be sharpened to the
single-order bound `q^{2M}`.
* **Saturation.** `card_lfsrWords_saturate`: for `n ≥ 2L` the number of
order-`L` files of length `n` does not depend on `n`. Longer observation
windows reveal no new order-`L` files: `2L` symbols already separate them all.
This is the counting shadow of the `2L` determination theorem.
-/
open Catalog.Probability.SeedRec
variable {K : Type*} [CommRing K] {L m n : ℕ}
variable (K) [Fintype K] [DecidableEq K]
variable [Nontrivial K] (L n : ℕ) [NeZero L]Formal statement
theorem Catalog.Probability.SeedRec.card_lfsrWords_ge(h : L ≤ n) :
Fintype.card K ^ L ≤ (lfsrWords K L n).card := by sorrySource