AFTD Auto-Formalizing Theoretical Domains

two_four_code_four_supports_intersect_ge_two

theoremverifiedformalization

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.

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

    lines 12–13

      rcases hS with ⟨x, hxC, hxcard, rfl⟩
      rcases hT with ⟨y, hyC, hycard, rfl⟩
  2. The codewords x and y are distinct (x ≠ y).

    Suppose, for contradiction, that x = y. Then their supports would be identical, contradicting S ≠ T.

    lines 14–16

      have hne_xy : x ≠ y := by
        rintro rfl
        exact hne rfl
  3. 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.

    lines 17–20

      have hdist : hammingDist x y ≤ 4 := by
        rcases hC x hxC y hyC hne_xy with h2 | h4
        · omega
        · omega
  4. 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.

    lines 21–24

    uses codeword_supp_diff_card_le_hammingDist, Finset.card_sdiff_add_card_inter, Finset.inter_comm

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

    line 25

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

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

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