Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.5 — quadrature for permutation-conjugated sums and products

Proved
SuperRamanujan227.Main.lemma_2_5

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

finite-free-probabilitygraph-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1polynomials

Let A,BA,BA,B be real symmetric m×mm\times mm×m matrices with A1=a1A\mathbf 1=a\mathbf 1A1=a1 and B1=b1B\mathbf 1=b\mathbf 1B1=b1 for real numbers a,ba,ba,b, and let pA,pBp_A,p_BpA​,pB​ be the polynomials with

χx(A)=(x−a) pA(x),χx(B)=(x−b) pB(x).\chi_x(A)=(x-a)\,p_A(x),\qquad \chi_x(B)=(x-b)\,p_B(x).χx​(A)=(x−a)pA​(x),χx​(B)=(x−b)pB​(x).

Let PPP be a uniformly random m×mm\times mm×m permutation matrix. Then, with both convolutions taken in degree m−1m-1m−1,

EP[χx(A+PBPT)]=(x−(a+b)) (pA⊞m−1pB)(x),\mathbb E_P\big[\chi_x(A+PBP^{\mathsf T})\big]=(x-(a+b))\,(p_A\boxplus_{m-1}p_B)(x),EP​[χx​(A+PBPT)]=(x−(a+b))(pA​⊞m−1​pB​)(x), EP[χx(APBPT)]=(x−ab) (pA⊠m−1pB)(x).\mathbb E_P\big[\chi_x(APBP^{\mathsf T})\big]=(x-ab)\,(p_A\boxtimes_{m-1}p_B)(x).EP​[χx​(APBPT)]=(x−ab)(pA​⊠m−1​pB​)(x).

Moreover pA⊞m−1pBp_A\boxplus_{m-1}p_BpA​⊞m−1​pB​ is real-rooted, and if at least one of pA,pBp_A,p_BpA​,pB​ has only nonnegative roots then pA⊠m−1pBp_A\boxtimes_{m-1}p_BpA​⊠m−1​pB​ is real-rooted.

This quadrature identity replaces the Haar average defining the finite free convolutions by an average over permutation matrices, which do have a combinatorial meaning; a,ba,ba,b are arbitrary real row sums.

Differences from the source:

  • encoding: ⊞ and ⊠ of Definition 2.4 (Haar averages over the orthogonal group) → the MSS coefficient formulas in degree m − 1; reason: the coefficient formulas agree with the Haar averages on characteristic polynomials [MSS22], the paper refers to them on p. 8; p_A, p_B have degree m − 1
  • encoding: p_A, p_B the polynomials satisfying χ_x(A) = (x − a)p_A(x), χ_x(B) = (x − b)p_B(x) → polynomials pA, pB given with these defining equations as hypotheses; reason: the quotient is unique since ℝ[x] is a domain; the hypotheses are satisfiable exactly when m ≥ 1, as the source presupposes
  • encoding: real-rooted; only nonnegative roots → nonzero with natDegree-many real roots; every real root is ≥ 0; reason: p_A, p_B are real-rooted (A, B symmetric), so their real roots are all their roots
Preamble
import Mathlib
import Definitions.Def_SuperRamanujan227_Main_Spectra
import Definitions.Def_SuperRamanujan227_Main_FiniteFreeConvolution
open Polynomial Matrix
Formal statement
namespace SuperRamanujan227.Main

/-- Lemma 2.5 (Quadrature, p. 8): for real symmetric `m × m` matrices with `A𝟙 = a𝟙`, `B𝟙 = b𝟙`
and `χ_x(A) = (x - a) p_A`, `χ_x(B) = (x - b) p_B`, the permutation averages of `χ_x(A + PBPᵀ)`
and `χ_x(APBPᵀ)` are `(x - (a+b)) (p_A ⊞ p_B)` and `(x - ab) (p_A ⊠ p_B)` (convolutions in
degree `m - 1`); `p_A ⊞ p_B` is real-rooted, and so is `p_A ⊠ p_B` when `p_A` or `p_B` has only
nonnegative roots. -/
theorem lemma_2_5 {m : ℕ} (A B : Matrix (Fin m) (Fin m) ℝ) (hA : A.IsSymm) (hB : B.IsSymm)
    (a b : ℝ) (hA1 : A *ᵥ (fun _ => (1 : ℝ)) = a • (fun _ => (1 : ℝ)))
    (hB1 : B *ᵥ (fun _ => (1 : ℝ)) = b • (fun _ => (1 : ℝ)))
    (pA pB : ℝ[X]) (hpA : A.charpoly = (X - C a) * pA) (hpB : B.charpoly = (X - C b) * pB) :
    expCharpolyAdd A B = (X - C (a + b)) * ffAdd (m - 1) pA pB ∧
      expCharpolyMul A B = (X - C (a * b)) * ffMul (m - 1) pA pB ∧
      RealRooted (ffAdd (m - 1) pA pB) ∧
      ((∀ x ∈ pA.roots, 0 ≤ x) ∨ (∀ x ∈ pB.roots, 0 ≤ x) →
        RealRooted (ffMul (m - 1) pA pB)) := by sorry

end SuperRamanujan227.Main
Source
Gil Cohen, Gal Maor, Quantitative Results on Super-Ramanujan Graphs, STOC 2027 submission #227 (October 2026), SHA-256 1ba5eacb267c8a63eff5e5b9d6b96d9f2b04d5a1e147d887b9e61574127831f8, Lemma 2.5, p. 8, Eqs. (3)–(4)
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me