Finite free convolutions of polynomials \thanks{ This research was partially supported by NSF grant CCF-1111257, an NSF Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS-0902962, a Simons Investigator Award to Daniel Spielman, and a MacArthur Fellowship.
Adam Marcus
Crisply
Yale University
Daniel A. Spielman
Yale University
Nikhil Srivastava
U. C. Berkeley
We study three convolutions of polynomials that are inspired by free probability. We define these to be the expected characteristic polynomials of certain random matrices. The symmetric additive and multiplicative convolutions have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, appears new. We prove that these convolutions produce real rooted polynomials and provide strong bounds on the locations of the roots of these polynomials. \dan{Turn this off
bounds.tex
\section{Transform bounds}

All of our transform bounds are proved using the following lemma.
It allows us to pinch together two of the roots of a polynomial without
  changing the value of the Cauchy transform at a particular point.
Through judicious use of this lemma, we are able to reduce statements about arbitrary
  polynomials to statements about polynomials with just one root.

\begin{lemma}[Pinching]\label{lem:pinch}
Let $\alpha > 0$, $d \geq 2$, and let 
  $p (x) \in \rrpoly{d}$ have at least two distinct roots.
Write $p (x) = \prod_{i=1}^{d} (x - \lambda_{i}) $
  where $\lambda_{1} \geq \lambda_{2} \geq \dots \geq \lambda_{d}$
  and $\lambda_{1} > \lambda_{k}$ for some $k$.
Then there exist real $\mu$ and $\rho$ so that
  $p (x) = \phat (x) + \ptil (x)$,
  where
\[
  \ptil (x) = (x- \mu)^{2} \prod_{i \not \in \setof{1,k}} (x - \lambda_{i}) \in \rrpoly{d}
\quad \text{and} \quad 
  \phat (x) = (x- \rho ) \prod_{i \not \in \setof{1,k}} (x - \lambda_{i}) \in \rrpoly{d-1},
\]
and 
\begin{itemize}
\item [a.]  $\maxroot{\shiftoper{\alpha} \ptil } = \maxroot{\shiftoper{\alpha}  \phat } = \maxroot{\shiftoper{\alpha } p}$,
\item [b.]  $\lambda_{1} > \mu > \lambda_{k}$, and
\item [c.]  $\rho > \lambda_{1}$.
In particular, if $d \geq 3$ then $\phat$ has at least two distinct roots.
\end{itemize}
\end{lemma}
\begin{proof}


Let $t = \maxroot{\shiftoper{\alpha } p}$ and set
\[
  \mu = t - \frac{2}{1/(t - \lambda_{1}) + 1/(t - \lambda_{k})}.
\]
We have chosen $\mu$ so that
\[
  \frac{2}{t - \mu} = \frac{1}{t - \lambda_{1}} + \frac{1}{t - \lambda_{k}}, 
\]
which implies
\[
  \frac{\deriv \ptil (t)}{\ptil  (t)} =
  \frac{\deriv p (t)}{p (t)} = \frac{1}{\alpha},
\]
and thus $\maxroot{\shiftoper{\alpha} \ptil } = t$.
Our choice of $\mu$ also guarantees that 
   $t - \mu$ is the harmonic average of $t - \lambda_{1}$  and $t - \lambda_{k}$.
Thus, $\mu$ must lie strictly between $\lambda_{1}$ and $\lambda_{k}$, which implies part $b$.
We may also conclude that $t - \mu < (1/2) (2t - (\lambda_{1} + \lambda_{k}))$,
  which implies that 
\begin{equation}\label{eqn:pinchMuAvg}
\mu > (\lambda_{1} + \lambda_{k})/2.
\end{equation}
We have
\[
\phat (x) = p (x) - \ptil (x)
= 
 \left(  (2 \mu - (\lambda_{1} + \lambda_{k} )) x - (\mu^{2} - \lambda_{1} \lambda_{k}) \right)
  \prod_{i \not \in \setof{1,k}} (x-\lambda_{i}).
\]
This and inequality \eqref{eqn:pinchMuAvg} imply that $\phat (x) \in \rrpoly{d-1}$.
As $\shiftoper{\alpha}$ is linear, we also have $(\shiftoper{\alpha} \phat) (t) = 0$.
To finish the proof of part $a$, we need to show that the maximum root of
  $\shiftoper{\alpha } \phat$ is less than $t$.
The one root of $\phat$ that is not a root of $p$ is
\[
 \rho  \defeq  \frac{\mu^{2} - \lambda_{1} \lambda_{k}}{2 \mu - (\lambda_{1} + \lambda_{k} )}.
\]
To see that $t > \rho $, compute
\[
  t- \rho  = \frac{(\lambda_{1} - \mu ) (\mu -\lambda_{k})}{2 \mu - \lambda_{1} - \lambda_{k}},
\]
which we know is greater than $0$ because of \eqref{eqn:pinchMuAvg} and the fact that 
  $\mu$ is between $\lambda_{1}$ and $\lambda_{k}$.
This completes the proof of part $a$.

To prove part $c$, note that
\[
  (2 \mu - (\lambda_{1} + \lambda_{k})) (\rho - \lambda_{1})
=
  \mu^{2} - 2 \lambda_{1} \mu  + \lambda_{1}^{2} = (\mu -\lambda_{1})^{2} > 0.
\]
\end{proof}





\subsection{Symmetric additive convolution}\label{sec:sqConvBound}

\newcommand{\phata}{\shiftoper{\alpha} \phat}
\newcommand{\ptila}{\shiftoper{\alpha} \ptil}
\newcommand{\pa}{\shiftoper{\alpha} p}
\newcommand{\qa}{\shiftoper{\alpha} q}

\newcommand{\pqa}{\shiftoper{\alpha} (p \sqsum_{d} q)}
\newcommand{\pqta}{\shiftoper{\alpha} (\ptil  \sqsum_{d} q)}
\newcommand{\pqha}{\shiftoper{\alpha} (\phat  \sqsum_{d} q)}

Theorem \ref{thm:symmetricAdditive} 
  tells us that if $p (x) \in \rrpoly{d}$ and $q (x) = x^{d-1}$,
  then $p (x) \sqsum_{d} q (x) = D p (x)$.
As $\maxroot{U_{\alpha} x^{d-1}} = (d-1) \alpha$,
  the following lemma may be viewed as a restriction of Theorem~\ref{thm:sqsumTrans}
  to the case that $q (x) = x^{d-1}$.

\begin{lemma}\label{lem:derivP}
For $\alpha \geq 0$, $d \geq 2$, and $p \in \rrpoly{d}$,
\begin{equation}\label{eqn:derivP}
\maxroot{\shiftoper{\alpha }  D p} \leq \maxroot{\shiftoper{\alpha} p} - \alpha.
\end{equation}
% with equality if and only if $p$ has only one root.
\end{lemma}
\begin{proof}
If $p = (x-\lambda)^{d}$, then $\maxroot{\shiftoper{\alpha} p} = \lambda + d\alpha$,
  and $\maxroot{\shiftoper{\alpha} D p} = \lambda + (d-1)\alpha$, giving equality in 
  \eqref{eqn:derivP}.

We now prove the rest of the lemma by induction on $d$, with $d = 2$ being the base case.
For a polynomial $p$ in $\rrpoly{d}$, define
\[
  \phi (p) = \maxroot{\shiftoper{\alpha} p} - \alpha - \maxroot{\shiftoper{\alpha } \deriv p} .
\]
We will prove that $\phi (p) \geq  0$ for all real rooted polynomials $p$.
% with at least two distinct roots.
In particular,
  for every $R > 0$, 
  we prove this for all polynomials $p \in \rrpoly{d}$ whose roots are bounded in abosolute value by $R$.
So, let $R > 0$ and let $p$ be a polynomial with roots in $[-R,R]$ that minimizes $\phi$.
As the set $[-R,R]^{d}$ is compact, there must be some polynomial at which the minimum is achieved.

Let $\beta = \maxroot{\shiftoper{\alpha } p} - \alpha$,
  $\beta ' = \maxroot{\shiftoper{\alpha} \deriv p}$,  
  and assume by way of contradiction that $\beta ' > \beta$.
If $p$ has at least two distinct roots, then we may apply Lemma~\ref{lem:pinch} to obtain
  polynomials $\ptil$ and $\phat$ with
\[
  \maxroot{\shiftoper{\alpha } \ptil} - \alpha = \maxroot{\shiftoper{\alpha } \phat} - \alpha
  = \beta .
\]
Observe that all of the roots of $\ptil$ have absolute value at most $R$.
We will obtain a contradiction by showing that $\maxroot{\shiftoper{\alpha} D \ptil} > \beta '$.

For $d \geq 3$, we use the inductive hypothesis
% and the fact that $\phat$ has at least two distinct roots 
 to conclude that
\[
  \maxroot{\shiftoper{\alpha} \deriv \phat} \leq  \beta ,
\]
and thus $(\shiftoper{\alpha} \deriv \phat) (\beta') > 0$.
As $\ptil = p - \phat$, this implies that $(\shiftoper{\alpha} \deriv \ptil) (\beta') < 0$,
  and so $\maxroot{\shiftoper{\alpha} \deriv \ptil} > \beta'$, a contradiction.
For the base case of $d = 2$, we observe that 
  $\phat$ has degree $1$ and so
  $\shiftoper{\alpha} \deriv \phat$
  merely equals the first coefficient of $\phat$.
As this coefficient is positive, we may again conclude that
  $(\shiftoper{\alpha} \deriv \phat) (\beta') > 0$, and thereby obtain a contradiction.
\end{proof}

Most of the work in the proof of Theorem~\ref{thm:sqsumTrans} is devoted to the case in which
  $p$ and $q$ have the same degree.
When their degrees are different, we use the following consequence of
  Theorem \ref{thm:symmetricAdditive} to simplify their symmetric additive
  convolution.

\begin{lemma}\label{lem:reduce_degree}
For $p \in \rrpoly{d}$ and $q \in \rrpoly{k}$ with $k < d$,
\[
p \sqsum_{d} q = \frac{1}{d}(\deriv p) \sqsum_{d-1} q.
\]
\end{lemma}
%\begin{proof}
%Noting that $q^{(d)}(0) = 0$, we merely compute
% \begin{align*}
% p \sqsum_{d} q
% &= \frac{1}{d!}\sum_{i=0}^d p^{(i)}(x)q^{(d-i)}(0)
% \\&=\frac{1}{d!}\sum_{i=1}^d p^{(i)}(x) q^{(d-i)}(0) 
% \\&=\frac{1}{d!}\sum_{i=0}^{d-1} p^{(i+1)}(x) q^{(d-i-1)}(0) 
% \\&= \frac{1}{d} p' \sqsum_{d-1} q
% \end{align*}
% and so the two have the same roots.
% \end{proof}


\begin{lemma}\label{lem:sqSumOne}
For $\alpha \geq 0$, $p = (x- \lambda)^{d}$ for some real $\lambda$ and $q \in \rrpoly{d}$, 
\[
  \maxroot{\shiftoper{\alpha} (p \sqsum_{d} q)}
 = 
  \maxroot{\shiftoper{\alpha} p} + 
  \maxroot{\shiftoper{\alpha} q} - \alpha d.
\]
\end{lemma}
\begin{proof}
From the definition \eqref{def:sqsum}, we know that $p (x) \sqsum_{d} q (x) = q (x - \lambda)$, and so 
\[
\maxroot{\shiftoper{\alpha} (p \sqsum_{d} q)} 
 = \lambda + \maxroot{\shiftoper{\alpha} q} .
\]
On the other hand, $\maxroot{\shiftoper{\alpha} p} = \lambda + \alpha d$.
\end{proof}

Our proof of Theorem~\ref{thm:sqsumTrans} will be very similar to our proof
  of Lemma \ref{lem:derivP}.

\begin{proof}[Proof of Theorem~\ref{thm:sqsumTrans}]
We will prove this by induction on $d$.
In the base case of $d = 1$ we observe that
\[
(x - \lambda) \sqsum_{1} (x- \mu) = (x - \lambda - \mu).
\]
This gives equality in \eqref{eqn:sqsumTrans}, as
\[
  \maxroot{\shiftoper{\alpha} (x - \lambda)} = \lambda + \alpha .
\]

If $d > k$, then by Lemma~\ref{lem:reduce_degree}, we have 
\begin{align*}
\maxroot{\shiftoper{\alpha} (p \sqsum_{d} q)}
& = \maxroot{\shiftoper{\alpha} (\deriv p \sqsum_{d-1} q)},
\\
&\leq \maxroot{\shiftoper{\alpha} \deriv p} + \maxroot{\shiftoper{\alpha} q} - (d-1)\alpha
& \text{(by induction)}
\\&\leq \maxroot{\shiftoper{\alpha}  p} + \maxroot{\shiftoper{\alpha} q}  - d\alpha
& \text{(by Lemma~\ref{lem:derivP})},
\end{align*}
as required.

We now consider the case in which $k = d$.
For a polynomial $p$ in $\rrpoly{d}$, define
\[
  \phi (p) = \maxroot{\shiftoper{\alpha} p} + \maxroot{\shiftoper{\alpha} q} - d \alpha - 
  \maxroot{\shiftoper{\alpha } (p \sqsum_{d} q)} .
\]
As before, we will prove that $\phi (p) \geq 0$ for all polynomials whose roots are in $[-R,R]$,
  for arbitrary large $R$.
So, let $R > 0$ and let $p$ be a polynomial in $\rrpoly{d}$ with roots in $[-R,R]$ that minimizes $\phi$.
If $p$ has just one root, then Lemma \ref{lem:sqSumOne} tells us that $\phi (p) = 0$.
Otherwise,
  let 
\[
\beta = \maxroot{\shiftoper{\alpha } p} + \maxroot{\shiftoper{\alpha} q} - d \alpha,
\quad \text{and} \quad 
\beta ' = \maxroot{\shiftoper{\alpha} (p \sqsum_{d} q)},
\]
 and assume by way of contradiction that $\beta' > \beta$.

We may apply Lemma~\ref{lem:pinch} to obtain
  polynomials $\ptil$ and $\phat$ with
\[
  \maxroot{\shiftoper{\alpha } \ptil} + \maxroot{\shiftoper{\alpha} q} - d\alpha
 = \maxroot{\shiftoper{\alpha } \phat} + \maxroot{\shiftoper{\alpha} q} - d\alpha
  = \beta .
\]
Observe that all of the roots of $\ptil$ have absolute value at most $R$.
We will obtain a contradiction by showing that $\maxroot{\shiftoper{\alpha} (\ptil \sqsum_{d} q)} > \beta '$.

By the inductive hypothesis, we know that
\[
  \maxroot{\shiftoper{\alpha} (\phat \sqsum_{d} q)} \leq  \beta,
\]
and thus $(\shiftoper{\alpha} (\phat \sqsum_{d} q)) (\beta') > 0$.
As $\ptil = p - \phat$, this implies that $(\shiftoper{\alpha} \ptil \sqsum_{d} q) (\beta') < 0$,
  and so $\maxroot{\shiftoper{\alpha} \ptil \sqsum_{d} q} > \beta'$, a contradiction.

\end{proof}


If one carries out the proof with a little more care, one can show that equality can only be achieved
  when $p$ has just one root or when $k = d$ and $q$ has just one root.  


\subsection{Symmetric multiplicative  convolution}\label{sec:multTrans}

We begin by considering the case in which $p = (x-\lambda)^{d}$.
We then have that
\[
\mtrans{p}{z} = \sum_{j \geq 1} (\lambda /z)^{j}
= 
\frac{\lambda}{z - \lambda}.
\]
Thus,
\[
\invmtrans{p}{w} = \frac{1+w}{w} \lambda ,
\]
and
\[
\strans{p}{w} = \lambda .
\]

\begin{lemma}\label{lem:multTransOne}
If $\lambda > 0$, $p (x) = (x-\lambda)^{d}$ and $q (x) \in \rrpos{d}$, then for all $w \geq 0$ 
\[
\strans{p \sqmult_{d} q}{w}
=
\strans{p}{w}
\strans{q}{w}.
 \]
\end{lemma}
\begin{proof}
For $p (x) = (x-\lambda)^{d}$, one may use either the definition \eqref{def:sqmult} or Theorem \ref{thm:symmetricMult}
  to compute
\[
  p (x) \sqmult_{d} q (x) = \lambda^{d} q (x/\lambda).
\]
As, $\mtrans{q (x/\lambda)}{\lambda z} = \mtrans{q (x)}{\lambda}$, 
\[
  \strans{p (x) \sqmult_{d} q (x)}{w}
 = \lambda \strans{q (x)}{w} .
\]
\end{proof}
With a little care, one can prove that this is the only case in which equality holds in Theorem~\ref{thm:multTransBound}.

The finite multiplicative convolution of polynomials of different degrees
  may be computed by taking the \textit{polar derivative with respect to 0} of the polynomial of higher degree.
We recall that the polar derivative at 0 of a polynomial $p$ of degree $d$ is given by
  $d p - x \deriv p$ (see \cite[p. 44]{Marden}).

\begin{lemma}\label{lem:multdegm1}
For $p (x) \in \rrpoly{d}$ and $q (x) \in \rrpoly{k}$, for $k < d$,
\[
  p (x) \sqmult_{d} q (x) = \frac{1}{d} (x \deriv  p (x) - d p (x)) \sqmult_{d-1} q (x).
\]
\end{lemma}
\begin{proof}
Follows from Theorem~\ref{thm:symmetricMult} by an elementary computation.
\end{proof}

Let $R$ be the operation on degree $d$ polynomials that maps $p (x)$ to $x^{d} p (1/x)$.
The polar derivative may be expressed in terms of $R$ by
\[
  d p - x \deriv p = R \deriv R p.
\]

\begin{claim}\label{clm:polarDeriv}
For $p = (x-\lambda)^{d}$,
\[
 x \deriv p -  d p = \lambda d (x- \lambda)^{d-1}.
\]
For $p \in \rrpos{d}$, $(x D - d)p \in \rrpos{d-1}$ and
\begin{equation}\label{eqn:polarDeriv}
  \maxroot{p} \geq \maxroot{x \deriv p - d p}.
\end{equation}
%with equality only when $p$ has exactly one root.
%Conversely if $p \in \rrpos{d}$ satisfies $d p (x) - \deriv p (x) = (x-\lambda)^{d-1}$,
%  then $p (x) = (x-\lambda )^{d-1} / (-\lambda d)$.
\end{claim}
\begin{proof}
The first part is a simple calculation.
Inequality \eqref{eqn:polarDeriv} follows from the fact that $p \in \rrpos{d}$ implies that $R p \in \rrpos{d}$
   and the fact that the roots of $\deriv R p$ interlace those of $R p$.
To see that $(x D - d)p \in \rrpos{d-1}$, it remains to check that the lead coefficient is positive.
\end{proof}


As we did with symmetric additive convolutions, we relate the
  $\widetilde{\mathcal{M}}$-transformation to the maximum root of a polynomial.
We have
\[
\mtrans{p}{z} = w
\quad \iff \quad 
\maxroot{\left(1 - \frac{x D}{d (w+1)} \right) p (x)} = 0.
\]
We therefore define the operator $\multoper{w}$ by
\[
  \multoper{w} p (x)= \left( 1 - \frac{x \deriv }{d (w+1)} \right) p (x),
\]
which gives
\[
\mtrans{p}{z} = w
\quad \iff \quad 
\maxroot{\multoper{w} p} = z.
\]
Note that the polar derivative is $d \multoper{0}$.

Our proof of Theorem \ref{thm:multTransBound} will also employ the following consequence
  of Lemma~\ref{lem:pinch}.

\begin{corollary}\label{cor:multPinch}
Let $w > 0$, $d \geq 2$, and let 
  $p (x) \in \rrpos{d}$ have at least two distinct roots.
Then there exist $\ptil \in \rrpos{d}$ and $\phat \in \rrpos{d-1}$
  so that 
  $p (x) = \phat (x) + \ptil (x)$,
  the largest root of $\ptil$ is at most the largest root of $p$, and
\[
\maxroot{\multoper{w} p}
=
\maxroot{\multoper{w} \ptil}
=
\maxroot{\multoper{w} \phat}.
\]
\end{corollary}
\begin{proof}
To derive this from Lemma \ref{lem:pinch}, let $t = \maxroot{\multoper{w} p}$
  and set
\[
\alpha = \frac{t D}{d (w+1)}.
\]
The polynomials $\ptil$ and $\phat$ constructed in Lemma \ref{lem:pinch} now
  satsify 
\[
\maxroot{\shiftoper{\alpha} \phat} = 
\maxroot{\shiftoper{\alpha} \ptil} = 
t
=
\maxroot{\multoper{w} \ptil} = 
\maxroot{\multoper{w} \phat}, 
\]
as desired.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{thm:multTransBound}]
As we have already shown that equality holds when one of $p$ or $q$ has just one root,
  we will henceforth assume that both have at least two distinct roots.
Under this assumption, we will prove that
\[
\maxroot{  \multoper{w} p \sqmult_{d} q}
\leq 
\frac{w}{1+w}
\maxroot{  \multoper{w} p }
\maxroot{  \multoper{w} q }.
\]
We will prove this by induction on the maximum degree of $p$ and $q$, which we call $d$.
The base case of $d = 1$ follows from Lemma \ref{lem:multTransOne}.

If the degree of $p$ is larger than the degree of $q$, then we may
  prove the hypothesis by
\begin{align*}
  \maxroot{\multoper{w}   (p \sqmult_{d} q)}
& =
 \maxroot{ (x \deriv  p (x) - d p (x)) \sqmult_{d-1} q (x)}
\quad \text{(by Lemma~\ref{lem:multdegm1})}
\\
& \leq 
\frac{w}{1+w}
\maxroot{  \multoper{w}  (x \deriv  p (x) - d p (x) ) }
\maxroot{  \multoper{w} q (x) }
\quad \text{(by induction)}
\\
& =
\frac{w}{1+w}
\maxroot{  (x \deriv  - d) \multoper{w} p (x) ) }
\maxroot{  \multoper{w} q (x) }
\quad \text{(as $\multoper{w}$ and $\multoper{0}$ commute)}
\\
& \leq 
\frac{w}{1+w}
\maxroot{  \multoper{w}  p (x) }
\maxroot{  \multoper{w} q (x) },
\end{align*}
by applying Claim~\ref{clm:polarDeriv} to
  $\multoper{w} p (x)$.
 

For polynomials $p \in \RRpos$, we define
\[
 \phi (p) \defeq 
\frac{w}{1+w}
\maxroot{  \multoper{w} p }
\maxroot{  \multoper{w} q }
-
\maxroot{  \multoper{w} p \sqmult_{d} q}.
\]
We will prove that $\phi (p) \geq 0$ for all polynomials $p \in \RRpos$.
%  with equality only when $p$ has exactly one root.
As before, we let $R$ be an arbitrary positive number and let $p$
  be a polynomial minimizing $\phi (p)$ over the space of degree $d$
  polynomials with roots in $[0,R]$.
If $p$ has just one real root, then we know from Lemma \ref{lem:multTransOne} that $\phi (p) = 0$.
If $p$ has two distinct roots, then we apply Corollary \ref{cor:multPinch} to obtain polynomials
  $\ptil$ and $\phat$
  with $\maxroot{\multoper{w} p} = \maxroot{\multoper{w} \ptil} = \maxroot{\multoper{w} \phat}$.
We define
\[
  \beta  = \frac{w}{1+w}
\maxroot{  \multoper{w} p }
\maxroot{  \multoper{w} q }
\quad \text{and} \quad 
\beta ' = \maxroot{  \multoper{w} (p \sqmult_{d} q)},
\]
and assume by way of contradiction that $\beta ' > \beta$.
By induction, we know that 
  $\maxroot{\multoper{w} (\phat \ \sqmult_{d} q)} \leq \beta$, and so
  $\multoper{w} (\phat \ \sqmult_{d} q) (\beta ') > 0$.
This implies that   $\multoper{w} (\ptil \ \sqmult_{d} q) (\beta ') < 0$,
  and thus   
  $\maxroot{\multoper{w} (\ptil \ \sqmult_{d} q)} > \beta'$.
As all of the roots of $\ptil$ are less than $R$, this contradicts the
  assumption that $p$ minimizes $\phi (p)$.
\end{proof}




\subsection{Asymmetric additive convolution}\label{sec:asymTrans}

The following is a restatement of Theorem \ref{thm:recsumTrans}.

\begin{theorem}\label{thm:rectConvBound}
Let $p (x)$ and $q (x)$ be in $\rrpos{d}$ for $d \geq 1$.
Then for all $\alpha \geq 0$,
\[
\maxroot{\shiftoper{\alpha} \subsquare (p \recsum_{d} q)}
\leq 
\maxroot{\shiftoper{\alpha} \subsquare p} + \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d,
\]
with equality only if $p$ or $q$ equals $x^{d}$.
\end{theorem}

We remark that if $q (x) = x^{d}$, then $p \recsum_{d} q = p$,
  and
\[
\shiftoper{\alpha} \subsquare q = \shiftoper{\alpha} x^{2d} = x^{2d-1} (x - 2 d \alpha),
\]
so
\[
\maxroot{\shiftoper{\alpha} \subsquare q} = 2 \alpha d.
\]
This is why the theorem holds with equality when $q (x) = x^{d}$.

The following lemma tells us that it suffices 
  to prove Theorem~\ref{thm:rectConvBound} in the case that $\alpha = 1$.

\begin{lemma}\label{lem:alpha1}
For a real-rooted polynomial $p (x)$,
\[
\maxroot{\shiftoper{\alpha} p (x)}
 = 
 \frac{1}{\alpha} \maxroot{\shiftoper{1} p (\alpha x)}.
\]
\end{lemma}
\begin{proof}
Let $q (x) = p (\alpha x)$, so
\[
  \shiftoper{1} q (x) = p (\alpha x) - \alpha p' (\alpha x).
\]
Let 
\[
w = \smax{\alpha}{p (x)} = \maxroot{\shiftoper{\alpha } p}
\quad \iff \quad p (w) - \alpha p' (w) = 0.
\]
Then,
\[
  (\shiftoper{1} q) (w/\alpha) = p (w) - \alpha p' (w) = 0.
\]
\end{proof}




Our proof of Theorem~\ref{thm:rectConvBound} will use the following lemma to pinch together roots
  of $p$ to reduce the analysis to a few special cases.

\begin{corollary}\label{cor:recPinch}
Let $\alpha > 0$, $d \geq 2$, and let 
  $p (x) \in \rrpos{d}$ have at least two distinct roots.
Then there exist $\ptil \in \rrpos{d}$ and $\phat \in \rrpos{d-1}$
  so that 
  $p (x) = \phat (x) + \ptil (x)$,
  the largest root of $\ptil$ is at most the largest root of $p$,
  $\phat$ has a root larger than $0$, and
\begin{equation}\label{eqn:recPinch}
\maxroot{\shiftoper{\alpha} \subsquare \ptil }
 = \maxroot{\shiftoper{\alpha} \subsquare  \phat }
 = \maxroot{\shiftoper{\alpha} \subsquare  p }
\end{equation}
\end{corollary}
\begin{proof}
Let $t = \maxroot{\shiftoper{\alpha } S p}$,
  so
\[
  \maxroot{(1 - 2 \alpha t D)p} = \sqrt{t}.
\]
Apply Lemma \ref{lem:pinch} with $2 \alpha t D$ in the place of $\alpha$
  to construct the polynomials $\ptil$ and $\phat$.
They satisfy
\[
\maxroot{\shiftoper{\alpha} \phat} = 
\maxroot{\shiftoper{\alpha} \ptil} = 
\sqrt{t},
\]
which implies \eqref{eqn:recPinch}.
\end{proof}


We will build up to the proof of Theorem \ref{thm:rectConvBound} by first handling three
  special cases:

\begin{itemize}
\item When $p (x) = (x-\lambda)^{d}$ and $q (x) = x^{d-1}$.   That is, we consider $\dxd (x-\lambda)^{d}$
  (Lemma \ref{lem:p1q0}).

\item When $p (x) \in \rrpos{d}$  and $q (x) = x^{d-1}$.
  That is, we consider $\dxd p (x)$
  (Lemma \ref{lem:pxq0}).

\item When $p (x) = (x-\lambda )^{d}$ and $q (x) = (x-\mu )^{d}$
  (Lemma \ref{lem:p1q1}).
\end{itemize}


As with the other convolutions, we may compute the asymetric additive convolution of two
  polynomials by first applying an operation to the polynomial of higher degree.
In this case it is $\dxd$, also known as the ``Laguerre Derivitive''.

\begin{lemma}\label{lem:rectConvDiffDegs}
Let $p \in \rrpos{d}$ and let $q \in \rrpos{k}$ for $k < d$.
Then,
\[
  p \recsum_{d} q = (1/d^{2}) (\dxd p) \recsum_{d-1} q.
\]
\end{lemma}
\begin{proof}
Follows from Theorem \ref{thm:asymmetricAdditive}.
\end{proof}

The following characterization of the Laguerre derivitive also follows
  from Theorem \ref{thm:asymmetricAdditive}.

\begin{claim}\label{clm:DxD}
If $q (x) = x^{d-1}$, then
\[
  p \recsum_{d} q = \deriv x \deriv p.
\]
\end{claim}

\begin{lemma}\label{lem:p1q0}
For $\alpha \geq  0$, $\lambda \geq 0$, $d \geq 2$ and $p (x) = (x-\lambda)^{d}$,
\[
\maxroot{\shiftoper{\alpha} \subsquare \dxd p}
\leq 
\maxroot{\shiftoper{\alpha} \subsquare p} - 2 \alpha ,
\]
with equality only if $\lambda = 0$.
\end{lemma}


\begin{proof}
By Lemma~\ref{lem:alpha1}, it suffices to consider the case of $\alpha = 1$.
As $\subsquare  p (x) = (x^{2} - \lambda)^{d}$,
\[
  \shiftoper{1 } \subsquare p (x) = (x^{2} - 2 \lambda  d - \lambda ) (x^{2} - \lambda)^{d-1}.
\]
So, the largest root of this polynomial is the largest root of 
\[
  r_{\lambda} (x) \defeq  (x^{2} - 2 \lambda d - \lambda ).
\]


We may also compute
\[
  \shiftoper{1 }  \subsquare \deriv x \deriv (x^{2}- \lambda)^{d}
= 
  q_{\lambda } (x) (x^{2} - \lambda)^{d-2},
\]
where
\[
  q_{\lambda} (x) \defeq d x^{4} - 2 d (d-1) x^{3}  - (d+1) \lambda x^{2} + 4 (d-1) \lambda x + \lambda^{2}.
\]

We now prove that
\[
 \maxroot{q_{\lambda }}  \leq \maxroot{r_{\lambda }} - 2,
\]
with equality only if $\lambda = 0$.

We first argue that $q_{\lambda} (x)$ is real rooted.
This follows from that fact that it is a factor of
  $\shiftoper{1} \subsquare \deriv x \deriv (x-\lambda)^{d}$.
For $\lambda \geq  0$
  all of the roots of $\deriv x \deriv (x-\lambda)^{d}$ are nonnegative, and so
  applying $\subsquare$ to it yields a polynomial with all real roots.

We now compute
\[
  \maxroot{r_{\lambda }} = d + \sqrt{d^{2} + \lambda}.
\]
Define
\[
  \mu_{\lambda} = d + \sqrt{d^{2} + \lambda} - 2.
\]
Elementary algebra gives
\[
  q_{\lambda } (\mu_{\lambda}) = 4 \lambda - 8 d \sqrt{d^{2} + \lambda} + 8 d^{2}
= 
  (2 d - 2 \sqrt{d^{2} + \lambda})^{2}.
\]
So, $q_{\lambda } (\mu_{\lambda}) \geq 0$,
  with equality only when $\lambda = 0$.
With just a little more work, we will show that $\mu_{\lambda}$ is an upper bound
  on the roots of $q_{\lambda }$ for all $\lambda$.

For $q_{\lambda }$ to have a root larger than $\mu_{\lambda}$, it would have to have two roots
  larger than $\mu_{\lambda}$.
When $\lambda = 0$, the polynomial $q_{\lambda }$ has one root at $\mu_{0}$ and a root at $0$
  with multiplicity $3$.
As $q_{\lambda }$ is real rooted for all $\lambda \geq 0$ and the roots of $q_{\lambda }$ are continuous functions
  of its coefficients, and thus of $\lambda$, we can conclude that for small $\lambda$ all but one of the roots
  of $q_{\lambda}$ must be near $0$.
Thus, for sufficiently small $\lambda$, $q_{\lambda}$ can have at most one root greater than $\mu_{\lambda}$, and so
  it must have none.
As the largest root of $q_{\lambda}$ and $\mu_{\lambda}$ are continuous function of $\lambda$, 
  $\maxroot{q_{\lambda}} > \mu_{\lambda}$ for all sufficiently  small $\lambda $.
As
  $q_{\lambda} (\mu_{\lambda}) > 0$ for all $\lambda  \geq 0$, we can conclude that
  $\maxroot{q_{\lambda}} > \mu_{\lambda}$ for all $\lambda \geq 0$.
\end{proof}


To see that Lemma~\ref{lem:p1q0} is equivalent Theorem~\ref{thm:rectConvBound} in the case of $q = x^{d-1}$,
  note that for $q (x) = x^{d-1}$,
\[
  \shiftoper{\alpha} \subsquare q (x) = \shiftoper{\alpha} q (x^{2}) = x^{2 (d-1)} - \alpha D x^{2 (d-1)}
  = x^{2d-3} (x - 2 (d-1) \alpha).
\]
The equivalence now follows from Claim~\ref{clm:DxD} and the fact that the 
  the largest root of this polynomial is $2 (d-1) \alpha$.


\begin{lemma}\label{lem:pxq0}
For $\alpha \geq  0$, $d \geq 2$ and $p \in \rrpos{d}$,
\[
\maxroot{\shiftoper{\alpha} \subsquare \dxd p}
\leq 
\maxroot{\shiftoper{\alpha} \subsquare p} - 2 \alpha,
\]
with equality only if $p (x) = x^{d}$.
\end{lemma}
\begin{proof}
For every $p \in \RRpos$, define
\[
  \phi (p) = 
\maxroot{\shiftoper{\alpha} \subsquare p}
- 
\maxroot{\shiftoper{\alpha} \subsquare \dxd p}
-
2 \alpha .
\]
We will show that $\phi (p) \geq 0$ for every polynomial $p \in  \RRpos$ of degree at least $2$,
   with equality only when $p = x^{d}$.

Our proof will be by induction on the degree of $p$.
For any $R > 0$, let $p$ be the polynomial in $\rrpos{d}$ having roots in
  $[0,R]$ that minimizes $\phi (p)$.
Since this set is compact, there is a polynomial $p$ at which the minimum is obtained.
If all the roots of $p$ are the same, then Lemma~\ref{lem:p1q0} implies that
  $\phi (p) \geq 0$, with equality only when all roots of $p$ are zero.
If $p$ has two distinct roots, then we apply Corollary~\ref{cor:recPinch} to obtain
  polynomials $\phat$ and $\ptil$.

Let 
\[
\beta = 
\maxroot{\shiftoper{\alpha} \subsquare  p}
-
2 \alpha 
=
\maxroot{\shiftoper{\alpha} \subsquare  \phat }
-
2 \alpha 
=
\maxroot{\shiftoper{\alpha} \subsquare  \ptil }
-
2 \alpha .
\]
Now, assume by way of contradiction that $\phi (p) \leq  0$.
This means that
\[
 \beta ' \defeq 
  \maxroot{\shiftoper{\alpha} \subsquare \dxd  p} \geq  \beta .
\]

If $d \geq 3$, then we may assume by induction that
$\phi (\phat) > 0$ and thus
\begin{equation}\label{eqn:p1q0}
  \shiftoper{\alpha} \subsquare \dxd \phat (\beta) > 0.
\end{equation}
If $d=2$, then $\phat$ has degree $1$ and so
  $\shiftoper{\alpha} \subsquare \dxd \phat$
  equals the lead coefficient of $\phat$,
  which also implies \eqref{eqn:p1q0}.


As $\ptil = p - \phat $, we may conclude that
\[
  \shiftoper{\alpha} \subsquare \dxd \ptil (\beta ')
=
  \shiftoper{\alpha} \subsquare \dxd p (\beta ')
-
  \shiftoper{\alpha} \subsquare \dxd \phat (\beta ')
=
-
  \shiftoper{\alpha} \subsquare \dxd \phat (\beta ')
< 0,
\]
and thus
\[
  \maxroot{\shiftoper{\alpha} \subsquare \dxd  \ptil } >  \beta' .
\]
But, this contracts the assumption that $p$ minimizes $\phi (p)$
  over polynomials in $\rrpos{d}$ with roots in $[0,R]$.
\end{proof}

In Section \ref{sec:cheby}, we establish the following special case of Theorem~\ref{thm:rectConvBound}.
\begin{lemma}\label{lem:p1q1}
For $\lambda, \mu > 0$, and $d \geq 1$, let $p (x) = (x - \lambda )^{d}$ and $q (x) = (x-\mu )^{d}$.
Then for all $\alpha \geq 0$,
\[
\maxroot{\shiftoper{\alpha} \subsquare (p \recsum_{d} q)}
<
\maxroot{\shiftoper{\alpha} \subsquare p} + \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d.
\]
\end{lemma}

We now use Lemma~\ref{lem:p1q1} to prove Theorem~\ref{thm:rectConvBound} through 
  a variation of the pinching argument employed in the proof of Lemma~\ref{lem:p1q0}.


\begin{proof}[Proof of Theorem~\ref{thm:rectConvBound}]
We will prove this by induction on the maximum degree of $p$ and $q$, which we call $d$.
Our base case of $d=1$ is handled by Lemma~\ref{lem:p1q1}.

Assume, without loss of generality, that the degree of $p$ is at least the degree of $q$.
If the degree of $p$ is larger than the degree of $q$, then we may
  prove the hypothesis by
\begin{align*}
  \maxroot{\shiftoper{\alpha} \subsquare  (p \recsum_{d} q)}
& =
  \maxroot{\shiftoper{\alpha} \subsquare  ((\dxd  p) \recsum_{d-1} q)}
\quad \text{(by Lemma~\ref{lem:rectConvDiffDegs})}
\\
& \leq \maxroot{\shiftoper{\alpha} \subsquare (\dxd p)} + \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha (d-1)
\quad \text{(by induction)}
\\
& \leq  \maxroot{\shiftoper{\alpha} \subsquare p} + \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d
\quad \text{(by Lemma~\ref{lem:p1q0})}.
\end{align*}
Lemma \ref{lem:p1q0} also tells us that equality is only achieved when $p = x^{d}$.

We now consider the case in which both $p$ and $q$ have degree $d$.
For polynomials $p$ and $q$ in $\rrpos{d}$, define
\[
  \phi (p,q) = 
 \maxroot{\shiftoper{\alpha} \subsquare p} + \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d
 -   \maxroot{\shiftoper{\alpha} \subsquare  (p \recsum_{d} q)}.
\]
We will prove that $\phi (p,q) \geq  0$ for all such polynomials,
  with equality only if one of them equals $x^{d}$.
For any $R > 0$, let $p$ and $q$ be the polynomials with all roots in $[0,R]$ that minimize $\phi (p,q)$.
Since the set of degree $d$ polynomials with roots in $[0,R]$ is compact, there exist polynomials $p$ and $q$
  on which the minimum is obtained.
If $p$ and $q$ each have only one root, then Lemma \ref{lem:p1q1} implies $\phi (p,q) \geq 0$,
    with equality only if one of them equals $x^{d}$.
If not, let $p$ have at least two distinct roots.
We may thus apply Corollary~\ref{cor:recPinch} to obtain
  polynomials $\phat$ and $\ptil$.

Let 
\begin{align*}
\beta 
& = 
\maxroot{\shiftoper{\alpha} \subsquare  p}
+ \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d
\\
& =
\maxroot{\shiftoper{\alpha} \subsquare  \phat }
+ \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d
\\
& =
\maxroot{\shiftoper{\alpha} \subsquare  \ptil }
+ \maxroot{\shiftoper{\alpha} \subsquare q} - 2 \alpha d
.
\end{align*}
Now, assume by way of contradiction that $\phi (p,q) \leq  0$.
This means that
\[
 \beta ' \defeq 
\maxroot{\shiftoper{\alpha} \subsquare  (p \recsum_{d} q)}
 \geq  \beta .
\]

For $d \geq 2$, we may assume by induction that
$\phi (\phat, q) > 0$ and thus
\begin{equation}\label{eqn:pxq0}
  (\shiftoper{\alpha} \subsquare (\phat  \recsum_{d} q)) (\beta) > 0.
\end{equation}

As $\ptil = p - \phat $, we may conclude that
\[
    (\shiftoper{\alpha} \subsquare (\ptil  \recsum_{d} q)) (\beta ')
=
    (\shiftoper{\alpha} \subsquare (p  \recsum_{d} q))(\beta ')
-
  (\shiftoper{\alpha} \subsquare (\phat  \recsum_{d} q)) (\beta ')
=
-
  (\shiftoper{\alpha} \subsquare (\phat  \recsum_{d} q)) (\beta ')
< 0,
\]
and thus
\[
  \maxroot{\shiftoper{\alpha} \subsquare \dxd  \ptil } >  \beta' .
\]
But, this contradicts the assumption that $p$ and $q$ minimize $\phi (p,q)$
  over polynomials with roots in $[0,R]$.


\end{proof}

\subsection{Chebyshev Polynomials}\label{sec:cheby}

This section is devoted to the proof of Lemma~\ref{lem:p1q1}.
For positive $\lambda$ and $\mu $, let
\[
  q^{\lambda , \mu}_{d} (x) = 
    (x-\lambda )^{d} \recsum_{d} (x-\mu )^{d}.
\]

Most of the work will be in the proof of the following lemma.
\begin{lemma}\label{lem:p1q1cauchy}
\[
  \cauchy{\subsquare q^{\lambda , \mu}_{d}}{t}
<
\frac{t}
{\sqrt{(t^{2} - (\lambda +\mu ))^{2} - 4 \lambda \mu }}.
\]
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem:p1q1}]
Compute
\[
  \shiftoper{\alpha /d} \subsquare (x-\lambda)^{d}
=
  \shiftoper{\alpha /d}  (x^{2}-\lambda)^{d}
=
  (x^{2} - \lambda)^{d-1} (x^{2} - \lambda - 2 \alpha x).
\]
So, the maximum root of this polynomial is the maximum root of
  $(x^{2} - \lambda - 2 \alpha x)$,
  which is 
\[
  \alpha + \sqrt{\alpha^{2} + \lambda}.
\]

Now, define
\[
t = \sqrt{\alpha^{2} + \lambda} + \sqrt{\alpha^{2} + \mu}.
\]
To prove Lemma \ref{lem:p1q1} it suffices to show that
  the maximum root of $\shiftoper{\alpha /d} \subsquare q_{d}^{\lambda , \mu}$
  is less than $t$,
 which follows
  from Lemma ~\ref{lem:p1q1cauchy}
  by computing
\[
2 d \cauchy{\subsquare q_{d}^{\lambda , \mu}}{t}
<
\frac{2 d t}
{\sqrt{(t^{2} - (\lambda +\mu ))^{2} - 4 \lambda \mu }}
= d/\alpha .
\]
\end{proof}


We will bound the Cauchy transform of $q_{d}^{\lambda ,\mu }$ by relating it to Chebyshev
  polynomials of the second kind, which we recall are defined by
\[
  U_{d} (x) = \sum_{k = 0}^{\floor{d/2}} (2x)^{d-2k} (-1)^{k} \binom{d-k}{k}.
\]

\begin{lemma}\label{lem:rectToCheby}
\[
q^{\lambda ,\mu}_{d} (x)   
= 
 (\lambda \mu)^{d/2}
U_{d} \left(\frac{x - (\lambda +\mu)}{2 \sqrt{\lambda \mu }} \right).
\]
\end{lemma}
\begin{proof}
The lemma is an immediate consequence of the following two identities, which we will now prove.
\begin{equation}\label{eqn:rectToCheby}
q^{1,1}_{d} (x) = U_{d} (x/2 - 1), 
\end{equation}
and
\begin{equation}\label{eqn:rectToRect11}
q_{d}^{\lambda ,\mu} (x) = (\lambda \mu)^{d/2} q_{d}^{1,1} \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} \right).
\end{equation}

We recall that the Chebyshev polynomials of the second kind may also be defined by the recurrence
\begin{align*}
  U_{0} (x) & = 1\\
  U_{1} (x) & = 2x\\
  U_{d} (x) & = 2x U_{d-1} (x) - U_{d-2} (x).
\end{align*}
We now develop an analogous recurrence for the polynomials $q^{\lambda , \mu}_{d} (x)$. 
We begin by using Theorem \ref{thm:asymmetricAdditive} to derive
\[
  q^{\lambda , \mu}_{d} (x)
=
  \sum_{k=0}^{d} x^{d-k} (-1)^{k} \sum_{i = 0}^{k} \binom{d-i}{k-i} \binom{d-k+i}{i} \lambda^{i} \mu^{k-i}.
\]
By examining the coefficients of $x^{d-k} \lambda^{i} \mu^{k-i}$ in this expression, we derive
\begin{align*}
  q^{\lambda , \mu }_{0} (x) & = 1\\
  q_{1}^{\lambda , \mu } (x) & = x - (\lambda +\mu )\\
  q_{d}^{\lambda , \mu } (x) & = x - (\lambda +\mu ) q^{\lambda , \mu }_{d-1} (x) - \lambda  \mu q^{\lambda , \mu }_{d-2} (x).
\end{align*}
We may now prove \eqref{eqn:rectToCheby} by a simple change of variables.
If we substitute $y = x/2 - 1$ and write the recurrence for $U_{d} (y)$, we obtain
  exactly the recurrences for $q^{1,1}_{d} (x)$.
It is particularly important to check that this holds for the degree 0 and 1 polynomials in the sequences.

We may similarly prove \eqref{eqn:rectToRect11} by induction.
The base case of degree 0 is trivial and for degree 1 we have
\[
\sqrt{\lambda \mu }  q^{1,1}_{1} \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} \right)
=
\sqrt{\lambda \mu } \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} - 2 \right)
= 
x - (\lambda +\mu).
\]
And, the recurrence for $q_{d}^{1,1}$ gives
\begin{align*}
\lefteqn{
(\lambda \mu )^{d/2}  q^{1,1}_{d} \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} \right)
}\\
& = 
(\lambda \mu )^{d/2} \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} - 2\right)
  q^{1,1}_{d-1} \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} \right)
 - 
(\lambda \mu )^{d/2}
  q^{1,1}_{d-2} \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} \right),
