ErrorCorrectingCodes.Codeword.uniformity_lemma
theoremverifiedimported Lean
Random matrix images of a nonzero vector are uniform. Let $\alpha$ be a finite field, and fix $n \ge 0$ and $k \ge 1$. Let $x \in \alpha^k$ be a nonzero vector. Then the distribution on $\alpha^n$ obtained by sampling an $n \times k$ matrix $G$ with entries in $\alpha$ uniformly at random and returning the product $Gx$ coincides with the uniform distribution on $\alpha^n$; that is, for every $v \in \alpha^n$, \[ \frac{\bigl|\{\,G \in \alpha^{n \times k} : Gx = v\,\}\bigr|}{\abs{\alpha}^{nk}} = \frac{1}{\abs{\alpha}^{n}}. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option linter.unusedSectionVars false in open Set Filter Asymptotics Finset in variable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] in variable {n k m : ℕ} in theorem ErrorCorrectingCodes.Codeword.uniformity_lemma (n k : ℕ) (x : Codeword k α) (h_x : x ≠ zero) (h_k : k ≥ 1) : matrix_dist n k x = uniform_vector_dist n α
- Source
- TCSlib, `ErrorCorrectingCodes.Codeword.uniformity_lemma`
- Lean proof
- By Allan Li (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.ErrorCorrectingCodes.Codeword.uniformity_lemma← ErrorCorrectingCodes.Codeword.uniformity_lemma (TCSlib/ErrorCorrectingCodes/LinearCodes.lean:99): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- ErrorCorrectingCodes.Codeword.uniform_vector_distThe uniform probability mass function on $\alpha^n$, encoded as a function $\alpha^n\to\mathbb{R}$ assigning $1/|\alpha|^n$ to each vector.
- ErrorCorrectingCodes.Codeword.get_matrix_rowUtility: extract row
iof matrixMas a1×kmatrix. - ErrorCorrectingCodes.Codeword.matrix_dist$\mu_x(v)$ is the fraction of $n\times k$ matrices $G$ satisfying $Gx=v$.
- ErrorCorrectingCodes.CodewordA codeword of length $n$ over alphabet $\alpha$ is a function $c : \mathrm{Fin}\,n \to \alpha$.
- ErrorCorrectingCodes.Codeword.zeroPointwise addition, subtraction, and the all-zero codeword.
- Used by 1
- ErrorCorrectingCodes.Codeword.prob_leq_ball_sizeWeight distribution of a random linear image is dominated by a Hamming ball. Let $\alpha$ be a finite field, let $n$ and $k \ge 1$ be…
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.
Lean’s trace was cut to the first 400 of 404 tactics.
set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option linter.unusedSectionVars false inopen Set Filter Asymptotics Finset invariable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] invariable {n k m : ℕ} in/-- **Uniformity Lemma**: for any nonzero `x ∈ αᵏ`, applying a uniformly random `n×k` matrix over `α` to `x` yields the uniform distribution over `αⁿ`. -/theorem ErrorCorrectingCodes.Codeword.uniformity_lemma (n k : ℕ) (x : Codeword k α) (h_x : x ≠ zero) (h_k : k ≥ 1) : matrix_dist n k x = uniform_vector_dist n α := by { unfold matrix_dist uniform_vector_dist funext v simp field_simp have h : (filter (fun G => Matrix.mulVec G x = v) Finset.univ).card = (Fintype.card α)^(n * (k-1)) := by -- Says that the amount of matrices G such that Gx = v is equal to the amount of matrices G such that -- for each row G_i, G_ix = v_i have h2 : (fun G => Matrix.mulVec G x = v) = (fun G => ∀ i, Matrix.mulVec (get_matrix_row n k G i) x = fun _ => v i) := by funext G apply propext apply Iff.intro · intro h_G i funext x' unfold get_matrix_row Matrix.mulVec dotProduct simp unfold Matrix.mulVec dotProduct at h_G simp at h_G exact congrFun h_G i · intro h_g unfold Matrix.mulVec dotProduct simp unfold get_matrix_row Matrix.mulVec dotProduct at h_g simp at h_g funext x₀ have h_g' : (fun x_1 : Fin 1 => Finset.sum Finset.univ fun x_2 => G x₀ x_2 * x x_2) = fun x => v x₀ := by exact h_g x₀ exact congrFun h_g' 1 -- Says that the number of matrices G such that for each row G_i, G_ix = v_i is equal to the product -- over i of the number of row vectors g such that gx = v_i have h3 : (filter (fun G => ∀ (i : Fin n), Matrix.mulVec (get_matrix_row n k G i) x = fun _ => v i) Finset.univ).card = Finset.prod Finset.univ (fun (i : Fin n) => (filter (fun g : Matrix (Fin 1) (Fin k) α => Matrix.mulVec g x = fun _ => v i) Finset.univ).card) := by have h3₀ : (fun G => ∀ (i : Fin n), Matrix.mulVec (get_matrix_row n k G i) x = fun _ => v i) = (fun G => ∀ (i : Fin n), (Finset.sum Finset.univ fun j => G i j * x j) = v i) := by unfold get_matrix_row Matrix.mulVec dotProduct simp funext G₀ simp apply Iff.intro · intro h_fun i₀ specialize h_fun i₀ have h_f : ∀x₀, (fun x_1 : Fin 1=> Finset.sum Finset.univ fun x_2 => G₀ i₀ x_2 * x x_2) x₀ = v i₀ := by exact congr_fun h_fun let x₀ : Fin 1 := 1 specialize h_f x₀ exact h_f · intro h_all i₀ funext x₀ specialize h_all i₀ exact h_all have h3₁ : Finset.prod Finset.univ (fun i => (filter (fun g : Matrix (Fin 1) (Fin k) α => Matrix.mulVec g x = fun x => v i) Finset.univ).card) = ((Finset.univ : Finset (Fin n)).pi (fun i => (filter (fun g : Matrix (Fin 1) (Fin k) α => (Matrix.mulVec g x = fun x => v i)) Finset.univ))).card := by simp let S : Finset ((a : Fin n) → a ∈ Finset.univ → Matrix (Fin 1) (Fin k) α) := ((Finset.univ : Finset (Fin n)).pi (fun i => (filter (fun g : Matrix (Fin 1) (Fin k) α => (Matrix.mulVec g x = fun _ => v i)) Finset.univ))) have h3₂ : S.card = (filter (fun G : Matrix (Fin n) (Fin k) α => ∀ (i : Fin n), (Finset.sum Finset.univ fun j => G i j * x j) = v i) Finset.univ).card := by let f : (s : (a : Fin n) → a ∈ Finset.univ → Matrix (Fin 1) (Fin k) α) → s ∈ S → (Matrix (Fin n) (Fin k) α) := fun s _ ↦ Matrix.of (fun i j => (s i (Finset.mem_univ i)) 1 j) apply Finset.card_bij f have h_map_to_generator : ∀ (a : (a : Fin n) → a ∈ Finset.univ → Matrix (Fin 1) (Fin k) α) (ha : a ∈ S), f a ha ∈ filter (fun G => ∀ (i : Fin n), (Finset.sum Finset.univ fun j => G i j * x j) = v i) Finset.univ:= by intro a ha simp intro i have h_av : Matrix.mulVec (a i (Finset.mem_univ i)) x = fun _ => v i := by apply Finset.mem_pi.mp at ha specialize ha i specialize ha (Finset.mem_univ i) apply Finset.mem_filter.mp at ha simp[ha] unfold Matrix.mulVec dotProduct at h_av simp at h_av have : i ∈ Finset.univ := by simp have h_av₂ : ∀x₀, (fun x_1 => Finset.sum Finset.univ fun x_2 => a i (this : i ∈ Finset.univ) x_1 x_2 * x x_2) x₀ = v i := by apply congr_fun h_av let x₀ : Fin 1 := 1 specialize h_av₂ x₀ exact h_av₂ exact h_map_to_generator have h_f_injective : ∀ (a : (a : Fin n) → a ∈ Finset.univ → Matrix (Fin 1) (Fin k) α) (ha : a ∈ S), ∀ (b : (a : Fin n) → a ∈ Finset.univ → Matrix (Fin 1) (Fin k) α) (hb : b ∈ S), f a ha = f b hb → a = b := by intro a b ha hb intro h_fab_eq funext y h_y apply congr_fun at h_fab_eq specialize h_fab_eq y simp[f] at h_fab_eq apply congr_fun at h_fab_eq funext 1 x_k specialize h_fab_eq x_k simp at h_fab_eq simp[h_fab_eq] exact h_f_injective have h_f_surjective : ∀ b ∈ filter (fun G => ∀ (i : Fin n), (Finset.sum Finset.univ fun j => G i j * x j) = v i) Finset.univ, ∃ a, ∃ (ha : a ∈ S), f a ha = b := by simp intro b h_eq let a₀ : ((a : Fin n) → a ∈ Finset.univ → Matrix (Fin 1) (Fin k) α) := fun a h_a => Matrix.of (fun i j => b a j) use a₀ simp[f] constructor · simp[S] unfold Matrix.mulVec dotProduct intro a funext x_1 simp[a₀] exact h_eq a · funext i j simp[a₀] exact h_f_surjective simp[S] at h3₂ simp_rw[h3₀, h3₁] rw[← h3₂] simp -- Says that the number of row vectors g such that gx = v_i is equal to |α|^(k-1) have h4 : ∀i, (filter (fun g : Matrix (Fin 1) (Fin k) α => Matrix.mulVec g x = fun _ => v i) Finset.univ).card = (Fintype.card α)^(k-1) := by intro i unfold Matrix.mulVec dotProduct simp have h4₀ : (filter (fun g : Matrix (Fin 1) (Fin k) α => (fun x_1 => Finset.sum Finset.univ fun x_2 => g x_1 x_2 * x x_2) = fun x => v i) Finset.univ) = Set.toFinset {g : Matrix (Fin 1) (Fin k) α | (Finset.sum (Finset.univ : Finset (Fin k)) fun a => (g 0 a) * (x a)) = v i} := by ext x simp constructor · intro h_filter apply congr_fun at h_filter specialize h_filter 1 exact h_filter · intro h_univ funext 1 exact h_univ let c := v i let S := (toFinset {g : Matrix (Fin 1) (Fin k) α | (Finset.sum Finset.univ fun a => g 0 a * x a) = c}) have h4₁ : S.card = (Fintype.card α)^(k-1) := by have h_nonzero_element : ∃ (j : Fin k), x j ≠ 0 := by by_contra h_zero push_neg at h_zero have h_x_eq_zero : x = zero := by ext l; exact h_zero l exact h_x h_x_eq_zero rcases h_nonzero_element with ⟨j, h_j⟩ have h_rearrange : S = (toFinset {g : Matrix (Fin 1) (Fin k) α | (g 0 j) = (c - Finset.sum (Finset.univ.erase j) fun a => (g 0 a)*(x a)) / (x j)}) := by ext y simp constructor · intro h_sum simp[S] at h_sum rw[h_sum] simp field_simp[h_sum] · intro h_formula field_simp at h_formula rw[eq_sub_iff_add_eq] at h_formula simp[S] simp_all simp_rw[h_rearrange] let S₂ := (toFinset {g : Matrix (Fin 1) (Fin k) α | g 0 j = (v i - Finset.sum (erase Finset.univ j) fun a => g 0 a * x a) / x j}) have h_g_bijection : S₂.card = (Finset.univ : Finset (Codeword (k-1) α)).card := by have h_k1 (l : Fin (k-1)) : ↑l < k := by have h_l2 : ↑l < k - 1 := l.2 omega have h_k2 (l : Fin (k-1)) : ↑l + 1 < k := by have h_l2 : ↑l < k - 1 := l.2 omega let f : (g : Matrix (Fin 1) (Fin k) α) → g ∈ S₂ → (Codeword (k-1) α) := fun g h_g => (fun (l : Fin (k-1)) => if h_llt : l.val < j then (g 0 ⟨l.val, by exact h_k1 l⟩) else (g 0 ⟨l.val + 1, by exact h_k2 l⟩)) apply Finset.card_bij f simp_all have h_f_inj : ∀ (a : Matrix (Fin 1) (Fin k) α) (ha : a ∈ S₂), ∀ (b : Matrix (Fin 1) (Fin k) α) (hb : b ∈ S₂), f a ha = f b hb → a = b := by simp[S₂] intro a h_a b h_b h_l let φa := (fun (l : Fin (k-1)) => if (l : ℕ) < (j : ℕ) then a 0 { val := ↑l, isLt := h_k1 l } else a 0 { val := ↑l + 1, isLt := h_k2 l }) let φb := (fun (l : Fin (k-1)) => if (l : ℕ) < (j : ℕ) then b 0 { val := ↑l, isLt := h_k1 l } else b 0 { val := ↑l + 1, isLt := h_k2 l }) have hφ : φa = φb := by simp[φa, φb]; exact h_l ext i₁ iκ have h_i1 : i₁ = 0 := by fin_cases i₁; simp rw[h_i1] have h_cases : iκ.val < j.val ∨ iκ.val = j.val ∨ iκ.val > j.val := by exact Nat.lt_trichotomy iκ.val j.val have h_eq_if_lt (i₀ : Fin k) (h_lt : ↑i₀ < ↑j) : a 0 i₀ = b 0 i₀ := by have h_i₀val : i₀ < k-1 := by have h_j_le : ↑j ≤ k-1 := Nat.le_pred_of_lt j.2 exact lt_of_lt_of_le h_lt h_j_le have h_φeq : φa ⟨↑i₀, by exact h_i₀val⟩ = φb ⟨↑i₀, by exact h_i₀val⟩ := by exact congrFun hφ ⟨↑i₀, by exact h_i₀val⟩ have h_φa : φa ⟨↑i₀, by exact h_i₀val⟩ = a 0 ↑i₀ := by simp[φa] intro h_jleq have h_notjleq : ¬(j ≤ i₀) := Nat.not_le_of_gt h_lt contradiction have h_φb : φb ⟨↑i₀, by exact h_i₀val⟩ = b 0 ↑i₀ := by simp[φb] intro h_jleq have h_notjleq : ¬(j ≤ i₀) := Nat.not_le_of_gt h_lt contradiction rw[h_φa, h_φb] at h_φeq exact h_φeq have h_eq_if_gt (i₀ : Fin k) (h_gt : (i₀ : ℕ) > (j : ℕ)) : a 0 i₀ = b 0 i₀ := by have h_i₀val : i₀ - 1 < k - 1 := by have h_i₀_lt_k : ↑i₀ < k := i₀.2 have h_i₀_gt_j : ↑i₀ > ↑j := h_gt omega have h_φeq : φa ⟨↑i₀ - 1, by exact h_i₀val⟩ = φb ⟨↑i₀ - 1, by exact h_i₀val⟩ := by exact congrFun hφ ⟨↑i₀ - 1, by exact h_i₀val⟩ have h_φa : φa ⟨↑i₀ - 1, by exact h_i₀val⟩ = a 0 ↑i₀ := by simp[φa] rw[if_neg] have h_i₀_pos : (i₀ : ℕ) > 0 := by exact Nat.lt_of_le_of_lt (Nat.zero_le j) h_gt have h_i₀_ge_one : 1 ≤ (i₀ : ℕ) := by rw [Nat.one_le_iff_ne_zero] intro h_zero exact Nat.ne_of_gt h_i₀_pos h_zero have h_simplify : (i₀ : ℕ) - 1 + 1 = ↑i₀ := by exact Nat.sub_add_cancel h_i₀_ge_one simp_rw[h_simplify] omega have h_φb : φb ⟨↑i₀ - 1, by exact h_i₀val⟩ = b 0 ↑i₀ := by simp[φb] rw[if_neg] have h_i₀_pos : (i₀ : ℕ) > 0 := by exact Nat.lt_of_le_of_lt (Nat.zero_le j) h_gt have h_i₀_ge_one : 1 ≤ (i₀ : ℕ) := by rw [Nat.one_le_iff_ne_zero] intro h_zero exact Nat.ne_of_gt h_i₀_pos h_zero have h_simplify : (i₀ : ℕ) - 1 + 1 = ↑i₀ := by exact Nat.sub_add_cancel h_i₀_ge_one simp_rw[h_simplify] omega rw[h_φa, h_φb] at h_φeq exact h_φeq rcases h_cases with (h_lt | h_eq | h_gt) · exact h_eq_if_lt iκ h_lt · have h_fineq : iκ = j := by exact Fin.eq_of_val_eq h_eq rw[h_fineq, h_a, h_b] field_simp have h_a_sum_split : (Finset.sum (Finset.univ : Finset (Fin k)) fun a_1 => a 0 a_1 * x a_1) = (Finset.sum (Finset.filter (fun i => i < j) Finset.univ) fun a_1 => a 0 a_1 * x a_1) + (Finset.sum (Finset.filter (fun i => i > j) Finset.univ) fun a_1 => a 0 a_1 * x a_1) + a 0 j * x j := by simp_rw[←Finset.sum_filter_add_sum_filter_not (Finset.univ : Finset (Fin k)) (fun i => i = j) (fun a_1 => a 0 a_1 * x a_1)] have h_eq_j : Finset.filter (fun i => i = j) (Finset.univ : Finset (Fin k)) = {j} := by ext i; simp have h_neq_split : Finset.filter (fun i => i ≠ j) (Finset.univ : Finset (Fin k)) = Finset.filter (fun i => i < j) (Finset.univ : Finset (Fin k)) ∪ Finset.filter (fun i => i > j) (Finset.univ : Finset (Fin k)) := by ext i; simp have h_disjoint : Disjoint (Finset.filter (fun i => i < j) (Finset.univ : Finset (Fin k))) (Finset.filter (fun i => i > j) (Finset.univ : Finset (Fin k))) := by apply Finset.disjoint_filter.mpr intro i h1 h2 exact lt_asymm h2 rw[h_eq_j, Finset.sum_singleton, h_neq_split, Finset.sum_union h_disjoint] ring have h_b_sum_split : (Finset.sum Finset.univ fun a_1 => b 0 a_1 * x a_1) = (Finset.sum (Finset.filter (fun i => i < j) Finset.univ) fun a_1 => b 0 a_1 * x a_1) + (Finset.sum (Finset.filter (fun i => i > j) Finset.univ) fun a_1 => b 0 a_1 * x a_1) + b 0 j * x j := by simp_rw[←Finset.sum_filter_add_sum_filter_not (Finset.univ : Finset (Fin k)) (fun i => i = j) (fun a_1 => b 0 a_1 * x a_1)] have h_eq_j : Finset.filter (fun i => i = j) (Finset.univ : Finset (Fin k)) = {j} := by ext i; simp have h_neq_split : Finset.filter (fun i => i ≠ j) (Finset.univ : Finset (Fin k)) = Finset.filter (fun i => i < j) (Finset.univ : Finset (Fin k)) ∪ Finset.filter (fun i => i > j) (Finset.univ : Finset (Fin k)) := by ext i; simp have h_disjoint : Disjoint (Finset.filter (fun i => i < j) (Finset.univ : Finset (Fin k))) (Finset.filter (fun i => i > j) (Finset.univ : Finset (Fin k))) := by apply Finset.disjoint_filter.mpr intro i h1 h2 exact lt_asymm h2 rw[h_eq_j, Finset.sum_singleton, h_neq_split, Finset.sum_union h_disjoint] ring rw[h_a_sum_split, h_b_sum_split] have h_lt_sum_eq : (Finset.sum (filter (fun i => i < j) Finset.univ) fun a_1 => a 0 a_1 * x a_1) = (Finset.sum (filter (fun i => i < j) Finset.univ) fun a_1 => b 0 a_1 * x a_1) := by apply Finset.sum_congr rfl intro i hi simp at hi have h_eq : a 0 i = b 0 i := by exact h_eq_if_lt i hi rw[h_eq] have h_gt_sum_eq : (Finset.sum (filter (fun i => i > j) Finset.univ) fun a_1 => a 0 a_1 * x a_1) = (Finset.sum (filter (fun i => i > j) Finset.univ) fun a_1 => b 0 a_1 * x a_1) := by apply Finset.sum_congr rfl intro i hi simp at hi have h_eq : a 0 i = b 0 i := by exact h_eq_if_gt i hi rw[h_eq] simp_rw[h_lt_sum_eq, h_gt_sum_eq] ring · exact h_eq_if_gt iκ h_gt exact h_f_inj have h_f_surj : ∀ b ∈ Finset.univ, ∃ a, ∃ (ha : a ∈ S₂), f a ha = b := by intro b h_b have h_l1 (l : Fin k) (h_lj : ↑l < j) : ↑l < k - 1 := by have h_jk : ↑j < k := j.is_lt exact Nat.lt_of_lt_of_le h_lj (Nat.le_pred_of_lt h_jk) have h_l2 (l : Fin k) (h_lj : ¬(↑l < j)) (h_lj' : ¬(↑l = j)) : ↑l - 1 < k - 1 := by have h_lk : l < k := l.is_lt have h_cases : k < 1 ∨ k = 1 ∨ k > 1 := by exact Nat.lt_trichotomy k 1 rcases h_cases with (h_klt | h_keq | h_kgt) · omega · have h_l0 : l = ⟨0, by exact Nat.lt_of_succ_le h_k⟩ := by apply Fin.ext have h_l_lt_1 : l.val < 1 := by simp subst h_keq interval_cases (l : ℕ) rfl exact Nat.eq_zero_of_le_zero (Nat.le_of_lt_succ h_l_lt_1) have h_j0 : j = ⟨0, by exact Nat.lt_of_succ_le h_k⟩ := by apply Fin.ext have h_j_lt_1 : j.val < 1 := by subst h_keq; exact j.isLt exact Nat.eq_zero_of_le_zero (Nat.le_of_lt_succ h_j_lt_1) push_neg at h_lj' rw[h_l0, h_j0] at h_lj' contradiction · have h_l_geq_1 : 1 ≤ (l : ℕ) := by have h_j_geq_0 : (j : Nat) ≥ 0 := Nat.zero_le _ have h_l_gt_j : (j : ℕ) < (l : ℕ) := by contrapose! h_lj' have h_j_leq_l : (j : ℕ) ≤ (l : ℕ) := Nat.le_of_not_lt h_lj exact Fin.ext (Nat.le_antisymm h_lj' h_j_leq_l) have h_l_gt_0 : (0 : Nat) < (l : Nat) := Nat.lt_of_le_of_lt h_j_geq_0 h_l_gt_j exact Nat.succ_le_of_lt h_l_gt_0 omega let p₀ : (Matrix (Fin 1) (Fin k) α) := fun _ l => if h_lj : l < j then b ⟨l.val, by exact h_l1 l h_lj⟩ else (if h_lj' : l = j then 0 else b ⟨l.val - 1, by exact h_l2 l h_lj h_lj'⟩) let p : (Matrix (Fin 1) (Fin k) α) := fun _ l => if l ≠ j then (p₀ 0 l) else ((v i - Finset.sum (Finset.erase Finset.univ j) fun c => (p₀ 0 c) * x c) / x j) use p have h_p : p ∈ S₂ := by let inS₂ (g : Matrix (Fin 1) (Fin k) α) : Prop := g 0 j = (v i - Finset.sum (erase Finset.univ j) fun c => g 0 c * x c) / x j have hS₂_mem : S₂ = toFinset {g | inS₂ g} := by simp[S₂, inS₂] rw[hS₂_mem, ←Finset.mem_coe] have h_finseteq : ↑(toFinset {g | inS₂ g}) = {g | inS₂ g} := by simp rw[h_finseteq, Set.mem_setOf_eq] simp only [inS₂, p] simp only [ne_eq, not_true, ↓reduceIte] congr 1 congr 1 apply Finset.sum_congr rfl intro c hc have hcj : c ≠ j := Finset.ne_of_mem_erase hc simp [hcj] use h_p funext l change (fun g h_g => (fun (l : Fin (k-1)) => if h_llt : l.val < j then (g 0 ⟨l.val, by exact h_k1 l⟩) else (g 0 ⟨l.val + 1, by exact h_k2 l⟩))) p h_p l = b l change (if h_llt : (l : ℕ) < (j : ℕ) then p 0 ⟨l.val, by exact h_k1 l⟩ else p 0 ⟨l.val + 1, by exact h_k2 l⟩) = b l split_ifs with h_if · let l_cast : (Fin k) := { val := ↑l, isLt := h_k1 l } change (fun _ l => if l ≠ j then (p₀ 0 l) else ((v i - Finset.sum (Finset.erase Finset.univ j) fun c => (p₀ 0 c) * x c) / x j)) 0 l_cast = b l change (if l_cast ≠ j then (p₀ 0 l_cast) else ((v i - Finset.sum (Finset.erase Finset.univ j) fun c => (p₀ 0 c) * x c) / x j)) = b l have h_l_neq_j : l_cast ≠ j := by have h_l_cast_lt : (l_cast : ℕ) < (j : ℕ) := by simp[l_cast, h_if] have h_l_cast_ne : (l_cast : ℕ) ≠ (j : ℕ) := by exact ne_of_lt h_l_cast_lt rw [Fin.val_ne_iff] at h_l_cast_ne exact h_l_cast_ne rw [if_pos h_l_neq_j] simp[p₀, l_cast] intro h_j_leq have h_jl_nat : (j : ℕ) ≤ (l : ℕ) := by rw[Fin.le_iff_val_le_val] at h_j_leq have h_l_val : (l : ℕ) = (({ val := ↑l, isLt := h_k1 l } : (Fin k)) : ℕ) := by simp rw[h_l_val] exact h_j_leq omega · simp[p, p₀] split_ifs with h_if₂ h_if₃ · simp[Fin.ext_iff] at h_if₂ omega · push_neg at h_if have h_lj : (↑l + 1 : ℕ) < (↑j : ℕ) :=h_if₃ omega · rfl exact h_f_surj rw[h_g_bijection] have h_codeword_card : (Finset.univ : Finset (Codeword (k-1) α)).card = (Fintype.card α)^(k-1) := by rw[Finset.card_univ] unfold Codeword rw[Fintype.card_fun] simp rw[h_codeword_card] rw[h4₀, h4₁] simp_rw[h2, h3, h4] simp[←pow_mul, mul_comm] norm_cast rw[h, ←pow_add] congr calc n * (k - 1) + n = n * (k - 1) + n * 1 := by rw [Nat.mul_one] _ = n * ((k - 1) + 1) := by rw [←Nat.mul_add] _ = n * k := by rw[Nat.sub_add_cancel h_k]}