SIEVING USING DIRICHLET SERIES

M. Ram Murty^{1}

1. Introduction.

Given a sequence of natural numbers, {a_{n}}_{n=1}^{∞}, there are at least three methods in analytic number theory to study properties of this sequence. The first is the method of Dirichlet series. One associates the Dirichlet series

f(s) = ∑_{n=1}^{∞} \frac{a_{n}}{n^{s}}

and tries to obtain analytic (or meromorphic) continuation of the series to a large enough domain. Then, from the analytic properties of f(s), one tries to obtain information on the growth of the coefficients, or the asymptotic properties of the summatory function

∑_{n≤x} a_{n}.

This can be viewed as the study of the sequence with respect to the usual (or archimedean) absolute value. A second method is via the sieve technique. One maps the sequence mod p as p ranges over a set of primes. Having some information about the images, one tries to infer properties of the original set. A third technique is the p-adic method, where the study is focussed on the divisibility of the sequence with respect to a single prime. One tries to get some p-adic analytic function to interpolate the values of the sequence and in this way study the sequence. This method can be viewed as the study of the sequence with respect to non-archimedean (or p-adic) absolute values. From this perspective, the sieve method stands at the interface of the other two methods.

It is however, not so well-known, that in many problems of a sieve nature, a simple method involving Dirichlet series can be invoked to obtain very precise information about the divisibility properties of a given sequence, especially when we are trying to sieve by a set of primes that can be described by what we call a Chebotarev condition (see the definition below). This method invokes a variant of the classical Wiener-Ikehara Tauberian theorem to derive the final asymptotic formula. Thus, the method cannot be deemed “elementary” both in the technical sense and the practical sense. For most applications, even this can be dispensed with and a simple argument using the sieve of Eratosthenes suffices. The purpose of this paper is to first describe how Dirichlet series can be used to obtain sieve estimates for certain types of problems, and second, how the sieve of Eratosthenes can also be used to obtain similar (albeit weaker) estimates.

1Research partially supported by an NSERC grant.

Our main purpose in this paper is to show that the sieve of Eratosthenes suffices to derive some of the results of [Se]. Our paper was inspired by Serre’s study of divisibility of Fourier coefficients of modular forms [Se]. There he applies the method of Dirichlet series to deduce various theorems concerning Fourier coefficients of Hecke eigenforms. A prototype of the theorems proved in [Se] can be described as follows. Let τ(n) be the Ramanujan τ-function, defined by the generating function

∑_{n=1}^{∞} τ(n)q^{n} = q ∏_{n=1}^{∞}(1 − q^{n})^{24}.

Fix a prime ℓ > 2. Then, almost all (in the sense of natural density) of the coefficients τ(n) are divisible by ℓ. Moreover,

#\{n ≤ x : τ(n) ≢ 0( mod ℓ)\} ∼ \frac{x}{(log x)^{α(ℓ)}}

for some 0 < α(ℓ) < 1.

After reviewing the method of Serre [Se] and making note of its virtues and limitations, we describe how the sieve of Eratosthenes can be invoked to get similar results, which are only “weaker” by a “log log x” factor. However, the latter method is more versatile and can be applied to contexts where the Chebotarev condition (or the “Frobenian property” as Serre calls it) may not hold. The last part of the paper deals with applications of the results.

Acknowledgements. I would like to thank Kalyan Chakraborty and Alina Cojocaru for their comments on an earlier version of this paper.

2. The Method of Dirichlet series.

Let P be a set of primes and let \overline{P} indicate its complement in the set of primes. One of the basic problems in sieve theory is to count the number of n ≤ x which are not divisible by any of the primes in P. In other words, we want to count the numbers ≤ x which are composed of primes solely belonging to \overline{P}. This suggests we define the Dirichlet series

f(s) = ∑_{n=1}^{∞} \frac{a_{n}}{n^{s}} = ∏_{p∈\overline{P}} (1 − \frac{1}{p^{s}} )^{−1}

so that a_{n} = 1 if n is not divisible by any prime of P and 0 otherwise. We are therefore interested in the summatory function

∑_{n≤x} a_{n}

which by the familiar Perron formula (see for example, [M, p. 54-57]) can be written as

\frac{1}{2πi} ∫_{2−i∞}^{2+i∞} f(s)\frac{x^{s}}{s} ds.

Clearly, f(s) converges absolutely in the region Re(s) > 1. Here is the variant of the classical Tauberian theorem that Serre uses.

Theorem 1. Suppose that we can write

