AFTD Auto-Formalizing Theoretical Domains

comparison_triangle_kappa_mem_eval_ker

theoremverified

Each 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.

Statement

theorem comparison_triangle_kappa_mem_eval_ker (n : ℕ) (t : comparison_triangle n) :
    Matrix.mulVec (comparison_eval_matrix n) (comparison_triangle_kappa t) = 0
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 9
  • 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_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) +…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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_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_feature1The type indexing the orthonormal coordinate basis of the formal linear feature space F_1 = span{1, d_e}: Option (comparison_edge n),…
  • comparison_signThe real-valued comparison sign d_e(x) of a strict order. A strict order on the labels Fin n is given by a permutation x : Equiv.Perm (Fin…
  • 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.
Used by 3

The proof, explained

To show that the triangle relation vector $\kappa$ evaluates to zero on every strict order (permutation) $x \in S_n$, we evaluate the matrix-vector product componentwise at $x$. Unfolding definitions reduces the evaluation to the polynomial identity $d_{ab} d_{ac} - d_{ab} d_{bc} + d_{ac} d_{bc} - 1 = 0$, where each $d_{uv} \in \{-1, 1\}$ indicates the relative order of $x(u)$ and $x(v)$. A case analysis on the relative ordering of the three distinct values $x(a), x(b), x(c)$ verifies the identity on all six valid total orderings, while the two cyclic non-transitive cases are ruled out by transitivity of strict inequality.

  1. It suffices to show that the matrix-vector product evaluated at any permutation $x$ is zero.

    We unpack the triangle $t$ into its three vertices $a < b < c$ in $\{0, \dots, n-1\}$. By function extensionality (`funext`), showing that the resulting vector is zero is equivalent to showing that it evaluates to zero on every permutation $x \in S_n$.

    lines 3–5

      classical
      obtain ⟨⟨a, b, c⟩, hab, hbc⟩ := t
      funext x
  2. Evaluating at $x$ reduces to $\prod_{e \in \{ab, ac\}} d_e - \prod_{e \in \{ab, bc\}} d_e + \prod_{e \in \{ac, bc\}} d_e - 1 = 0$, where $d_e = \operatorname{comparison\_sign}(x, e)$.

    We expand the matrix-vector multiplication as a dot product and substitute the definitions of the evaluation matrix and the relation vector $\kappa$. The vector $\kappa$ is nonzero only on four basis features: the pairs $\{ab, ac\}$, $\{ab, bc\}$, $\{ac, bc\}$, and the empty feature $\emptyset$ (with coefficients $1, -1, 1, -1$). Distributing the summation over additions and subtractions and simplifying with `Finset.sum_ite_eq'` isolates exactly these four terms.

    lines 6–9

    uses Matrix.mulVec, dotProduct, comparison_eval_matrix, comparison_triangle_kappa, Matrix.of_apply, Pi.zero_apply, 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, comparison_phi2, comparison_phi1

      simp only [Matrix.mulVec, dotProduct, comparison_eval_matrix, comparison_triangle_kappa,
        Matrix.of_apply, Pi.zero_apply, 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, comparison_phi2, comparison_phi1]
  3. The pairwise products expand to $d_{ab} d_{ac} - d_{ab} d_{bc} + d_{ac} d_{bc} - 1 = 0$, where each $d_{uv}$ is $1$ if $x(u) < x(v)$ and $-1$ otherwise.

    Each product over a two-element set of edges is expanded into a binary product via `Finset.prod_pair`, using $a < b < c$ to verify that the edges in each pair are distinct. We then unfold the definition of the comparison signs $d_{uv} = \operatorname{comparison\_sign}(x, (u, v))$, which evaluates to $1$ when $x(u) < x(v)$ and $-1$ otherwise.

    lines 10–13

    uses Finset.prod_pair, Subtype.ext_iff, Prod.ext_iff, ne_of_lt, comparison_sign

      rw [Finset.prod_pair (by simp [Subtype.ext_iff, Prod.ext_iff, (ne_of_lt hbc)]),
        Finset.prod_pair (by simp [Subtype.ext_iff, Prod.ext_iff, (ne_of_lt hab)]),
        Finset.prod_pair (by simp [Subtype.ext_iff, Prod.ext_iff, (ne_of_lt hab)])]
      simp only [comparison_sign]
  4. The values $x(a), x(b), x(c)$ are distinct natural numbers, and all comparisons are cast to standard inequality on $\mathbb{N}$.

    Since $a < b < c$, the indices $a, b, c$ are strictly pairwise distinct. Because $x$ is a permutation, it is injective, so the values $x(a), x(b), x(c)$ are also pairwise distinct ($h_1, h_2, h_3$). We convert these distinctness hypotheses and the strict inequalities on `Fin n` into relations on the underlying natural numbers using `Fin.ext_iff` and `Fin.lt_def`.

    lines 14–18

    uses ne_of_lt, Ne, Fin.ext_iff, Fin.lt_def

      have h1 : x a ≠ x b := fun h => (ne_of_lt hab) (x.injective h)
      have h2 : x a ≠ x c := fun h => (ne_of_lt (hab.trans hbc)) (x.injective h)
      have h3 : x b ≠ x c := fun h => (ne_of_lt hbc) (x.injective h)
      rw [Ne, Fin.ext_iff] at h1 h2 h3
      simp only [Fin.lt_def]
  5. The relation holds for all permutations.

    We case-split on all eight possible combinations of the three strict inequalities $x(a) < x(b)$, $x(a) < x(c)$, and $x(b) < x(c)$ via `split_ifs`. For the six combinations corresponding to valid linear orderings of three points, `norm_num` computes that $d_{ab} d_{ac} - d_{ab} d_{bc} + d_{ac} d_{bc} - 1 = 0$. For the two cyclic combinations that violate transitivity, `norm_num` leaves `False`, and `omega` derives a contradiction via linear integer arithmetic.

    line 19

      split_ifs <;> norm_num <;> omega
Matrix.mulVec
The matrix-vector product $(M v)_i = \sum_j M_{i,j} v_j$
dotProduct
The dot product of two vectors indexed by a finite type, $\sum_j u_j v_j$
comparison_eval_matrix
The matrix evaluating degree-2 comparison features on permutations, defined by $M_{x, i} = \Phi_2(x, i)$
comparison_triangle_kappa
The relation vector for a triangle $(a, b, c)$, taking values $+1$ on $\{ab, ac\}$ and $\{ac, bc\}$, $-1$ on $\{ab, bc\}$ and $\emptyset$, and $0$ elsewhere
Matrix.of_apply
Evaluating a matrix defined by a function $f$ at row $i$ and column $j$ gives $f(i, j)$
Pi.zero_apply
Evaluating the zero function at any point gives zero: $0(i) = 0$
mul_sub
Left distributivity of multiplication over subtraction: $a(b - c) = ab - ac$
mul_add
Left distributivity of multiplication over addition: $a(b + c) = ab + ac$
Finset.sum_sub_distrib
Distributivity of finite summation over subtraction: $\sum (f - g) = \sum f - \sum g$
Finset.sum_add_distrib
Distributivity of finite summation over addition: $\sum (f + g) = \sum f + \sum g$
mul_ite
Multiplication distributes over an if-then-else condition
mul_one
Multiplying by one on the right: $a \cdot 1 = a$
mul_zero
Multiplying by zero on the right: $a \cdot 0 = 0$
Finset.sum_ite_eq'
A finite sum of terms with an equality indicator collapses to the single matching term if present, and 0 otherwise
Finset.mem_univ
Every element of a finite type is a member of its universal finset
if_true
An if-then-else whose condition is True simplifies to the then-branch
comparison_phi2
The degree-2 feature evaluation function, which evaluates to $\Phi_1(x, i)$ on degree-1 features and $\prod_{e \in s} \operatorname{comparison\_sign}(x, e)$ on pairs of edges
comparison_phi1
The degree-1 feature evaluation function, which equals $1$ on the empty feature and the edge sign on a single edge
Finset.prod_pair
The product of a function over an unordered pair of distinct elements $\{u, v\}$ is $f(u) f(v)$
Subtype.ext_iff
Two subtype elements are equal if and only if their underlying values are equal
Prod.ext_iff
Two ordered pairs are equal if and only if their first and second components are respectively equal
ne_of_lt
In a strict preorder, if $u < v$ then $u \ne v$
comparison_sign
The sign of an edge $(u, v)$ under permutation $x$, equal to $1$ if $x(u) < x(v)$ and $-1$ otherwise
Ne
Inequality $u \ne v$ is defined as the negation of equality, $\neg (u = v)$
Fin.ext_iff
Two elements of `Fin n` are equal if and only if their underlying natural numbers are equal
Fin.lt_def
Strict inequality in `Fin n` is defined by strict inequality of the underlying natural numbers

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 comparison_triangle_kappa_mem_eval_ker (n : ℕ) (t : comparison_triangle n) :    Matrix.mulVec (comparison_eval_matrix n) (comparison_triangle_kappa t) = 0 := by  classical  obtain ⟨⟨a, b, c⟩, hab, hbc⟩ := t  funext x  simp only [Matrix.mulVec, dotProduct, comparison_eval_matrix, comparison_triangle_kappa,    Matrix.of_apply, Pi.zero_apply, 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, comparison_phi2, comparison_phi1]  rw [Finset.prod_pair (by simp [Subtype.ext_iff, Prod.ext_iff, (ne_of_lt hbc)]),    Finset.prod_pair (by simp [Subtype.ext_iff, Prod.ext_iff, (ne_of_lt hab)]),    Finset.prod_pair (by simp [Subtype.ext_iff, Prod.ext_iff, (ne_of_lt hab)])]  simp only [comparison_sign]  have h1 : x a ≠ x b := fun h => (ne_of_lt hab) (x.injective h)  have h2 : x a ≠ x c := fun h => (ne_of_lt (hab.trans hbc)) (x.injective h)  have h3 : x b ≠ x c := fun h => (ne_of_lt hbc) (x.injective h)  rw [Ne, Fin.ext_iff] at h1 h2 h3  simp only [Fin.lt_def]  split_ifs <;> norm_num <;> omega
See it in the graphDiscuss this resultChallenge it