| dbo:abstract
|
- The Erdős–Turán conjecture is an old unsolved problem in additive number theory (not to be confused with Erdős conjecture on arithmetic progressions) posed by Paul Erdős and Pál Turán in 1941. The question concerns subsets of the natural numbers, typically denoted by , called additive bases. A subset is called an (asymptotic) additive basis of finite order if there is some positive integer such that every sufficiently large natural number can be written as the sum of at most elements of . For example, the natural numbers are themselves an additive basis of order 1, since every natural number is trivially a sum of at most one natural number. Lagrange's four-square theorem says that the set of positive square numbers is an additive basis of order 4. Another highly non-trivial and celebrated result along these lines is Vinogradov's theorem. One is naturally inclined to ask whether these results are optimal. It turns out that Lagrange's four-square theorem cannot be improved, as there are infinitely many positive integers which are not the sum of three squares. This is because no positive integer which is the sum of three squares can leave a remainder of 7 when divided by 8. However, one should perhaps expect that a set which is about as sparse as the squares (meaning that in a given interval , roughly of the integers in lie in ) which does not have this obvious deficit should have the property that every sufficiently large positive integer is the sum of three elements from . This follows from the following probabilistic model: suppose that is a positive integer, and are 'randomly' selected from . Then the probability of a given element from being chosen is roughly . One can then estimate the expected value, which in this case will be quite large. Thus, we 'expect' that there are many representations of as a sum of three elements from , unless there is some arithmetic obstruction (which means that is somehow quite different than a 'typical' set of the same density), like with the squares. Therefore, one should expect that the squares are quite inefficient at representing positive integers as the sum of four elements, since there should already be lots of representations as sums of three elements for those positive integers that passed the arithmetic obstruction. Examining Vinogradov's theorem quickly reveals that the primes are also very inefficient at representing positive integers as the sum of four primes, for instance. This begets the question: suppose that , unlike the squares or the prime numbers, is very efficient at representing positive integers as a sum of elements of . How efficient can it be? The best possibility is that we can find a positive integer and a set such that every positive integer is the sum of at most elements of in exactly one way. Failing that, perhaps we can find a such that every positive integer is the sum of at most elements of in at least one way and at most ways, where is a function of . This is basically the question that Paul Erdős and Pál Turán asked in 1941. Indeed, they conjectured a negative answer to this question, namely that if is an additive basis of order of the natural numbers, then it cannot represent positive integers as a sum of at most too efficiently; the number of representations of , as a function of , must tend to infinity. (en)
- La conjecture d'Erdős-Turán est un problème non résolu en théorie additive des nombres, posé en 1941 par Paul Erdős et Pál Turán dans un article sur le problème de Sidon. (fr)
- A Conjectura de Erdős–Turán é um antigo problema em aberto em teoria aditiva dos números (não confundir com a ) proposto por Paul Erdős e Pál Turán em 1941. A questão concerne subconjuntos dos números naturais, tipicamente denotado por , chamados bases aditivas. Um subconjunto é chamado de base aditiva de ordem finita (resp. base aditiva assintótica) quando existe um inteiro positivo tal que todo número (resp. todo número suficientemente grande) pode ser escrito como a soma de elementos de . 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 que seja tão esparso quanto os quadrados (isto é, que dado um intervalo , aproximadamente dos inteiros em são elementos de ) 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 . Isto seguiria da seguinte intuição probabilística: suponha que é um inteiro positivo, e são selecionados 'aleatoriamente' de . Então a probabilidade de um dado elemento de ser escolhido é aproximadamente . Poderíamos então estimar seu valor esperado, o qual, neste caso, será consideravelmente grande. Assim, espera-se que haja bastante representações de como soma de três elementos de , a menos que haja alguma obstrução aritmética (o que significa que é 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 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 , diferente do conjunto dos quadrados e dos primos, seja deveras eficiente em representar inteiros positivos como soma de elementos de . Quão eficiente pode ser? Idealmente, gostaríamos de encontrar um inteiro positivo e um conjunto tal que todo inteiro positivo pode ser escrito como a soma de até elementos de de exatamente um único jeito. Falhando isto, talvez poderíamos tentar encontrar um conjunto tal que todo inteiro positivo pudesse ser escrito como a soma de até elementos de de no mínimo um jeito, e no máximo jeitos, onde é uma função de (isto é, não depende de ). 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 é uma base aditiva de ordem , então esta não pode representar os inteiros positivos como soma de até elementos de forma tão eficiente; mais precisamente, o número de representações de , como uma função de , deve divergir para infinito. (pt)
|
| rdfs:comment
|
- La conjecture d'Erdős-Turán est un problème non résolu en théorie additive des nombres, posé en 1941 par Paul Erdős et Pál Turán dans un article sur le problème de Sidon. (fr)
- The Erdős–Turán conjecture is an old unsolved problem in additive number theory (not to be confused with Erdős conjecture on arithmetic progressions) posed by Paul Erdős and Pál Turán in 1941. The question concerns subsets of the natural numbers, typically denoted by , called additive bases. A subset is called an (asymptotic) additive basis of finite order if there is some positive integer such that every sufficiently large natural number can be written as the sum of at most elements of . For example, the natural numbers are themselves an additive basis of order 1, since every natural number is trivially a sum of at most one natural number. Lagrange's four-square theorem says that the set of positive square numbers is an additive basis of order 4. Another highly non-trivial and celebra (en)
- A Conjectura de Erdős–Turán é um antigo problema em aberto em teoria aditiva dos números (não confundir com a ) proposto por Paul Erdős e Pál Turán em 1941. A questão concerne subconjuntos dos números naturais, tipicamente denotado por , chamados bases aditivas. Um subconjunto é chamado de base aditiva de ordem finita (resp. base aditiva assintótica) quando existe um inteiro positivo tal que todo número (resp. todo número suficientemente grande) pode ser escrito como a soma de elementos de . 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 ba (pt)
|
