Computer Science/Discrete Mathematics Seminar I

Topic: Furstenberg sets in finite fields

Speaker: Zeev Dvir

Affiliation: Princeton University

Date & Time: Monday October 28th, 2019, 11:00am - 12:00pm

Location: Simonyi Hall 101


A (k,m)-Furstenberg set K in F^n, where F is a finite field, is a set such that any k-dimensional subspace of F^n can be shifted so that it intersects K in at least m points. Such sets generalize in a natural way finite field Kakeya sets (in which k=1, and m=|F|), whose study has resulted in many applications, including in theoretical computer science. The main question is how small can such a set K be. While the polynomial method gives a complete answer to this question when k=1 (i.e., when K intersects lines in all directions), it fails completely for larger values of k. Until recently, the only bound for general k and m was given by Ellenberg and Erman using scheme theoretic techniques. In this talk I will discuss a new result (joint  with Manik Dhar and Ben Lund) that give improved (and in some cases tight) upper bounds on the size of Furstenberg sets for general k and m using completely elementary  arguments.