Optimality of Curtiss Bound on
Poincaré Multiplier for
Positive Univariate Polynomials

Symbolically, we have

$$\underset{\theta\in\Theta}{\forall}\ \ \underset{r\in R}{\exists}\ \ \operatorname*{opt}\left(f\right)=b\left(f\right).$$

After extensive exploration, we identified a natural split in strategies between collections of angles $0<\theta<\dfrac{\pi}{2}$ and those with additional angles $\dfrac{\pi}{2}\leq\theta\leq\pi$. We now have

$$\underset{\theta\in\Theta_{1}\cup\Theta_{2}}{\forall}\ \ \underset{r\in R}{\exists}\ \ \operatorname*{opt}\left(f\right)=b\left(f\right).$$

We first focus on the claim for $\theta\in\Theta_{1}$, polynomials with complex root arguments $0<\theta<\dfrac{\pi}{2}$. That is, for any collection of angles in this subset, there exists a corresponding collection of radii such that Curtiss’s bound is the minimum possible degree for the Poincaré multiplier to achieve a product with all non-negative coefficients. One way to show this is to prove that there exist radii such that any multiplier of smaller degree will produce a product with a negative coefficient. We can then rewrite the claim as

$$\underset{\theta\in\Theta_{1}}{\forall}\ \ \underset{r\in R}{\exists}\ \ \underset{g\in G}{\forall}\ \ \underset{k\in K}{\exists}\ \ \operatorname*{coeff}(gf,k)<0.$$

Note, with this rewrite we consider a problem with three quantifier alternations. As this is a very complex problem, we seek to reduce the search space for the negative coefficient. It is straightforward to prove that, rather than consider the entire set of multipliers of smaller degree, it is sufficient to focus on the set of multipliers with degree one less than Curtiss’s bound to show that any such multiplier will produce a product with a negative coefficient. We now have

$$\underset{\theta\in\Theta_{1}}{\forall}\ \ \underset{r\in R}{\exists}\ \ \underset{g\in G^{\prime}}{\forall}\ \ \underset{k\in K}{\exists}\ \ \operatorname*{coeff}(gf,k)<0$$

for a subset $G^{\prime}$ of the original multiplier search space $G$ that is determined by the Curtiss bound (hence, by $\theta$). After detailed analysis of examples, we surprisingly discovered that we can also narrow down the potential locations of the negative coefficient. In fact, although the collection of product coefficients grows in size with Curtiss’s bound, we can identify a negative coefficient from a subset of just 3 possibilities. Hence

$$\underset{\theta\in\Theta_{1}}{\forall}\ \ \underset{r\in R}{\exists}\ \ \underset{g\in G^{\prime}}{\forall}\ \ \underset{k\in K^{\prime}}{\exists}\ \ \operatorname*{coeff}(gf,k)<0$$

for a subset $K^{\prime}$ of the original coefficient search space $K$ that is determined by the number of angles in $\theta$ and the Curtiss bound (hence, by $\theta$). Finally, with more difficulty, we determined how to reduce the search space for the desired radii. By identifying a witness, in terms of $\cos\left(\theta\right)$, for all but one of the radii, we reduced the radii search space to just a one-dimensional space for the final radius. We have

$$\underset{\theta\in\Theta_{1}}{\forall}\ \ \underset{r\in R^{\prime}}{\exists}\ \ \underset{g\in G^{\prime}}{\forall}\ \ \underset{k\in K^{\prime}}{\exists}\ \ \operatorname*{coeff}(gf,k)<0$$

for a subset $R^{\prime}$ of the original radii search space $R$. Proving this final version of the claim was still a significant challenge. We examined the geometry of the product coefficients as a function of this final unknown radius in order to verify the claim. Expressing the coefficients of the original polynomial $f$ in terms of the elementary symmetric polynomials in the roots of $f$ proved essential to our progress, enabling us to make claims about the sign of the coefficients that were otherwise quite challenging.

Having proved the claim in the case where all angles fall in $\Theta_{1}$, we move on to the case where we have mixed angles from $\Theta_{1}$ or $\Theta_{2}$. The crux of this claim is that any polynomial in which Curtiss’s bound is optimal can be multiplied by a quadratic with angle $\dfrac{\pi}{2}\leq\theta<\pi$ and a radius that preserves the optimality of Curtiss’s bound or a linear factor with an appropriate radius that preserves the optimality of Curtiss’s bound. Thus, for any collection of additional angles in quadrant 2, we can inductively prove the existence of the necessary radii to ensure the optimality of Curtiss’s bound.

$$\underset{\theta\in\Theta_{2}}{\forall}\ \ \underset{r\in R}{\exists}\ \ \operatorname*{opt}\left(f_{\theta,r}\,f\right)=\operatorname*{opt}\left(f\right)=b(f)$$

