Entier friable

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Nombre lisse)
Aller à : navigation, rechercher

En théorie des nombres, un nombre entier naturel est dit friable (ou parfois lisse) si tous ses facteurs premiers sont « petits » relativement à une borne donnée.

La théorie des entiers friables, particulièrement importante en cryptographie basée sur la factorisation, constitue depuis une vingtaine d'années une branche dynamique de la théorie des nombres, avec des applications dans des domaine aussi variés que l'algorithmique (problème du logarithme discret), la théorie de la sommabilité (sommation friable des séries de Fourier[1]), la théorie élémentaire des nombres premiers (preuve élémentaire du théorème des nombres premiers de Daboussi en 1984[2]), la méthode du cercle (problème de Waring), le modèle de Billingsley, le modèle de Kubilius (en), l'inégalité de Turán-Kubilius (en), les théorèmes de type Erdős-Wintner (en), etc.

Définition[modifier | modifier le code]

Un entier strictement positif est dit y-friable si tous ses facteurs premiers sont inférieurs ou égaux à y.

Par exemple 72 900 000 000 = 28 × 36 × 58 est 5-friable car aucun de ses facteurs premiers ne dépasse 5.

Répartition[modifier | modifier le code]

D'après Hildebrand-Tenenbaum[3], pour tout \varepsilon>0, le nombre \Psi(x,y) des entiers y-friables n'excédant pas x vérifie

 
(*)\qquad \Psi(x,y)= x \varrho(u) \exp{O(R)} \;

dès que  y>(\log x)^{1+\varepsilon}, où 
u:=(\log x)/\log y, et


R:=(\log (u+1))/\log y + u \exp(-(\log y)^{3/5-\varepsilon}).

Cela implique notamment


(**)\qquad \Psi(x,y)= \{1+o(1)\}x \varrho(u)\;

si  y>\exp(\log\log x)^{5/3+\epsilon}
, où \varrho désigne la fonction de Dickman.
De plus, Hildebrand a montré[4] que la formule 
\Psi(x, y) = x\rho(u) \exp\{O(1)\}
est valable dans le domaine


 y>(\log x)^{2+\varepsilon}

si et seulement si l'hypothèse de Riemann est vraie.

Entier ultrafriable[modifier | modifier le code]

On dit qu'un nombre entier n est ultrafriable s'il n'est divisible par aucune puissance de nombre premier excédant une borne donnée à l'avance, disons y. On parle alors de nombre y-ultrafriable. Ainsi 12 est 3-friable mais seulement 4-ultrafriable. Les nombres ultrafriables interviennent en algorithmique, en théorie des graphes et bien entendu en théorie des nombres.

Notes[modifier | modifier le code]

  1. R. de la Bretèche et G. Tenenbaum, « Séries trigonométriques à coefficients arithmétiques », Journal d'analyse mathématique, vol. 92,‎ 2004, p. 1-79.
  2. Cf. Tenenbaum et Mendès France 2013.
  3. (en) A. Hildebrand et G. Tenenbaum, « On integers free of large prime factors », Transactions of the American Mathematical Society, vol. 296,‎ 1986, p. 265-290 (voir aussi Tenenbaum 2008).
  4. (en) A. Hildebrand, « Integers free of large prime factors and the Riemann hypothesis », Mathematika, vol. 31,‎ 1984, p. 258-271.

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Liens externes[modifier | modifier le code]

Suites des nombres y-friables sur l'encyclopédie en ligne des suites de nombres entiers :

  • nombres 2-friables : A000079 (2i)
  • nombres 3-friables : A003586 (2i3j)
  • nombres 5-friables : A051037 (2i3j5k)
  • nombres 7-friables : A002473 (2i3j5k7l)
  • nombres 11-friables : A051038 (etc.)
  • nombres 13-friables : A080197
  • nombres 17-friables : A080681
  • nombres 19-friables : A080682
  • nombres 23-friables : A080683

Articles connexes[modifier | modifier le code]