Théorème de Linnik

Le théorème de Linnik en théorie analytique des nombres répond à une question naturelle d'après le théorème de la progression arithmétique de Dirichlet. Il affirme qu'il existe deux nombres positifs $c$ et $L$ tels que pour n'importe quels entiers premiers entre eux $a$ et $d$ avec $1 \leq a \leq d$ , si l'on note p(a,d) le plus petit nombre premier dans la progression arithmétique

a+nd\quad (n\in \mathbb {N} ),

alors :

p(a,d)<cd^{L}.

Ce théorème a été démontré par Yuri Linnik en 1944.

Il a été montré en 1992 que la constante de Linnik $L$ est inférieure ou égale à 5,5^[1]; en 2019 la valeur de $L$ n'est pas connue mais est majorée par 5,18^[2]. De plus si l'hypothèse de Riemann généralisée est vraie alors $L$ = 2 convient pour presque tous les entiers $d$ ^[2]^,^[3]. Il est aussi conjecturé^[1] que :

\forall d\geq 2\quad p(a,d)<d^{2}.

Applications modifier

Une conjecture plus forte que le théorème de Linnick a été utilisée pour construire un algorithme de multiplication d'entiers ayant une complexité en temps de ${\mathcal {O}}(n\log n)$ , ses concepteurs ont cependant également trouvé un autre algorithme ne reposant sur aucune conjecture pour établir leur résultat^[2].

Notes et références modifier

↑ ^{a et b} (en) D. R. Heath-Brown, « Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression », Proc. London Math. Soc., vol. 64, n^o 3,‎ 1992, p. 265-338 (lire en ligne)
↑ ^{a b et c} (en) David Harvey et Joris Van Der Hoeven, « Integer multiplication in time O(n log n) », HAL,‎ 18 mars 2019 (lire en ligne).
↑ (en) E. Bombieri, J. B. Friedlander et Henryk Iwaniec, « Primes in Arithmetic Progressions to Large Moduli. III », J. Amer. Math. Soc., vol. 2, n^o 2,‎ 1989, p. 215–224 (lire en ligne)

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

Portail des mathématiques

[Heath-Brown-1] {a et b} (en) D. R. Heath-Brown, « Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression », Proc. London Math. Soc., vol. 64, n^o 3,‎ 1992, p. 265-338 (lire en ligne)

[HarveyHoeven-2] {a b et c} (en) David Harvey et Joris Van Der Hoeven, « Integer multiplication in time O(n log n) », HAL,‎ 18 mars 2019 (lire en ligne).

[3] (en) E. Bombieri, J. B. Friedlander et Henryk Iwaniec, « Primes in Arithmetic Progressions to Large Moduli. III », J. Amer. Math. Soc., vol. 2, n^o 2,‎ 1989, p. 215–224 (lire en ligne)

[1]

[2]

[3]