AFTD Auto-Formalizing Theoretical Domains

two_four_code_card_achievable

theoremverified

For every alphabet size $q \ge 2$ and every length $n$, there is a $\{2,4\}$-code $C \subseteq (\mathrm{Fin}\, n \to \mathrm{Fin}\, q)$ of cardinality exactly $1 + \binom{n}{2}$: the zero word together with the words carrying a fixed nonzero symbol on the two positions of some 2-element subset of $\{1,\dots,n\}$. This is equation (1) of arXiv:2610.30613, the lower-bound half of $A_q(n,\{2,4\}) = 1 + \binom{n}{2}$, and it holds for every $n$, with no threshold.

Statement

theorem two_four_code_card_achievable (q n : ℕ) (hq : 2 ≤ q) :
    ∃ C : Finset (Fin n → Fin q),
      C.card = 1 + n.choose 2 ∧ is_two_four_code (C : Set (Fin n → Fin q))
Source
step towards op_491_threshold_le
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_two_four_codeA set of codewords $C \subseteq (\mathrm{Fin}\, n \to \mathrm{Fin}\, q)$ is a $\{2, 4\}$-code if any two distinct codewords $x, y \in C$…
Used by 1
  • two_four_code_max_card_geFor every $q \ge 2$ and every $n$, $1 + \binom{n}{2} \le A_q(n,\{2,4\})$, i.e. the extremal code of the previous lemma is counted by the…

The proof, explained

