Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $p(x)$ be a non-zero polynomial in $F[x]$, $F$ a field, of degree $d$. Then $p(x)$ has at most $d$ distinct roots in $F$.

Is it possible to prove this without using induction on degree? If so, how can I do this?

share|improve this question
    
Assume it has $d+1$ roots. Let $P(x)(x-x_1)(x-x_2) \cdots (x-x_{d+1})=0 \implies P(x)$ is of degree $d+1$. (Note that $x$ gets multiplied $d+1$ times). –  Inceptio May 27 '13 at 10:23
1  
@Inceptio How do you show that the degree of the polynomial is $d+1$? You're using induction somewhere. ;-) –  egreg May 27 '13 at 10:24
    
@Inceptio aren't you using induction then? –  Ittay Weiss May 27 '13 at 10:24
    
@IttayWeiss: $x$ gets multiplied $d+1$ times is induction? –  Inceptio May 27 '13 at 10:26
1  
I don't think this is possible without using directly or indirectly induction... –  DonAntonio May 27 '13 at 11:00

3 Answers 3

If $p(x)$ were to have more than $d$ distinct roots in $F$, then it would have at least $d+1$ linear factors $(x - r_1), (x - r_2), \cdots$. This is impossible.

(Edit: see also Inceptio's comment.)

share|improve this answer
2  
and this uses induction.... –  Ittay Weiss May 27 '13 at 10:24
1  
@IttayWeiss The OP desired a proof of this new statement not using induction on the degree of the polynomial. I doubt the OP wants to prove this without induction at all, i.e. s/he is OK with using facts which were proven before with induction. Indeed I would bet this result (and many much more fundamental results) are provably impossible without mathematical induction at all. –  Goos May 27 '13 at 10:32
    
It is presumably already shown that the product of any number of polynomials has degree equal to the sum. The OPs question is undoubtedly okay with this preproven result. –  Goos May 27 '13 at 10:33
    
this may very well be the case. Perhaps OP should clarify what is precisely allowed and what is not. –  Ittay Weiss May 27 '13 at 10:34
    
@Goos: I'm not really quite sure about how it is or it is not an induction.? –  Inceptio May 27 '13 at 10:39

I'm not sure if using the residue theorem counts, and this only works over $\Bbb C$, but :

Look at $\int P'(z)/P(z) \;dz$ where you integrate on a circle $|z| = r > |x_i|$.

As $r \to \infty$, this is equivalent to $\int d/z \;dz = 2id\pi$.
Meanwhile, the residue theorem says that the integral is $\sum 2i\pi \mu_i$ where $\mu_i$ is the multiplicity of the root $x_i$. Hence the number of roots, counted with their multiplicity, is equal to $d$, the degree of the polynomial.

share|improve this answer
1  
I would +1, because this is a cute method. However, this proof fails over a general field $F$, and thus doesn't rigorously answer the OP's question. –  Goos May 27 '13 at 10:37

If $p(x)=0$ has a root $x=a$, then $p(a)=0$ and $p(x)=p(x)-p(a)$.

$p(x)-p(a)$ is the sum of terms like $c_rx^r-c_ra^r=c_r(x-a)(x^{r-1}+ax^{r-2}+a^2x^{r-3}+ \dots +a^{r-1})$

And since $x-a$ is a factor of every term, it is a factor of $p(x)$. So every root gives us a linear factor.

Suppose $p(x)=k(x-a_1)(x-a_2) \dots (x-a_d)$ of degree $d$ has the $d$ roots $a_1 \dots a_d$ and $b$ is distinct from all of these, then $p(b)$ is a product of non-zero factors, so cannot be equal to zero.

Is this a proof without induction? Difficult to say. For example, how do we prove that if $r$ divides each of $e_1, e_2 \dots e_n$ then it divides their sum?

But the division step, with $p(x)=(x-a)q(x)$ and $q(x)$ having strictly lower degree than $p(x)$ leads to a descending sequence of integers (the orders of the polynomials obtained by successive divisions) - and what we need to know for that is that (i) any strictly descending sequence of non-negative integers is finite; and (ii) we can bound the length of the sequence by $d$ - and we can do this by observing that there are $d$ non-negative integers less than $d$.

So it all depends on the properties of integers that we are allowed to assume - and that is because we need to say things about the degree of $p(x)$ - an integer, and we also need to do things like indexing the coefficients.

share|improve this answer

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.