Întreg friabil
În teoria numerelor , un număr friabil sau neted este un număr natural al cărui set de factori primi sunt mici, relativ la o anumită legătură.
Numerele întregi friabile sunt deosebit de importante în criptografia bazată pe factorizare, care timp de douăzeci de ani a fost o ramură dinamică a teoriei numerelor , cu aplicații în domenii la fel de variate precum algoritmica (problema logaritmului discret), teoria sumabilității ( sumarea friabilă a seriei Fourier ), teoria elementară a numerelor prime (dovada elementară a număr prim teorema lui Daboussi în 1984), The metoda cerc ( problema Waring ), modelul Billingsley, The Kubilius modelul (ro) , Turan-Kubilius inegalitate (en) , Erdős - Wintner tip teoreme etc.
Terminologie
Termenul neted este propus în engleză de criptologul american Ronald Linn Rivest la începutul anilor 1980. Termenul friabil , care desemnează capacitatea unui obiect de a fi redus în fragmente mici, este apoi propus de inginerul politehnic Jacques Balazard, soțul scriitorul Simone Balazard și tatăl matematicianului Michel Balazard. S-a impus treptat pe toată literatura în franceză și o parte din aceasta în engleză.
Definiție
Un întreg strict pozitiv se spune -B friabil , sau B-neted dacă toți ei factorii principali sunt la sau sub B .
De exemplu 72.900.000.000 = 2 8 × 3 6 × 5 8 este 5-friabil, deoarece niciunul dintre factorii săi primi nu depășește 5.
În această definiție, B nu este neapărat un factor prim al întregului B -friabil: 12 este 5-friabil sau 5-neted, chiar dacă 5 nu este un factor de 12. Numărul B nu trebuie să fie nici primul.
Divizia
Conform lui Hildebrand- Tenenbaum , pentru toți , numărul de y- numere întregi friabile care nu depășesc x satisface
ε>0{\ displaystyle \ varepsilon> 0}Ψ(X,y){\ displaystyle \ Psi (x, y)}
(∗)Ψ(X,y)=Xϱ(tu)expO(R){\ displaystyle (*) \ qquad \ Psi (x, y) = x \ varrho (u) \ exp {O (R)} \;}de îndată ce , unde
și
y>(ButurugaX)1+ε{\ displaystyle y> (\ log x) ^ {1+ \ varepsilon}}tu: =(ButurugaX)/Buturugay{\ displaystyle u: = (\ log x) / \ log y}
R: =(Buturuga(tu+1))/Buturugay+tuexp(-(Buturugay)3/5-ε).{\ displaystyle R: = (\ log (u + 1)) / \ log y + u \ exp (- (\ log y) ^ {3 / 5- \ varepsilon}).}Acest lucru implică în special
(∗∗)Ψ(X,y)={1+o(1)}Xϱ(tu){\ displaystyle (**) \ qquad \ Psi (x, y) = \ {1 + o (1) \} x \ varrho (u) \;}dacă , unde denotă funcția Dickman .
Mai mult, Hildebrand a arătat că formula este valabilă în domeniu
y>exp(ButurugaButurugaX)5/3+ϵ{\ displaystyle y> \ exp (\ log \ log x) ^ {5/3 + \ epsilon}}ϱ{\ displaystyle \ varrho}
Ψ(X,y)=Xρ(tu)exp{O(1)}{\ displaystyle \ Psi (x, y) = x \ rho (u) \ exp \ {O (1) \}}
y>(ButurugaX)2+ε{\ displaystyle y> (\ log x) ^ {2+ \ varepsilon}}dacă și numai dacă ipoteza Riemann este adevărată.
Întreg foarte fiabil
Un număr este menționat B -superlisse sau B -ultrafriable dacă toate divizorii de forma p n , cu p prim și n întreg, mai mic sau egal cu B .
De exemplu, 720 (2 4 3 2 5 1 ) este 5-neted, dar nu 5-ultralisse (deoarece are divizori primari mai mari de 5: 3 2 = 9> 5 sau 2 3 > 5). Pe de altă parte, este 16-ultralisse, deoarece cel mai mare divizor principal este 2 4 = 16. Acest număr este, desigur, și 17-ultralisse, 18-ultralisse și așa mai departe.
Numerele ultra-fiabile sunt utilizate în algoritmi , în teoria graficelor și, desigur, în teoria numerelor .
Note și referințe
(fr) Acest articol este preluat parțial sau în întregime din articolul Wikipedia din
limba engleză intitulat
„ Smooth number ” (a se vedea lista autorilor ) .
-
R. de la Bretèche și G. Tenenbaum , „ Seria trigonometrică cu coeficienți aritmetici ”, Journal of Mathematical Analysis (nl) , vol. 92,2004, p. 1-79.
-
Cf. Tenenbaum și Mendès Franța 2013 .
-
„Am inventat termenul„ număr lin ”pentru a desemna un număr care are doar factori primi mici. Nu-mi amintesc cu adevărat cum m-am gândit la asta, în afară de acel „neted” este chiar opusul lui „nodulos”. „ (Ronald Rivest, citat într-o discuție mathoverflow menționată în Tenenbaum, Words and Math ).
-
Gérald Tenenbaum , Cuvinte și matematică , Paris, Odile Jacob,2019, 215 p. ( ISBN 978-2-7381-4900-8 ) , p. 80-81
-
(în) A. Hildebrand și G. Tenenbaum , „ We integers free of premium wide factors ” , Trans. Amar. Matematica. Soc. , vol. 296,1986, p. 265-290(vezi și Tenenbaum 2015 ).
-
(în) A. Hildebrand , „ Numere întregi libere de factori premium și ipoteza Riemann ” , Mathematika , vol. 31,1984, p. 258-271.
Vezi și tu
linkuri externe
Secvențe de numere friabile y pe enciclopedia online a secvențelor de numere întregi :
- 2 numere friabile: A000079 (2 i )
- 3-numere friabile: A003586 (2 i 3 j )
- 5-numere friabile: A051037 (2 i 3 j 5 k )
- 7-numere friabile: A002473 (2 i 3 j 5 k 7 l )
- 11-numere friabile: A051038
- 13-numere friabile: A080197
- 17-numere friabile: A080681
- 19-numere friabile: A080682
- 23-numere friabile: A080683 (etc.)
Articole similare
Bibliografie
-
Gérald Tenenbaum , Introducere în teoria numerelor analitice și probabilistice , Paris, Belin,2015, 592 p. ( ISBN 978-2-7011-9656-5 ).
- Gérald Tenenbaum și Michel Mendès Franța , numere prime, între ordine și haos , Dunod,2013( ISBN 978-2-10-070656-3 și 2-10-070656-X )