Documentation

Complexitylib.Algebraic.LowerBound.Cutwidth.Extractor.Strong.Block.Recursion.Scheduled.Boolean.Internal

Transporting the actual bit program's retained-seed law #

Exact program serialization identifies every output coordinate. The canonical seed codec and the two-element output equivalence then transport strong extraction without changing its cap or error. Finite-field instances are derived locally from the proved quotient cardinalities.

theorem Algebraic.Cutwidth.Extractor.Internal.scheduledBlockBooleanExtractor_eq (n h Q E ell : ℕ) (x : Fin n → Bool) (seed : Fin (scheduledBlockSeedBits n h Q E ell) → Bool) (i : Fin (recursiveBlockCount 1 h)) (j : Fin ell) :
scheduledBlockBooleanExtractor n h Q E ell x seed i j = decide (scheduledBlockExtractor n h Q E ell x (decodeScheduledBlockSeeds n h Q E ell (List.ofFn seed)) i j = 1)
theorem Algebraic.Cutwidth.Extractor.Internal.scheduledBlockBooleanExtractor_xor (n h Q E ell : ℕ) (x x' : Fin n → Bool) (seed : Fin (scheduledBlockSeedBits n h Q E ell) → Bool) :
scheduledBlockBooleanExtractor n h Q E ell (fun (i : Fin n) => x i ^^ x' i) seed = fun (i : Fin (recursiveBlockCount 1 h)) (j : Fin ell) => scheduledBlockBooleanExtractor n h Q E ell x seed i j ^^ scheduledBlockBooleanExtractor n h Q E ell x' seed i j