# Why are there at most $n-1$ positive roots for polynomials with prime powers?

I was attempting to solve this old contest math problem posted Show that a matrix has positive determinant yesterday and I realize that I don't even know why the hint provided is true.

From that post: "For a natural number $i>0$, let $p_i$ be the $i$th prime number, that is, $p_1=2, p_2=3, p_3=5,...$. ... The hint provided is to use the fact that the polynomial $P(x)=a_nx^{p_n}+a_{n-1}x^{p_{n-1}} + \cdots + a_1x^{p_1}+a_0x^{p_1}$ has at most $n-1$ positive roots for all real constants."

I think the hint itself is maybe incorrect stated since $p_1$ is listed twice so I'll strengthen it a bit: $P(x)=a_nx^{p_n}+a_{n-1}x^{p_{n-1}} + \cdots + a_1x^{p_1}$ has at most $n-1$ positive roots for all real constants.

Is there a name for polynomials with only prime powers? Can anyone shed light on why this is true?

• Have you tried using Descarte's rule of signs? – OnceUponACrinoid Jun 7 '15 at 16:35

It seems that it doesn't have anything to do with primes.

Let $0=r_0 < r_1 < \cdots <r_n$ be integers. I claim that $P_n(x)=\sum_{i=0}^n a_i x^{r_i}$ has at most $n$ positive zeros.

Let's proceed by induction. When $n=0$, it's obvious.

Suppose the statement holds for $n=k$.

If $P_{k+1}(x)$ has $k+2$ positive zeroes, then its derivative $P_{k+1}'(x)=\sum_{i=1}^{k+1} r_i a_i x^{r_i-1}$ must have at least $k+1$ positive zeros. This means that $\sum_{i=1}^{k+1}r_i a_i x^{r_i-r_1}$ also has at least $k+1$ positive zeros, which contradicts to the induction hypothesis.

$\therefore P_n(x)$ has at most $n$ positive zeros.

This proves the statement in your question.

WLOG, let $a_n$ be positive. Now there are only $n-1$ coefficients left! hence the maximum number of sign changes possible is also exactly $n-1$, hence by Descartes rule of signs, that is the maximum possible number of positive roots.