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?

  • $\begingroup$ 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). $\endgroup$ – Inceptio May 27 '13 at 10:23
  • 1
    $\begingroup$ @Inceptio How do you show that the degree of the polynomial is $d+1$? You're using induction somewhere. ;-) $\endgroup$ – egreg May 27 '13 at 10:24
  • $\begingroup$ @Inceptio aren't you using induction then? $\endgroup$ – Ittay Weiss May 27 '13 at 10:24
  • 1
    $\begingroup$ @IttayWeiss: $x$ gets multiplied $d+1$ times is induction? $\endgroup$ – Inceptio May 27 '13 at 10:26
  • 1
    $\begingroup$ I don't think this is possible without using directly or indirectly induction... $\endgroup$ – DonAntonio May 27 '13 at 11:00

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

  • 2
    $\begingroup$ and this uses induction.... $\endgroup$ – Ittay Weiss May 27 '13 at 10:24
  • 1
    $\begingroup$ @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. $\endgroup$ – 6005 May 27 '13 at 10:32
  • $\begingroup$ 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. $\endgroup$ – 6005 May 27 '13 at 10:33
  • $\begingroup$ this may very well be the case. Perhaps OP should clarify what is precisely allowed and what is not. $\endgroup$ – Ittay Weiss May 27 '13 at 10:34
  • $\begingroup$ @Goos: I'm not really quite sure about how it is or it is not an induction.? $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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