hamming_norm_sum_two_degree_six_monomials
Let 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 + monomial J on (Fin 12 → ZMod 2) to ZMod 2 is equal to 128 - 2 ^ ((I ∩ J).card + 1).
Statement
theorem hamming_norm_sum_two_degree_six_monomials
(I J : Finset (Fin 12)) (hI : I.card = 6) (hJ : J.card = 6) :
hammingNorm (monomial I + monomial J) = 128 - 2 ^ ((I ∩ J).card + 1)- 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 4
- 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…
- monomial_mulFor any natural number s and any two finite subsets I and J of Fin s, the pointwise product of the coordinate monomials monomial I and…
- hamming_norm_monomialFor any natural number s and any finite subset T of Fin s, the Hamming norm of the coordinate monomial monomial T as a function from (Fin…
- hamming_norm_add_eqFor any finite type α and any two Boolean functions f, g : α → ZMod 2, the Hamming norm of their pointwise sum f + g equals hammingNorm f…
- Used by 1
- possible_weights_sum_two_degree_six_monomialsThe 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…
Read back from the Lean
For any two subsets $I, J \subseteq \text{Fin } 12$ such that the cardinality of $I$ is $6$ and the cardinality of $J$ is $6$, the Hamming norm of the function $(\text{monomial } I + \text{monomial } J) : (\text{Fin } 12 \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$ equals $128 - 2^{|I \cap J| + 1}$.
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 computes the Hamming norm of the sum of two degree-6 coordinate monomials using the general identity |f + g| = |f| + |g| - 2|f * g| for ZMod 2-valued functions. The norms of the individual monomials and their product (the monomial indexed by I ∪ J) are expressed as powers of 2. The principle of inclusion-exclusion relates the cardinality of the union |I ∪ J| to the intersection |I ∩ J|, reducing the expression by elementary arithmetic to 128 - 2 ^ (|I ∩ J| + 1).
The Hamming norm of the sum is expanded into powers of 2 in terms of |I|, |J|, and |I ∪ J|, reducing the equation to 2 ^ (12 - 6) + 2 ^ (12 - 6) - 2 * 2 ^ (12 - (I ∪ J).card) = 128 - 2 ^ ((I ∩ J).card + 1).
By `hamming_norm_add_eq`, the Hamming norm of the sum of two functions to ZMod 2 is |f + g| = |f| + |g| - 2|f * g|. The weight of each monomial is evaluated using `hamming_norm_monomial`, which gives 2 ^ (12 - |T|). The product of the two monomials is rewritten as the monomial of their union I ∪ J using `monomial_mul`. Finally, the known cardinalities |I| = 6 and |J| = 6 are substituted.
uses
hamming_norm_add_eq,hamming_norm_monomial,monomial_mulrw [hamming_norm_add_eq] rw [hamming_norm_monomial, hamming_norm_monomial] rw [hI, hJ] rw [monomial_mul] rw [hamming_norm_monomial]
The exponent 12 - |I ∪ J| is replaced by |I ∩ J|, giving 2 ^ (12 - 6) + 2 ^ (12 - 6) - 2 * 2 ^ (I ∩ J).card = 128 - 2 ^ ((I ∩ J).card + 1).
By inclusion-exclusion (`Finset.card_union_add_card_inter`), |I ∪ J| + |I ∩ J| = |I| + |J|. Because |I| = 6 and |J| = 6, linear arithmetic (`omega`) yields 12 - |I ∪ J| = |I ∩ J|. Rewriting with this equality replaces the exponent in the goal.
uses
Finset.card_union_add_card_interhave h_card : 12 - (I ∪ J).card = (I ∩ J).card := by have h_union := Finset.card_union_add_card_inter I J omega rw [h_card]
Both sides simplify to 128 - 2 ^ ((I ∩ J).card + 1), completing the proof.
The identity 2 * 2 ^ |I ∩ J| = 2 ^ (|I ∩ J| + 1) is established by ring arithmetic (`ring`) and rewritten into the goal. Since 2 ^ (12 - 6) + 2 ^ (12 - 6) = 64 + 64 = 128, both sides are definitionally identical and the goal is closed by reflexivity (`rfl`).
have h_pow : 2 * 2 ^ (I ∩ J).card = 2 ^ ((I ∩ J).card + 1) := by ring rw [h_pow] rfl
Finset.card_union_add_card_inter- For any two finite sets, the size of their union plus the size of their intersection equals the sum of their sizes.
hamming_norm_add_eq- The Hamming norm of the sum of two functions to ZMod 2 equals the sum of their Hamming norms minus twice the Hamming norm of their pointwise product.
hamming_norm_monomial- The Hamming norm of a coordinate monomial on s variables indexed by a subset T is 2 ^ (s - |T|).
monomial_mul- The pointwise product of two coordinate monomials indexed by I and J is the coordinate monomial indexed by their union I ∪ J.
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.
/-- Hamming weight of the sum of two degree-6 coordinate monomials in 12 variables. -/theorem hamming_norm_sum_two_degree_six_monomials (I J : Finset (Fin 12)) (hI : I.card = 6) (hJ : J.card = 6) : hammingNorm (monomial I + monomial J) = 128 - 2 ^ ((I ∩ J).card + 1) := by rw [hamming_norm_add_eq] rw [hamming_norm_monomial, hamming_norm_monomial] rw [hI, hJ] rw [monomial_mul] rw [hamming_norm_monomial] have h_card : 12 - (I ∪ J).card = (I ∩ J).card := by have h_union := Finset.card_union_add_card_inter I J omega rw [h_card] have h_pow : 2 * 2 ^ (I ∩ J).card = 2 ^ ((I ∩ J).card + 1) := by ring rw [h_pow] rfl