# Conjectura de Erdős–Turán para bases aditivas

A Conjectura de Erdős–Turán é um antigo problema em aberto em teoria aditiva dos números (não confundir com a Conjectura de Erdős para progressões aritméticas) proposto por Paul Erdős e Pál Turán em 1941.
A questão concerne subconjuntos dos números naturais, tipicamente denotado por $\mathbb {N}$, chamados bases aditivas. Um subconjunto $B$ é chamado de base aditiva de ordem finita (resp. base aditiva assintótica) quando existe um inteiro positivo $h$ tal que todo número (resp. todo número suficientemente grande) $n$ pode ser escrito como a soma de $h$ elementos de $B$. Por exemplo, o conjunto de todos números naturais é em si uma base aditiva de ordem 1, já que todo número natural pode ser trivialmente escrito como a soma de até 1 número natural. É um teorema não-trivial de Lagrange (Teorema dos quatro quadrados) que o conjunto dos números quadrados formam uma base aditiva de ordem 4. Outro teorema célebre e altamente não-trivial nesta mesma linha é o teorema de Vinogradov, que diz que todo número ímpar suficientemente grande pode ser escrito como a soma de três números primos, e portanto o conjunto dos primos formam uma base assintótica de ordem menor ou igual a 4.
É natural se perguntar se tais resultados são melhores possíveis. O teorema dos quatro quadrados de Lagrange, por exemplo, não pode ser melhorado, pois há infinitos inteiros positivos que não podem ser escritos como soma de três quadrados. Isto é porque nenhum inteiro positivo que é a soma de três quadrados pode deixar resto 7 quando dividido por 8. De toda forma, poderia-se esperar que um conjunto $B$ que seja tão esparso quanto os quadrados (isto é, que dado um intervalo $[1,N]$, aproximadamente $N^{1/2}$ dos inteiros em $[1,N]$ são elementos de $B$) que não possua este "defeito" inerente ao conjunto dos quadrados deveria possuir a propriedade de que todo inteiro positivo suficientemente grande pode ser escrito como a soma de três elementos de $B$. Isto seguiria da seguinte intuição probabilística: suponha que $N/2<n\leq N$ é um inteiro positivo, e $x_{1},x_{2},x_{3}$ são selecionados 'aleatoriamente' de $B\cap [1,N]$. Então a probabilidade de um dado elemento de $B$ ser escolhido é aproximadamente $1/N^{1/2}$. Poderíamos então estimar seu valor esperado, o qual, neste caso, será consideravelmente grande. Assim, espera-se que haja bastante representações de $n$ como soma de três elementos de $B$, a menos que haja alguma obstrução aritmética (o que significa que $B$ é de certa forma bem diferente dos conjuntos "típicos" de densidade similar), como no caso dos quadrados. Portanto, é de se esperar que os quadrados sejam consideravelmente ineficientes em representar inteiros positivos como somas de quatro elementos, pois já há muitas representações como somas de três elementos àqueles inteiros positivos $n$ que passaram pela obstrução aritmética. Examinar o teorema de Vinogradov também revela que os primos são, como os quadrados, bastante ineficientes no que se refere a representar inteiros positivos como soma de, por exemplo, quatro elementos.
A questão levantada por esta linha de raciocínio é a seguinte: suponha que $B$, diferente do conjunto dos quadrados e dos primos, seja deveras eficiente em representar inteiros positivos como soma de $h$ elementos de $B$. Quão eficiente $B$ pode ser? Idealmente, gostaríamos de encontrar um inteiro positivo $h$ e um conjunto $B$ tal que todo inteiro positivo $n$ pode ser escrito como a soma de até $h$ elementos de $B$ de exatamente um único jeito. Falhando isto, talvez poderíamos tentar encontrar um conjunto $B$ tal que todo inteiro positivo $n$ pudesse ser escrito como a soma de até $h$ elementos de $B$ de no mínimo um jeito, e no máximo $S(h)$ jeitos, onde $S$ é uma função de $h$ (isto é, não depende de $n$).
Esta é basicamente a questão levantada por Paul Erdős e Pál Turán em 1941. Com efeito, eles conjecturaram uma resposta negativa para esta questão, isto é, que se $B$ é uma base aditiva de ordem $h$, então esta não pode representar os inteiros positivos como soma de até $h$ elementos de forma tão eficiente; mais precisamente, o número de representações de $n$, como uma função de $n$, deve divergir para infinito.

