Arithmetical Aspects of the Large Sieve Inequality

Frontmatter

Introduction

Abstract

The idea of the large sieve appeared for the first time in the foundational paper of (Linnik, 1941). Later (Rényi, 1950), (Barban, 1964), (Roth, 1965), (Bombieri, 1965), (Davenport & Halberstam, 1966b) developed it and in particular, two distinct parts emerged from these works:

(1)

An analytic inequality for the values over a well-spaced set of points of a trigonometric polynomial S(α) = ∑_1≤N u _n e(nα), which, in arithmetical situations, most often reduces to

$$\sum\limits_{q \leqslant Q} {\sum\limits_{\alpha \,\bmod *q} {{{\left| {S\left( {a/q} \right)} \right|}^2} \leqslant \Delta \sum\limits_n {{{\left| {{u_n}} \right|}^2}} } }$$

(0.1)

for some ∆ depending on the length N of the trigonometric polynomial and on Q. The best value in a general context is ∆ = N ‒ 1 + Q² obtained independently in (Selberg, 1972) and in (Montgomery & Vaughan, 1973).

 

(2)

An arithmetical interpretation for ∑ _{a mod*q}|S(a/q)|², where this time, information on the distribution of (u _n ) modulo q is introduced. The most popular approach goes through a lower bound and is due to Montgomery, leading to what is sometimes referred to as Montgomery’s sieve, by reference to (Montgomery, 1968).

 

Today the terminology large sieve refers to a combination of the two aforementioned steps. We refer the reader to the excellent lecture notes (Montgomery, 1971) and the survey paper (Montgomery, 1978) for the early part of the development, but cite here the papers of (Bombieri & Davenport, 1968) and (Bombieri, 1971).

Olivier Ramaré

1. The large sieve inequality

Abstract

We begin with an abstract hermitian setting which we will use to prove the large sieve inequality. We develop more material than is required for such a task. This is simply to prepare the ground for future uses, and we shall even expand on this setting in chapter 7; the final stroke will only appear in section 10.1.

Olivier Ramaré

2. An extension of the classical arithmetical theory of the large sieve

Abstract

Part of the material given here has already appeared in (Ramaré & Ruzsa, 2001). Theorem 2.1 is the main landmark of this chapter. From there onwards, what we do should become clearer to the reader. In particular, we shall detail an application of Theorem 2.1 to the Brun-Titchmarsh Theorem.

Olivier Ramaré

3. Some general remarks on arithmetical functions

Abstract

We present here some general material pertaining to the family of functions we consider in our sieve setting (see chapter 2, in particular section 2.2).

Olivier Ramaré

4. A geometrical interpretation

Abstract

The expression appearing in Theorem 2.1 may look unpalatable, but is in fact simply the norm of a suitable orthonormal projection, as we show here. The reader may skip this chapter. While it does different insights on what we are doing, it will not be invoked before chapter 19, with two short detours at sections 9.4 and 11.4.

Olivier Ramaré

5. Further arithmetical applications

Abstract

In this section, we use the large sieve extension of the Brun-Titchmarsh inequality provided by Theorem 2.1 to detect products of two primes is arithmetic progressions. Let us consider the case of primes in [2, N], of which the prime number theorem tells us there are about N/ Log N. Next select a modulus q. The Brun-Titchmarsh Theorem 2.2 implies that at least

$$\frac{{\phi \left( q \right)}} {2}\left( {1 - \frac{{Log\,q}} {{\log \,N}}} \right)$$

(5.1)

congruence classes modulo q contains a prime ≤ N, so roughly speaking slightly less than ϕ(q)/2 when q is N ^ε . If this cardinality is > ϕ(q)/3, one could try to use Kneser’s Theorem and derive that all invertible residue classes modulo q contain a product of three primes, but the proof gets stuck: all the primes we detect — to show the cardinality is more than ϕ(q)/3 — could belong to a quadratic subgroup of index 2 … However the following theorem shows that if this is indeed the case for a given modulus q then the number of classes covered modulo some q′ prime to q is much larger: Theorem 5.1. Let N ≥ 2. Set P to be the set of primes in \(\left] {\sqrt N ,N} \right]\), of cardinality P, and let (q _i ) _i∈ I be a finite set of pairwise coprime moduli, not all more than \(\sqrt N /Log\,N\). Define

