Teorema de Erdős–Tetali

Em teoria aditiva dos números, uma área da matemática, o Teorema de Erdős–Tetali é um teorema de existência que diz respeito a bases aditivas econômicas de ordem arbitrária. Mais especificamente, o teorema diz que para todo inteiro $h\geq 2$ fixo, existe um subconjunto dos números naturais ${\mathcal {B}}\subseteq \mathbb {N}$ satisfazendo $$r_{{\mathcal {B}},h}(n)\asymp \log n,$$ onde $r_{{\mathcal {B}},h}(n)$ denota o número de formas de expressar um certo número natural n como a soma de h elementos de B.

Este teorema foi provado por Paul Erdős e Prasad V. Tetali, em um artigo publicado em 1990.

Motivação

A motivação original para este resultado é atríbuida a um problema sobre bases econômicas proposto por S. Sidon, em 1932. Uma base aditiva ${\mathcal {B}}\subseteq \mathbb {N}$ é dita econômica (ou também magra) quando esta é uma base aditiva de ordem h e

$r_{{\mathcal {B}},h}(n)\ll _{\varepsilon }n^{\varepsilon },$

para todo $\varepsilon >0$. Em outras palavras, estas são aquelas bases aditivas que necessitam perto do mínimo possível de elementos para representar um certo número n, e, ainda assim, representam todo número natural. Conceitos relacionados incluem sequências $B_{h}[g]$ e a Conjectura de Erdős–Turán para bases aditivas.

O problema de Sidon postulava a existência de bases econômicas de ordem 2. Uma resposta afirmativa foi dada por P. Erdős em 1956, estabelecendo o caso h = 2</math> do teorema. Apesar do fato que acreditava-se que a versão geral era verdadeira, nenhuma demonstração completa apareceu na literatura antes do artigo de Erdős e Tetali (1990).

Ideias da demonstração

A demonstração deste teorema é uma instância do método probabilístico, e pode ser dividida em três partes principais. Primeiramente, começamos definindo uma sequência aleatória $\omega \subseteq \mathbb {N}$ por

$\Pr(n\in \omega )=C\cdot n^{{\frac {1}{h}}-1}\log(n)^{\frac {1}{h}},$

onde $C>0$ é alguma constante real grande, $h\geq 2$ é um inteiro fixo e n é suficientemente grande para que a fórmula acima esteja bem definida. Uma discussão detalhada no espaço de probabilidade associado com este tipo de construção pode ser encontrada em Halberstam & Roth (1983). Em seguida, mostra-se que o valor esperado da variável aleatória $r_{\omega ,h}(n)$ possui a ordem de log. Isto é,

$\mathbb {E} (r_{\omega ,h}(n))\asymp \log n.$

Finalmente, mostra-se que $r_{\omega ,h}(n)$ quase certamente concentra em torno da média. Mais explicitamente: $$\Pr {\big (}\exists c_{1},c_{2}>0~|~{\text{para todo }}n{\text{ grande}},~c_{1}\mathbb {E} (r_{\omega ,h}(n))\leq r_{\omega ,h}(n)\leq c_{2}\mathbb {E} (r_{\omega ,h}(n)){\big )}=1$$ Esta é a etapa crítica da demonstração. Originalmente, essa parte é resolvida usando a desigualdade de Janson, um tipo de desiguladade de concentração para polinômios multivariados. Tao & Vu (2006) apresentam esta parte com uma desigualdade dupla mais sofisticada devida a V. Vu (2000), relativamente simplificando esta etapa assim. Alon & Spencer (2016) classificam esta demonstração como uma instância do paradigma de Poisson.

Relação com a conjectura de Erdős–Turán para bases aditivas

Ver artigo principal: Conjectura de Erdős–Turán para bases aditivas

Problema de matemática em aberto:

Seja ${\textstyle h\geq 2}$ um inteiro. Se ${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$ é um conjunto tal que ${\textstyle r_{{\mathcal {B}},h}(n)>0}$ para todo n, é verdade que isso implica que:

$\limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},h}(n)}{\log n}}>0$?

(mais problemas em aberto da matemática)

A conjectura de Erdős–Turán para bases aditivas original diz, em sua forma mais geral, que se ${\mathcal {B}}\subseteq \mathbb {N}$ é uma base aditiva de ordem h, então

$\limsup _{n\to \infty }r_{{\mathcal {B}},h}(n)=\infty ;$

isto é, ${\textstyle r_{{\mathcal {B}},h}(n)}$ não pode ser limitado. Em seu artigo de 1956, P. Erdős se perguntou se, na verdade, não seria o caso de que

