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 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.

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

MotivaçãoEditar

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ômica[1] (ou também magra[2]) quando esta é uma base aditiva de ordem h e

 
isto é,   para todo  . Em outras palavras, estas são aquleas 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  [3] 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,[4] estabelecendo o caso   do quê ainda viria a se tornar o Teorema de Erdős–Tetali. Apesar do fato que suspeitava-se que a versão geral era verdadeira, nenhuma demonstração completa apareceu na literatura antes do artigo de Erdős & Tetali (1990).[5]

Ideias da demonstraçãoEditar

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).[6] 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)[7] apresentam esta parte com uma desigualdade dupla mais sofisticada devida a V. Vu (2000),[8] relativamente simplificando esta etapa assim. Alon & Spencer (2016) classificam esta demonstração como uma instância do paradigma de Poisson.[9]

Avanços posterioresEditar

Ordens de crescimento além de logEditar

Uma questão que surge naturalmente é 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 (2018)[10] 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  . Enquanto melhoramentos para o majorante de f são naturais de se esperar (e.g. não é claro se o termo   é de fato necessário), qualquer melhora para o minorante produziria um contraexemplo para a versão forte da conjectura de Erdős–Turán (ver abaixo para detalhes).

Bases econômicas computáveisEditar

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)[11] 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ômicasEditar

Dada uma base aditiva arbitrária  , podemos perguntar se existe algum   tal que   é uma base econômica. V. Vu (2000)[12] 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.

Versão forte da conjectura de Erdős–Turán para bases aditivasEditar

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  . Em seu artigo de 1956 sobre o caso   de Erdős–Tetali, P. Erdős se perguntou se, na verdade, não seria o caso de que   sempre que   é uma base aditiva de ordem 2. Esta questão naturalmente se estende para  , fazendo uma afirmação bem mais forte que Erdős–Turán. 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.

Ver tambémEditar

  • 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ênciasEditar

  1. Como em Halberstam & Roth (1983), pg. 111.
  2. Como em Tao & Vu (2006), pg. 13.
  3. 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.
  4. Erdős, P. (1956). «Problems and results in additive number theory». Colloque Sur le Theorie des Nombres: 127–137 
  5. pg. 264 de Erdős & Tetali (1990).
  6. Ver Teorema 1 do Capítulo III.
  7. Seção 1.8 de Tao & Vu (2006).
  8. Vu, Van H. (1 de julho de 2000). «On the concentration of multivariate polynomials with small expectation». Random Structures & Algorithms (em inglês). 16 (4): 344–363. ISSN 1098-2418. doi:10.1002/1098-2418(200007)16:4<344::aid-rsa4>3.0.co;2-5 
  9. Capítulo 8, pg. 139 de Alon & Spencer (2016).
  10. Táfula, Christian. «An extension of the Erdős-Tetali theorem». Random Structures & Algorithms (em inglês). 0 (0). ISSN 1098-2418. doi:10.1002/rsa.20812 
  11. Kolountzakis, Mihail N. (13 de outubro de 1995). «An effective additive basis for the integers». Discrete Mathematics. 145 (1): 307–313. doi:10.1016/0012-365X(94)00044-J 
  12. Vu, Van H. (15 de outubro de 2000). «On a refinement of Waring's problem». Duke Mathematical Journal. 105 (1): 107–134. ISSN 0012-7094. doi:10.1215/s0012-7094-00-10516-9