Linnik tétele
A Linnik-tétel az analitikus számelméletben egy természetes kérdésnek felel meg a Dirichlet aritmetikai progressziójának tétele szerint . Azt állítja, hogy létezik két pozitív számok c és L olyan, hogy bármely egész szám elsődleges közöttük egy és d az 1 ≤ a ≤ d , ha mi jelöljük p ( a , d ) a legkisebb prímszám a számtani sorozat
így :
Ez a tétel mutattuk Jurij Linnik (en) 1944-ben.
1992-ben kimutatták, hogy a Linnik konstans L kisebb vagy egyenlő, mint 5,5; 2019-ben az L értéke nem ismert, de 5,18-mal nőtt. Sőt, ha az általánosított Riemann-hipotézis igaz, akkor L = 2 szinte minden d egész számra alkalmas . Azt is sejtik, hogy:
Alkalmazások
- A sejtés erősebb Linnick tétel használtuk fel egy egész szorzás algoritmus , amelynek időbonyolultsága az , hogy a tervezők, de talált egy másik algoritmust, amely nem hivatkozhat semmilyen sejtés létrehozni azok eredményét.
Megjegyzések és hivatkozások
- (en) DR Heath-Brown , „ Nulla-mentes régiók a Dirichlet L-funkciókhoz, és a legkevésbé fontosak egy aritmetikai progresszióban ” , Proc. London Math. Soc. , vol. 64, n o 3,1992, P. 265-338 ( online olvasás )
- (en) David Harvey és Joris Van Der Hoeven, „ Egész szorzás az O (n log n) időben ” , HAL ,2019. március 18( online olvasás ).
- (in) E. Bombieri , JB Friedlander és Henryk Iwaniec , " Prímek a számtani haladásban a nagy modulokba. III ” , J. Amer. Math. Soc. , vol. 2 n o 21989, P. 215–224 ( online olvasás )