AFTD Auto-Formalizing Theoretical Domains

ccz_layer_parity_repr_card_ge

theoremverifiedformalization

The Hadamard-free floor of arXiv:2610.01024 (Corollary 83): every set of nonzero parities on 3m qubits whose order-1, 2, 3 moments equal the syndrome of the layer of m >= 1 disjoint CCZ gates has at least 6m + 1 elements; so every Hadamard-free {CNOT, T} circuit for the layer uses at least 6m + 1 T gates.

Statement

theorem ccz_layer_parity_repr_card_ge (m : ℕ) (hm : 1 ≤ m) (S : Finset (Finset (Fin (3 * m)))) (hS : is_parity_repr S (ccz_layer_syndrome m)) : 6 * m + 1 ≤ S.card
Formalizes
arXiv:2610.01024, Corollary 83 (Hadamard-free floor of 6m + 1 for m disjoint CCZ gates)
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_parity_reprA finite set S of nonempty parities on n qubits is a parity representation of a syndrome s if the moment of S at every non-empty subset A…
  • ccz_layer_syndromeThe syndrome of the layer of m disjoint CCZ gates on 3m qubits (blocks {3j, 3j+1, 3j+2}): 1 on each block triple and 0 on every other…

The proof, explained

We form the incidence matrix M between the 3m qubits and the parities in S over the field with two elements. Vanishing of order-1 and order-2 moments implies that M has orthogonal rows and row sums zero. We construct an injective linear map L from a (3m + 1)-dimensional space into the kernel of M using partner qubit evaluations. By the rank-nullity theorem, the number of parities |S| is at least the rank of M (which is 3m) plus the dimension of the range of L (which is 3m + 1), giving |S| >= 6m + 1.

  1. The syndrome vanishes on any set not of size 3.

    By definition, the CCZ-layer syndrome is 1 if and only if the subset is of the form {3j, 3j+1, 3j+2} for some block index j. Since 3j, 3j+1, 3j+2 are pairwise distinct, every such subset has size exactly 3. Therefore, any subset with size different from 3 has syndrome 0.

    lines 4–9

    uses Finset.card_eq_three, Fin.ext_iff, if_neg

      unfold ccz_layer_syndrome
      rw [if_neg]
      rintro ⟨j, rfl⟩
      apply hA
      rw [Finset.card_eq_three]
      refine ⟨_, _, _, ?_, ?_, ?_, rfl⟩ <;> simp [Fin.ext_iff]
  2. For any qubit i, pairing it with the other two qubits p, q in its block yields syndrome 1.

    Given qubit i, we select p and q by cyclically shifting the residue of i mod 3 within the block floor(i/3). When a = i, the set {a, p, q} is precisely the CCZ block containing i, so its syndrome is 1.

    lines 15–25

    uses if_pos, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff

      have hi := i.isLt
      refine ⟨⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩,
        ⟨3 * (i.val / 3) + (i.val % 3 + 2) % 3, by omega⟩, fun a => ?_⟩
      unfold ccz_layer_syndrome
      by_cases hai : a = i
      · subst hai
        rw [if_pos rfl, if_pos]
        refine ⟨⟨a.val / 3, by omega⟩, ?_⟩
        ext x
        simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]
        omega
  3. When a is not i, the syndrome of {a, p, q} vanishes.

    If {a, p, q} were a CCZ block {3j, 3j+1, 3j+2}, then since p and q lie in block floor(i/3), j would have to equal floor(i/3), forcing a to equal i. Since a is distinct from i, this is impossible, so the syndrome is 0.

    lines 26–46

    uses if_neg, Fin.val_ne_of_ne, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff

      · rw [if_neg hai, if_neg]
        rintro ⟨j, hj⟩
        have h1 : a ∈ ({a, ⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩,
            ⟨3 * (i.val / 3) + (i.val % 3 + 2) % 3, by omega⟩} : Finset (Fin (3 * m))) := by simp
        have h2 : (⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩ : Fin (3 * m)) ∈
            ({a, ⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩,
            ⟨3 * (i.val / 3) + (i.val % 3 + 2) % 3, by omega⟩} : Finset (Fin (3 * m))) := by simp
        have h3 : (⟨3 * j.val, by omega⟩ : Fin (3 * m)) ∈
            ({⟨3 * j.val, by omega⟩, ⟨3 * j.val + 1, by omega⟩, ⟨3 * j.val + 2, by omega⟩} :
              Finset (Fin (3 * m))) := by simp
        have h4 : (⟨3 * j.val + 1, by omega⟩ : Fin (3 * m)) ∈
            ({⟨3 * j.val, by omega⟩, ⟨3 * j.val + 1, by omega⟩, ⟨3 * j.val + 2, by omega⟩} :
              Finset (Fin (3 * m))) := by simp
        have h5 : (⟨3 * j.val + 2, by omega⟩ : Fin (3 * m)) ∈
            ({⟨3 * j.val, by omega⟩, ⟨3 * j.val + 1, by omega⟩, ⟨3 * j.val + 2, by omega⟩} :
              Finset (Fin (3 * m))) := by simp
        rw [hj] at h1 h2
        rw [← hj] at h3 h4 h5
        simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] at h1 h2 h3 h4 h5
        have := Fin.val_ne_of_ne hai
        omega
  4. The incidence matrix M satisfies the syndrome condition for sets of size at most 3, and its entries are idempotent.

    We define M as the incidence matrix of qubits versus parities in S. The product of entries M a y over a set A is 1 iff A is a subset of y. Summing this over y in S counts parities containing A modulo 2, which equals the syndrome when A is nonempty and has size at most 3. Each entry is 0 or 1 in ZMod 2, hence idempotent.

    lines 49–65

    uses Matrix.of, Matrix.of_apply, Finset.prod_boole, Finset.natCast_card_filter, Finset.sum_coe_sort, Finset.sum_congr, Finset.subset_iff

      classical
      -- the incidence matrix of qubits against parities
      let M : Matrix (Fin (3 * m)) S (ZMod 2) := Matrix.of fun a y => if a ∈ (y : Finset _) then 1 else 0
      have hcount : ∀ A : Finset (Fin (3 * m)),
          ((S.filter fun y => A ⊆ y).card : ZMod 2) = ∑ y : S, ∏ a ∈ A, M a y := by
        intro A
        simp only [M, Matrix.of_apply, Finset.prod_boole]
        rw [Finset.natCast_card_filter, ← Finset.sum_coe_sort S]
        refine Finset.sum_congr rfl fun y _ => ?_
        split_ifs <;> simp_all [Finset.subset_iff]
      have hsyn : ∀ A : Finset (Fin (3 * m)), A.Nonempty → A.card ≤ 3 →
          ∑ y : S, ∏ a ∈ A, M a y = ccz_layer_syndrome m A := by
        intro A hA hA3
        rw [← hcount]
        exact hS.2 A ⟨hA.card_pos, hA3⟩
      have hM01 : ∀ a y, M a y * M a y = M a y := by
        intro a y; simp only [M, Matrix.of_apply]; split_ifs <;> simp
  5. The order-1 and order-2 moments vanish, while order-3 moments equal the syndrome.

    Sets of size 1 and 2 have syndrome 0 by the cardinality lemma, so order-1 and order-2 moments vanish (using idempotence when a = b). For triples, the sum evaluates directly to the syndrome of {a, b, c}.

    lines 67–85

    uses ccz_layer_syndrome_eq_zero_of_card_ne, Finset.card_le_two, Finset.card_pair, Finset.prod_pair, Finset.card_le_three, Finset.sum_congr, Matrix.of_apply, Finset.prod_boole, Finset.mem_insert, Finset.mem_singleton, forall_eq_or_imp, forall_eq

      have h1 : ∀ a, ∑ y : S, M a y = 0 := by
        intro a
        have := hsyn {a} (by simp) (by simp)
        rw [ccz_layer_syndrome_eq_zero_of_card_ne _ (by simp)] at this
        simpa using this
      have h2 : ∀ a b, ∑ y : S, M a y * M b y = 0 := by
        intro a b
        by_cases hab : a = b
        · subst hab; simp only [hM01]; exact h1 a
        · have := hsyn {a, b} (by simp) ((Finset.card_le_two).trans (by norm_num))
          rw [ccz_layer_syndrome_eq_zero_of_card_ne _ (by rw [Finset.card_pair hab]; norm_num)] at this
          simpa only [Finset.prod_pair hab] using this
      have h3 : ∀ a b c, ∑ y : S, M a y * M b y * M c y = ccz_layer_syndrome m {a, b, c} := by
        intro a b c
        rw [← hsyn {a, b, c} (by simp) Finset.card_le_three]
        refine Finset.sum_congr rfl fun y _ => ?_
        simp only [M, Matrix.of_apply, Finset.prod_boole,
          Finset.mem_insert, Finset.mem_singleton, forall_eq_or_imp, forall_eq]
        split_ifs <;> simp_all
  6. The set of parities S is nonempty.

    The first CCZ block {0, 1, 2} has syndrome 1, so the sum over S of M 0 y * M 1 y * M 2 y is 1. If S were empty, this sum would be 0, a contradiction in ZMod 2.

    lines 87–94

    uses not_nonempty_iff, Finset.univ_eq_empty, Finset.sum_empty, if_pos, zero_ne_one

      have hne : Nonempty S := by
        by_contra hS0
        rw [not_nonempty_iff] at hS0
        have := h3 ⟨0, by omega⟩ ⟨1, by omega⟩ ⟨2, by omega⟩
        rw [Finset.univ_eq_empty, Finset.sum_empty] at this
        unfold ccz_layer_syndrome at this
        rw [if_pos ⟨⟨0, by omega⟩, by simp⟩] at this
        exact zero_ne_one this
  7. Evaluating L(v, lambda) against the partner qubits p, q recovers the component v i.

    The linear map L maps (v, lambda) to M.transpose v + lambda * 1. Multiplying by M p y * M q y and summing over S, the lambda term vanishes because order-2 moments are zero. The v term sums v a * s({a, p, q}), which reduces to v i because the syndrome is 1 only when a = i.

    lines 96–116

    uses Matrix.mulVecLin, LinearMap.coprod, LinearMap.smulRight, LinearMap.id, Matrix.vecMul, dotProduct, mul_comm, ccz_layer_syndrome_partner, add_mul, Finset.sum_add_distrib, Finset.sum_mul, Finset.sum_comm, Finset.mul_sum, Finset.sum_congr, mul_zero, mul_ite, mul_one, Finset.sum_ite_eq', Finset.mem_univ, if_true, add_zero

      let L : (Fin (3 * m) → ZMod 2) × ZMod 2 →ₗ[ZMod 2] (S → ZMod 2) :=
        (Matrix.mulVecLin M.transpose).coprod (LinearMap.smulRight LinearMap.id 1)
      have hL : ∀ v l y, L (v, l) y = (∑ a, M a y * v a) + l := by
        intro v l y
        simp [L, Matrix.vecMul, dotProduct, mul_comm]
      -- evaluating against the two partners of `i` recovers `v i`
      have heval : ∀ v l i, ∃ p q : Fin (3 * m), ∑ y : S, L (v, l) y * M p y * M q y = v i := by
        intro v l i
        obtain ⟨p, q, hpq⟩ := ccz_layer_syndrome_partner i
        refine ⟨p, q, ?_⟩
        simp only [hL, add_mul, Finset.sum_add_distrib, Finset.sum_mul]
        rw [Finset.sum_comm]
        have e1 : ∀ a, ∑ y : S, M a y * v a * M p y * M q y = v a * ccz_layer_syndrome m {a, p, q} := by
          intro a
          rw [← h3, Finset.mul_sum]
          refine Finset.sum_congr rfl fun y _ => by ring
        have e2 : ∑ y : S, l * M p y * M q y = 0 := by
          rw [← mul_zero l, ← h2 p q, Finset.mul_sum]
          refine Finset.sum_congr rfl fun y _ => by ring
        simp only [e1, e2, hpq, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ,
          if_true, add_zero]
  8. The linear map L is injective.

    If L(v, lambda) = 0, the evaluation against partner qubits shows v i = 0 for all i, so v = 0. Then lambda * 1 = 0, which implies lambda = 0 because S is nonempty. Thus the kernel of L is trivial.

    lines 117–130

    uses LinearMap.ker_eq_bot, LinearMap.ker_eq_bot', congrFun, Pi.zero_apply, mul_zero, Finset.sum_const_zero, zero_add

      have hLinj : Function.Injective L := by
        rw [← LinearMap.ker_eq_bot, LinearMap.ker_eq_bot']
        rintro ⟨v, l⟩ hvl
        have hv : v = 0 := by
          funext i
          obtain ⟨p, q, h⟩ := heval v l i
          rw [← h, hvl]
          simp
        subst hv
        obtain ⟨y⟩ := hne
        have := congrFun hvl y
        rw [hL] at this
        simp only [Pi.zero_apply, mul_zero, Finset.sum_const_zero, zero_add] at this
        rw [this]; rfl
  9. The range of L is contained in the kernel of M.

    Multiplying M by L(v, lambda) computes M(M.transpose v + lambda * 1). In each row, the v component involves order-2 moments of M and the lambda component involves order-1 moments. Since all order-1 and order-2 moments vanish, the product is zero.

    lines 132–144

    uses LinearMap.range, LinearMap.ker, LinearMap.mem_ker, Matrix.mulVecLin_apply, Matrix.mulVec, dotProduct, Pi.zero_apply, mul_add, Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_comm, zero_mul, Finset.sum_mul, Finset.sum_congr, Finset.sum_const_zero, add_zero

      have hker : LinearMap.range L ≤ LinearMap.ker M.mulVecLin := by
        rintro x ⟨⟨v, l⟩, rfl⟩
        rw [LinearMap.mem_ker]
        funext b
        simp only [Matrix.mulVecLin_apply, Matrix.mulVec, dotProduct, hL, Pi.zero_apply, mul_add,
          Finset.sum_add_distrib, Finset.mul_sum]
        rw [Finset.sum_comm]
        have e1 : ∀ a, ∑ y : S, M b y * (M a y * v a) = 0 := by
          intro a
          rw [← zero_mul (v a), ← h2 b a, Finset.sum_mul]
          refine Finset.sum_congr rfl fun y _ => by ring
        have e2 : ∑ y : S, M b y * l = 0 := by rw [← Finset.sum_mul, h1, zero_mul]
        simp only [e1, e2, Finset.sum_const_zero, add_zero]
  10. The cardinality of S is at least 6m + 1.

    Since L is injective, its restriction to lambda = 0 shows M.transpose has rank 3m, so M has rank 3m. In addition, the range of L has dimension 3m + 1 and lies in the kernel of M, so the nullity of M is at least 3m + 1. By rank-nullity, the dimension of the parity space |S| is rank plus nullity, which is at least 3m + (3m + 1) = 6m + 1.

    lines 146–158

    uses Matrix.rank, LinearMap.finrank_range_of_inj, Module.finrank_fin_fun, Matrix.rank_transpose, LinearMap.finrank_range_add_finrank_ker, Submodule.finrank_mono, Module.finrank_prod, Module.finrank_self, Module.finrank_fintype_fun_eq_card, Fintype.card_coe, Prod.ext_iff

      have hrankT : M.transpose.rank = 3 * m := by
        have hinj : Function.Injective (Matrix.mulVecLin M.transpose) := by
          intro v w hvw
          have := @hLinj (v, 0) (w, 0) (by simpa [L] using hvw)
          exact (Prod.ext_iff.1 this).1
        rw [Matrix.rank, LinearMap.finrank_range_of_inj hinj, Module.finrank_fin_fun]
      have hrank : M.rank = 3 * m := by rw [← Matrix.rank_transpose]; exact hrankT
      have hnull := LinearMap.finrank_range_add_finrank_ker M.mulVecLin
      have hmono := Submodule.finrank_mono hker
      rw [LinearMap.finrank_range_of_inj hLinj, Module.finrank_prod, Module.finrank_fin_fun,
        Module.finrank_self] at hmono
      rw [← Matrix.rank, hrank, Module.finrank_fintype_fun_eq_card, Fintype.card_coe] at hnull
      omega
LinearMap.finrank_range_add_finrank_ker
In any vector space, rank-nullity states that the dimension of the domain equals the rank of a linear map plus the dimension of its kernel.

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

/-- The CCZ-layer syndrome vanishes on every set that is not of size three. -/theorem ccz_layer_syndrome_eq_zero_of_card_ne {m : ℕ} (A : Finset (Fin (3 * m)))    (hA : A.card ≠ 3) : ccz_layer_syndrome m A = 0 := by  unfold ccz_layer_syndrome  rw [if_neg]  rintro ⟨j, rfl⟩  apply hA  rw [Finset.card_eq_three]  refine ⟨_, _, _, ?_, ?_, ?_, rfl⟩ <;> simp [Fin.ext_iff]/-- For every qubit `i` of the layer, the two other qubits `p`, `q` of its CCZ block single out`i`: the syndrome of `{a, p, q}` is `1` exactly when `a = i`. -/theorem ccz_layer_syndrome_partner {m : ℕ} (i : Fin (3 * m)) :    ∃ p q : Fin (3 * m), ∀ a, ccz_layer_syndrome m {a, p, q} = if a = i then 1 else 0 := by  have hi := i.isLt  refine ⟨⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩,    ⟨3 * (i.val / 3) + (i.val % 3 + 2) % 3, by omega⟩, fun a => ?_⟩  unfold ccz_layer_syndrome  by_cases hai : a = i  · subst hai    rw [if_pos rfl, if_pos]    refine ⟨⟨a.val / 3, by omega⟩, ?_⟩    ext x    simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]    omega  · rw [if_neg hai, if_neg]    rintro ⟨j, hj⟩    have h1 : a ∈ ({a, ⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩,        ⟨3 * (i.val / 3) + (i.val % 3 + 2) % 3, by omega⟩} : Finset (Fin (3 * m))) := by simp    have h2 : (⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩ : Fin (3 * m)) ∈        ({a, ⟨3 * (i.val / 3) + (i.val % 3 + 1) % 3, by omega⟩,        ⟨3 * (i.val / 3) + (i.val % 3 + 2) % 3, by omega⟩} : Finset (Fin (3 * m))) := by simp    have h3 : (⟨3 * j.val, by omega⟩ : Fin (3 * m)) ∈        ({⟨3 * j.val, by omega⟩, ⟨3 * j.val + 1, by omega⟩, ⟨3 * j.val + 2, by omega⟩} :          Finset (Fin (3 * m))) := by simp    have h4 : (⟨3 * j.val + 1, by omega⟩ : Fin (3 * m)) ∈        ({⟨3 * j.val, by omega⟩, ⟨3 * j.val + 1, by omega⟩, ⟨3 * j.val + 2, by omega⟩} :          Finset (Fin (3 * m))) := by simp    have h5 : (⟨3 * j.val + 2, by omega⟩ : Fin (3 * m)) ∈        ({⟨3 * j.val, by omega⟩, ⟨3 * j.val + 1, by omega⟩, ⟨3 * j.val + 2, by omega⟩} :          Finset (Fin (3 * m))) := by simp    rw [hj] at h1 h2    rw [← hj] at h3 h4 h5    simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] at h1 h2 h3 h4 h5    have := Fin.val_ne_of_ne hai    omegatheorem ccz_layer_parity_repr_card_ge (m : ℕ) (hm : 1 ≤ m) (S : Finset (Finset (Fin (3 * m)))) (hS : is_parity_repr S (ccz_layer_syndrome m)) : 6 * m + 1 ≤ S.card := by  classical  -- the incidence matrix of qubits against parities  let M : Matrix (Fin (3 * m)) S (ZMod 2) := Matrix.of fun a y => if a ∈ (y : Finset _) then 1 else 0  have hcount : ∀ A : Finset (Fin (3 * m)),      ((S.filter fun y => A ⊆ y).card : ZMod 2) = ∑ y : S, ∏ a ∈ A, M a y := by    intro A    simp only [M, Matrix.of_apply, Finset.prod_boole]    rw [Finset.natCast_card_filter, ← Finset.sum_coe_sort S]    refine Finset.sum_congr rfl fun y _ => ?_    split_ifs <;> simp_all [Finset.subset_iff]  have hsyn : ∀ A : Finset (Fin (3 * m)), A.Nonempty → A.card ≤ 3 →      ∑ y : S, ∏ a ∈ A, M a y = ccz_layer_syndrome m A := by    intro A hA hA3    rw [← hcount]    exact hS.2 A ⟨hA.card_pos, hA3⟩  have hM01 : ∀ a y, M a y * M a y = M a y := by    intro a y; simp only [M, Matrix.of_apply]; split_ifs <;> simp  -- order-one and order-two moments vanish  have h1 : ∀ a, ∑ y : S, M a y = 0 := by    intro a    have := hsyn {a} (by simp) (by simp)    rw [ccz_layer_syndrome_eq_zero_of_card_ne _ (by simp)] at this    simpa using this  have h2 : ∀ a b, ∑ y : S, M a y * M b y = 0 := by    intro a b    by_cases hab : a = b    · subst hab; simp only [hM01]; exact h1 a    · have := hsyn {a, b} (by simp) ((Finset.card_le_two).trans (by norm_num))      rw [ccz_layer_syndrome_eq_zero_of_card_ne _ (by rw [Finset.card_pair hab]; norm_num)] at this      simpa only [Finset.prod_pair hab] using this  have h3 : ∀ a b c, ∑ y : S, M a y * M b y * M c y = ccz_layer_syndrome m {a, b, c} := by    intro a b c    rw [← hsyn {a, b, c} (by simp) Finset.card_le_three]    refine Finset.sum_congr rfl fun y _ => ?_    simp only [M, Matrix.of_apply, Finset.prod_boole,      Finset.mem_insert, Finset.mem_singleton, forall_eq_or_imp, forall_eq]    split_ifs <;> simp_all  -- S is nonempty: the first CCZ triple has odd moment  have hne : Nonempty S := by    by_contra hS0    rw [not_nonempty_iff] at hS0    have := h3 ⟨0, by omega⟩ ⟨1, by omega⟩ ⟨2, by omega⟩    rw [Finset.univ_eq_empty, Finset.sum_empty] at this    unfold ccz_layer_syndrome at this    rw [if_pos ⟨⟨0, by omega⟩, by simp⟩] at this    exact zero_ne_one this  -- the map (v, λ) ↦ M.transpose v + λ · 1  let L : (Fin (3 * m) → ZMod 2) × ZMod 2 →ₗ[ZMod 2] (S → ZMod 2) :=    (Matrix.mulVecLin M.transpose).coprod (LinearMap.smulRight LinearMap.id 1)  have hL : ∀ v l y, L (v, l) y = (∑ a, M a y * v a) + l := by    intro v l y    simp [L, Matrix.vecMul, dotProduct, mul_comm]  -- evaluating against the two partners of `i` recovers `v i`  have heval : ∀ v l i, ∃ p q : Fin (3 * m), ∑ y : S, L (v, l) y * M p y * M q y = v i := by    intro v l i    obtain ⟨p, q, hpq⟩ := ccz_layer_syndrome_partner i    refine ⟨p, q, ?_⟩    simp only [hL, add_mul, Finset.sum_add_distrib, Finset.sum_mul]    rw [Finset.sum_comm]    have e1 : ∀ a, ∑ y : S, M a y * v a * M p y * M q y = v a * ccz_layer_syndrome m {a, p, q} := by      intro a      rw [← h3, Finset.mul_sum]      refine Finset.sum_congr rfl fun y _ => by ring    have e2 : ∑ y : S, l * M p y * M q y = 0 := by      rw [← mul_zero l, ← h2 p q, Finset.mul_sum]      refine Finset.sum_congr rfl fun y _ => by ring    simp only [e1, e2, hpq, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ,      if_true, add_zero]  have hLinj : Function.Injective L := by    rw [← LinearMap.ker_eq_bot, LinearMap.ker_eq_bot']    rintro ⟨v, l⟩ hvl    have hv : v = 0 := by      funext i      obtain ⟨p, q, h⟩ := heval v l i      rw [← h, hvl]      simp    subst hv    obtain ⟨y⟩ := hne    have := congrFun hvl y    rw [hL] at this    simp only [Pi.zero_apply, mul_zero, Finset.sum_const_zero, zero_add] at this    rw [this]; rfl  -- the image of L lies in the kernel of M  have hker : LinearMap.range L ≤ LinearMap.ker M.mulVecLin := by    rintro x ⟨⟨v, l⟩, rfl⟩    rw [LinearMap.mem_ker]    funext b    simp only [Matrix.mulVecLin_apply, Matrix.mulVec, dotProduct, hL, Pi.zero_apply, mul_add,      Finset.sum_add_distrib, Finset.mul_sum]    rw [Finset.sum_comm]    have e1 : ∀ a, ∑ y : S, M b y * (M a y * v a) = 0 := by      intro a      rw [← zero_mul (v a), ← h2 b a, Finset.sum_mul]      refine Finset.sum_congr rfl fun y _ => by ring    have e2 : ∑ y : S, M b y * l = 0 := by rw [← Finset.sum_mul, h1, zero_mul]    simp only [e1, e2, Finset.sum_const_zero, add_zero]  -- dimension count  have hrankT : M.transpose.rank = 3 * m := by    have hinj : Function.Injective (Matrix.mulVecLin M.transpose) := by      intro v w hvw      have := @hLinj (v, 0) (w, 0) (by simpa [L] using hvw)      exact (Prod.ext_iff.1 this).1    rw [Matrix.rank, LinearMap.finrank_range_of_inj hinj, Module.finrank_fin_fun]  have hrank : M.rank = 3 * m := by rw [← Matrix.rank_transpose]; exact hrankT  have hnull := LinearMap.finrank_range_add_finrank_ker M.mulVecLin  have hmono := Submodule.finrank_mono hker  rw [LinearMap.finrank_range_of_inj hLinj, Module.finrank_prod, Module.finrank_fin_fun,    Module.finrank_self] at hmono  rw [← Matrix.rank, hrank, Module.finrank_fintype_fun_eq_card, Fintype.card_coe] at hnull  omega
See it in the graphDiscuss this resultChallenge it