$\limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},2}(n)}{\log n}}>0$

sempre que ${\mathcal {B}}\subseteq \mathbb {N}$ é uma base aditiva de ordem 2. Em outras palavras, isso está dizendo que ${\textstyle r_{{\mathcal {B}},2}(n)}$ não é somente ilimitado, mas também que nenhuma função menor que log domina ${\textstyle r_{{\mathcal {B}},2}(n)}$. Esta questão naturalmente se estende para $h\geq 3$, fazendo desta uma versão mais forte de Erdős–Turán para bases aditivas. Em certo sentido, o que está sendo conjecturado é que não existem bases aditivas substancialmente mais econômicas do que aquelas garantidas de existir pelo Teorema de Erdős–Tetali.

Avanços posteriores

Bases econômicas computáveis

Todas as demonstrações conhecidas para o teorema de Erdős–Tetali são, pela natureza do espaço de probabilidade infinito utilizado, não-construtivas. Não obstante, Kolountzakis (1995) mostrou a existência de um conjunto recursivo ${\mathcal {R}}\subseteq \mathbb {N}$ que satisfaz $r_{{\mathcal {R}},2}(n)\asymp \log n$, tal que ${\mathcal {R}}\cap \{0,1,\ldots ,n\}$ pode ser computado em tempo polinomial em n. A questão para $h\geq 3$ continua aberta.

Sub-bases econômicas

Dada uma base aditiva arbitrária ${\mathcal {A}}\subseteq \mathbb {N}$, podemos perguntar se existe algum ${\mathcal {B}}\subseteq {\mathcal {A}}$ tal que ${\mathcal {B}}$ é uma base econômica. V. Vu (2000) mostrou que este é de fato o caso para bases de Waring $\mathbb {N} ^{\wedge }k:=\{0^{k},1^{k},2^{k},\ldots \}$, onde, para todo k fixo, existe uma sub-base econômica de $\mathbb {N} ^{\wedge }k$ com ordem $s$ para todo $s\geq s_{k}$, onde $s_{k}$ é uma constante grande porém computável.

Ordens de crescimento além de log

Outra questão possível é a de se resultados similares se aplicam para outras funções além de log. Isto é, fixando um inteiro $h\geq 2$, para quais funções f podemos encontrar subconjuntos dos naturais ${\mathcal {B}}\subseteq \mathbb {N}$ satisfazendo $r_{{\mathcal {B}},h}(n)=\Theta (f(n))$? É consequência de um resultado de C. Táfula (2019) que se f é uma função real positiva, localmente integrável, satisfazendo às seguintes condições:

• ${\frac {1}{x}}\int _{1}^{x}f(t)\,\mathrm {d} t\asymp f(x)$, e
• $\log(x)\ll f(x)\ll x^{\frac {1}{h-1}}(\log x)^{-\varepsilon }$ para algum $\varepsilon >0$,

então existe uma base aditiva ${\mathcal {B}}\subseteq \mathbb {N}$ de ordem h que satisfaz $r_{{\mathcal {B}},h}(n)\asymp f(n)$. O caso minimal f(x) = log x recupera o teorema de Erdős–Tetali.

Ver também

• Teorema de Erdős–Fuchs: Para todo $C\in \mathbb {R}$ não-nulo, não existe ${\mathcal {B}}\subseteq \mathbb {N}$ satisfazendo $\textstyle {\sum _{n\leq x}r_{{\mathcal {B}},2}(n)=Cx+o\left(x^{1/4}\log(x)^{-1/2}\right)}$.
• Conjectura de Erdős–Turán para bases aditivas: Se ${\mathcal {B}}\subseteq \mathbb {N}$ é uma base aditiva de ordem 2, então $r_{{\mathcal {B}},2}(n)\neq O(1)$.
• Problema de Waring, o problema de representar números como somas de k-potências, com $k\geq 2$ fixo.

Referências

• Erdős, P.; Tetali, P. (1990). "Representations of integers as the sum of k terms". Random Structures & Algorithms. 1 (3): 245–261. ISSN 1098-2418. doi:10.1002/rsa.3240010302.
• Halberstam, H.; Roth, K. F. (1983). Sequences. Springer New York. ISBN 978-1-4613-8227-0. OCLC 840282845.
• Alon, N.; Spencer, J. (2016). The probabilistic method (4th ed.). Wiley. ISBN 978-1-1190-6195-3. OCLC 910535517.
• Tao, T.; Vu, V. (2006). Additive combinatorics. Cambridge University Press. ISBN 0521853869. OCLC 71262684.