Conjecture de Pólya

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Fonction sommatoire de la fonction de Liouville L(n) jusqu'à n = 107.
Gros plan sur la fonction sommatoire de la fonction de Liouville L(n) dans la région où la conjecture de Pólya est en défaut.

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.

Assertion[modifier | modifier le code]

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 :

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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. (de) George Pólya, « Verschiedene Bemerkungen zur Zahlentheorie », Jahresber. der DMV, vol. 28,‎ 1919, p. 31-40
  2. (en) C. B. Haselgrove, « A disproof of a conjecture of Pólya », Mathematika, vol. 5, no 02,‎ 1958, p. 141-145
  3. (en) R. S. Lehman, « On Liouville's function », Mathematics of Computation, vol. 14, no 72,‎ 1960, p. 311-320 (lire en ligne)
  4. (en) M. Tanaka, « A Numerical Investigation on Cumulative Sum of the Liouville Function », Tokyo Journal of Mathematics, vol. 3, no 1,‎ 1980, p. 187-189 (lire en ligne)