Optimal strong approximation for quadratic forms

Abstract

We study questions posed by Sarnak in his letter to S. Aaronson and A. Pollington, on ``the Solovay-Kitaev Theorem and Golden Gates''. We give the optimal exponent for the strong approximation problem for quadratic forms in 5 or more variables. We also give lower and upper bound for the exponent of approximation for quadratic forms in 4 variables which recovers the best upper bound, known previously under the Ramanujan conjecture, without any assumption. Our lower bound gives a nontrivial and numerically optimal bound on the diameter of LPS Ramanujan graphs. More generally, our numerical results suggests that our lower bound for the exponent is optimal for any quadratic forms in 4 variables. We consider the algorithmic aspect of the optimal strong approximation. As two applications of our algorithm, we develop and implement an algorithm in polynomial time in the size of digits of input integers for the navigation problem on LPS Ramanujan graphs and also the discrete log problem for the finite group ${\rm PGL}_2(\frac{\mathbb{Z}}{q\mathbb{Z}})$ by assuming one can factor quickly and a standard conjecture in Number theory. Finally, our work fits into a more general framework of studying small scale equidistribution of measures coming from number theory in the optimal range. We give a definite answer to a conjecture of Lester and Rudnick on the small scale equidistribution of orthonormal basis of eigenfunctions restricted to an individual eigenspace on the flat torus $\mathbb{T}^d$ for $d \geq 5$ and find the optimal range for equidistribution.