9
$\begingroup$

I am curious why the following is true. The text I am reading is "An Introduction to Numerical Analysis" by Atkinson, 2nd edition, page 133, line 4.

$p(x)$ is a polynomial of the form:

$$ p(x) = b_0 + b_1 x + \cdots + b_n x^n$$

If $p(x) = 0$ for all $x$, then $b_i = 0$ for $i=0,1,\ldots,n$.

Why is this true? For example, for $n=2$, I can first prove $b_0=0$, then set $x=2$ to get a linear system of two equations. Then I can prove $b_1=b_2 = 0$. Similarly, for $n=3$, I first prove $b_0=0$, then I calculate the rank of the resulting linear system of equations. That shows that $b_1=b_2=b_3=0$. But if $n$ is very large, I cannot keep manually solving systems of equations. Is there some other argument to show all the coefficients must be zero when the polynomial is always zero for all $x$?

Thanks.

  • 8
    Are you familiar with the fact that if $p(a) = 0$, then $p(x)$ is divisible by $x - a$? Use this $n+1$ times.2011-08-28
  • 3
    As explained in the answers, we can solve the problem by showing that a non-zero polynomial of degree $d$ has no more than $d$ roots. However, your approach can be made to work. To carry it out, one uses properties of the [Vandermonde matrix](http://en.wikipedia.org/wiki/Vandermonde_matrix). The details are somewhat more messy than the approach through counting roots, but accessible.2011-08-28
  • 0
    Hi Qiaochu Yuan, can you give me some more hints? I am aware of the Fundamental Theorem of Algebra, which can be found here: http://tutorial.math.lamar.edu/Classes/Alg/ZeroesOfPolynomials.aspx. If I divide a polynomial of degree $n$ by (x-a), and a is guaranteed to be a root (since the polynomial is a horizontal line at $y=0$), then I get as a result, another polynomial with degree $n-1$. After $n-1$ divisions, I get as a result, something like: $d + ex = 0$. $d$ and $e$ might not be the original polynomial coefficients. What would be the next step after this?2011-08-28
  • 1
    *For purposes of argumentation*: false over finite fields...2011-08-28
  • 2
    As you are interested in numerical methods the following is probably not of interest to you, but for the sake of completeness I feel compelled to point out that the conclusion is false, if your domain is finite. A non-zero polynomial can easily vanish at all points of, e.g. $\mathbf{Z}_m$ without being the zero polynomial. The easiest example is the polynomial $p(x)=x^2-x\in \mathbf{Z}_2[x]$ that vanishes at all the elements of $\mathbf{Z}_2$. If you don't study algebra, you can safely ignore this comment for now.2011-08-28

5 Answers 5

10

HINT $\ $ A nonzero polynomial over a field (or domain) has no more roots than its degree, as is easily proved by induction and the Factor Theorem. In fact if every natural was a root then the polynomial would be divisible by $\rm\:(x-1)\:(x-2)\:\cdots\:(x-n)\:$ for all $\rm\:n\in \mathbb N\:,\:$ which yields a contradiction for $\rm\:n\:$ greater than the degree of the polynomial.

Note that the proof of said statement depends crucially on the hypothesis that coefficient ring is an integral domain, i.e. a ring satisfying $\rm\:ab = 0\iff a=0\ \ or\ \ b=0\:.\:$ Over non-domains such as the integers modulo $\rm\:m\:$ not prime, polynomials can have more roots than their degree. In fact if this is true then one can use such roots to factor $\rm\:m\:,\:$ see here.

  • 0
    Following reading Bill Dubuque's, Shawn's, and Qiaochu Yuan's answer, I believe I must agree to the following fact. If a polynomial is equal to zero, then it must be of degree 0, and the coefficient must be set such that $b_0=0$. Since it is degree 0, the other coefficients must also be set to 0.2011-08-28
  • 4
    @jrand: The degree of the polynomial zero is not zero.2011-08-28
8

Note that $p(x)=0$ implies derivatives of all orders are also $0$. Let $x=0$ into $p(x) = b_0 + b_1 x + \cdots + b_n x^n$ to obtain $b_0 = 0$.

Now differentiate both sides: $p'(x) = b_1 + 2b_2 x + 3b_3 x^2 + \cdots + nb_n x^{n-1} $. Let $x=0$ again, and we get that $b_1=0$.

If we continue to differentiate and substitution $x=0$ we will get that $b_k=0$ for $k=0,1,2,\cdots, n$. This idea can easily be made into a rigorous induction proof.

A nice corollary of this result is that two polynomials are equal if and only if they have the same degree and coefficients.

5

If you are willing to accept $\displaystyle \lim_{x \rightarrow \infty}\frac{1}{x^{m}}=0$ and $\displaystyle \lim_{x \rightarrow \infty}x^m=\infty$ for all $m>0$, then you can argue as follows. Suppose you have a polynomial $f(x)=b_nx^n+ \ldots b_0$ with $b_n \neq 0$ and $n\geq 1$, then $$\lim_{x\rightarrow \infty}f(x)=\lim_{x \rightarrow \infty} x^n(b_n+ \ldots \frac{a_0}{x^n})=\lim_{x \rightarrow \infty} x^nb_n=\infty.$$

Since the constant function $0$ does not have this property, it cannot be equal to a polynomial with degree greater or equal to $1$.

1

Let $n\in \mathbb{N}$, and $$p(x)=b_0+b_1x+\ldots +b_nx^n$$ a polynomial of degree at most $n$. If $p(x)=0$ for every $x$, then $b_i=0$ for $i=0,\, 1,\ldots\, n$.

Proof:

By induction on $n$:

If $\deg(p)\leq 1$, then $p(x)=b_0+b_1x$. Since $p(0)=p(1)=0$ you get $b_0=b_1=0$.

Suppose that for any $$r(x)=c_0+c_1x+\ldots +c_nx^n$$ of degree at most $n$, if $r(x)=0$ for every $x$, then $c_i=0$ for $i=0,\, 1,\ldots\, n$. Let $$p(x)=b_0+b_1x+\ldots +b_{n+1}x^{n+1}.$$ Suppose that $p\equiv 0$. Since $p(0)=0$, you get that $b_0=0$. From here, I have two possible arguments. The first, that was my original one, is as follows:

We have $$p(x)=b_1x+b_2x^2+\ldots+b_{n+1}x^{n+1}=x(b_1+b_2x+\ldots+b_{n+1}x^{n}).$$ Then for all $x$, $$\begin{align*} 0&= p(x)\\ 0&= x(b_1+b_2x+\ldots+b_{n+1}x^{n}).\end{align*}$$ Then for any $x\neq 0$, $$q(x):=b_1+b_2x+\ldots+b_{n+1}x^{n}=0$$ If $q\not\equiv 0$, then we have a polynomial of degree at most $n$ with infinitely many roots. This can't be, therefore $q\equiv 0$. Now, $\deg(q)\leq n$ and $q\equiv 0$, therefore by the induction hypothesis, $b_i=0$ for $i=1,\,\ldots ,\, n+1$.

The second argument was inspired by @Ragib Zaman's answer. Just differentiate both sides of $p(x)=0$, then $$b_1+2b_2x+\ldots+(n+1)b_{n+1}x^n=0$$ for all $x$. By the induction hypothesis, $kb_k=0$ for $k=1,\,\ldots,\,n+1$, and this implies that $b_k=0$ for $k=1,\,\ldots,\,n+1$

Since $b_0=0$, this proves that $b_i=0$ for $i=0,\, 1,\ldots,\, n+1$.

  • 0
    In general, by the fundamental theorem of algebra we can say that the number of different roots of a polynomial of degree $n$ is at most $n$. I the argument above $q$ must be identically $0$ because if not we have a polynomial with infinite different roots.2011-08-28
  • 0
    My comment is the hint of @Bill2011-08-28
  • 0
    This induction is flawed because during your nth inductive step you use as a fact a property (for every q of degree n, if q(x)=0 for every nonzero x, then q=0) that the hypothesis at the beginning of the step (for every polynomial p of degree n, if p(x)=0 for every x, then p=0) does not imply.2011-08-28
  • 0
    @Didier Piau: I'm trying to prove a statement about the coefficients of polynomials, not about the polynomials. If I understand correct your comment, you say me that the hypothesis of induction does not implies that the polynomial $q$ is identically $0$. Yes that is true, but i don't pretend it. The fact that $q\equiv 0$ is something that I want to apply my hypothesis of induction.2011-08-28
  • 0
    I think that the answer is now more clear.2011-08-28
  • 0
    You did not read my first comment. Let me rephrase. Your crucial step is: *For every q of degree n, if q(x)=0 for every nonzero x, then q=0*. Why is that? Certainly not by the induction hypothesis you use, since this induction hypothesis reads: *For every r of degree n, if r(x)=0 for every x, then r=0*. The difference is *zero at every x* vs *zero at every NONZERO x*. // A more minor point is that you seem to confuse *degree equal to n* with *degree at most n* (for example q=0 and deg(q)=n are incompatible unless n=-infty). And finally I wonder .../...2011-08-28
  • 0
    .../... if you realize that the assertions that p=0 and that all the coefficients of p are zero, are strictly equivalent, by the very definition of a polynomial. But this is minor compared to the *zero at every x* vs *zero at every nonzero x* stuff. Good luck for the revision!2011-08-28
  • 0
    Yes, are equivalent. If all the coefficients of $p$ are $0$, then $p=0$. I'm in the aim of prove the converse. That is the reason because I insist in statements about the coefficients. My point is: given a proposition that depends on $n$, $P(n)$: if $i)$ $P(1)$ is true $ii)$ $P(n)$ $\Rightarrow$ $P(n+1)$ then $P(n)$ holds for every n. I want to use my $P(n)$ to prove my $P(n+1)$. For this, I need a polynomial of degree $n$ that be equal to $0$ for every $x$. I have $q$ of degree $n$, then I just need that $q(x)=0$ for every $x$. But this hold in the following way: $q(x)=0$ for every.../...2011-08-28
  • 0
    .../... nonzero $x$. If $q\not \equiv 0$, then $q$ is a polynomial of degree $n$ with infinitely many different roots, this can't be. Then $q(x)=0$ for every $x$, then the hypothesis of the inductive step holds and then my $P(n)$ also holds. From this point I think that we agree in how deduce form here the conclusion for the coefficients of the polynomial $p$ of degree $n+1$. In the other hand, what is the definition of polynomial maybe my answer is not worth if is direct of the definition.2011-08-28
  • 0
    What do you think @Didier Piau?2011-08-28
  • 0
    That you finally understood the step that "if q(x)=0 for every nonzero x then q(x)=0 for every x" was missing in your post. That one can hope this step will soon appear (with justification) there and that this is good. (But that you still confuse "degree n" with "degree at most n"...)2011-08-28
  • 0
    Why the -1 to this?2011-08-28
0

A polynomial can be uniquely fitted by knowing its value at $d+1$ points, where $d$ is the degree of the polynomial. If it's 0 at all points, that's clearly more than $d+1$ points.

But we also know that a polynomial can be written as $(x-r_0)(x-r_1)...(x-r_k)$, where the $r_i$ are the roots of polynomial (possibly complex). Again, if there are an infinite number of roots...