quadratic_comparison_evaluation_kernel_and_projector
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
LinearOrderis aTotalPreorder. - 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 thanLinearOrder— 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.
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.
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_commtheorem 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 _ _⟩
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.
uses
Fintype.card_finset_len,Fintype.card_fin,Fintype.card_congr,Equiv.ofBijective,Finset.card_eq_three,ne_of_lt,lt_or_gt_of_netheorem 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⟩
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.
uses
comparison_triangle_gram,cmpf_card_triangle,cmpf_card_edge,Matrix.range_mulVecLintheorem 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
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.
uses
le_antisymm,comparison_eval_ker_le_span_kappa,LinearMap.mem_ker,Matrix.mulVecLin_apply,comparison_triangle_kappa_mem_eval_kerhave 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)
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.
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_oneset ν : ℝ := (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
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.
uses
Finset.sum_comm,Matrix.mul_assoc,Matrix.mul_onehave 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 ν
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.
uses
Matrix.transpose_sub,Matrix.transpose_one,Matrix.transpose_mul,Matrix.transpose_transpose,Matrix.mul_assochave 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]
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.
uses
Fintype.linearIndependent_iff,Matrix.one_mulVec,Matrix.mulVec_mulVec,Matrix.mulVec_zerohave 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
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).
uses
LinearMap.mem_ker,LinearMap.mem_range,Matrix.mulVecLin_apply,finrank_span_eq_cardhave 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ν]
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.
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_lenrefine ⟨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.
- The combinatorics of ordering pairs and triples in the helper lemmas relies on the omega tactic for linear integer inequalities.
- Matrix algebraic identities verifying that B is the inverse of the Gram matrix and that Pi_ord is an orthogonal projector are verified by ring and linarith automation.
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.
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