Finite free convolutions

The finite free additive and multiplicative convolutions of Marcus, Spielman and Srivastava preserve real-rootedness, the additive one moves roots by at most the root range of the second factor, and the rectangular additive convolution preserves nonnegative roots. These convolutions are finite analogues of the free convolutions of random matrix theory.

Results

Write $p(x)=\sum_{i=0}^{d}a_ix^{d-i}$ and $q(x)=\sum_{j=0}^{d}b_jx^{d-j}$ in a degree box of size $d$. The finite free additive convolution is $$ (p\boxplus_dq)(x)=\sum_{k=0}^{d}x^{d-k}\sum_{i+j=k} \frac{(d-i)!\,(d-j)!}{d!\,(d-k)!}\,a_ib_j . $$ The rectangular additive convolution $p\boxplus_{m,n}q$ in a degree box of size $n$ multiplies each term by the further factor $\frac{(n+m-i)!\,(n+m-j)!}{(n+m)!\,(n+m-k)!}$. More generally, for real $\alpha$ the weight of $a_ib_j$ in the box of size $n$ is $$ \frac{(n)^{\underline{k}}}{(n)^{\underline{i}}\,(n)^{\underline{j}}}\cdot \frac{(n+\alpha)^{\underline{k}}}{(n+\alpha)^{\underline{i}}\,(n+\alpha)^{\underline{j}}}, \qquad k=i+j, $$ with falling factorials $(x)^{\underline{k}}$; $\alpha=m$ is the rectangular case. The finite free multiplicative convolution is $$ (p\boxtimes_dq)(x)=\sum_{k=0}^{d}(-1)^k\binom dk^{-1}a_kb_k\,x^{d-k}, $$ that is, $(-1)^d(p*_dq)(-x)$ for the Schur–Szegő composition $p*_dq=\sum_k\binom dk^{-1}p_kq_kx^k$ of the coefficients $p_k,q_k$ of $x^k$.

Theorem (real-rootedness).

Theorem (root location). Let $p,q$ have degree exactly $d$ and be real-rooted.

Theorem (stability and interlacing). Let $g\ne0$ be real-rooted with $\deg g\le D$.

Theorem (rectangular convolution). The polynomial $f\boxplus_{m,n}g$ has degree at most $n$. If $f,g$ have degree exactly $n$, positive leading coefficients and only nonnegative roots, then $f\boxplus_{m,n}g$ is zero or real-rooted with only nonnegative roots [GM22]. The same holds for the parameters $\alpha=\pm\tfrac12$, for real-rooted $f,g$ of degree at most $n$ with only nonnegative roots.

Use

The rectangular convolution gives a proof of the Narayana transformation theorem.

Proof

The additive theorem follows from the Lieb–Sokal lemma: the convolution is a differential operator in $q$ applied to $p$. The parameters $\pm\tfrac12$ reduce to $\boxplus_{2n}$ and $\boxplus_{2n+1}$ through the lifts $p(x^2)$ and $x\,p(x^2)$. The rectangular case uses a multiaffine polarization of $y^mp(xy)$ in $n+(m+n)$ variables, which is stable when $p(xy)$ is; the reciprocal polarization of $g$, applied as a differential operator to the polarization of $f$, gives $y^m(f\boxplus_{m,n}g)(xy)$ after the variables are identified [GM22].

