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 friable, ou lisse, est un entier naturel dont l'ensemble des facteurs premiers sont petits, relativement à une borne donnée. Ce terme aurait été inventé par Leonard Adleman.

Les entiers friables sont particulièrement importants dans la cryptographie basée sur la factorisation, qui 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 B-friable, ou B-lisse, si tous ses facteurs premiers sont inférieurs ou égaux à B.

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

Cette définition inclut les nombres qui ne figurent pas parmi les facteurs premiers : 12 est 5-friable, ou 5-lisse, même si 5 n'est pas un facteur de 12. Le nombre friable n'a pas non plus besoin d'être premier.

Répartition[modifier | modifier le code]

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

dès que , où , et

Cela implique notamment

si , où désigne la fonction de Dickman.
De plus, Hildebrand a montré[4] que la formule est valable dans le domaine

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

Entier ultrafriable[modifier | modifier le code]

Un nombre est dit B-superlisse ou B-ultrafriable si tous ses diviseurs de la forme , avec p premier et entier, satisfont :

Par exemple, 720 (243251) est 5-lisse mais pas 5-ultralisse (parce qu'il y a plusieurs puissances entières plus grandes que 5 : ou ). Il est par contre 16-ultralisse puisque sa plus grande puissance de facteur premier est 24 = 16. Ce nombre est bien sûr aussi 17-ultralisse, 18-ultralisse, etc.

Les nombres ultrafriables interviennent en algorithmique, en théorie des graphes et bien entendu en théorie des nombres.

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Smooth number » (voir la liste des auteurs).

  1. R. de la Bretèche et G. Tenenbaum, « Séries trigonométriques à coefficients arithmétiques », Journal d'analyse mathématique, vol. 92,‎ , 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,‎ , p. 265-290 (voir aussi Tenenbaum 2015).
  4. (en) A. Hildebrand, « Integers free of large prime factors and the Riemann hypothesis », Mathematika, vol. 31,‎ , p. 258-271.

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]

Bibliographie[modifier | modifier le code]