# Prove that a polynomial of degree $d$ has at most $d$ roots (without induction)

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?

• 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
• @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
• I don't think this is possible without using directly or indirectly induction... – DonAntonio May 27 '13 at 11:00

## 4 Answers

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.)

• and this uses induction.... – Ittay Weiss May 27 '13 at 10:24
• @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. – 6005 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. – 6005 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.

• 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. – 6005 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.

Okay, here's a proof that honest-to-god seems to avoid induction. Preliminarily, we'll have to know something about the Vandermonde matrix. Define the $n$-by-$n$ Vandermonde matrix $$V(\alpha_0, \cdots, \alpha_{n-1}) := \begin{bmatrix} 1 & \alpha_0 & \alpha_0^2 & \dots & \alpha_0^{n-1}\\ 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1}\\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1}\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & \alpha_{n-1} & \alpha_{n-1}^2 & \dots & \alpha_{n-1}^{n-1} \end{bmatrix}.$$

I'll record a proof of the following lemma that avoids induction; this proof is perhaps conceptually the clearest.

Lemma: $$\det(V(\alpha_0, \cdots, \alpha_{n-1})) = \prod_{1\le i< j \le n} (\alpha_i - \alpha_j)$$ Proof sketch: We write $V:= V(\alpha_0, \cdots, \alpha_{n-1})$. Consider $\det(V)$ as an element of the polynomial ring $\mathbb{Z}[\alpha_0, \cdots, \alpha_{n-1}]$. In this ring, the pairwise relatively prime linear factors $\alpha_i - \alpha_j$ each divide $\det(V)$. By degree considerations, it follows $\det(V) = C\cdot \prod_{1\le i< j \le n} (\alpha_i - \alpha_j)$ for some constant $C\in \mathbb{Z}$. Explicitly comparing coefficients of the polynomials in this equation gives $C = 1$ (this is a little work, something something exercise for reader).

Now, let $p(x) \in F[x]$ and write $p(x) = a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_0$, where not all the $a_i$ are zero. If $p$ has $n$ roots $r_0, \cdots, r_{n-1}$ in an algebraic closure $\overline{F}$, then $$V(r_0, \cdots, r_{n-1}) \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{bmatrix} = 0,$$ which implies $\det(V)= 0$, so $r_i = r_j$ for some $i$, $j$.

In particular, $p$ has at most $n-1 = \deg(p)$ distinct roots in $\overline{F}$.

Remark: As mentioned here, if you push this idea a little further by applying Cramer's rule to the Vandermonde matrix, you get Lagrange interpolation!