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 fixo, existe um subconjunto dos números naturais satisfazendo

onde denota o número de formas de expressar um certo número natural n como a soma de h elementos de B.Enunciado alternativo em notação grande Theta:

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 é dita econômicaComo em Halberstam & Roth (1983), pg. 111. (ou também magraComo em Tao & Vu (2006), pg. 13.) quando esta é uma base aditiva de ordem h e

para todo . 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 Ver Definição 3 (pg. 3) de O'Bryant, K. (2004), "A complete annotated bibliography of work related to Sidon sequences" (PDF), Electronic Journal of Combinatorics, 11: 39. 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 </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).Veja pg. 264 de Erdős–Tetali.

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 por

onde é alguma constante real grande, é 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).Ver Teorema 1 do Capítulo III. Em seguida, mostra-se que o valor esperado da variável aleatória possui a ordem de log. Isto é,

Finalmente, mostra-se que quase certamente concentra em torno da média. Mais explicitamente:

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)Seção 1.8 de 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.Capítulo 8, pg. 139 de Alon & Spencer (2016).

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

A conjectura de Erdős–Turán para bases aditivas original diz, em sua forma mais geral, que se é uma base aditiva de ordem h, então

isto é, 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

sempre que é uma base aditiva de ordem 2. Em outras palavras, isso está dizendo que não é somente ilimitado, mas também que nenhuma função menor que log domina . Esta questão naturalmente se estende para , 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 que satisfaz , tal que pode ser computado em tempo polinomial em n. A questão para continua aberta.

Sub-bases econômicas Dada uma base aditiva arbitrária , podemos perguntar se existe algum tal que é uma base econômica. V. Vu (2000) mostrou que este é de fato o caso para bases de Waring , onde, para todo k fixo, existe uma sub-base econômica de com ordem para todo , onde é 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 , para quais funções f podemos encontrar subconjuntos dos naturais satisfazendo ? É 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: , e para algum , então existe uma base aditiva de ordem h que satisfaz . O caso minimal recupera o teorema de Erdős–Tetali.

Ver também Teorema de Erdős–Fuchs: Para todo não-nulo, não existe satisfazendo . Conjectura de Erdős–Turán para bases aditivas: Se é uma base aditiva de ordem 2, então . Problema de Waring, o problema de representar números como somas de k-potências, com 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. . OCLC 840282845. Alon, N.; Spencer, J. (2016). The probabilistic method (4th ed.). Wiley. . OCLC 910535517. Tao, T.; Vu, V. (2006). Additive combinatorics. Cambridge University Press. . OCLC 71262684.

Categoria:Teoremas Categoria:Teoria dos números Categoria:Combinatória Categoria:Paul Erdős