comparison_triangle_gram
The 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 distinct ones share only the constant coordinate, where both are -1.
Statement
theorem comparison_triangle_gram (n : ℕ) : (comparison_triangle_matrix n).transpose * comparison_triangle_matrix n = (3 : ℝ) • (1 : Matrix (comparison_triangle n) (comparison_triangle n) ℝ) + Matrix.of (fun _ _ => (1 : ℝ))
- Source
- Step of arXiv:2610.34762 (Quantum ordinal selection with two comparisons), Section 3.1, Lemma 1 (quadratic_comparison_evaluation_kernel_and_projector)
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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_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_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_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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- quadratic_comparison_evaluation_kernel_and_projectorLet 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…
The proof, explained
To show that the Gram matrix of the triangle feature vectors satisfies U^T U = 3 I + 1 1^T, we compute the inner product ⟨κ_{t1}, κ_{t2}⟩ entrywise. Each triangle vector κ_t has support on three edge-pair features (with signs +1, -1, +1) and on the constant feature (with sign -1). For diagonal entries (t1 = t2), the squared norm is 1^2 + (-1)^2 + 1^2 + (-1)^2 = 4, matching 3(1) + 1. For off-diagonal entries (t1 ≠ t2), two distinct triangles cannot share two edges and therefore share no edge-pair features; only the constant feature contributes (-1)(-1) = 1, matching 3(0) + 1.
Two unordered pairs as 2-element finite sets are equal if and only if their elements match in either order.
We cast the equality of finite sets to standard set equality using Finset.coe_inj, then rewrite with Set.pair_eq_pair_iff.
uses
Finset.coe_inj,Set.pair_eq_pair_iffrw [← Finset.coe_inj] simp [Set.pair_eq_pair_iff]
The squared norm ∑ j, κ_t(j)^2 expands into indicator conditions on the sorted vertices a < b < c.
We decompose the triangle t into its vertices a, b, c with a < b and b < c, and unfold comparison_triangle_kappa. Expanding the product and distributing the sum, Finset.sum_ite_eq' collapses the indicator sums, eliminating cross terms between the constant feature (Sum.inl) and the edge-pair features (Sum.inr). Edge-pair equality is simplified using comparison_triangle_gram_pair_eq_pair_iff_finset.
uses
Finset.sum_ite_eq',comparison_triangle_gram_pair_eq_pair_iff_finsetclassical obtain ⟨⟨a, b, c⟩, hab, hbc⟩ := t dsimp at hab hbc dsimp [comparison_triangle_kappa] simp only [mul_sub, mul_add, Finset.sum_sub_distrib, Finset.sum_add_distrib, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true, Sum.inr.injEq, Sum.inl_ne_inr, Sum.inr_ne_inl, if_false, sub_zero, Subtype.ext_iff, comparison_triangle_gram_pair_eq_pair_iff_finset, Prod.ext_iff]
The squared norm of each triangle vector κ_t is 4.
From a < b and b < c, we deduce a ≠ b and b ≠ c using ne_of_lt. Since all three vertices are distinct, the three edge pairs defining the features are distinct from one another, so all cross-term indicators between different edge pairs evaluate to 0. This leaves 1 + 1 + 1 + 1 = 4, computed by norm_num.
uses
ne_of_lthave hab' : a ≠ b := ne_of_lt hab have hbc' : b ≠ c := ne_of_lt hbc simp [hab', hab'.symm, hbc', hbc'.symm] norm_num
The inner product of two distinct triangle vectors expands to 1 plus 9 potential edge-pair overlap indicators.
We unpack t1 = (a1, b1, c1) and t2 = (a2, b2, c2) and deduce (a1, b1, c1) ≠ (a2, b2, c2) via Subtype.ext. Unfolding the vectors and expanding the sum of products via Finset.sum_ite_eq', the constant feature product (-1)(-1) = 1 is isolated, leaving 9 indicator terms for the potential equalities between an edge-pair of t1 and an edge-pair of t2.
uses
Subtype.ext,Finset.sum_ite_eq',comparison_triangle_gram_pair_eq_pair_iff_finsetclassical obtain ⟨⟨a1, b1, c1⟩, h1ab, h1bc⟩ := t1 obtain ⟨⟨a2, b2, c2⟩, h2ab, h2bc⟩ := t2 dsimp at h1ab h1bc h2ab h2bc have hne' : (a1, b1, c1) ≠ (a2, b2, c2) := fun h => hne (Subtype.ext h) dsimp [comparison_triangle_kappa] simp only [mul_sub, mul_add, Finset.sum_sub_distrib, Finset.sum_add_distrib, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true, Sum.inr.injEq, Sum.inl_ne_inr, Sum.inr_ne_inl, if_false, sub_zero, Subtype.ext_iff, comparison_triangle_gram_pair_eq_pair_iff_finset, Prod.ext_iff]
No edge-pair feature of t1 can equal any edge-pair feature of t2 when t1 ≠ t2. automation
We prove the 9 negations in h_cases. Assuming any edge-pair feature matches, substituting variables either forces all three vertices to coincide (contradicting t1 ≠ t2), contradicts strict ordering via lt_asymm, or violates linear inequalities on the indices (closed by omega).
uses
lt_asymmhave h_cases : ¬ ((a2 = a1 ∧ b2 = b1) ∧ a2 = a1 ∧ c2 = c1 ∨ (a2 = a1 ∧ b2 = c1) ∧ a2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = b1) ∧ a2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ a2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = c1) ∧ a2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ a2 = a1 ∧ c2 = c1) ∧ ¬ ((a2 = a1 ∧ b2 = b1) ∧ b2 = a1 ∧ c2 = c1 ∨ (a2 = a1 ∧ b2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = b1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = c1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ b2 = a1 ∧ c2 = c1) ∧ ¬ ((a2 = a1 ∧ c2 = b1) ∧ b2 = a1 ∧ c2 = c1 ∨ (a2 = a1 ∧ c2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ c2 = b1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ c2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ c2 = c1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ c2 = c1) ∧ b2 = a1 ∧ c2 = c1) := by refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> { intro h rcases h with (⟨⟨h1, h2⟩, ⟨h3, h4⟩⟩ | ⟨⟨h1, h2⟩, ⟨h3, h4⟩⟩) <;> subst_vars <;> first | exact hne' rfl | exact (lt_asymm h1bc h2bc).elim | exact (lt_asymm h1ab h2ab).elim | omega }
The inner product of distinct triangle vectors κ_{t1} and κ_{t2} is 1.
Substituting the 9 negated edge-pair overlap conditions from h_cases zeroes out all edge-pair cross terms, leaving only the constant feature contribution 1.
rcases h_cases with ⟨h1, h2, h3, h4, h5, h6, h7, h8, h9⟩ simp [h1, h2, h3, h4, h5, h6, h7, h8, h9]
The matrix equation (U^T U) = 3 I + 1 1^T reduces entrywise to checking that ∑ j, κ_{t1}(j) * κ_{t2}(j) = 3 * (if t1 = t2 then 1 else 0) + 1.
By extensionality (ext t1 t2), we compare entries at (t1, t2). We expand matrix multiplication (Matrix.mul_apply), transpose (Matrix.transpose_apply), the triangle matrix definition (Matrix.of_apply), addition (Matrix.add_apply), scalar multiplication (Matrix.smul_apply), and the identity matrix (Matrix.one_apply).
uses
Matrix.mul_apply,Matrix.transpose_apply,Matrix.of_apply,Matrix.add_apply,Matrix.smul_apply,Matrix.one_applyext t1 t2 simp only [Matrix.mul_apply, Matrix.transpose_apply, comparison_triangle_matrix, Matrix.of_apply, Matrix.add_apply, Matrix.smul_apply, Matrix.one_apply]
The diagonal entries (t1 = t2) of both sides match with value 4.
When t1 = t2, the right-hand side evaluates via if_pos to 3 * 1 + 1 = 4. The left-hand side is the squared norm of κ_{t1}, which equals 4 by comparison_triangle_gram_same.
uses
if_pos,comparison_triangle_gram_sameby_cases h : t1 = t2 · subst h rw [if_pos rfl, comparison_triangle_gram_same] norm_num
The off-diagonal entries (t1 ≠ t2) of both sides match with value 1.
When t1 ≠ t2, the right-hand side evaluates via if_neg to 3 * 0 + 1 = 1. The left-hand side is the inner product of distinct triangle vectors, which equals 1 by comparison_triangle_gram_diff.
uses
if_neg,comparison_triangle_gram_diff· rw [if_neg h, comparison_triangle_gram_diff n t1 t2 h] norm_num
Finset.coe_inj- Two finite sets are equal if and only if their coerced sets of elements are equal.
Set.pair_eq_pair_iff- Two unordered pairs {x, y} and {z, w} are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Finset.sum_ite_eq'- Summing an indicator that is nonzero only when the index equals a collapses to the value at a (if a is in the set) or 0.
comparison_triangle_gram_pair_eq_pair_iff_finset- Two 2-element finite sets {x, y} and {z, w} are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
ne_of_lt- A strictly smaller element is not equal to the larger element.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
lt_asymm- Strict inequality is asymmetric: if a < b, then b < a is false.
Matrix.mul_apply- The (i, k) entry of the matrix product M * N is the sum ∑ j, M i j * N j k.
Matrix.transpose_apply- The (i, j) entry of the transpose matrix M^T is M j i.
Matrix.of_apply- The (i, j) entry of a matrix defined by a function f is f i j.
Matrix.add_apply- The (i, j) entry of the sum of two matrices is the sum of their entries.
Matrix.smul_apply- The (i, j) entry of a scalar multiple r • A is r times the (i, j) entry of A.
Matrix.one_apply- The (i, j) entry of the identity matrix is 1 if i = j and 0 otherwise.
if_pos- An if-then-else evaluates to the first branch when the condition is true.
if_neg- An if-then-else evaluates to the second branch when the condition is false.
comparison_triangle_gram_same- The squared norm of the triangle feature vector κ_t is 4 for any triangle t.
comparison_triangle_gram_diff- The inner product of the feature vectors κ_{t1} and κ_{t2} for distinct triangles t1 ≠ t2 is 1.
- On paper, the fact that two distinct triangles cannot share an edge-pair feature is immediate because any two edges of a triangle determine all three of its vertices. In the formal proof (lines 33–48), this is established by explicitly enumerating all 9 possible edge-pair coincidences and eliminating each branch via variable substitution, strict order asymmetry (lt_asymm), and linear arithmetic (omega).
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.
lemma comparison_triangle_gram_pair_eq_pair_iff_finset {α : Type*} [DecidableEq α] {x y z w : α} : ({x, y} : Finset α) = {z, w} ↔ x = z ∧ y = w ∨ x = w ∧ y = z := by rw [← Finset.coe_inj] simp [Set.pair_eq_pair_iff]lemma comparison_triangle_gram_same (n : ℕ) (t : comparison_triangle n) : ∑ j : comparison_feature2 n, comparison_triangle_kappa t j * comparison_triangle_kappa t j = 4 := by classical obtain ⟨⟨a, b, c⟩, hab, hbc⟩ := t dsimp at hab hbc dsimp [comparison_triangle_kappa] simp only [mul_sub, mul_add, Finset.sum_sub_distrib, Finset.sum_add_distrib, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true, Sum.inr.injEq, Sum.inl_ne_inr, Sum.inr_ne_inl, if_false, sub_zero, Subtype.ext_iff, comparison_triangle_gram_pair_eq_pair_iff_finset, Prod.ext_iff] have hab' : a ≠ b := ne_of_lt hab have hbc' : b ≠ c := ne_of_lt hbc simp [hab', hab'.symm, hbc', hbc'.symm] norm_numlemma comparison_triangle_gram_diff (n : ℕ) (t1 t2 : comparison_triangle n) (hne : t1 ≠ t2) : ∑ j : comparison_feature2 n, comparison_triangle_kappa t1 j * comparison_triangle_kappa t2 j = 1 := by classical obtain ⟨⟨a1, b1, c1⟩, h1ab, h1bc⟩ := t1 obtain ⟨⟨a2, b2, c2⟩, h2ab, h2bc⟩ := t2 dsimp at h1ab h1bc h2ab h2bc have hne' : (a1, b1, c1) ≠ (a2, b2, c2) := fun h => hne (Subtype.ext h) dsimp [comparison_triangle_kappa] simp only [mul_sub, mul_add, Finset.sum_sub_distrib, Finset.sum_add_distrib, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true, Sum.inr.injEq, Sum.inl_ne_inr, Sum.inr_ne_inl, if_false, sub_zero, Subtype.ext_iff, comparison_triangle_gram_pair_eq_pair_iff_finset, Prod.ext_iff] have h_cases : ¬ ((a2 = a1 ∧ b2 = b1) ∧ a2 = a1 ∧ c2 = c1 ∨ (a2 = a1 ∧ b2 = c1) ∧ a2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = b1) ∧ a2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ a2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = c1) ∧ a2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ a2 = a1 ∧ c2 = c1) ∧ ¬ ((a2 = a1 ∧ b2 = b1) ∧ b2 = a1 ∧ c2 = c1 ∨ (a2 = a1 ∧ b2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = b1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ b2 = c1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ b2 = c1) ∧ b2 = a1 ∧ c2 = c1) ∧ ¬ ((a2 = a1 ∧ c2 = b1) ∧ b2 = a1 ∧ c2 = c1 ∨ (a2 = a1 ∧ c2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ c2 = b1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ c2 = c1) ∧ b2 = a1 ∧ c2 = b1) ∧ ¬ ((a2 = a1 ∧ c2 = c1) ∧ b2 = b1 ∧ c2 = c1 ∨ (a2 = b1 ∧ c2 = c1) ∧ b2 = a1 ∧ c2 = c1) := by refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> { intro h rcases h with (⟨⟨h1, h2⟩, ⟨h3, h4⟩⟩ | ⟨⟨h1, h2⟩, ⟨h3, h4⟩⟩) <;> subst_vars <;> first | exact hne' rfl | exact (lt_asymm h1bc h2bc).elim | exact (lt_asymm h1ab h2ab).elim | omega } rcases h_cases with ⟨h1, h2, h3, h4, h5, h6, h7, h8, h9⟩ simp [h1, h2, h3, h4, h5, h6, h7, h8, h9]theorem comparison_triangle_gram (n : ℕ) : (comparison_triangle_matrix n).transpose * comparison_triangle_matrix n = (3 : ℝ) • (1 : Matrix (comparison_triangle n) (comparison_triangle n) ℝ) + Matrix.of (fun _ _ => (1 : ℝ)) := by ext t1 t2 simp only [Matrix.mul_apply, Matrix.transpose_apply, comparison_triangle_matrix, Matrix.of_apply, Matrix.add_apply, Matrix.smul_apply, Matrix.one_apply] by_cases h : t1 = t2 · subst h rw [if_pos rfl, comparison_triangle_gram_same] norm_num · rw [if_neg h, comparison_triangle_gram_diff n t1 t2 h] norm_num