two_four_code_four_supports_intersect_ge_two
Let $\alpha$ be an alphabet with decidable equality and a distinguished element $0$. Let $\mathcal{C} \subseteq (\mathrm{Fin}\, n \to \alpha)$ be a code containing the zero codeword $0$ such that any two distinct codewords have Hamming distance in $\{2, 4\}$. Let $\mathcal{H} = \mathrm{four\_supports}(\mathcal{C})$. For any two distinct supports $S, T \in \mathcal{H}$ with $S \ne T$, the cardinality of their intersection is at least 2: $2 \le (S \cap T).\mathrm{card}$.
Statement
theorem two_four_code_four_supports_intersect_ge_two {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (C : Set (Fin n → α)) (hC : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → hammingDist x y = 2 ∨ hammingDist x y = 4) (_h0 : 0 ∈ C) (S T : Finset (Fin n)) (hS : S ∈ four_supports C) (hT : T ∈ four_supports C) (hne : S ≠ T) : 2 ≤ (S ∩ T).card
- Formalizes
- arXiv:2610.30613 Lemma 3.3 -- Asymptotically Sharp Length Thresholds for q-ary Codes with Distances 2 and 4
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- codeword_suppThe support of a codeword $x : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality and zero is the finite set…
- four_supportsThe family of four-supports of a code $\mathcal{C} \subseteq (\mathrm{Fin}\, n \to \alpha)$ is the set of all Finsets…
- codeword_supp_diff_card_le_hammingDistFor any two codewords $x, y : \mathrm{Fin}\, n \to \alpha$, the sum of the cardinalities of the set differences of their supports,…
Read back from the Lean
Let $n$ be a natural number and let $\alpha$ be a type with decidable equality and a zero element. Let $C \subseteq (\mathrm{Fin}\ n \to \alpha)$ be a set of functions (codewords) such that: 1. For every pair of distinct codewords $x, y \in C$, the Hamming distance between $x$ and $y$ is either $2$ or $4$. 2. The zero codeword $0$ belongs to $C$. Let $S, T \subseteq \mathrm{Fin}\ n$ be finite sets. If $S$ and $T$ are distinct supports of codewords in $C$ that each have support size $4$ (i.e., $S \in \mathrm{four\_supports}(C)$, $T \in \mathrm{four\_supports}(C)$, and $S \neq T$), then the size of their intersection $|S \cap T|$ is at least $2$.
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
By definition of four-supports, S and T are the supports of distinct codewords x, y ∈ C of weight 4. Since x ≠ y, their Hamming distance is at most 4. Bounding the size of their symmetric difference by this Hamming distance and decomposing each support into its difference and the intersection S ∩ T shows that 8 - 2|S ∩ T| ≤ 4, from which |S ∩ T| ≥ 2 follows by linear arithmetic.
There exist codewords x, y ∈ C with supports S and T, respectively, such that |S| = 4 and |T| = 4.
By the definition of `four_supports C`, the assumptions S ∈ four_supports C and T ∈ four_supports C provide codewords x, y ∈ C whose supports are S and T, both having cardinality 4.
rcases hS with ⟨x, hxC, hxcard, rfl⟩ rcases hT with ⟨y, hyC, hycard, rfl⟩
The codewords x and y are distinct (x ≠ y).
Suppose, for contradiction, that x = y. Then their supports would be identical, contradicting S ≠ T.
have hne_xy : x ≠ y := by rintro rfl exact hne rfl
The Hamming distance between x and y is at most 4.
Because x and y are distinct elements of C, the code distance hypothesis ensures that their Hamming distance is either 2 or 4. In both cases, it is at most 4.
have hdist : hammingDist x y ≤ 4 := by rcases hC x hxC y hyC hne_xy with h2 | h4 · omega · omega
The symmetric difference bounds and support partition identities hold for S and T.
Applying `codeword_supp_diff_card_le_hammingDist` shows that |S \ T| + |T \ S| ≤ hammingDist x y. Then `Finset.card_sdiff_add_card_inter` decomposes each 4-element support into the disjoint union of a set difference and the intersection, using `Finset.inter_comm` to write the intersection as S ∩ T in both equations.
uses
codeword_supp_diff_card_le_hammingDist,Finset.card_sdiff_add_card_inter,Finset.inter_commhave hdiff := codeword_supp_diff_card_le_hammingDist x y have h1 := Finset.card_sdiff_add_card_inter (codeword_supp x) (codeword_supp y) have h2 := Finset.card_sdiff_add_card_inter (codeword_supp y) (codeword_supp x) rw [Finset.inter_comm (codeword_supp y)] at h2
The intersection S ∩ T contains at least 2 elements: 2 ≤ |S ∩ T|.
Adding the two partition equations |S \ T| + |S ∩ T| = 4 and |T \ S| + |S ∩ T| = 4 yields (|S \ T| + |T \ S|) + 2|S ∩ T| = 8. Since |S \ T| + |T \ S| ≤ hammingDist x y ≤ 4, linear integer arithmetic establishes 8 - 2|S ∩ T| ≤ 4, which simplifies to 2 ≤ |S ∩ T|.
omega
codeword_supp_diff_card_le_hammingDist- For any two codewords x and y, the sum of the sizes of the support differences, |codeword_supp(x) \ codeword_supp(y)| + |codeword_supp(y) \ codeword_supp(x)|, is at most the Hamming distance between x and y.
Finset.card_sdiff_add_card_inter- For any two finite sets s and t, the size of their difference plus the size of their intersection equals the size of s: |s \ t| + |s ∩ t| = |s|.
Finset.inter_comm- Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
- The hypothesis `_h0 : 0 ∈ C` (that the zero codeword belongs to C) is included in the theorem statement but is unused in the proof.
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.
/-- Any two distinct four-supports in a code with distances in {2, 4} containing the zero word intersect in at least two coordinates. -/theorem two_four_code_four_supports_intersect_ge_two {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (C : Set (Fin n → α)) (hC : ∀ x ∈ C, ∀ y ∈ C, x ≠ y → hammingDist x y = 2 ∨ hammingDist x y = 4) (_h0 : 0 ∈ C) (S T : Finset (Fin n)) (hS : S ∈ four_supports C) (hT : T ∈ four_supports C) (hne : S ≠ T) : 2 ≤ (S ∩ T).card := by rcases hS with ⟨x, hxC, hxcard, rfl⟩ rcases hT with ⟨y, hyC, hycard, rfl⟩ have hne_xy : x ≠ y := by rintro rfl exact hne rfl have hdist : hammingDist x y ≤ 4 := by rcases hC x hxC y hyC hne_xy with h2 | h4 · omega · omega have hdiff := codeword_supp_diff_card_le_hammingDist x y have h1 := Finset.card_sdiff_add_card_inter (codeword_supp x) (codeword_supp y) have h2 := Finset.card_sdiff_add_card_inter (codeword_supp y) (codeword_supp x) rw [Finset.inter_comm (codeword_supp y)] at h2 omega