Finite Models for the Kakeya Problems

Kakeya 问题的有限模型

• 批准号: 2246682
• 负责人: Zeev Dvir
• 金额: $ 40.92万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2246682&HistoricalAwards=false
• 关键词: Finite; Models; 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.

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