# Max-root inequality for convex combination of real-stable monic polynomials (Kadison-Singer Problem)

In the paper "The Kadison-Singer Problem" by Marcin Bownik (https://arxiv.org/pdf/1702.04578.pdf), the following Lemma (3.8) is proven:

Lemma: Let $$p, q\in \mathbb{R}[x]$$ be stable monic polynomials of the same degree. Suppose that every convex combination $$(1 − t)p + tq, 0 \leq t \leq 1$$, is also stable. Then for any $$0 \leq t_0 \leq 1$$, $$\operatorname{maxroot}(((1 − t_0)p + t_0q)$$ lies between $$\operatorname{maxroot}(p)$$ and $$\operatorname{maxroot}(q)$$.

Proof: WLOG, we can assume $$0 and $$\operatorname{maxroot}(p)\leq\operatorname{maxroot}(q).$$ The goal is then to show that

$$m_p := \operatorname{maxroot}(p) \leq \operatorname{maxroot}(((1 − t_0)p + t_0q) \leq maxroot(q) =: m_q.$$ The second inequality is easy. The first is proven by contradiction:

Suppose that $$(1 − t_0)p + t_0q$$ has no roots in $$[m_p, m_q]$$. This implies that $$(1−t_0)p+t_0q > 0$$ for all $$x \geq m_p$$. Then $$q(m_p)>0$$ and $$q$$ must have (counting multiplicity) at least 2 roots to the right of $$m_p$$. Letting now $$D$$ be the open disk in $$\mathbb{C}$$ centered at $$\frac{m_p+m_q}{2}$$ and radius $$\frac{m_q-m_p}{2}$$. It is claimed then that

$$((1 − t)p + tq)(z) \neq 0 \text{ for all } z \in\partial D \text{ and } t_0 \leq t \leq 1.$$

As by assumption, the convex combination of the polynomials is also real-stable, it is sufficient to check this for $$z=m_p$$ and $$z=m_q$$. As $$p(m_p)=0, this is clear for $$m_p$$ as $$t_0>0$$. However, for $$t=1$$, we have that

$$((1 − t)p + tq)(z)\mid_{t=1,z=m_q} = q(m_q)=0.$$

$$\inf_{(z,t)\in \partial D\times [t_0,1]} \vert ((1 − t)p + tq)(z)\vert>0,$$ which then itself is used to obtain a contradiction to the assumption that there are no zeros in $$[m_p, m_q]$$ via Rouche's Theorem.

So I neither see how they can claim that the infimum is positive nor how the proof should be adapted to correct for this perceived mistake. Thanks for any help.

Indeed, the proof in the linked paper does not seem valid.

Here is a "real" proof of the lemma in question, without using complex analysis:

Let $$m:=$$maxroot and $$q_t:=(1-t)p+tq$$, so that $$q_0=p$$ and $$q_1=q$$. As in your post, without loss of generality (wlog) $$m(p)\le m(q)$$. If $$m(p)=m(q)$$, then $$m(p)$$ is a common root of both $$p$$ and $$q$$, and hence $$m(p)$$ is a root of $$q_t$$ for all $$t$$, so that $$m(q_t)\ge m(p)$$, as desired. So, wlog $$m(p), and then, by shifting and rescalling, wlog $$\begin{equation*} m(p)=0,\quad m(q)=1. \end{equation*}$$ We want to show that $$\begin{equation*} m(q_t)\ge0 \end{equation*}$$ for all $$t\in[0,1]$$. Let $$\begin{equation*} t_*:=\min\{t\in[0,1]\colon m(q_s)\ge0\ \forall s\in[t,1]\}. \end{equation*}$$ This $$\min$$ exists in view of the continuity of $$q_s$$ in $$s$$ and the compactness of $$[0,1]$$.

Moreover, for each $$t\in[0,t_*]$$, $$q_t$$ is a convex combination of $$p=q_0$$ and $$q_{t_*}$$. So, wlog $$t_*=1$$, so that $$\begin{equation*} m(q_{t_n})<0 \tag{1} \end{equation*}$$ for some sequence $$(t_n)$$ such that $$t_n\uparrow1$$.

One of the following two cases must occur:

Case 1: there is a root $$r\in(0,1)$$ of $$q$$ of an odd multiplicity. Then $$q_1=q$$ changes its sign at $$r$$. So, for all $$t\in(0,1)$$ close enough to $$1$$, $$q_t$$ will change its sign in some small enough neighborhood of $$r$$ and thus will have a root close enough to $$r$$, which will contradict (1).

Case 2: there is no root $$r\in(0,1)$$ of $$q$$ of an odd multiplicity. Then $$q$$ does not change its sign on $$(0,1)$$ from $$+$$ to $$-$$ or vice versa. Therefore and because $$q(0)>0$$ (as was shown in your post), we see that $$q\ge0$$ on $$[0,1]$$ (and $$q>0$$ on $$(1,\infty)$$). Moreover, $$1$$ is a root of $$q$$. Also, $$q_t>0$$ on $$[0,\infty)$$ for all $$t>0$$, because $$p>0$$ on $$(0,\infty)$$. So, switching from $$q$$ to $$q_t$$, we will lose the (multiple) root $$1$$ of $$q$$, as well as all the other roots of $$q$$ in $$(0,\infty)$$ (all of them of an even multiplicity). Moreover, if $$t$$ is close enough to $$1$$, this loss cannot be regained elsewhere. Thus, we get a contradiction with the assumption that $$q_t$$ is stable (that is, with the assumption that all roots of $$q_t$$ are real).

Details on the loss and no gains in Case 2: We have $$q_t/t=q+sp$$, where $$s:=(1-t)/t$$ and $$t:=t_n$$. So, $$t\uparrow1$$ and hence $$s\downarrow0$$. For a real polynomial $$P$$ and an interval $$I\subseteq\mathbb R$$, let $$N_I(P)$$ denote the number of roots of $$P$$ in $$I$$ (counting the multiplicities), so that $$N_{\mathbb R}(P)$$ is the number of real roots of $$P$$; moreover, $$N_{\mathbb R}(P)$$ equals the degree of $$P$$ if $$P$$ is stable.

In view of (1), $$N_{(0,\infty)}(q+sp)=0$$, whereas $$N_{(0,\infty)}(q)\ge2$$ (this is what was referred to as the loss). On the other hand, the condition that the $$q_t$$'s are stable monic polynomials of the same degree implies that $$N_{\mathbb R}(q+sp)=N_{\mathbb R}(q)$$. So, to get a contradiction, it suffices to show that $$\begin{equation*} N_{(-\infty,0]}(q+sp)\le N_{(-\infty,0]}(q) \tag{2} \end{equation*}$$ for all small enough $$s>0$$ (this is what was referred to as the no-gain).

By standard and easy bounds on the roots of a polynomials and by compactness, eventually (that is, for all small enough $$s>0$$) every root of $$q+sp$$ will be in arbitrarily small neighborhood of a root of $$q$$. Let $$v$$ be any (necessarily real) root of $$q$$, so that $$\begin{equation*} q(x)=(x-v)^l q_1(x) \end{equation*}$$ for all real $$x$$, where $$l$$ is the natural number equal the multiplicity of the root $$v$$ of $$q$$, so that $$q_1$$ is a polynomial with $$b:=q_1(v)\ne0$$. Let then $$\begin{equation*} p(x)=(x-v)^k p_1(x) \end{equation*}$$ for all real $$x$$, where $$k$$ is the unique nonnegative integer such that $$p_1$$ is a polynomial with $$a:=p_1(v)\ne0$$.

One of the following two cases must occur:

Case 2.1: $$l\le k$$. Then, with $$u:=x-v$$, $$\begin{equation*} q(x)+sp(x)=u^l(q_1(x)+su^{k-l}p_1(x))\sim bu^l \end{equation*}$$ as $$s\to0$$ and $$x\to v$$, so that $$N_V(q+sp)=l=N_V(q)$$ for some neighborhood $$V$$ of $$v$$ and all small enough $$s>0$$.

Case 2.2: $$l>k$$. Then, again with $$u:=x-v$$, $$\begin{equation*} q(x)+sp(x)=u^kp_1(x)\big(R(u)u^{l-k}+s\big), \end{equation*}$$ where $$\begin{equation*} R(u):=\frac{q_1(v+u)}{p_1(v+u)}. \end{equation*}$$ Note that $$(R(u)u^{l-k})'=R(u)(l-k)u^{l-k-1}+R'(u)u^{l-k}\sim\dfrac ba\,(l-k)u^{l-k-1}$$ as $$u\to0$$. So, $$R(u)u^{l-k}$$ is monotonic with nonzero derivative in $$u$$ in a right neighborhood of $$0$$ and in a left neighborhood of $$0$$. It follows that the equation $$R(u)u^{l-k}+s=0$$ has no more than two roots $$u$$ in a neighborhood of $$0$$ if $$l-k$$ is even (and hence $$\ge2$$, by the Case 2.2 condition) and no more than one root $$u$$ in a neighborhood of $$0$$ if $$l-k$$ is odd. So, $$N_V(q+sp)\le k+2\le l=N_V(q)$$ for some neighborhood $$V$$ of $$v$$ and all small enough $$s>0$$ if $$l-k$$ is even, and $$N_V(q+sp)\le k+1\le l=N_V(q)$$ for some neighborhood $$V$$ of $$v$$ and all small enough $$s>0$$ if $$l-k$$ is odd.

So, in all cases $$N_V(q+sp)\le N_V(q)$$ for some neighborhood $$V$$ of $$v$$ and all small enough $$s>0$$. Thus, (2) is proved. $$\Box$$

• Thanks a lot. If I understand correctly, the argument for case 1 seems a continuity argument of sort $\lim_{t_n\to t_*} m(q_{t_n})=m(q_{t_*})>m_p=0$, which leads to the contradiction. Did I understand this correctly? If so, is it clear that $m()$ is continuous and secondly, why wouldn't this hold for case 2 as well? Commented Mar 23, 2021 at 6:41
• @Strickland : Thank you for your comment. Somehow, I thought only of the roots of $q$ in $(0,1)$ of odd multiplicities. This is now fixed. Commented Mar 23, 2021 at 14:11
• Thanks for the clarification. If still have some questions though, if you do not mind. 1. When you argue that $R(u)u^{l-k}+s=0$ has no more than two roots $u$ resp. one, I assume you base this on monotonicity. However, could it not have a root of multiplicity 4 for example? 2. It is immediately assumed that $m(p)<m(q)$. What if they are equal? Commented Mar 24, 2021 at 6:41
• @Strickland : (i) Such multiple roots cannot exist, because $R(u)u^{l-k}$ has a nonzero derivative in those right and left neighborhoods. I have now added this additional explanation. (ii) I have also added details on $m(p)<m(q)$. Commented Mar 24, 2021 at 13:59