Some Problems in Number Theory and Arithmetic Combinatorics

数论和算术组合学中的一些问题

• 批准号: 0500863
• 负责人: Ernest Croot
• 金额: --
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0500863&HistoricalAwards=false
• 关键词: Some; Problems; Number; Theory; Arithmetic

The proposer plans to work on a variety of problems in number theory and combinatorics. Among these are the problem of determining the structure of subsets of finite fields having few arithmetic progressions. For example, suppose S is a subset of the integers modulo p having about p/2 elements, and having the least number of three-term arithmetic progressions among all sets with about p/2 elements. How many three-term progressions does S have, and what can one say about the structure of S? The square dependence problem: pick integers at random less than x until a subset of these integers products to a square. Determine the expected stopping time of this process. This problem is central to running time estimates for integer factoring algorithms, problems related to sum-product estimates in finite fields (given a subset of a finite field, how large must the sumset or product set of that subset be?), and problems related to the complexity of inverting certain number theoretical functions (how difficult is it to decide whether an integer n is in the image of the Euler phi function?). The proposer has already made substantial progress on all of these problems, and forsees a rich research programme developing in the next several years. Two good examples of the research problems on which the proposer plans to work, both from the same area of mathematics, but of a very different character, are the square dependence problem and the three-term progression problem: When one uses the internet to make purchases, ones credit card information is encrypted using any of several coding schemes called ``public key encryption''. There are methods to break these codes (for, example the quadratic sieve); however, just how fast they work is not well understood. A good solution to the square dependence problem would give one a very precise estimate for how quickly these methods work, as well as indicate how one might tweak them to make them run faster. The other problem, the three-term progression problem, concerns triples of numbers which are equally spaced, such 3,5,7 or 11,22,33. A fundamental, well-studied problem in combinatorial mathematics is to determine when dense collections of integers contain such triples; for example, if you pick 100 numbers from among the numbers 1 through 1000, must your 100 numbers have one of these triples? No one knows exactly what makes certain collections of numbers have no or few of these triples; however, the proposer has a research plan to partially answer this question, and already has an accepted publication in a peer reviewed journal (JCTA) on the problem.

提议者计划在数论和组合学中解决各种问题。 其中包括确定有限域的子集的结构的问题有几个算术级数。例如，假设S是模p的整数的子集，具有大约p/2个元素，并且在具有大约p/2个元素的所有集合中具有最少数量的三项算术级数。 S有多少个三项级数，关于S的结构我们能说些什么？ 平方依赖问题：随机选取小于x的整数，直到这些整数的一个子集积成平方。 确定此过程的预期停止时间。 这个问题是整数分解算法的运行时间估计的核心，与有限域中的和积估计相关的问题（给定有限域的子集，该子集的和集或积集必须有多大？），以及与反演某些数论函数的复杂性有关的问题（决定整数n是否在欧拉函数的图像中有多难？）。 提案人已经在所有这些问题上取得了实质性进展，并预见在未来几年内将开展一项内容丰富的研究计划。 两个很好的例子的研究问题，这两个问题都来自同一领域的数学，但有一个非常不同的字符，是平方依赖问题和三项级数问题：当一个人使用互联网进行购买，信用卡信息加密使用任何几个编码方案称为"公钥加密“。 有一些方法可以破解这些代码（例如，二次筛）;然而，它们的工作速度有多快还不清楚。 平方依赖问题的一个好的解决方案将为这些方法的工作速度提供一个非常精确的估计，并指出如何调整它们以使它们运行得更快。 另一个问题，三项级数问题，涉及三个等距的数字，如3，5，7或11，22，33。 在组合数学中，一个基本的、研究得很好的问题是确定密集的整数集合何时包含这样的三元组;例如，如果你从数字1到1000中选择100个数字，你的100个数字必须有这些三元组之一吗？ 没有人确切地知道是什么使得某些数字集合没有或很少有这些三元组;然而，提议者有一个研究计划来部分回答这个问题，并且已经在同行评审期刊（JCTA）上发表了关于这个问题的公认论文。