Computer Science/Discrete Mathematics Seminar II

The Stepanov method is an elementary method for proving bounds on the number of roots of polynomials. At its core is the following idea. To upper bound the number of roots of a polynomial f(x) in a field, one sets up an auxiliary polynomial F(x) , of (magically) low degree, which vanishes at the roots of f with high multiplicity. That appropriate F exits is usually proved by a dimension argument. A series of papers by Stepanov around 1970 revealed the power of the method to prove results which before hand used algebraic geometric arguments, and refining it (independently) Bombieri and Schmidt were able to use it to prove the "Riemann hypothesis for finite fields", Weil's celebrated result from 1948 (which corollary on exponential sums is often used, besides number theory, for various pseudorandom constructions in TCS). Further work used the method to prove bounds even in cases where algebraic geometry seems unable to provide any nontrivial ones. My plan is to demonstrate Stepanov's method on a few simple examples, as time permits.