AFTD Auto-Formalizing Theoretical Domains

matrix_q_permanent_three_of_diag_one

theoremverifiedformalization

For any real symmetric 3-by-3 matrix A with all diagonal entries equal to 1, writing x = A 0 1, y = A 1 2, and z = A 0 2, the q-permanent of A at q equals 1 + (x^2 + y^2) * q + 2 * x * y * z * q^2 + z^2 * q^3.

Statement

theorem matrix_q_permanent_three_of_diag_one (A : Matrix (Fin 3) (Fin 3) ℝ)
    (hsymm : A.IsSymm) (hdiag : ∀ i, A i i = 1) (q : ℝ) :
    let x := A 0 1
    let y := A 1 2
    let z := A 0 2
    matrix_q_permanent q A = 1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3
Formalizes
arXiv:2611.14694, Proof of Proposition 5.1 -- Real positive definite counterexamples to a monotonicity conjecture for the q-permanent
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • matrix_q_permanentThe q-permanent of an n-by-n matrix M over a commutative semiring R at parameter q in R is the sum over all permutations sigma of Fin n of…
Used by 1

Read back from the Lean

For every 3 × 3 real matrix A and every real number q, if A is symmetric (A.IsSymm) and every diagonal entry of A is 1 (∀ i : Fin 3, A i i = 1), then the q-permanent of A is equal to 1 + (x^2 + y^2) * q + 2 * x * y * z * q^2 + z^2 * q^3, where x = A 0 1, y = A 1 2, and z = A 0 2.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof evaluates the q-permanent of a 3x3 symmetric matrix with unit diagonal by explicit expansion over the symmetric group S₃. It defines all six permutations of three elements, computes their inversion counts to determine the exponents of q, and expands each product of matrix entries. Using the unit diagonal entries (A i i = 1) and symmetry (A j i = A i j) reduces the matrix entries to the parameters x = A 0 1, y = A 1 2, and z = A 0 2, after which polynomial ring arithmetic simplifies the sum to the claimed expression.

  1. The variables x, y, z are introduced for the off-diagonal entries, and the six permutations p0 through p5 of {0, 1, 2} are defined.

    We name the off-diagonal entries x = A 0 1, y = A 1 2, and z = A 0 2. We then define all six elements of the symmetric group S₃: the identity p0 = 1, the three transpositions p1 = (0 1), p2 = (1 2), and p3 = (0 2), and the two 3-cycles p4 = (0 1)(1 2) and p5 = (1 2)(0 1).

    lines 8–14

      intro x y z
      let p0 : Equiv.Perm (Fin 3) := 1
      let p1 : Equiv.Perm (Fin 3) := Equiv.swap 0 1
      let p2 : Equiv.Perm (Fin 3) := Equiv.swap 1 2
      let p3 : Equiv.Perm (Fin 3) := Equiv.swap 0 2
      let p4 : Equiv.Perm (Fin 3) := Equiv.swap 0 1 * Equiv.swap 1 2
      let p5 : Equiv.Perm (Fin 3) := Equiv.swap 1 2 * Equiv.swap 0 1
  2. The definition of the q-permanent is unfolded and the sum over all permutations is expanded into six explicit summands.

    Unfolding `matrix_q_permanent` writes the q-permanent as the sum over all permutations σ of q^(inv σ) ∏ i, A i (σ i). Lean verifies by computational evaluation (`decide`) that the universe of permutations of Fin 3 is precisely {p0, p1, p2, p3, p4, p5} and that these six elements are distinct. We then peel off each permutation one by one using `Finset.sum_insert` and finish with `Finset.sum_singleton`.

    lines 15–26

    uses Finset.sum_insert, Finset.sum_singleton

      unfold matrix_q_permanent
      have h_univ : (Finset.univ : Finset (Equiv.Perm (Fin 3))) = {p0, p1, p2, p3, p4, p5} := by decide
      rw [show (∑ σ : Equiv.Perm (Fin 3), _) = ∑ σ ∈ (Finset.univ : Finset (Equiv.Perm (Fin 3))), _ from rfl]
      rw [h_univ]
      have ne0 : p0 ∉ ({p1, p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide
      have ne1 : p1 ∉ ({p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide
      have ne2 : p2 ∉ ({p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide
      have ne3 : p3 ∉ ({p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide
      have ne4 : p4 ∉ ({p5} : Finset (Equiv.Perm (Fin 3))) := by decide
      rw [Finset.sum_insert ne0, Finset.sum_insert ne1, Finset.sum_insert ne2,
          Finset.sum_insert ne3, Finset.sum_insert ne4, Finset.sum_singleton]
      dsimp only
  3. The inversion count of each permutation is determined and substituted into the powers of q.

    The number of inversions |{(i, j) : i < j ∧ σ j < σ i}| for each permutation is verified by finite evaluation (`decide`): p0 has 0 inversions; the transpositions p1 and p2 each have 1 inversion; the long transposition p3 has 3 inversions; and the 3-cycles p4 and p5 each have 2 inversions. Rewriting these values simplifies the powers of q across the six terms to q^0, q^1, q^1, q^3, q^2, and q^2.

    lines 27–33

      have h_inv0 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p0 p.2 < p0 p.1)).card = 0 := by decide
      have h_inv1 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p1 p.2 < p1 p.1)).card = 1 := by decide
      have h_inv2 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p2 p.2 < p2 p.1)).card = 1 := by decide
      have h_inv3 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p3 p.2 < p3 p.1)).card = 3 := by decide
      have h_inv4 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p4 p.2 < p4 p.1)).card = 2 := by decide
      have h_inv5 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p5 p.2 < p5 p.1)).card = 2 := by decide
      rw [h_inv0, h_inv1, h_inv2, h_inv3, h_inv4, h_inv5]
  4. Each product ∏ i, A i (σ i) is expanded into A 0 (σ 0) * A 1 (σ 1) * A 2 (σ 2) and evaluated at the concrete indices.

    We apply `Fin.prod_univ_three` to each of the six summands to expand the product over {0, 1, 2} into the product of three matrix entries. The values of each permutation on each input index are verified by definition (`rfl`), and rewriting them produces explicit entries such as A 0 1 * A 1 0 * A 2 2 for p1.

    lines 34–54

    uses Fin.prod_univ_three

      repeat rw [Fin.prod_univ_three]
      have hp0_0 : p0 0 = 0 := rfl
      have hp0_1 : p0 1 = 1 := rfl
      have hp0_2 : p0 2 = 2 := rfl
      have hp1_0 : p1 0 = 1 := rfl
      have hp1_1 : p1 1 = 0 := rfl
      have hp1_2 : p1 2 = 2 := rfl
      have hp2_0 : p2 0 = 0 := rfl
      have hp2_1 : p2 1 = 2 := rfl
      have hp2_2 : p2 2 = 1 := rfl
      have hp3_0 : p3 0 = 2 := rfl
      have hp3_1 : p3 1 = 1 := rfl
      have hp3_2 : p3 2 = 0 := rfl
      have hp4_0 : p4 0 = 1 := rfl
      have hp4_1 : p4 1 = 2 := rfl
      have hp4_2 : p4 2 = 0 := rfl
      have hp5_0 : p5 0 = 2 := rfl
      have hp5_1 : p5 1 = 0 := rfl
      have hp5_2 : p5 2 = 1 := rfl
      rw [hp0_0, hp0_1, hp0_2, hp1_0, hp1_1, hp1_2, hp2_0, hp2_1, hp2_2,
          hp3_0, hp3_1, hp3_2, hp4_0, hp4_1, hp4_2, hp5_0, hp5_1, hp5_2]
  5. The unit diagonal values and the symmetry of A are substituted into each term.

    From the hypothesis that all diagonal entries are 1, we obtain A 0 0 = 1, A 1 1 = 1, and A 2 2 = 1. From the symmetry of A, lower-triangular entries equal their upper-triangular counterparts: A 1 0 = A 0 1 = x, A 2 1 = A 1 2 = y, and A 2 0 = A 0 2 = z. Rewriting these equations expresses every factor in all six summands in terms of 1, x, y, and z.

    lines 55–61

      have hd0 : A 0 0 = 1 := hdiag 0
      have hd1 : A 1 1 = 1 := hdiag 1
      have hd2 : A 2 2 = 1 := hdiag 2
      have hs01 : A 1 0 = A 0 1 := hsymm.apply 0 1
      have hs12 : A 2 1 = A 1 2 := hsymm.apply 1 2
      have hs02 : A 2 0 = A 0 2 := hsymm.apply 0 2
      rw [hd0, hd1, hd2, hs01, hs12, hs02]
  6. The sum of the six terms simplifies algebraically to 1 + (x^2 + y^2) * q + 2 * x * y * z * q^2 + z^2 * q^3. automation

    We rewrite the goal to show that 1 * (1 * 1 * 1) + q^1 * (x * x * 1) + q^1 * (1 * y * y) + q^3 * (z * 1 * z) + q^2 * (x * y * z) + q^2 * (z * x * y) equals the target polynomial. The `ring` tactic expands and groups like powers of q, matching the constant term 1, the q coefficient x^2 + y^2, the q^2 coefficient xyz + zxy = 2xyz, and the q^3 coefficient z^2.

    lines 62–68

      change 1 * (1 * 1 * 1) +
        (q ^ 1 * (x * x * 1) +
          (q ^ 1 * (1 * y * y) +
            (q ^ 3 * (z * 1 * z) +
              (q ^ 2 * (x * y * z) + q ^ 2 * (z * x * y))))) =
        1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3
      ring
