# Lower Bound of a Coefficient

Fix $\epsilon >0$. Suppose $p_{n}(z) = z^{n}+a_{n-1}z^{n-1}+ \cdots + a_{0} \in \mathbb{Z}[x]$ is irreducible and has all positive real roots. Show that independently of $n$ except for finitely many explicitly computable exceptions that $|a_{n-1}| \geq (2-\epsilon)n$.

The sum of the roots is $-\frac{a_{n-1}}{a_n}$ which is $-a_{n-1}$. So $-a_{n-1} >0$ which means that $a_{n-1} \leq 0$. So $|a_{n-1}| = -a_{n-1}$. The problem can then be rephrased as follows: Show that the sum of the roots of the above polynomial is $\geq (2-\epsilon)n$. Could we use a proof by contradiction? I think irreducibility is an important property here.

Source: Computational excursions in analysis and number theory by P Borwein

-
This is not true as stated. For example, z-1 satisfies the premises but not the conclusion. – Chris Eagle Jan 3 '11 at 4:33
The correct statement is: for all $\epsilon>0$ there is $N>0$ such that for all $n \geq N$ and polynomials as stated, $|a_{n-1}| \geq (2-\epsilon)n$. – Yuval Filmus Jan 3 '11 at 4:40
What is the source of the problem? – Jonas Meyer Jan 3 '11 at 4:48

Given $x_1,x_2,\dots,x_{n-1},x_n\in \mathbb R^+$ are the $n$ roots of $p(z)=z^n+a_{n-1}z^{n-1}+a_{n-2}z^{n-2}+\cdots+a_1z+a_0\in\mathbb Z[x]$ we have that $a_{n-1}=-\sum_{i=1}^nx_i$ and

$$a_{n-2}=\sum_{i=1}^n\sum_{j=1\atop j\ne i}^nx_i\cdot x_j={a_{n-1}^2-\sum_{i=1}^nx_i^2\over 2}$$

By the givens, we have that $a_{n-2}\in\mathbb Z\setminus\mathbb Z^-$. Further, assuming that $n\gt 1$, we have that $a_{n-2}\in\mathbb Z^+$ since it is a sum of all-positive reals. Then we have that

$$a_{n-2}={a_{n-1}^2-\sum_{i=1}^nx_i^2\over 2}\ge 1$$

$$\implies a_{n-1}^2\ge 2+\sum_{i=1}^nx_i^2\ge 3\implies |a_{n-1}|\ge 2=(2-1)\cdot 2\tag 1$$

Applying the same process, we consider $a_{n-3}$ which, for $n\gt 2$, must be such that $-a_{n-3}\in\mathbb Z^+$:

$$-a_{n-3}=\sum_{i=1}^n\sum_{j=1\atop j\ne i}^n\sum_{k=1\atop k\ne i,j}^nx_i\cdot x_j\cdot x_k={|a_{n-1}^3|-\sum_{i=1}^nx_i^3-3\sum_{i=1}^n\sum_{j=1\atop j\ne i}^nx_i^2\cdot x_j\over 6}\ge 1$$

$$\implies |a_{n-1}^3|\ge 6+\sum_{i=1}^nx_i^3+3\sum_{i=1}^n\sum_{j=1\atop j\ne i}^nx_i\cdot x_j^2\tag 2$$

From $(1)$ we have $\sum_{i=1}^nx_i^2\ge1$, so we have that

$$3\sum_{i=1}^n\sum_{j=1\atop j\ne i}^nx_i\cdot x_j^2=3\sum_{i=1}^n\left(x_i\sum_{j=1\atop j\ne i}^nx_j^2\right)\ge 3$$

$$\implies |a_{n-1}^3|\ge 9\gt 8\implies |a_{n-1}|\ge 3=(2-1)\cdot 3=(2-0.5)\cdot 2$$

The set of sums relative to $|a_{n-1}^n|$ is based on the multinomial coefficients. In particular, note that the divisor chosen (for $a_{n-2},2$, for $a_{n-3},6$, etc.) is always $n!$, and we also have that the sum over all coefficients in a multinomial is $m^n$ for $m$ terms raised to the $n$ exponent. If we set $m=n$ we have exactly one term $n!\cdot x_1\cdot x_2\cdots x_{n-1}\cdot x_n$ in the expansion of $|a_{n-1}^n|=\left(\sum_{i=1}^nx_i\right)^n$.

Then, considering term $a_0$ for $n=k$ we have $|a_{n-k}|\in\mathbb Z^+$:

$$|a_0|=\Pi_{i=1}^nx_i\ge 1$$

and

$$|a_0|={|a_{n-1}^n|-\sum_{i=1}^nx_i^n-n\sum_{i=1}^n\sum_{j=1\atop j\ne i}^n\sum_{l=1}^{[\frac n2]}x_i^l\cdot x_j^{n-l}-\cdots\over n!}\ge 1$$

$$\implies |a_{n-1}^n|\ge n!+\sum_{i=1}^nx_i^n+\cdots$$

With the exception of the $\sum_{i=1}^nx_i^n$ term, we know from a previous iteration ($n=k-1$) that each of the terms added to $n!$ is greater than or equal to the coefficient in front of it; in fact, the $n\sum_{i=1}^n\sum_{j=1\atop j\ne i}^n\sum_{l=1}^{[\frac n2]}x_i^l\cdot x_j^{n-l}$ term is actually greater than or equal to $n\choose 2$ due to also being the sum over all $x_i^l\cdot x_j^{n-l}$ pairings. Further, the sum over all such terms is $r\ge{n^n\over n}=n^{n-1}$ since each sum is over $n$ terms (combining all subterms) and every such sum is individually $\ge 1$. Then we have

$$|a_{n-1}^n|\ge n!+\sum_{i=1}^nx_i^n+\cdots\ge n^{n-1}$$

We have that for all $n\gt 2$, $2^n\le n^{n-1}$, and in fact for all $n\gt 2k, k^n\le n^{n-1}$ ($2^k\ge k$), so given any $k\in\mathbb Z^+$,

$$|a_{n-1}^n|\ge (2k)^{2k-1}\ge k^n\implies |a_{n-1}|\ge k$$

This means that given $\epsilon\gt 0, n\in\mathbb Z^+$ we can choose $k\in\mathbb Z^+$ such that $k\ge (2-\epsilon)n$ and then we have for $m=2k$ the $m$ positive real roots ($x_i$) of $p(z)=z^m+a_{m-1}z^{m-1}+\cdots+a_2z^2+a_1z+a_0\in\mathbb Z[x]$ have sum

$$\sum_{i=1}^mx_i=|a_{m-1}|\ge (2-\epsilon)n$$

Since $m=2k\ge 2\cdot(2-\epsilon)n\ge 2n$, we have demonstrated the existence of $m\gt n$ satisfying the given conditions.

-