Lecture 13 Arithmetic Functions ¨ Today - Arithmetic functions, the Mobius function (Definition) Arithmetic Function: N→C An arithmetic function is a function f : Eg. π(n) = d(n) = σ(n) = σk (n) = ω(n) = Ω(n) = the number of primes ≤ n the number of positive divisors of n the sum of the positive divisors of n the sum of the kth powers of n the number of distinct primes dividing n the number of primes dividing n counted with multiplicity Eg. σ(1) = 1 σ(2) = 1 + 2 = 3 σ(3) = 1 + 3 = 4 σ(6) = 1 + 2 + 3 + 6 = 12 (Definition) Perfect Number: A perfect number n is one for which σ(n) = 2n (eg., 6, 28, 496, etc.) Big open conjecture: Every perfect number is even. Note: One can show that if n is an even perfect number, then n = 2m−1 (2m − 1) where 2m − 1 is a Mersenne prime (Euler) (Definition) Multiplicative: If f is an arithmetic function such that whenever (m, n) = 1 then f (mn) = f (m)f (n), we say f is multiplicative. If f satisfies the stronger property that f (mn) = f (m)f (n) for all m, n (even if not coprime), we say f is completely multiplicative Eg. ( 1 n=1 f (n) = 0 n<1 is completely multiplicative. It’s sometimes called 1 (we’ll see why soon). Eg. f (n) = nk for some fixed k ∈ N is also completely multiplicative Eg. ω(n) is not multiplicative (adds, but 2ω(n) is multiplicative) Eg. φ(n) is multiplicative (by CRT) Note: If f is a multiplicative function, then to know f (n) for all n, it suffices to know f (n) for prime powers n. This is why we wrote Y pei i −1 (pi − 1) φ(pe11 . . . perr ) = (Definition) Convolution: The convolution of two arithmetic functions f and g is f ∗ g defined by n X (f ∗ g)(n) = f (d)g d d|n (summing over positive divisors of n). Compare this to convolution from calculus or differential equations Z ∞ (f ∗ g)(x) = f (t)g(x − t)dt t=−∞ Z x or f (t)g(x − t)dt if f (y), g(y) are 0 for y < 0 t=0 Eg. f ∗ 1 = 1 ∗ f = f for every f (check 1) 1 is the identity for convolution Theorem 48. If f and g are multiplicative then f ∗ g is multiplicative. Proof. Suppose m and n are coprime. Then any divisor of mn is of the form d1 , d2 , where d1 |m and d2 |n, uniquely. So we have mn X (f ∗ g)(mn) = f (d)g d d|mn XX m n = f (d1 d2 )g · d1 d2 d1 |m d2 |n XX n m = f (d1 )f (d2 ) g g | {z } d1 d2 d1 |m d2 |n since (d ,d )=1 | {z } 1 2 since ( dm , dn )=1 1  = X f (d1 )g d1 |m 2  m  d1 X f (d2 )g d2 |n  n  d2 = (f ∗ g)(m)(f ∗ g)(n) Eg. Let U (n) = 1 for all n. Then for any arithmetic function f , we have n X X (f ∗ U )(n) = f (d) U = f (d) | {zd } d|n d|n =1 This is usually called F (n). If f is multiplicative, then F is multiplicative, by theorem (since U is obviously completely multiplicative) (that’s theorem 4.4 in the book). In particular, we compute U ∗ U X (U ∗ U )(n) = 1 · 1 = number of divisors of n = d(n) d|n so d(n) is multiplicative. For a prime power pα , the number of divisors is α + 1. So d(pe11 . . . perr ) = r Y (ei + 1) i=1 For the function rk (n) = nk , we have (rk ∗ U )(n) = X d|n which is therefore multiplicative. dk = σk (n) Since σk (pα ) = 1 + pk + · · · + pkα = pk(α+1) − 1 pk − 1 we get σk Y r k(e +1) Y pi i −1 pei i = k pi − 1 i=1 Theorem 49. For any positive integer n, we have X φ(n) = n d|n In other words φ ∗ U = r1 . Proof. Since both sides are multiplicative, enough to show it for prime powers. r1 (pα ) = pα X φ(d) = φ(1) + φ(p) + · · · + φ(pα ) d|pα = 1 + (p − 1) + p(p − 1) + · · · + pα−1 (p − 1) = 1 + p − 1 + p2 − p + p3 − p2 + · · · + pα − pα−1 = pα Eg. What is rk ∗ rk ? (rk ∗ rk )(n) = X d|n dk n k d = X nk = nk d(n) d|n m n Other multiplicative functions: ( D ) since ( mn D ) = ( D )( D ) There’s an interesting multiplicative Q∞ function - let τ (n) (Ramanujan’s tau function) be the coefficient of q n in q i=1 (1 − q i )24 . Then τ (1) = 1 τ (2) = −24 τ (3) = 252 τ (6) = −6048 = −24 · 252 = τ (2)τ (3) etc. Theorem 50. τ (n) is multiplicative (deep) Proof uses modular forms. A famous open conjecture is Lehmer’s conjecture: τ (n) = 6 0 for every natural number n. Proposition 51. f ∗ g = g ∗ f for any arithmetic functions f, g (ie., convolution is commutative) Proof. (f ∗ g)(n) = X f (d)g d|n n d = d0 so we write X X n n X n n (f ∗ g)(n) = f (d0 )g( 0 ) = f g n = f g(d) = (g ∗ f )(n) d d d d 0 as d ranges over divisors of n, so does d |n n d d|n d|n Proposition 52. f ∗ (g ∗ h) = (f ∗ g) ∗ h (ie., ∗ is associative) Proof left as exercise. ¨ The Mobius mu function is defined to be ( (−1)ω(n) if n is square free µ(n) = 0 otherwise remembering that ω(n) was additive, it’s easy to see µ(n) is a multiplicative function ( (−1)r µ(n) = 0 if n = p1 . . . pr for distinct primes pi if some p2 divides n Remember the function U (n) = 1 for all n. Theorem 53. ( 1 if n = 1 µ∗U =1 0 otherwise Proof. µ, U are multiplicative, so µ∗U is too. So enough to show that (µ∗U )(1) = 1 and (µ ∗ U )(pα ) = 0 for prime powers pα . The first is trivial: (µ ∗ U )(1) = X µ(1)U (1) = 1 · 1 = 1 d|1 (µ ∗ U )(pα ) = X µ(pα )U (pα ) d|pα = µ(1) + µ(p) = 1 + (−1) =0 So µ ∗ U = 1.