Mobius Inversion Formula, Zeta Functions

Lecture 14 Mobius Inversion Formula, Zeta Functions Recall: Mobius function µ(n) and other functions ( (−1)ω(n) µ(n) = 0 if n is squarefree if n is not squarefree ω(n) = number of primes dividing n U (n) = 1 ∀ n ( 1 n=1 1(n) = 0 n>1 µ∗U =U ∗µ=1 ( X 1 n=1 µ(d) = 0 n>1 d|n Theorem 54. Let f be an Parithmetic nfunction, P and nF = f ∗ U , so that F (n) = P d|n f (d). Then f (n) = d|n µ(d)F ( d ) = d|n µ( d )F (d). Proof. F =f ∗U F ∗ µ = (f ∗ U ) ∗ µ = f ∗ (U ∗ µ) =f ∗1=f  Theorem 55. If f and F are arithmetic functions and f (n) = P n, then F (n) = d|n f (d) for all n P d|n µ(d)F ( nd ) for all Proof. f =µ∗F =F ∗µ f ∗U =F  1 Showed last time that φ ∗ U = r1 (Recall that r1 (n) = n1 and and so Mobius inversion says that φ(n) = X d|n µ(d) P d|n φ(d) = n), X µ(d) n =n d d d|n n = pe11 pe22 . . . perr   1 1 1 1 1 1 (−1)r =n 1− ··· − + + ··· + − ··· + p1 pr p1 p2 p1 p3 pr−1 pr p1 p2 p3 p1 . . . pr      1 1 1 =n 1− 1− ... 1 − p1 p2 pr  Y 1 =n 1− p r|n Eg. There are 100 consecutive doors in a castle that are all closed. Person 1 opens all doors, person n changes state of every nth door, starting with door number n. At the end, which doors will be open? Door number n changes state d(n) number of times at the end, door n open if d(n) is odd. n = pe11 pe22 . . . perr d(n) = (e1 + 1)(e2 + 1) . . . (er + 1) d(n) odd if all e are even ⇒ at the end, open doors are 1, 4, 9, 16 . . . Eg. Describe the arithmetic function µ ∗ µ - ie., given n = pe11 pe22 . . . perr , what is (µ ∗ µ)(n). Since µ ∗ µ is multiplicative, it is enough to know it for a prime power pe . (µ ∗ µ)(n) = X  µ(d)µ d|pe = X pe d  µ(pi )µ(pe−i ) 0≤i≤e = µ(pe ) + µ(p)µ(pe−1 ) + µ(p2 )µ(pe−2 ) + · · · + µ(pe−1 )µ(p) + µ(pe ) Claim that if e ≥ 3, then (µ ∗ µ)(pe ) = 0 because for 0 ≤ i ≤ e, since i + (e − i) = e ≥ 3, one is ≥ 2 so µ(pi ) or µ(pe−i ) is 0, so all terms vanish. 2 e=0 e=1 (µ ∗ µ)(1) (µ ∗ µ)(p) e=2 (µ ∗ µ)(p2 ) = µ(1)µ(1) = 1 = µ(p) + µ(p) = −2 = µ(p2 ) + µ(p)µ(p) + µ(p2 ) = 1   0 ( (µ ∗ µ)(n) = Qr −2 e1 = 1   i=1 1 e1 = 2 P ei ≥ 3 otherwise (0 unless n is cube-free) Conjecture 56 (Mertens Conjecture). Consider the function M (n) = - how fast does this grow? P Mertens and Stieltjes independently conjectured that |M (n)| < would imply the Riemann Hypothesis. The claim that for every ε > 0, M (n) 1 n 2 +ε 1≤k≤n µ(k) √ n, which ⇒ 0 as n ⇒ ∞ is equivalent to Riemann Hypothesis. The strong form was disproved in 1985. The idea is that P M (n) is a sum of ±1 or 0 terms, expect massive cancelation. If we looked at µ(k) of only squarefree k only divisible by primes ≤ n, this sum would be (1 + µ(2))(1 + µ(3)) . . . (1 + µ(φk )) = (1 − 1)(1 − 1) · · · = 0 However, this sum includes a lot more integers than just 1 . . . n Zeta Functions - analogue of a generating function. Suppose we have sequence a0 , a1 . . . indexed by positive integers. We introduce generating function A(x) = a0 + a1 x + a2 x2 · · · = ∞ X an xn n=0 Can think of x ∈ R or C close to 0, if an ’s don’t grow too fast, will converge to a function of x in some small region around 0. 3 Eg. a0 , a1 · · · = 1 then A(x) = 1 + x + x2 · · · = 1 1−x Eg. an = 2n + 1 = 2, 3, 5, 9, 17 . . . , then X X an xn = (1 + 2n )xn X X = xn + (2x)n = 1 1 + 1 − x 1 − 2x We’re interested in multiplicative structure, we’ll use a different kind of generating function. Let f (n) be an arithmetic function, s a formal variable - eg, s ∈ C. Define Z(f, s) = X f (n) ns n≥1 It does make sense to talk about when it converges, note that if f (n) doesn’t grow too fast, say |f (n)| ≤ nm for some constant m, then sum converges for −(1+ε) ) < (s) > m + 1 (because | fn(n) s | < n Eg. One of the simplest arithmetic functions is U (n) = 1 ∀ n. Then X 1 Z(U, s) = = ζ(s) ns n≥1 which is called the Riemann Zeta Function. Tightly connected with distribution of prime numbers. ζ(s) has an Euler Product. First,     X 1 1 1 1 1 1 1 = 1 + s + s + s ... 1 + s + s ... 1 + s ... ... n2 2 4 8 3 9 5 n≥1 1 1 1 ... 1 − 21s 1 − 31s 1 − 51s Y ζ(s) = (1 − p−s )−1 = p prime This factorization is called an Euler Product Eg. 1 is even simpler Z(1, s) = X 1(n) =1 ns n≥1 4 Eg. ζ(s)−1 = Y (1 − p−s ) pprime = X µ(n) ns n≥1 = Z(µ, s) Note Z(f ∗ g, s) = Z(f, s)Z(g, s) ⇒ 1 = Z(1, s) = Z(U, s) Z(µ, s) | {z } ζ(s) In general, if f (n) is multiplicative, then X f (n) ns n≥1  Y  f (p) f (p2 ) f (p3 ) = 1 + s + 2s + 3s . . . p p p Z(f, s) = p prime and if f is completely multiplicative then f (pe ) = f (p)e , then Y 1 Z(f, s) = f (p) p prime 1 − ps Y = (1 − f (p)p−s )−1 p prime Some neat facts: 1. ζ(2) = X 1 π2 = 2 n 6 n≥1 ”Proof”. Use    x2 x2 x2 1− 2 1− 2 1 − 2 ... π 4π 9π 3 5 7 x x x sin x = x − + − ... 3! 5! 7! 2 4 6 sin x x x x =1− + − ... x 3! 5! 7! sin x = x  5 so 1− x2 x4 x6 + − ··· = 3! 5! 7!  1− x2 π2    x2 x2 1 − 2 ... 1− 2 9π 4π Look at coefficient of x2 : 1 1 1 1 = − 2 − 2 − 2 ... 6 π 4π 9π X 1 π2 = 6 n2 −  2. Look at coefficient of x4 to get 1 1 X 1 = 4 120 π 0 < i < j i2 j 2 X 0 < i < j Adding ζ(4) = P 1 i4 1 π4 = i2 j 2 120 we get X 1 X 1 π4 + 2 = ζ(4) + i4 i2 j 2 60 X 2 X 1 X 1 1 +2 = = ζ(2)2 i4 i2 j 2 i2  2 2 π4 π π4 ζ(4) + = = 60 6 36 π4 ζ(4) = 90 3. Probability of a random number being squarefree: number of squarefree integers ≤ x 6 → 2 as x → ∞ x π ”Proof”. ζ(2) = = π2 6 Y p 1 1 − p12  Y 1 6 ⇒ 1− 2 = 2 p π p Probability that random number divisible by p2 ≈ Q With ”independence” ⇒ p (1 − p12 ) = π62 6 1 p2 , probability not ≈ 1 − 1 p2 .  4. Probability that 2 random integers are coprime is 6 π2 5. Probability that 4 integers a, b, c, d satisfy (a, b) = (c, d) is 40% 7