To construct a {2,4}-code of cardinality 1 + n.choose 2 in Fin n → Fin q, we choose two distinct alphabet symbols 0 and 1, and let C consist of the all-zero word together with the n.choose 2 words that take value 1 on a 2-element subset of coordinates and 0 elsewhere. The cardinality equals 1 + n.choose 2 because the zero word has weight 0 whereas all other codewords have weight 2, and the assignment from 2-subsets to words is injective. The Hamming distance from the zero word to any weight-2 codeword is 2. For any two distinct weight-2 codewords w_S and w_T, their disagreeing coordinates form the symmetric difference (S \ T) ∪ (T \ S) of size 4 - 2|S ∩ T|, which is either 2 or 4 since distinct 2-element sets intersect in at most one element.

  1. The alphabet symbols 0 and 1 are well-defined elements of Fin q. automation

    Since q ≥ 2, both 0 < q and 1 < q hold by linear integer arithmetic, allowing 0 and 1 to be constructed as valid elements of Fin q.

    lines 1–5

    open Finset
    
    def two_four_code_card_achievable_z {q : ℕ} (hq : 2 ≤ q) : Fin q := ⟨0, by omega⟩
    def two_four_code_card_achievable_a {q : ℕ} (hq : 2 ≤ q) : Fin q := ⟨1, by omega⟩
    
  2. The symbols 1 and 0 in Fin q are distinct.

    Assuming 1 = 0 in Fin q, applying congr_arg Fin.val projects both sides to ℕ, giving 1 = 0, an absurdity.

    lines 6–11

    uses congr_arg, Fin.val

    lemma two_four_code_card_achievable_haz {q : ℕ} (hq : 2 ≤ q) :
        two_four_code_card_achievable_a hq ≠ two_four_code_card_achievable_z hq := by
      intro h
      have := congr_arg Fin.val h
      cases this
    
  3. The mapping S ↦ w_S from coordinate subsets to words is injective.

    Assuming w_S = w_T, evaluating at coordinate i via congr_fun shows i ∈ S ↔ i ∈ T. If i were in one set but not the other, w_S(i) and w_T(i) would reduce to 1 and 0 via if_pos and if_neg, contradicting two_four_code_card_achievable_haz. Hence S = T.

    lines 12–27

    uses congr_fun, if_pos, if_neg, two_four_code_card_achievable_haz

    def two_four_code_card_achievable_w {n q : ℕ} (hq : 2 ≤ q) (S : Finset (Fin n)) : Fin n → Fin q :=
      fun i => if i ∈ S then two_four_code_card_achievable_a hq else two_four_code_card_achievable_z hq
    
    lemma two_four_code_card_achievable_w_inj {n q : ℕ} (hq : 2 ≤ q) (S T : Finset (Fin n))
        (h : two_four_code_card_achievable_w hq S = two_four_code_card_achievable_w hq T) : S = T := by
      ext i
      have hi := congr_fun h i
      dsimp [two_four_code_card_achievable_w] at hi
      by_cases hSi : i ∈ S <;> by_cases hTi : i ∈ T
      · simp [hSi, hTi]
      · rw [if_pos hSi, if_neg hTi] at hi
        exact (two_four_code_card_achievable_haz hq hi).elim
      · rw [if_neg hSi, if_pos hTi] at hi
        exact (two_four_code_card_achievable_haz hq hi.symm).elim
      · simp [hSi, hTi]
    
  4. The all-zero word is not in the image of the size-2 subsets under w.

    If the zero word equaled w_S for some size-2 subset S (mem_image, mem_powersetCard), then because |S| = 2 > 0 (card_pos), S contains some coordinate i. Evaluating at i via congr_fun gives 0 = 1 via if_pos, contradicting two_four_code_card_achievable_haz.

    lines 28–44

    uses mem_image, mem_powersetCard, card_pos, congr_fun, if_pos, two_four_code_card_achievable_haz

    lemma two_four_code_card_achievable_zero_not_mem_image {n q : ℕ} (hq : 2 ≤ q) :
        (fun _ : Fin n => two_four_code_card_achievable_z hq) ∉
          (powersetCard 2 (univ : Finset (Fin n))).image (two_four_code_card_achievable_w hq) := by
      intro hmem
      rw [mem_image] at hmem
      rcases hmem with ⟨S, hS, hS_eq⟩
      rw [mem_powersetCard] at hS
      have hS_card : S.card = 2 := hS.2
      have hSne : S.Nonempty := by
        rw [← card_pos]
        omega
      rcases hSne with ⟨i, hi⟩
      have hi_eq := congr_fun hS_eq i
      dsimp [two_four_code_card_achievable_w] at hi_eq
      rw [if_pos hi] at hi_eq
      exact two_four_code_card_achievable_haz hq hi_eq
    
  5. Any two distinct 2-element subsets intersect in at most one element.

    For distinct size-2 sets s and t, if |s ∩ t| > 1, then since s ∩ t ⊆ s (inter_subset_left) and |s ∩ t| ≤ |s| = 2 (card_le_card), we must have |s ∩ t| = 2 = |s|. A subset of the same finite size equals the whole set (eq_of_subset_of_card_le), so s ∩ t = s. This implies s ⊆ t (inter_subset_right), which with |s| = |t| = 2 gives s = t (eq_of_subset_of_card_le), contradicting s ≠ t.

    lines 45–57

    uses card_le_card, inter_subset_left, eq_of_subset_of_card_le, inter_subset_right

    lemma two_four_code_card_achievable_inter_card_le_one_of_card_two {α : Type*} [DecidableEq α] {s t : Finset α}
        (hs : s.card = 2) (ht : t.card = 2) (hne : s ≠ t) :
        (s ∩ t).card ≤ 1 := by
      by_contra! h
      have h_le : (s ∩ t).card ≤ s.card := card_le_card inter_subset_left
      have h_eq : (s ∩ t).card = s.card := by omega
      have : s ∩ t = s := eq_of_subset_of_card_le inter_subset_left (by rw [h_eq])
      have h_sub : s ⊆ t := by
        rw [← this]
        exact inter_subset_right
      have : s = t := eq_of_subset_of_card_le h_sub (by rw [hs, ht])
      exact hne this
    
  6. The coordinates where w_S and w_T disagree form the symmetric difference (S \ T) ∪ (T \ S).

    By coordinate-wise extensionality, w_S(i) ≠ w_T(i) holds if and only if i ∈ S \ T or i ∈ T \ S (mem_filter, mem_univ, true_and, mem_union, mem_sdiff). When i is in both sets or neither set, both words agree; when i belongs to exactly one set, one word evaluates to 1 and the other to 0 via if_pos and if_neg, which are distinct by two_four_code_card_achievable_haz.

    lines 58–72

    uses mem_filter, mem_univ, true_and, mem_union, mem_sdiff, if_pos, if_neg, two_four_code_card_achievable_haz

    lemma two_four_code_card_achievable_filter_ne_w_w {n q : ℕ} (hq : 2 ≤ q) (S T : Finset (Fin n)) :
        (univ.filter (fun i => two_four_code_card_achievable_w hq S i ≠ two_four_code_card_achievable_w hq T i)) =
          (S \ T) ∪ (T \ S) := by
      ext i
      rw [mem_filter]
      simp only [mem_univ, true_and, mem_union, mem_sdiff]
      dsimp [two_four_code_card_achievable_w]
      by_cases hSi : i ∈ S <;> by_cases hTi : i ∈ T
      · simp [hSi, hTi]
      · rw [if_pos hSi, if_neg hTi]
        simp [hSi, hTi, two_four_code_card_achievable_haz hq]
      · rw [if_neg hSi, if_pos hTi]
        simp [hSi, hTi, (two_four_code_card_achievable_haz hq).symm]
      · simp [hSi, hTi]
    
  7. The Hamming distance between w_S and w_T for distinct 2-subsets S and T is either 2 or 4. automation

    The Hamming distance is the cardinality of the disagreeing coordinates, which equals |(S \ T) ∪ (T \ S)| by two_four_code_card_achievable_filter_ne_w_w. Because S \ T and T \ S are disjoint (disjoint_sdiff_sdiff), their union has size |S \ T| + |T \ S| (card_union_of_disjoint). Since |S \ T| + |S ∩ T| = 2 and |T \ S| + |S ∩ T| = 2 (card_sdiff_add_card_inter, inter_comm), the distance is 4 - 2|S ∩ T|. Since |S ∩ T| ≤ 1 by two_four_code_card_achievable_inter_card_le_one_of_card_two, the intersection size is 0 or 1, leaving distance 4 or 2, which omega concludes.

    lines 73–87

    uses two_four_code_card_achievable_filter_ne_w_w, card_union_of_disjoint, disjoint_sdiff_sdiff, card_sdiff_add_card_inter, inter_comm, two_four_code_card_achievable_inter_card_le_one_of_card_two

    lemma two_four_code_card_achievable_dist_w_w {n q : ℕ} (hq : 2 ≤ q) (S T : Finset (Fin n))
        (hS : S.card = 2) (hT : T.card = 2) (hST : S ≠ T) :
        hammingDist (two_four_code_card_achievable_w hq S) (two_four_code_card_achievable_w hq T) = 2 ∨
        hammingDist (two_four_code_card_achievable_w hq S) (two_four_code_card_achievable_w hq T) = 4 := by
      change (univ.filter (fun i => two_four_code_card_achievable_w hq S i ≠ two_four_code_card_achievable_w hq T i)).card = 2 ∨
             (univ.filter (fun i => two_four_code_card_achievable_w hq S i ≠ two_four_code_card_achievable_w hq T i)).card = 4
      rw [two_four_code_card_achievable_filter_ne_w_w]
      rw [card_union_of_disjoint disjoint_sdiff_sdiff]
      have h1 : (S \ T).card + (S ∩ T).card = 2 := by
        rw [card_sdiff_add_card_inter, hS]
      have h2 : (T \ S).card + (S ∩ T).card = 2 := by
        rw [inter_comm, card_sdiff_add_card_inter, hT]
      have h3 : (S ∩ T).card ≤ 1 := two_four_code_card_achievable_inter_card_le_one_of_card_two hS hT hST
      omega
    
  8. The Hamming distance between the all-zero word and w_S is 2 for any size-2 subset S.

    The set of coordinates where the zero word and w_S disagree (mem_filter, mem_univ, true_and) is exactly S, because for i ∈ S the value w_S(i) = 1 is nonzero by two_four_code_card_achievable_haz, while for i ∉ S both words are 0. Thus the set of differences is S itself, which has cardinality 2.

    lines 88–101

    uses mem_filter, mem_univ, true_and, two_four_code_card_achievable_haz

    lemma two_four_code_card_achievable_dist_zero_w {n q : ℕ} (hq : 2 ≤ q) (S : Finset (Fin n)) (hS : S.card = 2) :
        hammingDist (fun _ : Fin n => two_four_code_card_achievable_z hq) (two_four_code_card_achievable_w hq S) = 2 := by
      change (univ.filter (fun i => (fun _ : Fin n => two_four_code_card_achievable_z hq) i ≠ two_four_code_card_achievable_w hq S i)).card = 2
      have : (univ.filter (fun i => (fun _ : Fin n => two_four_code_card_achievable_z hq) i ≠ two_four_code_card_achievable_w hq S i)) = S := by
        ext i
        rw [mem_filter]
        simp only [mem_univ, true_and]
        dsimp [two_four_code_card_achievable_w]
        split_ifs with hi
        · simp [hi, (two_four_code_card_achievable_haz hq).symm]
        · simp [hi]
      rw [this, hS]
    
    /-- The extremal {2,4}-code: the zero word plus one indicator word per 2-subset of the coordinates, of cardinality 1 + C(n,2). -/
  9. The code C, defined as the zero word together with all w_S for 2-subsets S, has cardinality 1 + n.choose 2. automation

    We define C by inserting the all-zero word z into the image of the collection of 2-subsets under w. Because z is not in this image (two_four_code_card_achievable_zero_not_mem_image), insertion increases cardinality by 1 (card_insert_of_notMem). Injectivity of w (two_four_code_card_achievable_w_inj) implies the image has the same cardinality as powersetCard 2 univ (card_image_of_injective). Finally, the number of 2-subsets of an n-element set is n.choose 2 (card_powersetCard, card_univ, Fintype.card_fin). Linear arithmetic concludes |C| = 1 + n.choose 2.

    lines 102–116

    uses card_insert_of_notMem, two_four_code_card_achievable_zero_not_mem_image, card_image_of_injective, two_four_code_card_achievable_w_inj, card_powersetCard, card_univ, Fintype.card_fin

    theorem two_four_code_card_achievable (q n : ℕ) (hq : 2 ≤ q) :
        ∃ C : Finset (Fin n → Fin q),
          C.card = 1 + n.choose 2 ∧ is_two_four_code (C : Set (Fin n → Fin q)) := by
      open Finset in
      classical
      let z : Fin n → Fin q := fun _ => two_four_code_card_achievable_z hq
      let C : Finset (Fin n → Fin q) :=
        insert z ((powersetCard 2 (univ : Finset (Fin n))).image (two_four_code_card_achievable_w hq))
      use C
      constructor
      · dsimp [C]
        rw [card_insert_of_notMem (two_four_code_card_achievable_zero_not_mem_image hq)]
        rw [card_image_of_injective _ (fun _ _ => two_four_code_card_achievable_w_inj hq _ _)]
        rw [card_powersetCard, card_univ, Fintype.card_fin]
        omega
  10. The code C is a {2,4}-code: any two distinct codewords have Hamming distance 2 or 4.

    Given distinct codewords x, y ∈ C (Finset.mem_coe, mem_insert, mem_image), each is either the zero word z or an indicator word w_S for some 2-subset S (mem_powersetCard). If both are z, this contradicts x ≠ y. If one is z and the other is w_T, their distance is 2 (two_four_code_card_achievable_dist_zero_w, Or.inl), using hammingDist_comm if x is the indicator word. If both are indicator words w_S and w_T, x ≠ y implies S ≠ T, so their distance is 2 or 4 by two_four_code_card_achievable_dist_w_w.

    lines 117–133

    uses Finset.mem_coe, mem_insert, mem_image, mem_powersetCard, Or.inl, two_four_code_card_achievable_dist_zero_w, hammingDist_comm, two_four_code_card_achievable_dist_w_w

      · intro x hx y hy hxy
        rw [Finset.mem_coe, mem_insert, mem_image] at hx hy
        rcases hx with rfl | ⟨S, hS, rfl⟩
        · rcases hy with rfl | ⟨T, hT, rfl⟩
          · contradiction
          · rw [mem_powersetCard] at hT
            exact Or.inl (two_four_code_card_achievable_dist_zero_w hq T hT.2)
        · rcases hy with rfl | ⟨T, hT, rfl⟩
          · rw [mem_powersetCard] at hS
            rw [hammingDist_comm]
            exact Or.inl (two_four_code_card_achievable_dist_zero_w hq S hS.2)
          · rw [mem_powersetCard] at hS hT
            have hST : S ≠ T := by
              intro hST
              apply hxy
              rw [hST]
            exact two_four_code_card_achievable_dist_w_w hq S T hS.2 hT.2 hST
