Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01zg64tp40m
 Title: Optimal strong approximation for quadratic forms Authors: Talebizadeh Sardari, Naser Advisors: Sarnak, Peter Contributors: Mathematics Department Subjects: Mathematics Issue Date: 2016 Publisher: Princeton, NJ : Princeton University 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. URI: http://arks.princeton.edu/ark:/88435/dsp01zg64tp40m Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Mathematics

Files in This Item:
File Description SizeFormat
TalebizadehSardari_princeton_0181D_11897.pdf642.56 kBAdobe PDF

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.