f(s) = \frac{h(s)}{(s − 1)^{1−α}}

with h(s) holomorphic in the region Re(s) ≥ 1 and non-zero there. Then,

∑_{n≤x} a_{n} ∼ \frac{cx}{(log x)^{α}}

with c = h(1)/Γ(1 − α), where Γ is the usual Gamma function.

We will derive an application of this result which will be useful in some of the results to be derived below. This involves the enumeration of squarefull numbers. Recall that a natural number n is called squarefull if for every prime p|n, we have p^{2}|n. If we let a_{n} = 1 when n is squarefull and 0 otherwise, then it is easy to see that

g(s) = ∑_{n=1}^{∞} \frac{a_{n}}{n^{s}} = ∏_{p} (1 + \frac{1}{p^{2s}} + \frac{1}{p^{3s}} + ⋯) .

Notice that the Euler factor is, with x = p^{−s}, equal to

1 + x^{2}(1 − x)^{−1} = (1 − x^{2})^{−1}(1 + x^{3})

so that we can write it as

(1 − \frac{1}{p^{2s}} )^{−1} (1 + \frac{1}{p^{3s}} ) .

We see immediately that

g(s) = ζ(2s)h(s),

where h(s) is analytic for Re(s) > 1/3, and ζ(s) denotes the Riemann zeta function. Changing s to s − 1/2, we find that

∑_{n=1}^{∞} \frac{a_{n}\sqrt{n}}{n^{s}} = ζ(2s − 1)h(s − 1/2).

The right hand side is analytic in Re(s) ≥ 1 apart from a simple pole at s = 1. Theorem 1 implies

∑_{n≤x} a_{n}\sqrt{n} ∼ cx

for some non-zero constant c. Partial summation implies

∑_{n≤x} a_{n} ∼ c_{1}\sqrt{x}

for some non-zero constant c_{1}. We also deduce that

\begin{matrix}∑ & ′ \\ n>y \end{matrix} \frac{1}{n} ≪ \frac{1}{\sqrt{y}}

where the dash on the summation means that we sum over squarefull numbers. This fact, which will be useful below, easily follows by partial integration and we leave it as an exercise.

3. Applications.

We will say that a set of primes P satisfies the Chebotarev condition if there exists a Galois extension K/ℚ of finite degree with Galois group G and a subset D of G stable under conjugation such that for all primes p sufficiently large, p ∈ P if and only if the Artin symbol σ_{p}(K/ℚ) ∈ D. If we let β = |D|/|G| then it is easily seen by using the orthogonality relations for Artin L-functions that for P satisfying the Chebotarev condition,

∑_{p∈P} \frac{1}{p^{s}} = β log (\frac{1}{s − 1}) + θ(s)

where θ(s) is a function regular in Re(s) ≥ 1. One can apply Theorem 1 with α = 1 − β to deduce

∑_{n≤x} a_{n} ∼ \frac{cx}{(log x)^{1−β}}

for some constant c ≠ 0, where a_{n} = 1 if n is composed of only primes from P and is zero otherwise.

By considering the product

∏_{p∈P} (1 + \frac{1}{p^{s}} )

we see that Theorem 1 can be applied to show that

∑_{n≤x} μ^{2}(n)a_{n} ∼ \frac{c_{1}x}{(log x)^{1−β}} ,

where c_{1} is a non-zero constant and μ denotes the Möbius function. Thus, the number of squarefree n ≤ x composed of prime numbers of P also has similar asymptotic behaviour.

For example, if we wanted to count the number of natural numbers ≤ x which can be written as the sum of two squares, then by elementary number theory, we see that this is a sieve problem. After some reflection, this reduces to the counting of the number of n ≤ x which are not divisible by any prime ≡ 3( mod 4). This latter set of primes clearly satisfies the Chebotarev condition with K = ℚ(\sqrt{−1}) whose Galois group is of order two and we may take D to be the non-identity element. Thus, β = 1/2 and we deduce that the number of such integers is

∼ cx/\sqrt{log x},

for some non-zero constant.

A more striking example can be given with the Euler ϕ-function. Apart from ϕ(1) and ϕ(2), we note that ϕ(n) is always even. If we fix any odd prime ℓ, we can deduce that for almost all n, ϕ(n) is divisible by ℓ. Indeed, the set of primes ≢ 1( mod ℓ) satisfies the Chebotarev condition with K = ℚ(ζ_{ℓ}) whose Galois group is isomorphic to (ℤ/ℓℤ)^{∗} so that we may take for D the non-identity elements of the Galois group. This is because p ≡ 1( mod ℓ) if and only if p splits completely in K. Therefore, the number of n ≤ x, which are not divisible by a prime p ≡ 1( mod ℓ) is by Theorem 1,

