The Turán Sieve Method and Some of its Applications

Yu-Ru Liu and M. Ram Murty Department of Mathematics and Statistics Queen’s University Kingston, Ontario K7L 3N6

July 16, 1998

Abstract

We introduce the Turán sieve method and apply it to the probabilistic Galois theory problems in both the rational number field and the function field cases. We estimate the number of polynomials of degree n and height ≤ N whose Galois group is a proper subgroup of S_{n}. For the rational number field case, we get an estimate of O(N^{n−1/3} log N) and in the case of the function field over 𝔽_{q}, we get O((q^{N+1})^{n−1}N).

1 Introduction.

In 1934, Paul Turán gave a very simple proof of the celebrated theorem of Hardy and Ramanujan that the normal number of distinct prime factors of a natural number n is log log n. If ν(n) denotes the number of distinct prime factors of n, Turán proved that

∑_{n≤x}(ν(n) − log log n)^{2} = O(x log log x)

from which the normal order of ν(n) is easily deduced. The summation on the left hand side looks very much like the variance of the ‘random variable’ ν(n). Indeed, this similarity was amplified by Linnik when he developed the powerful large sieve method. However, Turán’s original derivation of the Hardy-Ramanujan Theorem has concealed in it, in seed form, an elementary sieve method. Undoubtedly, many of the experts are aware of this and have in fact used the method (dubbed ‘the normal order method’ in Hooley [?]) to solve cognate problems. Nowhere in the literature is the inherent sieve method in Turán’s derivation clearly exposed.

The purpose of this paper is to derive the ‘Turán sieve method’ and indicate a few of its applications. Most notably, we apply the method to determine the probability that a random polynomial of degree n, either in ℤ[x] or 𝔽_{q}[t, x], has Galois group equal to to S_{n}. This was treated by Gallagher in the ℤ[x] case by using the large sieve method. We also treat this case. Though our result is weaker than Gallagher’s, our method is far simpler. It is surprising that in the function field case (which is not treated by Gallagher) the elementary Turán sieve gives the correct exponent in the estimate. (See Theorem 3).

We now described the Turán’s sieve in an abstract setting.

Let S be a finite set and I be an index set. For each i ∈ I, we use Ω(i) to denote some specified conditions and define

S_{i} = {s ∈ S : s satisfies Ω(i)}.

For each s ∈ S, we define

π_{s}(I) = #{i ∈ I : s satisfies Ω(i)}.

Since S is a finite set, we can write

\frac{|S_{i}|}{|S|} = δ_{i} + r_{i},

here r_{i} is choosen to be relatively small with respect to δ_{i}.

For different i, j ∈ I, we assume that

\frac{|S_{i} ∩ S_{j}|}{|S|} = δ_{i}δ_{j} + r_{i,j},

where r_{i,j} is choosen to be relatively small with respect to δ_{i}δ_{j}. We say S_{i} and S_{j} are quasi-independent.

Theorem 1 (The Turán sieve) Let ν = ∑_{i∈I} δ_{i}, then

\frac{1}{|S|} ∑_{s∈S}(π_{s}(I) − ν)^{2} = ∑_{i∈I} δ_{i}(1 − δ_{i}) + ∑_{i,j∈I} r_{i,j} − 2ν ∑_{i∈I} r_{i}

here we use the convention that r_{i,i} = r_{i}.

Fix n ∈ ℕ and let F (x) = x^{n} +a_{1}x^{n−1} +⋯+a_{n} ∈ ℤ[x]. We denote Gal(F) to be the Galois group of the splitting field of F over ℚ. Since F (x) is of degree n, Gal(F) is a subgroup of S_{n}. The probabilistic Galois theory problem is to estimate the number of monic polynomials of degree n whose Galois group is a proper subgroup of S_{n}. We define the height of F, H(F), to be

H(F) = max{1, |a_{1}|, |a_{2}|, ⋯, |a_{n}|}.

Apply the Turán sieve, we get

Theorem 2

E_{n}(N) = #{F (x) ∈ ℤ[x] : deg(F) = n, F is monic, H(F) ≤ N and
Gal(F) ⫋ S_{n}}
≪ N^{n−1/3}(log N)^{2}.

