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).
- If $p,q$ are real-rooted of degree at most $d$, then $p\boxplus_dq$ is real-rooted [MSS22].
- If $p,q$ are real-rooted of degree at most $d$ and $q$ has only nonnegative roots, then $p\boxtimes_dq$ is real-rooted [MSS22].
- The signed reciprocal $\hat p=x^dp(-1/x)$ satisfies $\widehat{p*_dq}=\hat p\boxtimes_d\hat q$.
Theorem (root location). Let $p,q$ have degree exactly $d$ and be real-rooted.
- If the roots of $p$ lie in $[A,B]$ and the roots of $q$ lie in $[a,b]$, then the roots of $p\boxplus_dq$ lie in $[A+a,B+b]$ (Walsh's theorem in the finite free setting; see [LR18, Prop. 1.1]).
- If $\alpha_i$ and $\rho_i$ are the $i$th smallest roots of $p$ and of $p\boxplus_dq$, and the roots of $q$ lie in $[a,b]$, then $\alpha_i+a\le\rho_i\le\alpha_i+b$.
- $p(x+s)\boxplus_dq(x+t)=(p\boxplus_dq)(x+s+t)$ for all real $s,t$ and $\deg p,\deg q\le d$.
Theorem (stability and interlacing). Let $g\ne0$ be real-rooted with $\deg g\le D$.
- If $\deg f\le m\le D$, then $f\boxplus_Dg=f\boxplus_m\tfrac{m!}{D!}g^{(D-m)}$.
- Convolution by $g$ in a single variable $x_q$, namely $p\mapsto\sum_{i\le D}\frac{(D-i)!}{D!}\,[x^{D-i}]g\;\partial_q^{\,i}p$, maps multivariate real stable polynomials of degree at most $D$ in $x_q$ to real stable polynomials or zero. In the degree box $\kappa$ with $\kappa_q=D$, its algebraic symbol is $g(x_q+y_q)\prod_{i\ne q}(x_i+y_i)^{\kappa_i}$.
- If $g$ is monic of degree $D$, $\deg f,\deg h\le D$, both have positive leading coefficient and $h\ll f$, then $h\boxplus_Dg\ll f\boxplus_Dg$ in the zero-aware sense.
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
- [MSS22] 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} } - [GM22] 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} } - [LR18] 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} }