\\
& = 
\sqrt{\lambda \mu }  \left(\frac{x}{\sqrt{\lambda \mu}} - \frac{(\sqrt{\lambda} - \sqrt{\mu})^{2}}{\sqrt{\lambda \mu }} - 2\right)
  q^{\lambda , \mu }_{d-1} (x)
-
 (\lambda \mu) q^{\lambda , \mu }_{d-2} (x)
\qquad \text{(by induction)}
\\
& = 
(x - (\lambda + \mu))   q^{\lambda , \mu }_{d-1} (x)
-
 (\lambda \mu) q^{\lambda , \mu }_{d-2} (x).
\end{align*}
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:p1q1cauchy}]
Applying Lemma~\ref{lem:rectToCheby},
  we obtain
\begin{align*}
  \cauchy{\subsquare q_{d}^{\lambda , \mu}}{t}
& =
  \frac{1}{2d} \frac{\deriv \subsquare q_{d}^{\lambda , \mu }}{\subsquare q_{d}^{\lambda ,\mu }} (t)
\\
& = 
\frac{2 t}{2 d} 
\frac{\deriv q_{d}^{\lambda , \mu }}{q_{d}^{\lambda ,\mu }} (t^{2})
\\
& = 
\frac{t}{2 \sqrt{\lambda \mu} d } 
\frac{\deriv U_{d}}{U_{d}} ((t^{2} - (\lambda + \mu ))/ 2 \sqrt{\lambda \mu }).
\end{align*}
Theorem~\ref{thm:chebyBarrier} below tells us that
\[
\frac{1}{d} \frac{\deriv U_{d}}{U_{d}} (x)
<
\frac{1}{\sqrt{x^{2} - 1}}.
\]
Substituting this into the above equalities gives
\begin{align*}
  \cauchy{\subsquare q_{d}^{\lambda , \mu}}{t}