Similarly, we can consider the probabilistic Galois theory problem in the function field over 𝔽_{q}. By the Turán sieve, we obtain

Theorem 3

P_{n}(N) = #{F (x) = x^{n} + a_{1}(t)x^{n−1} + a_{2}(t)x^{n−2} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x],
H(F) ≤ N and Gal(F) ⫋ S_{n}}
≪ (q^{(N+1)})^{n−1}N.

here the height of F, H(F), is defined to be

H(F) = max{deg(a_{i}(t)), 1 ≤ i ≤ n}.

2 Proof of the Turán Sieve.

In this section, we prove the Turán sieve.

Proof of Theorem 1 :

\begin{aligned}\frac{1}{|S|} ∑_{s∈S}(π_{s}(I) − ν)^{2} & = \frac{1}{|S|} ∑_{s∈S}(π_{s}(I))^{2} − \frac{2ν}{|S|} ∑_{s∈S} π_{s}(I) + ν^{2} \\ & = S_{1} − S_{2} + ν^{2} (say) \end{aligned}

From the definition of π_{s}(I),

S_{1} = \frac{1}{|S|} ∑_{s∈S}(π_{s}(I))^{2} = \frac{1}{|S|} ∑_{s∈S}(∑_{{i∈I \atop s∈S_{i}}} 1)^{2}.

Interchanging the order of summation and rearranging terms gives :

S_{1} = \frac{1}{|S|} ∑_{i,j∈I} ∑_{s∈S_{i}∩S_{j}} 1 = ∑_{{i,j∈I \atop i≠j}} \frac{|S_{i} ∩ S_{j}|}{|S|} + ∑_{i∈I} \frac{|S_{i}|}{|S|}.

By the definition of δ_{i}, r_{i} and r_{i,j}, one finds

\begin{aligned}S_{1} & = ∑_{{i,j∈I \atop i≠j}} δ_{i}δ_{j} + ∑_{{i,j∈I \atop i≠j}} r_{i,j} + ∑_{i∈I} δ_{i} + ∑_{i∈I} r_{i} \\ & = (∑_{i∈I} δ_{i})^{2} − ∑_{i∈I} δ_{i}^{2} + ∑_{i,j∈I} r_{i,j} + ∑_{i∈I} δ_{i}. \end{aligned}  (1)

Similarly, we can show that

S^{2} = 2ν ∑_{i∈I} δ^{i} + 2ν ∑_{i∈I} r^{i}.  (2)

Combining equation (1) and (2) yields

\begin{aligned}S_{1} − S_{2} + ν^{2} & = (∑_{i∈I} δ_{i} − ν)^{2} + ∑_{i∈I} δ_{i}(1 − δ_{i}) + ∑_{i,j∈I} r_{i,j} − 2ν ∑_{i∈I} r_{i} \\ & = ∑_{i∈I} δ_{i}(1 − δ_{i}) + ∑_{i,j∈I} r_{i,j} − 2ν ∑_{i∈I} r_{i}. \end{aligned}

Corollary 1

#\{s ∈ S : π_{s}(I) = 0\} ≤ \frac{|S|}{ν} + \frac{|S|}{ν^{2}} ∑_{i,j∈I} |r_{i,j}| + \frac{2|S|}{ν} ∑_{i∈I} |r_{i}|.

Proof: Since (1 − δ_{i}) ≤ 1, by Theorem 1,

∑_{s∈S}(π_{s}(I) − ν)^{2} ≤ |S|ν + |S| ∑_{i,j∈I} |r_{i,j}| + 2|S| ∑_{i∈I} |r_{i}|.

Notice that

ν^{2}#{s ∈ S : π_{s}(I) = 0} ≤ ∑_{s∈S}(π_{s}(I) − ν)^{2},

Corollary 1 follows.

3 Probabilistic Galois Theory in the rational number field.

We want to get an upper bound for

E_{n}(N) = #{F (x) ∈ ℤ[x] : deg(F) = n, F is monic,
H(F) ≤ N and Gal(F) ⫋ S_{n}}.

