comparison_triangle_kappa_mem_eval_ker
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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
- 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…
- 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…
- 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 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.
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$.
classical obtain ⟨⟨a, b, c⟩, hab, hbc⟩ := t funext x
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.
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_phi1simp 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]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.
uses
Finset.prod_pair,Subtype.ext_iff,Prod.ext_iff,ne_of_lt,comparison_signrw [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]
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`.
uses
ne_of_lt,Ne,Fin.ext_iff,Fin.lt_defhave 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]
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.
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
- The final tactic line `split_ifs <;> norm_num <;> omega` explores all $2^3 = 8$ sign configurations for the three pairwise comparisons between $x(a)$, $x(b)$, and $x(c)$. The 6 configurations compatible with a total ordering evaluate to 0 by arithmetic (`norm_num`), while the 2 non-transitive cyclic configurations are refuted by `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.
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