\documentclass{article}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}{Algorithm}
\newtheorem{axiom}{Axiom}
\newtheorem{case}{Case}
\newtheorem{claim}{Claim}
\newtheorem{conclusion}{Conclusion}
\newtheorem{condition}{Condition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{criterion}{Criterion}
\newtheorem{definition}{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{notation}{Notation}
\newtheorem{observation}{Observation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\begin{document}
\baselineskip=18pt
\renewcommand{\thefootnote}{}
\title{Counting finite index subgroups \\ of lattices in Lie groups}
\author{Dorian Goldfeld$^1$, Alexander Lubotzky$^2$,\\ Nikolay Nikolov$^3$ and L\'{a}szl\'{o} Pyber$^4$}
\maketitle
\textbf{Addresses:}
\textbf{1.} Department of Mathematics, Columbia University, New York, NY 10027, U.S.A.,
\textbf{2.} Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel,
\textbf{3.} Tata Institute for Fundamental Research, Colaba, Mumbai 400005, India,
\textbf{4.} A. R\'{e}nyi Institute of Mathematics, Re\'{a}ltanoda ut. 13-15, H-1053, Budapest, Hungary.
\textbf{Corresponding author:} Alexander Lubotzky, tel +972 2 6584387, e-mail: alexlub@math.huji.ac.il .
\textbf{Pages: 9 (double spaced).}
\textbf{Wordcount: abstract 150, main text 2000.}
\textbf{ PNAS Classification.} Physical sciences: Mathematics.
\emph{2000 Mathematics Subject Classification 20H05; 22E40}
\newpage
\section*{Abstract}
We prove that for $n \to \infty$ the number of congruence subgroups of index at most $n$ in $\mathrm{SL}_2(\mathbb{Z})$ is roughly $n^{\frac{\gamma \log n}{\log \log n}}$ where $\gamma= (3-2\sqrt{2})/4$. The proof
is based on the Bombieri-Vinogradov `Riemann hypothesis on the average' and on the solution of a new type
of extremal problem in combinatorial number theory. Similar surprisingly sharp estimates are obtained for the subgroup growth of lattices in higher rank semisimple Lie groups. If $G$ is such a Lie group and $\Gamma$ is an irreducible lattice of $G$ it turns out that the subgroup growth of $\Gamma$ is independent of the lattice and depends only on the Lie type of the direct factors of $G$. It can be calculated easily from the root system. The most general case of this result relies on the Generalized Riemann Hypothesis but many special cases are unconditional. The proofs use techniques from number theory, algebraic groups, finite group theory and combinatorics.
\newpage
\section*{Statement of results: arithmetic groups}
For a group $\Gamma$ we denote by $s_n(\Gamma)$ the number of subgroups of index at most $n$ in $\Gamma$ (when it is finite). The study of the rate of growth of the sequence $\{s_n(\Gamma)\}$ has received considerable attention in the past two decades. One interesting case is when $\Gamma$ is an arithmetic group, or, more generally a lattice in a Lie group. Then the subgroup growth of $\Gamma$ relates to the congruence subgroup problem for $\Gamma$, see \cite{lub}.
Let $G$ be an absolutely simple, connected, simply connected algebraic group defined over a number field $k$. For a finite subset of valuations of $k$ including all the archimedean ones, let $\mathcal{O}_S$ denote the ring of $S$-integers of $k$ and set $\Gamma =G(\mathcal{O}_S)$. A subgroup $H \leq \Gamma$ is called a congruence subgroup if there is some ideal $I \vartriangleleft \mathcal{O}_S$ such that $H$ contains the kernel of the homomorphism $\Gamma \rightarrow G(\mathcal{O}_S/I)$.
Let $c_n(\Gamma)$ denote the number of congruence subgroups of index at most $n$ in $\Gamma$. In \cite{lub} Lubotzky proved that there exist numbers $a,b$ depending on $G,k$ and $S$, such that$^*$ \footnotetext{$^*$ The lower bound depended on GRH at the time but was made unconditional in \cite{GLP}} \[ n^{\frac{a \log n}{\log \log n}} \leq c_n(\Gamma) \leq n^{\frac{b \log n}{\log \log n}},\] and, moreover the sequence $s_n(\Gamma)$ has much faster growth (at least $n^{\log n}$) if the congruence subgroup property fails for $G$. Below we determine the precise rate of growth of $c_n(\Gamma)$. (All logarithms are in base $e$.)\medskip
Let $X$ be the Dynkin diagram of the split form of $G$ (e.g. $X=A_{n-1}$ if $G=\mathrm{SU}_n$).
Let $h$ be the Coxeter number of the root system $\Phi$ corresponding to $X$ (it is the order of the Coxeter element of the Weyl group of $X$). Then $h=\frac{|\Phi|}{l}$ where $l= \mathrm{rank}_\mathbb{C}(G)= \mathrm{rank}(X)$, and for later use define $R:=h/2$. Let
\[\gamma(G)=\frac{ (\sqrt{h(h+2)}-h)^2}{4h^2}. \]
Let GRH denote the Generalized Riemann Hypothesis for
Hecke $L$-functions of number fields.
The following was posed as a conjecture in \cite{GLP} and proved in \cite{LN}:
\begin{theorem}\label{arithmetic} Let $G$, $\Gamma$ and $\gamma(G)$ be as defined above. Assuming GRH we have
\[ \lim_{n \rightarrow \infty} \frac{\log c_n(\Gamma)}{(\log n)^2/ \log \log n}= \gamma(G),\] and moreover, this result is unconditional if $G$ is of inner type (e.g. $G$ splits) and $k$ is either an abelian extension of $\mathbb{Q}$ or a Galois extension
of degree less than 42. \end{theorem} \medskip
An interesting aspect
of this theorem is not only that the limit exists but that it is completely
independent of $k$ and $S$, and depends only on $G$. While the
independence on $S$ is a minor point and can be proved directly, the only way
we know to prove the independence on $k$ is by applying the whole machinery
of the proof.
In \cite{GLP} the crucial special case of $\Gamma=\mathrm{SL}_2(\mathcal{O}_S)$ is proved in full. There we have $\gamma(\mathrm{SL}_2)=\frac{1}{4}(3-2\sqrt{2})$. The lower bound follows using the Bombieri-Vinogradov Theorem
and the upper bound by a massive new combinatorial analysis.
It was also shown in \cite{GLP}, subject to the validity of GRH (and unconditionally in the same cases as in Theorem \ref{arithmetic}), that $\liminf \limits_{n\to\infty} \;\frac{\log c_n(\Gamma)}{(\log n)^2/ \log \log n} \geq \gamma(G)$.
\subsection*{Lattices}
Let $H$ be a connected \emph{characteristic 0} semisimple group. By this we mean that $H=\prod_{i=1}^r G_i(K_i)$ where for each $i$, $K_i$ is a local field of characteristic 0 and $G_i$ is a connected simple algebraic group over $K_i$. We assume throughout that none of the factors $G_i(K_i)$ is compact (so that
$\mathrm{rank}_{K_i}(G_i)\geq 1$). Let $\Gamma$ be an irreducible lattice of $H$, i.e. for every infinite normal subgroup $N$ of $H$ the image of $\Gamma$ in $H/N$ is dense there.
Assume now that \[\mathrm{rank}(H):=\sum_{i=1}^r \mathrm{rank}_{K_i}(G_i)\geq 2.\]
By Margulis' Arithmeticity Theorem
(\cite{margulis}) every irreducible lattice $\Gamma$ in $H$ is arithmetic. Also the split forms of the factors $G_i$ of $H$ are necessarily of the same type and we set $\gamma(H):=\gamma(G_i)$.
Moreover, a famous conjecture by Serre (\cite{serre} asserts that
such a group $\Gamma$ has the congruence subgroup property. It has been proved in many cases.
This enables us to prove:
\begin{theorem}\label{lat}
Assuming GRH and Serre's conjecture, then for every non-compact
higher rank characteristic 0 semisimple group $H$ and every irreducible lattice
$\Gamma$ in $H$ the limit \[ \lim\limits_{n\to \infty} \;
\frac{\log s_n(\Gamma)}{(\log n)^2/\log\log n}\] exists and equals
$\gamma(H)$, i.e. it is independent of the lattice $\Gamma$.
Moreover the above holds unconditionally if $H$ is a simple connected Lie group not locally isomorphic to $D_4(\mathbb{C})$ and $\Gamma$ is a non-uniform lattice in $H$ (i.e. $H/\Gamma$ is non-compact).
\end{theorem}
We point out the following geometric reformulation of the special case:
\begin{theorem}\label{t'} Let $H$ be a simple connected Lie group of $\mathbb{R}$-rank $\geq 2$ which is not locally isomorphic to $D_4(\mathbb{C})$. Put $X=H/K$ where $K$ is a maximal compact subgroup of $H$. Let $M$ be a finite volume non-compact manifold
covered by $X$ and let $b_n (M)$ be the number of covers of $M$ of
degree at most $n$. Then $\lim\limits_{n\to\infty} \;
\frac{\log b_n(M)}{(\log n)^2/\log\log n}$ exists, equals $\gamma(H)$
and is independent of $M$.
\end{theorem}
It is interesting to compare Theorems 2 and 3 with the results of Liebeck-Shalev\cite{ls}, and M\"{u}ller-Puchta \cite{MP}: If $H=\mathrm{SL}_2(\mathbb{R})$ and $\Gamma$ is a lattice in $H$ then $\lim \frac{\log s_n(\Gamma)}{\log n!}=-\chi(\Gamma)$, where $\chi$ is the Euler characteristic.
\section*{Proofs: the lower bound}
We shall illustrate the main idea of the proof with $\Gamma= \mathrm{SL}_d(\mathbb{Z})$ and refer to \cite{GLP} for the full details.
Choose any $\rho \in (0,\frac{1}{2})$. For $x>>0$ and a prime $q3$.
For a subgroup $H$ of $X(\mathbb{F}_q)$ define
\[ t(H)=\frac{ \log[X(\mathbb{F}_q):H]}{\log|H^{\diamondsuit}|},\]
where $H^{\diamondsuit}$ denotes the maximal abelian
quotient of $H$ whose order is coprime to $p$. Set $t(H)=\infty$ if $|H^{\diamondsuit}|=1$.
\medskip
Recall that $R=R(X)=h/2$ where $h$ is the Coxeter number of the root system of the \textbf{split} Lie type corresponding to $X$.
\begin{theorem}\label{t4} Given the Lie type $X$ then
\[ \liminf_{q \rightarrow \infty} \ \min \left \{ t(H)\ |\quad H\leq X(\mathbb{F}_q)\ \right \} \geq R.\]
\end{theorem}
The proof of this theorem does not depend on the classification of the finite simple groups, we use
instead the work of Larsen and Pink \cite{lpink} (which is a classification-free version of a result of Weisfeiler \cite{We}), and Liebeck, Saxl
and Seitz \cite{lss} (the latter for groups of exceptional type).
\textbf{Part II:}
Once Part I is proved, the argument reduces to an extremal problem on abelian groups:
\begin{theorem}\label{ab} Let $d$ and $R$ be fixed positive numbers. Suppose $A=C_{x_1}\times C_{x_2}\times \cdots \times C_{x_t}$ is an abelian group such that the orders $x_1,x_2,...,x_t$ of its cyclic factors do not repeat more than $d$ times each. Suppose that $r|A|^R\leq n$ for some positive integers $r$ and $n$. Then as $n,r$ tend to infinity we have
\[s_r(A)\leq n^{(\gamma +o(1))\frac{\log n}{\log \log n}},\]
where $\gamma=\frac{ (\sqrt{R(R+1)}-R)^2}{4R^2}$.
\end{theorem}
The proof of this for $R=1$ is given in \cite{GLP}. It is based on a quite difficult combinatorial analysis. The generalization for general $R$ in \cite{LN} is then straightforward.
\subsection*{Acknowledgments} In their work the authors were supported by
grants from the National Science Foundation (Goldfeld and Lubotzky), the Israel Science Foundation and the US-Israel Binational Science Foundation (Lubotzky) and Hungarian National Foundation for Scientific Research, Grant T037846 (Pyber). While this research was carried out Nikolov held a
Golda-Meir Postdoctoral Fellowship at the Hebrew University of
Jerusalem.
\begin{thebibliography}{99}
\bibitem{lub} A. Lubotzky, Subgroup growth and congruence subgroups, \emph{Inv.
Math. 119 (1995), 267-295.}
\bibitem{GLP}D. Goldfeld, A. Lubotzky, L. Pyber, Counting congruence subgroups,
\emph{to appear.}
\bibitem{LN} A. Lubotzky, N. Nikolov, Subgroup growth of lattices in semisimple Lie groups, \emph{to appear.}
\bibitem{margulis} G. Margulis, \emph{Discrete Subgroups of Semisimple Lie Groups}, Ergebnisse der Math. 17, Springer-Verlag, 1991.
\bibitem{serre} J-P. Serre, Le probl\`{e}me des groupes de congruence pour $\mathrm{SL}_2$, \emph{Ann. of Math. (2) 92, (1970), 489-527.}
\bibitem{ls} M. Liebeck, A. Shalev, Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks, \emph{preprint}.
\bibitem{MP} T. W. M\"{u}ller, J.-C. Puchta, Character theory of symmetric groups, subgroup growth of Fuchsian groups and random walks, \emph{preprint}.
\bibitem{bomb} E. Bombieri, On the large sieve, \emph{Mathematika 12 (1965), 201-225.}
\bibitem{murty} M. R. Murty, V. K. Murty,
A variant of the Bombieri-Vinogradov theorem, \emph{Canad. Math. Soc. Conference Proceedings 7 (1987), 243-272.}
\bibitem{LP} M. Liebeck, L. Pyber. Finite linear groups and bounded generation,
\emph{Duke Math. J. 107 (2001), no. 1, 159-171.}
\bibitem{lpink} M. Larsen, R. Pink, Finite subgroups of algebraic groups, \emph{J. Amer. Math. Soc. to appear.}
\bibitem{We} B. Weisfeiler, Post-classification version of Jordan's theorem on
finite linear groups, \emph{Proc. Nat. Acad. Sci U.S.A. 81 (1984), 5278-5279.}
\bibitem{lss} M. Liebeck, J. Saxl, G. Seitz, Subgroups of maximal rank in finite exceptional groups of Lie type, \emph{Proc. London Math. Soc.(3) 65 (1992), 297-325.}
\end{thebibliography}
\end{document}