Note that, in this case, the additional factors in the polynomial do not increase the Curtiss bound. For this sub-claim we utilize a different strategy, relying on linear algebra to rewrite the optimality claim as a separation between two sets.

Since we must treat angles separately according to their measure, we split the collection of angles $\theta_{1},\ldots,\theta_{\sigma}$ into three sets as detailed below. Let

	$\displaystyle f$	$\displaystyle=f_{\theta,r_{\theta}}\,f_{\phi,r_{\phi}}\,f_{\pi,p}$
	$\displaystyle f_{\theta,r_{\theta}}$	$\displaystyle=\prod\limits_{\begin{subarray}{c}1\leq i\leq\ell\\ 0<\theta_{i}<\frac{\pi}{2}\end{subarray}}\left(x^{2}-2r_{\theta_{i}}\cos\theta_{i}\,x+r_{\theta_{i}}^{2}\right)\ \ \ \text{where }r_{\theta_{i}}>0\ \text{and }0<\theta_{1}\leq\cdots\leq\theta_{\ell}<\dfrac{\pi}{2}$
	$\displaystyle f_{\phi,r_{\phi}}$	$\displaystyle=\prod\limits_{\begin{subarray}{c}1\leq i\leq k\\ \frac{\pi}{2}\leq\phi_{i}<\pi\end{subarray}}\left(x^{2}-2r_{\phi_{i}}\cos\phi_{i}\,x+r_{\phi_{i}}^{2}\right)\ \text{where }r_{\phi_{i}}>0\leavevmode\nobreak\ \text{and }\ \dfrac{\pi}{2}\leq\phi_{1}\leq\cdots\leq\phi_{k}<\pi$
	$\displaystyle f_{\pi,p}$	$\displaystyle=\prod\limits_{1\leq i\leq t}\left(x+p_{i}\right)\ \,\text{where }p_{i}>0$

where $k+\ell+t=\sigma$ and $2(k+\ell)+t=n=\deg(f)$.

Proof: [Proof of Theorem 2] We need to show

$$\underset{\frac{\pi}{2}\leq\phi_{1}\leq\cdots\leq\phi_{k}<\pi}{\forall}\ \ \underset{0<\theta_{1}\leq\cdots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{p_{1},\ldots,p_{t}>0}{\exists}\ \ \underset{r_{\phi_{1}},\ldots,r_{\phi_{k}}>0}{\exists}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \operatorname*{opt}\left(f\right)=b\left(f\right).$$

Let $\dfrac{\pi}{2}\leq\phi_{1}\leq\cdots\leq\phi_{k}<\pi\ \,$and $0<\theta_{1}\leq\cdots\leq\theta_{\ell}<\dfrac{\pi}{2}$ be arbitrary but fixed. We need to show

$$\underset{p_{1},\ldots,p_{t}>0}{\exists}\ \ \underset{r_{\phi_{1}},\ldots,r_{\phi_{k}}>0}{\exists}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \operatorname*{opt}\left(f\right)=b\left(f\right).$$

We need to find a witness for $p,r_{\phi},r_{\theta}$ such that $\operatorname*{opt}\left(f\right)=b\left(f\right)$. We propose a witness candidate as follows. From the All Angles in Quadrant 1 Lemma (Lemma 4), for the fixed $\theta$, we have

$$\underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \ \operatorname*{opt}\left(f_{\theta,r_{\theta}}\right)=b\left(f_{\theta,r_{\theta}}\right).$$

(1)

From the Some Angles in Quadrant 2 Lemma (Lemma 11), for the fixed $\phi$ and $\theta$, we have

$$\underset{p_{1},\ldots,p_{t}>0}{\exists}\ \ \ \underset{r_{\phi_{1}},\ldots,r_{\phi_{k}}>0}{\exists}\ \ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\forall}\ \ \ \operatorname*{opt}\left(f_{\theta,r_{\theta}}\,f_{\phi,r_{\phi}}\,f_{\pi,p}\right)=\operatorname*{opt}\left(f_{\theta,r_{\theta}}\right).$$

(2)

We propose $p,r_{\phi},r_{\theta}$ appearing in the above two facts as a witness candidate.

