Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can I prove, that a polynomial function $$f(x) = \sum_{0\le k \le n}a_k x^k\qquad n\in\mathbb N,\ a_k\in\mathbb C$$ is zero for at most $n$ different values of $x$? (Except $n=0$ where $f(x)$ is $0$ in all cases)

share|cite|improve this question
8  
Induction. If it has a root r, divide by (x - r). – Qiaochu Yuan Mar 8 '11 at 19:56
1  
Isn't this the fundamental theorem of algebra? Wikipedia (en.wikipedia.org/wiki/Fundamental_theorem_of_algebra) gives several proofs. – please delete me Mar 8 '11 at 19:56
2  
Hint: First show that $f(\alpha) = 0$ iff $x-\alpha$ divides $f(x)$ and then use induction on the degree of $f$ – kahen Mar 8 '11 at 19:57
    
Is there any background one needs to consider? For instance, is this some problem assigned in some course? If so, which course? – Aryabhata Mar 8 '11 at 20:01
4  
@Fuz: No, it is not "part" of fundamental theorem. It might be what you call a "Corollary", but it has other easier proofs. – Aryabhata Mar 8 '11 at 20:13
up vote 16 down vote accepted

Using Linear Algebra,

If the $n+1$ distinct roots are $\alpha_i$, then we have that $x = [a_0, a_1, \dots, a_n]^{T}$ is a solution of $Ax = 0$ where $A$ is the Vandermonde matrix using the $\alpha_i$.

Since the Vandermonde matrix is invertible for distinct $\alpha_i$, it follows that $x = [0, 0, \dots, 0]$.

Thus if $a_j \neq 0$ for some $j$, then your polynomial can have at most $n$ different roots.

Note: This is basically saying that given a field $K$, any polynomial of degree $n$ in $K[x]$ has at most $n$ distinct roots.

Fundamental Theorem of Algebra is an assertion of the fact that $\mathbb{C}$ is algebraically closed, and the $K$ above need not be algebraically closed.

share|cite|improve this answer

You don't need the fundamental theorem of algebra or the Vandermonde determinant, only the factor theorem.

Proposition: A polynomial of degree at most n with more than n roots vanishes identically.

Proof: By induction. The base case is $n=0$, which is obvious. Now take a polynomial f of degree at most n, and let $x_1,\ldots,x_{n+1}$ be distinct roots of f. By the factor theorem, we can write $$f(x) = (x-x_{n+1})g(x)$$ where g plainly has degree at most $n-1$. Now substitute $x = x_i$ for $i=1,\ldots,n$. For all these values of x the left hand side vanishes and the factor $(x_i-x_{n+1})$ is nonzero. Hence all these $x_i$ must be roots of g and by induction g is identically zero. QED

This same proof works over any field (or even integral domain).

share|cite|improve this answer
    
for polynomials $f,g\in K[x]$ there are $q,r\in K[x]$ such that $f=qg+r$ with $\text{deg}(r)<\text{deg}(g)$ or $r=0$ (polynomial division). if $f(\alpha)=0$, take $g(x)=x-\alpha$ to get $0=f(\alpha)=r$. Hence $r=0$ and $f(x)=q(x)(x-\alpha)$. – yoyo Mar 8 '11 at 21:18

The following literature may be of use here:

Theorem. A polynomial $\text{f}$ of degree $\text{n}$ over a field $\text{F}$ has at most $\text{n}$ roots in $\text{F}$.*

Proof. The results is obviously true for polynomials of degree $0$ and degree $1$. We assume it to be true for polynomials of degree $n-1$. If $a$ is a root of $f$, $f=(x-a)q$ where $q$ has degree $n-1$. Since $f(b)=0$ if and only if $a=b$ or $q(b)=0$, it follows by our inductive assumption that $f$ has at most $n$ roots. $\Box$

share|cite|improve this answer
1  
Most elegant proof of the lot. – Noldorin Apr 30 '14 at 17:25
    
It's obvious that $f=(x-a)q$ if $a$ is a root, but how can that be demonstrated? – FUZxxl Feb 26 at 16:57

Just a clarification here. The Fundamental Theorem of Algebra says that a polynomial of degree n will have exactly n roots (counting multiplicity). This is not the same as saying it has at most n roots. To get from "at most" to "exactly" you need a way to show that a polynomial of degree n has at least one root. Then you can proceed by induction.

There are lots of different kinds of proofs that a polynomial must have at least one root. None of them are totally trivial.

share|cite|improve this answer

There's probably a simple proof based on the fact that every polynomial of degree n has at most (n - 1) turning points. Clearly and without rigorous proof this points directly to the more general quality of a polynomial of degree n : it can only take on at most n identical values. And since the roots are a specific case when the value is 0, there clearly can be at most n roots.

share|cite|improve this answer

Suppose that the polynomial is defined in the field $\mathbb C$[X] as:
$$f=\sum_{i=0}^na_iX^i$$ Assume that the polynomial function defined by the above polynomial has $n+1$ distinct roots, i.e., $f(x)=0$ for $n+1$ distinct values of x $\in \Bbb C$.
I shall use the theorem:$$\prod_{i=1}^k\left(X-x_i\right)q=f \Longleftrightarrow x_1,...,x_k \text{ are distinct roots of }f\text{, where }q\in\Bbb C[X] $$ Let $n+1$ distinct roots of $f$ are $x_1,...,x_{n+1}$. Hence, by above theorem, we can say that $ \prod_{i=1}^{n+1}\left(X-x_i\right)q=f$. Since the coefficient lie in the field of complex numbers, hence left hand side has degree $n+1$, while $f$ is of degree n. This is impossible, therefore $f$ can have at most n distinct roots.

share|cite|improve this answer

Let $ f $ be a polynomial, such that $ f(r) = 0 $. Define $ f'(x) = \frac{f(x)}{x - r} $. Repeat this process, and consider the degree, $ \deg(f^{(n)}) $.

share|cite|improve this answer
    
Your argument is incomplete. – FUZxxl Jun 15 at 11:30
    
It is so on purpose. I would simply want to point OP in a direction. – M. Fischer Jun 15 at 13:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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