"Low degree Polynomials do not have too many roots" - what exactly does this mean?

Question

I am watching this video from a playlist on Algebraic Coding theory - https://www.youtube.com/watch?v=XH7npgKN93k&list=PLkvhuSoxwjI_UudECvFYArvG0cLbFlzSr&index=16 - this particular video in the playlist is titled "Polynomials over Finite Fields".

At approximately 1:28, she says "Low degree Polynomials do not have too many roots".

When she says this, on the white board she has written - "A non-zero polynomial $f$ of degree $\le d$ has $\le d$ roots", she also says that this is what she means more precisely. However it's still not precise or clear to me.

She repeats this multiple times over this video & even in the next video of the playlist. She says this fact is so important, that she has a cartoon parrot say "Low degree Polynomials do not have too many roots" multiple times.

It's not clear to me what exactly she means here?

• What is "Low Degree"?

• What is "Too many"?

Neither of these are precise terms, so it's difficult to figure out what she means.

Does she mean that if the field is $\mathbb F_q$ & $d$ is very, very small in relation to $q$, then the number of roots which $f$ has is very small as compared to the number of elements in $\mathbb F_q$?

Answer 1

It seems to me like "low degree polynomials don't have too many roots" is a kind of slogan which is meant to be memorable. This slogan is made precise by the statement "A (nonzero) degree $\leq d$ polynomial over $\mathbb{F}_q$ has $\leq d$ roots."

In fact, this slogan is true more broadly too, which is one reason to phrase it as an imprecise slogan. It's true in lots of settings, and so anytime you encounter a new kind of polynomial (with coefficients in a field, say, but we can relax this too), you should expect low degree polynomials to have few roots. You can then search the literature for a precise theorem witnessing this intuition. This makes the slogan more useful than any single theorem statement.

For example, you might ask about multivariate polynomials, say $p(X,Y) \in \mathbb{F}_q[X,Y]$. Following our slogan, you should expect there to be a relationship between the degree of $p$ and the expected number of roots, but now the literal naive degree bound is false! However, the slogan can still be made precise by the Schwartz-Zippel Lemma:

Choose $a,b \in \mathbb{F}_q$ randomly. The probability that $p(a,b) = 0$ is at most $\frac{\text{deg}(p)}{q}$

So, again informally, we see that polynomials of "small degree" (relative to $q$, say) have few roots (in the sense that we expect to take a while to randomly find one).

---

As you progress in mathematics, these kinds of informal statements become much more useful than their precise theorems -- at least for doing mathematics quickly. Usually you have some idea of how a proof might work, based on these kinds of heuristics, and then you fill in the heuristics one by one until you're left with an honest proof.

For example, in her next video, Mary Wootters explains Reed-Solomon Codes, which are extremely useful in practice. She uses this informal slogan as intuition for why we expect Reed-Solomon codes to work well. Then she moves into the more precise mathematics.

You can see an old blog post by Terry Tao about this kind of "post-rigor thinking" here

---

I hope this helps ^_^

Answer 2

It sounds to me like she's simply just stating a weaker theorem similar to the Fundamental Theorem of Algebra: if $p(x) = a_dx^d + a_{d - 1}x^{d - 1} + \dots + a_2x^2 + a_1x + a_0$ is a polynomial with coefficients in a field, then $p$ has at most $d$ roots.

Answer 3

I have not watched the video myself, but I think the emphasis should have been on field: a nonzero polynomial of degree $d$ whose coefficients are in the field $\mathbb F_q$ (i.e. is a member of $\mathbb F_q[x]$) cannot have more than $d$ zeroes in the field $\mathbb F_q$ (or in any extension field that includes $\mathbb F_q$ as a subfield). This statement need not be true if $\mathbb F_q$ is replaced by a ring. For example, the degree-$\mathbf 2$ polynomial $x^2 -1 \in \mathbb Z_{15}[x]$ has $\mathbf 4$ zeroes $+1, -1. +4. -4$ in $\mathbb Z_{15}$.