Ramanujan graphs and exponential sums over function fields

DOI10.1016/J.JNT.2020.05.010MaRDI QIDQ2197504zbMATH OpenOpenAlexWikidataFDO

Authors Naser T. Sardari, Masoud Zargar

Publication date 1 September 2020

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.07365

zbMATH Keywords

(optimal) strong approximationexponential sumsfunction fieldsKloosterman sumsLinnik-Selbergmorgensternoptimal diameterquadratic formsRamanujan graphsstationary phase over function fields

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Arithmetic theory of algebraic function fields (11R58) Exponential sums (11T23)

Abstract: We prove that $q+1$-regular Morgenstern Ramanujan graphs $X^{q,g}$ (depending on $ginmathbb{F}_q[t]$) have diameter at most $left(frac43+varepsilonight)lo{g}_q|X^{q,g}|+O_{varepsilon}(1)$ (at least for odd $q$ and irreducible $g$) provided that a twisted Linnik-Selberg conjecture over $mathbb{F}_q(t)$ is true. This would break the 30 year-old upper bound of $2lo{g}_q|X^{q,g}|+O(1)$, a consequence of a well-known upper bound on the diameter of regular Ramanujan graphs proved by Lubotzky, Phillips, and Sarnak using the Ramanujan bound on Fourier coefficients of modular forms. We also unconditionally construct infinite families of Ramanujan graphs that prove that $frac43$ cannot be improved.

Review text

The \(q+1\)-regular Morgenstern Ramanujan graphs \(X^{q,g}\) (depending on \(g\in \mathbb F_q[t]\)) have diameter at most \[(\frac{4}{3}+\varepsilon)\log_q|X^{q,g}|+O_\varepsilon\tag{1}\] (at least for odd \(q\) and irreducible \(g\)) provided that a twisted Linnik-Selberg conjecture over \(F_q(t)\) is true. It is a very remarkable result. This would break the 30 year-old upper bound of \(2\log_q|X^{q,g}|+O(1)\), a consequence of a well-known upper bound on the diameter of regular Ramanujan graphs proved by Lubotzky, Phillips, and Sarnak [\textit{A. Lubotzky} et al., Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)] using the Ramanujan bound on Fourier coefficients of modular forms. They construct infinite families of Ramanujan graphs that prove that \(\frac{4}{3}\) cannot be improved.

Recommendations

• Diameter of Ramanujan graphs and random Cayley graphs
• scientific article; zbMATH DE number 1156648
• Note on the girth of Ramanujan graphs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• scientific article; zbMATH DE number 772544

Cites work

• A new form of the circle method, and its application to quadratic forms.
• Eigenvalues and expanders
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• scientific article; zbMATH DE number 46534 (Why is no real title available?)
• scientific article; zbMATH DE number 48345 (Why is no real title available?)
• scientific article; zbMATH DE number 3467241 (Why is no real title available?)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• ON A TWISTED VERSION OF LINNIK AND SELBERG'S CONJECTURE ON SUMS OF KLOOSTERMAN SUMS
• Optimal strong approximation for quadratic forms
• Ramanujan graphs
• Rational points on cubic hypersurfaces over \(\mathbb F_q(t)\)
• Twisted Linnik implies optimal covering exponent for S^3

Cited in

(7)

• A connection between a question of Bermond and Bollobás and Ramanujan graphs
• Diameter of Ramanujan graphs and random Cayley graphs
• Optimal strong approximation for quadrics over \(\mathbb{F}_q [t]\)
• scientific article; zbMATH DE number 475381 (Why is no real title available?)
• scientific article; zbMATH DE number 1156648 (Why is no real title available?)
• Character sums, automorphic forms, equidistribution, and Ramanujan graphs Part I. The Kloosterman sum conjecture over function fields
• The shifted convolution problem in function fields

This page was built for publication: Ramanujan graphs and exponential sums over function fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197504)