Counting Primes, Groups and Manifolds

Dorian Goldfeld^{1}, Alexander Lubotzky^{2}, Nikolay Nikolov^{3} and László Pyber^{4}

July 27, 2005

Addresses:

1. Department of Mathematics, Columbia University, New York, NY 10027, U.S.A.,

2. Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel,

3. Tata Institute for Fundamental Research, Colaba, Mumbai 400005, India,

4. A. Rényi Institute of Mathematics, Reáltanoda ut. 13-15, H-1053, Budapest, Hungary.

Corresponding author: Alexander Lubotzky, tel +972 2 6584387, e-mail: alexlub@math.huji.ac.il .

Pages: 11 (double spaced). Wordcount: abstract 150, main text 2200. PNAS Classification. Physical sciences: Mathematics. 2000 Mathematics Subject Classification 20H05; 22E40

Abstract

Let Λ = SL_{2}(ℤ) be the modular group and let c_{n}(Λ) be the number of congruence subgroups of Λ of index at most n. We prove that lim_{n→∞} \frac{log c_{n}(Λ)}{(log n)^{2}/ log log n} = \frac{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 Γ is an irreducible lattice of G it turns out that the subgroup growth of Γ 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.

Statement of results: arithmetic groups

Let n be a large integer, Γ a finitely generated group and M a Riemannian manifold. Denote by π(n) the number of primes less or equal to n, s_{n}(Γ) is the number of subgroups of Γ of index at most n and b_{n}(M) is the number of covers of M of degree at most n. The aim of this note is to announce results which show that in some circumstances, these three seemingly unrelated functions are very much connected. This happens, for example, when Γ is an arithmetic group, in which case it is also the fundamental group of a suitable locally symmetric finite volume manifold M. The studies of s_{n}(Γ) and b_{n}(M) are then almost the same. Moreover, if Γ has the congruence subgroup property then estimating s_{n}(Γ) boils down to counting congruence subgroups of Γ. The latter is intimately related to the classical problem of counting primes. To present our results we need more notation.

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 O_{S} denote the ring of S-integers of k and set Γ = G(O_{S}). A subgroup H ≤ Γ is called a congruence subgroup if there is some ideal I ◁ O_{S} such that H contains the kernel of the homomorphism Γ → G(O_{S}/I).

Let c_{n}(Γ) denote the number of congruence subgroups of index at most n in Γ. The counting of congruence subgroups in arithmetic groups has already played a role in the proof of one of the main results of the theory of subgroup growth: A finitely generated residually finite group Γ has polynomial subgroup growth (i.e. s_{n}(Γ) = n^{O(1)}) if and only if Γ is virtually solvable of finite rank (cf. [?] and the references therein). That theorem required only a weak lower bound on the number congruence subgroups. In [?] Lubotzky proved a more precise result: there exist numbers a, b depending on G, k and S, such that^{∗}

n^{\frac{a log n}{log log n}} ≤ c_{n}(Γ) ≤ n^{\frac{b log n}{log log n}} ,

∗ The lower bound depended on GRH at the time but was made unconditional in [?]

and, moreover the sequence s_{n}(Γ) 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}(Γ). (All logarithms are in base e.)

Let X be the Dynkin diagram of the split form of G (e.g. X = A_{n−1} if G = SU_{n}). Let h be the Coxeter number of the root system Φ corresponding to X (it is the order of the Coxeter element of the Weyl group of X). Then h = \frac{|Φ|}{l} where l = rank_{ℂ}(G) = rank(X), and for later use define R := h/2. Let

γ(G) = \frac{(\sqrt{h(h + 2)} − h)^{2}}{4h^{2}} .

Let GRH denote the Generalized Riemann Hypothesis for Artin-Hecke Lfunctions of number fields as stated in [?]. The GRH implies in particular:

Let k be a Galois number field of degree d over the rationals and let q be a prime such that the cyclotomic field of q-th roots of unity is disjoint from k. Denote by π_{k}(x, q) the number of primes p with p ≤ x, p ≡ 1( mod q) and p splits completely at k. Then

|π_{k}(x, q) − \frac{x}{dϕ(q) log x}| < Cx^{\frac{1}{2}} log x log q

