possible_weights_sum_two_degree_six_monomials
The set of Hamming norms of all sums monomial I + monomial J of two coordinate monomials corresponding to 6-element subsets I, J of Fin 12 on (Fin 12 → ZMod 2) to ZMod 2 is {0, 64, 96, 112, 120, 124, 126}.
Statement
theorem possible_weights_sum_two_degree_six_monomials :
{w : ℕ | ∃ (I J : Finset (Fin 12)), I.card = 6 ∧ J.card = 6 ∧
hammingNorm (monomial I + monomial J) = w} =
{0, 64, 96, 112, 120, 124, 126}- Formalizes
- arXiv:2610.29807, Lemma 3.2: Some Results on the Weight Spectrum of Binary Reed-Muller Codes RM(m-7,m)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hamming_norm_sum_two_degree_six_monomialsLet I and J be two 6-element subsets of Fin 12. Then the Hamming norm of the sum of the corresponding coordinate monomials monomial I +…
- 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…
Read back from the Lean
The set of natural numbers $w$ such that there exist subsets $I, J \subseteq \text{Fin } 12$ each of cardinality 6 with the Hamming norm of the Boolean function $(\text{monomial } I + \text{monomial } J)$ equal to $w$ is exactly the set $\{0, 64, 96, 112, 120, 124, 126\}$.
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 proof establishes the set equality by showing both inclusions. An established formula states that the Hamming weight of the sum of two degree-6 coordinate monomials in 12 variables is given by 128 - 2^(|I ∩ J| + 1). Because the intersection size of two 6-element subsets must be an integer between 0 and 6, the only possible weights are 128 - 2^(k+1) for k ∈ {0, ..., 6}, which evaluates to {0, 64, 96, 112, 120, 124, 126}. Conversely, pairing a fixed 6-element set with explicit subsets of intersection sizes 6 down to 0 witnesses that every one of these seven weights is achieved.
The problem reduces to showing that an arbitrary integer w is the Hamming weight of the sum of two degree-6 monomials if and only if w ∈ {0, 64, 96, 112, 120, 124, 126}.
We define a reference subset I = {0, 1, 2, 3, 4, 5} for later use in witnessing values. By extensionality (`ext w`), the two sets are equal if they have the same members. Rewriting with `Set.mem_insert_iff` and `Set.mem_singleton_iff` turns membership in {0, 64, 96, 112, 120, 124, 126} into a seven-way disjunction, and `constructor` splits the equivalence into the forward and backward inclusions.
uses
Set.mem_insert_iff,Set.mem_singleton_ifflet I : Finset (Fin 12) := {0, 1, 2, 3, 4, 5} ext w simp only [Set.mem_insert_iff, Set.mem_singleton_iff] constructor
Every weight of a sum of two degree-6 monomials belongs to {0, 64, 96, 112, 120, 124, 126}.
Given 6-element subsets I' and J' such that w is the Hamming norm of monomial I' + monomial J', the theorem `hamming_norm_sum_two_degree_six_monomials` expresses w as 128 - 2^(|I' ∩ J'| + 1). Since I' ∩ J' ⊆ I' by `Finset.inter_subset_left`, their intersection size satisfies |I' ∩ J'| ≤ |I'| = 6 by `Finset.card_le_card`. Case analysis (`interval_cases`) across the possible values 0 ≤ |I' ∩ J'| ≤ 6 evaluates the formula to 126, 124, 120, 112, 96, 64, and 0 respectively, which confirms w is in the target set.
uses
hamming_norm_sum_two_degree_six_monomials,Finset.card_le_card,Finset.inter_subset_left· rintro ⟨I', J', hI, hJ, rfl⟩ rw [hamming_norm_sum_two_degree_six_monomials I' J' hI hJ] have h_le : (I' ∩ J').card ≤ 6 := by have := @Finset.card_le_card _ (I' ∩ J') I' Finset.inter_subset_left omega interval_cases (I' ∩ J').card <;> simp
Each of the seven values in {0, 64, 96, 112, 120, 124, 126} is achieved as the Hamming norm of a sum of two degree-6 monomials.
For each target value w in the disjunction, we exhibit the reference set I = {0, 1, 2, 3, 4, 5} and an explicit 6-element subset J with |I ∩ J| = k for each k ∈ {6, 5, 4, 3, 2, 1, 0}: - w = 0: J = {0, 1, 2, 3, 4, 5}, with |I ∩ J| = 6, yielding 128 - 2^7 = 0; - w = 64: J = {0, 1, 2, 3, 4, 6}, with |I ∩ J| = 5, yielding 128 - 2^6 = 64; - w = 96: J = {0, 1, 2, 3, 6, 7}, with |I ∩ J| = 4, yielding 128 - 2^5 = 96; - w = 112: J = {0, 1, 2, 6, 7, 8}, with |I ∩ J| = 3, yielding 128 - 2^4 = 112; - w = 120: J = {0, 1, 6, 7, 8, 9}, with |I ∩ J| = 2, yielding 128 - 2^3 = 120; - w = 124: J = {0, 6, 7, 8, 9, 10}, with |I ∩ J| = 1, yielding 128 - 2^2 = 124; - w = 126: J = {6, 7, 8, 9, 10, 11}, with |I ∩ J| = 0, yielding 128 - 2^1 = 126. In each case, the cardinalities and intersections are evaluated computationally, and `hamming_norm_sum_two_degree_six_monomials` confirms the resulting Hamming norm is w.
uses
hamming_norm_sum_two_degree_six_monomials· rintro (rfl | rfl | rfl | rfl | rfl | rfl | rfl) · refine ⟨I, {0, 1, 2, 3, 4, 5}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 5} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 3, 4, 5}).card = 6 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 2, 3, 4, 6}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 6} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 3, 4, 6}).card = 5 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 2, 3, 6, 7}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 6, 7} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 3, 6, 7}).card = 4 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 2, 6, 7, 8}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 6, 7, 8} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 6, 7, 8}).card = 3 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 6, 7, 8, 9}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 6, 7, 8, 9} (by decide) (by decide)] have : (I ∩ {0, 1, 6, 7, 8, 9}).card = 2 := by decide rw [this]; rfl · refine ⟨I, {0, 6, 7, 8, 9, 10}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 6, 7, 8, 9, 10} (by decide) (by decide)] have : (I ∩ {0, 6, 7, 8, 9, 10}).card = 1 := by decide rw [this]; rfl · refine ⟨I, {6, 7, 8, 9, 10, 11}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {6, 7, 8, 9, 10, 11} (by decide) (by decide)] have : (I ∩ {6, 7, 8, 9, 10, 11}).card = 0 := by decide rw [this]; rfl
Set.mem_insert_iff- An element belongs to the insertion of a into a set s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
hamming_norm_sum_two_degree_six_monomials- For any two 6-element subsets I and J of Fin 12, the Hamming norm of monomial I + monomial J is 128 - 2^(|I ∩ J| + 1).
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.inter_subset_left- The intersection of two finite sets s₁ ∩ s₂ is a subset of s₁.
- The cardinalities and intersection sizes of the explicit finite subsets of Fin 12 in the reverse direction are verified by computational reflection using the `decide` tactic.
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.
/-- The set of possible Hamming weights of sums of two degree-6 coordinate monomials in 12 variables is {0, 64, 96, 112, 120, 124, 126}. -/theorem possible_weights_sum_two_degree_six_monomials : {w : ℕ | ∃ (I J : Finset (Fin 12)), I.card = 6 ∧ J.card = 6 ∧ hammingNorm (monomial I + monomial J) = w} = {0, 64, 96, 112, 120, 124, 126} := by let I : Finset (Fin 12) := {0, 1, 2, 3, 4, 5} ext w simp only [Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨I', J', hI, hJ, rfl⟩ rw [hamming_norm_sum_two_degree_six_monomials I' J' hI hJ] have h_le : (I' ∩ J').card ≤ 6 := by have := @Finset.card_le_card _ (I' ∩ J') I' Finset.inter_subset_left omega interval_cases (I' ∩ J').card <;> simp · rintro (rfl | rfl | rfl | rfl | rfl | rfl | rfl) · refine ⟨I, {0, 1, 2, 3, 4, 5}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 5} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 3, 4, 5}).card = 6 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 2, 3, 4, 6}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 6} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 3, 4, 6}).card = 5 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 2, 3, 6, 7}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 6, 7} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 3, 6, 7}).card = 4 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 2, 6, 7, 8}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 6, 7, 8} (by decide) (by decide)] have : (I ∩ {0, 1, 2, 6, 7, 8}).card = 3 := by decide rw [this]; rfl · refine ⟨I, {0, 1, 6, 7, 8, 9}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 6, 7, 8, 9} (by decide) (by decide)] have : (I ∩ {0, 1, 6, 7, 8, 9}).card = 2 := by decide rw [this]; rfl · refine ⟨I, {0, 6, 7, 8, 9, 10}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {0, 6, 7, 8, 9, 10} (by decide) (by decide)] have : (I ∩ {0, 6, 7, 8, 9, 10}).card = 1 := by decide rw [this]; rfl · refine ⟨I, {6, 7, 8, 9, 10, 11}, by decide, by decide, ?_⟩ rw [hamming_norm_sum_two_degree_six_monomials I {6, 7, 8, 9, 10, 11} (by decide) (by decide)] have : (I ∩ {6, 7, 8, 9, 10, 11}).card = 0 := by decide rw [this]; rfl