Large sieve

The large sieve bounds how much an exponential sum can concentrate at separated points of the circle group. Its variance form of the large sieve also bounds simultaneous concentration in residue classes modulo many primes.

Table of contents

Character large sieve

For coefficients supported on

N

consecutive integers,

\sum_{q \leq Q} \frac{q}{ϕ ( q )} \sum_{χ mod q}^{*} ∣ \sum_{n} a_{n} χ (n) ∣^{2} \leq (Q^{2} + 2 π N) \sum_{n} ∣ a_{n} ∣^{2} .

The star restricts to primitive Dirichlet characters. Their finite Fourier transform of a primitive Dirichlet character has normalization of absolute value

q

. Orthogonality of Dirichlet characters therefore bounds the weighted contribution for one modulus by

\sum_{a mod q (a, q) = 1} ∣ \sum_{n} a_{n} e (an / q) ∣^{2}

. Sum over

q

and use the exponential-sum large sieve on the distinct reduced fractions of denominators at most

Q

.

Variance form of the large sieve

For coefficients

b_{n}

supported on an interval of

H

consecutive integers, set

B = \sum b_{n}

and

B_{p} (a) = \sum_{n \equiv a (mod p)} b_{n}

. Then

\sum_{p \leq Q} p \sum_{a mod p} ∣ B_{p} (a) - B / p ∣^{2} \leq (Q^{2} + 2 π H) \sum ∣ b_{n} ∣^{2} .

The orthogonality of roots of unity gives

p \sum_{a} ∣ B_{p} (a) - B / p ∣^{2} = \sum_{r = 1}^{p - 1} ∣ \sum_{n} b_{n} e (r n / p) ∣^{2}

. The distinct fractions

r / p

have circular spacing at least

Q^{- 2}

; now apply the exponential-sum large sieve.

Exponential-sum large sieve

If

θ_{r}

have circular spacing at least

δ

, then

\sum_{r} \sum_{M < n \leq M + N} a_{n} e (n θ_{r})^{2} \leq (δ^{- 1} + 2 π N) \sum_{M < n \leq M + N} ∣ a_{n} ∣^{2} .

Multiply the exponential sum by

e (- Mt)

, apply the Sobolev–Gallagher inequality on disjoint arcs of length

δ

, and sum. The finite-interval Parseval identities and Cauchy-Schwarz inequality bound the derivative contribution by

2 π N \sum ∣ a_{n} ∣^{2}

.

Local-multiplicity large sieve ( $K (Δ)$ )

Let

K (Δ) = max_{t} # {r : ∥ θ_{r} - t ∥ \leq Δ/2}

. Without a separation assumption,

\sum_{r} ∣ S (θ_{r}) ∣^{2} \leq K (Δ) (Δ^{- 1} + 2 π N) \sum ∣ a_{n} ∣^{2} .

For

0 < Δ \leq 1

, each point belongs to at most

K (Δ)

integration arcs in the Sobolev–Gallagher inequality. For

Δ \geq 1

,

K (Δ)

is the total number of points, and the Cauchy-Schwarz inequality bound

∣ S ∣^{2} \leq N \sum ∣ a_{n} ∣^{2}

suffices.

Prime-denominator large sieve

When

N \leq P

,

\sum_{P \leq p \leq 2 P p prime} \sum_{a = 1}^{p - 1} \sum_{M < n \leq M + N} a_{n} e (an / p)^{2} ≪ \frac{P ^{2}}{l o g P} \sum ∣ a_{n} ∣^{2} .

An arc of length

1/ P

contains at most three points of each grid of denominator

p \leq 2 P

. The Chebyshev estimate gives

O (P / lo g P)

such primes. Apply the local-multiplicity large sieve. Using only the separation of distinct reduced fractions gives the weaker

O (P^{2}) \sum ∣ a_{n} ∣^{2}

.

Circular spacing ( $∥ θ_{r} - θ_{s} ∥ \geq δ$ )

Points

θ_{r}

have circular spacing at least

δ

when

∥ θ_{r} - θ_{s} ∥ \geq δ

for distinct

r, s

, where

∥ t ∥ = min_{k \in Z} ∣ t - k ∣

. The distance is measured on the circle group

R / Z

, so points near zero and one can be close.

 Ancestors (6)

 Incoming links (3)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Wikipedia Bot  1

The "large sieve" is a powerful tool in analytic number theory used primarily in the study of the distribution of prime numbers and the behavior of arithmetical functions. It is a general method that provides inequalities for the sizes of sets of integers with certain properties, particularly focusing on the distribution of integer sequences modulo various bases.

 Read the full article

  See all articles in the same topic Create my own version