Bounds on the maximum real root of a polynomial with coefficients $-1,0,1$

Question

Suppose I have a polynomial that is given a form $$ f(x)=x^n - a_{n-1}x^{n-1} - \ldots - a_1x - 1 $$

where each $a_k$ can be either $0,1$.

I've tried a bunch of examples and found that the maximum real root seems to be between $1,2$, but as for specifics of a polynomial of this structure I am not aware.

Using IVT, we can see pretty simply that $f(1)\leq0$ and $f(2)> 0$ so there has to be a root on this interval, but thats a pretty wide range was wondering if this was previously studied

Answer 1

Note that for $x\geq 2,$ we have

$$f(x)\geq x^n-(1+x+...+x^{n-1})=x^n-{x^n-1 \over x-1}={x^{n+1}-2x^n+1 \over x-1}={x^{n}(x-2)+1 \over x-1}>0.$$

For $0\leq x<1,$ we have

$$f(x)\leq x^n-1<0.$$

So the maximal real root must be in $[1,2).$

---

Further analysis shows these bounds for the maximal root cannot be sharpened within your general class of polynomials.

The lower bound of $1$ is sharp: consider $$f_1(x):=x^n-1,$$ which has a maximal real root at $1$.

The upper bound of $2$ is sharp: consider $$f_2(x):=x^n-(1+x+...+x^{n-1}),$$

which for $x>1$ can be written as

$$f_2(x)={x^{n}(x-2)+1 \over x-1}.$$

Define $\xi:={2n \over n+1}\in [1,2)$ and observe that as $n\to \infty$, $\xi\to 2,f_2(\xi)\to -\infty.$ However, since $f_2(2)>0$, IVT implies that for $n$ large enough, $f_2$ has a root arbitrarily close to $2$.

Answer 2

The following bounds are valid for both the complex as well as any real roots of a monic polynomial $p(x)$ with coefficients in $\{-1, 0, 1\}$. (Monic: the coefficient of $x^n$ is $1$.)

Let's create from the given polynomial a Companion matrix $C$ (see https://en.wikipedia.org/wiki/Companion_matrix), thus, this matrix is similar to (i.e., has the same eigenvalues as) the Characteristic polynomial of some $n$-by-$n$ matrix $A$. (See https://en.wikipedia.org/wiki/Characteristic_polynomial.) But we don't really care about $A$.

The main idea is that the roots of the polynomial $p(x)$ are the values of the eigenvalues of the Companion matrix $C$.

We can give bounds on the eigenvalues of $C$ using the Gershgorin circle theorem (see https://en.wikipedia.org/wiki/Gershgorin_circle_theorem):

Gershgorin. All eigenvalues of any arbitrary real or complex matrix $C$ are located in the union of the following disks (filled circles): each disk is centered at the diagonal value $C_{ii}$ and has radius $R_i = \sum_{j\neq i}|C_{ij}|$ (row sums). Since the transpose of the given matrix has the same eigenvalues, we obtain a second union of disks with radii $R_i = \sum_{j\neq i}|C_{ji}|$ (column sums). We now have 2 sets of disk unions, but since the eigenvalues belong to both, the intersection is where they're located, which gives a better (tighter) bound.

Applying the theorem to our Companion matrix $C$, we observe:

• All centers $C_{ii} = 0$ except for $i = n$, where it is $C_{nn} = -a_{n-1}$
• For $1 < i < n$, radii $R_i = 1+ \max_{j=2}^{n-1}|a_{j-1}| = 1+1 = 2$
• For $i = 1$, $R_1 = |a_0| = 1$
• For $i = n$, $R_n = 1$.

Therefore, all eigenvalues of our Companion matrix $C$, corresponding to all roots of $p(x)$ are located in the union of 2 disks:

• Disk 1: centered at $0$ with radius $2$ (the disk corresponding to $i = 1$ has radius 1, so is completely internal to the larger disk)
• Disk 2: centered at $-a_{n-1}$ with radius $1$

Extremal real values of Disk 2:

• Case $a_{n-1} = -1$: $[-1-1, -1+1] = [-2, 0]$
• Case $a_{n-1} = 0$: $[0-1, 0+1] = [-1, 1]$
• Case $a_{n-1} = 1$: $[1-1, 1+1] = [0, 2]$

Therefore, the union of Disk 1 and Disk 2 gives the following extremal real values:

• Case $a_{n-1} = -1$: $[-2, 0] \cup [-2,2] = [-2,2]$
• Case $a_{n-1} = 0$: $[-1, 1] \cup [-2,2] = [-2,2]$
• Case $a_{n-1} = 1$: $[0, 2] \cup [-2,2] = [-2,2]$

Conclusion: all real roots are in $[-2,2]$.

Answer 3

Starting from @Golden_Ratio's answer,we can have a very good approximation of the largest root of $$g_2(x)=x^{n}(x-2)+1 $$ Computing the first iterate of Householder method with $x_0=2$ we have $$x_1=2-\frac 1{2^n-\frac n2 \left(1+\frac{n+1}{2^{n+2}-2 n}\right)}$$

It is simple to prove that $g_2(x_1)>0$ and $g''_2(x_1)>0$ and, by Darboux theorem, $x_1$ is just a slight overestimate of the solution.

Edit

Using the next order (no name) $$x_1=2-\frac 1{2^n+\frac n 6\left(\frac{2 (n+1) \left(n-3\ 2^n-1\right)}{n^2-\left(2^{n+3}+1\right) n+2^{2 n+3}} -3\right)}$$ For $n=10$, this gives $$x_1=\frac{8302702}{4153389}=\color{red}{1.9990186327}358\cdots$$

while the exact solution is $1.999018632710101$

Answer 4

First of all, about upper bound $2$, polynomials

$$x^n - \sum_{k=0}^{n-1} x^k = x^n - \frac{x^n-1}{x-1}$$

singled out by @Golden_Ratio, whose maximal real root is arbitrarily close to $2$, are indeed known to be extremal ; see here.

Besides, as excellent simulation tools exist in this 21st century, it is good to have a graphical representation of some examples for polynomials with varous degrees, like here (roots of 100 polynomials with degrees between $4$ and $42$) obtained with Matlab :

Different colors correspond to the roots of different polynomials.

Indeed

• Real roots appear to be within $[-2,2]$ with cases very close either to $-2$ or to $2$ (of course, this isn't a proof !).

• Non real roots display a classical trend : aggregation in the vicinity of the unit disk. See the rich description here and the fascinating Baez page where polynomials with $\pm1$ coefficients are mentionned.