Applications of Probabilistic Combinatorial Methods

纯数学是基础研究--它不能用它的直接用途来判断：历史告诉我们，重要的应用在多年后出人意料地出现。本着伟大的大卫·希尔伯特的精神，我们的项目是问题驱动的。正如他在一百多年前所说的：“只要一门科学提供了丰富的问题，它就活着。[……]正是通过解决问题，研究人员考验了他的钢材；他发现了新的方法和新的观点，获得了更广阔、更自由的视野。[……]数学问题应该是困难的，以吸引我们，但不是完全无法理解，以免它嘲笑我们的努力。”在这个项目中，大多数要考虑的问题是由历史上最大的问题提出者Paul Erdos在60多年前提出的，并且与素数和模算术的分布有关。事实上，这个项目的能量和动力将通过一个启动会议来建立，该会议将把在他的一些最具挑战性的问题上做出动态和有用工作的杰出的数学家聚集在一起。几十年来，主要问题似乎遥不可及，但几年前，霍夫和尼尔森证明了一些突破性的结果。在这个项目的范围内，在应用组合学和概率论的方法来解决仍然存在的几个主要问题时，可以推导出一些解决这些问题的新的数学技术，然后这些技术可能适用于许多其他问题，包括数论中的问题。这个项目有希望在学科内外的许多方面产生影响。例如，整数的因式分解在密码学中具有非常重要的实际意义，而重构问题很可能在生物学中使用(例如DNA测序)。第二个最短路径问题与一项拟议的精神分裂症诊断测试有关。这一裁决反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Pure mathematics is fundamental research -- it cannot be judged by its immediate use: history teaches us that important applications arise unexpectedly, years later. In the spirit of the great David Hilbert, our project is problem-driven. As he said over one hundred years ago, ''As long as a branch of science offers an abundance of problems, so long is it alive. [...] It is by the solution of problems that the investigator tests the temper of his steel; he finds new methods and new outlooks, and gains a wider and freer horizon. [...] A mathematical problem should be difficult in order to entice us, yet not completely inaccessible, lest it mock at our efforts.'' In the case of this project, most of the problems to be considered were posed over sixty years ago by Paul Erdos, the greatest problem poser in history, and are related to the distribution of primes and modular arithmetic. In fact, the energy and momentum of this project will be established by a kickoff conference which will bring together outstanding mathematicians who have done dynamic and useful work on some of his most challenging problems. For many decades, the main problems seemed to be out of reach, but a few years ago Hough and Nielsen proved some breakthrough results. Within the scope of this project, in applying methods of combinatorics and probability theory to solve several major problems that have remained, some new mathematical techniques for their solutions could be derived that might then be applicable to many other problems, including those in number theory. This project has the promise to be impactful in a number of ways within and beyond the discipline. For example, the factorization of integers is of great practical importance in cryptography, and reconstruction problems are likely to be of use in biology (e.g., DNA sequencing). The second shortest path problem is related to a proposed diagnostic test for schizophrenia.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.