reed_muller_code_mono
For 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.
Statement
theorem reed_muller_code_mono {r1 r2 s : ℕ} (h : r1 ≤ r2) :
reed_muller_code r1 s ≤ reed_muller_code r2 s- Source
- folklore
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- reed_muller_codeFor 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…
- 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 1
- 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…
Read back from the Lean
For all natural numbers r1, r2, and s, if r1 ≤ r2, then the Reed-Muller code of order r1 with s variables is a submodule of (is contained in) the Reed-Muller code of order r2 with s variables.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The Reed-Muller code RM(r, s) is defined as the linear span of monomials whose degree (the cardinality of the indexing set) is at most r. Because the linear span operator is monotone, the inclusion RM(r1, s) ≤ RM(r2, s) reduces to showing that any generator of degree at most r1 also has degree at most r2. This follows immediately from the assumption r1 ≤ r2 by transitivity of ≤.
It suffices to show that the generating set of reed_muller_code r1 s is contained in that of reed_muller_code r2 s.
By definition, reed_muller_code r s is the submodule spanned over ZMod 2 by monomials indexed by subsets of Fin s with cardinality at most r. By Submodule.span_mono, the span operation is order-preserving, so showing containment between the two codes reduces to showing the inclusion of their generating sets.
uses
Submodule.span_monounfold reed_muller_code apply Submodule.span_mono
Any monomial generator for reed_muller_code r1 s is also a generator for reed_muller_code r2 s.
Let f be an element of the generating set for r1, meaning f = monomial T for some subset T of Fin s with |T| ≤ r1. Since r1 ≤ r2, transitivity of the order relation (le_trans) gives |T| ≤ r2, which means f also belongs to the generating set for r2.
uses
le_transintro f hf obtain ⟨T, hT, rfl⟩ := hf exact ⟨T, le_trans hT h, rfl⟩
Submodule.span_mono- If a subset s is contained in a subset t, the submodule spanned by s is contained in the submodule spanned by t.
le_trans- The order relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity of Reed-Muller codes: RM(r1, s) is contained in RM(r2, s) when r1 ≤ r2. -/theorem reed_muller_code_mono {r1 r2 s : ℕ} (h : r1 ≤ r2) : reed_muller_code r1 s ≤ reed_muller_code r2 s := by unfold reed_muller_code apply Submodule.span_mono intro f hf obtain ⟨T, hT, rfl⟩ := hf exact ⟨T, le_trans hT h, rfl⟩