The PI intends to continue his research in combinatorial number theory, exponential sums and spectral problems around expanders and Hecke operators. Part of this is in an ongoing collaboration with A. Gamburd and P. Sarnak. A related issue is Furstenberg's invariant measure problems and stiffness conjectures for various group actions, which the PI plans to pursue jointly with E. Lindenstrauss. The PI is also involved in other applications of developments around additive combinatorics and exponential sums related to derandomization issues and the theory of pseudo-random sequences.
The proposal is a further development of a line of research that started five years ago with the discovery of certain new and quite elementary combinatorial principles around so-called 'sum-product phenomena'. Over the recent years its importance became increasingly clear as it turned out to have a surprisingly broad range of applications (from number theory to computer science) and lead to progress on various problems that were stalled for a long time. Research around expanders became really interdisciplinary and of interest to researchers in various fields also outside mathematics. For instance new robust construction of expanders play a role in connection with building expander-based computer architectures via the process of nanoscale self-assembly.
Various aspects in theoretical computer science,such as secure data exchange and complexity theory,lead naturally to the problem of a better understanding of the digital aspects of the basic arithmetic objects and functions.Typical questions are for instance how well these functions can be computed using simple logical circuits,what are their correlation properties with low complexity sequences and their randomness properties.There has been over the recent years a cross-fertilization between various disciplines where problems from the computer science world eventually lead to progress on classical questions in prime number theory.This is exactly the scope of the PI's research.Roughly speaking,one would ask for instance how complex a Boolean circuit has to be in order to recognize if an integer is a prime or not.Mathematically one is lead to study binary expansions of prime numbers and how freely digits can be prescribed.The subject leads quickly to basic number theoretic issues around the distribution of prime numbers.Through his recent research, the PI brought various new insights on this type of questions,making progress on the original computer science problems as well as the underlying number theoretic aspects.One sample is a better insight in the so-called Fourier-Walsh spectrum of the classical Moebius function and the prime numbers,which is the key to unveil their complexity theoretic aspects.
