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{\big (}a_{i}^{1/2}\log(a_{i})^{-1}{\big )}$, então $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{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{\big (}a_{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{\big (}n^{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:

1. $a_{i}^{(1)}-a_{i}^{(2)}=o{\big (}(a_{i}^{(1)})^{1/2}\log(a_{i}^{(1)})^{-k/2}{\big )}$
2. $|{\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{\big (}n^{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{\big (}n^{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.

Ver também

• Teorema de Erdős–Tetali: Para todo $h\geq 2$, existe um conjunto ${\mathcal {A}}\subseteq \mathbb {N}$ satisfazendo $r_{{\mathcal {A}},h}(n)=\Theta (\log(n))$. (Existência de bases econômicas)
• Conjectura de Erdős–Turán para bases aditivas: Se ${\mathcal {A}}\subseteq \mathbb {N}$ é uma base aditiva de ordem 2, então $r_{{\mathcal {A}},2}(n)\neq O(1)$. (Bases não podem ser muito econômicas)

Referências

• Erdős, P.; Fuchs, W. H. J. (1956). «On a Problem of Additive Number Theory». J. London Math. Soc. 31 (1): 67–73. doi:10.1112/jlms/s1-31.1.67 
• Newman, D. J. (1998). Analytic number theory. Col: GTM. 177. New York: Springer. pp. 31–38. ISBN 0-387-98308-2 
• Halberstam, H.; Roth, K. F. (1983) [1966]. Sequences 2nd ed. Berlin, New York: Springer-Verlag. ISBN 978-0-387-90801-4. MR 0210679 

Hardy, G. H. (1915). «On the expression of a number as the sum of two squares». Quart. J. Math. 46: 263–83 

Erdős, P.; Turán, P. (1941). «On a problem of Sidon in additive number theory, and some related problems». J. London Math. Soc. 16: 212–5 

Sárközy, A. (1980). «On a theorem of Erdős and Fuchs». Acta Arith. 37: 333–338 

Montgomery, H. L.; Vaughan, R. C. (1990). «On the Erdős–Fuchs theorem». Cambridge Univ. Press. A tribute to Paul Erdős: 331–338 

Horváth, G. (2004). «An improvement of an extension of a theorem of Erdős and Fuchs». Acta Math. Hung. 104: 27–37 

Tang, Min (2009). «On a generalization of a theorem of Erdős and Fuchs». Discrete Math. 309: 6288–6293 

Horváth, G. (2002). «On a theorem of Erdős and Fuchs». Acta Arith. 103 (4): 321–328 

Bateman, P. T.; Kohlbecker, E. E.; Tull, J. P. (1963). «On a theorem of Erdős and Fuchs in additive number theory». Proc. Am. Math. Soc. 14: 278–84