We verify that the proposed candidate is indeed a witness, that is, $\operatorname*{opt}\left(f\right)=b\left(f\right)$. Note

	$\displaystyle\operatorname*{opt}\left(f\right)$	$\displaystyle=\operatorname*{opt}\left(f_{\theta,r_{\theta}}\,f_{\phi,r_{\phi}}\,f_{\pi,p}\right)$
		$\displaystyle=\operatorname*{opt}\left(f_{\theta,r_{\theta}}\right)\ \ \text{by (\ref{l:reduce})}$
		$\displaystyle=b\left(f_{\theta,r_{\theta}}\right)\ \text{by (\ref{l:core})}$
		$\displaystyle=b\left(f_{\theta,r_{\theta}}\right)+b\left(f_{\phi,r_{\phi}}\right)+b\left(f_{\pi,p}\right)\ \text{since }b\left(f_{\phi,r_{\phi}}\right)=b\left(f_{\pi,p}\right)=0\$
		$\displaystyle=b\left(f_{\theta,r_{\theta}}\,f_{\phi,r_{\phi}}\,f_{\pi,p}\right)$
		$\displaystyle=b\left(f\right).$

Hence the theorem is proved. $\Box$ 

Proof: Note

	$\displaystyle gf$	$\displaystyle=\left(bx_{s}\right)\left(ax_{n}\right)$
		$\displaystyle=b\left(x_{s}ax_{n}\right)$
		$\displaystyle=b\left[\begin{array}[c]{c}x^{0}\\ \vdots\\ x^{s}\end{array}\right]\left[\begin{array}[c]{ccc}a_{0}&\cdots&a_{n}\end{array}\right]\left[\begin{array}[c]{c}x^{0}\\ \vdots\\ x^{n}\end{array}\right]$
		$\displaystyle=b\left[\begin{array}[c]{cccccc}a_{0}&\cdots&\cdots&a_{n}&&\\ &\ddots&&&\ddots&\\ &&a_{0}&\cdots&\cdots&a_{n}\end{array}\right]\left[\begin{array}[c]{c}x^{0}\\ \vdots\\ x^{s+n}\end{array}\right]$
		$\displaystyle=bA_{s}x_{s+n}$

Hence $\operatorname*{coeffs}\left(gf\right)=bA_{s}$. $\Box$ 

Proof: We need to prove the following claim for every $\ell\geq 0$.

$$\underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \operatorname*{opt}\left(f_{\theta,r_{\theta}}\right)=s$$

where $s=b(f_{\theta,r_{\theta}})$. By the One Less Degree Lemma (Lemma 5), it suffices to show

$$\begin{array}[c]{cl}&\underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)=s-1}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{0\leq k\leq 2\ell+s-1}{\exists}\ \ c_{k}<0.\end{array}$$

We will show it in three cases depending on the values of $\ell$.

Case:

$\ell=0$.

Here, $f=1$. The claim is trivially true since $\operatorname*{opt}\left(f_{\theta,r_{\theta}}\right)=b\left(f_{\theta,r_{\theta}}\right)=0$.

Case:

$\ell=1$.

Immediate from the Curtiss Bound (Theorem 1).

Case:

$\ell\geq 2$.

Note

		$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \operatorname*{opt}\left(f_{\theta,r_{\theta}}\right)=b\left(f_{\theta,r_{\theta}}\right)$
	$\displaystyle\iff$	$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)<s}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{k}{\exists}\ \ c_{k}<0$
	$\displaystyle\Longleftarrow\$	$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)=s-1}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{k}{\exists}\ \ c_{k}<0\ \ \ \ \text{by Lemma }\ref{lem:deg}$
	$\displaystyle\Longleftarrow\$	$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)=s-1}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{k\in\{s-2,\,2\ell+s-5,\,2\ell+s-2\}}{\exists}\ \ c_{k}<0\ \ \ \ \text{by Lemma }\ref{lem:subset}.$

We prove this final claim to be true in the Existence of Radii Lemma, Lemma 10.

$\Box$ 

Now we prove Lemmas 5 and 6, cited above, and also several other lemmas required for the main claim, the Existence of Radii Lemma (Lemma 10).

First, we prove the small but essential claim that if there is no Poincaré multiplier, $g$, of a certain degree, then there is also no Poincaré multiplier with smaller degree.

Proof: We will prove via the contrapositive:

$$\underset{g,\,\deg(g)<s}{\exists}\ \ \underset{k}{\forall}\ \ c_{k}\geq 0\ \ \ \ \Longrightarrow\ \ \ \ \underset{g,\,\deg(g)=s}{\exists}\ \ \underset{k}{\forall}\ \ c_{k}\geq 0.$$

Assume $\underset{g,\,\deg(g)<s}{\exists}\ \ \underset{k}{\forall}\ \ c_{k}\geq 0$. Then there exists a $g$ with $\deg(g)=t<s$ such that $g\,f_{\theta,r_{\theta}}$ has all non-negative coefficients. Let $u=s-t$.

