In analytic number theory, an arithmetic function is simply a function from the natural numbers
to the real or complex numbers. (One occasionally also considers arithmetic functions taking values in more general rings than
or
, as in this previous blog post, but we will restrict attention here to the classical situation of real or complex arithmetic functions.) Experience has shown that a particularly tractable and relevant class of arithmetic functions for analytic number theory are the multiplicative functions, which are arithmetic functions
with the additional property that
whenever are coprime. (One also considers arithmetic functions, such as the logarithm function
or the von Mangoldt function, that are not genuinely multiplicative, but interact closely with multiplicative functions, and can be viewed as “derived” versions of multiplicative functions; see this previous post.) A typical example of a multiplicative function is the divisor function
that counts the number of divisors of a natural number . (The divisor function
is also denoted
in the literature.) The study of asymptotic behaviour of multiplicative functions (and their relatives) is known as multiplicative number theory, and is a basic cornerstone of modern analytic number theory.
There are various approaches to multiplicative number theory, each of which focuses on different asymptotic statistics of arithmetic functions . In elementary multiplicative number theory, which is the focus of this set of notes, particular emphasis is given on the following two statistics of a given arithmetic function
:
- The summatory functions
of an arithmetic function
, as well as the associated natural density
(if it exists).
- The logarithmic sums
of an arithmetic function
, as well as the associated logarithmic density
(if it exists).
Here, we are normalising the arithmetic function being studied to be of roughly unit size up to logarithms, obeying bounds such as
,
, or at worst
A classical case of interest is when is an indicator function
of some set
of natural numbers, in which case we also refer to the natural or logarithmic density of
as the natural or logarithmic density of
respectively. However, in analytic number theory it is usually more convenient to replace such indicator functions with other related functions that have better multiplicative properties. For instance, the indicator function
of the primes is often replaced with the von Mangoldt function
.
Typically, the logarithmic sums are relatively easy to control, but the summatory functions require more effort in order to obtain satisfactory estimates; see Exercise 6 below.
If an arithmetic function is multiplicative (or closely related to a multiplicative function), then there is an important further statistic on an arithmetic function
beyond the summatory function and the logarithmic sum, namely the Dirichlet series
for various real or complex numbers . Under the hypothesis (43), this series is absolutely convergent for real numbers
, or more generally for complex numbers
with
. As we will see below the fold, when
is multiplicative then the Dirichlet series enjoys an important Euler product factorisation which has many consequences for analytic number theory.
In the elementary approach to multiplicative number theory presented in this set of notes, we consider Dirichlet series only for real numbers (and focusing particularly on the asymptotic behaviour as
); in later notes we will focus instead on the important complex-analytic approach to multiplicative number theory, in which the Dirichlet series (4) play a central role, and are defined not only for complex numbers with large real part, but are often extended analytically or meromorphically to the rest of the complex plane as well.
Remark 1 The elementary and complex-analytic approaches to multiplicative number theory are the two classical approaches to the subject. One could also consider a more “Fourier-analytic” approach, in which one studies convolution-type statistics such as
as
for various cutoff functions
, such as smooth, compactly supported functions. See this previous blog post for an instance of such an approach. Another related approach is the “pretentious” approach to multiplicative number theory currently being developed by Granville-Soundararajan and their collaborators. We will occasionally make reference to these more modern approaches in these notes, but will primarily focus on the classical approaches.
To reverse the process and derive control on summatory functions or logarithmic sums starting from control of Dirichlet series is trickier, and usually requires one to allow to be complex-valued rather than real-valued if one wants to obtain really accurate estimates; we will return to this point in subsequent notes. However, there is a cheap way to get upper bounds on such sums, known as Rankin’s trick, which we will discuss later in these notes.
The basic strategy of elementary multiplicative theory is to first gather useful estimates on the statistics of “smooth” or “non-oscillatory” functions, such as the constant function , the harmonic function
, or the logarithm function
; one also considers the statistics of periodic functions such as Dirichlet characters. These functions can be understood without any multiplicative number theory, using basic tools from real analysis such as the (quantitative version of the) integral test or summation by parts. Once one understands the statistics of these basic functions, one can then move on to statistics of more arithmetically interesting functions, such as the divisor function (2) or the von Mangoldt function
that we will discuss below. A key tool to relate these functions to each other is that of Dirichlet convolution, which is an operation that interacts well with summatory functions, logarithmic sums, and particularly well with Dirichlet series.
This is only an introduction to elementary multiplicative number theory techniques. More in-depth treatments may be found in this text of Montgomery-Vaughan, or this text of Bateman-Diamond.
— 1. Summing monotone functions —
The most fundamental estimate regarding the equidistribution of the natural numbers is the trivial bound
for any , which reflects the evenly spaced nature of the natural numbers. One also has the variant
also valid for any . (But note that if the summation is not over the natural numbers, but is also allowed to contain
, then the sum
(or
) is no longer
when
is small, and one should instead revert to (6).)
We have the following generalisation of (6) to summation of monotone functions:
Lemma 2 (Quantitative integral test) Let
be real numbers, and let
be a monotone function. Then
Note that monotone functions are automatically Riemann integrable and Lebesgue integrable, so there is no difficulty in defining the integral appearing above.
Proof: By replacing with
if necessary, we may assume that
is non-decreasing. By rounding up
and rounding down
, we may assume that
are integers. We have
and similarly
and the claim follows.
Thus, for instance, one has
for any (a weak form of Stirling’s formula, discussed in this previous blog post), and more generally one has
for all and some polynomial
with leading term
. (The remaining terms in
may be computed explicitly, but for our purposes it will not be essential to know what they are.)
Remark 3 If
are not required to be integers, then one cannot improve substantially on the size of the error term
, as one can see by considering what happens if
or
transitions from being infinitesimally smaller than an integer to infinitesimally larger than that integer. But if
are integer and one assumes more differentiability on
, one can get more precise control on the error term in Lemma 2 using the Euler-Maclaurin formula; see e.g. Exercise 7 below. However, we will usually not need these more refined estimates here. In any event, one can get even better control on the error term if one works with smoother sums such as (5) with
smooth, thanks to tools such as the Poisson summation formula. See this previous blog post for some related discussion.
In the converse direction, ifis highly oscillatory then there is usually no simple relationship between the sum
and the integral
; consider for instance the example
, in which the sum grows linearly in
but the integral stays bounded.
Lemma 2 combines well with the following basic lemma.
Lemma 4 (Cauchy sequences converge) Let
,
and
be functions such that
as
. Then the following are equivalent:
- (i) One has
for all
.
- (ii) There exists a constant
such that
for all
. In particular,
.
The quantity
in (ii) is unique; it is also real-valued if
are real-valued.
If in additionas
, then when (ii) holds,
converges conditionally to
.
Exercise 5 Prove Lemma 4.
We now give some basic applications of these lemmas. If is a real number not equal to
, then from Lemma 2 we have
for , and hence by Lemma 4, there is a real number
with
for all . In the case
, we conclude that the sum
is absolutely convergent, and
however for this identity is technically not true, since the sum on the right-hand side is now divergent using the usual conventions for infinite sums. (The identity can however be recovered by using more general interpretations of infinite sums; see this previous blog post.) The function
is of course the famous Riemann zeta function.
For the case, we again see from Lemma 2 that
for , and thus there exists a real number
such that
for . The constant
is known as Euler’s constant (or the Euler-Mascheroni constant), and has a value of
.
Exercise 6 Let
be an arithmetic function. If the natural density
of
exists and is equal to some complex number
, show that the logarithmic density
also exists and is equal to
. (Hint: first establish the identity
.) An important counterexample to the converse claim is given in Exercise 7 below.
Exercise 7 Let
be real numbers, and let
be a continuously differentiable function. Show that
(Hint: compare
with
. One may first wish to consider the case when
are integers, and deal with the roundoff errors when this is not the case later.) Conclude that if
is a non-zero real number, that the function
has logarithmic density zero, but does not have a natural density. (Hint: for the latter claim, argue by contradiction and consider sums of the form
.)
Remark 8 The above exercise demonstrates that logarithmic density is a cruder statistic than natural density, as it completely ignores oscillations by
, whereas natural density is very sensitive to such oscillations. As such, controlling natural density of some arithmetic functions (such as the von Mangoldt function
) often boils down to determining to what extent such functions “conspire”, “correlate”, or “pretend to be”
for various real numbers
. This fact is a little tricky to discern in the elementary approach to multiplicative number theory, but is more readily apparent in the complex analytic approach, which we will discuss in later notes.
Exercise 9 For non-negative natural numbers
, show that
for all
and some polynomial
with leading term
.
Exercise 10
Exercise 11 Show rigorously that for any non-negative integer
and real
, the Riemann zeta function
is
-times differentiable at
and one has
(There are several ways to justify the term-by-term differentiation in the first equation; one way is to instead establish a term-by-term integration formula and then apply the fundamental theorem of calculus. Another is to use Taylor series with remainder to control the error in Newton quotients. A third approach is to use complex analysis. You may find Exercise 7 to be useful for some of these approaches.)
— 2. Mertens’ theorems —
We can now use the above estimates to gain some useful initial estimates on the primes. Our starting point will be the fundamental theorem of arithmetic, which asserts that every natural number can be factored as
where is the number of times
divides
(this number will be
for all but finitely many primes). Taking logarithms, we obtain
or equivalently
(Here we use the standard notation in analytic number theory of using to denote the assertion that
divides
.) We can rearrange this as
where is the von Mangoldt function, defined to equal
when
is a power
of a prime
for some
, and zero otherwise. Roughly speaking, this function is the indicator function of the primes
weighted by the logarithm function; indeed, we have
except when is a power
of a prime
for some
. This latter situation occurs quite rarely, and so as a first approximation one can heuristically view the left and right-hand sides of (21) as being morally the same.
To control some error terms, we first use some elementary number theory to give a crude but useful upper bound.
Proposition 12 (Chebyshev upper bound) We have
for all
. In particular, specialising
to primes we have
Proof: We use the following slick (but perhaps somewhat unmotivated) argument. By telescoping series it suffices to establish the bound
for all natural numbers . We first consider the contribution of those
that are powers
of a prime
for some
. One has
, so there are at most
such primes, and each prime contributes at most
to the above sum; since
, we may discard this contribution and reduce to showing that
We will achieve this through an inspection of the binomial coefficient
Observe that if is a prime with
, then
divides
but not
, and so divides
. Taking logarithms, we conclude that
From the binomial theorem we have , and the claim follows.
By manipulating the basic identity (20) in several ways, we can start getting more control on various sums of , and hence over the primes. We begin with
Theorem 13 (First Mertens theorem) We have the estimate
for all
.
Proof: If we sum (20) over all , we have
By (8), the left-hand side is . As for the right-hand side, we can rewrite the conditions
by the change of variables
as
and
, to rearrange the right-hand side as
Applying (6), we conclude that
and so (22) follows from Proposition 12.
Now we prove (23). From the definition of the von Mangoldt function, one has
We crudely bound for
. Since
, we obtain
and the claim follows (23) from (22).
Exercise 14 (Chebyshev’s theorem) Show that there exists an absolute constant
such that there are
primes in
for all sufficiently large
. Conclude in particular that
.
From this we can obtain a sharper form of Theorem 19, controlling logarithmic sums of the primes:
Theorem 15 (Second Mertens’ theorem) One has
for
and some absolute constant
. Similarly, one has
for
and some absolute constant
.
The constant has no particular significance in applications, but the constant
can be usefully computed: see (34) below.
Proof: We just prove the first claim, as the second is similar (and can be deduced from the first by a modification of the argument used to deduce (23) from (22)). One could proceed here using summation by parts, but we will argue using an essentially equivalent method, based on the fundamental theorem of calculus. By Lemma 4, it suffices to show that
for both go to infinity. From the fundamental theorem of calculus we have
for all , and thus
From (23) one has
for all ; since
and
the claim follows.
This leads to a useful general formula for computing various slowly varying sums over primes:
- (i) For any fixed
, show that
as
.
- (ii) If
is a fixed compactly supported, Riemann integrable function, show that
as
.
- (iii) If
is a fixed natural number and
is a fixed compactly supported, Riemann integrable function, show that
as
.
- (iv) Obtain analogues of (i)-(iii) when the sum over primes
are replaced by the sum over integers
, but with factors of
replaced by
(with the convention that this expression vanishes at
).
Remark 17 An alternate way to phrase the above exercise is that the Radon measures
on
converge in the vague topology to the absolutely continuous measure
in the limit
, where
denotes the Dirac probability measure at
. Similarly for the Radon measures
To put this another way, the Radon measures
or
behave like Lebesgue measure on dyadic intervals such as
for fixed
and large
. This is weaker than the prime number theorem that we will prove in later notes, which basically asserts the same statement but on the much smaller intervals
. (Statements such as the Riemann hypothesis make the same assertion on even finer intervals, such as
.) See this previous blog post for some examples of this Radon measure perspective, which we will not emphasise in this set of notes.
Exercise 18 (Smooth numbers) For any
, let
denote the set of natural numbers less than
which are
-smooth, in the sense that they have no prime factors larger than
.
- (i) Show that for any fixed
, one has
where the Dickman function
is defined by the alternating series
(note that for any given
that only finitely many of the summands are non-zero; one can also view the
term as the
term of the summation after carefully working out what zero-dimensional spaces and empty products evaluate to). Hint: Use the inclusion-exclusion principle to remove the multiples of
from
for each prime
. This is a simple example of a sieve, which we will study in more detail in later notes.
- (ii) (Delay-differential equation) Show that
is continuous on
, continuously differentiable except at
, equals
for
and obeys the equation
for
. Give a heuristic justification for this equation by considering how
varies with respect to small perturbations of
.
- (iii) (Wirsing integral equation) Show that
for all
, or equivalently that
Give a heuristic justification for this equation by starting with a
-smooth number
and considering a factor
, where
is a prime factor of
chosen at random with probability
(if
occurs
times in the prime factorisation of
).
- (iv) (Laplace transform) Show that
for all
.
To proceed further we will start using the Riemann zeta function (13) that made an appearance in the previous section. We again use the fundamental theorem of arithmetic (19), this time to observe the Euler product identity
for any (where we allow both sides to be infinite). Indeed, by (19), the truncated version
of the right-hand side is the product of those for which
is the product of powers of primes up to
, by exponents that are at most
, and then by sending
and
to infinity via the monotone convergence theorem we obtain the claim. For
, the left-hand side converges to
, and the geometric series
converges to
, thus
for all .
The formula (26) gives a fundamental relationship between the Riemann zeta function and the primes that can be manipulated and exploited in a number of ways. For instance, from (11) we now have
for .
Taking logarithms, we thus have
when (note that
is clearly at least one). The logarithm here on the left-hand side is not so desirable, but we may remove it by using the Taylor expansion
and noting that is absolutely convergent, to conclude that
when is bounded. Taking
, and using monotone convergence, we recover Euler’s theorem
, but (28) gives more precise information. For instance we get a “cheap” version of Mertens’ second theorem, already anticipated by Euler:
Theorem 19 (Cheap second Mertens’ theorem) We have
for
.
Proof: We use a device known as Rankin’s trick to compare a Dirichlet series with a natural or logarithmic mean. Namely, observe that whenever , one has
, so in particular
. This gives us the ability to insert or remove factors of
in sums up to
while only losing constant factors; in particular
The claim now follows from (28).
While this bound is worse (by a factor of ) than what one could get in Theorem 15, Rankin’s trick will end up being useful later in some other contexts (again, in applications where losing a factor such as
is acceptable).
We can get more mileage out of (27) by differentiating in . Formally differentiating in
, we arrive at the identity
Exercise 20 Derive (29) rigorously. (Hint: For fixed
and small
, expand
using Taylor series with remainder.)
Using the geometric series expansion
and recalling the von Mangoldt function, we thus obtain the important identity
for the Dirichlet series of , and for all
. (In fact this identity will hold for a wider range of
, but we will address this in later notes.) For comparison, a Taylor expansion of (27) gives the closely related identity
Indeed, (30) is essentially the derivative of (31) in .
Exercise 21 Give an alternate proof of (30) based on (20). (Hint: expand out the product of
with
and collect terms.)
Remark 22 We have seen that the von Mangoldt function
obeys at least three useful identities: (30), (31) and (20). (Not surprisingly, these identities are closely related to each other: (30) is basically the derivative of (31), which is the Dirichlet series transform of (20).) It is because of these identities (and further related identities which we will see in later posts) that the von Mangoldt function is an extremely convenient proxy for the prime numbers in analytic number theory. Indeed, many question about primes in analytic number theory are most naturally tackled by converting them to a statement about the von Mangoldt function, by adding or subtracting the contribution of prime powers
for
, which are typically of significantly lower order), in order to access identities such as (30), (31) or (20).
for (note the claim is trivial if
is large).
This gives us a weaker version of Theorem 13:
Exercise 23 (Cheap first Mertens’ theorem) Use (32) and Rankin’s trick to show that
for all
.
Thus far, the estimates coming from the Euler product of the zeta function have led to worse bounds than what the first and second Mertens’ theorems give us. But now we can combine the two together. Recall from (11), (31) that
for . We can compare this against (25) by a variant of the Rankin trick. Namely, if we apply (33) with
for some large
, one obtains
and thus on subtracting (25)
For any fixed , we see from Exercise 16 that
From Mertens’ first theorem, we have
while from Mertens’ second theorem and dyadic decomposition of we have
Taking limits as , we conclude that
for any , hence on sending
and then
we obtain
We can compute this limit explicitly:
Lemma 24 (Exponential integral asymptotics) For sufficiently small
, one has
Proof: We start by using the identity to express the harmonic series
as
or on summing the geometric series
Since , we thus have
making the change of variables , this becomes
As ,
converges pointwise to
and is pointwise dominated by
. Taking limits as
using dominated convergence and (14), we conclude that
Since
the claim follows.
Exercise 25 Show that
Conclude that if
is the Gamma function, defined for
by the formula
then one has
.
This implies (using (10)) that
Taking exponentials, we conclude
Theorem 26 (Third Mertens’ theorem) We have
as
.
Because of this theorem, the factors and
frequently arise in analytic prime number theory. We give two examples of this below.
Exercise 27 Let
be the Dickman function from Exercise 18. Show that
.
Exercise 28 For any natural number
, define the Euler totient function
of
to be the number of natural numbers less than
that are coprime to
, or equivalently
is the order of the multiplicative group
of
. Show that
as
. ({Hint: treat the contribution of small primes
and large primes
separately.) Show that
cannot be replaced here by any larger quantity. (This result is due to Landau.)
— 3. The number of divisors —
We now consider the asymptotics of the divisor function
that counts the number of divisors of a given natural number . Informally: how many divisors does one expect a typical large number
to have? Remarkably, the answer turns out to depend on exactly on what one means by “typical”.
The first basic observation to make is that is a multiplicative function:
whenever
are coprime, since every divisor of
can be uniquely expressed as the product of a divisor of
and a divisor of
. The same argument has an important generalisation: if
are multiplicative functions, then the Dirichlet convolution
, defined by
is also multiplicative. The multiplicativity of the divisor function then follows from the identity
since the constant function is clearly multiplicative. For comparison, the identity (20) can be written in this notation as
where is the logarithm function. The operation of Dirichlet convolution is basically a special case of the more familiar Fourier-analytic notion of convolution, if one views the natural numbers
as a subset of the group
of non-zero rational numbers with multiplication as the group law. In particular, it is commutative, associative, and bilinear. Fourier analysis teaches us that it is often profitable to understand convolution via the Fourier transform; in this context, the counterpart of the Fourier transform becomes the operation of forming a Dirichlet series, which we will see more of later on.
Exercise 29 Show that the Dirichlet convolution of two multiplicative functions is again multiplicative.
Returning to the divisor function, we begin with a crude bound:
Lemma 30 (Divisor bound) We have
as
. Equivalently, we have
for any fixed
.
Proof: Let be fixed. Observe that for any prime power
, we have
. In particular, we see that
whenever
is sufficiently large depending on
, and
is a natural number. For the remaining values of
, we have
. By the multiplicativity of
, we thus have
as required.
Exercise 31 Obtain the sharper bound
for all
. (Hint: first establish that
for any
by performing the proof of Lemma 30 more carefully, then optimise in
.) It was in fact established by Wigert (in 1907) that one in fact has
as
, and that the constant
cannot be replaced by any smaller constant.
Now we consider the mean value of . We will take advantage of the general identity
for Dirichlet convolutions, and thus
In fact we have already implicitly used this identity to prove Mertens’ first theorem (Theorem 13). A similar argument gives the variant
We can use this to control the summatory function and logarithmic sum of the divisor function. For instance, by applying (36) with followed by (6), we have
and hence by (14)
(We will improve the control on the error term here later in this section.) Similarly, from (37) followed by (14) we have
and thus by (16) and a brief calculation
for some quadratic polynomial with leading term
. Comparing these bounds with (9) and (8), we arrive at the heuristic
behaves (as a rough first approximation) like
“on the average”.
Remark 32 One can justify the heuristic
by the following non-rigorous probabilistic argument: for a typical large number
, each number
would be expected to divide
with probability about
; since
, the “expected value” of
should thus be about
. We will continue this heuristic argument later in this set of notes.
We now give a supporting justification for the heuristic . Given any arithmetic function
, define the Dirichlet series
by the formula
whenever the series is absolutely convergent (in some cases we will be able to extend the domain of definition of this series to other choices of , but we will address this point later). For instance, we have from definition (13) of the Riemann zeta function that
when , and more generally from (18)
for any natural number and
, where we use
to denote the logarithm function
. The identities (29), (30) similarly become
for .
We record some basic properties of the Dirichlet series transform , under a mild hypothesis on
:
Exercise 33 (Basic properties of Dirichlet series) Suppose that
are arithmetic functions that are of at most subpolynomial growth in the sense that
as
, or equivalently that
for all
.
- (i) (Existence and uniqueness) Show that
are well-defined for
, and that
for all
if and only if
. (Hint: if
, first show that
and
agree at
, then proceed inductively.)
- (ii) (Multiplication by logarithm transforms to differentiation) Show that
is differentiable for
with
(note that this generalizes (40), and also is consistent with (41), (42)).
- (iii) (Convolution transforms to multiplication) Show that
is of subpolynomial and that
for all
. Use this and (20) to obtain an alternate proof of (30). We will make heavier use of (44) in later notes. Note that (44) also helps explain the commutative and associative nature of Dirichlet convolution.
- (iv) (Euler product) If
is multiplicative, show that
for any
(in particular, all products and sums here are absolutely convergent). If
is completely multiplicative, which means that
for all
(not necessarily coprime), simplify this to
- (v) (Dirichlet series and logarithmic density) If the logarithmic density of
exists and is equal to
, show that
as
, or in other words that
as
. (Hint:
.)
- (vi) (Leibniz rule) Establish the Leibniz rule
and comment on how this is compatible with parts (i)-(iii) of this exercise.
From Exercise 33(iii) we have in particular that
so in particular from (11) we have
when . We can now use Rankin’s trick to upper bound the logarithmic sums
:
This is of course compatible with the more precise asymptotic (39).
Exercise 34 (Cheap upper bound on multiplicative functions) Let
be a real number, and let
be a multiplicative function such that
for all primes
, and
for all primes
and
. Show that
is of at most subpolynomial growth, and
for
.
It is then natural to ask whether Dirichlet series methods can also confirm the bound (38). In the spirit of Rankin’s trick, a first attempt would be to exploit the simple inequality
and use ether (46) or (39), but this gives the very weak upper bound
which is significantly inferior to (38). The problem is that (48) is very inefficient when is much smaller than
. To do better, there is a standard rearrangement trick that moves much of the “mass” of a summatory function
to smaller values of
, effectively increasing the cutoff
and so replacing (48) with a less inefficient comparison. To describe this rearrangement trick, we return to the fundamental identity (20) and rearrange it as
which allows us to rewrite an arbitrary summatory function for some
as
For the latter sum, we write and interchange summations to obtain (after replacing
with
) the rearrangement identity
The expression in parentheses can be viewed as a weighted version of , with the weight tending to be larger for small
than for large
. Because of this reweighting, if one applies Rankin’s trick to bound the sum on the right-hand side, one can often obtain an upper bound on
that recovers the loss of
that would occur if one applied Rankin’s trick directly. For instance, suppose we take
. Since
, we conclude from (39) that
Now we turn to the sum . We first consider the contribution when
are coprime, in which case
. We observe that each prime
contributes at most
to this sum, while the primes
contribute
through all the powers of
less than
. By the Chebyshev bound (Proposition 12), we thus have
and so the contribution of the coprime case is by (39).
It remains to deal with the case when are not coprime; thus
and
for some prime
, some
, and some
. We can then bound this contribution to
by
We have , so by (49) we may bound this expression by
Performing the sums, this is
and on putting everything together we conclude that , which is consistent with (38) (though the bounds are weaker).
Exercise 35 (Cheap upper bound for summatory functions) With
as in Exercise 34, show that
for
.
We continue the analysis of the divisor function. Even though behaves like
on the average, it can fluctuate to be much larger or much smaller than this value. For instance,
equals
when
is prime, and when
is odd,
is twice as large as
, even though
and
are roughly the same size. A further hint of the irregularity of distribution can be seen by considering the
moments
and
of
for natural numbers
. The function
is multiplicative with
for every prime
. From Exercise 34 and Exercise 35 we have the upper bounds
for all , suggesting that
behaves like
on average. This may seem at first glance to be incompatible with the heuristic that
behaves like
on the average, but what is happening here is that
can occasionally be much larger than
, which does not significantly affect the mean of
, but does affect higher moments with
. (Continuing Remark 32, the issue here is that the events “
divides
” can be highly correlated with each other as
varies, due to common factors between different choices of
.) In fact, the typical value (in the sense of median, rather than mean) of
is not
or
, but is in fact
. See Section 4 below.
We can be more precise on the mean behaviour of , by establishing the following variant of Exercise 34.
Theorem 36 (Mean values of divisor-type multiplicative functions) Let
be a natural number, and let
be a multiplicative function obeying the estimates
for all primes
, and
for all primes
and all
. Let
denote the singular series
Note from Taylor expansion that
so
is finite (though it may vanish, if one of its factors vanishes), with
.
- (i) If
, then one has
for all
.
- (ii) If
, we have
for
.
- (iii) If
, one has
for
.
Note that the case of this proposition gives (a slightly weaker form of) the above estimates for
, since in that case
. Comparing with (9), (16), (18) we see that
behaves approximately like
on the average for
. The hypotheses on this theorem may be relaxed somewhat; see Exercise 38 below.
Proof: For brevity we omit the dependence of implicit constants on . We begin with (i). If
, then from (45) and crude bounds we have
, which suffices, so we will assume that
is sufficiently close to
. From (45) we have
where . For
close to
, we see from applying the chain rule and Taylor expansion that
and hence
where
Since is convergent, we conclude that
and the claim follows from (26).
To prove (ii) we induct on . First we establish the base case
of (ii). From (45) we have
so it suffices to show that
But from (45) we see that
(for instance), and the claim follows.
Now suppose that and the claim (ii) has already been proven for
. We let
be the multiplicative function with
for primes and
, then one easily verifies that
. Note that
satisfies the same hypotheses as
, but with
replaced by
. A brief calculation shows that
and thus . From (37) one has
and thus by induction hypothesis
From Lemma 2 we have
and
and the claim (ii) follows.
Finally, we prove (iii). Let ; if
, we assume inductively that (iii) is established for
. Let
be as before. From (36) one has
and thus by (6)
From (ii) we have
The error term can be treated by the induction hypothesis when
, giving the claim. When
, we instead use the Rankin trick and bound
and use (45) to bound as before, giving the claim.
Thus for instance we have
for any , where
is the quantity
Among other things, this shows that can be larger than any fixed power of
for arbitrarily large
; compare with Lemma 30.
A more accurate description of the distribution of is that
for
is asymptotically distributed in the limit
like a gaussian random variable with mean and variance comparable to
; see Section 4 below.
Exercise 37 Let
be the arithmetic function defined by setting
when
is squarefree (that is,
is not divisible by any perfect square other than
) and zero otherwise; the reason for the notation
will be given later. Show that
and
for
. Thus, the square-free numbers have natural and logarithmic density
. It can be shown by a variety of methods that
, although we will not use this fact here. The error term
may also be improved significantly (as we shall see when we turn to sieve-theoretic methods).
Exercise 38 The purpose of this exercise is to give an alternate derivation of parts (ii) and (iii) of Theorem 36 that does not rely so strongly on
being an integer; it also allows
to only be close to
on average, rather than in the pointwise sense. The arguments here are from Appendix A.2 Friedlander-Iwaniec, which are in turn based on this paper of Wirsing.
- (i) Let
be as in Theorem 36, and define
. By using (50) with
replaced by
, establish the integral equation
for all
, and deduce that
for all
and some
independent of
. Then use part (i) of Theorem 36 to deduce that
, thus establishing part (ii) of Theorem 36.
- (ii) Assume the following form of the prime number theorem:
for all
. By using (50) for
, establish part (iii) of Theorem 36.
- (iii) Extend Theorem 36 to the case when
is real rather than integer (replacing factorials by Gamma functions as appropriate), and (52) is replaced by
for all
. (For part (ii) of Theorem 36, one can weaken (52) further to
.)
Exercise 39 Show that
and
for any
. (Hint: the first estimate can be used to derive the second.) Conclude that the proportion of pairs
of natural numbers in the square
which are coprime converges to
as
.
Exercise 40 Let
be a prime, and let
be a residue class mod
. Show that
when
, and
when
. Give an intuitive explanatino as to why the second estimate is roughly twice as large as the first.
We now present a basic method to improve upon the estimate (38), namely the Dirichlet hyperbola method. The point here is that the error term in (6) is much stronger for large than for small
, so one would like to rearrange the proof of (38) so that (6) is only used in the former case and not the latter. To do this, we decompose
where and
, so that
may be decomposed as
Actually, it is traditional to rearrange this a bit as the identity
This decomposition is convenient for improving (38) for two reasons. Firstly, is supported on
and thus makes no contribution to
. At the other extreme,
is supported in
and so the restriction
may be removed here, simplifying the sum substantially:
For the final sum , we use (36) and (6) as before, to conclude that
By (14), we thus obtain an improved version of (38):
Remark 41 The Dirichlet hyperbola method may be visualised geometrically as follows, in a fashion that explains the terminology “hyperbola method”. The sum
can be interpreted as the number of lattice points (that is to say, elements of
) lying underneath the hyperbola
. The proof of (38) basically proceeded to count these lattice points by summing up the contribution of each column separately; this was an efficient process for the columns close to the
-axis, but led to relatively large error terms for columns far away from the
-axis. Symmetrically, one could proceed by summing by rows, which is efficient for rows close to the
-axis, but not far from that axis. The hyperbola method splits the difference between these two counting procedures, counting rows within
of the
-axis and columns within
of the
-axis, and then removing one copy of the square
to correct for it being double-counted. The estimation of this lattice point problem can be made more precise still by more sophisticated decompositions and approximations of the hyperbola, but we will not discuss this problem (known as the Dirichlet divisor problem) here.
From an algebraic perspective, it is the identity (54), decomposinginto Dirichlet convolutions of expressions with good spatial support properties, that is the key to the successful application of the hyperbola method. In later posts we will encounter more sophisticated identities that decompose various arithmetic functions (such as the von Mangoldt function
) into similar convolutions of spatially localised expressions. Unfortunately these identities are not as easy to visualise geometrically as the hyperbola method identity, as the corresponding geometric picture often takes place in three or higher dimensions.
Exercise 42 Define the third divisor function
by
, or equivalently
. Show that
for all
and some polynomial
with leading term
. (Note that Theorem 36(iii) only gives
; one needs a three-dimensional version of the hyperbola method to get the better error term. Hint: Decompose
at the threshold
. If one is having difficulty figuring out exactly what identity to use, try working backwards, by writing down all the relevant convolutions (e.g.
) that look tractable, and then do some elementary linear algebra to express
in terms of all the expressions that you know how to estimate well.) The
term can be improved further (for instance, the logarithmic factor can be removed), but this requires more sophisticated methods than the ones given above.
Exercise 43 State and prove an extension of the previous exercise to the
divisor function
for
, defined as the Dirichlet convolution
of
copies of
.
Remark 44 The error terms we have been able to obtain for sums involving
are significantly superior to those we can obtain for
by similar methods. The general reason for this is that it is relatively easy to control the convolution
of two functions
that are themselves well understood, but it is significantly more difficult to try to control the deconvolution
of a convolution
by a factor
even when one has good understanding of the latter two functions
. From a Fourier-analytic perspective, the problem is that dividing one Fourier transform by another can create singularities, whereas multiplying two Fourier series cannot. This can become problematic when the latter Fourier transform vanishes; in our arithmetic context, this corresponds to zeroes of the Dirichlet series
. As such, we will see the location of the zeroes of Dirichlet series such as the Riemann zeta function play an extremely important role in later posts. However, the elementary approach cannot easily access this information directly; as Mertens’ theorems demonstrate, some control on the deconvolution is still possible, but it is not as satisfactory as it could be.
— 4. The number of prime factors (optional) —
Given a natural number , we use
to denote the number of prime factors of
(not counting multiplicity), and
to denote the number of prime factors of
(counting multiplicity). Thus we can write
as divisor sums
We can ask what the mean values of and
are. We start with the estimation of
We can rearrange this sum (cf. (36)) as
which by (6) is
so by Theorem 15 (and crudely bounding by
, as we will not need additional accuracy here) gives
for (say). Thus we see that for
, one expects
to have about
prime factors on the average.
Now we look at the second moment
If we expand this out directly, we get
which we can rearrange as
where is the least common multiple of
, that is to say
if
and
if
. Here we run into a serious problem, which is that
can be significantly less than
, in which case the estimate
is horrendously inefficient (the error term is larger than the main term, which is always a bad sign). One could fix this by using the trivial estimate when
. But there is another cheap trick one can use here, due to Turán, coming from the fact that a given natural number
can have at most
prime factors that are larger than, say,
. Thus we can approximate the divisor sum (57) by a truncated divisor sum:
One can then run the previous argument with the truncated divisor sum and avoid the problem of dipping below
. Indeed, on squaring we see that
and hence (by (58))
for . Rearranging and using (6) as before, we obtain
The contribution of the error may be crudely bounded by
, which can easily be absorbed into the error term. The diagonal case
also contributes
thanks to Theorem 15. We conclude that
and thus by a final application of Theorem 15
We can combine this with (58) to give a variance bound:
To interpret this probabilistically, we see that if we pick uniformly at random, then the random quantity
will have mean
and standard deviation
. In particular, by Chebyshev’s inequality, we expect
to have
prime factors most of the time.
Remark 45 The strategy of truncating a divisor sum to obtain better control on error terms (perhaps at the expense of some inefficiency in the main terms) is one of the core techniques in sieve theory, which we will discuss in later notes.
The same estimates are true for :
Exercise 46
- (i) Show that
for
, and conclude that
- (ii) Show that
for all natural numbers
.
From the above exercise and Chebyshev’s inequality, we now know the typical number of prime factors of a large number, a fact known as the Hardy-Ramanujan theorem:
Theorem 47 (Hardy-Ramanujan theorem) Let
be an asymptotic parameter going to infinity, and let
be any quantity depending on
that goes to infinity as
. Let
be a natural number selected uniformly at random from
. Then with probability
,
has
distinct prime factors, and
repeated prime factors (counting multiplicity, thus
counts as
repeated prime factors). In particular,
has
prime factors counting multiplicity.
This already has a cute consequence with regards to the multiplication table:
Proposition 48 (Multiplication table bound) At most
of the natural numbers up to
can be written in the form
with
natural numbers.
In other words, for large , the
multiplication table only uses a small fraction of the numbers up to
. This simple-sounding fact is surprisingly hard to prove if one does not use the simple argument provided below.
Proof: Pick natural numbers uniformly at random. By the Hardy-Ramanujan theorem, with probability
,
and
will each have
prime factors counting multiplicity. Hence with probability
,
will have
prime factors counting multiplicity. But by a further application of the Hardy-Ramanujan theorem, the set of natural numbers up to
with this property has cardinality
. Thus all but
of the products
with
are contained in a set of cardinality
, and the claim follows.
Remark 49 In fact, the cardinality of the
multiplication table is known to be comparable to
with
; see this paper of Ford.
Exercise 50 (Typical number of divisors) Let
be an asymptotic parameter going to infinity. Show that one has
for all but
of the natural numbers
less than
. (Hint: first establish the bounds
.)
In fact, one can describe the distribution of or
more precisely, a fact known as the Erdös-Kac theorem:
Exercise 51 (Erdös-Kac theorem) (This exercise is intended for readers who are familiar with probability theory, and more specifically with the moment method proof of the central limit theorem, as discussed in this previous set of notes.) Let
be an asymptotic parameter going to infinity, and let
denote the truncated divisor sum
Define the quantity
thus by Mertens’ theorem
- (i) Show that
for all
.
- (ii) For any fixed natural number
, show that
where the quantity
is defined to equal zero when
is odd, or
when
is even.
- (iii) If
is drawn uniformly at random from the natural numbers up to
, show that the random variable
converges in distribution to the standard normal distribution
in the limit
. (You will need something like the moment continuity theorem from Theorem 4 of these notes.)
- (iv) Obtain the same claim as (iii), but with
replaced by
.
Informally, we thus have the heuristic formula
for , where
is distributed approximately according to a standard normal distribution. As in Exercise 50, this leads to a related heuristic formula
for the number of divisors. This helps reconcile (though does not fully explain) the discrepancy between the typical (or median) value of , which is
, and the mean (or higher moments) of
, which is of the order of
or
, as it suggests that
is in fact significantly larger than its median value of
with a relatively high probability. (Unfortunately, though, the heuristic (59) is not very accurate at the very tail end of the distribution when
is extremely large, and one cannot recover the correct exponent of the logarithm in (51), for instance, through a naive application of this heuristic.)
Remark 52 Another rough heuristic to keep in mind is that a “typical” number
less than
would be expected to have
divisors in any dyadic block
between
and
, and
prime divisors in any hyper-dyadic block
between
and
. For instance, for any fixed
, one should have
divisors in the interval
, but only
prime divisors. Typically, the only prime divisors that occur with multiplicity will be quite small (of size
). Note that such heuristics are compatible with the fact that
has mean
and that
and
both have mean
. One can make these heuristics more precise by introducing the Poisson-Dirichlet process, as is done in this previous blog post, but we will not do so here. The study of the distribution of factors of “typical” large natural numbers is a topic sometimes referred to as anatomy of integers. Interestingly, there is a strong analogy between this problem and the problem of studying the distribution of cycles of “typical” large permutations; see for instance this article of Granville for further discussion.
Exercise 53 Let
be a natural number. Show that for sufficiently large
, the number of natural numbers up to
that are the products of exactly
distinct primes is
.
— 5. Mobius inversion and the Selberg symmetry formula —
In Section 2, we used the identity , together with elementary estimates on
and
, to deduce various estimates on the von Mangoldt function
. Another way to extract information about
from this identity is to “deconvolve” or “invert” the operation of convolution to
. This can be achieved by the basic tool of Möbius inversion, which we now discuss. We first observe that the Kronecker delta function
, defined by
, is an identity for Dirichlet convolution, thus
for any arithmetic function . Since Dirichlet convolution is associative and commutative, this implies that if we can find an arithmetic function
with the property that
then any formula of the form may be inverted to the equivalent form
, a fact known as the Möbius inversion formula. It is then a routine matter to locate such a function
:
Exercise 54 Define the Möbius function
by setting
when
is the product of
distinct primes for some
, and
otherwise. Show that
is the unique arithmetic function that obeys (60).
Observe that is a multiplicative function that obeys the trivial bound
for all . Furthermore,
is
precisely when
is square-free, and zero otherwise, so the notation here is consistent with that in Exercise 37.
One can express the Möbius inversion formula as the assertion that
for any compactly supported arithmetic function . This already reveals that
must exhibit some cancellation beyond the trivial bound (61):
Lemma 55 (Weak cancellation for
) For any non-negative integer
, we have
for all
and some polynomial
with leading term
if
(and
if
).
Proof: We may of course take .
First suppose that . We apply (62) with
to conclude that
Since , we conclude from (61) that
and the case of (63) follows.
Now suppose inductively that , and that the claim has already been proven for smaller values of
. We apply (62) with
to conclude that
By (17) we have
for some polynomial with leading term
. Inserting this asymptotic and using the induction hypothesis to handle all the lower order terms of
, and (61) to handle the error term, we conclude that
for some polynomial of degree at most
. By (15) the error term is
, and the claim follows.
Exercise 56 Sharpen the
case of the above lemma to
, for any
.
From Möbius inversion we can write in terms of
:
Since , we have the general Leibniz-type identity
Since , we can obtain the alternative representation
by multiplying (60) by then applying (66), (65).
Using these identities and Lemma 55, we can recover many of the estimates in Section 2:
Exercise 57 (Alternate proof of Chebyshev and Mertens bounds) Use (65) and Lemma 55 to reprove the estimates
and
If one has a little bit more cancellation in the Möbius function, one can do better:
Theorem 58 (Equivalent forms of the prime number theorem) The following three statements are logically equivalent:
- (i) We have
as
.
- (ii) We have
as
.
- (iii) We have
as
.
In later notes we will prove that the claims (i), (ii), (iii) are indeed true; this is the famous prime number theorem. This result also illustrates a general principle, that one route to distribution estimates of the primes is via distribution estimates on the Möbius function, which can sometimes be a simpler object to study (for instance, the Möbius function is bounded in magnitude by , whereas the von Mangoldt function can grow logarithmically).
Proof: We use some arguments of Diamond. We first show that (i) implies (ii). From (67) and Möbius inversion we have
By (36) we thus have
For any fixed , we may use (i) to write
as
when
is sufficiently large, and
otherwise. From this, (61), and the
case of (63) we thus have
when is large enough. By (15), (61) we have
summing and then dividing by , we obtain (ii) since
is arbitrary.
Now we show that (ii) implies (iii). We start with the identity (64), which we write as
Let be a small fixed quantity. For
,
decreases through a fixed set of values, and from (ii) we conclude that
Meanwhile, since , we see from (61) that
Combining all three inequalities and dividing by , we conclude that
replacing by
, then sending
to zero, we obtain (iii).
To prove that (iii) implies (ii), we observe the identity
For any , we have from (iii) that
if
is sufficiently large depending on
, and
otherwise; thus
if is large enough, and the claim follows.
To conclude the theorem, it suffices to show that (ii) and (iii) jointly imply (i). From (65), (36) we have
Meanwhile, since , we have from (36) that
From (6) we have . It will thus suffice to show that
Let be a small fixed quantity. Arguing as in the implication of (iii) from (ii), we see from (ii) that
Next, we see from (8), (56) that
From Lemma 2 we have
and so from (iii) and (61) we conclude that
Summing this with (69) and then sending to zero, we obtain the claim.
Exercise 59 (Further reformulations of the prime number theorem) Show that the statements (i)-(iii) in the above theorem are also equivalent to the following statements:
- (iv) The number of primes less than or equal to
is
as
.
- (v) The
prime number
is equal to
as
.
Unfortunately it is not so easy to actually obtain the required cancellation of the Möbius function , and to obtain the desired asymptotics for
. However, one can do better if one works with the higher-order von Mangoldt functions
, defined by setting
for all . Thus
is the usual von Mangoldt function, and from (66), (68) we easily obtain the recursive identity
for . Among other things, this implies by induction that the
are non-negative, and are supported on those natural numbers that have at most
distinct prime factors. We have the following asymptotic for the summatory functions of
:
Proposition 60 (Summatory function of
) For any
, we have
for all
, and for some polynomial
of leading term
.
For , the error term here is comparable to the main term, and we obtain no improvement over the Chebyshev bound (Proposition 12). However, the estimates here become more useful for
. For an explicit formula for the polynomials
, together with sharper bounds on the error term, see this paper of Balazard.
Proof: From (70), (36) we have
By (9) we have
for some polynomial with leading term
. The claim then follows from (63), using (61), (15) to control the error term.
The case of this proposition is known as the Selberg symmetry formula:
Among other things, this gives an upper bound that comes within a factor of two of the prime number theorem:
Corollary 61 (Cheap Brun-Titchmarsh theorem) For any
, one has
Using the methods of sieve theory, we will obtain a stronger inequality, known as the Brun-Titchmarsh inequality, in later notes. This loss of a factor of two reflects a basic problem in analytic prime number theory known as the parity problem: estimates which involve only primes (or more generally, numbers whose number of prime factors has a fixed parity) often lose a factor of two in their upper bounds, and are trivial with regards to lower bounds, unless some non-trivial input about prime numbers is somehow injected into the argument. We will discuss the parity problem in more detail in later notes.
Proof: From the Selberg symmetry formula we have
(since ). From (71) we have the pointwise bound
, thus
By Proposition 12 and dyadic decomposition we have
and the claim follows.
With some additional argument of a “Fourier-analytic” flavour (or using arguments closely related to Fourier analysis, such as Tauberian theorems or Gelfand’s theory of Banach algebras), one can use the Selberg symmetry formula to derive the prime number theorem; see for instance these previous blog posts for examples of this. However, in this course we will focus instead on the more traditional complex-analytic proof of the prime number theorem, which highlights an important connection between the distribution of the primes and the zeroes of the Riemann zeta function.
Exercise 62 (Cheap Brun-Titchmarsh, again) Show that for any
, the number of primes between
and
is at most
.
Exercise 63 (Golomb identity) Let
be coprime natural numbers. Show that
Exercise 64 (Diamond-Steinig identity) Let
. Show that
can be expressed as a linear combination of convolutions of the form
, where
appears
times and
are non-negative integers with
and
. Identities of this form are due to Diamond and Steinig.
— 6. Dirichlet characters —
Now we consider the following vaguely worded question: how many primes are there in a given congruence class ? For instance, how many primes are there whose last digit is
(i.e. lie in
)?
If the congruence class is not primitive, that is to say that
and
share a common factor, then clearly the answer is either zero or one, with the latter occurring if the greatest common divisor
of
and
is a prime
which is congruent to
modulo
. So the interesting case is when
is primitive, that is to say that it lies in the multiplicative group
of primitive congruence classes.
In this case, we have the fundamental theorem of Dirichlet:
Theorem 65 (Dirichlet’s theorem, Euclid form) Every primitive congruence class
contains infinitely many primes.
For a small number of primitive congruence classes, such as or
, it is possible to prove Dirichlet’s theorem by mimicking one of the elementary proofs of Euclid’s theorem, but we do not know of a general way to do so; see this paper of Keith Conrad for some further discussion. For instance, there is no proof known that there are infinitely many primes that end in
that does not basically go through most of the machinery of Dirichlet’s proof (in particular introducing the notion of a Dirichlet character). Indeed, it looks like the problem of finding a new proof of Dirichlet’s theorem is an excellent test case for any proposed alternative approach to studying the primes that does not go through the standard approach of analytic number theory (cf. Remark 2 from the announcement for this course).
In fact, Dirichlet’s arguments prove the following stronger statement, generalising Euler’s theorem (Theorem 2 from this set of notes):
Theorem 66 (Dirichlet’s theorem, Euler form) Let
be a primitive residue class. Then the sum
is divergent.
There is a more quantitative form, analogous to Mertens’ theorem:
Theorem 67 (Dirichlet’s theorem, Mertens form) Let
be a primitive residue class. Then one has
for any
, where the Euler totient function
is defined as the order of the multiplicative group
.
Exercise 68 Let
be a primitive residue class. Use Theorem 67 to show that
as
for some quantity
, thus giving Theorem 66. (Hint: adapt the proof of Theorem 15.)
If one tries to adapt one of the above proofs of Mertens’ theorem (or Euler’s theorem) to this setting, one soon runs into the problem that the function is not multiplicative:
. To resolve this issue, Dirichlet used some Fourier analysis to express
in terms of completely multiplicative functions, known as Dirichlet characters.
We first quickly recall the Fourier analysis of finite abelian groups:
Theorem 69 (Fourier transform for finite abelian groups) Let
be a finite abelian group (which can be written additively or multiplicatively). Define a character on
to be a homomorphism
to the unit circle
of the complex numbers, and let
be the set of characters. Then
. Furthermore, given any function
, one has a Fourier decomposition
for all
, where the Fourier coefficients
are given by the formula
for all
.
Proof: Let be the
-dimensional complex Hilbert space of functions
with inner product
. Clearly any character
is a unit vector in this space. Furthermore, for any two characters
, we may shift the
variable by any shift
and conclude that
for any ; in particular, we see that if
, then
. Thus
is an orthonormal system in
. To complete the proof of the theorem, it thus suffices to show that this orthonormal system is complete, that is to say that the characters span
.
Each shift generates a unitary shift operator
, defined by setting
(if the group
is written multiplicatively). These shifts collectively form what is known as the regular representation of
. These operators all commute with each other, so by the spectral theorem they may all be simultaneously diagonalised by an orthonormal basis of joint eigenvectors. It is easy to see that these eigenvectors are characters (up to scaling), and so the characters span
as required.
See this previous post for a more detailed discussion of the Fourier transform on both finite and infinite abelian groups. We remark that an alternate way to establish that the characters of span is to use the classification of finite abelian groups to express
as the product of cyclic groups, at which point one can write down the characters explicitly.
Define a Dirichlet character of modulus to be a function
of the form
where is a character of
. Thus, for instance, we have the principal character
of modulus . Another important example of a Dirichlet character is the quadratic character
to a prime modulus
, defined by setting
to be
when
is a non-zero quadratic residue modulo
,
if
is a quadratic residue modulo
, and zero if
is divisible by
. (There are quadratic characters to composite moduli as well, but one needs to define them using the Kronecker symbol.) One can also easily verify that the product of two Dirichlet characters is again a Dirichlet character (even if the characters were initially of different modulus).
A technical remark: we consider two Dirichlet characters to be equal if they are equal as functions, that is to say that
for all
. As such, it is possible for a Dirichlet character to have multiple moduli: if
is a character of modulus
, it is also a character of modulus
for any natural number
whose prime factors also divide
. As such, it is slightly inaccurate to talk about “the” modulus of a Dirichlet character (though one could always work with the minimal modulus of a Dirichlet character, if desired), but this ambiguity will not cause much difficulty in practice.
Dirichlet characters of modulus
are completely multiplicative (thus
for all
, not necessarily coprime) and periodic of period
(thus
for all
). From Theorem 43 we see that there are exactly
Dirichlet characters of modulus
, and from (73) one has the Fourier inversion formula
From Mertens’ theorem we have
since the contribution of those for which
is not coprime to
is easily seen to be
(
must be a power of a prime dividing
in these cases). Thus, Theorem 67 follows from
Theorem 70 (Dirichlet’s theorem, character form) Let
be a non-principal Dirichlet character of modulus
. Then
for any
.
To prove this theorem, we use the “deconvolution” strategy. Observe that for any completely multiplicative function , one has
for any arithmetic functions . In particular, from (35) one has
Theorem 70 is seeking control on the logarithmic sums of , so it is natural to first control the logarithmic sums of
and
. To do this we use a somewhat crude lemma (which can be viewed as a twisted version of the quantitative integral test in Lemma 2):
Lemma 71 (Twisted quantitative integral test) Let
be a non-principal character of modulus
, and let
be an arithmetic function that is monotone on an interval
. Then
Proof: Without loss of generality we may assume that is monotone non-increasing. By rounding
up and
down to the nearest multiple of
, we may assume that
are multiples of
, then the left-hand side may be split into the sum of expressions of the form
. As
is non-principal, it is orthogonal to the principal character, and in particular
. Thus we may write
as
, which by the trivial bound
and monotonicity may be bounded by
. The claim then follows from telescoping series.
From this lemma we obtain the crude upper bounds
for any . (Strictly speaking, the function
is not monotone decreasing for
, but clearly we may just delete this portion of the sum from (75) without significantly affecting the estimate.) By Lemma 4 we thus have
for all and some complex number
.
Exercise 72 (Continuity of
-function at
) Let
be a non-principal character. For any
, define the Dirichlet
-function
by the formula
Show that
for any
. In particular, the Dirichlet
-function extends continuously to
. (In later notes we will extend this function to a much larger domain.)
We will shortly prove the following fundamental fact:
Theorem 73 (Non-vanishing) One has
for any non-principal character
.
Let us assume this theorem for now and conclude the proof of Theorem 70. Starting with the identity (74) and using (37), we see that
Inserting (75), (77) and using the trivial bound to control error terms, we conclude that
and Theorem 70 follows by dividing by and using Proposition 12.
Remark 74 It is important to observe that this argument is potentially ineffective: the implied constant in Theorem 70 will depend on what upper bound one can obtain for the quantity
. Theorem 73 ensures that this quantity is finite, but does not directly supply a bound for it, and so we cannot explicitly (or effectively) describe what the implied constant is as a computable function of
, at least if one only uses Theorem 73 as a “black box”. It is thus of interest to strengthen Theorem 73 by obtaining effective lower bounds on
for various characters
. This can be done in some cases (particularly if
is not real-valued), but to get a good effective bound for all characters
is a surprisingly difficult problem, essentially the Siegel zero problem; we will return to this issue in later notes.
Exercise 75 Show that
for any
and any non-principal character
. (You will not need to know the non-vanishing of
to establish this.) Conclude that
for any
and any primitive residue class
, where
is the polynomial in Proposition 60. Deduce in particular the cheap Brun-Titchmarsh bound
for any
and primitive residue class
.
It remains to prove the non-vanishing of . Here we encounter a curious repulsion phenomenon (a special case of the Deuring-Heilbronn repulsion phenonemon): the vanishing of
for one character
prevents (or “repels”) the vanishing of
for another character
. More precisely, we have
Proposition 76 Let
. Then there is at most one non-principal Dirichlet character
of modulus
for which
.
Proof: Let denote all the Dirichlet characters of modulus
, including the principal character
. The idea is to exploit a certain positivity when all the characters are combined together, which will be incompatible with two or more of the
vanishing.
There are a number of ways to see the positivity, but we will start with the Euler product identity
from (27). We can “twist” this identity by replacing by
for any Dirichlet character
, which by the complete multiplicativity of
gives
for any , where we allow for logarithms to be ambiguous up to multiples of
. By Taylor expansion, we thus have
for (cf. (31)). Summing this for
, we have
From (73) we see that . In particular, the left-hand side is non-negative. Exponentiating, we conclude the lower bound
Now we let . For non-principal characters
, we see from Exercise 72 that
stays bounded as
, and decays like
if
vanishes. For the principal character
, we will just use the crude upper bound
. By (11), we conclude that if two or more
are vanishing, then the product
will go to zero as
, contradicting (78), and the claim follows.
Call a Dirichlet character real if it only takes real values, and complex if it is not real. For instance, the character of modulus
that takes the values
on
,
on
,
on
,
on
, and
on
is a complex character. The above theorem, together with conjugation symmetry, quickly disposes of the complex characters
, as such characters can be “repelled” by their complex conjugates:
Corollary 77 Let
be a complex character. Then
.
Proof: If is a complex character of some modulus
, then its complex conjugate
is a different complex character with the same modulus
, and
. If
vanishes, we therefore have at least two non-principal characters of modulus
whose
-function vanishes at
, contradicting Theorem 73.
This only leaves the case of real non-principal characters to deal with. These characters are also known as quadratic characters, as
is the principal character; they are also connected to quadratic number fields, as we will discuss in a subsequent post. In this case, we cannot exploit the repulsion phenomenon, as we now only have one character for which
vanishes. On the other hand, for quadratic characters we have a much simpler positivity property, namely that
for all natural numbers . Actually, it is convenient to use a variant of this positivity property, namely that
which can be proven first by working in the case that is a power of a prime
and using (79), and then using multiplicativity to handle the general case. Crucially, we can do a little better than this: we can improve (80) to
whenever is a perfect square. Again, this can be verified by first working in the case when
is an even prime power.
It is now natural to consider sums such as to exploit this positivity. It turns out that the best choice of
to use here is
, that is to say to control the sum
On the one hand, from positivity on the squares (81), we can bound this sum by
for (say), thanks to (14). On the other hand, we can expand (82) using the Dirichlet hyperbola method (cf. (55)) as
From (12) one has
while from Lemma 71 we have
and so (using the trivial bound to control error terms) the previous expression can be rewritten as
The final error is . From Lemma 71 we have
. Inserting (77), we conclude that
If vanishes, then this leads to a contradiction if
is large enough. This concludes the proof of Theorem 73, and hence Dirichlet’s theorem.
Remark 78 The inequality (83) in fact shows that
is positive for every real character
. In fact, with the assistance of some algebraic number theory, one can show the class number formula which asserts (roughly speaking) that
is proportional to the class number of a certain quadratic number field. This will be discussed in a subsequent post.
Exercise 79 By using an effective version of the above arguments, establish the lower bound
for all non-principal characters
of modulus
(both real and complex).
Remark 80 The bound (84) is very poor and can be improved. For instance, the class number formula alluded to in the previous remark gives the effective bound
for real non-principal characters. In later notes we will also establish Siegel’s theorem, which gives an ineffective bound of the form
for such characters, and any
.
Exercise 81 Let
be a non-principal character. Show that the sum
is conditionally convergent. Then show that the product
is conditionally convergent to
.
Exercise 82 If
is a non-principal character of modulus
, establish the asymptotic
for any
. (Hint: use the hyperbola method.) Use this to give an alternate proof of the non-negativity of
when
is real.
[UPDATE: Major revision of this set of notes on Nov 22, 2022.]
136 comments
Comments feed for this article
4 April, 2015 at 6:56 am
Anonymous
In regards to exercise 11, is there a good explanation as to why $e^(i n t)$ has zero mean value ($t \neq 2k\pi$), but when one replaces the $n$ with a $\log(n)$, this is no longer the case?
13 April, 2015 at 6:11 am
Karaskas
Exercise 31: It should be
instead of
.
[Corrected, thanks – T.]
14 April, 2015 at 3:04 am
Anonymous
The summand
should be
.
[Corrected, thanks – T.]
26 August, 2015 at 4:25 pm
Heath-Brown’s theorem on prime twins and Siegel zeroes | What's new
[…] , one can show through summation by parts (see Lemma 71 of this previous post) […]
9 February, 2016 at 11:32 pm
Jarek Kuben
Small typographic remark: you’re using
(Fraktur G) instead of
(Fraktur S) for singular series. Same in Notes 2, however you got it right in Supplement 4 and Notes 4. :)
[Corrected, thanks – T.]
14 March, 2016 at 4:22 pm
Biases between consecutive primes | What's new
[…] One can also establish (2) (with smoothing) using elementary number theory methods (as in this previous post); we sketch the argument as follows. We can factor as a Dirichlet […]
2 July, 2016 at 6:51 am
254A, Supplement 3: The Gamma function and the functional equation (optional) | What's new
[…] use a trick previously employed to prove Lemma 40 of Notes 1. By (12) and the dominated convergence theorem, we […]
31 August, 2016 at 12:28 pm
Heuristic computation of correlations of higher order divisor functions | What's new
[…] is a certain explicit polynomial of degree with leading coefficient ; see e.g. Exercise 31 of this previous post for a discussion of the case (which is already typical). Similarly if . For more general , there […]
22 September, 2016 at 4:13 am
Anonymous
The 6th line in the proof of Theorem 36: o(1) should be O(1).
[Actually, I think the equation is correct as it stands – T.]
23 September, 2016 at 1:53 am
Anonymous
Did you implicitly assume that \frac{\log y}{\log x}-1=o(1)?
23 September, 2016 at 2:03 am
Anonymous
Please ignore my previous comment. I forgot to add the first summand in the final computation. Thanks!
8 October, 2016 at 10:17 am
Anonymous
In Remark 49:
should be
?
[Corrected, thanks – T.]
21 January, 2017 at 3:56 pm
254A, Notes 2: Complex-analytic multiplicative number theory | What's new
[…] Notes 1, we approached multiplicative number theory (the study of multiplicative functions and their […]
15 July, 2017 at 4:21 am
An Epsilon of Mathematics
[…] https://terrytao.wordpress.com/2014/11/23/254a-notes-1-elementary-multiplicative-number-theory/ (Terry what’s new) […]
17 July, 2017 at 4:28 am
An Epsilon of Mathematics
[…] https://terrytao.wordpress.com/2014/11/23/254a-notes-1-elementary-multiplicative-number-theory/ […]
11 August, 2017 at 8:43 am
Math student
Dear Prof. Tao,
in (8) and (9), do you mean
in the argument on the RHS instead of
?
[The two are equivalent up to constants – T.]
11 August, 2017 at 11:26 pm
Math student
Dear Prof. Tao,
I have a question regarding number theory in general. It seems as though sometimes, the same problem can be done using different methods (in fact, in ex. 10 there are
). Would you deem it advisable to do the problem several times, using the different methods, or rather to use the one one is least familiar with and then go on to the next exercise for brevity?
13 August, 2017 at 10:04 am
Terence Tao
One shouldn’t be measuring progress in terms of the number of exercises solved per unit time; it’s about how well you understand the material. The purpose of doing exercises is to test this understanding and to develop your technique and intuition; as long as you feel you have learned something at the completion of an exercise, it has not been time wasted.
See also my advice pages on this blog, including:
https://terrytao.wordpress.com/career-advice/there%E2%80%99s-more-to-mathematics-than-grades-and-exams-and-methods/
https://terrytao.wordpress.com/career-advice/ask-yourself-dumb-questions-%E2%80%93-and-answer-them/
https://terrytao.wordpress.com/career-advice/learn-and-relearn-your-field/
https://terrytao.wordpress.com/career-advice/learn-the-limitations-of-your-tools/
https://terrytao.wordpress.com/career-advice/learn-the-power-of-other-mathematicians-tools/
https://terrytao.wordpress.com/career-advice/continually-aim-just-beyond-your-current-range/
13 August, 2017 at 11:32 pm
Math student
The question of course always being WHICH tools and tricks to learn about in a given amount of time, which doubtlessly an experienced world-class number theorist can answer more readily than a rather mediocre “maths script-kiddy” like myself. I wonder whether the way mathematics is built favours the one who learns rather fringe material, the one who studies that which no-one else studies, so that he can make discoveries that withstand the attempts of the “mainstreamers”, if there is such a thing.
25 August, 2017 at 2:43 pm
Tom Gannon
Thanks for these notes! In the first paragraph, “to the classical situation of real ofr complex arithmetic functions,” I imagine should be “real or complex”?
[Corrected, thanks – T.]
22 September, 2017 at 11:18 pm
Maths student
Dear Prof. Tao,
I think in the paragraph before equation (20), one needs
, where
is the majorizing constant implicit in the 