Skip navigation
Please use this identifier to cite or link to this item:
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
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 PDFView/Download

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