AFTD Auto-Formalizing Theoretical Domains

reed_muller_code

def

For natural numbers r and s, the binary Reed-Muller code RM(r, s) is the submodule of Boolean functions from (Fin s → ZMod 2) to ZMod 2 spanned by all monomials associated with subsets of Fin s of cardinality at most r.

Statement

def reed_muller_code (r s : ℕ) : Submodule (ZMod 2) ((Fin s → ZMod 2) → ZMod 2)
Defined in
arXiv:2610.09341, Appendix A.1; MacWilliams and Sloane (1977), Ch. 13
Verified
25 Oct 2026
Axioms
none listed
Built on 1
  • monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
Used by 2
  • reed_muller_four_block_concat_degree_sevenLet g0 and g3 be Boolean functions on Fin 12 in the Reed-Muller code reed_muller_code 5 12, and let g1 and g2 be Boolean functions on Fin…
  • reed_muller_code_monoFor any natural numbers r1, r2, and s such that r1 ≤ r2, the Reed-Muller code reed_muller_code r1 s is a submodule of reed_muller_code r2 s.

Read back from the Lean

For natural numbers r and s, reed_muller_code r s is defined as the ZMod 2-submodule of functions from (Fin s → ZMod 2) to ZMod 2 given by the ZMod 2-linear span of the set of functions f for which there exists a subset T : Finset (Fin s) such that T.card ≤ r and f = monomial T.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The Reed-Muller code RM(r, s) over ZMod 2, defined as the subspace of Boolean functions spanned by monomials of degree at most r. -/
def reed_muller_code (r s : ℕ) : Submodule (ZMod 2) ((Fin s → ZMod 2) → ZMod 2) := Submodule.span (ZMod 2) { f | ∃ (T : Finset (Fin s)), T.card ≤ r ∧ f = monomial T }
See it in the graphDiscuss this resultChallenge it