$$A\left( {{q_i}} \right) = \left\{ {a \in \mathbb{Z}/{q_i}\mathbb{Z}/\exists p \in p,p \equiv a\left[ {{q_i}} \right]} \right\}$$

.

Olivier Ramaré

6. The Siegel zero effect

Abstract

When dealing with the Brun-Titchmarsh Theorem (Theorem 2.2 of this monograph), and in general, with sieve methods, the question of the connections between the parity principle, the constant 2 in this theorem and the so-called Siegel zeros cannot be avoided. (Selberg, 1949) shows that the constant 2 + o(1) in the Brun-Titchmarsh Theorem is optimal, if we stick to a sieve method in a fairly general context. He expanded this theory into what is known as the “parity principle” in (Selberg, 1972). See also (Bombieri, 1976). However, this objection is methological and belongs much more to the realm of the combinatorial sieve. In the restricted framework of the Brun-Tichmarsh Theorem, or in the even more restricted framework of this Theorem for the initial interval only, the constant 2 and “the parity principle” are indeed two different issues. This chapter is first devoted to links and parallels between Siegel zeros and the constant 2 in the aforementioned Theorem.

Olivier Ramaré

7. A weighted hermitian inequality

Abstract

We continue to develop the theory in the general context of chapter 1 with a view to an application in the chapter that follows.

Olivier Ramaré

8. A first use of local models

Abstract

We now turn towards another way of using the large sieve inequality in an arithmetical way, here on prime numbers. This application comes from (Ramaré & Schlage-Puchta, 2008). A exposition in the French addressing a large audience can be found in (Ramare, 2005).

Olivier Ramaré

9. Twin primes and local models

Abstract

We saw in the previous section, and in an extremely simple example, how local models enter into the game of sieving. Further, we took the opportunity of exploring somewhat more intricate weights. While doing this, we missed one crucial fact: the good almost orthogonality bounds for our local models in the previous chapter come from the simple structure of the set we are sieving, as will be more evident in Lemma 19.4. Technically speaking, the expression for c _q in terms of additive characters has ϕ(q) summands, while the one in terms of divisors (8.12) has only 2^ω(q) summands. We now give further details in the case of prime twins, where this feature will clearly show up. A general treatment is given in section 11.6.

Olivier Ramaré

10. The three primes theorem

Abstract

We prove here the celebrated theorem of (Vinogradov, 1937):

Olivier Ramaré

11. The Selberg sieve

Abstract

In this chapter, we first present the Selberg sieve in a fashion similar to what we did up to now. In passing, we shall extend the Selberg sieve to the case of non-squarefree sifting sets, as was already done in (Selberg, 1976), but our setting will also carry through to sieving sequences and not only sets. Furthermore, this setting will enable us to compare the three different approaches: via the large sieve inequality, via local models or via the Selberg sieve.

Olivier Ramaré

12. Fourier expansion of sieve weights

Abstract

The previous chapter contains an expansion of \({\Sigma _d}{\lambda _d}{1_\mathcal{L}}_{_d}\left( n \right) \) as a linear combination of additive characters, simply by combining (11.30) and (11.33). The theme of the present chapter is to expand similarly the sieve weights

$${\beta _\kappa }\left( n \right) = {\left( {\sum\limits_d {{\lambda _d}{1_{{\mathcal{L}_d}}}\left( n \right)} } \right)^2}.$$

(12.1)

This is indeed what is done in the case of primes in (Ramaré, 1995) and what is rapidly presented in a general context in (Ramaré & Ruzsa, 2001), equation (4.1.21). Such a material is used in (Green & Tao, 2006).

Olivier Ramaré

13. The Selberg sieve for sequences

Abstract

The setting we developed for the Selberg sieve enables us to sieve sequences even if the compact set K is not squarefree, though it will still have to be multiplicatively split. The adaptation is easy enough but we record the necessary formulae and detail some examples.

Olivier Ramaré

14. An overview

Abstract

It is time for us to take some height and look at what we have been doing from farther away. The first approach, through the large sieve inequality, relied on an arithmetical rewriting of

$$\sum\limits_q {\sum\limits_{a\,\bmod *q} {{{\left| {S\left( {a/q} \right)} \right|}^2}\quad \left( {S\left( \alpha \right) = \sum\limits_n {{u_n}e\left( {n\alpha } \right)} } \right)} }$$

