AFTD Auto-Formalizing Theoretical Domains

comparison_pi_ord_mulVec_phi2

theoremverified

Pi_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 also v_triangle^T phi_2(x) = 0.

Statement

theorem comparison_pi_ord_mulVec_phi2 (n : ℕ) (x : Equiv.Perm (Fin n)) :
    Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x
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_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_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.
  • 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_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_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_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_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_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 1

The proof, explained

The theorem proves that the projection matrix $\Pi_{\mathrm{ord}}$ fixes the quadratic evaluation vector $\phi_2(x)$ of any strict order (permutation) $x$. By definition, $\Pi_{\mathrm{ord}} = I - \frac{1}{3} U U^T + c v v^T$, where $U$ encodes the triangle relations and $v = U \mathbf{1}$. Because every valid order satisfies all triangle relations, $\phi_2(x)$ is orthogonal to every column of $U$, giving $U^T \phi_2(x) = 0$ and consequently $v \cdot \phi_2(x) = 0$. Distributing $\Pi_{\mathrm{ord}} \phi_2(x)$ across the linear combination eliminates both correction terms, leaving only the identity component $\phi_2(x)$.

  1. The feature vector $\phi_2(x)$ is orthogonal to the triangle constraint matrix from the left: $\phi_2(x) U = 0$.

    For any triangle $t$, the $t$-th column of $U$ is the triangle relation vector $\kappa_t$. By `comparison_triangle_kappa_mem_eval_ker`, every $\kappa_t$ lies in the kernel of the evaluation matrix, so evaluating it at the permutation $x$ yields zero. Applying function congruence (`congrFun`) at $x$ and expanding the definitions of vector-matrix multiplication and dot product shows that the $t$-th entry of the row-matrix product $\phi_2(x) U$ is zero.

    lines 3–8

    uses congrFun, comparison_triangle_kappa_mem_eval_ker, mul_comm

      classical
      have hU : Matrix.vecMul (comparison_phi2 x) (comparison_triangle_matrix n) = 0 := by
        funext t
        have := congrFun (comparison_triangle_kappa_mem_eval_ker n t) x
        simpa [Matrix.vecMul, Matrix.mulVec, dotProduct, comparison_triangle_matrix,
          comparison_eval_matrix, mul_comm] using this
  2. The dot product of the column-sum vector $v = U \mathbf{1}$ with $\phi_2(x)$ is zero: $v \cdot \phi_2(x) = 0$.

    By commutativity of the dot product (`dotProduct_comm`) and the adjoint identity $w \cdot (U \mathbf{1}) = (w U) \cdot \mathbf{1}$ (`Matrix.dotProduct_mulVec`), $v \cdot \phi_2(x)$ equals $(\phi_2(x) U) \cdot \mathbf{1}$. Because $\phi_2(x) U = 0$, this evaluates to $0 \cdot \mathbf{1} = 0$ (`zero_dotProduct`).

    lines 9–11

    uses dotProduct_comm, Matrix.dotProduct_mulVec, zero_dotProduct

      have hv : dotProduct (Matrix.mulVec (comparison_triangle_matrix n) (fun _ => 1))
          (comparison_phi2 x) = 0 := by
        rw [dotProduct_comm, Matrix.dotProduct_mulVec, hU, zero_dotProduct]
  3. The transposed triangle matrix annihilates $\phi_2(x)$: $U^T \phi_2(x) = 0$.

    Multiplying a vector by the transpose of a matrix from the left is the same as multiplying the row vector by the matrix from the right (`Matrix.mulVec_transpose`), so $U^T \phi_2(x) = \phi_2(x) U = 0$.

    lines 12–13

    uses Matrix.mulVec_transpose

      have hUt : Matrix.mulVec (comparison_triangle_matrix n).transpose (comparison_phi2 x) = 0 := by
        rw [Matrix.mulVec_transpose, hU]
  4. Applying $\Pi_{\mathrm{ord}}$ to $\phi_2(x)$ leaves $\phi_2(x)$ unchanged, because the correction terms vanish.

    Unfolding the definition of $\Pi_{\mathrm{ord}}$ reveals it as the identity matrix minus a multiple of $U U^T$ plus a multiple of the outer product $v v^T$. Distributing the matrix-vector multiplication over addition, subtraction, and scalar multiplication turns the $U U^T$ term into $U (U^T \phi_2(x))$ via `Matrix.mulVec_mulVec` and the $v v^T$ term into $(v \cdot \phi_2(x)) v$ via `Matrix.vecMulVec_mulVec`. Since $U^T \phi_2(x) = 0$ and $v \cdot \phi_2(x) = 0$, both correction terms vanish ($U 0 = 0$), leaving $I \phi_2(x) = \phi_2(x)$.

    lines 14–19

    uses Matrix.add_mulVec, Matrix.sub_mulVec, Matrix.one_mulVec, Matrix.smul_mulVec, Matrix.mulVec_mulVec, Matrix.mulVec_zero, Matrix.vecMulVec_mulVec

      unfold comparison_pi_ord
      simp only []
      rw [Matrix.add_mulVec, Matrix.sub_mulVec, Matrix.one_mulVec, Matrix.smul_mulVec,
        Matrix.smul_mulVec, ← Matrix.mulVec_mulVec, hUt, Matrix.mulVec_zero, Matrix.vecMulVec_mulVec,
        hv]
      simp
