Topics in combinatorial and algorithmic number theory

Dartmouth College, Hanover NH

Investigators

Abstract

Abstract for the award DMS-0703850of Pomerance This proposal deals with several problems in computational and combinatorial number theory, and the theory of arithmetic functions with applications to ranks of elliptic curves. In the first category, the PI will work with Hendrik Lenstra on improving the AKS primality test, with applications to the construction of finite fields, and he will work with Lenstra and Jonathan Pila on a rigorously fast factorization algorithm involving jacobian varieties of hyperelliptic curves of genus 2. In combinatorial number theory, the PI will continue his recent work with Michael Filaseta, Kevin Ford, Sergei Konyagin, and Gang Yu dealing with the covering congruences problem of Paul Erdos. Among the arithmetic functions that the PI will study are the order of the multiplicative group modulo an integer (Euler's function) and the order of the largest cyclic subgroup of this group (Carmichael's function), including the index of this subgroup in the full group. This index has applications to the work of Ulmer on the ranks of elliptic curves over function fields of positive characteristic and some questions of Arnold. The PI will be working jointly with Igor Shparlinski on the former applications and with Michel Balazard on the latter. With the Carmichael function, the PI intends with Florian Luca to strongly improve the known results concerning its range. One would think that basic questions concerning the integers, such as deciding when one is prime, factoring another, or the multiplicative structure of the remainders when a particular number is used as a divisor, would be well-understood by now. But they are not, and for one of these problems, namely factoring, the fact that it is apparently difficult in general is the basis for the security of cryptographic systems that underpin commerce and communication. The principal proposed activities of this proposal concern these fundamental problems, mostly from the theoretical side. In addition, the PI proposes to study some applications of the multiplicative structure of remainders to the study of the ranks of certain elliptic curves. Elliptic curves arise from cubic equations in two variables; one studies the solutions to such an equation with the variables coming from a given algebraic domain such as the rational numbers and similar domains. They have provided a rich source of structure for number theorists. These curves too have been used in cryptographic systems and in computational number theory, but the PI's focus here is a statistical study of certain algebraic invariants of the solution sets as one varies curve parameters. Finally, the PI will study some problems in combinatorial number theory, including the famous covering congruences problem of the late Paul Erdos. Here one asks if there can be a finite set of large integers and a single remainder for each such that every integer when divided by the given large numbers leaves at least one corresponding remainder in the given pre-set list. The current record for "large" is 25, and it is not known if one can do this with arbitrarily large numbers.