& <
\frac{t}{2 \sqrt{\lambda \mu} } 
\frac{1}{
  \sqrt{ ((t^{2} - (\lambda + \mu ))/ 2 \sqrt{\lambda \mu })^{2} - 1}
}
\\
& = 
\frac{t}{2 \sqrt{\lambda \mu} } 
\frac{1}{
  \sqrt{ (t^{2} - (\lambda + \mu ))^{2}/ 4 \lambda \mu  - 1 }
}
\\
& = 
\frac{t}{
 \sqrt{(t^{2} - (\lambda + \mu ))^{2}  - 4 \lambda \mu }
}.
\end{align*}
\end{proof}





\begin{theorem}\label{thm:chebyBarrier}
For $t \geq 1$,
\[
  \cauchy{U_{d}}{t} 
 < \frac{1}{\sqrt{t^{2}- 1}}.
\]
\end{theorem}

We will require a few standard facts about Chebyshev polynomials.
Let $T_{d}$ denote the degree $d$ Chebyshev polynomial of the first kind.

Recall that for $x \geq 1$,
\begin{align*}
  T_{d} (x) & = \cosh ((d+1) \acosh x) \\
  U_{d} (x) & = \frac{\sinh ((d+1) \acosh x)}{\sinh \acosh x},
\end{align*}
where
\begin{align*}
  \cosh (\theta )  = \frac{1}{2}\left(e^{x} + e^{-x} \right) , \quad 
  \sinh (\theta )  = \frac{1}{2}\left(e^{x} - e^{-x} \right) , \quad \text{ and } \quad 
  \sinh (\acosh x)  = \sqrt{x^{2} - 1}.