Let 𝔽_{p} be the finite field and let 𝔽_{p}[x] be the ring of polynomials in x with coefficients in 𝔽_{p}. It is a Euclidean domain, and hence is a unique factorization domain.

Lemma 1 Let N_{k} be the number of monic irreducible polynomials in 𝔽_{p}[x] with degree k. Then

N_{k} = \frac{1}{k} ∑_{d|k} μ(d)p^{\frac{k}{d}} ,

where μ(d) is the Möbius function.

Proof: Define a set

A = {f(x) ∈ 𝔽_{p}[x] : f(x) is monic }.

Applying the method used to prove the Euler product for the Riemann zeta-function, we have

∑_{f∈A} T^{deg(f)} = ∏_{p∈A p is irreducible}(1 − T^{deg(p)})^{−1}

= ∏_{k=1}^{∞}(1 − T^{k})^{−N_{k}}.

On the other hand, for a fixed degree k, the number of polynomials in A with degree k is p^{k}. So,

∑_{f∈A} T^{deg(f)} = ∑_{k=o}^{∞} p^{k}T^{k} = \frac{1}{1 − pT} .

Hence, we have

\frac{1}{1 − pT} = ∏_{k=1}^{∞}(1 − T^{k})^{−N_{k}}.

Taking the logarithm on both sides and applying the identity − log(1 − x) = ∑_{i=1}^{∞} \frac{x^{i}}{i},

we get

∑_{i=1}^{∞} \frac{p^{i}T^{i}}{i} = ∑_{i=1}^{∞} T^{i}(∑_{jk=i} \frac{N_{k}}{j}).

Comparing the coefficient of T^{i} in the equation, we get

p^{i} = ∑_{k|i} kN_{k}.

Applying the Möbius inversion formula, Lemma 1 follows.

Given a monic polynomial F (x) ∈ ℤ[x], if the factorization of F (x)(mod p) has r_{1} linear factors, r_{2} quadratic factors, r_{3} cubic factors and etc, we say F (x) has mod p type r = (r_{1}, r_{2}, r_{3}, ⋯). For a permutation σ ∈ S_{n}, if σ has r_{1} cycles of length 1, r_{2} cycles of length 2 and etc, we say σ has cycle type r = (r_{1}, r_{2}, ⋯). The above two types are closely related : for a fixed type r, if there exists a prime p such that F (x)(mod p) is of type r, then there exists a permutation σ ∈ Gal(F) ⊆ S_{n} whose cycle type is r. The converse is also true and this is essentially a consequence of the Chebotarev density theorem. (See [?] and [?]) Notice that : if Gal(F) ⫋ S_{n}, there exist a conjugacy class C of S_{n} such that Gal(F) ∩ C = ∅. Also, each cycle type represent a conjugacy classes of S_{n}. Combine the above facts : if F is an element of E_{n}(N), there exists a cycle type r which is never represented by its Galois group. Hence, to obtain an upper bound for E_{n}(N), it suffices to get an upper bound for

E_{r,n}(N) = #{F (x) ∈ E_{n}(N) : F does not have mod p type r for all primes p}.

Then, summing E_{r,n}(N) over all possible types r will give us an upper bound for E_{n}(N). In fact, there is a uniform upper bound for E_{r,n} for all types r. Since the number of types r is bounded, to prove Theorem 2, it suffices to prove the following theorem which is also interesting in its own right.

Theorem 4

E_{r,n}(N) ≪ N^{n−1/3}(log N)^{2}.

Before proving Thorem 4, we need the following lemmas.

Lemma 2 Fix a type r = (r_{1}, r_{2}, ⋯), ∑_{k} r_{k}k = n. There are (δ(r)p^{n} + O(p^{n−1}))

many monic polynomials in 𝔽_{p}[x] with degree n and of type r, here δ(r) = ∏_{k} \frac{1}{r_{k}!k^{r_{k}}}.

We denote the number of such polynomials by ω(p).

Proof: From Lemma 1,

