VO Analytic Number Theory PDF

Preview

Summary

Number Theoretic Functions, Averaging, Euler-McLaurin Sum, Abelian Summation, Dirichlet Series, Product Representation, Chebyshev's Theorem, Prime Number Theorem (PNT) , Meromorphic continuation, Zero free regions of the Zetafunction, Error Term in the PNT, Equidistribution....

Description

Analytic Number Theory

1

Number Theoretic functions

Definition 1.1. A number theoretic function is a function N → C. Example 1.2. Some important number theoretic functions are σ 0 (n) := number of positive divisors of n = σ 1 (n) := sum of positive divisors of n = σ k (n) :=

∑

∑

∑

1

d|n

d

d|n

dk

d|n

{

(−1)k 0 ฀ ฀ 1 I(n) := n

µ(n) :=

if n = pi1 · · · pik else

φ(n) := |(Z/nZ)∗ | =

∑n

1

k=1 gcd(n,k)=1

U (n) := 1 N (n) := n. Definition 1.3. For number theoretic functions f, g : N → C we deőne their sum and Dirichlet convolution as (f + g)(n) := f (n) + g(n) and (f ⋆ g)(n) :=

∑ d|n

f (d) · g

(n ) d

.

Proposition 1.4. Let A be the set of all number theoretic functions and let +, ⋆ as above. Then (A, +, ⋆) is a commutative ring with identity.

1

Proof. The identity is I(n) as (f ⋆ I)(n) =

(

∑ d|n

) d f (d)I = f (n)I(1) = f (n). n

Associativity is clear once you see that ∑

(f ⋆ g)(n) =

f (a)g(b)

ab=n

and hence ((f ⋆ g) ⋆ h) (n) =

∑

f (a)g(b)h(c) = (f ⋆ (g ⋆ h)) (n).

abc=n

Theorem 1.5. (A, +, ⋆) is a factorial integral domain (a UFD). Proof. See Article of Cashwell and Everett. Definition 1.6. For a given number theoretic function f we deőne the summatory function Sf of f by Sf (n) := ∑ d|n f (d) = (f ⋆ U )(n). Proposition 1.7. For all n ∈ N we have

∑

µ(d) = I(n)

d|n

meaning that µ ⋆ U = I. Proof. The case n = 1 is trivial. For n > 1 consider the prime factor decomposition n = pα11 · · · pαk k (k > 0), then we get ∑ µ(d) = µ(1) + µ(p1 ) + . . . + µ(pk ) + µ(p1 p2 ) + . . . + µ(p1 · · · pk ) d|n

( ) ( ) ( ) k k k · (−1) + (+1) + . . . + · (−1)k =1+ 1 2 k

= (1 − 1)k = 0.

Theorem 1.8. Let f be an arithmetic function with f (1) = 0. Then there exists a uniquely determined Dirichlet1 and inverse f −1 of f satisfying f ⋆ f −1 = f −1 ⋆ f = I. It is determined recursively by f −1 (1) = f (1) f −1 (n) =

−1 ∑ f (1)

d|n d=n

2

f

(n ) d

f −1 (d).

(1)

Proof. We will proof that (f ⋆ f −1 )(n) = I(n) has a unique solution in the unknown f −1 (n). For n = 1 we have f (1)f −1 (1) = 1 ⇒ f −1 (1) =

1 . f (1)

(2)

Assume now that f −1 (k) is determined for all k < n. Then solve (f ⋆ f −1 )(n) = I(n) for f −1 (n). This gives (n ) ∑ f f −1 (d) = 0 d d|n (n ) ∑ f −1 (d) = 0 ⇔ f (1)f −1 (n) + f d d|n d=n

⇔ f −1 (n) = −

(n ) 1 ∑ f f −1 (d). f (1) d d|n d=n

Corollary 1.9. The number theoretic functions f ∈ A with f (1) = 0 form an abelian group under Dirichlet convolution and we have (f ⋆ g )−1 = f −1 ⋆ g −1 . Theorem 1.10 (Möbius inversion formula). Let f , g be two number theoretic functions, then (n ) (n ) ∑ ∑ ⇔ g(n) = f (n) = f (d)µ g d d d|n d|n ⏞ ⏟⏟ ⏞ ⏞ ⏟⏟ ⏞ g=f ⋆µ

g⋆U

Proof. (⇒) Let f = g ⋆ U . Then f ⋆ µ = (g ⋆ U ) ⋆ µ = g ⋆ (U ⋆ µ) = g ⋆ I = g . (⇐) Let g = f ⋆ µ. Then g ⋆ u = (f ⋆ µ) ⋆ u = f ⋆ (µ ⋆ u) = f ⋆ I = f . Let us consider the von Mangoldt function Λ deőned by { log(p) if n = pα . Λ(n) = 0 else Proposition 1.11. The von Mangoldt function fulfills log n =

∑

Λ(d).

d|n

Proof. The case n = 1 is trivial. ∑ For n > 1 consider the prime factor decomposition n = pα11 · · · pkαk ⇒ log(n) = 1≤i≤k αi log(pi ) to get ∑ ∑ ∑ Λ(pm Λ(d) = i ) 1≤i≤k 1≤m≤αk

d|n

=

∑

αi log(pi )

1≤i≤k

= log(n).

3

Corollary 1.12. The von Mangoldt function fulfills Λ(n) = −

∑ d|n

µ(d) log d.

Proof. With f = log and g = Λ in the Möbius inversion formula gives (n ) ∑ µ(d) log Λ(n) = d d|n ∑ ∑ = log n µ(d) log d µ(d) − d|n

d|n

=−

Exercise 1.13. Proof that

∑ d|n

∑

⏞ ⏟⏟ ⏞ =I(n)

µ(d) log d

d|n

φ(d) = n and use Möbius inversion formula to conclude that φ(n) =

∑

dµ

d|n

(n ) d

.

Definition 1.14. A number theoretic function f is called multiplicative if f (1) = 1 and for any m, n gcd(m, n) = 1 we have f (mn) = f (m)f (n). Further f is called completely multiplicative if the above relation holds for all m, n. Remark 1.15. Note that f multiplicative ⇒ f (1) = 0 ⇒ f invertible. Proposition 1.16. Let f, g be multiplicative number theoretic functions. Then f ⋆ g is multiplicative as well. Proof. Let gcd(m, n) = 1 and let us denote f ⋆ g by h. Then we have ( mn ) ∑ f (c)g h(mn) = c c|mn If c|mn, then c = ab with (a, b) = 1 and a|m, b|n and vice versa. Hence we get ( mn ) ∑ f (ab)g h(mn) = ab a|m b|n

=

∑

f (a)f (b)g

a|m b|n

⎛

= ⎝

∑

a|m

(m ) (n ) g b a

⎞⎛ ⎞ (m ) (n ) ∑ ⎠ = h(m)h(n). ⎠⎝ f (a)g f (n)g a b b|n

Corollary 1.17. For any multiplicative number theoretical function f , Sf is multiplicative as well. Proof. Just note that U is (completely) multiplicative and Sf = f ⋆ U . 4

Remark 1.18. The analogue of this result for completely multiplicative functions is false. Exercise 1.19. Find a counterexample as noted in the above remark. Remark 1.20. The advantage of dealing with multiplicative functions comes from the fact that they are fully determined by their values at prime powers n = pα1 1 · · · pkαk ⇒ f (n) = f (pα11 ) . . . f (pαk k ). For completely multiplicative functions the values at primes only are already enough. Proposition 1.21. If f is multiplicative, so is f −1 . Proof. Let g = f −1 , then we have the relation g(pk ) = − =−

∑

( f (d)g

d=1 d|pk

∑

pk d

)

) ( ) ( f pt g pk−t .

1≤t≤k

Now let h be the uniquely determined multiplicative function that coincides with g at all prime powers. Then for k > 0 we have ∑ ) ( ) ( f pt h pk−t (h ⋆ f )(pk ) = 0≤t≤k

∑k ( ) ( ) ( ) f pt h pk−t = f (1)h pk + t=1

( ) ( ) = g pk − g pk = 0 and for k (= 0) we have ( ) (h ⋆ f)(1) = 1. So (h ⋆ f ) pk = I pk for all k ≥ 0 and since h and f are multiplicative h ⋆ f is also multiplicative, hence h ⋆ f = I . Therefore g coincides with h as the inverse is unique, especially g is multiplicative. Corollary 1.22. Multiplicative number theoretical functions build a subgroup of the group of invertible number theoretical functions. Proposition 1.23. If f is multiplicative then ∑ ∏ (1 − f (p)) . µ(d )f (d ) = d|n

∑

p|n

Proof. Let g(n) = d|n µ(d )f (d ). Since µ and f are multiplicative we have that µ·f and g = Sµ·f are multiplicative. Therefore it is sufficient to evaluate g at prime powers, ∑ µ(d )f (d ) = µ(1)f (1) + µ(p)f (p) = 1 − f (p). g(pk ) = d|pk

So g(n) =

∏

g(pαp ) =

p|n

∏ p|n

5

(1 − f (p)).

Example 1.24. The totient function fulőlls ) ∏ ( ∑ ∑ 1 1 n 1 − = n = n µ(d) µ(d) . φ(n) = d d p d|n d|n p|n

Proposition 1.25. If f is completely multiplicative, then f −1 (n) = µ(n)f (n). Proof. Let g(n) = µ(n)f (n). Then we get (n ) ∑ ∑ (g ⋆ f )(n) = µ(d )f (d )f µ(d) = f (n)I(n) = I(n). = f (n) d d|n d|n Example 1.26. The Liouville function λ(n) = (−1)α1 +...+αk for n = pα11 · · · pkαk fulőlls { ∑ 1 if n is a square . λ(d) = 0 otherwise d|n ∑ Observe that λ is completely multiplicative, hence g(n) := d|n λ(d) is multiplicative, hence we only need to evaluate g at prime powers, ∑ λ(d) g(pk ) = d|pk

( ) ( ) = 1 + λ(p) + λ p2 − . . . + λ pk

= 1 − 1 + 1 − . . . + (−1)k { 1 if k even . = 0 otherwise For arbitrary n we have

( g(n) = g

k ∏

) piαi

=

∏k

g (pαi i ) .

i=1

i=1

If at least one αi is odd, then g(n) = 0, if all αi are even, then g(n) = 1. We further claim that λ−1 (n) = |µ(n)|. By complete multiplicativity we have that λ−1 (n) = µ(n)λ(n) and since λ(n) = µ(n) for square free numbers we have λ−1 (n) = µ2 (n) = |µ(n)|. Example 1.27. We try to compute σk−1. Recall that ∑ ) ( σ k (n) = d k = U ⋆ N k (n) d|n

where N k (n) = nk is completely multiplicative. Since U is multiplicative too we know that σ k is multiplicative. If we evaluate σ k on prime powers, σ k (pα ) = 1 + pk + p2k + . . . + pαk ⎧ pk(α+1) − 1 ⎪ ⎪ ⎪ if k = 0 ⎨ pk − 1 , = ⎪ ⎪ ⎪ ⎩α + 1 if k = 0 6

we get for arbitrary n

1 αs σ k (n) = σ k (pα 1 ) . . . σ k (p s ).

Further we can calculate its inverse σk = N k ⋆ U

( ) ⇒ σk−1 = (N k )−1 ⋆ U −1 = µN k ⋆ µ (n ) ∑ ⇒ σk−1(n) = . d k µ(d)µ d d|n

Definition 1.28. We deőne the derivative f ′ of a number theoretic function f as f ′ (n) = f (n) log n. Example 1.29. We have I ′ (n) = I (n) log(n) ≡ 0, U ′ (n) = U (n) log(n) = log(n) =

∑

Λ(d )

d|n

hence Λ ⋆ U = U ′ . Proposition 1.30. Let f, g be to number theoretical functions. Then 1. (f + g)′ = f ′ + g ′ 2. (f ⋆ g )′ = f ′ ⋆ g + f ⋆ g ′ 3. f (1) = 0 ⇒ (f −1 )′ = −f ′ ⋆ (f ⋆ f )−1 . Proof. 1. is trivial. ( ) For 2. observe that log(n) = log(d) + log nd . Therefore we get (n ) ∑ f (d)g log(n) (f ⋆ g)′ (n) = d d|n (n ) (n ) ∑ (n ) ∑ log = + f (d ) log(d )g f (d)g . d d d d|n d|n ⏞ ⏟⏟ ⏞ ⏞ ⏟⏟ ⏞ (f ′ ⋆g)(n)

(f ⋆g ′ )(n)

For 3. we have

( −1 )′ ( )′ f = f ⋆ f −1 ⋆ f −1 ⎛ ⎞ ( ) ′ = ⎝ f ⋆ f −1 −f ′ ⋆ f −1 ⎠ ⋆ f −1 ⏞ ⏟⏟ ⏞ =0

= −f ′ ⋆ (f ⋆ f )−1 .

7

Theorem 1.31 (Selberg’s identity). For n ≥ 1 we have (n ) ∑ ∑ = Λ(n) log(n) + Λ(d)Λ d

µ(d) log2

d|n

d|n

(n ) d

.

Proof. Taking the derivative of Λ ⋆ U = U ′ yields Λ′ ⋆ U + Λ ⋆ U ′ = U ′′ ⇒ Λ′ ⋆ U + Λ ⋆ (Λ ⋆ U ) = U ′′ . Convolution with U −1 = µ yields Λ′ + Λ ⋆ Λ = U ′′ ⋆ µ.

2

Averages of number theoretical functions

The symbols o and O are used in the following as well as asymptotic equality ∼. A problem is the irregular behavior of for example σ 1 . We have σ 1 (p)∑= p + 1, on the other hand for őxed k there n exists n ∈ N with σ 1 (n) > kn. So for the investigation we consider n1 k=1 σ 1 (n). We have a couple of tools to evaluate such sums, in particular the Euler summation formula (analogy between sum and integral) and Abel summation (based on discrete version of partial integration). Theorem 2.1 (Euler Summation Formula). Let f : R → C be in C 1 [(y, x)], where 0 < y < x. Then ∫ x ∫ x ∑ (t − ⌊t⌋ )f ′ (t) dt + f (x)(⌊x⌋ − x) − f (y )(⌊y⌋ − y ). f (n) = f (t) dt + y

y 0.

∑∞

1 n=1 ns

converges for Re(s) > 1. Let b(n) = (−1)n then σ¯ b = 1, but

∑∞

n=1

(−1)n ns

Proposition 3.6. For a ∈ A we have 0 ≤ σ a − σ a ≤ 1. Proof. We have to show that

for σ > Re(s0 ) + 1. If

∑∞ |a(n)| ∑∞ a(n) converges ⇒ converges ns0 nσ n=1 n=1

  ∑∞ a(n)    a(n)  ≤ A. Hence we have converges, then ∃A ∀n :  ns0  ns0 n=1      A |a(n)|  a(n)   a(n)   1  = =  ns   ns0   ns−s0  ≤ nσ−σ0 nσ ∑∞ |a(n)| ∑∞ 1 ≤ A < ∞. ⇒ σ σ−σ0 n n n=1 n=1

∑∞ f (pj ) Theorem 3.7. Let f ∈ A be multiplicative. For every p in P the series j=0 pj s converges uniformly on compact subsets of {s | Re(s) > σ¯ f } and we have that ⎛ ⎞ ∞ ∏ ∑∞ f (n) ∑ f (pj ) ⎝ ⎠= . pjs ns p n=1

j=0

The convergence is again uniform on compact subsets. Proof. First note that we have

  ( ) ( )  ∞ ∑ ∑∞ |f (n)|  ∑∞ f pj  |f pj |  ≤ ≤ .   jσ nσ  j=M pjs  j=M p n=pM

Hence we have uniform convergence on compact subsets of {s | Re(s) > σ¯ f }. Now let p1 < p2 < . . . be the sequence of primes and Nk = {n ∈ N | (p|n ∧ p prime) ⇒ p ≤ pk }. Then ) ( ( )     ⎛ j j ( ) ⎞    ∞ ∑∞ f (n)  ∑∞ f p 11 · · · f p kk ∑∞ f (n)   ∑ ∑∞ f pj ∏  =  ⎝  ⎠− − ··· jk s j1 s  js ns  ns   · · · p p  p≤pk j=0 p 1 k j1 =0 n=1 jk =0 n=1 ( )   j j ∑ 1 k ∞ ∞ ∑ f (n)  ∑ f p 1 · · · pk ∞  − =  ··· j s j s ns  p 11 · · · pkk  j=0 n=1 jk =0      ∑ f (n) ∑∞ f (n)   ∑ f (n)  ∑ |f (n)| k→∞   ≤  −−−−→ 0 =  = −  nσ ns  ns    ns n≥pk n=1 n∈N / k n∈Nk

uniformly on compact subsets.

16

Corollary 3.8. If f ∈ A is completely multiplicative, then Proof. Just note that

∑∞

f (n) n=1 ns

=

∏ ( p 1−

f (p) ps

)−1

.

( ) ( ) ∑∞ f pj ∑∞ ( f (p) )j f (p) −1 = = 1− . pjs ps ps j=0 j=0

Definition 3.9. We deőne ζ(s) := LU (s) =

∑∞

1 n=1 ns

for Re(s) > 1, the Riemann Zeta-Function.

Remark 3.10. We have σ ζ = σ ζ = 1. By the Theorems on analyticity and convergence we know that the convergence is uniform ∏ on compact subsets and ζ is an analytic function there. As U is completely multiplicative we have ζ(s) = p (1 − p1s )−1 which is called the product representation of ζ for Re(s) > 1. Theorem 3.11. The following relations hold. 1. ζ(s) = 0 for Re(s) > 1 ∑∞ n) 2. ζ ′ (s) = − n=1 log( = −Llog (s) for Re(s) > 1 ns ∑ 1 = Lµ (s) for Re(s) > 1 = n≥1 µ(n) 3. ζ(s) ns 4. ζ 2 (s) =

∑ n≥1

σ0 (n) ns

= Lσ0 (s) for Re(s) > 1

∑∞ σ (n) 5. ζ(s)ζ(s − 1) = n=1 n1 s = Lσ1 (s) for Re(s) > 2 ∑ φ(n) ζ(s−1) 6. ζ(s) = ∞n=1 ns = Lφ (s) for Re(s) > 2 ∑∞

7.

ζ(2s) ζ(s)

=

8.

ζ(s)′ ζ(s)

=−

λ(n) n=1 ns

∑∞

= Lλ (s) for Re(s) > 1

Λ(n) n=1 ns

= −LΛ (s) for Re(s) > 1

Proof. For 1 recall Hurwitz’ Theorem from complex analysis which says that if fn are analytic functions with f (s) = lim fn (s) uniformly on compact subsets of some domain and the fn (s) have less than K zeroes then f (s) ( )−1 ∏ also has less than K zeroes or f = 0. Applying this result with K = 0 by setting fn (s) = p σ a to a larger subset of C. Example 3.13. Assume that Re(s) > 1. Then we get for the zeta function ) ( 1 1 1 1 1 1−s (1 − 2 )ζ (s) = 1 + s + s + . . . − 2 + s + 3 6 2s 4s 2 1 1 1 = 1 − s + s − s + ... 3 2 4 ∑ (−1)n−1 = =: η(s). ns n≥1 Now note that the series for η(s) converges not only for Re(s) > 1 but for Re(s) > 0. Therefore we can continue the zeta function to Re(s) > 0, s = 1 by deőning ζ(s) =

η(s) . 1 − 21−s

Proposition 3.14. The Riemann ζ-function has the integral representation ∫ ∞ ζ(s) = s ⌊x⌋ x−s−1 dx. 1

By the resulting identity ζ(s) −

1 =1−s s−1

∫

∞ 1

{x } dx xs+1

it has an analytic continuation to Re(s) > 0 with the exception of a simple pole at s = 1 with residue 1.

18

Proof. For Re(s) > 2 we have ∑

∑ n−1 n − s ns n n≥1 n≥1 ∑ ∑ n n − = s (n + 1)s n n≥1 n≥1 ∑ ) ( −s = n n − (n + 1)−s

ζ(s) =

n≥1

=

∑

∫

n+1

n≥1 ∑∞

=s

n

∫

=s

∑∞ ∫ ∫n=1 ∞ 1

Moreover, we have s

∫∞ 1

x · x−s−1 dx =

s s−1

1 ζ(s) − =1+s s−1

∫

n+1

x−s−1 dx

n n

n=1

=s

x−s−1 dx

ns

n+1

⌊x⌋ x−s−1 dx

n

⌊x⌋ x−s−1 dx.

1 = 1 + s−1 . Taking the difference yields ∞ 1

∫ (⌊x⌋ − x) x ⏞ ⏟⏟ ⏞

−s−1

dx = 1 − s

−{x}

∞ 1

{x}x−s−1 dx,

which makes sense for Re(s) > 0. This gives an extension to Re(s) > 0 of ζ as a meromorphic function with a simple pole of residue 1 at s = 1. The same procedure∑may be applied to all number theoretical functions, by using the technique of Abel summation. Let a ∈ A, A(x) := n≤x a(n) then Abel summation yields ∑ n≤x

1 a(n) = A(x) − ns xs

∫

x

A(t) 1

−s dt ts+1

x→∞

A(x) For Re(s) sufficiently large we have that xs −−−−→ 0 and the integral converges. Applying this to a(n) = Λ(n) and letting ψ(x) := A(x) we obtain for Re(s) > 1 ∫ ∞ ∑ Λ(n) ζ ′ (s) ψ(x)x−s−1 dx. = = s s ζ(s) n 1 n≥1

Note that we also have ψ(x) =

∑ n≤x

Λ(n) =

∑ p

19

∑ ν≥1 pν ≤x

log p ≤ x log x.

4

The prime number theorem

∑ In the focus will be π(x) := p≤x 1 the prime counting function. Gauss conjectured that π(x) ∼ x , i.e. there exists positive constants c 1 , c 2 such that proved the weaker result π(x) ≍ log(x) c1

x . log(x)

Chebyshev

x x . ≤ π(x) ≤ c 2 log(x) log(x)

For example one may take c 1 = 61, c 2 = 6. Theorem 4.1. We have ∀n ≥ 2

6n n < π(n) < . 6 log(n) log(n)

( ) ≤ 4n . The second inequality is trivial by the result about the sum of Proof. We start by observing that 2n ≤ 2n n binomial coefficients and the őrst one follows by simple computations using the factorials. Taking logarithms yields n log 2 ≤ log((2n)!) − 2 log(n!) ≤ n log 4. We may write log n! =

∑

αn (p) log p

p≤n

with

n ⌊ log ฀ log p ⌋ ฀ ∑ n αn (p) = . pm m=1

This gives ∑

log((2n)!) − 2 log(n!) =

p≤2n

2n ⌊ log log p ⌋ (฀ ∑

m=1

Together with the above inequality this yields n log 2 ≤ ≤

∑

⎛

⏞

฀

฀ ฀) n log p. −2 m p ⏟⏟ ⏞

∈{0,1}

⎞ 2n ⌊ log log p ⌋ ∑ ⎟ ⎜ 1⎠ log p ⎝

p≤2n

∑

2n pm

m=1

log(2n) log p = log(2n)π(2n). log p p≤2n

Which gives a strong estimate for even integers π(2n) ≥

2n log(2) 1 2n n log 2 > = . log(2n) 4 log(2n) log(2n) 2

In the obvious but weaker way we can extend this to odd integers π(2n + 1) ≥ π(2n) >

2n + 1 1 2n 1 2n + 1 1 2n ≥ > . 6 log(2n + 1) 4 2n + 1 log(2n + 1) 4 log 2n 20

n Together we have obtained π(n) > 61 log(n) . For the upper bound, we again use

log((2n)!) − 2 log(n!) =

∑ p≤2n

2n ⌊ log ฀ log p ⌋ (฀ ∑ 2n

m=1

pm

฀

n −2 m p

฀)

log p.

If we neglect all terms except for m = 1 we get together with the above inequality (฀ ฀ ฀ ฀) ∑ 2n n log p − 2 log((2n)!) − 2 log(n!) ≥ p p p≤2n ⏞ ⏟⏟ ⏞ =1 for p∈[n,2n]

∑

⇒ n log 4 ≥ log((2n)!) − 2 log(n!) ≥

log p =

n x and so these m have no contribution to the above sum. Hence we can write ∑ ∑ ψ(x) = log p x pm ≤x m≤ log log 2

∑

=

θ(x1/m ).

x m≤ log log 2

Which further implies ∑

log x/ log 2

0 ≤ ψ(x) − θ (x) ≤

θ(x1/m ).

m=2

Finally we have θ(x) ≤ x log x and we can use this to get ∑

log x/ log 2

0 ≤ ψ(x) − θ(x) ≤

m=2

( ) log x √ √ x1/m log x1/m ≤ x log x. log 2

Dividing by x gives the wan...