Finite Models for the Kakeya Problems

经典的Kakeya针问题要求确定旋转单位长度线段（或“针”）所需的平面上的最小面积。这个老问题的现代变体对理解分析、偏微分方程、组合学、数论甚至计算机科学等领域的各种现象至关重要。在过去的二十年中，随着几种有影响力的技术的引入，这类问题取得了巨大的进展，这些技术后来被用于解决其他难题。尽管取得了令人振奋的进展，但至今仍有几个核心问题没有得到解决。这个项目的目标是找到方法，在有限的环境中，在现有技术失败的情况下，在Kakeya问题的困难实例上取得进展。PI将研究的问题根植于组合学，但在其他领域也有应用，包括计算机科学。该项目的目标之一是通过寻找新的应用程序和扩展已知的应用程序来进一步加强这些联系。研究生将作为这个项目的一部分接受培训。本课题的具体研究目标分为四个主要主题：(1)有限域Kakeya问题的高维变异体。在过去几年中，PI及其合作者在这些变体上取得了重大进展，但仍存在许多重要的开放性问题。特别是，减少字段大小并更好地理解新发现的与线性哈希函数的连接。(2) Kakeya问题的等差级数变体。这些变体是出了名的困难，可能会导致对现实的Kakeya猜想的解决。我们确定了这些问题的几种“中等难度”变体，希望这些变体能够促进新技术的发展。(3)抽象的Kakeya问题：我们描述了一个用于研究Kakeya类型问题的抽象框架，并提出了与局部可解码码（在理论计算机科学中重要的代码）的潜在联系。(4)最后，我们将有限Kakeya型问题重新解释为整数优化问题的松弛，并建议这些问题可以使用实际优化工具进行研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.