Théorème de Behrend

En arithmétique combinatoire, le théorème de Behrend énonce que le sous-ensemble des entiers de 1 à $n$ dans lequel aucun nombre n'est multiple d'aucun autre de l'ensemble à une densité logarithmique qui tend vers 0 lorsque $n$ tend vers l'infini. Le théorème porte le nom de Felix Behrend, qui le publie en 1935.

Enoncé

La densité logarithmique d'un ensemble d'entiers de 1 à $n$ peut être définie en posant pour chaque entier $i$ un poids valant $1/i$, et diviser le poids total par $\log n$ (où, de manière équivalente, par la $n$-ième somme partielle de la série harmonique). Le résultat correspondant vaut 1 ou est proche de 1 lorsque l'ensemble inclus un grand nombre d'entiers de 1 à $n$, et est petit dans le cas contraire, en particulier lorsque les nombres manquants sont eux-même petit devant $n$.

Un sous ensemble de $\{1,\dots n\}$ est dit primitif si aucun de ses éléments n'est multiple d'aucun autre. Le théorème de Behrend énonce que la densité logarithmique d'un tel ensemble doit vérifiée $O(1/{\sqrt {\log \log n}})$.

Exemples

Il existe de grands sous-ensembles primitifs de $\{1,\dots n\}$. Cepandant, ces ensembles ont de faible densité logarithmique.

• Le sous-ensemble $\{\lceil (n+1)/2\rceil ,\dots n\}$, chaque pair de nombres ont un facteur en commun plus petit que deux. C'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 à le plus grand cardinal parmi les sous-ensembles primitifs. Puisque tous ces éléments sont grands, ce sous-ensemble à une faible densité logarithmique, étant un $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 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 que la borne de Behrend est optimale. Cet exemple est le meilleur possible dans le sens où aucun autre sous-ensemble primitif ne possède la même densité logarithmique avec un facteur multiplicatif plus élevé.

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'anti-sémitisme croissant en Europe, mais il découvre à l'arrivé que la preuve est déjà connue.