N_{k} = \frac{1}{k} ∑_{d|k} μ(d)p^{\frac{k}{d}} ∼ \frac{p^{k}}{k} .

Hence,

#{monic polynomials in 𝔽_{p}[x] with degree n and of type r}

= ∏_{k} \binom{N_{k} + r_{k} − 1}{r_{k}}

= ∏_{k} \frac{1}{r_{k}!}(\frac{p^{k}}{k})^{r_{k}} + O(p^{n−1})

= δ(r)p^{n} + O(p^{n−1}).

Lemma 3 Fix a type r = (r_{1}, r_{2}, ⋯). There are

((2N + 1)^{n} \frac{ω(p)}{p^{n}} + O(\frac{N^{n−1}}{p^{n−1}} ω(p)))

many monic polynomials in ℤ[x] with height ≤ N whose mod p type is r.

Proof: Apply Lemma 2 and the following observation : fix a monic polynomial f(x) in 𝔽_{p}[x]. The number of monic polynomials F (x) ∈ ℤ[x] with H(F) ≤ N and F (x) ≡ f(x) (mod p) is

(\frac{2N + 1}{p} + O(1))^{n} = \frac{(2N + 1)^{n}}{p^{n}} + O ((\frac{N}{p})^{n−1}) .

Proof of Theorem 4 : The proof is an application of the Turán sieve. Let S = {s = (a_{1}, a_{2}, ⋯, a_{n}) ∈ ℤ^{n}, |a_{i}| ≤ N}. For each s ∈ S, we define F (s) = x^{n} + a_{1}x^{n−1} + ⋯ + a_{n}. Let I = {p : primes and p ≤ z}. For each p ∈ I, we define Ω(p) to be the condition that F (s) (mod p) is of type r, hence,

S_{p} = {s ∈ S : F (s) (mod p) is of type r}

and

π_{s}(I) = #{p ∈ I : F (s) (mod p) is of type r}.

From Lemma 3, we have

|S_{p}| = (2N + 1)^{n} \frac{ω(p)}{p^{n}} + O(\frac{N^{n−1}}{p^{n−1}} ω(p)).

Hence,

\frac{|S_{p}|}{|S|} = \frac{ω(p)}{p^{n}} + O(\frac{ω(p)}{p^{n−1}N}).

We set δ_{p} = \frac{ω(p)}{p^{n}} and r_{p} = O(\frac{ω(p)}{p^{n−1}N}). For different primes p, q, in I, S_{p} and S_{q} are quasi-independent. We have

\frac{|S_{p} ∩ S_{q}|}{|S|} = \frac{ω(p)ω(q)}{p^{n}q^{n}} + O(\frac{ω(p)ω(q)}{p^{n−1}q^{n−1}N}).

By Lemma 2,

ν = ∑_{p≤z} \frac{ω(p)}{p^{n}} ∼ δ(r)\frac{z}{log z} .

Apply Corollary 1,

E_{r,n}(N) ≤ #{s ∈ S, π_{s}(I) = 0}

≪ \frac{N^{n} log z}{z} + \frac{N^{n}(log z)^{2}}{z^{2}} ∑_{p,q∈I} \frac{pq}{N} + \frac{N^{n} log z}{z} ∑_{p∈I} \frac{p}{N} (note: ω(p) ≤ p^{n})

≪ \frac{N^{n}(log z)^{2}}{z} (1 + \frac{z^{3}}{N}).

Choosing z = N^{1/3}, we get

E_{r,n}(N) ≪ N^{n−1/3}(log N)^{2}.

4 Probabilistic Galois Theory in the function field over 𝔽_{q}.

4.1 Reducible polynomials in 𝔽_{q}[t, x].

Before we start the function field version of the probabilistic Galois theory problem, we estimate first the number of reducible polynomials in 𝔽_{q}[t, x]. More precisely, we find an upper bound for

R_{n}(N) = #{F (x) = x^{n} + a_{1}(t)x^{n−1} + a_{2}(t)x^{n−2} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x],

H(F) ≤ N and F is reducible}.