References

  1. [MSS22] Adam W. Marcus, Daniel A. Spielman, & Nikhil Srivastava. Finite free convolutions of polynomials. Probability Theory and Related Fields, 182(3-4), 807-848, 2022.
    BibTeX
    @article{MarcusSpielmanSrivastava2022,
      author = {Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil},
      title = {Finite free convolutions of polynomials},
      year = {2022},
      journal = {Probability Theory and Related Fields},
      volume = {182},
      number = {3-4},
      pages = {807--848},
      doi = {10.1007/s00440-021-01105-w},
      url = {https://doi.org/10.1007/s00440-021-01105-w}
    }
  2. [GM22] Aurelien Gribinski & Adam W. Marcus. A rectangular additive convolution for polynomials. Combinatorial Theory, 2(1), 2022.
    BibTeX
    @article{GribinskiMarcus2022,
      author = {Gribinski, Aurelien and Marcus, Adam W.},
      title = {A rectangular additive convolution for polynomials},
      year = {2022},
      journal = {Combinatorial Theory},
      volume = {2},
      number = {1},
      doi = {10.5070/c62156888},
      url = {https://doi.org/10.5070/c62156888}
    }
  3. [LR18] Jonathan Leake & Nick Ryder. On the Further Structure of the Finite Free Convolutions. arXiv e-prints, 2018.
    BibTeX
    @article{LeakeRyder2018x,
      author = {Jonathan Leake and Nick Ryder},
      title = {On the {F}urther {S}tructure of the {F}inite {F}ree {C}onvolutions},
      year = {2018},
      eprint = {1811.06382v1},
      url = {https://arxiv.org/abs/1811.06382v1},
      journal = {arXiv e-prints}
    }

Definitions

  • Finite free additive convolution

    RealRooted.finiteFreeAdditiveConvolutionsource
    def finiteFreeAdditiveConvolution (d : ℕ) (p q : ℝ[X]) : ℝ[X] :=
      ∑ k ∈ Finset.range (d + 1),
        C (finiteFreeAdditiveConvolutionCoeff d p q k) * X ^ (d - k)
  • Rectangular additive convolution

    RealRooted.rectangularAdditiveConvolutionsource
    def rectangularAdditiveConvolution (m n : ℕ) (f g : ℝ[X]) : ℝ[X] :=
      ∑ k ∈ Finset.range (n + 1),
        C (rectangularConvolutionCoeff m n f g k) * X ^ (n - k)
  • Rectangular additive convolution with a real parameter

    RealRooted.generalizedRectangularAdditiveConvolutionsource
    def generalizedRectangularAdditiveConvolution (α : ℝ) (n : ℕ) (p q : ℝ[X]) : ℝ[X] :=
      ∑ k ∈ Finset.range (n + 1),
        C (generalizedRectangularConvolutionCoeff α n p q k) * X ^ (n - k)
  • Finite free multiplicative convolution

    RealRooted.finiteFreeMultiplicativeConvolutionsource
    def finiteFreeMultiplicativeConvolution (d : ℕ) (p q : ℝ[X]) : ℝ[X] :=
      C ((-1 : ℝ) ^ d) * (schurSzegoComp d p q).comp (-X)
  • Signed reciprocal x^d p(-1/x)

    RealRooted.signedReciprocalsource
    def signedReciprocal (d : ℕ) (p : ℝ[X]) : ℝ[X] :=
      reflect d (p.comp (-X))
  • Zero, or real-rooted with nonnegative roots

    RealRooted.HasOnlyNonnegRootssource
    def HasOnlyNonnegRoots (p : ℝ[X]) : Prop :=
      p = 0 ∨ p.Splits ∧ ∀ r ∈ p.roots, 0 ≤ r
  • Two-block polarization of y^m p(xy)

    RealRooted.rectangularPolarizationsource
    def rectangularPolarization (m n : ℕ) (p : ℂ[X]) :
        MvPolynomial (Sum (Fin n) (Fin (m + n))) ℂ :=
      ∑ k ∈ Finset.range (n + 1),
        MvPolynomial.C
            (p.coeff k / (n.choose k : ℂ) / ((m + n).choose (m + k) : ℂ)) *
          MvPolynomial.rename Sum.inl (MvPolynomial.esymm (Fin n) ℂ k) *
          MvPolynomial.rename Sum.inr
            (MvPolynomial.esymm (Fin (m + n)) ℂ (m + k))
  • Signed reciprocal of the rectangular polarization

    RealRooted.reciprocalRectangularPolarizationsource
    def reciprocalRectangularPolarization (m n : ℕ) (p : ℂ[X]) :
        MvPolynomial (Sum (Fin n) (Fin (m + n))) ℂ :=
      MvPolynomial.C ((-1 : ℂ) ^ m) *
        signedMultiaffineReciprocal (rectangularPolarization m n p)

Theorems

  • Marcus–Spielman–Srivastava: ⊞_d preserves real-rootednessMain result

    RealRooted.splits_finiteFreeAdditiveConvolutionsource
    theorem splits_finiteFreeAdditiveConvolution
        (d : ℕ) {p q : ℝ[X]}
        (hp : p.Splits) (hq : q.Splits)
        (hpdeg : p.natDegree ≤ d) (hqdeg : q.natDegree ≤ d) :
        (finiteFreeAdditiveConvolution d p q).Splits
  • Walsh–Leake–Ryder: ⊞_d sends roots in [A, B] and [a, b] into [A + a, B + b]

    RealRooted.IsRealRootedIn.finiteFreeAdditiveConvolution_Iccsource
    theorem IsRealRootedIn.finiteFreeAdditiveConvolution_Icc {d : ℕ} {p q : ℝ[X]} {A B a b : ℝ}
        (hpd : p.natDegree = d) (hqd : q.natDegree = d) (hp : IsRealRootedIn (Icc A B) p)
        (hq : IsRealRootedIn (Icc a b) q) :
        IsRealRootedIn (Icc (A + a) (B + b)) (finiteFreeAdditiveConvolution d p q)
  • Weyl bounds: the ith root of p ⊞_d q lies between α_i + a and α_i + b

    RealRooted.orderedRoot_finiteFreeAdditiveConvolution_boundssource
    theorem orderedRoot_finiteFreeAdditiveConvolution_bounds
        {d : ℕ} {p q : ℝ[X]} {a b : ℝ}
        (hpd : p.natDegree = d) (hqd : q.natDegree = d)
        (hp : p ≠ 0 ∧ p.Splits) (hq : IsRealRootedIn (Set.Icc a b) q)
        (i : Fin d) :
        orderedRoot p d i + a ≤
            orderedRoot (finiteFreeAdditiveConvolution d p q) d i ∧
          orderedRoot (finiteFreeAdditiveConvolution d p q) d i ≤
            orderedRoot p d i + b
  • Translating the arguments of ⊞_d by s and t translates the output by s + t

    RealRooted.finiteFreeAdditiveConvolution_comp_X_add_Csource
    theorem finiteFreeAdditiveConvolution_comp_X_add_C {d : ℕ} {p q : ℝ[X]} (hp : p.natDegree ≤ d)
        (hq : q.natDegree ≤ d) (s t : ℝ) :
        finiteFreeAdditiveConvolution d (p.comp (X + C s)) (q.comp (X + C t)) =
          (finiteFreeAdditiveConvolution d p q).comp (X + C (s + t))
  • For deg f ≤ m: f ⊞_D g = f ⊞_m (m!/D!) g^(D−m)

    RealRooted.finiteFreeAdditiveConvolution_eq_lowerDegreesource
    theorem finiteFreeAdditiveConvolution_eq_lowerDegree
        {D m : ℕ} (hmD : m ≤ D) {f : ℝ[X]} (hf : f.natDegree ≤ m) (g : ℝ[X]) :
        finiteFreeAdditiveConvolution D f g =
          finiteFreeAdditiveConvolution m f
            (finiteFreeAdditiveDerivativeNormalization D m g)
  • The coordinate convolution symbol is g(x_q + y_q) times spectator factors

    RealRooted.algebraicSymbol_finiteFreeAdditiveConvolutionDegreeBoxsource
    theorem algebraicSymbol_finiteFreeAdditiveConvolutionDegreeBox
        {σ : Type*} [Fintype σ] [DecidableEq σ]
        (q : σ) (D : ℕ) {g : ℝ[X]} (hgdeg : g.natDegree ≤ D)
        (κ : σ → ℕ) (hκ : κ q = D) :
        MvPolynomial.algebraicSymbol κ
            (finiteFreeAdditiveConvolutionDegreeBox D g q κ) =
          finiteFreeAdditiveConvolutionSymbol g q *
            ∏ i ∈ Finset.univ.erase q,
              (MvPolynomial.X (Sum.inl i) + MvPolynomial.X (Sum.inr i)) ^ κ i
  • Finite free additive convolution preserves multivariate real stability

    RealRooted.finiteFreeAdditiveConvolutionAt_realStableOrZerosource
    theorem finiteFreeAdditiveConvolutionAt_realStableOrZero
        {σ : Type*} [Finite σ] (q : σ) (D : ℕ) {g : ℝ[X]}
        (hg0 : g ≠ 0) (hgs : g.Splits) (hgdeg : g.natDegree ≤ D)
        {p : MvPolynomial σ ℝ} (hpq : p.degreeOf q ≤ D) (hp : MvRealStable p) :
        MvRealStableOrZero (finiteFreeAdditiveConvolutionAt D g q p)
  • Convolution by a fixed monic split factor preserves directed interlacing

    RealRooted.interl_finiteFreeAdditiveConvolution_rightsource
    theorem interl_finiteFreeAdditiveConvolution_right
        {D : ℕ} {g f h : ℝ[X]} (hg : g.Monic) (hgs : g.Splits)
        (hgdeg : g.natDegree = D) (hfdeg : f.natDegree ≤ D)
        (hhdeg : h.natDegree ≤ D) (hhf : StrictInterl h f)
        (hf : HasPosLeadingCoeff f) (hh : HasPosLeadingCoeff h) :
        Interl (finiteFreeAdditiveConvolution D h g)
          (finiteFreeAdditiveConvolution D f g)
  • Gribinski–Marcus: the rectangular convolution preserves nonnegative roots

    RealRooted.HasOnlyNonnegRoots.rectangularAdditiveConvolutionsource
    theorem HasOnlyNonnegRoots.rectangularAdditiveConvolution {m n : ℕ} {f g : ℝ[X]}
        (hfdeg : f.natDegree = n) (hgdeg : g.natDegree = n)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        (hf : HasOnlyNonnegRoots f) (hg : HasOnlyNonnegRoots g) :
        HasOnlyNonnegRoots (rectangularAdditiveConvolution m n f g)
  • The parameter −1/2 preserves nonnegative roots

    RealRooted.splits_and_roots_nonneg_rectangular_neg_halfsource
    theorem splits_and_roots_nonneg_rectangular_neg_half (n : ℕ) (p q : ℝ[X])
        (hp : p.Splits) (hq : q.Splits)
        (hproots : ∀ r ∈ p.roots, 0 ≤ r) (hqroots : ∀ r ∈ q.roots, 0 ≤ r)
        (hpdeg : p.natDegree ≤ n) (hqdeg : q.natDegree ≤ n) :
        (generalizedRectangularAdditiveConvolution (-(1 / 2 : ℝ)) n p q).Splits ∧
          ∀ r ∈ (generalizedRectangularAdditiveConvolution (-(1 / 2 : ℝ)) n p q).roots,
            0 ≤ r
  • The parameter 1/2 preserves nonnegative roots

    RealRooted.splits_and_roots_nonneg_rectangular_pos_halfsource
    theorem splits_and_roots_nonneg_rectangular_pos_half (n : ℕ) (p q : ℝ[X])
        (hp : p.Splits) (hq : q.Splits)
        (hproots : ∀ r ∈ p.roots, 0 ≤ r) (hqroots : ∀ r ∈ q.roots, 0 ≤ r)
        (hpdeg : p.natDegree ≤ n) (hqdeg : q.natDegree ≤ n) :
        (generalizedRectangularAdditiveConvolution (1 / 2 : ℝ) n p q).Splits ∧
          ∀ r ∈ (generalizedRectangularAdditiveConvolution (1 / 2 : ℝ) n p q).roots,
            0 ≤ r
  • Marcus–Spielman–Srivastava: ⊠_d preserves real-rootedness

    RealRooted.splits_finiteFreeMultiplicativeConvolutionsource
    theorem splits_finiteFreeMultiplicativeConvolution {d : ℕ} {p q : ℝ[X]}
        (hp : p.Splits) (hpdeg : p.natDegree ≤ d) (hq : q.Splits) (hqdeg : q.natDegree ≤ d)
        (hq_roots : ∀ r ∈ q.roots, 0 ≤ r) :
        (finiteFreeMultiplicativeConvolution d p q).Splits
  • The signed reciprocal turns Schur–Szegő composition into ⊠_d

    RealRooted.signedReciprocal_schurSzegoCompsource
    theorem signedReciprocal_schurSzegoComp
        (d : ℕ) (f g : ℝ[X]) :
        signedReciprocal d (schurSzegoComp d f g) =
          finiteFreeMultiplicativeConvolution d
            (signedReciprocal d f) (signedReciprocal d g)
  • Coefficients of the rectangular additive convolution

    RealRooted.coeff_rectangularAdditiveConvolution_of_lesource
    theorem coeff_rectangularAdditiveConvolution_of_le (m n : ℕ) (f g : ℝ[X])
        {j : ℕ} (hj : j ≤ n) :
        (rectangularAdditiveConvolution m n f g).coeff j =
          rectangularConvolutionCoeff m n f g (n - j)
  • The rectangular additive convolution has degree at most n

    RealRooted.natDegree_rectangularAdditiveConvolution_lesource
    theorem natDegree_rectangularAdditiveConvolution_le (m n : ℕ) (f g : ℝ[X]) :
        (rectangularAdditiveConvolution m n f g).natDegree ≤ n
  • The rectangular polarization is multiaffine in both blocks

    RealRooted.isMultiaffine_rectangularPolarizationsource
    theorem isMultiaffine_rectangularPolarization (m n : ℕ) (p : ℂ[X]) :
        MvPolynomial.IsMultiaffine (rectangularPolarization m n p)
  • Rectangular polarization preserves upper-half-plane stability

    RealRooted.mvUpperHalfPlaneStable_rectangularPolarizationsource
    theorem mvUpperHalfPlaneStable_rectangularPolarization
        {m n : ℕ} {p : ℂ[X]} (hpdeg : p.natDegree = n)
        (hplead : p.leadingCoeff ≠ 0)
        (hstable : MvUpperHalfPlaneStable (xyLift p)) :
        MvUpperHalfPlaneStable (rectangularPolarization m n p)
  • The signed reciprocal polarization is also stable

    RealRooted.mvUpperHalfPlaneStable_reciprocalRectangularPolarizationsource
    theorem mvUpperHalfPlaneStable_reciprocalRectangularPolarization
        {m n : ℕ} {p : ℂ[X]} (hpdeg : p.natDegree = n)
        (hplead : p.leadingCoeff ≠ 0)
        (hstable : MvUpperHalfPlaneStable (xyLift p)) :
        MvUpperHalfPlaneStable (reciprocalRectangularPolarization m n p)
  • The differential pairing of the two polarizations is the rectangular convolution

    RealRooted.rectangularDifferential_diagonal_identitysource
    theorem rectangularDifferential_diagonal_identity
        (m n : ℕ) (f g : ℝ[X]) :
        MvPolynomial.rename rectangularDiagonal
            (applyNegDifferential
              (reciprocalRectangularPolarization m n
                (g.map Complex.ofRealHom))
              (rectangularPolarization m n (f.map Complex.ofRealHom))) =
          MvPolynomial.X 1 ^ m *
            xyLift ((rectangularAdditiveConvolution m n f g).map
              Complex.ofRealHom)

Lean source RealRooted/Challenges/Preservers/FiniteFreeConvolutions.lean at revision d6670742. Formalized 2026-09-11.