congr_arg
If two inputs are equal, applying a function to them yields equal outputs: if a₁ = a₂ then f a₁ = f a₂.
Fin.val
The canonical projection from Fin n to its underlying natural number value.
congr_fun
If two functions are equal, their values at any argument are equal: if f = g then f a = g a.
if_pos
When condition c is true, the conditional if c then t else e reduces to t.
if_neg
When condition c is false, the conditional if c then t else e reduces to e.
two_four_code_card_achievable_haz
The alphabet symbols 1 and 0 in Fin q are distinct whenever 2 ≤ q.
mem_image
An element b belongs to the image of s under f if and only if b = f a for some a ∈ s.
mem_powersetCard
A finset s belongs to powersetCard n t if and only if s ⊆ t and |s| = n.
card_pos
A finset is nonempty if and only if its cardinality is strictly positive.
card_le_card
If s ⊆ t for finsets s and t, then |s| ≤ |t|.
inter_subset_left
The intersection s ∩ t is a subset of s.
eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finsets, then s = t.
inter_subset_right
The intersection s ∩ t is a subset of t.
mem_filter
An element a belongs to the filter of s by predicate p if and only if a ∈ s and p a holds.
mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The conjunction True ∧ p simplifies to p.
mem_union
An element belongs to s ∪ t if and only if it belongs to s or to t.
mem_sdiff
An element belongs to s \ t if and only if it belongs to s and not to t.
two_four_code_card_achievable_filter_ne_w_w
The set of coordinates where words w_S and w_T differ is the symmetric difference (S \ T) ∪ (T \ S).
card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
disjoint_sdiff_sdiff
The set differences x \ y and y \ x are disjoint.
card_sdiff_add_card_inter
For any finsets s and t, |s \ t| + |s ∩ t| = |s|.
inter_comm
Intersection of finsets is commutative: s ∩ t = t ∩ s.
two_four_code_card_achievable_inter_card_le_one_of_card_two
Two distinct 2-element subsets have intersection size at most 1.
card_insert_of_notMem
Inserting an element not already in a finset increments its cardinality by 1.
two_four_code_card_achievable_zero_not_mem_image
The all-zero word is not in the image of the size-2 subsets under the indicator mapping w.
card_image_of_injective
An injective function preserves the cardinality of a finset under image.
two_four_code_card_achievable_w_inj
The mapping S ↦ w_S is injective on finsets of coordinates.
card_powersetCard
The number of size-k subsets of a finset s is |s|.choose k.
card_univ
The cardinality of the universal finset of a finite type equals the Fintype cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
Finset.mem_coe
Membership of an element in the set coercion of a finset is equivalent to membership in the finset.
mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Or.inl
From a proof of A, deduces the disjunction A ∨ B.
two_four_code_card_achievable_dist_zero_w
The Hamming distance between the all-zero word and w_S is 2 for any size-2 subset S.
hammingDist_comm
Hamming distance is symmetric: hammingDist x y = hammingDist y x.
two_four_code_card_achievable_dist_w_w
For distinct 2-element subsets S and T, the Hamming distance between w_S and w_T is 2 or 4.

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

