Algorithms, Combinatorics and Optimization Seminar Sarah Peluse
Stanford University
Title: Three-term polynomial progressions in subsets of finite fields

Abstract: Szemerédi's theorem on arithmetic progressions states that any subset of the integers of positive density contains arbitrarily long arithmetic progressions x,x+y,...,x+my with y nonzero. Bergelson and Leibman proved a generalization of Szemerédi's theorem for polynomial progressions x,x+P₁(y),...,x+P_m(y). In contrast to Szemerédi's theorem, quantitative bounds for Bergelson and Leibman's theorem are not known except in a few special cases. In particular, there are no general results for three-term progressions x,x+P(y),x+Q(y). In this talk, I will discuss the related problem of obtaining bounds for subsets of finite fields that lack nontrivial three-term polynomial progressions. It turns out that any subset A of F_q of size at least q^1-1/16+δ contains very close to |A|³/q progressions x,x+P(y),x+Q(y). I will show how to deduce this result from a bound for the dimension of a certain algebraic variety, and sketch how such a dimension bound can be proven.

Date: Thursday, November 30, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.