Finite Models for the Kakeya Problems

The classical Kakeya needle problem asks to determine the smallest area in the plane needed to rotate a unit length line segment (or `needle’) around completely. Modern variants of this old problem turn out to be central to understanding various types of phenomena in areas ranging from analysis, partial differential equations, combinatorics, number theory and even computer science. The last two decades saw tremendous progress on this family of problems with the introduction of several influential techniques, which have later found use in attacking other hard problems. Despite this exciting progress, several core issues remain unsolved even today. The goal of this project is to find ways to make progress on those hard instances of the Kakeya problem in finite settings where existing techniques fail. The problems the PI will study are rooted in combinatorics but have applications in other areas, including in computer science. One of the goals of this project is to further strengthen these connections by finding new applications and expanding on known ones. Graduate students will be trained as part of this project. The specific research goals of this project are grouped into four main topics: (1) High-dimensional variants of the finite field Kakeya problem. The PI and co-authors made significant progress in the past few years on these variants but many important open problems still remain. In particular, reducing the field size and understanding better the newly discovered connections to linear hash functions. (2) Arithmetic progressions variants of the Kakeya problem. These variants are notoriously difficult and could potentially lead to the resolution of the Kakeya conjecture over the reals. We identify several ‘intermediate difficulty’ variants of these problems in the hope that these could lead to the development of new techniques. (3) Abstract Kakeya problems: We describe an abstract framework for studying Kakeya-type problems and suggest a potential connection to Locally Decodable Codes (codes important in theoretical computer science). (4) Finally, we describe a novel reinterpretation of finite Kakeya type problems as relaxations of integer optimization problems and suggest that these could be studied using tools from real optimization. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.