# Teorema de Erdős–Fuchs

Em matemática, na área de teoria aditiva dos números, o Teorema de Erdős–Fuchs é um teorema sobre o número de formas que um número pode ser representado como a soma de dois elementos de um determinado conjunto, afirmando que a ordem média desse número não pode ser muito próximo de uma função linear.
O nome deste teorema vem de Paul Erdős e Wolfgang Heinrich Johannes Fuchs, que publicaram sua prova em 1956.

## Enunciado

Seja ${\mathcal {A}}\subseteq \mathbb {N}$ um conjunto infinito de números naturais, e escreva $r_{{\mathcal {A}},h}(n)$ para sua função de representação, que denota o número de formas de escrever num número natural $n$ como a soma de $h$ elementos de ${\mathcal {A}}$ (levando ordem em consideração). Consideramos então a função de representação acumulada $s_{{\mathcal {A}},h}(x):=\sum _{n\leqslant x}r_{{\mathcal {A}},h}(n),$ que conta (também levando ordem em consideração) o número de soluções para $k_{1}+\cdots +k_{h}\leqslant x$, onde $k_{1},\ldots ,k_{h}\in {\mathcal {A}}$. O teorema então diz que, para qualquer $c>0$, a relação $s_{{\mathcal {A}},2}(n)=cn+o\left(n^{1/4}\log(n)^{-1/2}\right)$ não pode ser satisfeita; isto é, nenhum ${\mathcal {A}}\subseteq \mathbb {N}$ satisfaz a estimativa acima.

## Teoremas do tipo de Erdős–Fuchs

O teorema de Erdős–Fuchs possui uma história interessante de precedentes e generalizações. Em 1915, G. H. Hardy já sabia que no caso da sequência ${\mathcal {Q}}:=\{0,1,4,9,\ldots \}$ dos quadrados perfeitos tem-se $\limsup _{n\to +\infty }{\frac {\left|s_{{\mathcal {Q}},2}(n)-\pi n\right|}{n^{1/4}\log(n)^{1/4}}}>0$ Esta estimativa é um pouco melhor do que a descrita por Erdős–Fuchs, contudo, pelo preço de uma pequena perda de precisão, P. Erdős e W. H. J. Fuchs atingiram completa generalidade em seu resultado (pelo menos para o caso $h=2$). Outra razão pela qual este resultado é tão célebre pode ser devido ao fato de que, em 1941, P. Erdős e P. Turán conjecturaram que, sujeito às mesmas hipóteses que as do teorema enunciado, a relação $s_{{\mathcal {A}},2}(n)=cn+O(1)$ não poderia ser válida. Este fato manteve-se sem demonstração até 1956, quando Erdős e Fuchs obtiveram seu teorema, que é ainda mais forte que as estimativas previamente conjecturadas.

### Versões melhoradas para h = 2

Este teorema foi estendido em diversas direções diferentes. Em 1980, A. Sárközy considerou duas sequências que estão "perto" em algum sentido. Ele provou o seguinte:
* Teorema (Sárközy, 1980). Se ${\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}$ e ${\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}$ são dois subconjuntos infinitos dos números naturais com $a_{i}-b_{i}=o{\biga_{i}^{1/2}\log(a_{i})^{-1}{\big )}$, então $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\bign^{1/4}\log(n)^{-1/2}{\big )}$ nunca é válido, para nenhuma constante $c>0$.
Em 1990, H. L. Montgomery e R. C. Vaughan conseguiram remover o termo com log do lado direito do enunciado original de Erdős–Fuchs, mostrando que $s_{{\mathcal {A}},2}(n)=cn+o(n^{1/4})$ nunca é válido. Em 2004, G. Horváth estendeu ambos estes resultados, provando o seguinte:
* Teorema (Horváth, 2004). Se ${\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}$ e ${\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}$ são subconjuntos infinitos dos números naturais com $a_{i}-b_{i}=o{\biga_{i}^{1/2}{\big )}$ e $|{\mathcal {A}}\cap [0,n]|-|{\mathcal {B}}\cap [0,n]|=O(1)$, então $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\bign^{1/4}{\big )}$ nunca é válido, para nenhuma constante $c>0$.

### Caso geral (h ≥ 2)

A generalização natural do Teorema de Erdős–Fuchs, para $h\geqslant 3$, é sabida ser válida, e também com a mesma força da versão de Montgomery–Vaughan. Com efeito, M. Tang mostrou em 2009 que, nas condições do teorema original de Erdős–Fuchs, para todo $h\geqslant 2$ a relação $s_{{\mathcal {A}},h}(n)=cn+o(n^{1/4})$ nunca é válida. Em outra direção, em 2002, G. Horváth deu uma generalização precisa para o resultado de 1980 de Sárközy, mostrando que
* Teorema (Horváth, 2002) Se ${\mathcal {A}}^{(j)}=\{a_{1}^{(j)}<a_{2}^{(j)}<\ldots \}$ ($j=1,\ldots ,k$) são $k$(pelo menos dois) subconjuntos infinitos dos números naturais satisfazendo as seguintes estimativas:
* $a_{i}^{(1)}-a_{i}^{(2)}=o{\big(a_{i}^{(1)})^{1/2}\log(a_{i}^{(1)})^{-k/2}{\big )}$
* $|{\mathcal {A}}^{(j)}\cap [0,n]|=\Theta {\big|{\mathcal {A}}^{(1)}\cap [0,n]|{\big )}$ (for $j=3,\ldots ,k$)
    então a relação:
    $|\{(i_{1},\ldots ,i_{k}):a_{i_{1}}^{(1)}+\ldots +a_{i_{k}}^{(k)}\leqslant n,~a_{i_{j}}^{(j)}\in {\mathcal {A}}^{(j)}(j=1,\ldots ,k)\}|=cn+o{\bign^{1/4}\log(n)^{1-3k/4}{\big )}$
    nunca é válida, para nenhuma constante $c>0$.

### Aproximações não-lineares

Ainda outra direção na qual o teorema de Erdős–Fuchs pode ser melhorado é considerando aproximações para $s_{{\mathcal {A}},h}(n)$ diferentes de $cn$ para algum $c>0$. Em 1963, P. T. Bateman, E. E. Kohlbecker and J. P. Tull mostraram uma versão um pouco mais forte do seguinte:
* Teorema (Bateman–Kohlbecker–Tull, 1963). Seja $L(x)$ uma função de variação lenta que é ou convexa ou côncava de certo ponto em diante. Então, nas condições do teorema original de Erdős–Fuchs, a estimativa $s_{{\mathcal {A}},2}(n)=nL(n)+o{\bign^{1/4}\log(n)^{-1/2}L(n)^{\alpha }{\big )}$ nunca é válida, onde $\alpha =3/4$ se $L(x)$ é limitada, e $1/4$ caso contrário.
No final do artigo em questão, é observado que é possível estender o método usado para provar o teorema acima no sentido de obter resultados considerando $n^{\gamma }$ com $\gamma \neq 1$, mas tais resultados são considerados pouco definitivos.