On a Reciprocal Tarry-Escott Problem, the Distribution of Roots of Polynomials Modulo a Composite, and Sieve Methods

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

DMS-0301282 Poonen, Bjorn M. (Croot, Ernest S.) Abstract Title: On a Reciprocal Tarry-Escott Problem, the Distribution of Roots Of Polynomials Modulo a Composite, and Sieve Methods The Proposer's research project has three goals: He wishes to finish working on his results and methods on the Prouhet-Tarry-Escott problem, which he will write up in one or more papers; he plans to continue and to write up in a paper his work with an undergraduate on cryptology; and, he wishes to continue to develop a new sieve method for determining the number of primes in thin sets of integers. The proposer's work on the Prouhet-Tarry-Escott problem gives a new method for constructing solutions to certain systems of diophantine equations with many variables, and the method may lead to a solution of one of more unsolved problems in this area. The work on cryptology centers around showing that certain algorithms for attacking public-key cryptosystems, that find low-height roots of polynomials modulo an integer q (such as Coppersmith's method), cannot be easily improved. Finally, the proposer plans to continue developing a sieve method for counting the number of primes in a given set of integers, which allows one to use additional analytic information (besides the usual data used by the combinatorial sieve) about the set, in the hopes that the method will lead to the solution of one or another known, difficult, unsolved problems in prime number theory. Since the time of the ancient Greeks, mathematicians have been trying to understand how the prime numbers are spaced; that is, how does the distance between consecutive prime numbers vary as one considers larger and larger primes? Sieve methods were developed as a theoretical tool for answering this type of question; however, there are many natural questions about such spacings that they currently cannot answer. One of the proposer's research goals is to finish developing a new sieve method which he hopes to use to make progress on some of these unsolved problems. The proposer's work on cryptology was motivated by research with an undergraduate on a certain method (Coppersmith's algorithm) for attacking the RSA cryptosystem, which is a procedure for sending secure data via the internet. The proposer (and student) plans to continue his work on a related problem in number theory, the solution of which would show that this method of attack cannot be much improved. Lastly, the proposer plans to continue his work on the Prouhet-Tarry-Escott problem. This problem is a longstanding unsolved question in number theory, and proposer is developing new methods to make progress on it and other, similar problems.