Théorème de Linnik

Modèle:Voir homonymes 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

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

alors :

$p(a,d)<c{d}^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 Modèle:Math est inférieure ou égale à 5,5; en 2019 la valeur de Modèle:Math n'est pas connue mais est majorée par 5,18. 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:MathModèle:,. Il est aussi conjecturé que :

$\mathrm{\forall }d\ge 2p(a,d)<d^2.$

Applications

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