∼ \frac{cx}{(log x)^{1/(ℓ−1)}} .

Therefore, almost all numbers are divisible by a prime p ≡ 1( mod ℓ). This means, for almost all numbers, ℓ divides ϕ(n).

The result involving Ramanujan’s τ-function follows from a result of Deligne [D] who showed the existence of an ℓ-adic representation

ρ_{ℓ} : Gal(\overline{ℚ}/ℚ)→GL_{2}(ℤ_{ℓ})

such that

Tr ρ_{ℓ}(σ_{p}) = τ(p), det ρ_{ℓ}(σ_{p}) = p^{11}.

By considering the “reduction mod ℓ” map, we obtain an extension K_{ℓ}/ℚ which is Galois and

Tr ρ_{ℓ}(σ_{p}) ≡ τ(p)( mod ℓ).

Therefore, primes p for which ℓ|τ(p) satisfy a Chebotarev condition. The corresponding β can be calculated from the image of Galois in GL_{2}(𝔽_{ℓ}). See [Se] for further details.

An equally striking result is that for algebraic number fields K of finite degree over ℚ, the Dedekind zeta function

ζ_{K}(s) = ∑_{𝔞} \frac{1}{N(𝔞)^{s}} = ∑_{n=1}^{∞} \frac{a_{n}}{n^{s}}

has the property that for almost all n, a_{n} = 0 whenever [K : ℚ] > 1. This is a generalization of the result cited above involving numbers that can be written as the sum of two squares, where in that case K = ℚ(i). To see this, let A(x) be the number of n ≤ x such that n = N(𝔞) has a solution. Let A^{∗}(x) be the number of such n which are squarefree. Since any natural number n can be written uniquely as n = uv, with (u, v) = 1, v squarefull and u squarefree, we see that

A(x) = ∑_{v≤x} A^{∗}(x/v).

This sum can be split into two parts, the first being those with v < z and the second with z ≤ v ≤ x. Using the trivial estimate of x/v for A^{∗}(x/v) in the second sum and applying the remark made at the end of the previous section, we find

∑_{z≤v≤x} A^{∗}(x/v) ≪ \frac{x}{\sqrt{z}} .

If we choose z = log x, we find that the contribution from the second sum is o(x) and hence negligible. Now if n is squarefree, a necessary condition for the equation n = N(𝔞) to have a solution is that 𝔞 is composed of prime ideals of degree 1 over ℚ. That is, n must be divisible by primes p which have a degree one prime ideal lying above it in K. This is clearly a set of primes satisfying a Chebotarev condition. We can make this more precise. If K̃ denotes the Galois closure of K over ℚ, and H is the subgroup of G = Gal(K̃/ℚ) that fixes K, then p has a first degree prime ideal in K lying above it if and only if σ_{p}(K̃/ℚ) belongs to some conjugate of H. If we let

D = ⋃_{g∈G} gHg^{−1}

then D is stable under conjugation and we may apply Theorem 1 with α = 1 − β with β = |D|/|G|. It is an elementary exercise in group theory that 0 < β < 1. Indeed, each of the distinct conjugates have the identity element in common and therefore,

|D| ≤ 1 + (|H| − 1)[G : H] = |G| − [G : H] + 1 < |G|

if [G : H] > 1 which is the same as saying K ≠ ℚ. By our previous remarks, we deduce

A^{∗}(x) ∼ \frac{c_{1}x}{(log x)^{1−β}} .

Inserting this estimate above in the first sum to be considered, we find

A(x) ≪ \begin{matrix}∑ & ′ \\ v<z \end{matrix} \frac{x}{v(log x)^{1−β}} .

Since the sum

\begin{matrix}∑ & ′ \\ v \end{matrix} \frac{1}{v}

converges, we find that the total estimate is o(x), as desired.

The above situation is a special case of a more general phenomenon involving Artin L-series. If

L(s, χ) = ∑_{n=1}^{∞} \frac{a_{n}}{n^{s}}

is an Artin L-function attached to a Galois extension of ℚ, such that the set S of elements g belonging to the Galois group with χ(g) = 0 is non-empty, then almost all of the coefficients a_{n} vanish. The argument to prove this proceeds as above. By the Chebotarev density theorem, the set P of primes p whose Artin symbol belongs to S has a positive density and hence is Chebotarev. We can proceed as above and deduce that the number of n ≤ x such that a_{n} ≠ 0 is

