I recently attended a Workshop on Pseudorandomness in Chennai Mathematical Institute on Pseudorandomness. Venkat Guruswami made the following beautiful statement in passing during his talk (on coding theory):
It is remarkable how much one can prove using the simple fact that a degree $d$ polynomial over a field can have at most $d$ roots.
I believe this is also called the Stepanov Method (in those applications, typically roots occur with large multiplicity as well). One place where I've seen this is in a paper on square root bounds for the smallest non-residue by Michael Forbes, Neeraj Kayal, Rajat Mittal and Chandan Saha .
This principal was highlighted in the workshop with the unique and list decoding of Reed-Solomon code (which can be found in this course, for example) in Venkat's talk. In Neeraj Kayal's talk, he gave two other examples -- the proofs of the Finite Field Kakeya Conjecture and the Joints Conjecture (both of which can be found in this very nice survey by Zeev Dvir). Other examples that I can think of is Dana Moshkovitz's proof of the Schwartz-Zippel Lemma, and another favourite of mine is the AKS Primality test which (if I'm allowed to make a stretch) uses only this fact essentially.
I was wondering if there are other examples of elegant results using (essentially) just this simple fact.
This post is closely related to the earlier question "Polynomial methods for complexity results" but that was for a more general 'polynomial method'.
