Beyond the polynomial method: Kakeya sets over finite rings and high dimensional variants

Abstract

A Kakeya Set in F_q^n is a set that contains a line in every direction. It has been known for over a decade that such sets must be large. This goes back to Dvir's proof of the finite field Kakeya conjecture as posed by Wolff. Dvir's proof uses the polynomial method to solve this problem. The problem over finite fields also has applications in psuedorandomness and is crucially used in the construction of currently state-of-the-art seeded mergers and extractors. Wolff's motivation was to pose a possibly simpler problem whose resolution might help with solving the notoriously difficult Euclidean Kakeya conjecture. The Euclidean Kakeya problem also has many connections with analysis, PDEs, and combinatorics. This thesis will look at two generalizations of the finite field Kakeya problem. One where F_q is replaced by the ring Z/NZ and another where we look at higher dimensional analogues of this problem. In both cases, the polynomial method does not work - as over Z/NZ polynomials do not represent all functions and in the other case a degree d polynomial can have much larger than d roots over a higher dimensional affine flat. We will cover a series of results that solve these problems by extending and in some cases going beyond the polynomial method. We will also cover recent applications of the higher dimensional Kakeya problem to give a tight analysis of the behaviour of linear hashes. At a high level, we show that if we pick subspaces of large enough dimension in comparison to the size of a set then for a large fraction of them their every shift intersects with the set in close to the expected number of points.