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 ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ um conjunto infinito de números naturais, e escreva ${\displaystyle 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 ${\displaystyle n}$ como a soma de ${\displaystyle h}$ elementos de ${\displaystyle {\mathcal {A}}}$ (levando ordem em consideração). Consideramos então a função de representação acumulada

que conta (também levando ordem em consideração) o número de soluções para ${\displaystyle k_{1}+\cdots +k_{h}\leqslant x}$, onde ${\displaystyle k_{1},\ldots ,k_{h}\in {\mathcal {A}}}$. O teorema então diz que, para qualquer ${\displaystyle c>0}$, a relação não pode ser satisfeita; isto é, nenhum ${\displaystyle {\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^[1] já sabia que no caso da sequência ${\displaystyle {\mathcal {Q}}:=\{0,1,4,9,\ldots \}}$ dos quadrados perfeitos tem-se

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 ${\displaystyle 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^[2] conjecturaram que, sujeito às mesmas hipóteses que as do teorema enunciado, a relação 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^[3] considerou duas sequências que estão "perto" em algum sentido. Ele provou o seguinte:

• Teorema (Sárközy, 1980). Se ${\displaystyle {\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}}$ e ${\displaystyle {\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}}$ são dois subconjuntos infinitos dos números naturais com ${\displaystyle a_{i}-b_{i}=o{\big (}a_{i}^{1/2}\log(a_{i})^{-1}{\big )}}$, então ${\displaystyle |\{(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 ${\displaystyle c>0}$.

Em 1990, H. L. Montgomery e R. C. Vaughan^[4] conseguiram remover o termo com log do lado direito do enunciado original de Erdős–Fuchs, mostrando que

nunca é válido. Em 2004, G. Horváth^[5] estendeu ambos estes resultados, provando o seguinte:

• Teorema (Horváth, 2004). Se ${\displaystyle {\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}}$ e ${\displaystyle {\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}}$ são subconjuntos infinitos dos números naturais com ${\displaystyle a_{i}-b_{i}=o{\big (}a_{i}^{1/2}{\big )}}$ e ${\displaystyle |{\mathcal {A}}\cap [0,n]|-|{\mathcal {B}}\cap [0,n]|=O(1)}$, então ${\displaystyle |\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}{\big )}}$ nunca é válido, para nenhuma constante ${\displaystyle c>0}$.

Caso geral (h ≥ 2)

A generalização natural do Teorema de Erdős–Fuchs, para ${\displaystyle 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^[6] mostrou em 2009 que, nas condições do teorema original de Erdős–Fuchs, para todo ${\displaystyle h\geqslant 2}$ a relação

nunca é válida. Em outra direção, em 2002, G. Horváth^[7] deu uma generalização precisa para o resultado de 1980 de Sárközy, mostrando que

• Teorema (Horváth, 2002) Se ${\displaystyle {\mathcal {A}}^{(j)}=\{a_{1}^{(j)}<a_{2}^{(j)}<\ldots \}}$ (${\displaystyle j=1,\ldots ,k}$) são ${\displaystyle k}$(pelo menos dois) subconjuntos infinitos dos números naturais satisfazendo as seguintes estimativas:

1. ${\displaystyle a_{i}^{(1)}-a_{i}^{(2)}=o{\big (}(a_{i}^{(1)})^{1/2}\log(a_{i}^{(1)})^{-k/2}{\big )}}$
2. ${\displaystyle |{\mathcal {A}}^{(j)}\cap [0,n]|=\Theta {\big (}|{\mathcal {A}}^{(1)}\cap [0,n]|{\big )}}$ (for ${\displaystyle j=3,\ldots ,k}$)

então a relação:

${\displaystyle |\{(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 ${\displaystyle 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 ${\displaystyle s_{{\mathcal {A}},h}(n)}$ diferentes de ${\displaystyle cn}$ para algum ${\displaystyle c>0}$. Em 1963, P. T. Bateman, E. E. Kohlbecker and J. P. Tull^[8] mostraram uma versão um pouco mais forte do seguinte:

• Teorema (Bateman–Kohlbecker–Tull, 1963). Seja ${\displaystyle 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 ${\displaystyle s_{{\mathcal {A}},2}(n)=nL(n)+o{\big (}n^{1/4}\log(n)^{-1/2}L(n)^{\alpha }{\big )}}$ nunca é válida, onde ${\displaystyle \alpha =3/4}$ se ${\displaystyle L(x)}$ é limitada, e ${\displaystyle 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 ${\displaystyle n^{\gamma }}$ com ${\displaystyle \gamma \neq 1}$, mas tais resultados são considerados pouco definitivos.

Ver também

• Teorema de Erdős–Tetali: Para todo ${\displaystyle h\geq 2}$, existe um conjunto ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ satisfazendo ${\displaystyle r_{{\mathcal {A}},h}(n)=\Theta (\log(n))}$. (Existência de bases econômicas)
• Conjectura de Erdős–Turán para bases aditivas: Se ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ é uma base aditiva de ordem 2, então ${\displaystyle 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