Fix a monic irreducible polynomial v(t) ∈ 𝔽_{p}[t] with degree n_{v}. We define F_{v} to be 𝔽_{q}[t]/(v(t)), a finite field with q^{n_{v}} elements. Let F_{v}[x] be the ring of polynomials in x with coefficients in F_{v}. It is a Euclidean domain, and hence is a unique factorization domain. Give F (x) = x^{n} + a_{1}(t)x^{n−1} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x]. We denote F (x)(mod v(t)) = x^{n}+u_{1}(t)x^{n−1}+⋯+u_{n}(t), where a_{i}(t) ≡ u_{i}(t)(mod v(t)) and deg(u_{i}(t)) < deg(v(t)). Since F_{v}[x] is a unique factorization domain, we can factor F (x)(mod v(t)) as a product of monic irreducible polynomials.

Lemma 4 Let N_{k} be the number of monic irreducible polynomials in F_{v}[x] with degree k. Then

N_{k} = \frac{1}{k} ∑_{d|k} μ(d)(q^{n_{v}})^{\frac{k}{d}} .

Proof: The proof is an analogus of Lemma 1, except replacing p by q^{n_{v}}.

Theorem 5

R_{n}(N) ≪ (q^{N+1})^{(n−1)}N.

Proof: The proof is an application of the Turán sieve. Let S = {s = (a_{1}(t), a_{2}(t), ⋯, a_{n}(t)) ∈ (𝔽_{q}[t])^{n}, deg(a_{i}(t)) ≤ N}. For each s ∈ S, we define F (s) = x^{n} + a_{1}(t)x^{n−1} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x]. Let I = {v(t) ∈ 𝔽_{q}[t] : v(t) is monic, irreducible and deg(v) = n_{v} ≤ z}. For each v(t) ∈ I, we define Ω(v) to be the condition that F (s) (mod v(t)) is irreducible, hence,

S_{v} = {s ∈ S : F (s) (mod v(t)) is irreducible}.

and

π_{s}(I) = #{v(t) ∈ I : F (s) (mod v(t)) is irreducible}.

Let ω(v) denote the number of monic irreducible polynomials of degree n in F_{v}[x]. We observe that for a fixed monic polynomial f(x) in F_{v}[x], there are q^{(N−n_{v}+1)n} many s ∈ S such that F (s) ≡ f(x) (mod v(t)). Hence, we have

|S_{v}| = q^{(N−n_{v}+1)n}ω(v)

and

\frac{|S_{v}|}{|S|} = \frac{ω(v)}{q^{n_{v}n}}.

We set δ_{v} = \frac{ω(v)}{q^{nvn}} and r_{v} is 0. Moreover, for different v(t), w(t) ∈ I, S_{v} and S_{w} are quasi-independent with r_{v,w} = 0. By lemma 4, ω(v) ∼ \frac{1}{n}. Hence, we have

ν = ∑_{v∈I} \frac{1}{n} ∼ \frac{1}{n} \frac{q^{z}}{z} .

Applying Corollary 1, we get

\begin{aligned}R_{n}(N) & ≤ #\{s ∈ S, π_{s}(P) = 0\} \\ & ≪ \frac{q^{(N+1)n}z}{q^{z}} . \end{aligned}

Choosing z = N, the theorem follows.

4.2 Probabilistic Galois theory in 𝔽_{q}[t, x].

We want to get an upper bound for

\begin{aligned}P_{n}(N) & = #\{F (x) = x^{n} + a_{1}(t)x^{n−1} + a_{2}(t)x^{n−2} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x], \\ & H(F) ≤ N and Gal(F) ⫋ S_{n}.\} \end{aligned}

Remark We notice the fact that not all polynomials in 𝔽_{q}[t, x] are separable. However, in our case, the number of such polynomials is negligible : give F (x) ∈ 𝔽_{q}[t, x] of degree n. By Theorem 5, without loss of generality, we can assume that F (x) is irreducible. Moreover, for an irreducible polynomial F (x) ∈ 𝔽_{q}[t, x], F (x) is inseparable if and only if F (x) = G(x^{p}) for some polynomial G. Hence, if p ∤ n, F (x) is always separable. Otherwise, the number of inseparable polynomials is at most (q^{N+1})^{\frac{n}{p}}, which is negligible in our cases. Hence, without loss of generality, we can assume that all F (x) in the correspondence set of P_{n}(N) are separable, hence Gal(F) always exist.

