two_four_code_card_achievable
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.
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.
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⟩
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.
uses
congr_arg,Fin.vallemma 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
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.
uses
congr_fun,if_pos,if_neg,two_four_code_card_achievable_hazdef 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]
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.
uses
mem_image,mem_powersetCard,card_pos,congr_fun,if_pos,two_four_code_card_achievable_hazlemma 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
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.
uses
card_le_card,inter_subset_left,eq_of_subset_of_card_le,inter_subset_rightlemma 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
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.
uses
mem_filter,mem_univ,true_and,mem_union,mem_sdiff,if_pos,if_neg,two_four_code_card_achievable_hazlemma 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]
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.
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_twolemma 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
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.
uses
mem_filter,mem_univ,true_and,two_four_code_card_achievable_hazlemma 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). -/
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.
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_fintheorem 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
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.
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.
- The construction represents codewords as functions `Fin n → Fin q`, where coordinates and alphabet symbols are zero-indexed.
- The cardinality calculation relies on showing that the all-zero word is disjoint from the image of the weight-2 words, which follows from the nonemptiness of 2-element coordinate sets.
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.
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