This is a lecture given on the occasion of the launch of the PIMS CRG in "L-functions and Number Theory".
The theory of expander graphs is undergoing intensive development. It finds more and more applications to diverse areas of mathematics. In this talk, aimed at a general audience, I will introduce the concept of expander graphs and discuss some interesting connections to arithmetic geometry, group theory and cryptography, including some very recent breakthroughs.
We begin by reviewing various classical problems concerning the existence of primes or numbers with few prime factors as well as some of the key developments towards resolving these long standing questions. Then we put the theory in a natural and general geometric context of actions on affine n-space and indicate what can be established there. The methods used to develop a combinational sieve in this context involve automorphic forms, expander graphs and unexpectedly arithmetic combinatorics. Applications to classical problems such as the divisibility of the areas of Pythagorean triangles and of the curvatures of the circles in an integral Apollonian packing, are given.
Dr. Matiyasevich is a distinguished logician and mathematician based at the Steklov Institute of Mathematics at St. Petersburg. He is known for his outstanding work in logic, number theory and the theory of algorithms.
At the International Congress of Mathematicians in Paris in 1900 David Hilbert presented a famous list of 23 unsolved problems. It was 70 years later before a solution was found for Hilbert's tenth problem. Matiyasevich, at the young age of 22, acheived international fame for his solution.