14
$\begingroup$

The following is an exercise (Exercise #3 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics.

Let $P(x)$ be a nonzero polynomial with real coefficients. Show that the following two conditions are equivalent:

  • There exists a nonzero polynomial $Q(x)$ with real coefficients such that all coefficients of $P(x) Q(x)$ are nonnegative.

  • There does not exist a real number $a > 0$ such that $P(a) = 0$.

That the first item implies the second is straightforward (since if $a$ is a positive real root of $P(x)$ then it is a positive real root of $P(x)Q(x)$, but since $P(x)Q(x)$ is nonzero with all coefficients nonnegative, this is impossible). However, I can't seem to find a way to prove that the second item implies the first. I would very much like to see a proof if someone can provide it.

$\endgroup$
  • $\begingroup$ It seems obvious from the linear factorization Theorem that all real coefficients of $P{x)$ are positive. Why not choose a simple nonzero $Q(x)$ like $1$? $\endgroup$ – John Molokach Nov 26 '15 at 15:10
  • $\begingroup$ @JohnMolokach I don't understand your suggestion. If p(x) has no positive real roots it does not follow that all of its coefficients are positive. Take p(x) = -x^2 -1 for example. $\endgroup$ – Cosima Maslani Nov 26 '15 at 15:15
  • $\begingroup$ Mariani, sorry. It seems I assumed at least one negative real root. $\endgroup$ – John Molokach Nov 26 '15 at 15:19
  • 2
    $\begingroup$ Hint: it suffices to prove this for quadratic polynomials (I left this hint before, then had a doubt, now I'm sure of it so put it back.) $\endgroup$ – Matt Samuel Nov 26 '15 at 15:34
6
+100
$\begingroup$

Another proof, due to Polya (1928):

Suppose that $f(x) = \sum_{j=0}^d f_j x^j$ is positive on $[0, \infty)$. We claim that, for $N$ sufficiently large, $(1+x)^N f(x)$ has positive coefficients.

Proof: Suppose to the contrary that there is an infinite sequence of pairs $(k_i, N_i)$ such that the coefficient of $x^{k_i}$ in $(1+x)^{N_i} f(x)$ is nonpositive, with $N_i \to \infty$. Passing to a subsequence, we may assume that $\lim_{i \to \infty} k_i/N_i$ exists; call this limit $\alpha$. It will be convenient to assume $\alpha \neq 1$; if $\alpha=1$ then replace $f$ by its reversal $\sum_{j=0}^d f_{d-j} x^j$, which will replace $k_i$ by $N_i-k_i$ and hence $\alpha$ by $1-\alpha$.

Now, the coefficient of $x^{k_i}$ in $(1+x)^{N_i} f(x)$ is $$\sum_{j=0}^d f_j \binom{N_i}{k_i-j} = \binom{N_i}{k_i} \sum_{j=0}^d f_j \frac{k_i}{(N_i-k_i+1)} \frac{(k_i-1)}{(N_i-k_i+2)} \cdots \frac{(k_i-j)}{(N_i-k_i+j+1)} .$$ So the sum on the right hand side is $\leq 0$ for all $i$.

Sending $i \to \infty$, the right hand sum approaches $\sum_{j=0}^d f_j \left( \frac{\alpha}{1-\alpha} \right)^j = f\left( \frac{\alpha}{1-\alpha} \right) >0$. (We wanted $\alpha \neq 1$ so $\tfrac{\alpha}{1-\alpha}$ is well defined.) So we have a sequence of nonpositive numbers aproaching a positive limit, a contradiction.

$\endgroup$
  • $\begingroup$ In the second paragraph, it should be "we claim... $(1+x)^N f(x)$ has positive coefficients", no? $\endgroup$ – leonbloy Apr 4 '16 at 21:16
  • $\begingroup$ @leonbloy Isn't that what I wrote? $\endgroup$ – David E Speyer Apr 4 '16 at 23:38
  • $\begingroup$ I can only read "we claim... $(1+x)^N$ has positive coefficients" $\endgroup$ – leonbloy Apr 4 '16 at 23:44
  • $\begingroup$ @leonbloy Oops! Thanks. $\endgroup$ – David E Speyer Apr 5 '16 at 0:05
5
$\begingroup$

Call $S$ the set of polynomial satisfying the first property.

It is straightforward to show that if $P,Q$ are two nonzero polynomials, $PQ \in S \iff P \in S $ and $Q \in S$.

Since $\Bbb R[x]$ has the unique factorisation property, it is enough to understand who is in $S$ by checking what irreducible polynomial is in $S$.

Obviously, any polynomial with nonnegative coefficient is in $S$ and any one with a positive real root isn't, so we are left with checking polynomials of the form $X^2-aX+b$ for $a,b>0$ and $\delta = a^2/b < 4$.

Let $p(x) = x^2+ax+b$.

We try to show it is in $S$ by multiplying it with $p(-x)$ :
$p(x)p(-x) = x^4 + (2b-a^2)x^2 + b^2$.

It turns out that this polynomial is "less bad" than $p$ : the new polynomial has $\delta' = a'^2/b' = (2-\delta)^2$

If $\delta < 2$ then $p(x)p(-x)$ has nonnegative coefficients, so it is in $S$, which proves that $p$ is in $S$. So values of $\delta$ close to $0$ are good, while values close to $4$ are bad.

The map $f : \delta \mapsto \delta' = (2- \delta)^2$ has two fixed points, $1$ and $4$. Checking the derivatives show that the map is repulsive at $4$. More precisely, $f'(\delta) \in [2 \sqrt 2 ; 4]$ for $\delta \in [2+\sqrt 2 ; 4]$, which shows that $f^n(\delta)$ eventually gets lower than $2$ after some $n = \Theta(-\log(4 - \delta))$ steps.

This shows that every degree $2$ irreducible polynomial $x^2+ax+b$ is in $S$, and now we know exactly which irreducible polynomials are not in $S$ (the $x-a$ for $a>0$)

So $p$ is in $S$ if and only if it has no positive real root.

$\endgroup$
  • $\begingroup$ when you realize the argument of the roots is a measure of the difficulty, it makes sense to try to push them away from the real axis, by somehow precomposing $p$ with $\sqrt x$. This leads to looking for a $q$ such that $q(x^2)$ has the roots of $p$, and by then the way is clear. $\endgroup$ – mercio Apr 2 '16 at 15:54
  • $\begingroup$ How do you show $PQ\in S$ implies $P$ and $Q$ are in $S$? $\endgroup$ – Jason DeVito Apr 5 '16 at 0:23
  • $\begingroup$ (I forgot to say that I assume $P$ and $Q$ are nonzero) if $PQ \in S$ then there is a nonzero polynomial $R$ such that $(PQ)R$ has nonnegative coefficients. But $(PQ)R = P(QR)$ and so $P(QR)$ has nonnegative coefficients and $QR$ is nonzero, which shows that $P$ is in $S$ $\endgroup$ – mercio Apr 5 '16 at 5:28
2
$\begingroup$

copy of answer on duplicate:

It is not difficult to see that it is enough to prove this for the case $$F(x)=x^2+ax+b$$ where $F$ is irreducible, i.e. $a^2-4b<0$. So consider $$(x^2+ax+b)\sum_{i=0}^\infty c_ix^i$$ We want to show that we can choose the $c_i$ to be equal to $0$ for $i>N$ for some $N$, and still have all non-negative coefficients. Now: $$c_0b\geq 0\Leftrightarrow c_0\geq 0$$ we set, to make things easier $c_0=1$. Then the next condition reads $$c_0a+c_1b\geq 0\Leftrightarrow c_1\geq -\frac{a}{b}$$ Again, to make things simple, set $c_1=-\frac{a}{b}$. The next condition reads $$c_2b+c_1a+c_0\geq 0\Leftrightarrow c_2\geq \frac{1}{b}(\frac{a^2}{b}-1)=\frac{a^2}{b^2}-\frac{1}{b}$$ Now if $\frac{a^2}{b^2}-\frac{1}{b}\leq 0$ we are done, since we can set $c_2=c_3=\dots=0$. If not, we set $c_2=\frac{a^2}{b^2}-\frac{1}{b}$. The next condition reads $$c_3b+c_2a+c_1\geq 0\Leftrightarrow c_3\geq \frac{1}{b}\left(\frac{a}{b}-\frac{a^3}{b^2}+\frac{a}{b}\right)=\frac{2a}{b^2}-\frac{a^3}{b^3}$$ Again, if $\frac{2a}{b^2}-\frac{a^3}{b^3}\leq 0$ we are done by setting $c_3=c_4=\dots=0$. If not, we set $c_3=\frac{2a}{b^2}-\frac{a^3}{b^3}$. The next condition reads $$c_4b+c_ca+c_2\geq 0\Leftrightarrow c_4\geq \frac{1}{b}\left(\frac{1}{b}-\frac{a^2}{b^2}+\frac{a^4}{b^3}-\frac{2a^2}{b^2}\right)=\frac{a^4}{b^4}-\frac{3a^2}{b^3}+\frac{1}{b^2}$$ This process keeps repeating.

The next step is to find a closed form for this sequence of lower bounds. Therefore we define

$$g(n,m)=\begin{cases} 0 &\text{ if } n>m\\ 0 &\text{ if } n\not\equiv m\mod 2\\ (-1)^{\frac{m+n}{2}}\binom{\frac{m+n}{2}}{n} &\text{ otherwise} \end{cases}$$ Then the conditions read $$c_n\geq \sum_{m=0}^n \frac{a^{m}}{b^{m/2+n/2}}g(n,m)=\frac{1}{b^{n/2}}\sum_{m=0}^n \left(\frac{a}{\sqrt{b}}\right)^mg(n,m)$$ And so it suffices to prove that for all $a,b$ with $a^2-4b<0\Leftrightarrow \frac{a}{\sqrt{b}}<2$, the expression $\sum_{m=0}^n \left(\frac{a}{\sqrt{b}}\right)^mg(n,m)$ will be $\leq 0$ for some $n>0$.

To prove this, we use inspiration from this paper. Write $$H_n(x)=\sum_{m=0}^n (x)^mg(n,m)$$ Then using the substituion $x=2\cosh(z)$ we find that $$H_n(x)=\pm\frac{\sinh((n+1)z)}{\sinh(z)}$$ So $$H_n(x)=0\Leftrightarrow z=\frac{i\pi k}{n+1}, k\in\{1,\dots,n\}\Leftrightarrow x=2\cosh\left(\frac{i\pi k}{n+1}\right)\in(-2,2)$$ From here it is easy to finish the proof: for $n$ big enough we will be able to find $k$ such that $$\frac{a}{\sqrt{b}}\in \left[2\cosh\left(\frac{i\pi k}{n+1}\right),2\cosh\left(\frac{i\pi (k+1)}{n+1}\right)\right]$$ and $H_n(x)$ is non-positive on this interval.

Note that the condition of irreduciblity of $x^2+ax+b$ is nicely used, since it ensures that $\frac{a}{\sqrt{b}}$ is in the range $[-2,2]$ where $H_n(x)$ switches sign

To see what this looks like in the case mentioned by Arthur in the comments: we first create a small table with values for $g(n,n)$:

$$ \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & -3 & 0 & 1\\ 0 & 0 & 0 & 0 & -1 & 0 & 4 & 0 & -3 & 0\\ 0 & 0 & 0 & 1 & 0 & -5 & 0 & 6 & 0 & -1\\ 0 & 0 & -1 & 0 & 6 & 0 & -10 & 0 & 4 & 0\\ 0 & 1 & 0 & -7 & 0 & 15 & 0 & -10 & 0 & 1\\ -1 & 0 & 8 & 0 & -21 & 0 & 20 & 0 & -5 & 0 \end{pmatrix} $$

So the conditions read

$$c_0 \geq 1$$ $$c_1 \geq \frac{1.9}{1}=1.9$$ $$c_2 \geq 1.9^2-1=2.61$$ $$c_3 \geq 2*1.9-1.9^3=3.059$$ $$c_4\geq 3.2021$$ $$c_5\geq 3.02499$$ $$c_6\geq 2.545381$$ $$c_7\geq 1.8112339$$ $$c_8\geq 0.89596341$$ $$c_9\geq -0.108903421$$ This is smaller then $0$, so we can set $c_9=c_{10}=\dots=0$, and find $$T(x)=1+1.9x+2.61x^2+3.059x^3+3.2021x^4+3.02499x^5+2.545381x^6+1.8112339x^7+0.89596341x^8$$ will work, and indeed $$(x^2-1.9x+1)(1+1.9x+2.61x^2+3.059x^3+3.2021x^4+3.02499x^5+2.545381x^6+1.8112339x^7+0.89596341x^8)=1 + 4.440892098500626\dot{}10^{-16} x^3 + 4.440892098500626\dot{}10^{-16} x^6 + 4.440892098500626\dot{}10^{-16} x^7 + 0.108903 x^9 + 0.895963 x^{10}$$ I think it's safe to say that, without rounding errors, we would find $$(x^2-1.9x+1)(1+1.9x+2.61x^2+3.059x^3+3.2021x^4+3.02499x^5+2.545381x^6+1.8112339x^7+0.89596341x^8)=1 + 0.108903 x^9 + 0.895963 x^{10}$$

So it's not suprising that Arthur conjectured that this is a counter example, since it requires a rather arbitrary looking degree $8$ polynomial.


for the other test case: $F(x)=x^4-x+1$: we factor over $\mathbb{R}$, and find one quadratic that already has positive coefficients, and the quadratic $$G(x)=0.713639-1.45427 x+x^2$$ Using the algorithm, we find $$c_0=1, c_1\geq 2.03782 c_2\geq 2.75145, c_3\geq 2.75144, c_4\geq 1.75142, c_5\geq -0.286423$$ so we are done, and $$(0.713639-1.45427 x+x^2)(1+2.03782x+2.75145x^2+2.75144x^3+1.75142x^4)=1.75142x^6+0.204402x^5+0.713639$$

$\endgroup$
0
$\begingroup$

The equivalent statement of the second statement implies the first statement is there exists a nonzero polynomial $Q(x)$ with real coefficients such that at least one coefficient of $P(x)Q(x)$ is negative implies there exists a real number $a>0$ such that $P(a)=0$. But this statement is false since if we take $P\left( x \right) = {x^2} + 1$ and $Q\left( x \right) = - x$ then the coefficients of $P(x)Q(x)$ are all negative. But $P(x)$ has no positive real root.

$\endgroup$
  • 3
    $\begingroup$ The negation of “all coefficients are positive” is “at least a coefficient is nonpositive”. Assuming that zero coefficients should be disregarded (as it seems to be apparent from the question), the correct negation is “at least a coefficient is negative”. Certainly not “all coefficients are negative”. $\endgroup$ – egreg Apr 2 '16 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.