Discrete Mathematics/Analytic Number Theory

Introduction

Analytic Number Theory is the application of Analysis to Number Theoretic Problems. A quick overview of some portions of Analytic Number theory follow.

Zeta function

The zeta function, defined by

$\zeta (s)=\sum _{n=1}^{\infty }n^{-s}$

for real values of s > 1, plays a central role in the theory. It converges absolutely when s > 1. It satisfies the Euler product formula,

$\zeta (s)=\prod _{p}{\frac {1}{1-p^{-s}}}$

where the product is over all prime numbers. To see this, note that multiplying the series definition by 1-2^-s and rearranging terms(which is justified since the series converges absolutely) eliminates the even terms, i.e. $(1-2^{-s})(1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{5^{s}}}+\ldots )=(1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{5^{s}}}+\ldots )-({\frac {1}{2^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{6^{s}}}+{\frac {1}{8^{s}}}+{\frac {1}{10^{s}}}+\ldots )=(1+{\frac {1}{3^{s}}}+{\frac {1}{5^{s}}}+{\frac {1}{7^{s}}}+\ldots )$

Likewise after multiplying by 1-3^-s all remaining terms with n divisible by 3 are eliminated. After repeating this process for all primes it follows that

$\zeta (s)\prod _{p}\left(1-p^{-s}\right)=1$

since 1 is the only number not divisible by a prime and thus only the n=1 term is left. Solving for ζ(s) immediately gives the Euler product formula.

Dirichlet series

The series for the zeta function is a special case of a Dirichlet series. A Dirichlet series is one of the form

$\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}$ where $a$ is a sequence of complex numbers.

Many important arithmetic functions, $a$, have the properties that $a(1)=1$ and $a(m)a(n)=a(mn)$ when $m$ and $n$ are relatively prime. Such functions are called multiplicative.

For a multiplicative function $a$, its associated Dirichlet series may be expressed as an Euler product by

$\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}=\prod _{p}\sum _{k=0}^{\infty }{\frac {a(p^{k})}{p^{ks}}}$.

This can be shown in a manner similar to the proof for the zeta function.

A completely multiplicative function is one where $a(m)a(n)=a(mn)$ even if $m$ and $n$ are not relatively prime.

For a completely multiplicative function, the Euler product simplifies to

$\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}=\prod _{p}{\frac {a(p)}{1-p^{-s}}}$.

The product of two Dirichlet series is given by the formula

$\left(\sum _{k=1}^{\infty }{\frac {a(k)}{k^{s}}}\right)\left(\sum _{m=1}^{\infty }{\frac {b(m)}{m^{s}}}\right)=\sum _{n=1}^{\infty }{\frac {(a*b)(n)}{n^{s}}}$

where $a*b$ represents the Dirichlet convolution of $a$ and $b$, which is defined by

$(a*b)(n)=\sum _{d|n}a(d)b\left({\frac {n}{d}}\right)$

Some important Dirichlet series include:

