[proofplan] We apply the large-sieve mean-square discrepancy bound to the finitely supported sequence $b_n=\Lambda(n)$ for $1 \leq n \leq \lfloor x \rfloor$. This gives the desired progression-discrepancy estimate directly, because the definition of $E_\Lambda(x;q,a)$ is exactly the discrepancy appearing in that bound. The remaining work is to prove the elementary estimate $\sum_{n\leq x}\Lambda(n)^2 \leq Cx\log x$ by separating prime powers according to their base prime. [/proofplan] [step:Apply the mean-square discrepancy bound to the von Mangoldt weights] Let $N := \lfloor x \rfloor$, and define a sequence $b: \{1,\dots,N\} \to \mathbb{R}$ by $b_n := \Lambda(n)$ for every integer $1 \leq n \leq N$. Let $\varphi: \mathbb{N} \to \mathbb{N}$ denote Euler's totient function. We use the following mean-square discrepancy estimate for reduced residue classes: for every complex sequence $(b_n)_{1\leq n\leq N}$ and every $Q \geq 1$, \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} \left|\sum_{1 \leq n \leq N,\ n \equiv a \bmod q} b_n - \frac{1}{\varphi(q)}\sum_{1 \leq n \leq N,\ \gcd(n,q)=1} b_n\right|^2 \leq (N+Q^2)\sum_{n=1}^{N}|b_n|^2. \end{align*} This is the locally staged [Large Sieve Mean Square Discrepancy Bound](/theorems/7187) [quotetheorem:TEMP-28]. The sequence $b$ is finite, so the estimate applies. Since $N=\lfloor x \rfloor$, the condition $1\leq n \leq N$ is equivalent to $1\leq n \leq x$ for integers $n$. Therefore the expression inside the absolute value is precisely $E_\Lambda(x;q,a)$. Hence \begin{align*} \sum_{q \leq Q} \sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} |E_\Lambda(x;q,a)|^2 \leq (N+Q^2)\sum_{n=1}^{N}\Lambda(n)^2. \end{align*} Because $N \leq x$ and $\sum_{n=1}^{N}\Lambda(n)^2=\sum_{n\leq x}\Lambda(n)^2$, this gives \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} |E_\Lambda(x;q,a)|^2 \leq (x+Q^2)\sum_{n\leq x}\Lambda(n)^2. \end{align*} [guided] Let $N := \lfloor x \rfloor$. The reason for introducing $N$ is that the large-sieve discrepancy estimate is naturally stated for sequences indexed by integers $1,\dots,N$, while the theorem uses the analytic convention $n \leq x$. For an integer $n$, the inequalities $n \leq x$ and $n \leq \lfloor x \rfloor$ are equivalent. Define $b: \{1,\dots,N\} \to \mathbb{R}$ by $b_n := \Lambda(n)$. Let $\varphi: \mathbb{N} \to \mathbb{N}$ denote Euler's totient function. We apply the mean-square discrepancy estimate for reduced residue classes, which states that for every finite complex sequence $(b_n)_{1\leq n\leq N}$ and every $Q \geq 1$, \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} \left|\sum_{1 \leq n \leq N,\ n \equiv a \bmod q} b_n - \frac{1}{\varphi(q)}\sum_{1 \leq n \leq N,\ \gcd(n,q)=1} b_n\right|^2 \leq (N+Q^2)\sum_{n=1}^{N}|b_n|^2. \end{align*} This is the locally staged Large Sieve Mean Square Discrepancy Bound [quotetheorem:TEMP-28]. We verify the hypotheses: the sequence is finite, because it is indexed by $\{1,\dots,N\}$, and $Q \geq 1$ is assumed in the theorem. Substituting $b_n=\Lambda(n)$ gives \begin{align*} \sum_{1 \leq n \leq N,\ n \equiv a \bmod q} b_n - \frac{1}{\varphi(q)}\sum_{1 \leq n \leq N,\ \gcd(n,q)=1} b_n = \sum_{1 \leq n \leq x,\ n \equiv a \bmod q} \Lambda(n) - \frac{1}{\varphi(q)}\sum_{1 \leq n \leq x,\ \gcd(n,q)=1} \Lambda(n). \end{align*} The right-hand side is exactly $E_\Lambda(x;q,a)$ by definition. Therefore the discrepancy bound gives \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} |E_\Lambda(x;q,a)|^2 \leq (N+Q^2)\sum_{n=1}^{N}\Lambda(n)^2. \end{align*} Finally, $N \leq x$, and the integer endpoint convention gives $\sum_{n=1}^{N}\Lambda(n)^2=\sum_{n\leq x}\Lambda(n)^2$. Hence \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} |E_\Lambda(x;q,a)|^2 \leq (x+Q^2)\sum_{n\leq x}\Lambda(n)^2. \end{align*} [/guided] [/step] [step:Bound the square sum of the von Mangoldt function] We prove that there is an absolute constant $C_0>0$ such that \begin{align*} \sum_{n\leq x}\Lambda(n)^2 \leq C_0 x\log x. \end{align*} Since $\Lambda(n)$ is nonzero only when $n=p^k$ for a prime $p$ and an integer $k\geq 1$, and then $\Lambda(p^k)=\log p$, we have \begin{align*} \sum_{n\leq x}\Lambda(n)^2 = \sum_{p^k \leq x,\ p \text{ prime},\ k\geq 1}(\log p)^2. \end{align*} For each prime $p\leq x$, the number of integers $k\geq 1$ with $p^k\leq x$ is at most $\log x/\log p$. Therefore \begin{align*} \sum_{p^k \leq x,\ p \text{ prime},\ k\geq 1}(\log p)^2 \leq \sum_{p\leq x} \frac{\log x}{\log p}(\log p)^2 = \log x \sum_{p\leq x}\log p. \end{align*} Since $\log p \leq \log x$ for every prime $p\leq x$ and there are at most $\lfloor x \rfloor$ such primes, we obtain \begin{align*} \sum_{p\leq x}\log p \leq x\log x. \end{align*} This gives the weaker bound $\sum_{n\leq x}\Lambda(n)^2 \leq x(\log x)^2$. To get the stated $x\log x$ bound, split the prime powers into first powers and higher powers. For $k=1$, \begin{align*} \sum_{p\leq x}(\log p)^2 \leq \log x \sum_{p\leq x}\log p. \end{align*} Using the elementary Chebyshev estimate $\sum_{p\leq x}\log p \leq C_1x$ for an absolute constant $C_1>0$, we get \begin{align*} \sum_{p\leq x}(\log p)^2 \leq C_1x\log x. \end{align*} (citing a result not yet in the wiki: Chebyshev Estimate for the First Chebyshev Function) For $k\geq 2$, the condition $p^k\leq x$ implies $p\leq x^{1/2}$. The number of exponents $k\geq 2$ satisfying $p^k\leq x$ is at most $\log x/\log p$, so \begin{align*} \sum_{p^k \leq x,\ p \text{ prime},\ k\geq 2}(\log p)^2 \leq \log x\sum_{p\leq x^{1/2}}\log p. \end{align*} Applying the same Chebyshev estimate with $x^{1/2}$ in place of $x$ gives \begin{align*} \sum_{p^k \leq x,\ p \text{ prime},\ k\geq 2}(\log p)^2 \leq C_1x^{1/2}\log x. \end{align*} Since $x\geq 2$, we have $x^{1/2}\leq x$, and hence \begin{align*} \sum_{n\leq x}\Lambda(n)^2 \leq 2C_1x\log x. \end{align*} Thus the estimate holds with $C_0:=2C_1$. [/step] [step:Combine the two estimates] From the first step, \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} |E_\Lambda(x;q,a)|^2 \leq (x+Q^2)\sum_{n\leq x}\Lambda(n)^2. \end{align*} From the second step, $\sum_{n\leq x}\Lambda(n)^2 \leq C_0x\log x$, where $C_0>0$ is absolute. Substitution gives \begin{align*} \sum_{q \leq Q} \sum_{a \bmod q,\ \gcd(a,q)=1} |E_\Lambda(x;q,a)|^2 \leq C_0(x+Q^2)x\log x. \end{align*} Renaming $C:=C_0$ proves the asserted estimate with an absolute implicit constant. [/step]