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 Felix Behrend (en), qui le publie en 1935.

Histoire

Ce théorème tient son nom du mathématicien Felix Behrend qui l'a démontré en 1934, et publié en 1935. 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à connue.

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

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}})$.

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 optimale : 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é.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Behrend's theorem » (voir la liste des auteurs).

• P. Erdős, A. Sárközy et E. Szemerédi, « On an extremal problem concerning primitive sequences », Journal of the London Mathematical Society, second Series, vol. 42,‎ 1967, p. 484–488 (DOI 10.1112/jlms/s1-42.1.484, MR 0218325, lire en ligne)