AFTD Auto-Formalizing Theoretical Domains

quadratic_comparison_evaluation_kernel_and_projector

theoremverifiedformalization

Let n >= 3, N = C(n,2), nu_triangle = C(n,3). Strict orders on [n] are given by permutations x of Fin n (x i = rank of label i); for an edge {a,b}, a<b, d_ab(x) = +1 if x_a < x_b and -1 otherwise. In the formal feature spaces F_1 = span{1, d_e} and F_2 = span{1, d_e, d_e d_f : e, f distinct edges} with orthonormal coordinate bases, let phi_1(x), phi_2(x) be the evaluation vectors, kappa_abc = e_(ab,ac) - e_(ab,bc) + e_(ac,bc) - e_0 the triangle relation vector of a < b < c, U_triangle the matrix with columns kappa_abc, v_triangle = U_triangle 1, and Pi_ord = I - (1/3) U_triangle U_triangle^T + v_triangle v_triangle^T / (3 (nu_triangle + 3)). Then: (1) the features 1, d_e of F_1 are linearly independent as real functions on strict orders; (2) the evaluation kernel of F_2 (coefficient vectors c with <phi_2(x), c> = 0 for every strict order x) is the span of the kappa_abc; (3) the kappa_abc are linearly independent; (4) Pi_ord is the orthogonal projector onto the evaluated quotient, i.e. Pi_ord^2 = Pi_ord, Pi_ord^T = Pi_ord, and the kernel of Pi_ord equals the evaluation kernel; (5) the image of Pi_ord has dimension 1 + N + C(N,2) - nu_triangle; (6) Pi_ord phi_2(x) = phi_2(x) for every strict order x.

Statement

theorem quadratic_comparison_evaluation_kernel_and_projector (n : ℕ) (hn : 3 ≤ n) :
    LinearIndependent ℝ
        (fun i : comparison_feature1 n => fun x : Equiv.Perm (Fin n) => comparison_phi1 x i) ∧
      LinearMap.ker (comparison_eval_matrix n).mulVecLin =
        Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) ∧
      LinearIndependent ℝ (comparison_triangle_kappa (n := n)) ∧
      comparison_pi_ord n * comparison_pi_ord n = comparison_pi_ord n ∧
      (comparison_pi_ord n).transpose = comparison_pi_ord n ∧
      LinearMap.ker (comparison_pi_ord n).mulVecLin =
        LinearMap.ker (comparison_eval_matrix n).mulVecLin ∧
      Module.finrank ℝ (LinearMap.range (comparison_pi_ord n).mulVecLin) =
        1 + n.choose 2 + (n.choose 2).choose 2 - n.choose 3 ∧
      ∀ x : Equiv.Perm (Fin n),
        Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x