For a monic irreducible polynomial v(t) ∈ 𝔽_{q}[t], we define mod v(t) type in the obvious way. As before, to obtain an upper bound for P_{n}(N), it suffices to get an upper bound for

P_{r,n}(N) = #{F (x) ∈ P_{n}(N) : F does not have mod v(t) type r

for all monic irreducible polynomials v(t)}.

We prove Theorem 6

P_{r,n}(N) ≪ (q^{(N+1)})^{n−1}N.

The analogus of Lemma 2 and Lemma 3 in the function field are the followings:

Lemma 5 Fix a type r = (r_{1}, r_{2}, ⋯), ∑_{k} r_{k}k = n. There are (δ(r)(q^{n_{v}})^{n} +

O((q^{n_{v}})^{n−1}) many monic polynomials in F_{v}[x] with degree n and of type r, here

δ(r) = ∏_{k} \frac{1}{r_{k}!k^{r_{k}}}. We denote the number of such polynomials by ω(v).

Lemma 6 Fix a type r = (r_{1}, r_{2}, ⋯). There are (q^{N−n_{v}+1})^{n}ω(v) many monic polynomials in 𝔽_{q}[t, x] with height ≤ N whose mod v(t) type is r.

Proof of Theorem 6: The proof is again an application of the Turán sieve. Let S = {s = (a_{1}(t), a_{2}(t), ⋯, a_{n}(t)) ∈ (𝔽_{q}[t])^{n}, deg(a_{i}(t)) ≤ N}. For each s ∈ S, we define F (s) = x^{n} + a_{1}(t)x^{n−1} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x]. Let I = {v(t) ∈ 𝔽_{q}[t] : v(t) is monic, irreducible and deg(v) = n_{v} ≤ z}. For each v(t) ∈ I, we define Ω(v) to be the condition that F (s) (mod v(t)) is of type r. By Lemma 6,

\frac{|S_{v}|}{|S|} = \frac{ω(v)}{q^{n_{v}n}}.

The rest of the proof is just the same as the proof of Theorem 5.

5 Concluding Remarks.

Given F (x) = x^{n} + a_{1}x^{n−1} + ⋯ + a_{n} ∈ ℤ[x] with H(F) ≤ N, if we assume a_{n} = 0, Gal(F) is a proper subgroup pf S_{n}. Since the order of such elements is N^{n−1}, we have

E_{n}(N) ≫ N^{n−1}.

By the same argument, we can show that

P_{n}(N) ≫ (q^{N+1})^{n−1}.

In 1936, van der Waerden [?] conjectured that

E_{n}(N) ≪ N^{n−1}.

By developing the large sieve in function fields over finite fields, it is possible to prove the following :

Theorem 7 The number of the set

{F (x) = x^{n} + a_{1}(t)x^{n−1} + ⋯ + a_{n}(t) ∈ 𝔽_{q}[t, x], deg(a_{i}(t)) ≤ N and Gal(F) ⫋ S_{n}}

is ≪ (q^{N+1})^{n−1}.

Th details are involved and we relegate this to a further paper.

References

[1] G. Frobenius, Über Beziehungen zwischen den Primidealen eines algebraischen Körpers und den Substitutionen seiner Gruppe, S. B. Akad. Wiss. Wien 134, 1925, 69-80.

[2] C. Hooley, Application of sieve methods to the theory of numbers, Cambridge Unibersity press, 1976.

[3] P.X. Gallagher, The large sieve and probabilistic Galois theory, Analytic Number Theory (Proc. Sympos. Pure Math., Val 24), Amer. Math. Soc., 1973.

[4] N. Jacobson, Basic algebra I, Freeman, 1996, 302-304.

[5] B.L. van der Waerden, Die Seltenheit der reduziblen Gleichungen und der Gleichungen mit Affekt, Monatsh. Math 43, 1936.