A note on Linnik's theorem on quadratic non-residues (Q1737357): Difference between revisions

This article gives a short elementary proof of \textit{Yu. V. Linnik}'s classical result about least quadratic non-residues [C. R. (Dokl.) Acad. Sci. URSS, n. Ser. 30, 292--294 (1941; Zbl 0024.29302)]. This result says that for every \(\varepsilon>0\), there is a constant \(C_{\varepsilon}>0\) such that for all natural numbers \(N\), the number of primes less or equal \(N\) whose least quadratic non-residue exceeds \(N^{\varepsilon}\) is bounded by \(C_{\varepsilon}\). Linnik himself proved this result using his large sieve, which is Fourier analytic in nature. Let \(\Psi(n,B)\) be the number of \(B\)-smooth numbers less or equal \(n\) and let \(d\) be the number of primes less or equal \(N\) whose least quadratic non-residue is greater than \(B\). The authors use a simple combinatorial inequality to obtain an upper bound for \(\Psi(N^3,B)\) in terms of \(d\) and \(B\). Combining this with a weak lower bound for \(\Psi(n,B)\), which can be proved by elementary means as well, they deduce Linnik's result. The said combinatorial inequality, which is at the heart of this short article, states that for any sets \(A_1,\ldots,A_d\subseteq \{1,\ldots,n\}\), \[ (d+1)^2\left| \bigcap_{i=1}^d A_i \right| \le (d+1)^2n-4d \sum\limits_{i=1}^d |A_i^c| + 4\sum\limits_{i\not=j} |A_i^c\cap A_j^c|. \]