O (\frac{x}{(log x)^{δ}} )

for some δ > 0.

By taking the permutation representation attached to a subgroup H of the Galois group, we see that the Artin L-function is the Dedekind zeta function of the fixed field of H. Indeed, if V is the ℂ-vector space with basis {e_{g_{i}H}}, indexed by the cosets of H, the permutation representation r_{G/H} of G attached to the cosets of H is given by the action g ·e_{g_{i}H} = e_{gg_{i}H} for g ∈ G. It is now straightforward to calculate the character of this representation and we see it is induced from the trivial representation of the subgroup H (see [S, p. 29]). By the invariance of Artin L-series under induction, it follows that the Artin L-series attached to χ = tr r_{G/H} is equal to the Dedekind zeta function of the fixed field of H. The condition on χ, namely that the set of elements g such that χ(g) = 0, is satisfied provided that H is a proper subgroup of the Galois group. In this way, we can retrieve the earlier result about the vanishing of the coefficients of the Dedekind zeta function.

If χ is an irreducible character of the Galois group, then it is a classical result of Burnside (see Isaacs [Is, p. 40]) that there exist elements g such that χ(g) = 0 whenever χ(1) > 1. The proof of this fact is not difficult. For the sake of completeness, we sketch it here. The first step is to show that if G is a finite cyclic group, and S is the set of elements that generate G, then for any character (possibly reducible) of G, we have

∑_{s∈S} |χ(s)|^{2} ≥ |S|,

whenever χ(s) ≠ 0 for all s ∈ S. Indeed, the product

∏_{s∈S} |χ(s)|^{2}

is an element of the cyclotomic field ℚ(ζ_{n}), where n = |G| and it is invariant under the action of the Galois group of ℚ(ζ_{n})/ℚ. Since the product is nonzero, it must be ≥ 1. The result follows by applying the arithmetic-geometric mean inequality. If now, χ is an irreducible character of a group G with χ(1) > 1, the second step is to partition G into equivalence classes of elements that generate the same cyclic subgroup. If χ(g) ≠ 0 for all g ∈ G, then for each equivalence class S, we have by the above

∑_{s∈S} |χ(s)|^{2} ≥ |S|.

Summing this over all equivalence classes of non-identity elements gives

∑_{g≠1} |χ(g)|^{2} ≥ |G| − 1.

But as χ is irreducible, we have

|G| = ∑_{g∈G} |χ(g)|^{2} ≥ |G| − 1 + χ(1)^{2},

which is a contradiction if χ(1) > 1.

4. The sieve of Eratosthenes.

The classical method of Eratosthenes allows us to deduce a crude estimate for the sum function in Theorem 1, which is useful in many instances when, for example, the hypothesis of Theorem 1 are not satisfied. If we let P(z) to be the product of the primes p ∈ P, with p ≤ z, then the usual inclusionexclusion principle gives the upper bound

(1)  ∑_{n≤x} a_{n} = ∑_{d|P(z)} μ(d) [\frac{x}{d}] ≤ x ∏_{{p∈P \atop p≤z}} (1 − \frac{1}{p}) + O(2^{z}).

This simple inequality allows us to prove:

Theorem 2. Suppose that

∑_{p≤z,p∈P} \frac{1}{p} ≥ α log log z + O(1).

Then,

∑_{n≤x} a_{n} ≪ \frac{x}{(log log x)^{α}} .

Proof. We apply the elementary inequality 1 − t ≤ e^{−t} to the product in (1) to deduce

∑_{n≤x} a_{n} ≤ x exp (− ∑_{p≤z,p∈P} \frac{1}{p}) + O(2^{z}).

Choosing z = c log x, with c sufficiently small, gives the result.

As indicated in [MS],Theorem 2 can be sharpened by observing that in the sum in (1), we have the condition that d ≤ x. If we denote by G(x, z) the number of n ≤ x all of whose prime factors are ≤ z and belong to P, then, the estimate (1) can be written as

(2)  ∑_{n≤x} a_{n} ≤ x ∑_{d|P(z),d≤x} \frac{μ(d)}{d} + O(G(x, z)).

When P is the set of all prime numbers, the function G(x, z) has been well studied in sieve theory and precise information about its behaviour exists. For our purposes however, we can derive an elementary estimate following Rankin (see [M, p. 130]) in our slightly general context.

