Primes in arithmetic progressions and short intervals without $L$-functions

Abstract

We develop a sieve that can detect primes in multiplicatively structured sets under certain conditions. We apply it to obtain a new $L$-function free proof of Linnik's problem of bounding the least prime $p$ such that $p\equiv a(\mathrm{mod}q)$ (with the bound $p\ll q^{350}$) as well as a new $L$-function free proof that the interval $(x-x^{39/40},x]$ contains primes for every large $x$. In a future work we will develop the sieve further and provide more applications.

33 pages