---
tag: 5252P3NHT7
kind: concept
name: Selberg sieve
msc: [11N35, 11N36]
sources:
  - url: https://en.wikipedia.org/wiki/Selberg_sieve
same_as:
  wikidata: Q15777141
  wikipedia: Selberg sieve
---

## Summary

The Selberg sieve is an upper bound sieve of Atle Selberg.
It replaces the indicator of "no prime factor below $z$" by the square of a sum of real weights.
It then chooses the weights to minimise the main term, which is a quadratic form.
It gives sharp upper bounds with a simple remainder term, for example the Brun–Titchmarsh bound for primes in arithmetic progressions.
It is also called the $\Lambda^2$ sieve.

## Explanations

### L1 human

A sieve wants to count the numbers in a list that are not divisible by any small prime.
Selberg's trick is to use the fact that a square is never negative.
He builds, for each number, a square of a sum of weights that equals $1$ when the number survives and is $\ge 0$ otherwise.
Summing these squares gives an upper bound for the count, and he then picks the weights that make this bound as small as possible.
The method gives only upper bounds, but these are often close to the truth.