Some Problems in Number Theory and Arithmetic Combinatorics

点击翻译按钮获取中文摘要

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.