AFTD Auto-Formalizing Theoretical Domains

comparison_triangle_gram

theoremverified

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 LinearOrder is a TotalPreorder.
  • 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 than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  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.

    lines 3–4

    uses Finset.coe_inj, Set.pair_eq_pair_iff

      rw [← Finset.coe_inj]
      simp [Set.pair_eq_pair_iff]
  2. 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.

    lines 8–15

    uses Finset.sum_ite_eq', comparison_triangle_gram_pair_eq_pair_iff_finset

      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]
  3. 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.

    lines 16–19

    uses ne_of_lt

      have hab' : a ≠ b := ne_of_lt hab
      have hbc' : b ≠ c := ne_of_lt hbc
      simp [hab', hab'.symm, hbc', hbc'.symm]
      norm_num
  4. 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.

    lines 23–32

    uses Subtype.ext, Finset.sum_ite_eq', comparison_triangle_gram_pair_eq_pair_iff_finset

      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]
  5. 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).

    lines 33–48

    uses lt_asymm

      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 }
  6. 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.

    lines 49–50

      rcases h_cases with ⟨h1, h2, h3, h4, h5, h6, h7, h8, h9⟩
      simp [h1, h2, h3, h4, h5, h6, h7, h8, h9]
  7. 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).

    lines 56–58

    uses Matrix.mul_apply, Matrix.transpose_apply, Matrix.of_apply, Matrix.add_apply, Matrix.smul_apply, Matrix.one_apply

      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]
  8. 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.

    lines 59–62

    uses if_pos, comparison_triangle_gram_same

      by_cases h : t1 = t2
      · subst h
        rw [if_pos rfl, comparison_triangle_gram_same]
        norm_num
  9. 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.

    lines 63–64

    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.

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

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
See it in the graphDiscuss this resultChallenge it