open Finsetdef two_four_code_card_achievable_z {q : ℕ} (hq : 2 ≤ q) : Fin q := ⟨0, by omega⟩def two_four_code_card_achievable_a {q : ℕ} (hq : 2 ≤ q) : Fin q := ⟨1, by omega⟩lemma two_four_code_card_achievable_haz {q : ℕ} (hq : 2 ≤ q) :    two_four_code_card_achievable_a hq ≠ two_four_code_card_achievable_z hq := by  intro h  have := congr_arg Fin.val h  cases thisdef two_four_code_card_achievable_w {n q : ℕ} (hq : 2 ≤ q) (S : Finset (Fin n)) : Fin n → Fin q :=  fun i => if i ∈ S then two_four_code_card_achievable_a hq else two_four_code_card_achievable_z hqlemma two_four_code_card_achievable_w_inj {n q : ℕ} (hq : 2 ≤ q) (S T : Finset (Fin n))    (h : two_four_code_card_achievable_w hq S = two_four_code_card_achievable_w hq T) : S = T := by  ext i  have hi := congr_fun h i  dsimp [two_four_code_card_achievable_w] at hi  by_cases hSi : i ∈ S <;> by_cases hTi : i ∈ T  · simp [hSi, hTi]  · rw [if_pos hSi, if_neg hTi] at hi    exact (two_four_code_card_achievable_haz hq hi).elim  · rw [if_neg hSi, if_pos hTi] at hi    exact (two_four_code_card_achievable_haz hq hi.symm).elim  · simp [hSi, hTi]lemma two_four_code_card_achievable_zero_not_mem_image {n q : ℕ} (hq : 2 ≤ q) :    (fun _ : Fin n => two_four_code_card_achievable_z hq) ∉      (powersetCard 2 (univ : Finset (Fin n))).image (two_four_code_card_achievable_w hq) := by  intro hmem  rw [mem_image] at hmem  rcases hmem with ⟨S, hS, hS_eq⟩  rw [mem_powersetCard] at hS  have hS_card : S.card = 2 := hS.2  have hSne : S.Nonempty := by    rw [← card_pos]    omega  rcases hSne with ⟨i, hi⟩  have hi_eq := congr_fun hS_eq i  dsimp [two_four_code_card_achievable_w] at hi_eq  rw [if_pos hi] at hi_eq  exact two_four_code_card_achievable_haz hq hi_eqlemma two_four_code_card_achievable_inter_card_le_one_of_card_two {α : Type*} [DecidableEq α] {s t : Finset α}    (hs : s.card = 2) (ht : t.card = 2) (hne : s ≠ t) :    (s ∩ t).card ≤ 1 := by  by_contra! h  have h_le : (s ∩ t).card ≤ s.card := card_le_card inter_subset_left  have h_eq : (s ∩ t).card = s.card := by omega  have : s ∩ t = s := eq_of_subset_of_card_le inter_subset_left (by rw [h_eq])  have h_sub : s ⊆ t := by    rw [← this]    exact inter_subset_right  have : s = t := eq_of_subset_of_card_le h_sub (by rw [hs, ht])  exact hne thislemma two_four_code_card_achievable_filter_ne_w_w {n q : ℕ} (hq : 2 ≤ q) (S T : Finset (Fin n)) :    (univ.filter (fun i => two_four_code_card_achievable_w hq S i ≠ two_four_code_card_achievable_w hq T i)) =      (S \ T) ∪ (T \ S) := by  ext i  rw [mem_filter]  simp only [mem_univ, true_and, mem_union, mem_sdiff]  dsimp [two_four_code_card_achievable_w]  by_cases hSi : i ∈ S <;> by_cases hTi : i ∈ T  · simp [hSi, hTi]  · rw [if_pos hSi, if_neg hTi]    simp [hSi, hTi, two_four_code_card_achievable_haz hq]  · rw [if_neg hSi, if_pos hTi]    simp [hSi, hTi, (two_four_code_card_achievable_haz hq).symm]  · simp [hSi, hTi]lemma two_four_code_card_achievable_dist_w_w {n q : ℕ} (hq : 2 ≤ q) (S T : Finset (Fin n))    (hS : S.card = 2) (hT : T.card = 2) (hST : S ≠ T) :    hammingDist (two_four_code_card_achievable_w hq S) (two_four_code_card_achievable_w hq T) = 2 ∨    hammingDist (two_four_code_card_achievable_w hq S) (two_four_code_card_achievable_w hq T) = 4 := by  change (univ.filter (fun i => two_four_code_card_achievable_w hq S i ≠ two_four_code_card_achievable_w hq T i)).card = 2 ∨         (univ.filter (fun i => two_four_code_card_achievable_w hq S i ≠ two_four_code_card_achievable_w hq T i)).card = 4  rw [two_four_code_card_achievable_filter_ne_w_w]  rw [card_union_of_disjoint disjoint_sdiff_sdiff]  have h1 : (S \ T).card + (S ∩ T).card = 2 := by    rw [card_sdiff_add_card_inter, hS]  have h2 : (T \ S).card + (S ∩ T).card = 2 := by    rw [inter_comm, card_sdiff_add_card_inter, hT]  have h3 : (S ∩ T).card ≤ 1 := two_four_code_card_achievable_inter_card_le_one_of_card_two hS hT hST  omegalemma two_four_code_card_achievable_dist_zero_w {n q : ℕ} (hq : 2 ≤ q) (S : Finset (Fin n)) (hS : S.card = 2) :    hammingDist (fun _ : Fin n => two_four_code_card_achievable_z hq) (two_four_code_card_achievable_w hq S) = 2 := by  change (univ.filter (fun i => (fun _ : Fin n => two_four_code_card_achievable_z hq) i ≠ two_four_code_card_achievable_w hq S i)).card = 2  have : (univ.filter (fun i => (fun _ : Fin n => two_four_code_card_achievable_z hq) i ≠ two_four_code_card_achievable_w hq S i)) = S := by    ext i    rw [mem_filter]    simp only [mem_univ, true_and]    dsimp [two_four_code_card_achievable_w]    split_ifs with hi    · simp [hi, (two_four_code_card_achievable_haz hq).symm]    · simp [hi]  rw [this, hS]/-- The extremal {2,4}-code: the zero word plus one indicator word per 2-subset of the coordinates, of cardinality 1 + C(n,2). -/theorem two_four_code_card_achievable (q n : ℕ) (hq : 2 ≤ q) :    ∃ C : Finset (Fin n → Fin q),      C.card = 1 + n.choose 2 ∧ is_two_four_code (C : Set (Fin n → Fin q)) := by  open Finset in  classical  let z : Fin n → Fin q := fun _ => two_four_code_card_achievable_z hq  let C : Finset (Fin n → Fin q) :=    insert z ((powersetCard 2 (univ : Finset (Fin n))).image (two_four_code_card_achievable_w hq))  use C  constructor  · dsimp [C]    rw [card_insert_of_notMem (two_four_code_card_achievable_zero_not_mem_image hq)]    rw [card_image_of_injective _ (fun _ _ => two_four_code_card_achievable_w_inj hq _ _)]    rw [card_powersetCard, card_univ, Fintype.card_fin]    omega  · intro x hx y hy hxy    rw [Finset.mem_coe, mem_insert, mem_image] at hx hy    rcases hx with rfl | ⟨S, hS, rfl⟩    · rcases hy with rfl | ⟨T, hT, rfl⟩      · contradiction      · rw [mem_powersetCard] at hT        exact Or.inl (two_four_code_card_achievable_dist_zero_w hq T hT.2)    · rcases hy with rfl | ⟨T, hT, rfl⟩      · rw [mem_powersetCard] at hS        rw [hammingDist_comm]        exact Or.inl (two_four_code_card_achievable_dist_zero_w hq S hS.2)      · rw [mem_powersetCard] at hS hT        have hST : S ≠ T := by          intro hST          apply hxy          rw [hST]        exact two_four_code_card_achievable_dist_w_w hq S T hS.2 hT.2 hST
See it in the graphDiscuss this resultChallenge it