Roots over a field.
So this is one of my favorite propositions, but it doesn’t have a name.
Well it doesn’t have a name in this course, and it doesn't have a name in general, but
polynomials over any field F of degree n greater than or equal to 1 have
at most n roots. Okay?
And it turns out that - so, you can approach this in
two ways, you can try to approach this by contradiction or you can try to approach this by induction.
The reason why I avoid using contradiction is because
what's going to happen is you end up with what I like to call a “dot dot dot argument”, where
what you're doing is you do some work and you say, “Well just repeat this work
you know because n is a finite number you have to only repeat this finitely many times.”
When you want to write a proof like that to actually write it out formally, you
probably are going to need to use induction.
So that's what we're going to use here, instead of using a “dot dot dot argument”,
we're going to actually just formally prove this by induction.
This is a formal proofs class so we should probably try to be as formal as we can.
So let P of n be the statement that all polynomials over F
of degree n have at most n roots.
So we prove this by induction.
So what does induction need? Need a base case, inductive hypothesis, and inductive conclusion.
So notice here that I've outlined what P of n actually is
and I find that for a lot of students learning induction for the first time,
this is a very useful trick.
Actually write down what you're trying to prove.
Make sure you understand where the n falls, so here the n
falls in two spots, there's one spot and there's another spot,
and once you have that, really understand what the statement is,
you can try to go through the proof.
I really encourage students to not just try to…
not just try to blindly go through a proof. Really try to understand what you're trying to prove
and then try to prove it. That sounds obvious, but a lot of students will try to go through
a question without knowing what the question’s asking.
Make sure you understand the statement of the question.
If you don't understand the statement, it's very difficult to actually go through a proof.
Okay, so let's proceed.
Base case, well the base case, what does the base case say?
All polynomials of degree 1 have at most 1 root.
Okay, so grammatically it's not correct, but that's fine.
So when n equals 1, let's take our linear polynomial,
it’s degree 1 a x plus b inside our polynomial ring over F,
with a non-zero, right? We know that a is non-zero because it has degree 1.
Then if I solve for this, if I find a root of this, I can
see that x is equal to negative a inverse times b is a root.
Notice that this makes sense because
a is a non-zero element, which is invertible in a field,
and I’m multiplying by negative 1 and by b, which both are in my field.
This is perfectly reasonable as an element.
So this must be a root of our polynomial
and this must be in our field, we're done.
So we found a root.
This could be 0, that's perfectly fine.
So the base case, all linear polynomials have a root over a field,
that's done.
Inductive hypothesis, well we're just going to assume that P k is true for some
natural number k.
So don't forget, quantify your variables,
k is inside N, and it's for some and not for all.
So we're assuming that P k is true for some, right? If you assume that P k is true for all
natural numbers k, then you're done, there's nothing to prove, right?
You've assumed that your statement is true all the time,
but what we're doing is we're assuming this is true for some
value k and we're going to try to prove that it's true for k plus 1. It’s that domino effect.
I'm going through this inductive proof, again, kind of slowly
just to remind ourselves what induction is. We'll need
all of these elements of this proof a little bit later.
So assume that P k is true, then how do we prove P k plus 1?
Well what do we need to do? We need to take a degree k plus 1 polynomial
and show that it has at most k plus 1 roots.
Now we're going to do something a little bit sneaky but that's pretty clever.
So take our degree k plus 1 polynomial.
If it has no roots,
so if there's no root of the polynomial, then you're done, right?
I mean 0 is less than k plus 1 for sure.
So you're done if you have no roots, so we might as well assume that we have a root.
So let's call it c, alright, so we have some root,
say c, is an element of our field F.
By the Factor Theorem, since we have a root, we know that x minus c must be a factor of p of x,
so we're going to write p of x as
x minus c, times q of x for some polynomial q of x
of degree k, right? We also know, again, because the degree
of the product is the sum of the degrees.
x minus c is degree 1,
p of x is degree k plus 1, so therefore q of x must have degree k.
By the inductive hypothesis what do we know? Well we know that
q of x is a degree k polynomial, so we can apply the induction hypothesis. We've
gotten down to a smaller case, that's the whole idea behind induction, right?
Take some bigger case, and break it down.
Sometimes you break it down into, you know…
usually you break it down to degree 1 and degree k, or
something that depends on 1 so then it depends on k.
Sometimes you break it down like in the Fundamental Theorem of Arithmetic,
you broke it down into very smaller parts.
You know so you had some n and you broke it down to two factors, that's possible as well.
But the key is you break it down to a smaller case that you
know something about because of your induction hypothesis.
q of x is degree k, therefore it has at most k roots.
q of x has at most k roots, x minus c has 1 root,
k plus 1 is k plus 1, p of x has at most k plus 1 roots.
Notice that you could have repetition,
c might be a repeated root, that's perfectly reasonable.
We've already talked about the case where p of x has no roots,
right, so it is possible for a polynomial to have no roots,
but that's fine, that's definitely less than n.
And we're done. So therefore, by the Principle of Mathematical Induction,
P of n is true for all natural numbers n,
so this last little concluding statement wraps it all up nicely.
That's the major ideas here.