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[1]. 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.
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 = 23 × 31 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 :
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.
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 × 10361[2].
Un contre-exemple explicite, pour n = 906 180 359, a été donné par R. Sherman Lehman en 1960[3] ; le plus petit contre-exemple est n = 906 150 257, trouvé par Minoru Tanaka en 1980[4].
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.