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.
Seja
um conjunto infinito de números naturais, e escreva
para sua função de representação, que denota o número de formas de escrever num número natural
como a soma de
elementos de
(levando ordem em consideração). Consideramos então a função de representação acumulada
![{\displaystyle s_{{\mathcal {A}},h}(x):=\sum _{n\leqslant x}r_{{\mathcal {A}},h}(n),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cc84cebd78638ba888785e61b95be9a2bd87f9c)
que conta (também levando ordem em consideração) o número de soluções para
![{\displaystyle k_{1}+\cdots +k_{h}\leqslant x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8edf71abedebc4c1898424e2202e8d3a32247283)
, onde
![{\displaystyle k_{1},\ldots ,k_{h}\in {\mathcal {A}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cc8b55b1aaa03b42d551baeff52fcc32db80cb0)
. O teorema então diz que, para qualquer
![{\displaystyle c>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84)
, a relação
![{\displaystyle s_{{\mathcal {A}},2}(n)=cn+o\left(n^{1/4}\log(n)^{-1/2}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ba98d447020cb7f5ef272b4a57ef0adf6cd2bef)
não pode ser satisfeita; isto é,
nenhum ![{\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/99e13aa9284e1fa149e48050e0966beb7495b0cb)
satisfaz a estimativa acima.
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
dos quadrados perfeitos tem-se
![{\displaystyle \limsup _{n\to +\infty }{\frac {\left|s_{{\mathcal {Q}},2}(n)-\pi n\right|}{n^{1/4}\log(n)^{1/4}}}>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f091fe43caf1e7148d5f9abf38fd0f244d3ee813)
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/377419f817c2a1af4abdf5159b27aa21b5de5c2b)
). 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
![{\displaystyle s_{{\mathcal {A}},2}(n)=cn+O(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f562f5acb229abdfdaadb61066986b29f1d0c0d)
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.
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
e
são dois subconjuntos infinitos dos números naturais com
, então
nunca é válido, para nenhuma constante
.
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
![{\displaystyle s_{{\mathcal {A}},2}(n)=cn+o(n^{1/4})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/973fc907dc3321e7f8f2601acd8ae570cf4457d8)
nunca é válido. Em 2004, G. Horváth
[5] estendeu ambos estes resultados, provando o seguinte:
- Teorema (Horváth, 2004). Se
e
são subconjuntos infinitos dos números naturais com
e
, então
nunca é válido, para nenhuma constante
.
A generalização natural do Teorema de Erdős–Fuchs, para
, é 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
a relação
![{\displaystyle s_{{\mathcal {A}},h}(n)=cn+o(n^{1/4})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87cb9e352efc09b2e675ef8d674f9930dd853772)
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
(
) são
(pelo menos dois) subconjuntos infinitos dos números naturais satisfazendo as seguintes estimativas:
(for
)
- 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 )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92b01e64aa27e523ce2bb91397208da70ddc0883)
- nunca é válida, para nenhuma constante
.
Ainda outra direção na qual o teorema de Erdős–Fuchs pode ser melhorado é considerando aproximações para
diferentes de
para algum
. 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
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
nunca é válida, onde
se
é limitada, e
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
com
, mas tais resultados são considerados pouco definitivos.
- Teorema de Erdős–Tetali: Para todo
, existe um conjunto
satisfazendo
. (Existência de bases econômicas)
- Conjectura de Erdős–Turán para bases aditivas: Se
é uma base aditiva de ordem 2, então
. (Bases não podem ser muito econômicas)
↑ 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