\end{align*}
We also recall that for $x \geq 1$, $\acosh x \geq 0$.


We also need the derivative of $U_{d}$:
\[
  U_{d}' (x) = \frac{1}{x^{2}-1} \left((d+1) T_{d+1} (x) - x U_{d} (x) \right).
\]




\begin{proof}[Proof of Theorem~\ref{thm:chebyBarrier}]
Using claim~\ref{clm:cheby2}, we compute

\begin{align*}
\cauchy{U_{d}}{x}
& =
\frac{1}{d}\frac{U_{d}' (x)}{U_{d} (x)}\\
& = 
\frac{1}{d} \frac{1}{x^{2}-1} \left((d+1) \frac{T_{d+1} (x)}{U_{d} (x)}  - x \right)
\\
&  <
\frac{1}{d}\frac{1}{x^{2}-1} \left((d+1) \left(\frac{d}{d+1} \sqrt{x^{2}-1} + \frac{1}{d+1} x \right) - x \right)
& \text{(by claim \ref{clm:cheby2}})
\\
& =
\frac{1}{d} \frac{1}{x^{2}-1} \left(d \sqrt{x^{2}-1} +  x - x \right)
\\
& =
\frac{1}{d} \frac{1}{x^{2}-1} \left(d \sqrt{x^{2}-1} \right)
\\
& = 
\frac{1}{\sqrt{x^{2}-1}}.
\end{align*}

\end{proof}

\begin{claim}\label{clm:cheby2}
For $x \geq  1$ and $d \geq 0$,
\[
  \frac{T_{d+1} (x)}{U_{d} (x)}
<
\frac{d}{d+1} \sqrt{x^{2}-1} + \frac{1}{d+1} x.
 \]
\end{claim}
\begin{proof}
For $\theta = \acosh x$, we have
\[
  \frac{T_{d+1} (x)}{U_{d} (x)}
=
  \coth ((d+1) \theta) \sinh (\theta ),
\]
where we recall that
\[
\coth ((d+1) \theta)
 = 
 \frac{1 + e^{-2 (d+1) \theta }}{1 - e^{-2 (d+1) \theta }}.
\]

By substituting $\alpha = 2 \theta$ and $t = 1/ (d+1)$
  into claim~\ref{clm:cheby1}, we learn that
\[
  \coth ((d+1) \theta)
 <
   \left(1 - \frac{1}{d+1} \right)
 + 
   \frac{1}{d+1} \coth \theta .
\]

So,
\begin{align*}
  \frac{T_{d+1} (x)}{U_{d} (x)}
 & <
  \left(   \left(1 - \frac{1}{d+1} \right)
 + 
   \frac{1}{d+1} \coth \theta 
  \right)     \sinh (\theta )
\\
 & = 
\left(1 - \frac{1}{d+1} \right) \sqrt{x^{2}- 1}
 +
 \frac{1}{d+1} x.
\end{align*}
\end{proof}



\begin{claim}\label{clm:cheby1}
For some $\alpha > 0$,
 let 
\[
F (t) = \frac{1+e^{-\alpha /t}}{1 - e^{-\alpha /t}}.
\]
For all $t \in (0,1)$,
\[
  F (t) < t F (1) + (1-t) F (0) = (1-t) + t F (1).
\]
\end{claim}
\begin{proof}
The above statement with ``$\leq $'' will follow from a demonstration
  that $F$ is convex on $(0,1)$.
The inequality is strict because $F$ is not linear.

The second derivative of $F$ with respect to $t$ is
\[
\frac{
\alpha e^{\alpha /t} (2 t + 2 (\alpha -t)e^{\alpha /t})
}{
t^{4} (e^{\alpha /t} - 1)^{3}.
}
\]
We need to show that this is positive for $t \in (0,1)$.
The only term that is not obviously positive is
\[
2 t + 2 (\alpha -t)e^{\alpha /t}.
\]
To show that this is positive, it suffices to show that
\[
  t e^{-\alpha /t} \geq t - \alpha .
\]
Dividing both sides by $t$, this becomes equivalent to
\[
  e^{-\alpha /t} \geq 1 - \alpha /t,
\]
which is true for all positive $\alpha$ and $t$.
\end{proof}







defs.tex
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{warning}[theorem]{Warning}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}


\newdimen\pIR
\pIR= -131072sp
\newcommand\StevesR{{\rm I\kern\pIR R}}
\def\Reals#1{\StevesR^{#1}}

\def\pleq{\preccurlyeq}
\def\pgeq{\succcurlyeq}

\def\acosh{\mathrm{acosh}}

\def\Span#1{\textbf{Span}\left(#1  \right)}
\def\bvec#1{{\mbox{\boldmath $#1$}}}


\def\prob#1#2{{\mathbb{P}}_{#1}\left[ #2 \right]}
\def\pvec#1#2{\vec{\mbox{P}}^{#1}\left[ #2 \right]}

\newcommand\symExpec{\operatorname{\mathbb{E}}\displaylimits}

\def\expec#1{\symExpec_{#1} }
\def\var#1{\mbox{\bf Var}\left[ #1 \right]}
\newcommand{\E}{\mathbb{E}}

\def\defeq{\stackrel{\mathrm{def}}{=}}
\def\setof#1{\left\{#1  \right\}}
\def\sizeof#1{\left|#1  \right|}




\def\floor#1{\left\lfloor #1 \right\rfloor}
\def\ceil#1{\left\lceil #1 \right\rceil}

\def\dim#1{\mathrm{dim} (#1)}
\def\sgn#1{\mathrm{sgn} (#1)}
\def\dist#1#2{\mathrm{dist} (#1, #2)}

\def\trace#1{\mathrm{Tr} \left(#1 \right)}
\def\trop{\mathrm{Tr }}


\def\union{\cup}
\def\intersect{\cap}
\def\Union{\bigcup}
\def\Intersect{\bigcap}


\def\form#1#2{\left\langle #1, #2\right\rangle}

\def\abs#1{\left|#1  \right|}


\def\norm#1{\left\| #1 \right\|}
\def\smallnorm#1{\| #1 \|}

