AFTD Auto-Formalizing Theoretical Domains

reed_muller_code_mono

theoremverified

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

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 ≤.

  1. 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.

    lines 4–5

    uses Submodule.span_mono

      unfold reed_muller_code
      apply Submodule.span_mono
  2. 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.

    lines 6–8

    uses le_trans

      intro 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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it