Lemma 3. Suppose that

∑_{p≤z,p∈P} \frac{log p}{p} ≤ α log x + O(1).

Then,

G(x, z) ≪ x(log z)^{α} exp (−\frac{log x}{log z}) .

Proof. For any δ > 0, we clearly have

G(x, z) ≤ \begin{matrix}∑ & ′ \\ n≤x \end{matrix} (\frac{x}{n})^{δ}

where the dash on the summation indicates that p|n implies p ≤ z, p ∈ P. Writing δ = 1 − η, and using the inequality e^{t} ≤ 1 + te^{t}, we obtain

G(x, z) ≤ x exp (−η log x + ∑_{p≤z,p∈P} \frac{1}{p} + ηz^{η} ∑_{p≤z,p∈P} \frac{log p}{p}) .

By partial summation

∑_{p≤z,p∈P} \frac{1}{p} ≤ α log log z + O(1).

Inserting this estimate as well as the estimate in the hypothesis, we obtain

G(x, z) ≤ x exp (−η log x + α log log z + ηz^{η}(α log z + O(1))) .

We choose η = 1/ log z to obtain

G(x, z) ≪ x(log z)^{α} exp (−\frac{log x}{log z}) .

This completes the proof.

Lemma 3 allows us to insert a very good estimate for the error term in (2). However, it remains to consider the main term. This is handled as in [MS]. Clearly,

∑_{d|P(z),d≤x} \frac{μ(d)}{d} = ∑_{d|P(z)} \frac{μ(d)}{d} − ∑_{d|P(z),d>x} \frac{μ(d)}{d}.

We estimate the latter sum in the following lemma. Lemma 4. If

∑_{p≤z,p∈P} \frac{log p}{p} ≤ α log z + O(1),

then,

∑_{d|P(z),d>x} \frac{1}{d} ≪ (log z)^{α+1} exp (−\frac{log x}{log z}) .

Proof. Clearly, the sum in question is by partial summation,

≪ ∫_{x}^{∞} \frac{G(t, z)}{t^{2}}dt

and inserting the estimate from Lemma 3, and changing variables, we are reduced to estimating

(log z)^{1+α} ∫ ∞_{\frac{log x}{log z}} e^{−u}du.

The integral is estimated as

≪ exp (−\frac{log x}{log z}) ,

which implies the result.

We can combine both of these lemmas and deduce: Theorem 5. Suppose that

∑_{p≤z,p∈P} \frac{log p}{p} ≤ α log z + O(1).

Then,

(3)  ∑_{n≤x} a_{n} = x ∏_{p≤z,p∈P} (1 − \frac{1}{p}) + O (x(log z)^{α+1} exp (−\frac{log x}{log z})) .

Corollary 6. If in addition, we have

∑_{p≤z,p∈P} \frac{log p}{p} = α log z + O(1),

then

∑_{n≤x} a_{n} ≪ x (\frac{log log x}{log x})^{α} .

Proof. By partial summation, the hypothesis implies

∑_{p≤z,p∈P} \frac{1}{p} = α log log z + O(1).

As explained before, inserting this fact into the main term gives us an estimate of

\frac{x}{(log z)^{α}}

for the term involving the product in (3). If we choose

log z = \frac{A log x}{log log x}

for a sufficiently large constant A, we immediately obtain the result.

It is possible to get a slightly better result than this with a sharper choice of z. The improvement is only marginal and any effort in that direction seems to destroy the elementary nature of the derivation. (See the remark on p. 1110 in [MS].)

References

[D] P. Deligne, Formes modulaires et représentations ℓ-adiques, Séminaire Bourbaki, 1968 /69, exposé 355, p. 139-172. - Berlin, Springer - Verlag, 1971 (Lecture Notes in Mathematics, 179).

[Is] M. Isaacs, Character Theory of Finite Groups, 1976, Dover.

[M] M. Ram Murty, Problems in Analytic Number Theory, GTM/RIM, Vol 206, Springer-Verlag, 2001.

[MS] M. Ram Murty and N. Saradha, On the sieve of Eratosthenes, Canadian Journal of Mathematics, 39 (1987), 1107-1122.

[Se] J.-P. Serre, Divisibilité de certaines fonctions arithmétiques, L’Enseignement Math., 22 (1976), 227-260.

[S] J.-P. Serre, Linear representations of Finite Groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, 1977.

M. Ram Murty, Department of Mathematics, Queen’s University, Kingston, Ontario, K7L 3N6, Canada murty@mast.queensu.ca