\newcommand{\energy}[1]{\mathcal{E}\left(#1 \right)}


\def\biE{\overrightarrow{\mathrm{E}}}

\def\Reff{\mathrm{R_{eff}}}
\def\Ceff{\mathrm{C_{eff}}}

\def\calC{\mathcal{C}}
\def\calE{\mathcal{E}}
\def\calG{\mathcal{G}}
\def\calL{\mathcal{L}}
\def\calS{\mathcal{S}}
\def\calP{\mathcal{P}}



\newcommand\ddelta{\boldsymbol{\delta}}
\newcommand\Ppsi{\boldsymbol{\mathit{\Psi}}}
\newcommand\PPsi{\boldsymbol{\mathit{\Psi}}}
\newcommand\ppsi{\boldsymbol{\mathit{\psi}}}
\newcommand\pphi{\boldsymbol{\mathit{\phi}}}
\newcommand\Llambda{\boldsymbol{\mathit{\Lambda}}}
\newcommand\PPi{\boldsymbol{\Pi}}
\def\aa{\pmb{\mathit{a}}}
\newcommand\bb{\boldsymbol{\mathit{b}}}
\newcommand\cc{\boldsymbol{\mathit{c}}}
\newcommand\dd{\boldsymbol{\mathit{d}}}
\newcommand\ee{\boldsymbol{\mathit{e}}}
\newcommand\ff{\boldsymbol{\mathit{f}}}
\renewcommand\gg{\boldsymbol{\mathit{g}}}
\newcommand\ii{\boldsymbol{\mathit{i}}}
\newcommand\jj{\boldsymbol{\mathit{j}}}
\newcommand\kk{\boldsymbol{\mathit{k}}}
\renewcommand\ll{\boldsymbol{\mathit{l}}}
\newcommand\pp{\boldsymbol{\mathit{p}}}
\newcommand\qq{\boldsymbol{\mathit{q}}}
\newcommand\bs{\boldsymbol{\mathit{s}}}
\newcommand\nn{\boldsymbol{\mathit{n}}}
\newcommand\rr{\boldsymbol{\mathit{r}}}
\renewcommand\ss{\boldsymbol{\mathit{s}}}
\def\tt{\boldsymbol{\mathit{t}}}
\newcommand\uu{\boldsymbol{\mathit{u}}}
\newcommand\vv{\boldsymbol{\mathit{v}}}
\newcommand\ww{\boldsymbol{\mathit{w}}}
\newcommand\yy{\boldsymbol{\mathit{y}}}
\newcommand\zz{\boldsymbol{\mathit{z}}}
\newcommand\xx{\boldsymbol{\mathit{x}}}

\renewcommand\AA{\boldsymbol{\mathit{A}}}
\newcommand\BB{\boldsymbol{\mathit{B}}}
\newcommand\CC{\boldsymbol{\mathit{C}}}
\newcommand\DD{\boldsymbol{\mathit{D}}}
\newcommand\GG{\boldsymbol{\mathit{G}}}
\newcommand\II{\boldsymbol{\mathit{I}}}
\newcommand\JJ{\boldsymbol{\mathit{J}}}
\newcommand\KK{\boldsymbol{\mathit{K}}}
\newcommand\NN{\boldsymbol{\mathit{N}}}
\newcommand\MM{\boldsymbol{\mathit{M}}}
\newcommand\LL{\boldsymbol{\mathit{L}}}
\newcommand\RR{\boldsymbol{\mathit{R}}}
\renewcommand\SS{\boldsymbol{\mathit{S}}}
\newcommand\UU{\boldsymbol{\mathit{U}}}
\newcommand\WW{\boldsymbol{\mathit{W}}}
\newcommand\VV{\boldsymbol{\mathit{V}}}
\newcommand\XX{\boldsymbol{\mathit{X}}}
\newcommand\mm{\boldsymbol{\mathit{m}}}

\newcommand\ppi{\boldsymbol{\pi}}
\newcommand\cchi{\boldsymbol{\chi}}
\newcommand\aalpha{\boldsymbol{\alpha}}
\newcommand\bbeta{\boldsymbol{\beta}}
\newcommand\ggamma{\boldsymbol{\gamma}}

\newcommand\phat{{\widehat{{p}}}}
\newcommand\uhat{{\hat{{u}}}}
\newcommand\vhat{{\hat{{v}}}}
\newcommand\what{{\hat{{w}}}}
\newcommand\xhat{\boldsymbol{\hat{\mathit{x}}}}


\newcommand\ptil{{\widetilde{{p}}}}

\newcommand\Ghat{{\widehat{{G}}}}
\newcommand\LLhat{\boldsymbol{\mathit{\widehat{L}}}}

\newcommand\thetahat{{\hat{\theta }}}



\newcommand{\sym}[1]{\mathrm{sym} (#1)}

\def\Complex#1{\mathbb{C}^{#1}}

\newcommand{\imag}[1]{\mathsf{Im} (#1)}

\def\Branden{Br\"{a}nd\'{e}n}

\renewcommand{\H}{\mathcal{H}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}

\newcommand{\dan}[1]{}
\newcommand{\nikhil}[1]{}
\newcommand{\adam}[1]{}
%\newcommand{\dan}[1]{{\bf \color{blue} Dan: #1}}
%\newcommand{\nikhil}[1]{{\bf \color{green} Nikhil: #1}}
%\newcommand{\adam}[1]{{\bf \color{red} Adam: #1}}

\renewcommand{\H}{\mathcal{H}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\AND}{\quad \text{and} \quad}
\newcommand{\mydet}[1]{\det\left(#1\right)}
\newcommand{\mixed}[2]{\mu \left[#1 \right] \left(#2 \right)}



finiteConvMaster.tex
\documentclass[11pt]{article}
\usepackage{amsmath,amsfonts,amsthm,alltt,amssymb}
\textheight 8.5in
\topmargin -0.2in
\oddsidemargin 0.2in
\textwidth 6.3in
\allowdisplaybreaks[2]

\input{defs}

\input{freedefs}

%%%---------------------------------------------
%%%  begin document
%%%



\begin{document}

\title{
Finite free convolutions of polynomials
\thanks{
This research was partially supported by NSF grant CCF-1111257,
  an NSF Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS-0902962,
  a Simons Investigator Award to Daniel Spielman, and a MacArthur Fellowship.
}}

\author{
Adam Marcus\\
Crisply\\
Yale University\\
\and
Daniel A. Spielman \\ 
Yale University
\and 
Nikhil Srivastava\\
U. C. Berkeley
}


\maketitle

\begin{abstract}
We study three convolutions of polynomials that are inspired by free probability.
We define these to be the expected characteristic
  polynomials of certain random matrices.
The symmetric additive and multiplicative convolutions have been studied for a century.
The asymmetric additive convolution, and the connection of all of them with random matrices, appears new.
We prove that these convolutions produce real rooted polynomials and provide strong bounds
  on the locations of the roots of these polynomials.
\dan{Turn this off}
\end{abstract}


\tableofcontents


\input{introConvs}

\input{summary}

\input{formulas}

\input{realrooted}


\input{bounds}

\section{Conclusions}

This paper is part of an effort motivated by 
  the method of interlacing polynomials \cite{IF1,IF2}
  to better understand how operations that preserve the real rootedness
  of polynomial affect their roots.
In \cite{IF4} we use the results of this paper to demonstrate the existence of
  bipartite Ramanujan graphs of every number of vertices and every degree.

The are other interesting connections between the finite free convolutions of polynomials
  introduced here and the standard free probability.
For example, Guionnet and Shlyakhtenko have proved that in an appropriately taken limit,
  the inequalities in Theorems \ref{thm:sqsumTrans}, \ref{thm:recsumTrans} and \ref{thm:multTransBound}
  become equalities.
We are preparing a paper on this and other relations.

\bibliographystyle{alpha}
\bibliography{free}

%\appendix
%\section{List of Notation Used}



\end{document}

 



formulas.tex
\newcommand{\pol}[2]{\mathrm{Pol}_{#1}\left\{ #2 \right\}}
\newcommand{\func}[1]{f\left[ {#1} \right]}
\newcommand{\rst}[1]{R_{st}({#1})}
\newcommand{\rstt}{\rst{\theta}}
\newcommand{\e}{\mathsf{e}}
\newcommand{\disteq}{\stackrel{\mathrm{dist}}{=}}
\newcommand{\dil}[1]{\mathrm{dil}(#1)}
\newcommand{\ind}[1]{\mathbf{1}_{\{#1\}}}

\section{Convolution Formulas}
In this section, we will derive explicit formulas for the additive (both
symmetric and non-symmetric) and multiplicative convolutions of two polynomials
in terms of their coefficients. 

We denote the coefficient of $(-1)^{k} x^{d-k}$ of the characteric polynomial of a $d$-dimensional
  matrix $A$ by $\e_{k} (A)$, which we recall is the $k$th elementary symmetric function of
  the eigenvalues of $A$.
For a subsets $S, T \subseteq \setof{1, \dots , d}$, we write $A (S,T)$ for the submatrix of $A$
  indexed by rows in $S$ and columns in $T$.
We write $A (S,:)$ for the submatrix containing rows in $S$.
We recall that
\[
  \e_{k} (A)
=
  \sum_{|S|=k}\det(A(S,S)).
\]



\subsection{Multiplicative Convolution}
We establish Theorem \ref{thm:symmetricMult} by establishing the identity for each	 
  of the coefficients individually.

\begin{theorem} For $d\times d$ symmetric matrices $A$ and $B$ and random
	orthonormal $Q$:
$$ \E_Q\e_k(AQBQ^T)=\frac{\e_k(A)\e_k(B)}{\binom{d}{k}}.$$
\end{theorem}

\begin{proof}
We first show that we can assume without loss of generality that
  $A$ and $B$ are diagonal.
To see this, diagonalize these matrices as $A = U C U^{T}$
  and $B = V D V^{T}$ where $U$ and $V$ are orthonormal.
We then have that
\begin{align*}
\E_{Q} \det (x I - A Q B Q^{T})
& =
\E_{Q} \det (x I - U C U^{T} Q V D V^{T} Q^{T})
\\
& =
\E_{Q} \det (x I - C U^{T} Q V D V^{T} Q^{T} U)
\\
& =
\E_{Q} \det (x I - C Q D Q^{T}),
\end{align*}
as $U^{T} Q V$ is distributed according to the Haar mesure.

Assuming that $A$ and $B$ are diagonal, we compute
\begin{align*}
	\E_Q \e_k(AQBQ^T) &=  \E \sum_{|S|=k} \det(A(S,:)QBQ(S,:)^T)
	\\ &= \E_Q \sum_{|S|=k} \det(A(S,S)Q(S,:)BQ(S,:)^T)  \quad \text{since $A$ is diagonal}
	\\ &= \E_Q \sum_{|S|=k} \det(A(S,S))\det(Q(S,:)BQ(S,:)^T)
	\\ &= \E_Q\E_P \sum_{|S|=k}\det(A(S,S))\det((PQ)(S,:)B(PQ)(S,:)^T)
	\\&\quad\textrm{where $P$ is a random permutation matrix, since $PQ\disteq Q$}
	\\ &= \E_Q \E_P \sum_{|S|=k}\det(A(S,S))\det(P(S,:)QBQ^TP(S,:)^T)
	\\ &= \E_Q \left(\sum_{|S|=k}\det(A(S,S))\right)\left(\E_P \det(P(S,:)QBQ^TP(S,:)^T)\right) 
	\\ &\quad\textrm{since the distribution of $P(S,:)$ is independent of $S$} 
	\\ &= \E_Q \e_k(A)\left(\frac{1}{\binom{d}{k}}\sum_{|T|=k} \det((QBQ^T)(T,T)\right) 
	\\ &= \E_Q \frac{\e_k(A)\e_k(QBQ^T)}{\binom{d}{k}}
	\\ &= \frac{\e_k(A)\e_k(B)}{\binom{d}{k}}.
\end{align*}
\end{proof}



\subsection{Symmetric Additive Convolution}
We now prove Theorem \ref{thm:symmetricAdditive}
   by establishing it for each coefficient.

\begin{theorem}\label{thm:symmetricAdditiveCoeff}
If $A$ and $B$ are $d\times d$ symmetric matrices then
$$ \E_Q  \e_k(A+Q BQ ^T) = \sum_{i+j=k}
\frac{(d-i)!(d-j)!}{d!(d-k)!}\e_i(A)\e_j(B)$$
where $Q $ is a random orthogonormal matrix.
\end{theorem}

\begin{proof} 
Writing $A = U C U^{T}$
  and $B = V D V^{T}$
  where $C$ and $D$ are diagonal and $U$ and $V$ are orthonormal,
  we derive
\[
 \E_Q \e_k(A+Q BQ ^T) 
 =\E_Q \e_k(C+U^TQVDV^TQ^TU)
 =\E_Q \e_k(C+QDQ^T),
\]
since $U^{T} Q V$ is a random orthonormal matrix.
Thus, we may assume that $A$ and $B$ are diagonal.
Given this assumption, we let $e_{i}$ denote the elementary unit vector in direction $i$ and compute
\begin{align*}
 \E_Q \e_k(A+Q BQ ^T) 
 &= \E_Q e_k\left(\sum_{i\le d} a_ie_ie_i^T + \sum_{i\le d}b_i(Q e_i)(Q e_i)^T\right)
 \\&= \E_Q \sum_{S,T:|S|+|T|=k} \e_k\left(\sum_{i\in S} a_ie_ie_i^T+\sum_{i\in T} b_i(Q e_i)(Q e_i)^T\right)
 \\&=\E_Q \sum_{|S|+|T|=k} \e_k\left( M_{ST}(A(S,S)\oplus B(T,T))M_{ST}^T\right)
 \\&=\E_Q\sum_{|S|+|T|=k} \det(M_{ST}^TM_{ST}(A(S,S)\oplus B(T,T))
 \\&=\sum_{|S|+|T|=k} \det A(S,S)\det B(T,T)\cdot(\E_Q\det(M_{ST}^TM_{ST}))
\end{align*}
where $M_{ST}=[I(:,S)|(Q I)(:,T)]$ is $d\times k$ with columns $\{e_i\}_{i\in S}$ and
$\{Q e_i\}_{i\in T}$.

It now turns out that the expectation $\E_Q  \det(M_{ST}^TM_{ST})$ depends
only on $|S|=:i$ and $|T|=:j$. Fixing $S$ and $T$ and removing subscripts to ease notation,
we have
\begin{align*}
\E_Q \det(M^TM) &= \E_Q
\e_i(I(:,S)I(:,S)^T)\e_j(I(:,\overline{S})^TQI(:T)I(:,T)^TQ^TI(:,\overline{S}))
\\&=\E_Q \E_\Pi (1)\cdot\e_j(I(:,\overline{S})^T\Pi QI(:T)I(:,T)^TQ^T\Pi^T I(:,\overline{S}))
\\&\qquad\textrm{where $\Pi$ is a random permutation matrix, since $\Pi Q\disteq Q$}
\\&=\E_Q\E_R \e_j(I(:,R)^TQ(:,T)Q(:,T)^TI(R,:))
\\&\qquad\textrm{where $R$ is a uniformly random subset of $[d]$ of size
$|\overline{S}|=d-i$}
\\&=\E_Q\frac{1}{\binom{d}{d-i}}\sum_{|R|=d-i} \e_j(P(R,R))\quad\textrm{writing
$P = Q(:,T)Q(:,T)^T$}
\\&=\E_Q\frac{1}{\binom{d}{d-i}}\sum_{|R|=d-i}\sum_{W\subset R,|W|=j} \e_j(P(W,W)) 
\\&=\E_Q\frac{1}{\binom{d}{d-i}}\sum_{W\subset [d],|W|=j}\binom{d-j}{d-i-j} \e_j(P(W,W)) 
\\&\qquad\textrm{since each $W$ of size $j = k-i \le d-i$ appears
$\binom{d-j}{d-i-j}$ times}
\\&=\E_Q \frac{\binom{d-j}{d-i-j}}{\binom{d}{d-i}}\e_j(P)
\\&= \frac{\binom{d-j}{d-i-j}}{\binom{d}{d-i}}\cdot 1\quad\textrm{since $P$ is a
projection of rank $j$.}
\\&=\frac{(d-i)!(d-j)!}{d!(d-k)!}.
\end{align*}
Thus we may write the quantity of interest as
$$\sum_{i+j=k}\frac{(d-i)!(d-j)!}{d!(d-k)!}\sum_{|S|=i,|T|=j}\det(A(S,S))\det(B(T,T))
= \sum_{i+j=k}\frac{(d-i)!(d-j)!}{d!(d-k)!}\e_i(A)\e_j(B),$$
as desired.
\end{proof}

We remark that the above formula may also be obtained using the methods (based on
establishing rotational invariance) we use in the next section for the asymmetric
additive convolution.




\subsection{Asymmetric Additive Convolution}
Recall that the asymmetric additive convolution of the characteristic polynomials of matrices $A$ and
 $B$ is defined as:
$$ h[A,B](x) =  \E_{Q,R}\det(xI-(A+QBR^T)(A+QBR^T)^T)= p (x) \recsum_{d} q(x),$$
where the expectation is taken over random orthonormal matrices
  and 
$$ p(x) = \charp{AA^T}{x},\quad q(x)=\charp{BB^T}{x}.$$

In this section, we will derive the explicit formula: 
\begin{equation}\label{eqn:recformula} h[A,B](x)=\sum_{k=0}^d x^{d-k}(-1)^k
	\sum_{i+j=k}\left(\frac{(d-i)!(d-j)!}{d!(d-k)!}\right)^2\e_i(AA^T)\e_j(BB^T).\end{equation}
Observe that both sides of the equation are invariant under left and right
multiplication of $A$ and $B$ by orthonormal matrices, so by taking singular
value decompositions it suffices to prove it for the case when $A$ and $B$ are
diagonal. This will be accomplished in two steps. First, we will pass from random
orthonormal matrices to random signed permutations.
A signed permutation matrix is a matrix whose nonzero entries are $\pm 1$ that has
  exactly one nonzero entry in each row and column.
A uniform random signed permutation matrix may be obtained by multiplying a random diagonal
  with uniform $\pm 1$ entries by a uniform random permutation matrix.

Define
\[
 f[A,B](x) \defeq  \E_{P,S}\det(xI-(A+P B S^{T})(A+ P B S^{T})^{T}),
\]
where $P$ and $S$ are uniform random signed permutation matrices.

\begin{theorem}[Asymetric Additive Quadrature]\label{thm:recperms} 
For all $d$ dimensional square matrices $A$ and $B$,
\begin{equation}
\label{eqn:signedperms}
f[A,B] (x) = h [A,B] (x).
\end{equation}
\end{theorem}

This theorem establishes a quadrature result: it shows that the integral over the the orthonormal group
  may be computed by taking the expectation over a discrete subset of that group.
Using similar techniques, we may establish the following theorem.

\begin{theorem}[Symmetric Additive Quadrature] 
For all $d$ dimensional symmetric square matrices $A$ and $B$,
\begin{equation}
\expec{Q} \charp{A + Q B Q^{T}}{x}
=
\expec{P} \charp{A + P B P^{T}}{x},
\end{equation}
where the first expectation is over orthonormal matrices and the second is over signed permutation matrices.
\end{theorem}

Then, we will explicitly calculate the polynomial $f[A,B] (x)$ in the diagonal case.

\begin{theorem}\label{thm:recdiag} When $A$ and $B$ are diagonal,
	$$ f[A,B](x)=\sum_{k=0}^d x^{d-k}(-1)^k \sum_{i+j=k}
\left(\frac{(d-i)!(d-j)!}{(d-k)!d!}\right)^2 \e_i(AA^T)\e_j(BB^T).$$
\end{theorem}
The combination of Theorems \ref{thm:recperms} and \ref{thm:recdiag} immediately establishes
\eqref{eqn:recformula}.

\subsubsection{Quadrature}\label{subsec:quadrature}
Theorem \ref{thm:recperms} follows easily from the following lemma, which says
that $f$ is invariant under left and right multiplication of $A,B$ by orthonormal
matrices.
\begin{lemma}\label{lem:recinvar} For any $A,B$ and orthonormal $Q,R$: 
$$f[A,QBR^T] = f[A,B]$$
\end{lemma}
\begin{proof}[Proof of Theorem \ref{thm:recperms}]
\begin{align*} h[A,B] &= \E_{Q,R}\chi((A+QBR^T)(A+QBR^T)^T)
\\&= \E_{Q,R}\chi((A+PQBR^TS^T)(A+PQBR^TS^T)^T)\quad\text{for any fixed $P,S$}
\\&= \E_{Q,R}\E_{P,S}\chi((A+PQBR^TS^T)(A+PQBR^TS^T)^T)
\\&= \E_{Q,R} f[A,QBR^T]
	\\&= \E_{Q,R} f[A,B]\quad\text{by Lemma \ref{lem:recinvar}}
\\&= f[A,B].\end{align*}
\end{proof}

We prove Lemma \ref{lem:recinvar} by showing that it holds for orthonormal
matrices acting on two-dimensional coordinate subspaces, and then appealing to
the fact that such matrices generate all orthonormal matrices.
 For $s \neq t$, let $\rstt$ denote the $d\times d$ matrix whose nonzero entries are given by
\begin{enumerate}
\item $\rstt[s,s] = \rstt[t,t] = \cos(\theta)$
\item $\rstt[s,t] = -\rstt[t,s] = \sin(\theta)$
\item $\rstt[k,k] = 1$ for $k \neq s, t$
\end{enumerate}
The key observation is that any expected characteristic polynomial over a distribution
  that is invariant under a small subset of such rotations must be invariant under
  all of them.
\begin{lemma}\label{lem:rsttquad} Let $A,B$ be $d\times d$ matrices and let $s,t\in [d]$ be two distinct indices.
Let $P$ be a random matrix supported on $O(d)$ such that the distribution of $P$ is the same as the
distribution of $P\rst{j\pi/2}$ for $j=0,1,2,3$.  Then, for
every angle $\theta$, 
$$ \E_{P} \det(A+PBP^T) = \E_P \det(A+P\rstt B\rstt^T P^T).$$
\end{lemma}

\begin{proof}
The hypothesis tells us that
\begin{align*}
	4\cdot \E_P \det(A+P\rstt B\rstt^T P^T) 
	&= \E_P \sum_{j=0}^3 \det(A+P\rst{j\pi/2}\rstt B\rstt^T\rst{j\pi/2}^TP^T)
	\\&= \E_P \sum_{j=0}^3 \det(A+P\rst{j\pi/2+\theta}
	B\rst{j\pi/2+\theta}^TP^T)
	\\&= \E_P \sum_{j=0}^3
	\det(\rst{j\pi/2+\theta}^TP^TAP\rst{j\pi/2+\theta}+B)
	\\&= \E_P \sum_{j=0}^3\sum_{k=-2}^2 c^{P}_{k} e^{ki(j\pi/2+\theta)}
	\\&\quad\textrm{by Lemma \ref{lem:gt3}, for some $c^{P}_{k}$ depending on $P$}
	\\&= \E_P \sum_{k=-2}^2 c^{P}_{k} e^{ik\theta}\left(i^0+i^k+i^{2k}+i^{3k}\right)
	\\&= \E_P (4 c^{P}_0),
	\\&\qquad\textrm{since the inner sum vanishes for $|k|=1,2$.}
\end{align*}
Since this quantity is independent of $\theta$, we may take $\theta=0$ and the claim is proved.
\end{proof}
\begin{lemma}\label{lem:gt3}
Let $A, B$ be $d \times d$ matrices and let
\[
\mydet{\rstt A \rstt^T + B} = \sum_k c_k e^{i k\theta}
\]
Then $c_k = 0$ for $|k| \geq 3$.
\end{lemma}
\begin{proof}
Recall that all $2\times 2$ rotations may be diagonalized as
$$ R_{\theta}=\begin{bmatrix} \cos\theta &-\sin\theta \\ \sin\theta &
\cos\theta\end{bmatrix}=\ U \begin{bmatrix}e^{i\theta} & 0 \\ 0 & e^{-i\theta}\end{bmatrix}U^\dagger,$$
where 
$$ U=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ i & -i\end{bmatrix}$$
is independent of $\theta$. This implies that $\rstt =VDV^\dagger$ for diagonal $D$ containing $e^{i\theta}$ and $e^{-i\theta}$
in positions $s$ and $t$ and ones elsewhere, with $V$ independent of $\theta$. Thus, we see that
\begin{align*}
\mydet{\rstt A \rstt^T + B} &= \mydet{\rstt A+ B\rstt} 
			    \\&= \mydet{ VDV^\dagger A+BVDV^\dagger}
			\\&= \mydet{ DV^\dagger A V+V^\dagger BVD}
\end{align*}
Notice that the matrix $M=DV^\dagger AV+V^\dagger BVD$ depends linearly on $e^{i\theta},
e^{-i\theta}$, and that the $e^{i\theta}$ (resp. $e^{-i\theta}$) terms appear only in the $s$th
(resp. $t$th) row and column of $M$. Since each monomial in the expansion of the 
determinant contains at most one entry from each row and each column and
$e^{i\theta}\cdot e^{-i\theta}=1$, this
implies that no terms of degree higher than two in $e^{i\theta}$ or
$e^{-i\theta}$ appear.
\end{proof}

We are now in a position to complete the proof of Lemma \ref{lem:recinvar} and
thereby Theorem \ref{thm:recperms}.
\begin{proof}[Proof of Lemma \ref{lem:recinvar}]
Since each $Q,R$ is a product of a finite number of orthonormal matrices
acting on two-dimensional coordinate subspaces, it suffices to show that
$$f[A,\rstt D_{st}B] = f[A,B]=f[A,BD_{st}^T\rstt^T],$$
for every rotation $\rstt$ and diagonal reflection $D_{st}$ with
	$D(s,s)=\pm 1, D(t,t)=\pm 1$, and identity elsewhere.

We will show the first equality.
Since the distribution of $P$ is invariant under reflections, it is immediate
that
$$ f[A,D_{st}B]=f[A,B],$$
so replacing $B$ by $D_{st}B$ it suffices to show that
$$ f[A,\rstt B] = f[A,B]$$
for every $\theta$.
For any (not necessarily symmetric) $d\times d$ matrix $A$, let $\dil{A}$ denote
the symmetric $2d\times 2d$ matrix 
$$ \dil{A}=\begin{bmatrix} 0 & A \\ A^T & 0 \end{bmatrix},$$
and let $A\oplus B$ denote the $2d\times 2d$ block matrix
$$ \begin{bmatrix} A & 0 \\ 0 & B\end{bmatrix}.$$
Observe that
$$ f[A,B](x^2) = \E_{P,S}\det(x I-\dil{A}-(P\oplus S)\dil{B}(P\oplus S)^T).$$
whence
\begin{align*}
	f[A,\rstt B](x^2) 
	&= \E_{P,S}\det(x I - \dil{A} -(P\oplus S)\dil{\rstt B}(P\oplus S)^T)
	\\&= \E_{P,S}\det(x I - \dil{A} -(P\oplus S)(\rstt\oplus
	I)\dil{B}(\rstt \oplus I)^TP\oplus S)^T)
\end{align*}
For every fixed $S$, the random matrix $P\oplus S$ is invariant under
right multiplication by $\rst{j\pi/2}\oplus I$ for $j=0,1,2,3$, since these are
themselves signed permutation matrices. Thus, we may apply Lemma
\ref{lem:rsttquad} to conclude that for every $S$,
\begin{align*}
	&\E_{P}\det(x I - \dil{A} -(P\oplus S)(\rstt\oplus I)\dil{B}(\rstt \oplus I)^TP\oplus S)^T)
	\\&=\E_{P}\det(x I - \dil{A} -(P\oplus S)\dil{B}P\oplus
S)^T).\end{align*}
Taking expectations of both sides with respect to $S$ yields $f[A,\rstt
B]=f[A,B]$, as desired.

The argument for the other side is identical, except we consider $I\oplus \rstt$
instead of $\rstt \oplus I$.
\end{proof}

\subsubsection{Calculation for Diagonal Matrices}
\begin{proof}[Proof of Theorem \ref{thm:recdiag}]
	Let $(a_i)_{i\le n}$ and $(b_j)_{j\le n}$ be the diagonal entries of $A$ and $B$. Observe
	that $$ \chi((A+PBS^T)SS^T(A+PBS^T)^T)=\chi((AS+PB)(AS+PB)^T),$$
	so that
	$$f[A,B](x^2) = \E \det(xI-\dil{AS+PB}).$$
	
	Let $\sigma, \pi$ be the permutations
	corresponding to $S,P$, and let $[i\sigma(i)\gets a_i ]$ denote a matrix with entry $a_i$ in position
	$i\sigma(i)$ and zeros elsewhere.
	Then the nonzero entries of $M=AS+PB$ are given by $[i\sigma(i)\gets
	\epsilon_i a_{i}] + [\pi(j)j\gets \xi_{j} b_{j}]$, where and the signs $\epsilon_i,
	\xi_j\in \pm 1$ are chosen independently. In particular,
	each entry of $M$ has mean zero. 

Thus, if we expand $\det(xI-\dil{M})$
	in permutations {\em for any fixed $\sigma,\pi$}, the only terms that survive
	are the involutions, which correspond to bipartite matchings in the
	support of $\dil{M}$, i.e., pairings of entries from the upper right and
	lower left blocks of $\dil{M}$ (see the appendix of \cite{IF1} for the
	simple calculation).
Indexing\footnote{In what follows, it is good to think of the matrix $M$ as a directed bipartite
	graph in which the left nodes are indexed by the entries $a_i$, the right
	nodes are indexed by the $b_j$, and the entries of $M$ are given by
	rightward edges labeled by  $a_{i\sigma(i)}$ and leftward edges labeled by $b_{\pi(j)j}$.}
	such $k$-matchings of the
	entries by bijections $\rho:S\rightarrow T$, where $S,T$ are $k$-subsets of the rows and
	columns of $M$, we have for fixed every fixed $\sigma,\pi$:
\begin{align*}
	\E_{\epsilon,\xi} \det(xI-\dil{M}) 
	&= \sum_{k=0}^{d} (-1)^k x^{2d-2k} \sum_{S,T\in\binom{[d]}{k}}
\sum_{\rho:S\rightarrow T} \E_{\epsilon,\xi} \prod_{j\in S} M_{i\rho(i)}^2.\end{align*}
In particular, the coefficient of $x^{2d-2k}$ is:
\begin{align*}
	&\sum_{S,T\in\binom{[d]}{k}}
	\sum_{\rho:S\rightarrow T} \E_{\epsilon,\xi}\prod_{i\in S}
	( \epsilon_{i}a_{i}\ind{\rho(i)=\sigma(i)}
	+\xi_{\rho(i)}b_{\rho(i)}\ind{\pi\rho(i)=i})^2
	\\ &= \sum_{S,T\in\binom{[d]}{k}}
	\sum_{\rho:S\rightarrow T} \prod_{i\in S}
	( a_{i}^2\ind{\rho(i)=\sigma(i)} +b_{\rho(i)}^2\ind{\pi\rho(i)=i})
	\\ &\quad\textrm{since the cross terms vanish because of the independent mean zero signs.}
	\\&= \sum_{S,T\in\binom{[d]}{k}}
	\sum_{\rho:S\rightarrow T} \sum_{R\subset S}
	\left(\prod_{i\in R}
	a_i^2\ind{\rho(i)=\sigma(i)}\right)\left(\prod_{i\in S\setminus R}
	b_{\rho(i)}^2 \ind{\pi\rho(i)=i}\right).
\end{align*}
We now calculate the expectation of this with respect to $\sigma,\pi$. The key
point is that the events $\{\ind{\rho(i)=\sigma(i)}\}_{i\in R}$ and the events
$\{\ind{\pi\rho(i)=i}\}_{i\in S\setminus R}$ are independent because $\sigma$
and $\pi$ are independent and $\rho(R)$ is disjoint from $\rho(S\setminus R)$.
Thus, the expectation over $\sigma,\pi$ is given by:
\begin{align*}
	&\sum_{S,T\in\binom{[d]}{k}}
	\sum_{\rho:S\rightarrow T} \sum_{R\subset S}
	\left(\E_\sigma\prod_{i\in R}
	a_i^2\ind{\rho(i)=\sigma(i)}\right)\left(\E_\pi\prod_{i\in S\setminus R}
	b_{\rho(i)}^2 \ind{\pi\rho(i)=i}\right)
	\\&= \sum_{S,T\in\binom{[d]}{k}}
	\sum_{\rho:S\rightarrow T} \sum_{R\subset S}
	\left(\prod_{i\in R}
	a_i^2\right)\left(\E_\sigma\prod_{i\in R}\ind{\rho(i)=\sigma(i)}\right)\left(\prod_{i\in S\setminus R}
	b_{\rho(i)}^2\right)\left(\E_\pi\prod_{i\in S\setminus R} \ind{\pi\rho(i)=i}\right)
\end{align*}
Observe that 
$$\E_\sigma\prod_{i\in R}\ind{\rho(i)=\sigma(i)}=\frac{(d-|R|)!}{d!}$$
only depends on the size of $R$, and similarly
$$\E_\pi\prod_{i\in S\setminus R} \ind{\pi\rho(i)=i} = \frac{(d-|S\setminus R|)!}{d!}.$$
Thus, the expectation of interest simplifies to:
\begin{align*} 
	&\sum_{S,T\in\binom{[d]}{k}}
	\sum_{\rho:S\rightarrow T} \sum_{R\subset S}
	\left(\prod_{i\in R} a_i^2\right)\left(\prod_{i\in S\setminus R} b_{\rho(i)}^2\right)
	\frac{(d-|R|)!}{d!} \frac{(d-|S\setminus R|)!}{d!}
	\\&= \sum_{S,T\in\binom{[d]}{k}} \sum_{\substack{R\subset S\\ Z\subset T\\|R|+|Z|=k}}\sum_{\substack{\rho:S\rightarrow T \\ \rho(S\setminus R)=Z}} 
	(a_i^2)^R(b_{j}^2)^{Z} \frac{(d-|R|)!}{d!} \frac{(d-|Z|)!}{d!},
	\\&\quad\textrm{where we have written $Z=\rho(S\setminus R)$ and $(a_i)^S:=\prod_{i\in S}a_i$ 
		 to ease notation}
	\\&= \sum_{S,T\in\binom{[d]}{k}} \sum_{\substack{R\subset S\\ Z\subset T\\|R|+|Z|=k}} 
	 (a_i^2)^R(b_{j}^2)^{Z} \cdot (|R|)! (|Z|)! \cdot \frac{(d-|R|)!}{d!} \frac{(d-|Z|)!}{d!}
 \end{align*}
 \begin{align*}
	 &=\sum_{r+z=k}\frac{r!z!(d-r)!(d-z)!}{(d!)^2}\sum_{\substack{|R|=r\\|Z|=z}}
	 \sum_{\substack{S\supset R\\ T\supset Z}}(a_i^2)^R(b_j^2)^Z
	 \\&=\sum_{r+z=k}\frac{r!z!(d-r)!(d-z)!}{(d!)^2}\sum_{\substack{|R|=r\\|Z|=z}}
	 \binom{d-r}{k-r}\binom{d-z}{k-z}(a_i^2)^R(b_j^2)^Z
	 \\&=\sum_{r+z=k}\frac{r!z!(d-r)!(d-z)!}{(d!)^2}\frac{(d-r)!}{(d-k)!(k-r)!}\frac{(d-z)!}{(d-k)!(k-z)!}
	 \sum_{\substack{|R|=r\\|Z|=z}}
	 (a_i^2)^R(b_j^2)^Z
	 \\&=\sum_{r+z=k}\left(\frac{(d-r)!(d-z)!}{(d-k)!d!}\right)^2\e_r(AA^T)\e_z(BB^T),
\end{align*}
as desired.
\end{proof}

freedefs.tex

%%%------------------------------------------
%%%  Defs just for free probability stuff
%%%


\newcommand{\smax}[2]{#1\text{--}\mathsf{max}\left(#2 \right)}
\newcommand{\maxroot}[1]{\mathsf{maxroot} \left(#1 \right)}

\usepackage{tikz,amstext}


\newcommand*\myrect[1]{%
  \begin{tikzpicture}
    \node[draw,rectangle,inner sep=0pt] {#1};
  \end{tikzpicture}}

\newcommand{\sqsum}{\mathbin{\text{\myrect{\textnormal{+}}}}}
\newcommand{\recsum}{\mathbin{\textnormal{\myrect{++}}}}
\newcommand{\sqmult}{\mathbin{\textnormal{\myrect{$\times$}}}}
\newcommand{\cauchy}[2]{\mathcal{G}_{#1} \left(#2 \right)}
\newcommand{\invcauchy}[2]{\mathcal{K}_{#1} \left(#2 \right)}
\newcommand{\rtrans}[2]{\mathcal{R}_{#1} \left(#2 \right)}
\newcommand{\reccauchy}[2]{\mathcal{B}_{#1} \left(#2 \right)}
\newcommand{\invreccauchy}[2]{\mathcal{F}_{#1} \left(#2 \right)}
\newcommand{\rectrans}[2]{\mathcal{T}_{#1} \left(#2 \right)}
\newcommand{\strans}[2]{\widetilde{\mathcal{S}}_{#1} \left(#2 \right)}
\newcommand{\mtrans}[2]{\widetilde{\mathcal{M}}_{#1} \left(#2 \right)}
\newcommand{\invmtrans}[2]{\widetilde{\mathcal{M}}^{(-1)}_{#1} \left(#2 \right)}


\newcommand{\subsquare}{\mathbb{S}}
\newcommand{\deriv}{D}
\newcommand{\dxd}{\deriv x \deriv}
\newcommand{\shiftoper}[1]{U_{#1}}

\newcommand{\multoper}[1]{V_{#1}}


\newcommand{\rrpoly}[1]{\mathbb{P} (#1)}
\newcommand{\RRpoly}{\mathbb{P}}
\newcommand{\rrpos}[1]{\mathbb{P}^{+} (#1)}
\newcommand{\RRpos}{\mathbb{P}^{+}}
\newcommand{\rrneg}[1]{\mathbb{P}^{-} (#1)}
\newcommand{\RRneg}{\mathbb{P}^{-}}

\newcommand{\charp}[2]{\chi_{#2} \left(#1 \right)}

introConvs.tex
\section{Introduction}

We study three convolutions on polynomials that are inspired by free probability.
Instead of capturing the distributions of eigenvalues of random matrices, these capture the expected characteristic
  polynomials of random matrices.
Two of the convolutions have been clasically studied.
The third, and the connection of all of them with random matrices, appears new.

For a matrix $M$, we define 
\[
\charp{M}{x} = \det (xI - M)
\]
to be the characteristic polynomial of the matrix $M$ in the variable $x$.

The convolutions we study may be defined in terms of integrals over the group of orthonormal matrices.
For $d$-dimensional symmetric matrices  $A$ and $B$  with characteristic polynomials $p$ and $q$,
  we define the \textit{symmetric additive convolution} of $p$ and $q$ to be
\begin{equation}\label{def:sqsum}
  p (x) \sqsum_{d} q (x) = \expec{Q} \charp{A + Q B Q^{T}}{x},
\end{equation}
where the expectation is taken over orthonormal matrices $Q$ sampled according to the Haar measure.

When $A$ and $B$ are positive semidefinite, we define
  we define the \textit{symmetric multiplicative convolution} of $p$ and $q$ to be
\begin{equation}\label{def:sqmult}
  p (x) \sqmult_{d} q (x) = \expec{Q} \charp{A Q B Q^{T}}{x},
\end{equation}
where the expectation is taken over random orthonormal matrices $Q$ sampled according to the Haar measure.

For arbitrary $d$-dimensional square matrices $A$ and $B$ that are not necessarily symmetric
  such that $A A^{T}$ and $B B^{T}$ have characteristic polynomials $p$ and $q$,
  we define the \textit{asymmetric multiplicative convolution} of $p$ and $q$ to be
\[
  p (x) \recsum_{d} q (x) = \expec{R,Q} \charp{(A + R B Q) (A + R B Q)^{T}}{x},
\]
where the expectation is taken over random orthonormal matrices $R$ and $Q$ sampled according to the Haar measure.

We derive expressions for these expected characteristic polynomials,
  prove that all of the resulting polynomials are real rooted, and
  prove bounds on the locations of their roots.

Free probability theory (see \cite{voiculescu1997free,nica2006lectures,anderson2010introduction}
  considers the limits for large matrices of the moments eigenvalues of matrices such as those above.
For each operation, free probability provides a transform of the moments of the eigenvalues of the individual
  matrices from which one can easily derive the transform of the moments of the eigenvalues of the resulting matrices.
We show that for our ``finite free convolutions'' these transforms provide upper bounds on the roots of the resulting
  polynomials.
For the symmetric additive convolution, this transform is equivalent to the barrier function
  studied in \cite{BSS,IF2}.
In \cite{IF4}, we use the result of the present paper to prove the existence of
  bipartite Ramanujan graphs of every number of vertices.



notation.tex

\begin{tabular}{l | l | l}
Notation & Latex & Meaning\\
\hline
$\sqsum $ & \texttt{\textbackslash sqsum}  & additive symmetric (square) convolution
\\
$\recsum $ & \texttt{\textbackslash recsum}  & additive asymmetric  (rectangular) convolution
\\
$\sqmult$ &  \texttt{\textbackslash sqmult}  & multiplicative convolution
\\
$\charp{x}{M}$ & \texttt{\textbackslash charp\{x\}\{M\}}
& characteristic poly of $M$ in $x$ \\
$\cauchy{p}{x}$ & \texttt{\textbackslash cauchy\{p\}\{x\}} & the Cauchy/Stieltjes transform\\
$\invcauchy{p}{x}$ & \texttt{\textbackslash invcauchy\{p\}\{x\}} & the inverse Cauchy/Stieltjes transform (not sure I like $\mathcal{G}$)\\
$\rtrans{p}{x}$  & \texttt{\textbackslash rtrans\{p\}\{x\}} & the Voiculescu R-transform\\
$\reccauchy{p}{x}$ & \texttt{\textbackslash reccauchy\{p\}\{x\}} & analog of Cauchy for rectangular (nonstandard)\\
$\invreccauchy{p}{x}$ & \texttt{\textbackslash invreccauchy\{p\}\{x\}} & analog of inverse Cauchy for asymmetric (nonstandard)\\
$\rectrans{p}{x}$  & \texttt{\textbackslash rectrans\{p\}\{x\}} & analog of  R-transform for rectangular (nonstandard)\\
$\subsquare$ & \texttt{\textbackslash subsquare} & $\subsquare p (x) = p (x^{2})$\\
$\deriv$ & \texttt{\textbackslash deriv} & the derivative\\
$\shiftoper{t}$ & \texttt{\textbackslash shiftoper\{t\}} & the operator $I - t D$\\
$\maxroot{p}$ & \texttt{\textbackslash maxroot\{p\}} & the largest root of the polynomial\\
$\rrpoly{d}$ & \texttt{\textbackslash rrpoly\{d\}} & real rooted polynomials of degree $d$, positive leading coefficient\\
$\rrpos{d}$ & \texttt{\textbackslash rrpos\{d\}} & nonnegative rooted polynomials of degree $d$, positive leading coefficient\\
\end{tabular}


realrooted.tex
\section{Real Rootedness of the Asymmetric Additive Convolution}\label{sec:rr}

We will use the theory of stable polynomials to prove Theorem \ref{thm:asymAdditiveRR}.
For this theorem, we will require Hurwitz stable polynomials.
We recall that a  multivariate polynomial
   $p (z_{1}, \dots , z_{m}) \in \Reals{}[z_{1}, \dots , z_{m}]$
  is \textit{Hurwitz stable} if it
   is identically zero or if whenever the real part of $z_{i}$ is positive for all $i$,
  $p (z_{1}, \dots , z_{m}) \not = 0$.

Instead of proving Theorem \ref{thm:asymAdditiveRR} directly, we prove the following theorem
  from which it follows.

\begin{theorem}\label{thm:asymNegRR}
Let
\[
  p (x) = \sum_{i=0}^{d} x^{d-i} a_{i}
\quad \text{and} \quad 
  q (x) = \sum_{i=0}^{d} x^{d-i} b_{i}
\]
have only nonpositive real roots.
Then,
\[
  r (x) 
 \defeq 
 \sum_{k=0}^{d} x^{d-k} \sum_{i+j = k}
 \left(\frac{(d-i)! (d-j)!}{d! (d-i-j)!} \right)^{2}   a_{i} b_{j}
\]
is also in $\rrneg{d}$.
\end{theorem}

We will use the following result to prove that a polynomial is in $\RRneg$.

\begin{lemma}\label{lem:rrneg}
Let $r (x)$ be a polynomial such that 
  $h (x,y) = r (xy)$ is Hurwitz stable.
Then, $r \in \RRneg$.
\end{lemma}
\begin{proof}
Let $\zeta $ be any root of $r$.
If $\zeta$ is neither zero or negative, then it has a square root with positive real part.
Setting both $x$ and $y$ to this square root would contradict the Hurwitz stability of $h$.
\end{proof}

We will prove that $p \recsum_{d} q$ is in $\RRneg$
  by constructing a Hurwitz stable polynomial and applying Lemma \ref{lem:rrneg}.
To this end, we need a few tools for constructing Hurwitz stable polynomials.

The first is elementary.
\begin{claim}\label{clm:pxy}
If $p (x) \in \RRneg$, then the polynomial $f (x,y) = p (xy)$ is Hurwitz stable.
\end{claim}
\begin{proof}
If both $x$ and $y$ have positive real part, then $xy$
  cannot be a nonpositive real, and thus cannot be a root of $p$.
\end{proof}


The second is essentially a result of Borcea and \Branden.
It's proof is identical to that of Proposition 3.4 in \cite{BBLeeYang1}.
\dan{Can we find some place where this is actually stated and proved?}
\begin{proposition}[Polarization]\label{pro:bbpolarization}
Let 
\[
p (x,y) = \sum_{i=0}^{d}\sum_{j=0}^{d} c_{i,j} x^{i} y^{j}
\]
be a Hurwitz stable polynomial.
Let for each integer $i$, let $\sigma_{i}^{x}$ be the $i$th elementary symmetric
  polynomial in the variables $x_{1}, \dots , x_{d}$, and let $\sigma_{i}^{y}$
  be the corresponding polynomial in $y_{1}, \dots , y_{d}$.
Then, the polynomial
\[
  P (x_{1}, \dots , x_{d}, y_{1}, \dots , y_{d})
\defeq 
\sum_{i=0}^{d}\sum_{j=0}^{d} c_{i,j} 
\frac{\sigma_{i}^{x} \sigma_{j}^{y}}{\binom{d}{i} \binom{d}{j}}
\]
is Hurwitz stable.
\end{proposition}
The polynomial $P$ is called the \textit{polarization} of $p$.
We remark that $P (x, \dots ,x, y, \dots , y) = p (x,y)$. 


The last result we need is due to  Lieb and Sokal \cite{LiebSokal} (see also \cite[Theorem 8.4]{borceaBrandenLeeYang2}).
\begin{theorem}\label{thm:diffoper}
Let $P (z_{1}, \dots , z_{d})$ and $Q (z_{1}, \dots , z_{d})$ be Hurwitz stable polynomials.
Let $\deriv_{i}^{z}$ denote the derivative with respect to $z_{i}$.
Then,
\[
  Q (\deriv_{1}^{z}, \dots , \deriv_{d}^{z}) P (z_{1}, \dots , z_{d})
\]
is Hurwitz stable.
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm:asymNegRR}]
Define $f (x,y) = p (xy)$ and $g (x,y) = (xy)^{d} q (1/xy)$.
Let $F (x_{1}, \dotsc , x_{d}, y_{1}, \dotsc , y_{d})$
  be the polarization of $f (x,y)$ in the variables
  $x_{1}, \dots , x_{d}, y_{1}, \dots , y_{d}$.
Let $G (x_{1}, \dots , x_{d}, y_{1}, \dots , y_{d})$ be the analogous polarization of $g (x,y)$.

Let $\sigma_{i}^{x}$ be the $i$th elementary symmetric function in
  $x_{1}, \dotsc , x_{d}$, and let $\delta_{i}^{x}$ be the $i$th
  elementary symmetric function in $D^{x}_{1}, \dotsc , D^{x}_{d}$.
Define $\sigma_{i}^{y}$ and $\delta_{i}^{y}$ analogously.

Then,
\[
  F (x_{1}, \dotsc , x_{d}, y_{1}, \dots , y_{d})
  = 
  \sum_{i=0}^{d}  a_{i} 
  \frac{\sigma_{d-i}^{x} \sigma_{d-i}^{y} }{\binom{d}{i}^{2}},
\]
and
\[
  G (D^{x}_{1}, \dotsc , D^{x}_{d}, D^{y}_{1}, \dotsc , D^{y}_{d)}
  = 
  \sum_{i=0}^{d}  b_{i} 
  \frac{\delta_{i}^{x}  \delta_{i}^{y} }{\binom{d}{i}^{2}}.
\]
Define 
\[
H (x_{1}, \dotsc , x_{d}, y_{1}, \dots , y_{d})
  =
  G (D^{x}_{1}, \dotsc , D^{x}_{d}, D^{y}_{1}, \dotsc , D^{y}_{d})
  F (x_{1}, \dotsc , x_{d}, y_{1}, \dots , y_{d}).
\]
We know from Theorem \ref{thm:diffoper} that $H$ is Hurwitz stable.
Define
\[
  h (x,y) =   H (x, \dots, x, y, \dots , y).
\]
It is immediate that $h$ is Hurwitz stable too.
We will prove that $h (x,y) = r (xy)$,
  which by Lemma~\ref{lem:rrneg} implies that $r$ is in $\RRneg$.

It will be convenient to know that
\[
  \delta^{x}_{i} \sigma^{x}_{j}
=
\begin{cases}
\binom{d+i-j}{i} \sigma^{x}_{j-i}& \text{if $i \leq j$}           
\\
0  & \text{otherwise}.
\end{cases}
\]
We may now compute
\begin{align*}
H (x_{1},\dotsc x_{d}, y_{1}, \dots , y_{d})
& = 
  \sum_{i=0}^{d} 
   b_{i} 
  \frac{\delta_{i}^{x}  \delta_{i}^{y} }{\binom{d}{i}^{2}}
  \sum_{j=0}^{d}
   a_{j} 
  \frac{\sigma_{d-j}^{x} \sigma_{d-j}^{y} }{\binom{d}{j}^{2}}
\\
& = 
  \sum_{i=0}^{d}
  \sum_{j : i \leq d-j}
  \frac{ b_{i}}{\binom{d}{i}^{2}}
  \frac{ a_{j}}{\binom{d}{j}^{2}}
  \delta_{i}^{x}   \delta_{i}^{y} 
  \sigma_{d-j}^{x}   \sigma_{d-j}^{y} 
\\
& = 
  \sum_{i +j \leq d} 
  \frac{a_{j} b_{i}}{\binom{d}{i}^{2} \binom{d}{j}^{2}}
  \delta_{i}^{x} 
  \delta_{i}^{y} 
  \sigma_{d-j}^{x} 
  \sigma_{d-j}^{y} 
\\
& = 
  \sum_{i +j \leq d} 
  \frac{a_{j} b_{i}}{\binom{d}{i}^{2} \binom{d}{j}^{2}}
  \binom{d+i - (d-j) }{i}^{2}
  \sigma_{d-i-j}^{x}
  \sigma_{d-i-j}^{y}
\\
& = 
  \sum_{i +j \leq d} 
  a_{j} b_{i}
 \frac{\binom{i+j}{i}^{2}}{\binom{d}{i}^{2} \binom{d}{j}^{2}}
  \sigma_{d-i-j}^{x}
  \sigma_{d-i-j}^{y}
\\
& = 
  \sum_{k = 0}^{d} 
  \sum_{i + j = k}
  a_{j} b_{i}
  \frac{\binom{k}{i}^{2}}{\binom{d}{i}^{2} \binom{d}{j}^{2}}
  \sigma_{d-k}^{x}
  \sigma_{d-k}^{y}.
\end{align*}
So, 
\begin{align*}
  h (x, y)
& = 
  \sum_{k = 0}^{d} 
  \sum_{i + j = k}
  a_{j} b_{i}
 \left(  \frac{\binom{d}{k} \binom{k}{i}}{\binom{d}{i} \binom{d}{j}} \right)^{2}
  x^{d-k} y^{d-k}.
\\
& = 
  \sum_{k = 0}^{d} 
  \sum_{i + j = k}
  a_{j} b_{i}
 \left(   \frac{
  (d-i) ! (d-j) !
}{
 d! (d-i-j) ! 
}   \right)^{2}
  x^{d-k} y^{d-k}.
\end{align*}
So, $r (xy) = h (x,y)$ and therefore must have only nonpositive real roots.
\end{proof}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "finiteConvMaster"
%%% End:


summary.tex
\subsection{Summary of Results}

We derive the following expression for the symmetric additive convolution of two polynomials.

\begin{theorem}\label{thm:symmetricAdditive}
Let 
\begin{align*}
  p (x) = \sum_{i=0}^{d} x^{d-i} (-1)^{i} a_{i},
\quad  \text{ and} \quad 
  q (x)  = \sum_{i=0}^{d} x^{d-i} (-1)^{i} b_{i}.
\end{align*}
Then,
\begin{equation}\label{eqn:symmetricSum}
  p (x) \sqsum_{d} q (x)  = \sum_{k=0}^{d} x^{d-k} (-1)^{k} 
  \sum_{i+j = k} \frac{(d-i)! (d-j)!}{d! (d-i-j)!}   a_{i} b_{j}.
\end{equation}
This is equivalent to the identities
\[
  p (x) \sqsum_{d} q (x) = 
  \frac{1}{d!} \sum_{i=0}^{d} (d-i)! b_{i} p^{(i)} (x)
=
   \frac{1}{d!} \sum_{i=0}^{d} p^{(i)} (x) q^{(d-i)} (y),
\]
where $p^{(i)}$ denotes the $i$th derivative of $p$.
\end{theorem}

The convolution \eqref{eqn:symmetricSum} was studied by Walsh~\cite{Walsh22}, who proved results
  including the following theorem.
\begin{theorem}\label{thm:symmetricAdditiveRR}
If $p$ and $q$ are real rooted polynomials of degree $d$, then so is
  $p \sqsum_{d} q$.
Moreover, 
\[
  \maxroot{p \sqsum_{d} q} \leq \maxroot{p} + \maxroot{q}.
\]
\end{theorem}
See also \cite{Marden} and \cite[Theorem 5.3.1]{rahman2002analytic}.

In Theorem~\ref{thm:sqsumTrans} we strengthen this bound on the maximum root.
Our result is much tighter in the case that most of the roots of $p$ and $q$
  are far from their maximum roots.

We derive the following expression for the 
 asymmetric additive convolution.
\begin{theorem}\label{thm:asymmetricAdditive}
For 
\[
  p (x)  = \sum_{i=0}^{d} x^{d-i} (-1)^{i} a_{i},
\quad \text{and} \quad 
  q (x)  = \sum_{i=0}^{d} x^{d-i} (-1)^{i} b_{i},
\]
having only nonnegative real roots,
\begin{equation}\label{eqn:asymSum}
  p (x) \recsum_{d} q (x) = \sum_{k=0}^{d} x^{d-k} (-1)^{k} 
\sum_{i+j = k}
 \left(\frac{(d-i)! (d-j)!}{d! (d-i-j)!} \right)^{2}   a_{i} b_{j}.
\end{equation}
This is equivalent to the identity
\[
  p (x) \recsum_{d} q (x) 
 =
  \left(\frac{1}{d!} \right)^{2} \sum_{i=0}^{d} ((d-i)!)^{2} b_{i} (\deriv x \deriv)^{i} p (x).
\]
\end{theorem}

We are not aware of previous studies of this convolution.
We prove the following theorem in Section \ref{sec:rr}.
\begin{theorem}\label{thm:asymAdditiveRR}
If $p$ and $q$ have only nonnegative real roots, then the same is true of
  $p \recsum_{d} q$.
\end{theorem}




\begin{theorem}\label{thm:symmetricMult}
For 
\begin{align*}
  p (x)  = \sum_{i=0}^{d} x^{d-i} (-1)^{i} a_{i} 
 \quad \text{ and} \quad 
  q (x)  = \sum_{i=0}^{d} x^{d-i} (-1)^{i} b_{i}
\end{align*}
having only nonnegative real roots,
\[
  p (x) \sqmult_{d} q (x) =
  \sum_{i=0}^{d} x^{d-i} (-1)^{i} \frac{a_{i} b_{i}}{\binom{d}{i}}.
\]
\end{theorem}


This convolution was studied by Szego \cite{Szego22}, who proved the following theorem.

\begin{theorem}\label{thm:symmetricMultRR}
If $p$ and $q$ have only nonnegative real roots, then the same is true of 
  $p \sqmult_{d} q$.
Moreover,
\[
    \maxroot{p \sqmult_{d} q} \leq \maxroot{p} \maxroot{q}.
\]
\end{theorem}

We strengthen this result in Theorem~\ref{thm:recsumTrans}.


\subsection{Transforms}\label{sec:cauchy}

In free probability, each of these three convolutions comes equipped with a
  natural transform of probability measures.
We define analogous transforms on polynomials and use them to bound the extreme roots
  of the convolutions of polynomials.

We will view a vector $(\lambda_{1}, \dotsc , \lambda_{d})$
  as providing a discrete distribution that takes each value $\lambda_{i}$
  with probability $1/d$.
The Cauchy/Hilbert/Stieltjes transform of such a distribution is the function
\[
  \cauchy{\lambda}{x} = \frac{1}{d} \sum_{i=1}^{d} \frac{1}{x-\lambda_{i}}.
\]
Given a polynomial $p$ with roots $\lambda_{1}, \dotsc , \lambda_{d}$,
  we similarly define
\[
  \cauchy{p}{x} = \cauchy{\lambda}{x}.
\]
We will prove theorems about the inverse  of the Cauchy transform, which we define by
\[
  \invcauchy{p}{w} = \max \setof{x : \cauchy{p}{x} = w}.
\]
For a real rooted polynomial $p$, and thus for real $\lambda_{1}, \dotsc , \lambda_{d}$,
 it is the value of $x$ that is larger than all the $\lambda_{i}$ for which $\cauchy{p}{x} = w$.

As $\cauchy{p}{x} = \frac{1}{d} \frac{p' (x)}{p (x)}$,
\[
\cauchy{p}{x} = w
\quad \iff \quad 
p (x) - \frac{1}{w d} p' (x) = 0.
\]
This tells us that 
\[
  \invcauchy{p}{w} = \maxroot{\shiftoper{1/wd} p},
\]
where we define
\[
  \shiftoper{\alpha} p (x) \defeq  p (x) - \alpha \deriv p (x).
\]


Voiculescu's R-transform of the probability distribution that is uniform on $\lambda$
  is given by $\rtrans{\lambda }{w} = \invcauchy{\lambda }{w} - 1/w$.
We overload this notation to produce a transform on polynomials
\[
  \rtrans{p}{w} = \invcauchy{p}{w} - 1/w.
\]

If $\lambda$ and $\mu$ are probability distributions on the reals, and if $\lambda \sqsum \mu $ is their
  free additive convolution, then
\[
  \rtrans{\lambda \sqsum \mu}{w} = \rtrans{\lambda}{w} + \rtrans{\mu}{w}.
\]
For our finite additive convolution, we obtain an analogous inequality whose proof may be found
  in  Section \ref{sec:sqConvBound}.
\nikhil{We haven't defined $\rrpoly{d}$ yet. Also, do we need the $d$ and $k$
	version here or can we just say they both have degree $d$? It is fine if
	you go with the coeffs definition, but it doesn't make immediate sense
	with the expected charpoly over random matrices definition when $k<d$.}
\begin{theorem}\label{thm:sqsumTrans}
For degree $d$  polynomials $p$ and $q$ that have only real roots,
\begin{equation}\label{eqn:sqsumTrans}
  \rtrans{p \sqsum_{d} q}{w} \leq  \rtrans{p}{w} + \rtrans{q}{w}.
\end{equation}
\end{theorem}
\dan{In the next version, we will prove that equality only happens if $p (x) = (x-\lambda)^{d}$}

We will often write this inequality as
\[
  \maxroot{\shiftoper{\alpha} (p \sqsum_{d} q)} + d \alpha
  \leq 
  \maxroot{\shiftoper{\alpha} p}
  +
  \maxroot{\shiftoper{\alpha} q}.
\]
%or as
%\[
%  \smax{\alpha}{p \sqsum_{d} q} + d \alpha \leq \smax{\alpha}{p} + \smax{\alpha}{q}.
%\]

To define the transform for the asymmetric additive convolution,
  we define $\subsquare$ to be the operation that converts a polynomial $p (x)$
  into the polynomial $p (x^{2})$.
If $p$ has only positive real roots $\lambda_{i}$, then $\subsquare p$ has roots $\pm \sqrt{\lambda_{i}}$.
We overload this notation so that if $\lambda$ is a probability distribution supported on the nonnegative reals,
  then $\subsquare \lambda$ is the corresponding probability distribution on $\pm \sqrt{\lambda_{i}}$.

If $\lambda$ and $\mu$ are probability distributions on positive numbers, and if
  $\lambda \recsum \mu$ is their free asymmetric convolution, then
\[
  \rtrans{\subsquare \lambda \recsum \subsquare \mu}{w} = \rtrans{\subsquare \lambda}{w} + \rtrans{\subsquare \mu}{w}.
\]
\dan{We should look up how they say this in the free probability literature.}

We obtain an analogous inequality whose proof appears in Section~\ref{sec:asymTrans}.
\begin{theorem}\label{thm:recsumTrans}
For degree $d$ polynomials $p$ and $q$ having only nonnegative real roots,
\[
	\rtrans{\subsquare (p \recsum_{d} q)}{w} \leq  \rtrans{\subsquare p}{w} + \rtrans{\subsquare q}{w}.
\]
\end{theorem}

To bound the roots of the finite multiplicative convolution, we employ a variant of Voiculescu's S-transform.
We first define a variant of the moment transform, which we write as a power series in $1/z$ instead of in $z$:
\[
  \mtrans{p}{z} = z \cauchy{p}{z} - 1
=
  \frac{1}{d} \sum_{i=1}^{d} \sum_{j \geq 1} \left(\frac{\lambda_{i}}{z} \right)^{j}.
\]
For a polynomial $p$ having only nonnegative real roots and a $z > 0$,
\[
z > \maxroot{p} \quad \iff \quad \mtrans{p}{z} < \infty .
\]
We define the inverse of this transform, $\invmtrans{p}{w}$, to be the largest
  $z$ so that $\mtrans{p}{z} = w$, and 
\[
\strans{p}{w}
 = 
\frac{w}{w+1} \invmtrans{p}{w}.
\]

This is the reciprocal of the usual $S$-transform.
We prove the following bound on this transformation in Section~\ref{sec:multTrans}.

\begin{theorem}\label{thm:multTransBound}
For $p$ and $q$ having only nonnegative real roots and a $w > 0$,
\[
  \strans{p \sqmult_{d} q}{w} \leq \strans{p}{w} \strans{q}{w}.
\]
%with equality only when $p$ or $q$ has only one distinct root.
\end{theorem}
\dan{In the next version, we will prove that equality only happens if $p (x) = (x-\lambda)^{d}$}





\subsection{Notation}

Let $\rrpoly{d}$ be the family of real rooted polynomials of degree $d$ with positive leading coefficient,
  and let $\RRpoly$ be the union over $d$ of $\rrpoly{d}$.
Let $\rrpos{d}$ be the subset of these polynomials having only nonnegative roots.
We let $\RRpos $ be the union of $\rrpos{d}$ over all $d \geq 1$.
We also define $\rrneg{d}$ and $\RRneg$ to be the set of polynomials having only nonpositive roots.

For a function $f (x)$, we write the derivative as $\deriv f (x)$.
For a number $\alpha$, we let $\shiftoper{\alpha}$ be the operator that maps
  $f$ to $f - \alpha D f$.
That is, $\shiftoper{\alpha}$ is multiplication by $1 - \alpha D$.



finiteConvMaster.bbl
\begin{thebibliography}{MSS15b}

\bibitem[AGZ10]{anderson2010introduction}
Greg~W Anderson, Alice Guionnet, and Ofer Zeitouni.
\newblock {\em An introduction to random matrices}, volume 118.
\newblock Cambridge University Press, 2010.

\bibitem[BB09a]{borceaBrandenLeeYang2}
J.~Borcea and P.~Br{\"a}nd{\'e}n.
\newblock The {Lee-Yang} and {P{\'o}lya-Schur} programs. {II}. {Theory} of
  stable polynomials and applications.
\newblock {\em Communications on Pure and Applied Mathematics},
  62(12):1595--1631, 2009.

\bibitem[BB09b]{BBLeeYang1}
Julius Borcea and Petter Br{\"a}nd{\'e}n.
\newblock The {L}ee--{Y}ang and {P}{\'o}lya--{S}chur programs, {I}. {L}inear
  operators preserving stability.
\newblock {\em Invent. Math.}, 177(3):541--569, 2009.

\bibitem[BSS12]{BSS}
Joshua Batson, Daniel~A Spielman, and Nikhil Srivastava.
\newblock Twice-{Ramanujan} sparsifiers.
\newblock {\em SIAM Journal on Computing}, 41(6):1704--1721, 2012.

\bibitem[LS81]{LiebSokal}
Elliott~H. Lieb and Alan~D. Sokal.
\newblock A general {Lee-Yang} theorem for one-component and multicomponent
  ferromagnets.
\newblock {\em Communications in Mathematical Physics}, 80(2):153--179, 1981.

\bibitem[Mar66]{Marden}
M.~Marden.
\newblock {\em Geometry of polynomials}.
\newblock Number~3. Amer Mathematical Society, 1966.

\bibitem[MSS15a]{IF1}
Adam~W. Marcus, Daniel~A. Spielman, and Nikhil Srivastava.
\newblock Interlacing families {I}: Bipartite {Ramanujan} graphs of all
  degrees.
\newblock {\em Annals of Mathematics}, 182, 2015.
\newblock to appear.

\bibitem[MSS15b]{IF2}
Adam~W. Marcus, Daniel~A. Spielman, and Nikhil Srivastava.
\newblock Interlacing families {II}: Mixed characteristic polynomials and the
  {Kadison--Singer} problem.
\newblock {\em Annals of Mathematics}, 182, 2015.
\newblock to appear.

\bibitem[MSS15c]{IF4}
Adam~W. Marcus, Daniel~A. Spielman, and Nikhil Srivastava.
\newblock Interlacing families {IV}: Bipartite {Ramanujan} graphs of all sizes.
\newblock 2015.
\newblock in preparation.

\bibitem[NS06]{nica2006lectures}
Alexandru Nica and Roland Speicher.
\newblock {\em Lectures on the combinatorics of free probability}, volume~13.
\newblock Cambridge University Press, 2006.

\bibitem[RS02]{rahman2002analytic}
Q.I. Rahman and G.~Schmeisser.
\newblock {\em Analytic theory of polynomials}.
\newblock Clarendon Press Oxford, 2002.

\bibitem[Sze22]{Szego22}
G~Szeg{\"o}.
\newblock Bemerkungen zu einem {Satz} von {J H Grace} {\"u}ber die {Wurzeln}
  algebraischer {Gleichungen}.
\newblock {\em Mathematische Zeitschrift}, 13(1):28--55, 1922.

\bibitem[Voi97]{voiculescu1997free}
Dan~V Voiculescu.
\newblock {\em Free probability theory}.
\newblock American Mathematical Society, 1997.

\bibitem[Wal22]{Walsh22}
JL~Walsh.
\newblock On the location of the roots of certain types of polynomials.
\newblock {\em Transactions of the American Mathematical Society},
  24(3):163--180, 1922.

\end{thebibliography}