comparison_triangle_kappa_mem_eval_ker
Evaluating any triangle relation vector against any permutation yields zero: the triangle relations lie in the kernel of the evaluation matrix.
congrFun
Equal functions take equal values at any argument.
mul_comm
Multiplication in a commutative magma is commutative ($a * b = b * a$).
dotProduct_comm
The dot product of two vectors is commutative ($v \cdot w = w \cdot v$).
Matrix.dotProduct_mulVec
Vector-matrix multiplication is adjoint to matrix-vector multiplication with respect to the dot product: $v \cdot (A w) = (v A) \cdot w$.
zero_dotProduct
The dot product of the zero vector with any vector is zero ($0 \cdot v = 0$).
Matrix.mulVec_transpose
Multiplying by the transpose of a matrix on the left is equivalent to multiplying by the matrix on the right: $A^T x = x A$.
Matrix.add_mulVec
Matrix-vector multiplication distributes over matrix addition: $(A + B) x = A x + B x$.
Matrix.sub_mulVec
Matrix-vector multiplication distributes over matrix subtraction: $(A - B) x = A x - B x$.
Matrix.one_mulVec
The identity matrix acts trivially on vectors: $I v = v$.
Matrix.smul_mulVec
Scalar multiplication factors out of matrix-vector multiplication: $(c \cdot M) v = c \cdot (M v)$.
Matrix.mulVec_mulVec
Matrix-vector multiplication associates with matrix multiplication: $M (N v) = (M N) v$.
Matrix.mulVec_zero
Multiplying any matrix by the zero vector gives the zero vector: $A 0 = 0$.
Matrix.vecMulVec_mulVec
Multiplying an outer product matrix $u v^T$ by a vector $w$ yields $(v \cdot w) u$.

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_pi_ord_mulVec_phi2 (n : ℕ) (x : Equiv.Perm (Fin n)) :    Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x := by  classical  have hU : Matrix.vecMul (comparison_phi2 x) (comparison_triangle_matrix n) = 0 := by    funext t    have := congrFun (comparison_triangle_kappa_mem_eval_ker n t) x    simpa [Matrix.vecMul, Matrix.mulVec, dotProduct, comparison_triangle_matrix,      comparison_eval_matrix, mul_comm] using this  have hv : dotProduct (Matrix.mulVec (comparison_triangle_matrix n) (fun _ => 1))      (comparison_phi2 x) = 0 := by    rw [dotProduct_comm, Matrix.dotProduct_mulVec, hU, zero_dotProduct]  have hUt : Matrix.mulVec (comparison_triangle_matrix n).transpose (comparison_phi2 x) = 0 := by    rw [Matrix.mulVec_transpose, hU]  unfold comparison_pi_ord  simp only []  rw [Matrix.add_mulVec, Matrix.sub_mulVec, Matrix.one_mulVec, Matrix.smul_mulVec,    Matrix.smul_mulVec, ← Matrix.mulVec_mulVec, hUt, Matrix.mulVec_zero, Matrix.vecMulVec_mulVec,    hv]  simp
See it in the graphDiscuss this resultChallenge it