for some constant C = C(k) > 0 depending only on k (a more precise bound is given in [?]).

The lower bound for the limit in the following Theorem was proved in [?] and the upper bound in [?]:

Theorem 1 Let G, Γ and γ(G) be as defined above. Assuming GRH we have

lim_{n→∞} \frac{log c_{n}(Γ)}{(log n)^{2}/ log log n} = γ(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 ℚ or a Galois extension of degree less than 42.

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 [?] the crucial special case of Γ = SL_{2}(O_{S}) is proved in full. There we have γ(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.

Lattices

Let H be a connected characteristic 0 semisimple group. By this we mean that H = ∏_{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 rank_{K_{i}}(G_{i}) ≥ 1). Let Γ be an irreducible lattice of H, i.e. for every infinite normal subgroup N of H the image of Γ in H/N is dense there.

Assume now that

rank(H) := ∑_{i=1}^{r} rank_{K_{i}}(G_{i}) ≥ 2.

By Margulis’ Arithmeticity Theorem ([?]) every irreducible lattice Γ in H is arithmetic. Also the split forms of the factors G_{i} of H are necessarily of the same type and we set γ(H) := γ(G_{i}).

Moreover, a famous conjecture of Serre ([?]) asserts that such a group Γ has the congruence subgroup property. It has been proved in many cases. This enables us to prove: Theorem 2 Assuming GRH and Serre’s conjecture, then for every non-compact higher rank characteristic 0 semisimple group H and every irreducible lattice Γ in H the limit

lim_{n→∞} \frac{log s_{n}(Γ)}{(log n)^{2}/ log log n}

exists and equals γ(H), i.e. it is independent of the lattice Γ.

Moreover the above holds unconditionally if H is a simple connected Lie group not locally isomorphic to D_{4}(ℂ) and Γ is a non-uniform lattice in H (i.e. H/Γ is non-compact).

Theorem 2 shows, in particular, some algebraic similarity between different lattices Γ in the same Lie group G. This is an addition to other results in the theory e.g. Furstenberg’s theorem showing that the boundaries of all such Γ’s are the same or Margulis super-rigidity, which shows that the finite dimensional representation theory of the different Γ’s in the same G are similar. (cf [?] and the references therein).

We point out the following geometric reformulation of the special case:

Theorem 3 Let H be a simple connected Lie group of ℝ-rank ≥ 2 which is not locally isomorphic to D_{4}(ℂ). 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_{n→∞} \frac{log b_{n}(M)}{(log n)^{2}/ log log n} exists, equals γ(H) and is independent of M.

It is interesting to compare Theorems 2 and 3 with the results of Liebeck-Shalev[?], and Müller-Puchta [?]: If H = SL_{2}(ℝ) and Γ is a lattice in H then lim_{n→∞} \frac{log s_{n}(Γ)}{log n!} = −χ(Γ), where χ is the Euler characteristic.

We finally mention a conjecture and a question: Let X be the symmetric space associated with a simple Lie group H as in Theorem 3. Denote by m_{n}(X) the number of manifolds covered by X of volume at most n. By a well known result of Wang [?], this number is finite unless H is locally isomorphic to SL_{2}(ℝ) or SL_{2}(ℂ).

Conjecture. If ℝ-rank(H) ≥ 2 then

lim_{n→∞} \frac{log m_{n}(X)}{(log n)^{2}/ log log n} = γ(H).

Question: Estimate m_{n}(X) for the case of H having ℝ-rank equal to one. For H = SO(n, 1) the results of [?] suggest that lim_{n→∞} \frac{log m_{n}(H)}{log n!} may exist, but we do not have any clue what it could be.

Proofs: the lower bound

We shall illustrate the main idea of the proof with Γ = SL_{d}(ℤ) and refer to [?] for the full details.

Choose any ρ ∈ (0, \frac{1}{2}). For x >> 0 and a prime q < x let P (x, q) be the set of primes p ≤ x such that p ≡ 1 mod q. Let L(x, q) = |P (x, q)| and M(x, q) = ∑_{p∈P (x,q)} log p. Then the Bombieri-Vinogradov Theorem [?] ensures the existence of a prime q ∈ (\frac{x^{ρ}}{log x}, x^{ρ}) such that

L(x, q) = \frac{x}{ϕ(q) log x}+O (\frac{x}{ϕ(q)(log x)^{2}} ); M(x, q) = \frac{x}{ϕ(q)}+O (\frac{x}{ϕ(q)(log x)^{2}} ) .

Put L := L(x, q) and M := M(x, q).

By strong approximation (cf. [?], Window 9) Γ maps onto G_{P} := ∏_{p∈P (x,q)} SL_{d}(𝔽_{p}). Let B(p) be the subgroup of upper triangular matrices of SL_{d}(𝔽_{p}) and set

B_{P} := ∏_{p∈P (x,q)} B(p).

The group B_{P} maps onto the diagonal ∏_{p}(𝔽_{p}^{∗})^{d−1} which in turn maps onto 𝔽_{q}^{(d−1)L}. For fixed σ ∈ (0, 1) ∩ \frac{1}{L(d−1)}ℕ the latter vector space has about q^{σ(1−σ)(d−1)^{2}L^{2}} subgroups of index q^{σ(d−1)L} (see Proposition 1.5.2 in [?]), each giving rise to a subgroup of index n = [G_{P} : B_{P}]q^{σ(d−1)L} in Γ. Now log[G_{P} : B_{P}] ∼ d(d − 1)M/2 as x → ∞ and after some algebraic manipulations we obtain that for this chosen value of n

\frac{log c_{n}(Γ)}{(log n)^{2}/ log log n} ≥ \frac{σ(1 − σ)ρ(1 − ρ)}{(σρ + R)^{2}} − o(1), (x → ∞)

where in our case R = d/2. As shown in [?] §3 the maximum value of the above expression for σ, ρ ∈ (0, 1) is precisely γ(G) = ^{\frac{(\sqrt{R(R+1)}−R)^{2}}{4R^{2}}} and is achieved for σ_{0} = ρ_{0} = \sqrt{R(R + 1)} − R. By taking x sufficiently large we can choose σ ∈ (0, 1) ∩ \frac{1}{L(d−1)}ℕ to be arbitrarily close to σ_{0}, and take ρ = ρ_{0}. This proves the lower bound.

The reason for invoking the GRH in Theorem ?? is that in the general case we need an equivalent of the Bombieri-Vinogradov theorem for k in place of ℚ.

The work of M.R. Murty and V.K. Murty [?] gives an analogue of it for number fields but their result is weaker in general. It suffices for our needs when, for example k/ℚ, is an abelian extension.

The upper bound

The proof of the upper bound in [?] is inspired by the special case solved in [?] and has two parts:

I. A reduction to an extremal problem for abelian groups, and

II. Solving this extremal problem (Theorem ?? below).

Part I:

The subgroup structure of the groups SL_{2}(𝔽_{p}) is completely known. Using this it is shown in [?] that Theorem ?? for SL_{2}(ℤ) is equivalent to the following extremal result on counting subgroups of abelian groups:

Let C_{m} denote the cyclic group of order m. For all pairs P_{−} and P_{+} of disjoint sets of primes, let

f(n) := max {s_{r}(X) | X = ∏_{p∈P_{−}} C_{p−1} × ∏_{p∈P_{+}} C_{p+1} } ,

where the maximum is taken over all sets P_{−}, P_{+} and r ∈ ℕ such that n ≥ r ∏_{p∈P} p, (here P = P_{−} ∪ P_{+}).

Theorem 4 We have

lim sup_{n→∞} \frac{log c_{n}(SL_{2}(ℤ))}{(log n)^{2}/ log log n} = lim sup_{n→∞} \frac{log f(n)}{(log n)^{2}/ log log n}.

By contrast there is no such precise description of the subgroup structure even for SL_{n}(𝔽_{p}). Still, surprisingly, the proof of the general upper bound reduces to a similar extremal problem for abelian groups using some ideas of [?], [?] and the following Theorem which is the main new ingredient in [?].

Let X(𝔽_{q}) be a finite quasisimple group of Lie type X over the finite field 𝔽_{q} of characteristic p > 3. For a subgroup H of X(𝔽_{q}) define

t(H) = \frac{log[X(𝔽_{q}) : H]}{log |H^{♢}|},

where H^{♢} denotes the maximal abelian quotient of H whose order is coprime to p. Set t(H) = ∞ if |H^{♢}| = 1.

Recall that R = R(X) = h/2 where h is the Coxeter number of the root system of the split Lie type corresponding to X.

Theorem 5 Given the Lie type X then

lim inf_{q→∞} min {t(H) | H ≤ X(𝔽_{q}) } ≥ R.

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 [?] (which is a classification-free version of a result of Weisfeiler [?]), and Liebeck, Saxl and Seitz [?] (the latter for groups of exceptional type).

Part II:

Once Part I is proved, the argument reduces to an extremal problem on abelian groups:

Theorem 6 Let d and R be fixed positive numbers. Suppose A = C_{x_{1}} × C_{x_{2}} × ⋯×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} ≤ n for some positive integers r and n. Then as n, r tend to infinity we have

s_{r}(A) ≤ n^{(γ+o(1)) \frac{log n}{log log n}} ,

where γ = ^{\frac{(\sqrt{R(R+1)}−R)^{2}}{4R^{2}}} .

The starting point of the proof of this theorem in [?] is a well-known formula for counting subgroups of finite abelian groups (see [?]). We refer the reader to [?] for the details which are too complicated to be given here.

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.

References

[1] A. Lubotzky, D. Segal, Subgroup growth, Progress in Mathematics 212, Birkäuser, Boston, 2003.

[2] A. Lubotzky, Subgroup growth and congruence subgroups, Inv. Math. 119 (1995), 267-295.

[3] D. Goldfeld, A. Lubotzky, L. Pyber, Counting congruence subgroups, to appear.

[4] A. Weil, Sur les “formules explicites” de la théorie des nombres premiers, Oeuvres Scientifiques, Springer-Verlag, Volume II, 48 - 61.

[5] M. R. Murty, V. K. Murty, N. Saradha, Modular forms and the Chebotarev density theorem. Amer. J. Math. 110 (1988), no. 2, 253–281.

[6] A. Lubotzky, N. Nikolov, Subgroup growth of lattices in semisimple Lie groups, to appear.

[7] E. Bombieri, On the large sieve, Mathematika 12 (1965), 201-225.

[8] G. Margulis, Discrete Subgroups of Semisimple Lie Groups, Ergebnisse der Math. 17, Springer-Verlag, 1991.

[9] J-P. Serre, Le problème des groupes de congruence pour SL_{2}, Ann. of Math. (2) 92, (1970), 489-527.

[10] M. Liebeck, A. Shalev, Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks, preprint.

[11] T. W. Müller, J.-C. Puchta, Character theory of symmetric groups, subgroup growth of Fuchsian groups and random walks, preprint.

[12] H. C. Wang, Topics on totally discontinuous groups, Symmetric Spaces (W. Boothby, G. Weiss, eds.), M. Dekker (1972), 460–487.

[13] M. Burger, T. Gelander, A. Lubotzky, S. Mozes, Counting hyperbolic manifolds, Geometric and Functional Analysis (GAFA), Vol. 12 (2002) 1161-1173.

[14] M. R. Murty, V. K. Murty, A variant of the Bombieri-Vinogradov theorem, Canad. Math. Soc. Conference Proceedings 7 (1987), 243-272.

[15] M. Liebeck, L. Pyber. Finite linear groups and bounded generation, Duke Math. J. 107 (2001), no. 1, 159-171.

[16] M. Larsen, R. Pink, Finite subgroups of algebraic groups, J. Amer. Math. Soc. to appear.

[17] B. Weisfeiler, Post-classification version of Jordan’s theorem on finite linear groups, Proc. Nat. Acad. Sci U.S.A. 81 (1984), 5278-5279.

[18] M. Liebeck, J. Saxl, G. Seitz, Subgroups of maximal rank in finite exceptional groups of Lie type, Proc. London Math. Soc.(3) 65 (1992), 297-325.

[19] L. M. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc. 101 (1987), 771-775.