Conjecture de Pólya
# Conjecture de Pólya

En théorie des nombres, la conjecture de Pólya énonce que la plupart (c'est-à-dire plus de la moitié) des entiers naturels inférieurs à un entier donné ont un nombre impair de facteurs premiers. La conjecture a été proposée par le mathématicien hongrois George Pólya en 1919. En 1958, il a été prouvé que celle-ci était fausse. La taille du plus petit contre-exemple est souvent utilisée pour montrer qu'une conjecture peut être vraie pour beaucoup de nombres tout en étant fausse.

## Assertion

La conjecture de Pólya énonce que pour tout entier n supérieur à 2, si l'on partitionne les entiers naturels inférieurs ou égaux à n (en ne comptant pas 0) entre ceux qui ont un nombre impair de facteurs premiers et ceux qui en ont un nombre pair, alors le premier ensemble a plus (ou autant) d'éléments que le second. Il faut noter que les facteurs premiers sont comptés autant de fois qu'ils sont répétés. Ainsi, 24 = $2^3$ × $3^1$ a 3 + 1 = 4 facteurs premiers, alors que 30 = 2 × 3 × 5 a 3 facteurs premiers.

De façon équivalente, la conjecture peut être formulée avec la fonction de Liouville de la façon suivante :

    $L(n)=\sum _{k=1}^{n}\lambda (k)\leq 0$

pour tout n > 1. Ici, λ(k) = $(−1)^{Ω(k)}$ vaut 1 si le nombre de facteurs premiers de l'entier k est pair, et -1 s'il est impair. La fonction Ω compte le nombre total de facteurs premiers d'un entier.

## Contre-exemple

La conjecture de Pólya a été réfutée par C. Brian Haselgrove en 1958. Il a montré qu'elle avait un contre-exemple, qu'il a estimé à environ 1,845 × $10^{361}.$

Un contre-exemple explicite, pour n = 906 180 359, a été donné par R. Sherman Lehman en 1960 ; le plus petit contre-exemple est n = 906 150 257, trouvé par Minoru Tanaka en 1980.

La conjecture de Pólya est en défaut pour la plupart des valeurs de n dans la région 906 150 257 ≤ n ≤ 906 488 079. Dans cette zone, la fonction de Liouville atteint une valeur maximale de 829 en n = 906 316 571.