## História

Esta conjectura foi escrita em um trabalho conjunto de Paul Erdős e Pál Turán em 1941. No artigo original, é enunciado
"(2) Se $f(n)>0$ para $n>n_{0}$, então $\varlimsup _{n\rightarrow \infty }f(n)=\infty$"
Acima, $f(n)$ denota o número de maneiras de escrever um número natural $n$ como a soma de dois elementos (não necessariamente distintos) de $B$. Se $f(n)$ é sempre positivo (i.e. maior que zero) para $n$ suficientemente grande, então $B$ é chamado de base aditiva assintótica (de ordem 2). Este problema atraiu uma atenção considerável da comunidade matemática, mas continua em aberto.
Em 1964, Erdős publicou uma versão multiplicativa desta conjectura.

## Progresso

Enquanto a conjectura continua em aberto, houve certos avanços no problema. Em primeiro lugar, é útil expressar o problema numa linguagem mais concisa. Dado um subconjunto $B\subseteq \mathbb {N}$, definimos sua função de representação por $r_{B}(n)=\#\{(a_{1},a_{2})\in B^{2}~|~a_{1}+a_{2}=n\}$. Sendo assim, a conjectura então diz que se $r_{B}(n)>0$ para todo $n$ suficientemente grande, então $\limsup _{n\rightarrow \infty }r_{B}(n)=\infty$.
Em geral, para todo $h\geq 2$ e todo subconjunto $B\subseteq \mathbb {N}$, podemos definir a função de h-representação de $B$ como $r_{B,h}(n)=\#\{(a_{1},\cdots ,a_{h})\in B^{h}~|~a_{1}+\cdots +a_{h}=n\}$. Dizemos que $B$ é uma base aditiva assintótica de ordem $h$ se $r_{B,h}(n)>0$ para todo $n$ suficientemente grande. Pode-se deduzir por um argumento elementar que se $B$ é uma base assintótica de ordem $h$, então
$\displaystyle n\leq \sum _{m=1}^{n}r_{B,h}(m)\leq |B\cap [1,n]|^{h}$
Assim obtemos o minorante $n^{1/h}\leq |B\cap [1,n]|$.
A conjectura original nasceu enquanto Erdős e Turán procuravam uma solução parcial para um problema de Sidon (veja: Sequência de Sidon). Mais tarde, Erdős se propôs a responder à seguinte questão proposta por Sidon: quão próximo do minorante $|B\cap [1,n]|\geq n^{1/h}$ pode uma base aditiva $B$ de ordem $h$ chegar? Esta questão foi respondida para o caso $h=2$ por Erdős em 1956. Erdős mostrou que existe uma base aditiva $B$ de ordem 2 e constantes $c_{1},c_{2}>0$ tais que $c_{1}\log n\leq r_{B}(n)\leq c_{2}\log n$ para todo $n$ suficientemente grande. Em particular, isto implica na existência de bases aditivas $B$ que satisfazem $r_{B}(n)=n^{1/2+o(1)}$, o que é essencialmente o melhor possível em termos de eficiência. Isto motivou Erdős a conjecturar o seguinte:
* Se $B$ é uma base aditiva de ordem $h$, então $\limsup _{n\rightarrow \infty }r_{B,h}(n)/\log n>0.$
Em 1986, Eduard Wirsing mostrou que uma grande classe de bases aditivas, incluindo os números primos, contém um subconjunto significamente mais magro que ainda é uma base aditiva. Em 1990, Erdős e Prasad V. Tetali estenderam o resultado de 1956 de Erdős para bases de ordem arbitrária. Em 2000, V. Vu provou que sub-bases magras existem nas bases de Waring usando o método do círculo de Hardy e Littlewood em conjunto com seus resultados sobre concentração polinomial. Em 2006, Borwein, Choi, e Chu provaram que para toda base aditiva $B$, de algum momento em diante $f(n)$ sempre excede 7.