Theorems Flashcards

1
Q

Dirichlet’s Theorem

A

If k > 0 and gcd(h, k) = 1, then there are infinitely many primes in the arithmetic progression nk + h for n = 1, 2, …

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Prime Number Theorem

A

For large x, the ratio πœ‹(x) / (x/logx) approaches 1, i.e.
πœ‹(x)
β€”β€”β€”- ⟢ 1 as x ⟢ ∞
(x/logx)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Properties of divisibility

A

Let a, b, d, m, n be arbitrary integers unless otherwise indicated. Then

(1) d|m and d|n β‡’ d|(am + bn)
(2) ad|an and a β‰  0 β‡’ d|n
(3) d|n and n β‰  0 β‡’ |d| ≀ |n|
(4) d|n and n|d β‡’ |d| = |n|
(5) d|n and nd≠ 0 ⇒ (n/d) | n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Common divisor

A

Given any two integers a and b, there is a common divisor of the form d = ax + by where x, y ∈ Z. Moreover, every common divisor of a and b divides this d.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Euclid’s Lemma

A

If a|bc and gcd(a, b) = 1, then a|c.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Prime numbers

A

(1) Every integer n > 1 is a prime number of a product of prime numbers.
(2) There are infinitely many prime numbers.
(3) If p is a prime and p ∀ a, then (p, a) = 1
(4) If p is a prime and p|ab, then p|a or p|b. More generally if p|a…a, then p divides at least one of the factors.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Fundamental Theorem of Arithmetic

A

Every integer n > 1 can be represented as a product of prime factors in only one way, apart from the order of the factors.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

∞
βˆ‘ 1 / pβ‚™
n=1

A
Let pβ‚™ denote the nth prime. The infinite series
              ∞
              βˆ‘  1 / pβ‚™
            n=1
diverges.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Quotient and remainder terms

A

Given positive integers a and b with b > 0, there exists a unique pair of integers q and r such that a = bq + r with 0 ≀ r < b. Moreover, r = 0 if and only if b|a.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Euclidean Algorithm

A