. This rewriting did in fact handle the sum W(q) = ∑_{a mod*q} |S(a/q)|² as one single term, and we tried to maximize it in the subsequent analysis. More precisely, whenever (u _n ) vanishes outside of a given compact set, we prove a useful lower bound for this quantity.

Olivier Ramaré

15. Some weighted sequences

Abstract

Upto now, we did not investigate precisely what happens at the place at infinity. We introduced some Fourier transforms in chapter 10, and we already saw some expressions frequent in this area of mathematics in section 1.2.1. We expand all these considerations in this chapter, and, inter alia, shall provide a proof of Theorem 1.1.

Olivier Ramaré

16. Small gaps between primes

Abstract

In this chapter, we show how the perfectly well distributed weighted sequence (b _v (n)) _n built in the preceding chapter can be used to simplify the analysis of the hermitian product stemming from a local system. We show furthermore that the key point of Bombieri & Davenport’s proof concerning small differences between primes is in fact contained in Lemma 1.2 and 1.1.

Olivier Ramaré

17. Approximating by a local model

Abstract

It is high time we show in a somewhat general setting how to approximate a given weighted sequence by a local model. Let us start with such a sequence (f(n)) _n together with an additional function ψ∞ (which will take care of the size constraints), for which we assume the following bound:

$$\sum\limits_{q \leqslant D} {\mathop {m{\text{ax}}}\limits_{a\,\bmod q} \left| {\sum\limits_{n \equiv a\left[ q \right]} {f\left( n \right){\psi _\infty }\left( n \right) - {f_q}\left( a \right)X/q} } \right| \leqslant E}$$

(17.1)

for some parameters D, E, X and (f _q ) _q . The Bombieri-Vinogradov Theorem falls within this framework with ψ∞ being the characteristic function of real numbers ≤ N and E = N/(Log N) ^A , together with D = √N/(Log N) ^B for some B = B(A); then f(n) = Λ(n) and f _q = q𝟙u _q /ϕ(q), and finally X = N. Note that the function f _q that appears is precisely the one we used as a local model for the primes. The parameter X is here for homogeneity and could be dispensed with, simply by incorporating it in f _q . However, in usual applications, X will be here to treat the dependence on the size, i.e. the contribution of the infinite place, while f _q will be independent of it and only accounts for the effect of the finite places. We shall need some properties of these f _q ’s, namely:

$$\left. {\forall d} \right|q,\forall a\bmod d,\quad J_{\tilde d}^{\tilde q}{f_q} = {f_d}.$$

(17.2)

This equation may look unpalatable, but here is an equivalent formulation:

$$\forall d\left| {q,\quad {f_d}\left( a \right)/d = \sum\limits_{\mathop {b\;\bmod q}\limits_{b \equiv a\left[ q \right]} } {{f_q}\left( b \right)/q} } \right.$$

(17.3)

where it is maybe easier to consider f _q /q as one function (the density, as in (13.1) and (13.2)).

Olivier Ramaré

18. Selecting other sets of moduli

Abstract

Concerning the moduli, we used mainly the simple condition d ≤ z, while everything we do is valid with a condition d ∈ D for some divisor closed set¹. Usual sets are {d ≤ z}, or the set of integers ≤ z and with prime factors belonging to some sets (like prime to 2 or bounded by some y), or with a bounded number of prime factors.

Olivier Ramaré

19. Sums of two squarefree numbers

Abstract

To illustrate further how we may handle additive problems with the material we have presented, we prove the following Theorem. Note that we freely use chapter 4 in the sequel.

Olivier Ramaré

20. On a large sieve equality

Abstract

This last chapter presents directions to investigate, some limitations, and other slightly off topic material. We use also this pretext to provide a simple introduction to some modern techniques. Let us finally point out that (Ramaré, 2007a) contains also material on this subject, but very different in nature. We omit it here.

Olivier Ramaré

21. Appendix

Abstract

Here is a theorem inspired by (Halberstam & Richert, 1971) but where we take care of the values of our multiplicative function on powers of primes as well. The reader will find in (Martin, 2002) an appendix with a similar result. Moreover, we present a completely explicit estimate, which complicates the proof somewhat. In (Cazaran & Moree, 1999), the reader will find, inter alia, a presentation of many results in the area, a somewhat different exposition as well as a modified proof: the authors achieve there a better treatment of the error term by appealing to a preliminary sieving.

Olivier Ramaré

Backmatter