My co-authors (J. Ellenberg and C. Hall) and myself have received some interesting remarks from P. Sarnak concerning our joint work discussed a few days ago. With his permission, it follows below (with minimal editing to clean-up the list of references at the end).
One important point he makes is that the result of Abramovich, who gave a lower bound for the gonality of modular curves using Selberg’s 3/16 lower-bound for the eigenvalue of the Laplace operator on these curves and an inequality of Li-Yau, had been anticipated by P. Zograf in a little-known paper in Russian (see here for the English translation; it is Theorem 5 at the very end of that paper). We will soon update the arXiv version of our paper to add a reference to this result (the PDF from my home page is already updated).
Dear Jordan,Chris and Emmanuel,
I was pointed to your recent posting with the above
title.I particularly like the application in Corollary 4.
It would be nice if you supplemented it with a similar explicit application
which requires the full force of the blossoming number/combinatorial theory of
what I like to call “thin subgroups of SL(n,Q)”.By the latter I mean a finitely
generated such group which is not of finite index in the S-integral points of
the Zariski closure of the group.
My reason for writing is to point out a couple of papers connected to
parts of your paper,which are not commonly known and which should be.The first
is a paper of Zograf [Z] and the second
is result of Solovay ,called the Solovay-Kitaev theorem (see[ C-N ]),
which was pointed out to me some years ago by Dorit Aharonov.
Zograf’s paper should have been cited in the paper of Abramovich
that you cite as a key to your paper.I feel partially responsible for this
mistake as I communicated Abramovich’s paper.I was
aware of the results in Zograf which give a lower bound for
the genus of a curve in terms of its volume and lambda_1 ,
but I was not aware that he also gave the lower bound on the gonality.
Anyway his genus lower bound is what you use in (5) page 8 of your paper and
attribute to Kelner and the gonality lower bound is
the same as that in Abramovich. Note that his bound is based
on the earlier paper of Yang and Yau [Y-Y] rather than Li and Yau.
Since Abramovich’s paper there have been improvements in
bounds towards Selberg’s Conjecture and thus improvements
in the gonality lower bound.The recent paper of Blomer
and Brumley [B-B] gives the best such bounds in the case
of general Shimura curves.For me it is an interesting
question as to whether for modular curves,the ratio gonality/genus tends to a
limit as the genus goes to infinity? If so is this constant the same as what
one gets for the same ratio,gonality/genus,of a random curve of large genus?
Solovay’s theorem is concerned with diameter and expansion
in the group SU(2). Let A and B be members of SU(2) such that
the group generated by them is Zariski dense in SL(2,C).
The issue is how quickly can one approximate any element in
SU(2),by words in A and B.Given any g in SU(2) and e>0 there is a word w in A
and B such that d(w,g)<e [in some some fixed metric on SU(2)].Let l(e,g)
be the length of the shortest such w and let l(e) be the maximum of l(e,g) as g
varies over SU(2).If A and B form an “expander” in
the sense that the left convolution operator corresponding
to A+A^(-1)+B +B^(-1) on L^2(SU(2),haar) has a spectral gap,
then l(e)=O(log (1/e)).This “diameter” bound is optimal.
In [G-J-S] a substitute in this setting was
found for the argument exploiting the high dimension of any
nontrivial representation of G(F_p) [G a Chavelley group],that
is used in all proofs of expansion in this finite simple group setting.
This led to many examples of such expanders in SU(2) and it was
conjectured there that every such pair A,B gives an expander.
[B-G] have the best result towards this conjecture showing that
it is true if A and B have entries in Q bar.In terms of
technical difficulty this is probably the most difficult case
of expansion that is known.The proof of expansion for SL_2(F_p)
relies indirectly on the proof in [E-M] of the Erdos-Volkman
ring conjecture ,while this SU(2) case relies on the
proof in [B] of the more difficult quantitive local version
of this ring conjecture.
What Solovay proves is the analogue of your “esperante” property,
though he didnt give it any such colorful name. He shows that
l(e)=O(log(1/e)^2),for any given A and B as above.So
in this setting we have the small diameter property but
unlike your case ,where as you note a proof of the expansion property
is close to being proven,for SU(2) it remains wide open.Solovay proves this
polynomial diameter bound in an appendix
to his paper with Yao[S-Y], where it is used as one of the ingredients
to analyse how quantum computation classes can simulate classical ones up to
polynomial slowdown [whether the converse
is true or false is far from clear].For this purpose they need not
only that the diameter is small,but also that one can find a short
word quickly, and Solovay’s proof provides such a short word
in more or less the same number operations.The expansion proof
of an optimally small diameter goes via a counting argument and
it offers no means of finding a short word (or path in the
graph case).Even in the case of optimal expansion in the
graph setting,that is of Ramanujan Graphs,no fast algorithm for
finding a short path between vertices is known,and I have long
thought of this as a basic problem. In [L],Larsen resolves this
problem when one relaxes the diameter bound to something slightly bigger
than O(log) and also allowing a random element into the
algorithm,making it a probablistic algorithm.For computer science applications
what he does is surely good enough.
I know that you guys are avid bloggers,so feel free to include this letter in
your discussions if you feel it is appropriate.
[B] J. Bourgain, GAFA 13 (2003), 334-365.
[B-B] V. Blomer and F. Brumley, “On the Ramanujan Conjecture over
Number Fields”, arXiv:1003.0559.
[B-G] J.Bourgain and A.Gamburd, Invent Math. 171 (2008), 83-121.
[E-M] G.Edgar and C.Miller, Proc. AMS 131 (2003) 1121-1129.
[J-G-S] D.Jakobson, A.Gamburd and P.Sarnak, Journal European
Math. Soc. 1 (1999), 51-85.
[L] M.Larsen, International Math. Res. Notices (2003) No 27, 1455-1471.
[C-N] M. Nielsen and I. Chuang, “Quantum computation and
Quantum Information” CUP, Cambridge 2000.
[S-Y] R.Solovay and A.Yao, preprint 1996.
[Y-Y] P.Yang and S.T.Yau, Ann Scuola Norm. Super. Pisa, 7 (1980), 55-63.
[Z] P.Zograf, “Small eigenvalues of automorphic Laplacians in spaces
of cusp forms”, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov
(LOMI) 134 (1984), 157-168; translation Journal of Math. Sciences 36,
Number 1, 106-114, DOI: 10.1007/BF01104976