Crivo de Selberg
# Crivo de Selberg

Em Matemática, na área de teoria dos números, o crivo de Selberg é uma técnica para estimar o tamanho de conjuntos crivados (ou "peneirados", pois crivo significa peneira) de inteiros positivos que satisfazem um conjunto de condições que são expressadas por congruência. Foi desenvolvida por Atle Selberg na década de 1940.

## Descrição

Em termos de teoria dos crivos o crivo de Selberg é do tipo combinatório: isto é, provém do uso cauteloso do princípio da inclusão-exclusão. Selberg substitui os valores da função de Möbius que surgem por um sistema de pesos que são então otimizados segundo o problema dado. O resultado retorna um limite superior para o tamanho do conjunto crivado.
Seja A um conjunto de inteiros positivos ≤ x e seja P um conjunto de primos. Para cada p in P, seja A$_p$ o conjunto de elementos de A divisíveis por p e estender isso para fazer A$_d$ a intersecção de A$_p$ para p dividindo d, onde d é um produto de primos distintos de P. Ainda seja A$_1$ a notação para o próprio A. Seja z um número real positivo e P(z) a notação para o produto dos primos em P ≤ z. A finalidade deste crivo é estimar
    $S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .$
Assumimos então que |A$_d$| pode ser estimado por
    $\left\vert A_{d}\right\vert ={\frac {1}{f(d)}}X+R_{d}.$
onde f é uma função multiplicativa e X = |A|. Seja a função g obtida a partir de f pela fórmula de inversão de Möbius, isto é
    $g(n)=\sum _{d\mid n}\mu (d)f(n/d)$
    $f(n)=\sum _{d\mid n}g(d)$
onde μ é a função de Möbius. Put
    $V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {\mu ^{2}(d)}{g(d)}}.$
então
    $S(A,P,z)\leq {\frac {X}{V(z)}}+O\left({\sum _{\begin{smallmatrix}d_{1},d_{2}<z\\d_{1},d_{2}\mid P(z)\end{smallmatrix}}\left\vert R_{[d_{1},d_{2}]}\right\vert }\right).$
Muitas vezes, é útil para estimar V(z) pelo limite
    $V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,$

## Aplicações

* No Teorema de Brun–Titchmarsh no número de primos em progressão aritmética;
* O número de n ≤ x de tal forma que n é co-primo com φ(n) é assintótico para e$^{−γ}$ x / log log log (x) .