Brun–Titchmarshの不等式

そのような $n$ は $n=c+km$（$k$ は整数）と書け、条件は $k$ が半開区間 $(\alpha,\alpha+y/m]$（$\alpha:=(x-c)/m$）に入ることである。この区間の整数の個数は $\lfloor\alpha+y/m\rfloor-\lfloor\alpha\rfloor$ で、$\lfloor u\rfloor$ と $u$ の差は $[0,1)$ にあるから、個数と $y/m$ の差の絶対値は $1$ 未満である。$\square$

$q/\varphi(q)=\prod_{p\mid q}(1-1/p)^{-1}=\prod_{p\mid q}(1+p^{-1}+p^{-2}+\cdots)$ であり、平方因子をもたない $d$ について $1/\varphi(d)=\prod_{p\mid d}(p-1)^{-1}=\frac1d\prod_{p\mid d}(1+p^{-1}+p^{-2}+\cdots)$ である。$\gcd(d,q)=1$ のとき、2 つを掛けて展開すると
$$ \frac{q}{\varphi(q)}\cdot\frac1{\varphi(d)}=\sum_{n}\frac1n $$
となる。右辺の $n$ は、$n=dm$ で $m$ の素因数がすべて $d$ か $q$ の素因数であるような正の整数を動く。
正の整数 $n\le D$ を 1 つとり、$d$ を「$n$ を割り $q$ を割らない素数」の積とすると、$d$ は平方因子をもたず、$\gcd(d,q)=1$、$d\le n\le D$ で、$n/d$ の素因数は $d$ か $q$ の素因数である。逆に $n$ が $d'$ の展開に現れれば、$n$ を割り $q$ を割らない素数はちょうど $d'$ の素因数なので $d'=d$ である。よって各 $n\le D$ は、左辺を $d$ について足した和の展開にちょうど 1 回現れ、ほかの項は正である。よって
$$ \frac{q}{\varphi(q)}\sum_{d}\frac1{\varphi(d)}\ge\sum_{n\le D}\frac1n\ge\int_1^{\lfloor D\rfloor+1}\frac{dt}{t}\ge\log D $$
である。$\square$

$Y:=y/q$、$D:=\sqrt Y/\log Y$ とおき、$Y$ は $D\ge2$ となるほど大きいとする。
篩の設定． $\mathcal A$ を、$x< n\le x+y$、$n\equiv a\pmod q$ をみたす整数 $n$ を並べた列、$\mathcal P$ を $D$ 以下で $q$ を割らない素数の集合とし、$P:=\prod_{p\in\mathcal P}p$、$X:=Y$、$g(d):=1/d$ とおく。$g$ は乗法的で $0< g(p)< 1$ である。$d\mid P$ なら $\gcd(d,q)=1$ なので、中国剰余定理 により「$n\equiv a\pmod q$ かつ $d\mid n$」は $n$ が法 $qd$ の 1 つの剰余類に入ることと同値である。lem-bt-count により、その個数 $A_d$ は $y/(qd)=Xg(d)$ との差が $1$ 以下で、$\lvert r_d\rvert\le1$ である。
主要な項． $h(p)=g(p)/(1-g(p))=1/(p-1)$ なので、平方因子をもたない $d\mid P$ について $h(d)=1/\varphi(d)$ である。$d\le D$ が平方因子をもたず $\gcd(d,q)=1$ なら、$d$ の素因数は $D$ 以下で $q$ を割らないので $d\mid P$ である。よって $G(D)$ は lem-bt-phi の左辺に等しく、$G(D)\ge\frac{\varphi(q)}{q}\log D$ である。
素数を篩に入れる． $(x,x+y]$ に含まれる素数 $p\equiv a\pmod q$ のうち、$p\le D$ のものは $D$ 個以下である。$p>D$ なら、$p$ は $\mathcal P$ のどの素数でも割り切れないので $\gcd(p,P)=1$ であり、$S(\mathcal A,\mathcal P)$ に数えられる。Selbergの篩 の定理「Selbergの篩」の 3 の最初の不等式で、剰余項の和は $D$ 以下の $d_1,d_2$ の組の個数で押さえられ、$D^2$ 以下である。よって
$$ \pi(x+y;q,a)-\pi(x;q,a)\le D+\frac{X}{G(D)}+D^2\le\frac{y}{\varphi(q)\log D}+2D^2 $$
である（$D\ge1$ なので $D\le D^2$）。
$D$ の選び方． $2D^2=\dfrac{2Y}{(\log Y)^2}=\dfrac{2y}{q(\log Y)^2}\le\dfrac{2y}{\varphi(q)(\log Y)^2}$、$\log D=\frac12\log Y-\log\log Y$ なので
$$ \pi(x+y;q,a)-\pi(x;q,a)\le\frac{y}{\varphi(q)\log Y}\Bigl(\frac1{\frac12-\frac{\log\log Y}{\log Y}}+\frac2{\log Y}\Bigr) $$
である。$Y\to\infty$ で括弧の中は $2$ に収束するので、$Y\ge Y_0$ で $2+\varepsilon$ 以下になり、かつ $D\ge2$ となる $Y_0$ がとれる。$Y_0$ は $\varepsilon$ だけで決まる。最後の主張は $x$ を $0$、$y$ を $x$ とした場合である。$\square$

