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 | Size | Format | |
---|---|---|---|---|

TalebizadehSardari_princeton_0181D_11897.pdf | 642.56 kB | Adobe PDF | View/Download |

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