• MAT417H1: Analytic Number Theory
• Math 675 Analytic Theory of Numbers lsa.umich.edu

The sieve of Eratosthenes

The inclusion-exclusion principle or the Möbius inversion formula can in theory be used to calculate $\pi(x)$. For sufficiently large $x$, let us write
$$P=\prod_{p \leqslant \sqrt{x}} p$$
then an integer $n, \sqrt{x}<n \leqslant x$, is a prime number if, and only if, $(n, P)=1$. Thus we may write
$$\pi(x)-\pi(\sqrt{x})+1=\sum_{n \leqslant x} \delta((n, P))=\sum_{d \mid P} \mu(d)\left\lfloor\frac{x}{d}\right\rfloor .$$
At this stage, if we content ourselves with estimating $\lfloor x / d\rfloor$ using $x / d+O(1)$, we obtain
$$\pi(x)-\pi(\sqrt{x})+1=x \prod_{p \leqslant \sqrt{x}}\left(1-\frac{1}{p}\right)+O\left(2^{\pi(\sqrt{x})}\right) .$$
By Mertens’ formula, the main term in this estimate equals
$$\left{2 \mathrm{e}^{-\gamma}+o(1)\right} x / \ln x$$
but Chebyshev’s estimates show that the error term is larger than any power of $x$.

Brun’s combinatorial sieve

The sieve of Eratosthenes is based on the identity
$$\mu * \mathbf{1}=\delta \text {. }$$
Brun’s idea consists in introducing two auxiliary functions $\mu_1, \mu_2$, satisfying
$$\mu_1 * \mathbf{1} \leqslant \delta \leqslant \mu_2 * 1$$
and vanishing sufficiently often so that the number of terms in the resulting formula analogous to (4.1) is not prohibitive.

Brun’s initial choice, leading to what is customarily referred to in the literature as Brun’s pure sieve, is the following.

(Brun). Denote by $\chi_t$ the characteristic function of the set of integers $n$ such that $\omega(n) \leqslant t$. Then, for any integer $h \geqslant 0$, the functions defined by
$$\mu_i(n):=\mu(n) \chi_{2 h+2-i}(n) \quad(i=1,2)$$
satisfy the inequalities.
Proof. Since $\mu_i * 1(n)$ only depends on the squarefree kernel of $n$, it is enough to consider the case when $\mu(n)^2=1$. If $\omega(n)=k$, then, for each $r, 0 \leqslant r \leqslant k$, it is clear that $n$ has exactly $\left(\begin{array}{l}k \ r\end{array}\right)$ divisors $d$ such that $\omega(d)=r$. We can thus write, for any given $t \geqslant 0$,
$$\mu \chi_t * \mathbf{1}(n)=\sum_{d \mid n, \omega(d) \leqslant t} \mu(d)=\sum_{r \leqslant t}(-1)^r\left(\begin{array}{l} k \ r \end{array}\right)=(-1)^t\left(\begin{array}{c} k-1 \ t \end{array}\right),$$
where the last equality is easily obtained by induction on $t$.

Application to twin primes

Here we illustrate the results of the previous paragraph with Brun’s theorem on twin primes.

It is obvious that the difference between two consecutive odd primes must be at least 2 . When it is exactly 2 , we say that these primes are twins, such as ${3,5},{5,7},{11,13},{17,19},{29,31}$, etc. A famous conjecture asserts the existence of infinitely many twin primes.
Let us write
$$\mathcal{J}:={p: p+2 \text { is prime }} \quad \text { and } \quad J(x):=|\mathcal{J} \cap[1, x]| .$$
On the basis of an analytic approach, and in agreement with a heuristic probabilistic calculation, Hardy \& Littlewood (1922) conjectured that
$$J(x) \sim 2 \prod_{p>2}\left(1-\frac{1}{(p-1)^2}\right) \frac{x}{(\ln x)^2} \quad(x \rightarrow \infty) .$$
By Brun’s pure method, we establish the following result.
Theorem 4.5 (Brun). As $x$ tends to infinity, we have
$$J(x) \ll x\left(\frac{\ln _2 x}{\ln x}\right)^2$$

下面是一些经典的Quadratic Reciprocity题目

Problem 1. If $p \equiv 1$ (4), show that $p$ is the sum of two squares; i.e., $p=a^2+b^2$ with $a, b \in \mathbb{Z}$. (Hint: $p=\alpha \beta$ with $\alpha$ and $\beta$ being nonunits in $\mathbb{Z}[i]$. Take the absolute value of both sides and square the result.) This important result was discovered by Fermat.
Problem 2. An integer is called a biquadratic residue modulo $p$ if it is congruent to a fourth power. Using the identity $x^4+4=\left((x+1)^2+1\right)\left((x-1)^2+1\right)$ show that -4 is a biquadratic residue modulo $p$ iff $p \equiv 1$ (4).
Problem 3. Suppose that $f$ is such that $b \equiv a f(p)$. Show that $f^2 \equiv-1(p)$ and that $2^{(p-1) / 4} \equiv$ $f^{a b / 2}(p)$.
Problem 4. Show that $x^4 \equiv 2(p)$ has a solution iff $p$ is of the form $A^2+64 B^2$.

BS equation代写