Our ultimate goal for this section is to prove that there exist radii such that there is no multiplier with degree less than $b(f_{\theta,r_{\theta}})$. The One Less Degree Lemma (Lemma 5) states that it suffices to show there is no multiplier with degree $b(f_{\theta,r_{\theta}})-1$. Next, we show that if we consider a multiplier of degree one less, it suffices to examine a specific subset of the coefficients in the product rather than all coefficients to prove the claim. Note that the surprisingly small subset of coefficients was selected by examining the geometry of the coefficients and determining a minimally sufficient set. This is the proof that a subset will suffice. The proof that this particular subset satisfies the claim is given in Lemma 10.

Proof: Recall that

	$\displaystyle s$	$\displaystyle=b\left(f_{\theta,r_{\theta}}\right)$
	$\displaystyle g$	$\displaystyle=x^{s-1}+b_{s-2}x^{s-2}+\cdots+b_{1}x+b_{0}$
	$\displaystyle t_{i}$	$\displaystyle=\cos(\theta_{i}).$

Note that if $\deg(f)=2\ell$ and $\deg(g)=s-1$, then $\deg(g\,f)=2\ell+s-1$.

		$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)=s-1}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{k}{\exists}\ \ c_{k}<0$
	$\displaystyle\iff$	$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)=s-1}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{0\leq k\leq 2\ell+s-1}{\exists}\ \ c_{k}<0$
	$\displaystyle\Longleftarrow\ \,$	$\displaystyle\ \underset{0<\theta_{1}\leq\ldots\leq\theta_{\ell}<\frac{\pi}{2}}{\forall}\ \ \underset{r_{\theta_{1}},\ldots,r_{\theta_{\ell}}>0}{\exists}\ \ \underset{\deg(g)=s-1}{\underset{g\in\mathbb{R}[x]}{\forall}}\ \ \underset{k\in\{s-2,\,2\ell+s-5,\,2\ell+s-2\}}{\exists}\ \ c_{k}<0.$

$\Box$ 

The next two lemmas are helpful in the proof of Lemma 10 and are listed separately here to streamline the proof of Lemma 10.

Proof: Recall from the Coefficients Lemma (Lemma 3) for $0\leq i\leq 2\ell$ and $0\leq j\leq s-1$,

$\displaystyle\operatorname*{coeffs}(gf)$

$\displaystyle=\left[\begin{array}[c]{ccc}b_{0}&\cdots&b_{s-1}\end{array}\right]\left[\begin{array}[c]{cccccc}a_{0}&\cdots&\cdots&a_{2\ell}&&\\ &\ddots&&&\ddots&\\ &&a_{0}&\cdots&\cdots&a_{2\ell}\end{array}\right]$

Then

	$\displaystyle\operatorname*{coeff}(gf,x^{k})$	$\displaystyle=\sum_{i+j=k}a_{i}b_{j}$
		$\displaystyle=\sum_{i=0}^{k}a_{i}b_{k-i}.$

Hence,

$$\operatorname*{coeff}(gf,x^{k})=\displaystyle\sum_{i+j=k}a_{i}b_{j}=\displaystyle\sum_{i=0}^{k}a_{i}b_{k-i}\;\;\text{for}\;\;0\leq k\leq 2\ell+s-1.$$

Then we have

	$\displaystyle c_{s-2}$	$\displaystyle=\sum_{i=0}^{s-2}a_{i}b_{(s-2)-i}$
		$\displaystyle=a_{0}b_{s-2}+a_{1}b_{s-3}+\sum_{i=2}^{s-2}a_{i}b_{(s-2)-i}$
	$\displaystyle c_{2\ell+s-5}$	$\displaystyle=\sum_{i+j=2\ell+s-5}a_{i}b_{j}$
		$\displaystyle=a_{2\ell-4}b_{s-1}+a_{2\ell-3}b_{s-2}+a_{2\ell-2}b_{s-3}+a_{2\ell-1}b_{s-4}+a_{2\ell}b_{s-5}$
		$\displaystyle=a_{2\ell-4}+a_{2\ell-3}b_{s-2}+a_{2\ell-2}b_{s-3}+a_{2\ell-1}b_{s-4}+b_{s-5}\ \ \ \ \text{since }a_{2\ell}=b_{s-1}=1$
	$\displaystyle c_{2\ell+s-2}$	$\displaystyle=\sum_{i+j=2\ell+s-2}a_{i}b_{j}$
		$\displaystyle=a_{2\ell-1}b_{s-1}+a_{2\ell}b_{s-2}$
		$\displaystyle\ =a_{2\ell-1}+b_{s-2}\ \ \ \ \text{since }a_{2\ell}=b_{s-1}=1.$

$\Box$ 

The following lemma verifies a property of elementary symmetric polynomials in the roots $\alpha_{1},\ldots,\alpha_{2\ell}$ that is required for the proof of the Existence of Radii Lemma (Lemma 10).

Proof: We will induct on $\ell$, the number of quadratic factors of $f$ with non-real roots.