We are given positive integers and b where b∀a. Let rβ‚€ = a and
r₁ = b, and apply the division repeatedly to obtain a set of remainders r₁, …, rβ‚™β‚Šβ‚ defined successively by the relations
rβ‚€ = r₁q₁ + rβ‚‚ 0 < rβ‚‚ < r₁
r₁ = rβ‚‚qβ‚‚ + r₃ 0 < r₃ < rβ‚‚
… …
rβ‚™β‚‹β‚‚ = rₙ₋₁qₙ₋₁ + rβ‚™ 0 < rβ‚™ < rₙ₋₁
rₙ₋₁ = rβ‚™qβ‚™ + rβ‚™β‚Šβ‚ rβ‚™β‚Šβ‚ = 0
Then rβ‚™ = gcd(a, b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

βˆ‘ πœ‡(d)

d|n

A

If n β‰₯ 1, we have
βˆ‘ πœ‡(d) = [1/n] = 1 if n = 1
d|n = 0 if n > 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

βˆ‘ πœ™(d)

d|n

A

If n β‰₯ 1, we have
βˆ‘ πœ™(d) = n
d|n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

A relation connecting πœ™ and πœ‡

A

If n β‰₯ 1, we have
πœ™(n) = βˆ‘ πœ‡(d) n/d
d|n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Product formula for πœ™(n)

A

For n β‰₯ 1, we have
πœ™(n) = n ∏ (1 - 1/p)
p|n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Properties of πœ™(n)

A

(a) πœ™(pα΅…) = pα΅… - pᡅ⁻¹ for prime p and a β‰₯ 1
(b) πœ™(mn) = πœ™(m)πœ™(n)d / πœ™(d), where d = (m, n)
(c) πœ™(mn) = πœ™(m)πœ™(n) if (m, n) = 1
(d) a|b β‡’ πœ™(a)|πœ™(b)
(e) πœ™(n) is even for n β‰₯ 3. Moreover if n has r distinct odd prime factors, then 2 Ν¬ |πœ™(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Properties of Dirichlet Convolution

A

Let f, g, and k be arithmetical functions. Then

a) f βˆ— g = g βˆ— f
(b) (f βˆ— g) βˆ— k = f βˆ— (g βˆ— k
i. e. Dirichlet convolution is commutative and associative.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Identity function on an arithmetical function

A

Let f be an arithmetical function. Then for all f, we have

f βˆ— I = I βˆ— f = f

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Dirichlet Inverse

A

If f is an arithmetical function with f(1) β‰  0, then there exists a unique arithmetical function f⁻¹ such that
f βˆ— f⁻¹ = f⁻¹ βˆ— f = I
The arithmetical function f⁻¹ is called the Dirichlet inverse of f. Moreover, f⁻¹ is given by the recursion formula
f⁻¹(1) = 1 / f(1)
f⁻¹(n) = - (1 / f(1)) βˆ‘ f(n/d) f⁻¹(d) for n > 1
d|n
d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Set of arithmetical functions

A

The set of all arithmetical functions f with f(1) β‰  0 forms an abelian group under the operation βˆ—.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Mobius Inversion Formula

A
The equation
              f(n) =  βˆ‘  g(d)
                       d|n
implies
             g(n) =  βˆ‘  f(d) πœ‡(n/d)
                       d|n
The converse holds.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Von-Mangoldt formula for log

A

If n β‰₯ 1, we have
log n = βˆ‘ Ξ›(d)
d|n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Von-Mangoldt formula in terms of log and πœ‡

A

If n β‰₯ 1, we have
Ξ›(n) = βˆ‘ πœ‡(d) log(n/d) = - βˆ‘ πœ‡(d) log d
d|n d|n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

When is f(1) = 1?

A

If f is multiplicative, then f(1) = 1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Properties of functions with f(1) = 1

A

Given an arithmetical function f with f(1) = 1,
(a) f is multiplicative if and only if
f(p₁ Ν£ ΒΉ … pβ‚– Ν£ ᡏ) = f(p₁ Ν£ ΒΉ) … f(pβ‚– Ν£ ᡏ)
for all primes pα΅’ and all integers aα΅’ β‰₯ 1
(b) If f is multiplicative, then f is completely multiplicative if and
only if
f(p Ν£ ) = f(p) Ν£
for all primes p and all integers a β‰₯ 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Dirichlet product of multiplicative functions
If f and g are multiplicative functions, then the Dirichlet product f βˆ— g is also multiplicative. Note that the Dirichlet product of two completely multiplicative functions is not always completely multiplicative. Also, if both g and f βˆ— g are multiplicative, then f is multiplicative.
26
Dirichlet inverse of a multiplicative function
If g is multiplicative, then g⁻¹, the Dirichlet inverse of g, is multiplicative.
27
Inverse of a completely multiplicative function
Let f be a multiplicative function. Then f is a completely multiplicative function if and only if f⁻¹(n) = πœ‡(n) f(n) for all n β‰₯ 1.
28
βˆ‘ πœ‡(d) f(d) | d|n
If f is multiplicative, then βˆ‘ πœ‡(d) f(d) = ∏ (1 - f(p)) d|n p|n
29
Product formula for πœ™β»ΒΉ(n)
πœ™β»ΒΉ(n) = ∏ (1 - p) | p|n
30
βˆ‘ Ξ»(d) | d|n
For every n β‰₯ 1, we have βˆ‘ Ξ»(d) = 1 if n is a square d|n 0 otherwise
31
πœŽβ‚β»ΒΉ(n)
For n β‰₯ 1, we have that πœŽβ‚β»ΒΉ(n) = βˆ‘ d Ν£ πœ‡(d) πœ‡(n/d) d|n
32
Let 𝛼 and 𝛽 be arithmetical functions. Then we have 𝛼 ⚬ (𝛽 ⚬ F) = (𝛼 βˆ— 𝛽) ⚬ F where F : (0, ∞) ⟢ C such that F(x) = 0 for 0 < x < 1
33
(𝛼 β—‹ F)(m) for integers m
Let F : (0, ∞) ⟢ C such that F(x) = 0 for 0 < x < 1 and let 𝛼 be an arithmetical function. Also let G : (0, ∞) ⟢ C such that G(x) = 0 for 0 < x < 1 and G(x) = (𝛼 β—‹ F)(x) = βˆ‘ 𝛼(n) F(x/n) n≀x If F(x) = 0 for all nonintegral x (i.e. x is not an integer), we find that (𝛼 β—‹ F)(m) = (𝛼 βˆ— F)(m) for all integers m.
34
Dirichlet convolution identity function on β—‹
The identity function for Dirichlet convolution is also a left identity on the operation β—‹.
35
Generalised Inversion Formula
``` Let 𝛼 be an arithmetical function with Dirichlet inverse 𝛼⁻¹. Then the equation G(x) = βˆ‘ 𝛼(n) F(x/n) n≀x implies F(x) = βˆ‘ 𝛼⁻¹(n) G(x/n) n≀x The converse also holds. ```
36
Generalised Mobius Inversion Formula
``` If 𝛼 is a completely multiplicative function, we have G(x) = βˆ‘ 𝛼(n) F(x/n) n≀x if and only if F(x) = βˆ‘ πœ‡(n) 𝛼(n) G(x/n) n≀x ```
37
Arithmetic on derivatives of arithmetical functions
If f and g are arithmetical functions, we have (a) (f + g)' = f' + g' (b) (f βˆ— g)' = f' βˆ— g + f βˆ— g' (c) (f⁻¹)' = -f' βˆ— (f βˆ— f)⁻¹ as long as f(1) β‰  0
38
Selberg Identity
For n β‰₯ 1, we have Ξ›(n) log n + βˆ‘ Ξ›(n) Ξ›(n/d) = βˆ‘ Β΅(d) logΒ²(n/d) d|n d|n
39
f(t) = O(g(t)) for t β‰₯ a
``` f(t) = O(g(t)) for t β‰₯ a implies that x x ∫ f(t) dt = O( ∫ g(t) dt ) a a for x β‰₯ a ```
40
Euler Summation Formula
If f has a continuous derivative f' on the interval [y, x], where 0 < y < x, then x x βˆ‘ f(n) = ∫ f(t) dt + ∫ (t - [t])f'(t) dt + f(x)([x] - x) - f(y)([y] - y) y
41
Euler Summation formula if f has a continuous derivative on | x > 0
Let f have a continuous derivative on x > 0. Then x x βˆ‘ f(n) = ∫ f(t) dt + f(x)([x] - x) + f(1) + ∫ (t - [t])f'(t) dt n≀x 1 1
42
Consequences of Euler's Summation Formula
If x β‰₯ 1 then we have: (a) βˆ‘ 1/n = log x + 𝛾 + O(1/x) n≀x where 𝛾 is Euler's constant defined by the equation n 𝛾 = lim ( βˆ‘ 1/k - log n ) nβ†’βˆž k=1 (b) βˆ‘ 1/nΛ’ = x¹⁻˒ / (1-s) + ΞΆ(s) + O(x⁻˒) if s > 0, s β‰  1 n≀x (c) βˆ‘ 1/nΛ’ = O(x¹⁻˒) if s > 1 n>x (d) βˆ‘ nα΅… = xᡅ⁺¹ / (a + 1) + O(xα΅…) if a β‰₯ 0 n≀x
43
Dirichlet's Asymptotic Formula (weak)
For all x β‰₯ 1, we have βˆ‘ d(n) = x log x + O(x) n≀x
44
Dirichlet's Asymptotic Formula
For all x β‰₯ 1, we have βˆ‘ d(n) = x log x + (2𝛾 - 1)x + O(√x) n≀x
45
Average order of 𝜎(n)
For all x β‰₯ 1, we have βˆ‘ 𝜎(n) = 1/2 ΞΆ(2) xΒ² + O(x log x) n≀x
46
Average order of πœŽβ‚(n) for a > 0
If x β‰₯ 1 and a > 0, a β‰  1, we have βˆ‘ πœŽβ‚(n) = ( ΞΆ(a + 1) / (a + 1) ) x Ν£ ⁺¹ + O(x α·© ) n≀x where 𝛽 = max{1, a}
47
Average order of πœŽβ‚(n) for a < 0
Write a = -𝛽, so 𝛽 > 0. Let 𝛿 = max{0, 1 - 𝛽}. Then if x > 1, we have βˆ‘ πœŽβ‚(n) = ΞΆ(𝛽 + 1) x + O(xᡟ) if 𝛽 β‰  1 n≀x ΞΆ(2) x + O(log x) if 𝛽 = 1
48
Average order of πœ™(n)
For x > 1, we have βˆ‘ πœ™(n) = (3/πœ‹Β²) xΒ² + O(x log x) n≀x
49
lim 1/x βˆ‘ πœ‡(n) | xβ†’βˆž n≀x
lim 1/x βˆ‘ πœ‡(n) = 0 xβ†’βˆž n≀x This is equivalent to the PNT.
50
lim 1/x βˆ‘ Ξ›(n) | xβ†’βˆž n≀x
lim 1/x βˆ‘ Ξ›(n) = 1 xβ†’βˆž n≀x This is equivalent to the PNT.
51
Partial sums of a Dirichlet product
If h = f βˆ— g, let H(x) = βˆ‘ h(n), F(x) = βˆ‘ f(n), G(x) = βˆ‘ g(n) n≀x n≀x n≀x Then H(x) = βˆ‘ f(n) G(x/n) = βˆ‘ g(n) F(x/n) n≀x n≀x
52
βˆ‘ F(x/n) | n≀x
If F(x) = βˆ‘ f(n) n≀x, we have βˆ‘ βˆ‘ f(d) = βˆ‘ f(n) [x/n] = βˆ‘ F(x/n) n≀x d|n n≀x n≀x
53
βˆ‘ πœ‡(n) [x/n] | n≀x
We have βˆ‘ πœ‡(n) [x/n] = 1 n≀x
54
βˆ‘ Ξ›(n) [x/n] | n≀x
We have βˆ‘ Ξ›(n) [x/n] = (log [x])! n≀x
55
∞ | βˆ‘ πœ‡(n) / n | n=1
``` For all x β‰₯ 1, we have ∞ | βˆ‘ πœ‡(n) / n | ≀ 1 n=1 with equality holding only when x < 2. ```
56
Legendre's Identity
``` For every x β‰₯ 1, we have [x]! = ∏ pᡅ⁽ᡖ⁾ where ∞ 𝛼(p) = βˆ‘ [x/pᡐ] m=1 ```
57
(log[x])! when x β‰₯ 2
If x β‰₯ 2, we have (log[x])! = x log x - x + O(log x) and hence βˆ‘ Ξ›(n) [x/n] = x log x - x + O(log x) n≀x
58
When x β‰₯ 2, βˆ‘ [x/p] log p p≀x
When x β‰₯ 2, βˆ‘ [x/p] log p = x log x + O(x) p≀x
59
Dirichlet's Hyperbola Method
Let F(x) = βˆ‘ f(n), G(x) = βˆ‘ g(n) and H(x) = βˆ‘ (f βˆ— g)(n), n≀x n≀x n≀x so that H(x) = βˆ‘ βˆ‘ f(d) g(n/d) = βˆ‘ f(d) g(q) n≀x d|n q, d qd≀x If a, b ∈ R such that ab = x, than βˆ‘ f(d) g(q) = βˆ‘ f(n) G(x/n) + βˆ‘ g(n) F(x/n) - F(a) G(b) q, d n≀a n≀b qd≀x
60
πœ“(x) / x - ΞΈ(x) / x
For x > 0, we have 0 ≀ πœ“(x) / x - ΞΈ(x) / x ≀ (log x)Β² / (2 √x log2) This implies that lim ( πœ“(x) / x - ΞΈ(x) / x ) = 0 xβ†’βˆž Hence if either πœ“(x) / x or ΞΈ(x) / x tends to a limit, the so does the other and the limits are equal.
61
Abel's Identity
For any arithmetical function a(n), let A(x) = βˆ‘ a(n) n≀x where A(x) = 0 if x < 1. Assume f has a continuous derivative on the interval [y, x], where 0 < y < x. Then we have x βˆ‘ a(n) f(n) = A(x) f(x) - A(y) f(y) - ∫ A(t) f'(t) dx y < n ≀ x y
62
Abel's Identity where f has a continuous derivative on x > 0
For any arithmetical function a(n), let A(x) = βˆ‘ a(n) n≀x where A(x) = 0 if x < 1. Assume f has a continuous derivative on x > 0. Then we have x βˆ‘ a(n) f(n) = A(x) f(x) - ∫ A(t) f'(t) dt n≀x 1
63
ΞΈ(x) and πœ‹(x) in terms of integrals
``` For x β‰₯ 2, we have x ΞΈ(x) = πœ‹(x) log x - ∫ πœ‹(t) / t dt 2 and x πœ‹(x) = ΞΈ(x) / logx + ∫ ΞΈ(t) / (t logΒ²(t)) dt 2 ```
64
lim ΞΈ(x) / x | xβ†’βˆž
lim ΞΈ(x) / x = 1 xβ†’βˆž This is equivalent to the PNT.
65
lim πœ“(x) / x | xβ†’βˆž
lim πœ“(x) / x = 1 xβ†’βˆž This is equivalent to the PNT.
66
Relating the PNT to the asymptotic value of the nth prime
Let pβ‚™ denote the nth prime. Then the following asymptotic relations are logically equivalent. lim (πœ‹(x) log x) / x = 1 xβ†’βˆž lim (πœ‹(x) log πœ‹(x)) / x = 1 xβ†’βˆž lim pβ‚™ / (n log n) = 1 nβ†’βˆž
67
Order of magnitude of πœ‹(n)
For every integer n β‰₯ 2, we have | 1/6) (n / log n) < πœ‹(n) < 6 (n / log n
68
Order of magnitude of pβ‚™
For n β‰₯ 1, the nth prime satisfies the inequalities | 1/6 n log n < pβ‚™ < 12 (n log n + n log(12/e) )
69
Shapiro's Tauberian Theorem
``` Let {a(n)} be a non-negative sequence such that βˆ‘ a(n) [x/n] = x log x + O(x) n≀x for all x β‰₯ 1. Then (a) For x β‰₯ 1, we have βˆ‘ a(n) / n = log x + O(1) n≀x (b) There exists a constant B > 0 such that βˆ‘ a(n) ≀ Bx n≀x for all x β‰₯ 1. (c) There exists a constant A > 0 and an xβ‚€ > 0 such that βˆ‘ a(n) β‰₯ A(x) n≀x for all x β‰₯ xβ‚€ ```
70
Shapiro's Theorem on Ξ›(n)
``` For all x β‰₯ 1, we have βˆ‘ Ξ›(n) / n = log x + O(1) n≀x Also, there exist positive constants c₁ and cβ‚‚ such that βˆ‘ Ξ›(n) = πœ“(x) ≀ c₁x n≀x for all x β‰₯ 1 and βˆ‘ Ξ›(n) = πœ“(x) β‰₯ cβ‚‚x n≀x for all sufficiently large x. ```
71
Shapiro's Theorem on ΞΈ(n)
``` For all x β‰₯ 1, we have βˆ‘ log p / p = log x + O(1) p≀x Also, there exist positive constants c₁ and cβ‚‚ such that βˆ‘ Λ₁(n) = ΞΈ(x) ≀ c₁x n≀x for all x β‰₯ 1 and βˆ‘ Λ₁(n) = ΞΈ(x) β‰₯ cβ‚‚x n≀x for all sufficiently large x. Here, Λ₁(n) = log p if n is a prime p 0 otherwise ```
72
βˆ‘ πœ“(x/n) and βˆ‘ ΞΈ(x/n) | n≀x n≀x
``` We have βˆ‘ πœ“(x/n) = x log x - x + O(log x) n≀x and βˆ‘ ΞΈ(x/n) = x log x + O(x) n≀x ```
73
An asymptotic formula for the partial sums βˆ‘ 1/p p≀x
There is a constant A such that βˆ‘ 1/p = log log x + A + O(1 / log x) p≀x for all x β‰₯ 2.
74
Relating M(x) to the PNT
``` We have lim ( M(x) / x - H(x) / (x log x) ) = 0 xβ†’βˆž Hence the PNT implies lim ( M(x) / x ) = 0 xβ†’βˆž Also, M(x) = o(x) as x ⟢ ∞ implies πœ“(x) ∼ x as x ⟢ ∞ and so lim ( M(x) / x ) = 0 xβ†’βˆž also implies the PNT. ```
75
Relating βˆ‘ πœ‡(n) / n n≀x to the PNT
``` If A(x) = βˆ‘ πœ‡(n) / n n≀x the relation A(x) = o(1) as x ⟢ ∞ implies the PNT. In other words, the PNT is a consequence of the statement that ∞ βˆ‘ πœ‡(n) / n n≀x converges and has sum 0. ```
76
Selberg's Asymptotic Formula
For x > 0, we have πœ“(x) log x + βˆ‘ Ξ›(n) πœ“(x/n) = 2x log x + O(x) n≀x
77
Deducing Selberg's Asymptotic Formula
Let F be a real or complex valued function defined on (0, +∞), and let G(x) = log x βˆ‘ F(x/n) n≀x Then F(x) log x + βˆ‘ F(x/n) Ξ›(n) = βˆ‘ πœ‡(d) G(x/d) n≀x d≀x
78
If N β‰₯ 1 and 𝜎 β‰₯ c > πœŽβ‚, what is ∞ | βˆ‘ f(n) / n⁻˒ | n=N
If N β‰₯ 1 and 𝜎 β‰₯ c > πœŽβ‚, we have ∞ ∞ | βˆ‘ f(n) / n⁻˒ | ≀ N^-(𝜎 - c) βˆ‘ |f(n)| / nᢜ n=N n=N
79
For a Dirichlet series F(n), what is lim F(𝜎 + it) πœŽβ†’+∞
``` Let ∞ F(s) = βˆ‘ f(n) / nΛ’ n=1 Then lim F(𝜎 + it) = f(1) πœŽβ†’+∞ uniformly for -∞ < t < ∞ ```
80
Uniqueness Theorem
Given 2 Dirichlet series ∞ ∞ F(s) = βˆ‘ f(n) / nΛ’ and G(s) = βˆ‘ g(n) / nΛ’ n=1 n=1 both absolutely convergent for 𝜎 > πœŽβ‚, if F(s) = G(s) for each s is an infinite sequence {sβ‚–} such that πœŽβ‚– ⟢ ∞ as k ⟢ ∞, then f(n) = g(n) for all n.
81
Half-planes with F(s) never zero
``` Let F(s) = βˆ‘ f(n) / nΛ’ and assume that F(s) β‰  0 for some s with 𝜎 > πœŽβ‚. Then there is a half-plane 𝜎 β‰₯ c > πœŽβ‚ in which F(s) is never zero. ```
82
Dirichlet convolution in half-plane of convergence
Given two functions F(s) and G(s) represented by Dirichlet series ∞ ∞ F(s) = βˆ‘ f(n) / nΛ’ for 𝜎>a and G(s) = βˆ‘ g(n) / nΛ’ for 𝜎>b n=1 n=1 In the half-plane where both series converge absolutely, we have ∞ F(s) G(s) = βˆ‘ h(n) / nΛ’ n=1 where h = f βˆ— g, the Dirichlet convolution of f and g: h(n) = βˆ‘ f(d) g(n/d) d|n Conversely, if F(s)G(s) = βˆ‘ 𝛼(n)/nΛ’ for all s in a sequence {sβ‚–} with πœŽβ‚– ⟢ ∞ as k ⟢ ∞, then 𝛼 = f βˆ— g.
83
Euler Product
Let f be a multiplicative arithmetical function such that the series βˆ‘f(n) is absolutely convergent. Then the sum of the series can be expressed as an absolutely convergent infinite product ∞ βˆ‘ f(n) = ∏ (1 + f(p) + f(pΒ²) + ...) n=1 p extended over all primes. If f is completely multiplicative, then ∞ βˆ‘ f(n) = ∏ 1 / (1 - f(p)) n=1 p
84
Product formulae for Dirichlet series in half plane of convergence
Assume βˆ‘ f(n)/nΛ’ converges absolutely for 𝜎 > πœŽβ‚. If f is multiplicative, we have ∞ βˆ‘ f(n) / nΛ’ = ∏ (1 + f(p)/pΛ’ + f(pΒ²)/pΒ²Λ’ + ...) if 𝜎 > πœŽβ‚ n=1 p and if f is completely multiplicative, we have ∞ βˆ‘ f(n) / nΛ’ = ∏ (1 - f(p)/p)⁻¹ if 𝜎 > πœŽβ‚ n=1
85
Modulus of Dirichlet series with bounded partial sums
Let sβ‚€ = πœŽβ‚€ + itβ‚€ and assume that the Dirichlet series βˆ‘ f(n)/n˒⁰ has bounded partial sums, say | βˆ‘ f(n) / n˒⁰ | ≀ M n≀x for all x β‰₯ 1. Then for each 𝜎 > πœŽβ‚€, we have | βˆ‘ f(n) / nΛ’ | ≀ 2Ma^(πœŽβ‚€ - 𝜎) (1 + (|s - sβ‚€|) / (𝜎 - πœŽβ‚€) ) a
86
Convergent/ divergent Dirichlet series for s = πœŽβ‚€ + itβ‚€
If the series βˆ‘ f(n)/nΛ’ converges for s = πœŽβ‚€ + itβ‚€, then it also converges for all s with 𝜎 > πœŽβ‚€. If it diverges for s = πœŽβ‚€ + itβ‚€, then it diverges for all s with 𝜎 < πœŽβ‚€.
87
Bounds on πœŽβ‚ and 𝜎_c
For any Dirichlet series with 𝜎_c finite, we have | 0 ≀ πœŽβ‚ - 𝜎_c ≀ 1
88
πœŽβ‚ and 𝜎_c on ∞ βˆ‘ (-1)ⁿ / nΛ’ n=1
``` The series ∞ βˆ‘ (-1)ⁿ / nΛ’ n=1 converges if 𝜎 > 0 but only converges absolutely for πœŽβ‚ = 1. Therefore 𝜎_c = 0 and πœŽβ‚ = 1. ```
89
Analytic functions
Let {fβ‚™} be a sequence of functions analytic on an open subset S of the complex plane, and assume that {fβ‚™} converges uniformly on every compact subset of S to a limit function f. Then f is analytic on S and the sequence of derivatives {fβ‚™'} converges uniformly on every compact subset of S to the derivative of f'.
90
Dirichlet series on compact rectangles
A Dirichlet series converges uniformly on every compact rectangle lying interior to the half-plane of convergence 𝜎 > 𝜎_c.
91
Derivative of Dirichlet series
``` The sum function ∞ F(s) = βˆ‘ f(n) / nΛ’ n=1 of a Dirichlet series is analytic in its half-plane of convergence 𝜎 > 𝜎_c and its derivative F'(s) is represented in this half-plane by the Dirichlet series ∞ F'(s) = - βˆ‘ (f(n) log n) / nΛ’ n=1 obtained by differentiating term by term ```
92
Landau's Theorem
Let F(s) be represented in the half-plane 𝜎 > c by the Dirichlet series ∞ F(s) = βˆ‘ f(n) / nΛ’ n=1 where c is finite and assume f(n) β‰₯ 0 for all n β‰₯ nβ‚€. If F(s) is analytic in some disc about the point s = c, then the Dirichlet series converges in the half-plane 𝜎 > c - πœ€ for some πœ€ > 0. Consequently, if the Dirichlet series has a finite abscissa of convergence 𝜎_c, then F(s) has a singularity on the real axis at the point s = 𝜎_c.
93
Half-plane of a Dirichlet series as an exponential
Let F(s) = βˆ‘ f(n)/nΛ’ be absolutely convergent for 𝜎 > πœŽβ‚ and assume that f(1) β‰  0. If F(s) β‰  0 for 𝜎 > πœŽβ‚€ > πœŽβ‚, then for 𝜎 > πœŽβ‚€ we have F(s) = exp( G(s) ) with ∞ G(s) = log(f(1)) + βˆ‘ (f' βˆ— f⁻¹)(n) / ( (log n)nΛ’ ) n=1 where f⁻¹ is the Dirichlet inverse of f and f'(n) = f(n) log n.
94
∞ βˆ‘ f(n) g(n) / n^(a+b) n=1
Given two Dirichlet series F(s) = βˆ‘ f(n)/nΛ’ and G(s) = βˆ‘ g(n)/nΛ’ with abscissae of absolute convergence πœŽβ‚ and πœŽβ‚‚ respectively. Then for a > πœŽβ‚ and b > πœŽβ‚‚ we have T ∞ lim (1 / 2T) ∫ F(a + it) G(b - it) dt = βˆ‘ f(n) g(n) / n^(a+b) Tβ†’βˆž -T n=1
95
If F(s) = βˆ‘ f(n)/nΛ’ converges absolutely for 𝜎 > πœŽβ‚, then for 𝜎 > πœŽβ‚ we have T ∞ lim (1 / 2T) ∫ |F(𝜎 + it)|Β² dt = βˆ‘ |f(n)|Β² / n^(2𝜎) Tβ†’βˆž -T n=1 In particular, if 𝜎 > 1, we have (a) T ∞ lim (1 / 2T) ∫ |ΞΆ(𝜎 + it)|Β² dt = βˆ‘ 1 / n^(2𝜎) = ΞΆ(2𝜎) Tβ†’βˆž -T n=1 (b) T ∞ lim (1 / 2T) ∫ |΢⁽ᡏ⁾(𝜎 + it)|Β² dt = βˆ‘ log²ᡏ(n) / n^(2𝜎) = ΢⁽²ᡏ⁾(2𝜎) Tβ†’βˆž -T n=1 (c) T ∞ lim (1 / 2T) ∫ |ΞΆ(𝜎 + it)|⁻² dt = βˆ‘ πœ‡Β²(n) / n^(2𝜎) = ΞΆ(2𝜎) / ΞΆ(4𝜎) Tβ†’βˆž -T n=1 (d) T ∞ lim (1 / 2T) ∫ |ΞΆ(𝜎 + it)|⁴ dt = βˆ‘ dΒ²(n) / n^(2𝜎) = ΢⁴(2𝜎) / ΞΆ(4𝜎) Tβ†’βˆž -T n=1
96
Integral formula for coefficients of a Dirichlet series
Assume the series F(s) = βˆ‘ f(n)/nΛ’ converges absolutely for 𝜎 > πœŽβ‚ Then for 𝜎 > πœŽβ‚ and x > 0 we have T lim (1 / 2T) ∫ F(𝜎 + it) x^(𝜎 + it) dt = f(n) if x = n Tβ†’βˆž -T 0 otherwise
97
What is c+i∞ 1 / 2πœ‹i ∫ aαΆ» / z dz c-i∞
Let c > 0 and a be any postitive real number. Then we have c+i∞ 1 if a > 1 1 / 2πœ‹i ∫ aαΆ» / z dz = 1/2 if a = 1 c-i∞ 0 if 0 < a < 1 Moreover, we have c+iT | 1 / 2πœ‹i ∫ aαΆ» / z dz | ≀ a Ν¨ / (πœ‹ T log(1/a)) if 0 < a < 1 c-iT c+iT | 1 / 2πœ‹i ∫ 1/z dz - 1/2 | ≀ c / πœ‹T if a = 1 c-iT c+iT | 1 / 2πœ‹i ∫ aαΆ» / z dz - 1 | ≀ a Ν¨ / (πœ‹ T log a) if a > 1 c-iT
98
Perron's Formula
Let F(s) = βˆ‘ f(n)/nΛ’ be absolutely convergent for 𝜎 > πœŽβ‚, and let c > 0 and x > 0 be arbitrary. Then if 𝜎 > πœŽβ‚ - c, we have c+i∞ βˆ— 1 / 2πœ‹i ∫ F(s + z) xαΆ» / z dz = βˆ‘ f(n) / nΛ’ c-i∞ n≀x where βˆ‘* means that the last term in the sum must be multiplies by 1/2 when x is an integer.
99
Perron's Formula for s = 0
If c > πœŽβ‚ Perron's Formula is valid for s = 0 and we obtain the following integral representation for the partial sum of the coefficients: c+i∞ βˆ— 1 / 2πœ‹i ∫ F(z) xαΆ» / z dz = βˆ‘ f(n) c-i∞ n≀x
100
Riemann-zeta function for 𝜎 > 0, x > 0 and s β‰  1.
Suppose that 𝜎 > 0, x > 0 and s β‰  1. Then for N an integer, we have ∞ ΞΆ(s) = βˆ‘ 1 / nΛ’ + N¹⁻˒ / (s - 1) - s ∫ {t} / t˒⁺¹ dt n≀N N
101
Poles of the Riemann-zeta function
The Riemann-zeta function has a simple pole at s = 1 with residue 1, but is otherwise analytic in the half-plane 𝜎 > 0.
102
Properties of the gamma function
For 𝜎 > 0, we have that sπšͺ(s) = πšͺ(s + 1). Moreover πšͺ(1) = 1 and πšͺ(n) = (n - 1)! for all n ∈ N.
103
Poles of the gamma function
The function πšͺ(s) has an analytic continuation as a meromorphic function on C, the only singularities being at s = -k ∈ Z ≀ 0. These singularities are simple poles with residues (-1)ᡏ / k!.
104
Representations of the gamma function
πšͺ(s) = lim (nΛ’ n!) / s(s + 1) ... (s + n) for s β‰  0, -1, -2, ... ∞ 1 / πšͺ(s) = s exp(𝛾s) ∏ (1 + s/n) exp(-s/n) for all s n=1
105
Functional equation for the gamma function
πšͺ(s) πšͺ(1 - s) = πœ‹ / sin(πœ‹s) for all s
106
Multiplication formula for the gamma equation
For all s and all integers m β‰₯ 1, we have | πšͺ(s) πšͺ(s + 1/m) ... πšͺ(s + (m-1)/m) = (2πœ‹)^((m-1)/2) m^(1/2 - ms) πšͺ(ms)
107
Functional equation for the Riemann-zeta function
For all s, we have | ΞΆ(s) = 2 (2πœ‹)˒⁻¹ πšͺ(1 - s) sin(πœ‹s / 2) ΞΆ(1 - s)
108
Riemann Hypothesis
If 0 < Re(s) < 1 and ΞΆ(s) = 0, then Re(s) = 1/2
109
βˆ‘ (x - n) a(n) | n≀x
For any arithmetical function a(n), let A(x) = βˆ‘ a(n) (n≀x) where A(x) = 0 if x < 1. Then x βˆ‘ (x - n) a(n) = ∫ A(t) dt n≀x 1
110
L'Hopital's Rule for increasing linear piecewise functions
Let A(x) = βˆ‘ a(n) (n≀x) and let A₁(x) = βˆ«β‚Λ£ A(t) dt. Assume a(n) β‰₯ 0 for all n. If we have the asymptotic formula A₁(x) ∼ Lxᢜ as x ⟢ ∞ for some c > 0 and L > 0, then we have A(x) ∼ cLxᢜ⁻¹ as x ⟢ ∞
111
L'Hopital's rule on πœ“(x)
We have πœ“β‚(x) = βˆ‘ (x - n) Ξ›(n) n≀x and the asymptotic formula πœ“β‚(x) ∼ 1/2 xᢜ as x ⟢ ∞ implies πœ“(x) ∼ x as x ⟢ ∞
112
For c > 0, u > 0, for every k β‰₯ 1, what is c+i∞ 1 / 2πœ‹i ∫ u⁻ᢻ / (z (z + 1) ... (z +k)) dz c-i∞
If c > 0 and u > 0, then for every integer k β‰₯ 1, we have c+i∞ 1 / 2πœ‹i ∫ u⁻ᢻ / (z (z + 1) ... (z +k)) dz = (1 / k!) (1 - u)ᡏ if 0 < u ≀ 1 c-i∞ 0 if u > 1 the integral being absolutely convergent.
113
Contour integral representation for πœ“β‚(x) / xΒ²
If c > 1 and x β‰₯ 1, we have c+i∞ πœ“β‚(x) / xΒ² = 1 / 2πœ‹i ∫ x˒⁻¹ / s(s + 1) (- ΞΆ'(s) / ΞΆ(s) ) ds c-i∞
114
Contour integral representation for πœ“β‚(x) / xΒ² - 1/2 (1 - 1/x)Β²
If c > 1 and x β‰₯ 1, we have c+i∞ πœ“β‚(x) / xΒ² - 1/2 (1 - 1/x)Β² = 1 / 2πœ‹i ∫ x˒⁻¹ h(s) ds c-i∞ where h(s) = 1 / s(s + 1) (- ΞΆ'(s) / ΞΆ(s) - 1 / (s - 1) )
115
Upper bounds for |΢(s)| and |΢'(s)| near the line 𝜎 = 1
For every A > 0, there exists a constant M (depending on A) such that |ΞΆ(s)| ≀ M log t and |ΞΆ'(s)| ≀ M logΒ² t for all s with 𝜎 β‰₯ 1/2 satisfying 𝜎 > 1 - A / log t and t β‰₯ e
116
Riemann-zeta formula β‰₯ 1 for 𝜎 > 1
If 𝜎 > 1, we have | ΞΆΒ³(𝜎) |ΞΆ(𝜎 + it)|⁴ |ΞΆ(𝜎 + 2it)| β‰₯ 1
117
Non-vanishing of ΞΆ(1 + it)
We have ΞΆ(1 + it) β‰  0 for every real t
118
Inequalities for | 1 / ΞΆ(s) | and | ΞΆ'(s) / ΞΆ(s) |
``` There is a constant M > 0 such that | 1 / ΞΆ(s) | < M log⁷ t and | ΞΆ'(s) / ΞΆ(s) | < M log⁹ t whenever 𝜎 β‰₯ 1 and t β‰₯ e. ```
119
First Order Poles of f'(s) / f(s)
If f(s) has a pole of order k at s = 𝛼, then the quotient f'(s) / f(s) has a first order pole at s = 𝛼 with residue -k.
120
Where is F(s) = - ΞΆ'(s) / ΞΆ(s) - 1 / (s - 1) analytic?
The function F(s) = - ΞΆ'(s) / ΞΆ(s) - 1 / (s - 1) is analytic at s = 1.
121
Formula for πœ“(x) ∼ x
For x β‰₯ 1, we have ∞ πœ“β‚(x) / xΒ² - 1/2 (1 - 1/x)Β² = 1 / 2πœ‹ ∫ h(1 + it) exp(it log x) dt -∞ where the integral ∞ ∫ | h(1 + it) | dt -∞ converges. Therefore, by the Riemann-Lebesgue Lemma, we have πœ“β‚(x) ∼ 1/2 xΒ² and hence πœ“(x) ∼ x as x ⟢ ∞
122
Zero-free regions for ΞΆ(s)
Assume 𝜎 β‰₯ 1/2. Then there exist constants A > 0 and C > 0 such that | ΞΆ(𝜎 + it) | > C / log⁷ t whenever 1 - A / log⁹ t < 𝜎 ≀ 1 and t β‰₯ e This implies that ΞΆ(𝜎 + it) β‰  0 for such 𝜎 and t.
123
Number of Dirichlet characters
There are exactly πœ™(k) distinct Dirichlet characters modulo k.
124
Number of Dirichlet characters
There are exactly πœ™(k) distinct Dirichlet characters modulo k.
125
Properties of Dirichlet characters
Let k be a positive integer. (i) Then we have that 𝝌(n) = 0 or 𝝌(n) = exp(2πœ‹in / πœ™(k)) for some m ∈ N. (ii) Let (n, k) = 1. Then the inverse of a Dirichlet character 𝝌 modulo k is given by the complex conjugate 𝝌 bar which is defined by _ ___ 𝝌(n) = 𝝌(n) Furthermore, 𝝌 bar is also a Dirichlet character modulo k.
126
Sums over 𝝌(n)
Let k N. Then we have (i) k βˆ‘ 𝝌(n) = πœ™(k) if 𝝌 = πŒβ‚€ n=1, (n,k)=1 0 if 𝝌 β‰  πŒβ‚€ (i) βˆ‘ 𝝌(n) = πœ™(k) if n ≑ 1 mod k 𝝌 mod k 0 otherwise
127
What is _ | βˆ‘ 𝝌ᡣ(m) 𝝌ᡣ(n)
Let πŒβ‚€, ..., 𝝌_(πœ™(k) - 1) denote the Dirichlet characters modulo k, where k ∈ N. Let m, n ∈ Z such that (n, k) = 1. Then we have πœ™(k)-1 _ βˆ‘ 𝝌ᡣ(m) 𝝌ᡣ(n) = πœ™(k) if m ≑ n mod k r=0 0 otherwise
128
βˆ‘ 𝝌(n) f(n)
Let 𝝌 be any non-principal character modulo k and let f be a non-negative function which has a continuous negative derivative f'(x) for all x β‰₯ xβ‚€. Then if y β‰₯ x β‰₯ xβ‚€, we have βˆ‘ 𝝌(n) f(n) = O(f(x)) where we sum over x < n ≀ y. If in addition f(x) ⟢ 0 as x ⟢ ∞, then the infinite series ∞ βˆ‘ 𝝌(n) f(n) n=1 converges, and we have, for x β‰₯ xβ‚€, ∞ βˆ‘ 𝝌(n) f(n) = βˆ‘ 𝝌(n) f(n) + O(f(x)) n≀x n=1
129
βˆ‘ 𝝌(n) / n
If 𝝌 is any non-principal character modulo k and if x β‰₯ 1, we have ∞ βˆ‘ 𝝌(n) / n = βˆ‘ 𝝌(n) / n + O(1 / x) n≀x n=1
130
βˆ‘ (𝝌(n) log n) / n
If 𝝌 is any non-principal character modulo k and if x β‰₯ 1, we have ∞ βˆ‘ (𝝌(n) log n) / n = βˆ‘ (𝝌(n) log n) / n + O((log x) / x) n≀x n=1
131
βˆ‘ 𝝌(n) / √n
If 𝝌 is any non-principal character modulo k and if x β‰₯ 1, we have ∞ βˆ‘ 𝝌(n) / √n = βˆ‘ 𝝌(n) / √n + O(1 / √x) n≀x n=1
132
A(n) = βˆ‘ 𝝌(d) | d|n
Let 𝝌 be any real-valued character modulo k and let A(n) = βˆ‘ 𝝌(d) d|n Then A(n) β‰₯ 0 for all n and A(n) β‰₯ 1 if n is a square.
133
Properties of B(n) such that A(n) = βˆ‘ 𝝌(d) and B(n) = βˆ‘ A(n) / √n d|n n≀x
For any real-valued non-principal character 𝝌 modulo k, let A(n) = βˆ‘ 𝝌(d) and B(n) = βˆ‘ A(n) / √n d|n n≀x Then (a) B(x) ⟢ ∞ as x ⟢ ∞. (b) B(x) = 2√x L(1, 𝝌) + O(1) for all x β‰₯ 1
134
When is L(1, 𝝌) nonzero?
For any real-valued non-principal character 𝝌 modulo k, we have L(1, 𝝌) β‰  0.
135
``` Formula for βˆ‘ log p / p p≀x p≑h mod k if k > 0 and (h, k) = 1 ```
If k > 0 and (h, k) = 1, we have for all x > 1, βˆ‘ log p / p = (1 / πœ™(k)) log x + O(1) p≀x p≑h mod k where the sum is extended over those primes p ≀ x which are congruent to h mod k.
136
``` Formula for βˆ‘ log p / p p≀x p≑h mod k for all x > 1 in terms of characters ```
For x > 1, we have βˆ‘ log p / p = (1 / πœ™(k)) log x p≀x πœ™(k)-1 _ p≑h mod k + (1 / πœ™(k)) βˆ‘ 𝝌ᡣ(h) βˆ‘ 𝝌ᡣ(p) log p / p r=1 p≀x + O(1)
137
Formula for βˆ‘ log p / p p≀x for all x > 1
For each x > 1 and 𝝌 β‰  πŒβ‚€, we have βˆ‘ 𝝌(p) log p / p = - L'(1, 𝝌) βˆ‘ πœ‡(n) 𝝌(n) / n + O(1) p≀x p≀x
138
Size of L(1, 𝝌) βˆ‘ πœ‡(n) 𝝌(n) / n n≀x
For x > 1 and 𝝌 β‰  πŒβ‚€, we have L(1, 𝝌) βˆ‘ πœ‡(n) 𝝌(n) / n β‰ͺ 1 n≀x
139
Formula for L'(1, 𝝌) βˆ‘ πœ‡(n) 𝝌(n) / n n≀x
If 𝝌 β‰  πŒβ‚€ and L(1, 𝝌) = 0, we have L'(1, 𝝌) βˆ‘ πœ‡(n) 𝝌(n) / n = log x + O(1) n≀x
140
``` Formula for βˆ‘ log p / p p≀x p≑h mod k for all x > 1 in terms of number of characters ```
Let N(k) denote the number of non-principal characters 𝝌 modulo k such that L(1, 𝝌) = 0. For x > 1, we have βˆ‘ log p / p = ( (1 - N(k)) / πœ™(k) ) log x + O(1) p≀x p≑h mod k
141
Prime Number Theorem for arithmetic progressions
For (a, k) = 1, we have πœ‹β‚(x) ∼ πœ‹(x) / πœ™(k) ∼ (1 / πœ™(k)) (x / log x) as x ⟢ ∞.
142
Alternative formulation for the PNT for arithmetic progressions
If the relation πœ‹β‚(x) ∼ πœ‹(x) / πœ™(k) as x ⟢ ∞ holds for every integer a relatively prime to k, then πœ‹β‚(x) ∼ πœ‹_b(x) as x ⟢ ∞ whenever (a, k) = (b, k) = 1. The converse is also true.
143
Size of integral of a continuous function on a contour
Consider a contour 𝛾 and a continuous function f defined on 𝛾. Suppose that |f(z)| ≀ M for all z on 𝛾. Then | ∫ f(z) dz | ≀ ML 𝛾 where L is the length of 𝛾.
144
Cauchy's Integral Formula
Let U be a domain. Let 𝛾 be a positively oriented simple closed contour with its image and interior lying entirely within U. Suppose that a is a point in the interior of 𝛾. If f is holomorphic on U, then f(a) = 1 / 2πœ‹i ∫ f(z) / (z - a) dz 𝛾
145
Laurent's Theorem
If f is holomorphic on an annulus A = {z ∈ C : R < |z - a| < S} for 0 ≀ R < s. Then there exists a sequence (bβ‚™), n ∈ Z, of complex numbers such that ∞ f(z) = βˆ‘ bβ‚™(z - a)ⁿ n=-∞ for every z ∈ A. Such a series is referred to as a Laurent series. Moreover for any r with R < r < S and for any n ∈ Z, if 𝛾 is a circular closed contour with centre a and radius r, then bβ‚™ = 1 / 2πœ‹i ∫ f(w) / (w - a)ⁿ⁺¹ dw 𝛾
146
Cauchy's Residue Theorem
If 𝛾 is a closed contour traversed anticlockwise, if f is a function which is holomorphic on a domain containing the image and interior of 𝛾, except for a finite number of isolated singularities on the interior (call them a₁, ..., aβ‚–), then k ∫ f(z) dz = 2πœ‹i βˆ‘ Res(f, a) 𝛾 j=1