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 Modèle:Math et Modèle:Math tels que pour n'importe quels entiers premiers entre eux Modèle:Math et Modèle:Math avec Modèle:Math, si l'on note p(a,d) le plus petit nombre premier dans la progression arithmétique

<math>a + nd\quad(n\in\N),</math>

alors :

<math> p(a,d) < c d^L.</math>

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

Il a été montré en 1992 que la constante de Linnik Modèle:Math est inférieure ou égale à 5,5<ref name=Heath-Brown>Modèle:Article</ref>; en 2019 la valeur de Modèle:Math n'est pas connue mais est majorée par 5,18<ref name="HarveyHoeven"/>. De plus si l'hypothèse de Riemann généralisée est vraie alors Modèle:Math = 2 convient pour presque tous les entiers Modèle:Math<ref name="HarveyHoeven">Modèle:Article.</ref><ref>Modèle:Article</ref>. Il est aussi conjecturé<ref name=Heath-Brown/> que :

<math>\forall d \ge 2 \quad p ( a , d ) < d^2 .</math>

Applications

• 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 <math>\mathcal{O}(n \log n)</math>, ses concepteurs ont cependant également trouvé un autre algorithme ne reposant sur aucune conjecture pour établir leur résultat<ref name="HarveyHoeven"/>.