Théorème de Behrend

En théorie combinatoire des nombres, le théorème de Behrend énonce que les ensembles d'entiers compris entre 1 et $n$ dans lesquels aucun élément n'est multiple d'un autre ont une densité logarithmique qui tend vers 0 lorsque $n$ tend vers l'infini. Le théorème porte le nom de Modèle:Lien, qui le publie en 1935.

Histoire

Ce théorème tient son nom du mathématicien Felix Behrend qui l'a démontré en 1934Modèle:Références multiples, et publié en 1935Modèle:Références multiples. Paul Erdős montre le même résultat, lors d'un trajet en train en 1934, allant de Hongrie à Cambridge pour fuir l'antisémitisme croissant en Europe, mais il découvre à l'arrivée que la preuve est déjà connueModèle:Références multiples.

Énoncé

La densité logarithmique d'un ensemble d'entiers compris entre 1 et $n$ peut être définie en associant à chaque entier $i$ un poids valant $1/i$, et en divisant le poids total de l'ensemble par la $n$-ième somme partielle de la série harmonique (ou, de manière équivalente lorsque $n$ tend vers l'infini, par $\log n$). Cette densité vaut 1 ou est proche de 1 si l'ensemble inclut la plupart des entiers compris entre 1 et $n$ ; elle est petite dans le cas contraire, en particulier lorsque les nombres manquants sont eux-mêmes petits devant $n$Modèle:Références multiples.

Un sous-ensemble de $[[1,n]]$ est dit primitif si aucun de ses éléments n'est multiple d'un autre. Le théorème de Behrend énonce que la densité logarithmique d'un tel ensemble est inférieure à $O(1/\sqrt{\log \log n})$Modèle:Références multiples.

Exemples

Il existe de grands sous-ensembles primitifs de $[[1,n]]$. Cependant, ces ensembles ont de faible densité logarithmique.

• Le sous-ensemble $\{\lceil (n+1)/2\rceil ,\dots n\}$ : pour chaque paire de nombres, le quotient du plus grand par le plus petit est strictement inférieur à 2, et le plus grand nombre n'est donc pas un multiple du plus petit. Cet ensemble est donc un ensemble primitif. D'après le théorème de Dilworth (utilisant une partition des entiers en chaînes de puissances de deux multipliées par un nombre impair), ce sous-ensemble a le plus grand cardinal parmi les sous-ensembles primitifs de $[[1,n]]$. Puisque tous ses éléments sont grands, ce sous-ensemble à une faible densité logarithmique, inférieure à $O(1/\log n)$.
• Un autre exemple d'ensemble primitif est celui constitué des nombres premiers. Cet ensemble à une densité logarithmique un peu plus grande, $O(\log \log n/\log n)$, donnée par la divergence de la série des inverses des nombres premiers.

Ces deux ensembles primitifs ont des densités logarithmiques bien plus faibles que la borne donnée par le théorème de Behrend. En démontrant une conjecture de G. H. Hardy, Paul Erdős et Subbayya Sivasankaranarayana Pillai ont montré que, pour $k\approx \log \log n$, l'ensemble des nombres de $[[1,n]]$ ayant exactement $k$ facteurs premiers (comptés avec multiplicité) possède une densité logarithmique de $\frac{1+o(1)}{\sqrt{2\pi \log \log n}}$, montrant ainsi que la borne de Behrend est optimaleModèle:Références multiples : cet exemple est optimal au sens où aucun autre sous-ensemble primitif ne possède la même densité logarithmique avec un facteur multiplicatif $k$ plus élevéModèle:Références multiples.

Références

• Modèle:Article