AFTD Auto-Formalizing Theoretical Domains

three_hadamard_clean_return_numerator

theoremverified

The (1,0) entry of the unnormalized three-Hadamard, two-diagonal-phase chain is 1-u+v+u*v.

Statement

theorem three_hadamard_clean_return_numerator (u v : ℂ) :
    ((!![1, 1; 1, -1] : Matrix (Fin 2) (Fin 2) ℂ) *
      Matrix.diagonal ![1,u] * !![1,1;1,-1] *
      Matrix.diagonal ![1,v] * !![1,1;1,-1] : Matrix (Fin 2) (Fin 2) ℂ) 1 0 =
        1 - u + v + u*v
Source
Supporting algebra for OP-3, arXiv:2610.01024, Section E.1; developed in deep session IN-184. These helpers do not establish a lower bound for arbitrary circuit gate lists.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem computes the (1, 0) entry of the product of five 2 × 2 matrices: three unnormalized Hadamard matrices alternating with two diagonal phase matrices with diagonals (1, u) and (1, v). The proof proceeds by direct expansion, reducing matrix multiplication to two-element sums and evaluating them explicitly. The resulting polynomial expression is then simplified using commutative ring arithmetic.

  1. The (1, 0) entry of the five-matrix product expands to 1 + (-u) + (v + u * v).

    Expanding the definitions of matrix multiplication (Matrix.mul_apply), vector-matrix multiplication (Matrix.vecMul), and dot products (dotProduct), while unrolling all index sums over Fin 2 into their two terms at indices 0 and 1 (Fin.sum_univ_two), reduces the entry at row 1, column 0 of the 2 × 2 matrix product to an explicit polynomial expression in u and v.

    line 6

    uses Matrix.mul_apply, Matrix.vecMul, dotProduct, Fin.sum_univ_two

      simp [Matrix.mul_apply, Matrix.vecMul, dotProduct, Fin.sum_univ_two]
  2. The identity holds in ℂ. automation

    Standard polynomial normalization in the commutative ring ℂ proves that 1 + (-u) + (v + u * v) = 1 - u + v + u * v.

    line 7

      ring
Matrix.mul_apply
The (i, k) entry of the product of two matrices M and N is given by the sum ∑ j, M i j * N j k over all intermediate indices j.
Matrix.vecMul
The multiplication of a row vector by a matrix, where the j-th component is the dot product of the vector with the j-th column of the matrix.
dotProduct
The dot product of two vectors is the sum over all indices of their componentwise products.
Fin.sum_univ_two
A sum of a function over the two-element type Fin 2 equals f 0 + f 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

theorem three_hadamard_clean_return_numerator (u v : ℂ) :    ((!![1, 1; 1, -1] : Matrix (Fin 2) (Fin 2) ℂ) *      Matrix.diagonal ![1,u] * !![1,1;1,-1] *      Matrix.diagonal ![1,v] * !![1,1;1,-1] : Matrix (Fin 2) (Fin 2) ℂ) 1 0 =        1 - u + v + u*v := by  simp [Matrix.mul_apply, Matrix.vecMul, dotProduct, Fin.sum_univ_two]  ring
See it in the graphDiscuss this resultChallenge it