4
$\begingroup$

Ths isn't the proper Fundamental Theorem of Arithmetic (which includes complex roots), but just the maximum number of real roots for polynomial $f(x)$ with real coefficients... which is $deg(f)$.

I believe there isn't a High School-level proof of the full theorem, but is there one of this simpler theorem?

I think there should be a very simple proof using the Factor Theorem:

$$f(a)=0 \iff (x-a) \mid f(x)$$

The only way to have an extra zero is to have an extra factor of $(x-a)$, which increases the degree by one.

Because an extra factor might be the same as one already present, forming a multiple root or zero, the number of distinct roots may be fewer than this. So it is only a maximum.∎

However, I'm not sure how to make this rigorous, or how to show it covers all possible polynomials (i.e. all polynomials can be built up from $(x-a)$ factors - maybe it follows from the Factor Theorem?).

Or maybe there's a completely different, simpler approach?

BTW: I am interested in it as a way to understand the Schwartz-Zippel lemma for Polynomial Identity Testing (a probabilistic algorithm: subtracting the polynomials to get zero if identical, then use the maximum zeros/roots to calculate probability of guessing roots - false positives). The relevant part to this question is:

A polynomial of one variable of degree {d} can vanish at only {d} points without being identically zero The Curious History of the Schwartz-Zippel Lemma

Also at the wikipedia article

a polynomial of degree d can have no more than d roots.

Because the guesses can be made using only integers (I think modulo, making them fields), it seems to me that the simpler theorem for real polynomials should be enough...

$\endgroup$
4
  • 1
    $\begingroup$ If you are trying to show that a polynomial can have no more than $\partial f$ distinct roots, then you can use polynomial division to show the result (that is, if $r_1,...,r_p$ are distinct roots of $f$ then show $\partial f \ge p$). Otherwise, you need to characterise what is meant by a multiple root. As you are probably aware, $x^2+1$ has no real roots. $\endgroup$
    – copper.hat
    Commented May 14, 2018 at 5:11
  • $\begingroup$ @copper.hat Thanks, yes that's what I want, for reals. I think I follow you: for each of the $p$ distinct real roots $r_p$, there is a distinct factor $(x-r_p)$, and (because there may be other distinct factors, duplicate factors, and factors thst can't be reduced, like $x^2+1$), the degree is at least $p$. Starting from distinct roots avoids the problem. Proving an inequality means we needn't prove the converse. I forgot about complex roots, and they mean I was wrong: one can't build up every polynomial from factors like $(x-r), r \in \Bbb R$, like your example $x^2+1$. $\endgroup$ Commented May 14, 2018 at 8:17
  • $\begingroup$ I think the basic fact for showing the result is that $\partial (f \cdot g) = \partial f + \partial g$. Hence each distinct, real root adds one to the degree. $\endgroup$
    – copper.hat
    Commented May 14, 2018 at 16:10
  • $\begingroup$ @copper.hat I see that (and the idea is in my sketch), but I have trouble putting it all together into a rigorous proof - and seeing/showing that it is indeed rigorous. I was hoping there'd be a standard detailed proof - but I guess that is all done on the proper FTA. $\endgroup$ Commented May 15, 2018 at 9:44

1 Answer 1

0
$\begingroup$

If $P(x)$ is a polynomial such that $P(a)=0$ then it is only possible when it can be expressed as $(x-a)F(x)$ because when we subsitute $x=a$ we get $0$
The second statement is also obvious,
Let $P(x)$ have $p$ roots then it may be written as $(x-p_1)(x-p_2)...(x-p_p)$ which is a polynomial of degree p.

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .