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 ≤ a ≤ d, si l'on note p(a,d) le plus petit nombre premier dans la progression arithmétique

alors :

Ce théorème a été démontré par Yuri Linnik (en) 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 :

ApplicationsModifier

  • 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  , ses concepteurs ont cependant également trouvé un autre algorithme ne reposant sur aucune conjecture pour établir leur résultat[2].

Notes et référencesModifier

  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, no 3,‎ , p. 265-338 (lire en ligne)
  2. a b et c (en) David Harvey et Joris Van Der Hoeven, « Integer multiplication in time O(n log n) », HAL,‎ (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, no 2,‎ , 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).