Random walks and super-approximation

The PI will study random-walks given by symmetries and explore their applications to various branches of mathematics and beyond. Consider a space with lots of symmetries, for example a sphere. Choose a finite set of symmetries of this space, put a particle at a point, and each time move it according to a randomly picked symmetry from our chosen set. This is called a random-walk. When after a few steps, an observer no longer has much information about the position of the particle, it is said that the random-walk has the spectral gap property. There are many important questions about different random-walks on the same space. For instance a major problem is whether under reasonable assumptions spectral gap is a property of the space rather than a random-walk. Another question is whether it is possible to have two random-walks where observing one gives us information about the other. The PI will solve these type of questions for spaces that emerge from number theoretic problems; this is known as super-approximation conjecture. The PI will continue his mentoring of graduate students and postdocs under this award. Having a single random-walk on an infinite space with the spectral gap property was the source of many applications. For instance, by discretizing the space, highly connected sparse graphs, known as expanders, were constructed. Having a random-walk with spectral gap on spheres were used to obtain an effective distribution of points on spheres, and recently used in quantum computing. In the past 15 years, it has been shown that the flexibility of the choice of random-walk which comes with the super-approximation makes it a powerful tool for a wide range of applications. Here are a few examples: affine sieve, sieve in group theory, variation of Galois representations, Zaremba’s conjecture, mixing in geometrically finite hyperbolic manifolds, and orbit equivalence rigidity. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.