Formalizes
arXiv:2610.34762 (Quantum ordinal selection with two comparisons), Section 3.1, Lemma 1 (Quadratic evaluation kernel). Strict orders are modelled as permutations (ranks); 'orthogonal projector onto the evaluated quotient' is stated as: symmetric, idempotent, with kernel equal to the evaluation kernel.
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 17
  • comparison_pi_ordThe real square matrix Pi_ord on comparison_feature2 n defined by Pi_ord = I - (1/3) U U^T + (1 / (3 (C(n,3) + 3))) v v^T, where U =…
  • comparison_eval_matrixThe real evaluation matrix of F_2 on strict orders, with rows indexed by the permutations x of Fin n (strict orders given by ranks) and…
  • comparison_phi1The real linear evaluation vector phi_1(x) : comparison_feature1 n → ℝ of a strict order x (a permutation of Fin n giving the ranks): its…
  • comparison_phi2The real quadratic evaluation vector phi_2(x) : comparison_feature2 n → ℝ of a strict order x (a permutation of Fin n giving the ranks):…
  • comparison_triangle_gramThe Gram matrix of the triangle relation vectors is U_triangle^T U_triangle = 3 I + 1 1^T: each kappa_abc has squared norm 4 and two…
  • comparison_feature2The type indexing the orthonormal coordinate basis of the formal quadratic feature space F_2 = span{1, d_e, d_e d_f}: the sum type of…
  • comparison_triangle_matrixThe real matrix U_triangle with rows indexed by comparison_feature2 n and columns by triangles, whose column at the triangle t is the…
  • comparison_feature1The type indexing the orthonormal coordinate basis of the formal linear feature space F_1 = span{1, d_e}: Option (comparison_edge n),…
  • comparison_phi1_linearIndependentThe constant function 1 and the comparison signs d_e, e an edge of [n], are linearly independent real functions on strict orders…
  • comparison_triangle_kappaThe real triangle relation vector kappa_abc : comparison_feature2 n → ℝ of a triangle a < b < c: kappa_abc = e_(ab,ac) - e_(ab,bc) +…
  • comparison_eval_ker_le_span_kappaEvery formal quadratic feature vector c in F_2 that evaluates to zero on every strict order (<phi_2(x), c> = 0 for all permutations x of…
  • comparison_edgeThe type of edges of the label set [n] = Fin n: the subtype of pairs (a, b) in Fin n × Fin n with a < b, each unordered edge {a, b} being…
  • comparison_triangleThe type of triangles of the label set [n] = Fin n: the subtype of triples (a, (b, c)) in Fin n × Fin n × Fin n with a < b and b < c.
  • comparison_pi_ord_mulVec_phi2Pi_ord fixes the quadratic evaluation vector phi_2(x) of every strict order x: U_triangle^T phi_2(x) = 0 by the triangle relations, hence…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • comparison_triangle_kappa_mem_eval_kerEach triangle relation vector kappa_abc evaluates to zero on every strict order: d_ab d_ac - d_ab d_bc + d_ac d_bc - 1 = 0.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

For any natural number $n \ge 3$, the following eight statements hold simultaneously: 1. The family of functions from the symmetric group $S_n$ (Equiv.Perm (Fin n)) to $\mathbb{R}$, indexed by first-order comparison features $i \in \text{comparison\_feature1 } n$, given by $x \mapsto \phi_1(x)(i)$, is linearly independent over $\mathbb{R}$. 2. The kernel of the linear map induced by matrix-vector multiplication by the second-order evaluation matrix $\text{comparison\_eval\_matrix } n$ (from $\mathbb{R}^{\text{comparison\_feature2 } n}$ to $\mathbb{R}^{S_n}$) equals the $\mathbb{R}$-linear span of the range of the triangle vectors $\kappa_t$ across all triangles $t \in \text{comparison\_triangle } n$. 3. The family of triangle vectors $(\kappa_t)_{t \in \text{comparison\_triangle } n}$ is linearly independent over $\mathbb{R}$. 4. The matrix $\Pi_{\text{ord}}(n)$ (comparison_pi_ord n) is idempotent: $\Pi_{\text{ord}}(n) \cdot \Pi_{\text{ord}}(n) = \Pi_{\text{ord}}(n)$. 5. The matrix $\Pi_{\text{ord}}(n)$ is symmetric: $\Pi_{\text{ord}}(n)^T = \Pi_{\text{ord}}(n)$. 6. The kernel of the linear map induced by $\Pi_{\text{ord}}(n)$ equals the kernel of the linear map induced by $\text{comparison\_eval\_matrix } n$. 7. The dimension (as an $\mathbb{R}$-module) of the range of the linear map induced by $\Pi_{\text{ord}}(n)$ equals $1 + \binom{n}{2} + \binom{\binom{n}{2}}{2} - \binom{n}{3}$. 8. For every permutation $x \in S_n$, $\Pi_{\text{ord}}(n)$ fixes the second-order feature vector $\phi_2(x)$: that is, $\Pi_{\text{ord}}(n) \phi_2(x) = \phi_2(x)$.

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

The proof establishes the algebraic and geometric structure of the quadratic feature space F_2 for strict orders on n elements. First, the Gram matrix of the nu = C(n, 3) triangle relation vectors kappa_abc is shown to be U^T U = 3 I + J, which is explicitly inverted by B = (1/3) I - 1/(3(nu+3)) J. The orthogonal projector onto the evaluated quotient is identified as Pi_ord = I - U B U^T, yielding its idempotence, symmetry, and kernel ker Pi_ord = range U = span(kappa_abc). Since B (U^T U) = I, the triangle relation vectors are linearly independent, so the kernel has dimension nu, and the rank-nullity theorem computes the dimension of the image of Pi_ord.

  1. The number of comparison edges on n elements is C(n, 2).

    We construct an explicit bijection between comparison edges (ordered pairs (a, b) with a < b) and 2-element subsets {a, b} of Fin n. Injectivity follows because the elements of {a, b} are ordered, and surjectivity follows by ordering any two distinct elements. The cardinality of 2-element subsets is C(n, 2) by Fintype.card_finset_len.

    lines 1–23

    uses Fintype.card_finset_len, Fintype.card_fin, Fintype.card_congr, Equiv.ofBijective, Finset.card_pair, ne_of_lt, lt_or_gt_of_ne, Finset.pair_comm

    theorem cmpf_card_edge (n : ℕ) : Fintype.card (comparison_edge n) = n.choose 2 := by
      classical
      have hc := Fintype.card_finset_len (α := Fin n) 2
      rw [Fintype.card_fin] at hc
      rw [← hc]
      refine Fintype.card_congr (Equiv.ofBijective
        (fun e : comparison_edge n => (⟨{e.1.1, e.1.2}, Finset.card_pair (ne_of_lt e.2)⟩ :
          {s : Finset (Fin n) // s.card = 2})) ⟨?_, ?_⟩)
      · rintro ⟨⟨a, b⟩, hab⟩ ⟨⟨a', b'⟩, hab'⟩ h
        have hab2 : a.val < b.val := hab
        have hab2' : a'.val < b'.val := hab'
        simp only [Subtype.mk.injEq] at h
        have h1 : a ∈ ({a', b'} : Finset (Fin n)) := h ▸ Finset.mem_insert_self _ _
        have h2 : b ∈ ({a', b'} : Finset (Fin n)) := h ▸ by simp
        simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] at h1 h2
        simp only [Subtype.mk.injEq, Prod.mk.injEq, Fin.ext_iff]
        omega
      · rintro ⟨s, hs⟩
        obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.mp hs
        rcases lt_or_gt_of_ne hxy with h | h
        · exact ⟨⟨(x, y), h⟩, rfl⟩
        · exact ⟨⟨(y, x), h⟩, by simp only [Subtype.mk.injEq]; exact Finset.pair_comm _ _⟩
    
  2. The number of comparison triangles on n elements is C(n, 3).

    Similarly, comparison triangles (ordered triples (a, b, c) with a < b < c) are in bijection with 3-element subsets {a, b, c} of Fin n. Injective ordering and case analysis on the permutations of three distinct elements ensure bijectivity, giving C(n, 3) total triangles.

    lines 24–60

    uses Fintype.card_finset_len, Fintype.card_fin, Fintype.card_congr, Equiv.ofBijective, Finset.card_eq_three, ne_of_lt, lt_or_gt_of_ne

    theorem cmpf_card_triangle (n : ℕ) : Fintype.card (comparison_triangle n) = n.choose 3 := by
      classical
      have hc := Fintype.card_finset_len (α := Fin n) 3
      rw [Fintype.card_fin] at hc
      rw [← hc]
      refine Fintype.card_congr (Equiv.ofBijective
        (fun t : comparison_triangle n => (⟨{t.1.1, t.1.2.1, t.1.2.2}, by
          rw [Finset.card_eq_three]
          exact ⟨_, _, _, ne_of_lt t.2.1, ne_of_lt (t.2.1.trans t.2.2), ne_of_lt t.2.2, rfl⟩⟩ :
          {s : Finset (Fin n) // s.card = 3})) ⟨?_, ?_⟩)
      · rintro ⟨⟨a, b, c⟩, hab, hbc⟩ ⟨⟨a', b', c'⟩, hab', hbc'⟩ h
        simp only [Fin.lt_def] at hab hbc hab' hbc'
        simp only [Subtype.mk.injEq] at h
        have m : ∀ v, v ∈ ({a, b, c} : Finset (Fin n)) ↔ v ∈ ({a', b', c'} : Finset (Fin n)) :=
          fun v => by rw [h]
        have h1 := (m a).mp (by simp)
        have h2 := (m b).mp (by simp)
        have h3 := (m c).mp (by simp)
        have h4 := (m a').mpr (by simp)
        have h5 := (m b').mpr (by simp)
        have h6 := (m c').mpr (by simp)
        simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] at h1 h2 h3 h4 h5 h6
        simp only [Subtype.mk.injEq, Prod.mk.injEq, Fin.ext_iff]
        omega
      · rintro ⟨s, hs⟩
        obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hs
        rcases lt_or_gt_of_ne hxy with h1 | h1 <;> rcases lt_or_gt_of_ne hxz with h2 | h2 <;>
          rcases lt_or_gt_of_ne hyz with h3 | h3
        · exact ⟨⟨(x, y, z), h1, h3⟩, by simp only [Subtype.mk.injEq]⟩
        · exact ⟨⟨(x, z, y), h2, h3⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩
        · exact absurd (h1.trans h3) (not_lt.mpr h2.le)
        · exact ⟨⟨(z, x, y), h2, h1⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩
        · exact ⟨⟨(y, x, z), h1, h2⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩
        · exact absurd (h3.trans h1) (not_lt.mpr h2.le)
        · exact ⟨⟨(y, z, x), h3, h2⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩
        · exact ⟨⟨(z, y, x), h3, h1⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩
    
  3. The column space of the triangle relation matrix U equals the span of the triangle relation vectors kappa_abc, and the Gram matrix satisfies U^T U = 3 I + J.

    Let U be the feature-by-triangle matrix whose columns are the triangle relation vectors kappa_t. By Matrix.range_mulVecLin, the range of U as a linear map is the span of the kappa_t. The Gram matrix identity U^T U = 3 I + J (where J is the all-ones matrix) and the counts N = C(n, 2) and nu = C(n, 3) are recorded from the helper lemmas.

    lines 61–86

    uses comparison_triangle_gram, cmpf_card_triangle, cmpf_card_edge, Matrix.range_mulVecLin

    theorem quadratic_comparison_evaluation_kernel_and_projector (n : ℕ) (hn : 3 ≤ n) :
        LinearIndependent ℝ
            (fun i : comparison_feature1 n => fun x : Equiv.Perm (Fin n) => comparison_phi1 x i) ∧
          LinearMap.ker (comparison_eval_matrix n).mulVecLin =
            Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) ∧
          LinearIndependent ℝ (comparison_triangle_kappa (n := n)) ∧
          comparison_pi_ord n * comparison_pi_ord n = comparison_pi_ord n ∧
          (comparison_pi_ord n).transpose = comparison_pi_ord n ∧
          LinearMap.ker (comparison_pi_ord n).mulVecLin =
            LinearMap.ker (comparison_eval_matrix n).mulVecLin ∧
          Module.finrank ℝ (LinearMap.range (comparison_pi_ord n).mulVecLin) =
            1 + n.choose 2 + (n.choose 2).choose 2 - n.choose 3 ∧
          ∀ x : Equiv.Perm (Fin n),
            Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x := by
      classical
      set U := comparison_triangle_matrix n with hU
      have hG := comparison_triangle_gram n
      rw [← hU] at hG
      have hν := cmpf_card_triangle n
      have hN := cmpf_card_edge n
      have hUt : U.transpose = fun t => comparison_triangle_kappa t := by
        funext t i; rfl
      have hrangeU : LinearMap.range U.mulVecLin =
          Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) := by
        rw [Matrix.range_mulVecLin]
        rfl
  4. The evaluation kernel of F_2 equals the span of the triangle relation vectors kappa_abc.

    By antisymmetry: the evaluation kernel is contained in the span of the kappa vectors by comparison_eval_ker_le_span_kappa, and conversely every kappa vector belongs to the kernel by comparison_triangle_kappa_mem_eval_ker because the triangle relation holds for all strict orders.

    lines 87–92

    uses le_antisymm, comparison_eval_ker_le_span_kappa, LinearMap.mem_ker, Matrix.mulVecLin_apply, comparison_triangle_kappa_mem_eval_ker

      have hker : LinearMap.ker (comparison_eval_matrix n).mulVecLin =
          Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) := by
        refine le_antisymm (comparison_eval_ker_le_span_kappa n) (Submodule.span_le.mpr ?_)
        rintro _ ⟨t, rfl⟩
        exact LinearMap.mem_ker.mpr (by
          rw [Matrix.mulVecLin_apply]; exact comparison_triangle_kappa_mem_eval_ker n t)
  5. The matrix B = (1/3) I - kappa_c J is the exact symmetric inverse of the Gram matrix U^T U.

    With J the nu × nu all-ones matrix, we have J^2 = nu J. Choosing kappa_c = 1 / (3 (nu + 3)), direct multiplication shows that B (3 I + J) = I, so B is the two-sided inverse of the Gram matrix U^T U. Furthermore, B is symmetric because I and J are symmetric.

    lines 93–118

    uses Matrix.sub_mul, Matrix.mul_add, Matrix.smul_mul, Matrix.one_mul, Matrix.mul_smul, Matrix.mul_one, Matrix.transpose_sub, Matrix.transpose_smul, Matrix.transpose_one

      set ν : ℝ := (n.choose 3 : ℝ) with hνdef
      set J : Matrix (comparison_triangle n) (comparison_triangle n) ℝ :=
        Matrix.of fun _ _ => (1 : ℝ) with hJ
      set κc : ℝ := 1 / (3 * (ν + 3)) with hκc
      set B : Matrix (comparison_triangle n) (comparison_triangle n) ℝ :=
        (1 / 3 : ℝ) • (1 : Matrix (comparison_triangle n) (comparison_triangle n) ℝ) - κc • J
        with hB
      have hJJ : J * J = ν • J := by
        ext i j
        simp [J, Matrix.mul_apply, hν, ν]
      have hν0 : (0 : ℝ) ≤ ν := by positivity
      have hscal : (1 / 3 : ℝ) - κc * 3 - κc * ν = 0 := by
        rw [hκc]; field_simp; ring
      have hBM : B * (U.transpose * U) = 1 := by
        rw [hG, hB, Matrix.sub_mul, Matrix.mul_add, Matrix.mul_add, Matrix.smul_mul, Matrix.smul_mul,
          Matrix.smul_mul, Matrix.smul_mul, Matrix.one_mul, Matrix.one_mul, Matrix.mul_smul,
          Matrix.mul_one, hJJ]
        simp only [smul_smul]
        ext i j
        simp only [Matrix.sub_apply, Matrix.add_apply, Matrix.smul_apply, smul_eq_mul, J,
          Matrix.of_apply, Matrix.one_apply]
        split_ifs <;> linarith [hscal]
      have hBt : B.transpose = B := by
        rw [hB, Matrix.transpose_sub, Matrix.transpose_smul, Matrix.transpose_smul,
          Matrix.transpose_one]
        congr 2
  6. The projector Pi_ord equals I - U B U^T and satisfies (U B U^T) U = U.

    Since v = U 1, the rank-one term v v^T equals U J U^T. Substituting B = (1/3) I - kappa_c J into U B U^T yields (1/3) U U^T - kappa_c v v^T, which exactly matches the definition of Pi_ord as I - U B U^T. Multiplying on the right by U and using B (U^T U) = I gives (U B U^T) U = U.

    lines 119–135

    uses Finset.sum_comm, Matrix.mul_assoc, Matrix.mul_one

      have hPi : comparison_pi_ord n = 1 - U * B * U.transpose := by
        have hv : Matrix.vecMulVec (U.mulVec (fun _ => 1)) (U.mulVec (fun _ => 1)) =
            U * J * U.transpose := by
          ext i j
          simp only [Matrix.vecMulVec_apply, Matrix.mulVec, dotProduct, mul_one, Matrix.mul_apply,
            J, Matrix.of_apply, Matrix.transpose_apply, Finset.sum_mul]
          rw [Finset.sum_comm]
          simp only [Finset.mul_sum]
        unfold comparison_pi_ord
        dsimp only
        rw [← hU, hv, hB, Matrix.mul_sub, Matrix.sub_mul, Matrix.mul_smul, Matrix.smul_mul,
          Matrix.mul_smul, Matrix.smul_mul, Matrix.mul_one, hκc, hνdef]
        abel
      have hUBU : U * B * U.transpose * U = U := by
        simp only [Matrix.mul_assoc]
        rw [hBM, Matrix.mul_one]
      clear_value B J κc ν
  7. Pi_ord is an orthogonal projector: it is idempotent (Pi_ord^2 = Pi_ord) and symmetric (Pi_ord^T = Pi_ord).

    Squaring Pi_ord gives (I - U B U^T)^2 = I - 2 U B U^T + (U B U^T)^2. Using (U B U^T) U = U, the square reduces to U B U^T, yielding Pi_ord^2 = Pi_ord. Symmetry follows from B^T = B and transposition of matrix products: (I - U B U^T)^T = I - U B^T U^T = Pi_ord.

    lines 136–145

    uses Matrix.transpose_sub, Matrix.transpose_one, Matrix.transpose_mul, Matrix.transpose_transpose, Matrix.mul_assoc

      have hP2 : comparison_pi_ord n * comparison_pi_ord n = comparison_pi_ord n := by
        rw [hPi, Matrix.sub_mul, Matrix.mul_sub, Matrix.mul_sub, Matrix.one_mul, Matrix.one_mul,
          Matrix.mul_one]
        have : U * B * U.transpose * (U * B * U.transpose) = U * B * U.transpose := by
          rw [← Matrix.mul_assoc, ← Matrix.mul_assoc, hUBU]
        rw [this]
        abel
      have hPt : (comparison_pi_ord n).transpose = comparison_pi_ord n := by
        rw [hPi, Matrix.transpose_sub, Matrix.transpose_one, Matrix.transpose_mul,
          Matrix.transpose_mul, Matrix.transpose_transpose, hBt, Matrix.mul_assoc]
  8. The triangle relation vectors kappa_abc are linearly independent.

    If a linear combination sum_t g_t kappa_t = U g vanishes, multiplying by B U^T gives g = B (U^T U) g = B U^T (U g) = 0. Therefore, the columns of U are linearly independent.

    lines 146–157

    uses Fintype.linearIndependent_iff, Matrix.one_mulVec, Matrix.mulVec_mulVec, Matrix.mulVec_zero

      have hLI : LinearIndependent ℝ (comparison_triangle_kappa (n := n)) := by
        rw [Fintype.linearIndependent_iff]
        intro g hg
        have hUg : U.mulVec g = 0 := by
          rw [← hg]
          funext i
          simp [Matrix.mulVec, dotProduct, U, comparison_triangle_matrix, mul_comm, Finset.sum_apply]
        have : g = (B * (U.transpose * U)).mulVec g := by rw [hBM, Matrix.one_mulVec]
        intro t
        rw [this, ← Matrix.mulVec_mulVec, ← Matrix.mulVec_mulVec, hUg, Matrix.mulVec_zero,
          Matrix.mulVec_zero]
        rfl
  9. The kernel of Pi_ord equals the range of U, and its dimension is C(n, 3).

    A vector c satisfies Pi_ord c = 0 if and only if c = U B U^T c, meaning c lies in the column space of U. Conversely, Pi_ord U = 0, so ker Pi_ord = range U. Since the columns of U are linearly independent, the dimension of ker Pi_ord is the number of triangles, nu = C(n, 3).

    lines 158–171

    uses LinearMap.mem_ker, LinearMap.mem_range, Matrix.mulVecLin_apply, finrank_span_eq_card

      have hkerP : LinearMap.ker (comparison_pi_ord n).mulVecLin = LinearMap.range U.mulVecLin := by
        ext c
        simp only [LinearMap.mem_ker, LinearMap.mem_range, Matrix.mulVecLin_apply]
        constructor
        · intro h
          refine ⟨(B * U.transpose).mulVec c, ?_⟩
          rw [hPi, Matrix.sub_mulVec, Matrix.one_mulVec, sub_eq_zero] at h
          rw [Matrix.mulVec_mulVec, ← Matrix.mul_assoc]
          exact h.symm
        · rintro ⟨y, rfl⟩
          rw [Matrix.mulVec_mulVec, hPi, Matrix.sub_mul, Matrix.one_mul, hUBU, sub_self,
            Matrix.zero_mulVec]
      have hfr : Module.finrank ℝ (LinearMap.ker (comparison_pi_ord n).mulVecLin) = n.choose 3 := by
        rw [hkerP, hrangeU, finrank_span_eq_card hLI, hν]
  10. All eight assertions of the theorem hold, concluding the proof.

    We combine: linear independence of F_1 features from comparison_phi1_linearIndependent; the evaluation kernel equality; linear independence of kappa; idempotence and symmetry of Pi_ord; ker Pi_ord = ker Phi_2; the dimension of range Pi_ord computed via rank-nullity (ambient dimension 1 + N + C(N, 2) minus nullity C(n, 3)); and the fixpoint property Pi_ord phi_2(x) = phi_2(x) from comparison_pi_ord_mulVec_phi2.

    lines 172–181

    uses comparison_phi1_linearIndependent, comparison_pi_ord_mulVec_phi2, LinearMap.finrank_range_add_finrank_ker, Module.finrank_fintype_fun_eq_card, Fintype.card_sum, Fintype.card_option, Fintype.card_finset_len

      refine ⟨comparison_phi1_linearIndependent n, hker, hLI, hP2, hPt, ?_, ?_,
        fun x => comparison_pi_ord_mulVec_phi2 n x⟩
      · rw [hkerP, hrangeU, hker]
      · have hrn := LinearMap.finrank_range_add_finrank_ker (comparison_pi_ord n).mulVecLin
        rw [hfr, Module.finrank_fintype_fun_eq_card] at hrn
        have hcard : Fintype.card (comparison_feature2 n) =
            1 + n.choose 2 + (n.choose 2).choose 2 := by
          rw [Fintype.card_sum, Fintype.card_option, Fintype.card_finset_len, hN]
          ring
        omega
cmpf_card_edge
The number of comparison edges (ordered pairs with a < b) on n vertices is C(n, 2).
cmpf_card_triangle
The number of comparison triangles (ordered triples with a < b < c) on n vertices is C(n, 3).
Fintype.card_finset_len
The number of subsets of size k in a finite type alpha is C(|alpha|, k).
Fintype.card_fin
The cardinality of Fin n is n.
Fintype.card_congr
A bijection between two finite types implies they have the same cardinality.
Equiv.ofBijective
A bijective function between types can be promoted to an equivalence.
Finset.card_pair
The set {a, b} has cardinality 2 whenever a ≠ b.
ne_of_lt
A strict inequality a < b implies a ≠ b.
lt_or_gt_of_ne
In a linear order, a ≠ b implies a < b or b < a.
Finset.pair_comm
The unordered pair {a, b} equals {b, a}.
Finset.card_eq_three
A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements.
comparison_triangle_gram
The Gram matrix U^T U of the triangle relation vectors equals 3 I + J, where J is the all-ones matrix.
Matrix.range_mulVecLin
The range of the linear map represented by a matrix is the linear span of its columns.
le_antisymm
If A ≤ B and B ≤ A in a partial order, then A = B.
comparison_eval_ker_le_span_kappa
The kernel of the evaluation matrix is bounded above by the linear span of the triangle relation vectors kappa.
LinearMap.mem_ker
A vector belongs to the kernel of a linear map if and only if the map evaluates to 0 on it.
Matrix.mulVecLin_apply
The linear map defined by a matrix acts by matrix-vector multiplication.
comparison_triangle_kappa_mem_eval_ker
Every triangle relation vector kappa belongs to the evaluation kernel (evaluates to 0 on all permutations).
Matrix.sub_mul
Matrix multiplication distributes over matrix subtraction on the left: (A - B) C = A C - B C.
Matrix.mul_add
Matrix multiplication distributes over matrix addition on the right: A (B + C) = A B + A C.
Matrix.smul_mul
Scalar multiplication commutes with matrix multiplication on the left: (c • A) B = c • (A B).
Matrix.one_mul
The identity matrix is a left identity for matrix multiplication: I A = A.
Matrix.mul_smul
Matrix multiplication commutes with scalar multiplication on the right: A (c • B) = c • (A B).
Matrix.mul_one
The identity matrix is a right identity for matrix multiplication: A I = A.
Matrix.transpose_sub
Transposition distributes over matrix subtraction: (A - B)^T = A^T - B^T.
Matrix.transpose_smul
Transposition commutes with scalar multiplication: (c • A)^T = c • A^T.
Matrix.transpose_one
The identity matrix is symmetric: I^T = I.
Finset.sum_comm
Finite double summations can interchange summation order.
Matrix.mul_assoc
Matrix multiplication is associative: (A B) C = A (B C).
Matrix.transpose_mul
The transpose of a matrix product reverses factors: (A B)^T = B^T A^T.
Matrix.transpose_transpose
The double transpose of a matrix is the matrix itself: (A^T)^T = A.
Fintype.linearIndependent_iff
A family of vectors indexed by a finite type is linearly independent if and only if vanishing of their linear combination implies all coefficients are zero.
Matrix.one_mulVec
Multiplying the identity matrix by a vector yields the vector itself: I v = v.
Matrix.mulVec_mulVec
Matrix-vector multiplication satisfies A (B v) = (A B) v.
Matrix.mulVec_zero
Multiplying any matrix by the zero vector yields zero: A 0 = 0.
LinearMap.mem_range
A vector belongs to the range of a linear map if and only if it is the image of some vector.
finrank_span_eq_card
The dimension of the span of a linearly independent family indexed by a finite type equals the cardinality of the index type.
comparison_phi1_linearIndependent
The linear comparison features (the constant 1 and the edge signs) are linearly independent as functions on permutations.
comparison_pi_ord_mulVec_phi2
The projector Pi_ord fixes every evaluation vector: Pi_ord phi_2(x) = phi_2(x).
LinearMap.finrank_range_add_finrank_ker
The rank-nullity theorem: dim range(f) + dim ker(f) = dim V for a linear map f on V.
Module.finrank_fintype_fun_eq_card
The dimension of the function space eta → R over R equals the cardinality of eta.
Fintype.card_sum
The cardinality of a sum type alpha ⊕ beta is |alpha| + |beta|.
Fintype.card_option
The cardinality of Option alpha is |alpha| + 1.

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

theorem cmpf_card_edge (n : ℕ) : Fintype.card (comparison_edge n) = n.choose 2 := by  classical  have hc := Fintype.card_finset_len (α := Fin n) 2  rw [Fintype.card_fin] at hc  rw [← hc]  refine Fintype.card_congr (Equiv.ofBijective    (fun e : comparison_edge n => (⟨{e.1.1, e.1.2}, Finset.card_pair (ne_of_lt e.2)⟩ :      {s : Finset (Fin n) // s.card = 2})) ⟨?_, ?_⟩)  · rintro ⟨⟨a, b⟩, hab⟩ ⟨⟨a', b'⟩, hab'⟩ h    have hab2 : a.val < b.val := hab    have hab2' : a'.val < b'.val := hab'    simp only [Subtype.mk.injEq] at h    have h1 : a ∈ ({a', b'} : Finset (Fin n)) := h ▸ Finset.mem_insert_self _ _    have h2 : b ∈ ({a', b'} : Finset (Fin n)) := h ▸ by simp    simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] at h1 h2    simp only [Subtype.mk.injEq, Prod.mk.injEq, Fin.ext_iff]    omega  · rintro ⟨s, hs⟩    obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.mp hs    rcases lt_or_gt_of_ne hxy with h | h    · exact ⟨⟨(x, y), h⟩, rfl⟩    · exact ⟨⟨(y, x), h⟩, by simp only [Subtype.mk.injEq]; exact Finset.pair_comm _ _⟩theorem cmpf_card_triangle (n : ℕ) : Fintype.card (comparison_triangle n) = n.choose 3 := by  classical  have hc := Fintype.card_finset_len (α := Fin n) 3  rw [Fintype.card_fin] at hc  rw [← hc]  refine Fintype.card_congr (Equiv.ofBijective    (fun t : comparison_triangle n => (⟨{t.1.1, t.1.2.1, t.1.2.2}, by      rw [Finset.card_eq_three]      exact ⟨_, _, _, ne_of_lt t.2.1, ne_of_lt (t.2.1.trans t.2.2), ne_of_lt t.2.2, rfl⟩⟩ :      {s : Finset (Fin n) // s.card = 3})) ⟨?_, ?_⟩)  · rintro ⟨⟨a, b, c⟩, hab, hbc⟩ ⟨⟨a', b', c'⟩, hab', hbc'⟩ h    simp only [Fin.lt_def] at hab hbc hab' hbc'    simp only [Subtype.mk.injEq] at h    have m : ∀ v, v ∈ ({a, b, c} : Finset (Fin n)) ↔ v ∈ ({a', b', c'} : Finset (Fin n)) :=      fun v => by rw [h]    have h1 := (m a).mp (by simp)    have h2 := (m b).mp (by simp)    have h3 := (m c).mp (by simp)    have h4 := (m a').mpr (by simp)    have h5 := (m b').mpr (by simp)    have h6 := (m c').mpr (by simp)    simp only [Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] at h1 h2 h3 h4 h5 h6    simp only [Subtype.mk.injEq, Prod.mk.injEq, Fin.ext_iff]    omega  · rintro ⟨s, hs⟩    obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hs    rcases lt_or_gt_of_ne hxy with h1 | h1 <;> rcases lt_or_gt_of_ne hxz with h2 | h2 <;>      rcases lt_or_gt_of_ne hyz with h3 | h3    · exact ⟨⟨(x, y, z), h1, h3⟩, by simp only [Subtype.mk.injEq]⟩    · exact ⟨⟨(x, z, y), h2, h3⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩    · exact absurd (h1.trans h3) (not_lt.mpr h2.le)    · exact ⟨⟨(z, x, y), h2, h1⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩    · exact ⟨⟨(y, x, z), h1, h2⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩    · exact absurd (h3.trans h1) (not_lt.mpr h2.le)    · exact ⟨⟨(y, z, x), h3, h2⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩    · exact ⟨⟨(z, y, x), h3, h1⟩, by simp only [Subtype.mk.injEq]; ext; simp; tauto⟩theorem quadratic_comparison_evaluation_kernel_and_projector (n : ℕ) (hn : 3 ≤ n) :    LinearIndependent ℝ        (fun i : comparison_feature1 n => fun x : Equiv.Perm (Fin n) => comparison_phi1 x i) ∧      LinearMap.ker (comparison_eval_matrix n).mulVecLin =        Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) ∧      LinearIndependent ℝ (comparison_triangle_kappa (n := n)) ∧      comparison_pi_ord n * comparison_pi_ord n = comparison_pi_ord n ∧      (comparison_pi_ord n).transpose = comparison_pi_ord n ∧      LinearMap.ker (comparison_pi_ord n).mulVecLin =        LinearMap.ker (comparison_eval_matrix n).mulVecLin ∧      Module.finrank ℝ (LinearMap.range (comparison_pi_ord n).mulVecLin) =        1 + n.choose 2 + (n.choose 2).choose 2 - n.choose 3 ∧      ∀ x : Equiv.Perm (Fin n),        Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x := by  classical  set U := comparison_triangle_matrix n with hU  have hG := comparison_triangle_gram n  rw [← hU] at hG  have hν := cmpf_card_triangle n  have hN := cmpf_card_edge n  have hUt : U.transpose = fun t => comparison_triangle_kappa t := by    funext t i; rfl  have hrangeU : LinearMap.range U.mulVecLin =      Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) := by    rw [Matrix.range_mulVecLin]    rfl  have hker : LinearMap.ker (comparison_eval_matrix n).mulVecLin =      Submodule.span ℝ (Set.range (comparison_triangle_kappa (n := n))) := by    refine le_antisymm (comparison_eval_ker_le_span_kappa n) (Submodule.span_le.mpr ?_)    rintro _ ⟨t, rfl⟩    exact LinearMap.mem_ker.mpr (by      rw [Matrix.mulVecLin_apply]; exact comparison_triangle_kappa_mem_eval_ker n t)  set ν : ℝ := (n.choose 3 : ℝ) with hνdef  set J : Matrix (comparison_triangle n) (comparison_triangle n) ℝ :=    Matrix.of fun _ _ => (1 : ℝ) with hJ  set κc : ℝ := 1 / (3 * (ν + 3)) with hκc  set B : Matrix (comparison_triangle n) (comparison_triangle n) ℝ :=    (1 / 3 : ℝ) • (1 : Matrix (comparison_triangle n) (comparison_triangle n) ℝ) - κc • J    with hB  have hJJ : J * J = ν • J := by    ext i j    simp [J, Matrix.mul_apply, hν, ν]  have hν0 : (0 : ℝ) ≤ ν := by positivity  have hscal : (1 / 3 : ℝ) - κc * 3 - κc * ν = 0 := by    rw [hκc]; field_simp; ring  have hBM : B * (U.transpose * U) = 1 := by    rw [hG, hB, Matrix.sub_mul, Matrix.mul_add, Matrix.mul_add, Matrix.smul_mul, Matrix.smul_mul,      Matrix.smul_mul, Matrix.smul_mul, Matrix.one_mul, Matrix.one_mul, Matrix.mul_smul,      Matrix.mul_one, hJJ]    simp only [smul_smul]    ext i j    simp only [Matrix.sub_apply, Matrix.add_apply, Matrix.smul_apply, smul_eq_mul, J,      Matrix.of_apply, Matrix.one_apply]    split_ifs <;> linarith [hscal]  have hBt : B.transpose = B := by    rw [hB, Matrix.transpose_sub, Matrix.transpose_smul, Matrix.transpose_smul,      Matrix.transpose_one]    congr 2  have hPi : comparison_pi_ord n = 1 - U * B * U.transpose := by    have hv : Matrix.vecMulVec (U.mulVec (fun _ => 1)) (U.mulVec (fun _ => 1)) =        U * J * U.transpose := by      ext i j      simp only [Matrix.vecMulVec_apply, Matrix.mulVec, dotProduct, mul_one, Matrix.mul_apply,        J, Matrix.of_apply, Matrix.transpose_apply, Finset.sum_mul]      rw [Finset.sum_comm]      simp only [Finset.mul_sum]    unfold comparison_pi_ord    dsimp only    rw [← hU, hv, hB, Matrix.mul_sub, Matrix.sub_mul, Matrix.mul_smul, Matrix.smul_mul,      Matrix.mul_smul, Matrix.smul_mul, Matrix.mul_one, hκc, hνdef]    abel  have hUBU : U * B * U.transpose * U = U := by    simp only [Matrix.mul_assoc]    rw [hBM, Matrix.mul_one]  clear_value B J κc ν  have hP2 : comparison_pi_ord n * comparison_pi_ord n = comparison_pi_ord n := by    rw [hPi, Matrix.sub_mul, Matrix.mul_sub, Matrix.mul_sub, Matrix.one_mul, Matrix.one_mul,      Matrix.mul_one]    have : U * B * U.transpose * (U * B * U.transpose) = U * B * U.transpose := by      rw [← Matrix.mul_assoc, ← Matrix.mul_assoc, hUBU]    rw [this]    abel  have hPt : (comparison_pi_ord n).transpose = comparison_pi_ord n := by    rw [hPi, Matrix.transpose_sub, Matrix.transpose_one, Matrix.transpose_mul,      Matrix.transpose_mul, Matrix.transpose_transpose, hBt, Matrix.mul_assoc]  have hLI : LinearIndependent ℝ (comparison_triangle_kappa (n := n)) := by    rw [Fintype.linearIndependent_iff]    intro g hg    have hUg : U.mulVec g = 0 := by      rw [← hg]      funext i      simp [Matrix.mulVec, dotProduct, U, comparison_triangle_matrix, mul_comm, Finset.sum_apply]    have : g = (B * (U.transpose * U)).mulVec g := by rw [hBM, Matrix.one_mulVec]    intro t    rw [this, ← Matrix.mulVec_mulVec, ← Matrix.mulVec_mulVec, hUg, Matrix.mulVec_zero,      Matrix.mulVec_zero]    rfl  have hkerP : LinearMap.ker (comparison_pi_ord n).mulVecLin = LinearMap.range U.mulVecLin := by    ext c    simp only [LinearMap.mem_ker, LinearMap.mem_range, Matrix.mulVecLin_apply]    constructor    · intro h      refine ⟨(B * U.transpose).mulVec c, ?_⟩      rw [hPi, Matrix.sub_mulVec, Matrix.one_mulVec, sub_eq_zero] at h      rw [Matrix.mulVec_mulVec, ← Matrix.mul_assoc]      exact h.symm    · rintro ⟨y, rfl⟩      rw [Matrix.mulVec_mulVec, hPi, Matrix.sub_mul, Matrix.one_mul, hUBU, sub_self,        Matrix.zero_mulVec]  have hfr : Module.finrank ℝ (LinearMap.ker (comparison_pi_ord n).mulVecLin) = n.choose 3 := by    rw [hkerP, hrangeU, finrank_span_eq_card hLI, hν]  refine ⟨comparison_phi1_linearIndependent n, hker, hLI, hP2, hPt, ?_, ?_,    fun x => comparison_pi_ord_mulVec_phi2 n x⟩  · rw [hkerP, hrangeU, hker]  · have hrn := LinearMap.finrank_range_add_finrank_ker (comparison_pi_ord n).mulVecLin    rw [hfr, Module.finrank_fintype_fun_eq_card] at hrn    have hcard : Fintype.card (comparison_feature2 n) =        1 + n.choose 2 + (n.choose 2).choose 2 := by      rw [Fintype.card_sum, Fintype.card_option, Fintype.card_finset_len, hN]      ring    omega
See it in the graphDiscuss this resultChallenge it