Finset.sum_insert
If an element a is not in a finite set s, then the sum of a function over s ∪ {a} equals its value at a plus its sum over s.
Finset.sum_singleton
The sum of a function over a singleton set {a} equals its value at a.
Fin.prod_univ_three
The product of a function over the three-element set {0, 1, 2} equals f 0 * f 1 * f 2.

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

/-- The q-permanent of a real symmetric 3x3 matrix with unit diagonal equals 1 + (x^2+y^2)q + 2xyz q^2 + z^2 q^3. -/theorem matrix_q_permanent_three_of_diag_one (A : Matrix (Fin 3) (Fin 3) ℝ)    (hsymm : A.IsSymm) (hdiag : ∀ i, A i i = 1) (q : ℝ) :    let x := A 0 1    let y := A 1 2    let z := A 0 2    matrix_q_permanent q A = 1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3 := by  intro x y z  let p0 : Equiv.Perm (Fin 3) := 1  let p1 : Equiv.Perm (Fin 3) := Equiv.swap 0 1  let p2 : Equiv.Perm (Fin 3) := Equiv.swap 1 2  let p3 : Equiv.Perm (Fin 3) := Equiv.swap 0 2  let p4 : Equiv.Perm (Fin 3) := Equiv.swap 0 1 * Equiv.swap 1 2  let p5 : Equiv.Perm (Fin 3) := Equiv.swap 1 2 * Equiv.swap 0 1  unfold matrix_q_permanent  have h_univ : (Finset.univ : Finset (Equiv.Perm (Fin 3))) = {p0, p1, p2, p3, p4, p5} := by decide  rw [show (∑ σ : Equiv.Perm (Fin 3), _) = ∑ σ ∈ (Finset.univ : Finset (Equiv.Perm (Fin 3))), _ from rfl]  rw [h_univ]  have ne0 : p0 ∉ ({p1, p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide  have ne1 : p1 ∉ ({p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide  have ne2 : p2 ∉ ({p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide  have ne3 : p3 ∉ ({p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide  have ne4 : p4 ∉ ({p5} : Finset (Equiv.Perm (Fin 3))) := by decide  rw [Finset.sum_insert ne0, Finset.sum_insert ne1, Finset.sum_insert ne2,      Finset.sum_insert ne3, Finset.sum_insert ne4, Finset.sum_singleton]  dsimp only  have h_inv0 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p0 p.2 < p0 p.1)).card = 0 := by decide  have h_inv1 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p1 p.2 < p1 p.1)).card = 1 := by decide  have h_inv2 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p2 p.2 < p2 p.1)).card = 1 := by decide  have h_inv3 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p3 p.2 < p3 p.1)).card = 3 := by decide  have h_inv4 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p4 p.2 < p4 p.1)).card = 2 := by decide  have h_inv5 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p5 p.2 < p5 p.1)).card = 2 := by decide  rw [h_inv0, h_inv1, h_inv2, h_inv3, h_inv4, h_inv5]  repeat rw [Fin.prod_univ_three]  have hp0_0 : p0 0 = 0 := rfl  have hp0_1 : p0 1 = 1 := rfl  have hp0_2 : p0 2 = 2 := rfl  have hp1_0 : p1 0 = 1 := rfl  have hp1_1 : p1 1 = 0 := rfl  have hp1_2 : p1 2 = 2 := rfl  have hp2_0 : p2 0 = 0 := rfl  have hp2_1 : p2 1 = 2 := rfl  have hp2_2 : p2 2 = 1 := rfl  have hp3_0 : p3 0 = 2 := rfl  have hp3_1 : p3 1 = 1 := rfl  have hp3_2 : p3 2 = 0 := rfl  have hp4_0 : p4 0 = 1 := rfl  have hp4_1 : p4 1 = 2 := rfl  have hp4_2 : p4 2 = 0 := rfl  have hp5_0 : p5 0 = 2 := rfl  have hp5_1 : p5 1 = 0 := rfl  have hp5_2 : p5 2 = 1 := rfl  rw [hp0_0, hp0_1, hp0_2, hp1_0, hp1_1, hp1_2, hp2_0, hp2_1, hp2_2,      hp3_0, hp3_1, hp3_2, hp4_0, hp4_1, hp4_2, hp5_0, hp5_1, hp5_2]  have hd0 : A 0 0 = 1 := hdiag 0  have hd1 : A 1 1 = 1 := hdiag 1  have hd2 : A 2 2 = 1 := hdiag 2  have hs01 : A 1 0 = A 0 1 := hsymm.apply 0 1  have hs12 : A 2 1 = A 1 2 := hsymm.apply 1 2  have hs02 : A 2 0 = A 0 2 := hsymm.apply 0 2  rw [hd0, hd1, hd2, hs01, hs12, hs02]  change 1 * (1 * 1 * 1) +    (q ^ 1 * (x * x * 1) +      (q ^ 1 * (1 * y * y) +        (q ^ 3 * (z * 1 * z) +          (q ^ 2 * (x * y * z) + q ^ 2 * (z * x * y))))) =    1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3  ring
See it in the graphDiscuss this resultChallenge it