${\frac {\zeta ^{\prime }(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }{\frac {\Lambda (n)}{n^{s}}}$

${\frac {1}{\zeta (s)}}=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}$

$\zeta (s-k)=\sum _{n=1}^{\infty }{\frac {n^{k}}{n^{s}}}$

and

$\zeta (s)\zeta (s-k)=\sum _{n=1}^{\infty }{\frac {\sigma _{k}(n)}{n^{s}}}$

Big-Oh notation

Many problems involve functions that are incredibly difficult to work with exactly, but where the rate of growth of the function, rather than its exact values, is of primary concern. Because of this a notation (often called "Big-Oh notation") was invented.

The notation

$f(x)=O(g(x))$

is used to denote that, for a sufficiently large number $x_{0}$, there exists a number $C$ such that

$\left|f(x)\right|\leq Cg(x)$ for all $x>x_{0}$.

The expression $f(x)=g(x)+O(h(x))$ denotes that $f(x)-g(x)=O(h(x))$.

Dirichlet's Theorem

One of the first results proven with analytic number theory was Dirichlet's Theorem which states that for any 2 relatively prime integers a & b, there are infinitely many values of k for which ak+b is a prime number. The proof involves complex-valued functions of the set of integers called Dirichlet characters defined by the properties that χ(n) depends only on its residue class modulo a, χ(n) is completely multiplicative, and χ(n) = 0 iff a and n are not relatively prime. The principal character χ₀ is defined to be 1 when a & n are relatively prime and 0 otherwise. It is easy to show that χ₀ is a character. It can be shown that the number of characters is equal to φ(a). It can also be shown that the sum of the values of χ(n) over all characters χ is equal to φ(a) if $n\equiv 1{\pmod {a}}$ and 0 otherwise. The Dirichlet series corresponding to a character is called a Dirichlet L-series and is traditionally denoted by L(s,χ). It is simple to show that L(1,χ₀) diverges. Through a complicated argument it is shown that L(1,χ) converges and is nonzero if χ is nonprincipal. The function

$\sum _{p\equiv b{\pmod {a}}}{\frac {1}{p}}=\sum _{\chi }{\frac {L(1,\chi )}{\chi (b)}}+O(1)$

must diverge since L(1,χ₀)/χ(b) diverges and the other terms all converge. Since all terms of the sum on the left are finite its divergence implies there are an infinite number of terms of this sum and thus infinitely many primes of the form ak+b.

Riemann zeta function & xi function

The zeta function introduced above(the Euler zeta function) converges for all values of s such that Re(s)>1. The Riemann zeta function is defined as the analytic continuation of the Euler zeta function, and is defined for all complex values of s except s=1. Where both functions exist, the Euler and Riemann zeta functions are equal by definition. It can be shown that if the xi function is defined by

$\xi (s)={\frac {1}{2}}s(s-1)\Gamma ({\frac {s}{2}})\pi ^{-{\frac {s}{2}}}\zeta (s)$

then ξ(s)=ξ(1-s). This is the symmetric form of the famous functional equation for the Riemann zeta function, and provides a convenient way of computing the Riemann zeta function when Re(s)<1.

The series definition of Euler's zeta function shows that ζ(s) has no zeroes for Re(s)>1. It can also be shown that the zeta function has no zeroes with Re(s)=1. The functional equation shows that for integer values of n, ζ(-2n)=0, and any other zeroes lie in the so-called critical strip, 0<Re(s)<1. The well-known Riemann Hypothesis states that all nontrivial zeros(i.e. those not of the form s=-2n), have Re(s)=1/2. It is easy to show that the zeroes of the xi function are exactly the nontrivial zeroes of the zeta function.

Hadamard product formula

The Hadamard product formula states that functions with certain properties(in particular the xi function) are close enough to a polynomial that they may be represented in terms of a product over the zeroes. For the xi function the Hadamard product formula states that

$\xi (s)=e^{A+Bs}\prod _{\rho }(1-{\frac {s}{\rho }})$

for certain values of A and B, where the product is over the zeroes of ξ(s). This formula is one of the main reasons the zeroes of the xi function, and thus the zeta function, are of considerable importance.

Distribution of squarefree numbers

Let S(x) denote the number of squarefree numbers less than or equal to x. To evaluate this function we begin by counting all integers less than or equal to x. Then we subtract those that are divisible by 4, those divisible by 9, those divisible by 25, and so on. We then have removed numbers with 2 repeated prime factors twice those with 3 repeated prime factors 3 times and so on. To remedy the repetition of the numbers with 2 repeated prime factors we add on the number of integers less than or equal to x divisible by 36, those divisible by 100, those divisible by 225 and so on. We have now reincluded those with 3 repeated prime factors so we uncount them. Continuing this process gives

$S(x)=\sum _{n^{2}\leq x}\mu (n)\left\lfloor {\frac {x}{n^{2}}}\right\rfloor =\sum _{n^{2}\leq x}\mu (n){\frac {x}{n^{2}}}+O({\sqrt {x}})={\frac {x}{\zeta (2)}}+O({\sqrt {x}})={\frac {6}{\pi ^{2}}}x+O({\sqrt {x}})$

In addition to information about how common squarefree numbers are this estimate gives information on how they are distributed. For example to show that there are infinitely many pairs of consecutive squarefree numbers(i.e. that differ by 1) assume there are only finitely many such pairs. Then there is some x₀ such that all such pairs lie below x₀. Then for n > x₀ n and n+1 cannot be squarefree, and thus at most half the integers above x₀ are squarefree, or more precisely,

$S(x)\leq {\frac {1}{2}}(x-x_{0})+x_{0}+1={\frac {x}{2}}+O(1)$

but since ${\frac {6}{\pi ^{2}}}>{\frac {1}{2}}$ this contradicts the estimate obtained earlier, thus there are infinitely many pairs of consecutive squarefree numbers.

The estimate also shows that for large enough x, there is at least one squarefree number between x^3 and (x+1)^3. To see this, note that the number of squarefree numbers in that range is

$S\left((x+1)^{3}\right)-S(x^{3})={\frac {6}{\pi ^{2}}}\left((x+1)^{3}-x^{3}\right)+O\left({\sqrt {(x+1)^{3}}}\right)+O\left({\sqrt {x^{3}}}\right)={\frac {18}{\pi ^{2}}}x^{2}+O\left(x^{3 \over 2}\right)$

which is at least one for sufficiently large x.

To do: Add mention of prime number theorem and sieve methods, as well as Dirichlet inversion