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\le 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 $\underset{n\to \mathrm{\infty }}{\bar{\lim }}f(n)=\mathrm{\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)=\mathrm{\#}\{(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 $\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{r}_B(n)=\mathrm{\infty }$.

Em geral, para todo $h\ge 2$ e todo subconjunto $B\subseteq \mathbb{N}$, podemos definir a função de h-representação de $B$ como $r_{B,h}(n)=\mathrm{\#}\{(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

$n\le \sum _{m=1}^n{r}_{B,h}(m)\le |B\cap [1,n]{|}^h$

Assim obtemos o minorante $n^{1/h}\le |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]|\ge 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\le r_B(n)\le 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 $\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{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.