thm-bt-main を $\varepsilon=1$ で使い、その $Y_0$ を $Y_0>e$ にとる。$y/q\ge Y_0$ なら $C=3$ でよい。$1< Y:=y/q< Y_0$ なら、lem-bt-count により類に入る整数は $Y+1< 2Y$ 個以下なので、$\varphi(q)\le q$ と $\log Y< \log Y_0$ から
$$ \pi(x+y;q,a)-\pi(x;q,a)< \frac{2y}{q}=\frac{2\log Y\cdot y}{q\log Y}\le\frac{2\log Y_0\cdot y}{\varphi(q)\log(y/q)} $$
である。$C:=\max\{3,2\log Y_0\}$ とすればよい。$\square$

$x/q\ge x^{1-\vartheta}$ なので、$x^{1-\vartheta}\ge Y_0$（$Y_0$ は thm-bt-main の $\varepsilon$ に対するもの）となる $x$ では定理が使える。$\log(x/q)\ge(1-\vartheta)\log x$ を代入すればよい。$\square$

thm-bt-main で $q=1$、$a=0$ とする。$\varphi(1)=1$ で、すべての整数が法 $1$ で $0$ に合同である。$\square$

定数． $u_\ell:=1/(\ell(\ell-1))\le\frac12$ で $\sum_\ell u_\ell\le\sum_{n\ge2}\frac1{n(n-1)}=1$ なので、無限積は収束して正の値 $A$ をもつ。$z\ge2$ について $A_z:=\prod_{\ell\le z}(1-u_\ell)$ とおくと、$A_z\ge A$、$A_z\to A$（$z\to\infty$）である。
有限個の $\ell$ で篩う． $z$ を固定し、$P_z:=\prod_{\ell\le z}\ell$、$\pi_z(x)$ を「$x$ 以下の素数 $p$ で、$\ell\le z$ のどの $\ell$ についても $\ell^2\nmid p-1$ となるもの」の個数とする。素数 $p$ について、$\ell^2\mid p-1$ となる $\ell\le z$ の積を $g$ とすると、$P_z$ の約数 $d$ について「$d^2\mid p-1$」は「$d\mid g$」と同値である（$d$ は平方因子をもたず、異なる $\ell$ の $\ell^2$ は互いに素）。Möbius関数 の定理「約数にわたる和」により $\sum_{d\mid g}\mu(d)$ は $g=1$ のとき $1$、それ以外で $0$ なので
$$ \pi_z(x)=\sum_{p\le x}\ \sum_{\substack{d\mid P_z\\ d^2\mid p-1}}\mu(d)=\sum_{d\mid P_z}\mu(d)\,\pi(x;d^2,1) $$
である。各 $d$ について $\gcd(1,d^2)=1$ なので、算術級数の素数定理 の定理「算術級数の素数定理」により $\pi(x;d^2,1)/\pi(x)\to1/\varphi(d^2)$ である。和は有限個の項なので
$$ \frac{\pi_z(x)}{\pi(x)}\to\sum_{d\mid P_z}\frac{\mu(d)}{\varphi(d^2)}=\prod_{\ell\le z}\Bigl(1-\frac1{\varphi(\ell^2)}\Bigr)=A_z $$
である（$\varphi(d^2)=\prod_{\ell\mid d}\varphi(\ell^2)$、$\varphi(\ell^2)=\ell(\ell-1)$）。
上から． $p-1$ が平方因子をもたなければ $\pi_z(x)$ に数えられるので $\pi^\ast(x)\le\pi_z(x)$ であり、$\limsup\pi^\ast(x)/\pi(x)\le A_z$ である。
下から． $\pi_z(x)$ に数えられて $\pi^\ast(x)$ に数えられない $p$ では、ある $\ell>z$ について $\ell^2\mid p-1$ なので
$$ \pi^\ast(x)\ge\pi_z(x)-\sum_{\ell>z}\pi(x;\ell^2,1) $$
である。$\ell^2\ge x$ の項は $0$ である（$p=1+k\ell^2$、$k\ge1$ なら $p>\ell^2\ge x$）。$z< \ell\le x^{1/4}$ の項には cor-bt-uniform を区間 $(0,x]$、法 $\ell^2$ で使う。$x/\ell^2\ge\sqrt x$ なので $\log(x/\ell^2)\ge\frac12\log x$ であり、
$$ \sum_{z< \ell\le x^{1/4}}\pi(x;\ell^2,1)\le\frac{2Cx}{\log x}\sum_{n>z}\frac1{n(n-1)}=\frac{2Cx}{\lfloor z\rfloor\log x} $$
である。$x^{1/4}< \ell< \sqrt x$ の項では、類に入る $n\le x$ は $n=1+k\ell^2$（$k\ge1$）なので個数は $x/\ell^2$ 以下であり、和は $x\sum_{n>x^{1/4}}\frac1{n(n-1)}\le x/\lfloor x^{1/4}\rfloor$ 以下である。
素数定理 により $\pi(x)\log x/x\to1$ で、$x/(\lfloor x^{1/4}\rfloor\pi(x))\to0$ なので、
$$ \liminf_{x\to\infty}\frac{\pi^\ast(x)}{\pi(x)}\ge A_z-\frac{2C}{\lfloor z\rfloor} $$
である。上からと下からの評価で $z\to\infty$ とすれば、$\pi^\ast(x)/\pi(x)\to A$ である。$\square$