Mobius Inversion — Number Theory's Secret Weapon Explained

[00:00:00]today we're going to look at a really famous result from number Theory involving so-called arithmetic functions and maybe before we look at the result what is an arithmetic function well it's simply a function whose domain is the natural numbers in other words the positive integers so there are some famous arithmetic functions like the identity functions on the natural numbers that's kind of a silly one you have the oiler fee function which counts the number of Rel relatively prime numbers between one and N if you're looking at the of n you have the divisor function which counts the number of divisors of a function and you have the sum of divisors function which is exactly what it sounds it sums all the divisors of a number that being said this Mobius inversion formula is for maybe abstract or general arithmetic functions so let's look at what it is and then we'll look at some special cases of this Mobius inversion that are well built out of those functions that we just uh described so let's say we've got two functions f and g from natural numbers to complex numbers then f and g satisfy this sum right here if and only if they satisfy this sum right here so let's look at this first one we have F of n is equal to the sum over all divisors of n of G of D okay so that's pretty interesting it's a way of kind of decomposing our function f as you know values of G based on the divisors of n but then we've got another way of kind of doing the opposite decomposing G in terms of the divisors of n so we've got G of n is equal to the sum over all divisors of n of mu of D * F of n / d but what's mu of D well it's the so-called Mobius function well that's where this name Mobius inversion comes from because the fact we're using this Mobius and function and we're kind of like inverting one formula into the other using this Mobius inversion formula so what's the Mobius function well it's kind of an interesting function um it gives you the value of one if you input the number one mu of n is equal to zero if there is a square of a prime that divides n so for example mu of 8 is going to be zero because four divides 8 and 4 is 2^ 2ar and then mu of n is equal to minus1 to the K if N is a product of K distinct primes so like mu of 6 is 1 because that's - 1^ SAR and 6 is equal to 2 * 3 those are distinct primes okay so now we've got an idea of the mobious function and how it relates to our Mobius inversion formula what's the idea of this proof well we're going to do this via an example so let's look at F of 6 and I guess we're looking at this forward Direction so that means we're supposing this box up here that's on the upper left so that means F of 6 is G of 1+ G of 2+ G of 3+ G of six that's the sum over all the values of G evaluated at the divisors of six the divisors of six are obviously 1 2 3 and six but now let's also look at F of three which is pretty clearly equal to G of 1 plus G of3 notice that F of 2 is going to be equal to G of 1 + G of 2 obviously those only have two terms because they're prime numbers and then notice that g of one or sorry F of one is simply equal to G of one but now notice that if we do F of 6 minus F of 3 minus F of 2 + f of 1 we get G of 6 because observe we'll have G of 1 - 2 * G of of 1 plus G of 1 so the G of 1's cancel the G of 2's cancel the G of 3's cancel and we're left with G of six but now notice that this has a coefficient of one but the number one is like we said before mu evaluated at six this F of3 has a coefficient of negative 1 that's mu of three this coefficient of f of two has uh well is negative 1 as well that's mu of 2 and then this F of one has a coefficient of positive one that is Mu of one so we see that out of these four equations right here we're able to build an equation which is like this other side of our Mobius inversion formula okay so now that we kind of see how this goes let's see the proof in general and then we'll look at like I said some special cases of function that satisfy these Mobius inversion formulas so the first step of our proof of the main result for this video is a limit and that limit involves the just sum of values of the Mobius function so we've got the sum over all divisors of n of mu of D is equal to Delta n comma 1 so in other words this is equal to one if n is equal to one and zero if n is not equal to one that's the so-called chroner Delta so how can we do this well we're going to do this by induction on the number of prime factors of n so if we're doing induction we need a base case so what's the base case here well I think our base case is that n has zero prime factors but if n has zero prime factors then n is equal to one that's the only number with zero prime factors but now let's observe that if we sum over all of the divisors of one of mu of those divisors well there's only a single divisor of one that's the number one so that's going to give us mu of one which is equal to one by our definition of mu over here okay so now let's look at our induction step starting with an induction hypothesis so let's suppose for some K bigger than zero the statement holds and by the statement holds I mean for all natural numbers that are divisible by K primes or have K different prime factors maybe not counting the multiplicity of the prime factor and then what we'll do is let P or sorry let N be a prime that has k+ one prime factors so we'll say that it's P1 R1 all the way up to PK RK so those are K prime factors and then PK + 1 r k + 1 so that's the K plus first prime factor but now what we'll do is we'll smash these first K prime factors together into a single number which we'll be able to apply the induction hypothesis to and we'll call that number M and and then we'll rename this k + first prime factor as well we'll just name that P so we'll have M * P to the r we're raming we're renaming that exponent as well and now well now we're ready to do our final calculation so we'll do the sum over all divisors of n of mu of D so we can break that down into divisors that contain no multiples of p a single multiple of P a multiple of p^2 and so on and so forth up to a multiple of P to the r and that's going to give us the sum over all divisors of M of mu of D and then plus a sum over all divisors of M time P but notice that that's going to be the sum over all divisors of M of mu of D * p that's just another way of doing that and then plus a sum over all divisors of M of mu of D * p^ 2 all the way up to the sum over all divisors of M of mu of D * P to the r but now here's a nice result notice that D * p^2 is divisible by the square of a prime the next term is also divisible by the square of a prime and so on and so forth so those will all give us a value of zero in the Mobius function so all of this is exactly zero then observe that what we have right here is D which divides M times a prime P since D divides M it doesn't contain P so that means we can in some ways Factor the P out of this mu and change this plus sign to a minus sign just over here based on our formula it's kind of like rewriting -1 the K as minus -1 to the K-1 if you will but now observe that these two terms will cancel each other because we have exactly the same sum so now putting that all together we get the value of zero which is exactly what we should have because if K is bigger than or equal to z k + 1 is bigger than or equal to 1 which means in has at least one prime factor but anything that has at least one prime factor is not equal to one and thus well we have finished this maybe second case of our limma okay so let's see how this can be used for our main result so observe that our result over here is an if and only if statement this formula holds if and only if this formula holds so that means we'll start with one side we will assume this formula this F of n as the sum of divisors of n of values of G holds and prove that the other formula holds okay so let's see how we can do that so let's suppose for all natural numbers n we have F of n is equal to the sum over all divisors of n of G of D and then let's consider the Maybe right hand side of the wouldbe formula that we're trying to construct so we're doing the sum of all divisors of n of mu of D * F of n over D so something like that but observe that if D is a divisor of n then that means that n/ D is equal to K which is some other natural number well actually what it means is that n is equal to a natural number time D but then we can just divide it to see what we have right here okay but notice that that is equivalent like I said before to saying that n is equal to D * K and so in fact we're kind of reindexing this sum instead of O all over all divisors of n we're going to be well it's still kind of over all divisors of n but we're going to write that as D * k equals n just to be able to rewrite this as Mu of D and then F of K because if we've got that written in terms of f of K it's easier to use this like assumed formula so let's just maybe put an arrow here to say that that is the like change of index or the change of variables we're doing here okay so now from here we can rewrite this as the sum over all D * k = n of mu of D and then we'll rewrite F of K using this formula right here so it's going to be the sum over all divisors of K I'll call those e of G of e okay nice but now let's notice the following so let's do another color here observe that what we have is e divides K so that means that K Over E equals L but that's equivalent to saying that K is equal to e * L okay but then notice that D * K is equal to n but that means that uh D * e * L is equal to n just replacing K with e * l so that allows us to rewrite this as the sum overall D * e * Lal n of mu of D times G of e okay so I think that's looking pretty good but now what we'll do is change the order of summation so in fact what we kind of did here was turn this double sum or this iterated sum I should say iterated sum into a double sum and now we're going to reverse the order of summation so it's going to go something like this this is going to be the sum over all e * m is equal to n of G of e so now notice that the the G sum is on the outside if you will and then after that the sum of all divisors d e of M of mu time or mu of D okay cool and then well what's the branch from here to here well in fact we're kind of like setting m equal to D * L if you will of course we're using a slightly different D down here but that's kind of neither here nor there okay but now observe that we can use our limma so by our limma this right here this inner sum is equal to one if m is equal to one and zero otherwise in other words it's equal to Delta M1 but that means that this outer sum only survives when it's not being multiplied by zero in in other words in the case when m is equal to 1 but if m is equal to 1 and E * m is equal to n then that means that e must be equal to n leaving us with G of n but let's see what we have starting here and ending here is exactly this second formula from our Mobius inversion so we've achieved this forward Direction starting with this first Formula and achieving this second formula now let's do the reverse now moving on we need to do our reverse Direction so in other words we're going to suppose for all natural numbers n we know that g evaluated n is the sum over all divisors of n d of mu of D times F of n over D and then from there we're going to consider the right hand side of our wouldbe first Formula because we're working from second to First here and work that down to the left hand side of course using the Assumption okay so let's see how that goes so in other words like I said we are considering the sum over all divisors of n of G of D okay so well what do we do well we use this formula right here that we are assuming so that's going to be the sum over all divisors of n of the sum of all divisors D Prime of d of mu of D Prime and then F of D over D Prime so something like that but now we're going to play the same kind of game that we did with reindexing for uh this version as well or this direction as well so notice that D over D Prime is equal to some natural number we'll call it e but that's equivalent to saying that e * D Prime is equal to D so I guess I left off here that D over D Prime was equal to e so let's fit that in there right there okay good but then we also know that n/ D is equal to K so we have n/ D is equal to some natural number K but that's equivalent to saying that n is equal to D * K which is equivalent to saying that n is equal to e * D Prime Time K using the fact that D is e * D Prime okay so that's kind of a bunch going on there but it does allow us to achieve our goal of changing this iterated sum into a double sum like we did before so this is going to be the sum over D Prime * e * k = n of mu of D Prime Times F of e okay cool but now well we're going to change this double sum back into an iterated sum so it's going to look something like this so we'll have the sum overall e * K Prime equal m of e * K Prime equals n of f of e and then inside of that sum we'll have the sum overall D Prime * K Prime of mu of D Prime okay great but from here we can use our limma again which isn't on the board anymore but let's recall that this inner sum is equal to Delta let's see uh K Prime comma 1 in in other words it's only one or it's only nonzero when K Prime is equal to one and in that case it's equal to one but if K Prime is equal to one e is equal to n so that means this whole thing collapses to F of n as needed okay so now we've proven that these two formulas holding is equivalent and like I said before now we're going to look at some special number Theory functions or functions in important in number theory that satisfy this Mobius inversion formula so in order to efficiently talk about these pairs of functions that satisfy our mobus inversion formula let's make a definition so let's say that f and g form a mobious pair if they satisfy one and thus both of these mobus inversion formulas and then for some examples the identity function and the oiler fee function form a Mobius pair the divisor function and the constant function one form a mobus pair and the sum of divisor function and the identity function form a Mobius pair so let's briefly look at the proof of maybe at least one of these so let's notice that the identity on the natural numbers evaluated at n is equal to n but n is equal to well the number of numbers between 1 and N I think that's pretty clear but then we can partition this set from one to n in terms of elements that have a common divisor of D or greatest common divisor of D where D is a divisor of n so in other words we can rewrite this as the sum over all divisors of n of the number of elements between one and N whose gcd with n is equal to D okay but then now let's observe that that's simply equal to the sum over all divisors of n of the set D and then 2 * D and then 3 * D all the way up to D * n/ D I think that's you know pretty clear and then uh from there that's going to be the sum over all divisors of n of of Fe of n over D so I'll leave this equality as a bit of an exercise but it's not too hard to check and then from here we can reindex and we'll have the sum over all divisors of n of the of D but that would be our Mobius pair satisfying this first equation but then if it f satisfies this first equation it means it also satisfies this second equation which can be written as the of n equals the sum over all divisors of n of mu of D * D Over N okay so that shows that this yellow underlined pair is a Mobius pair and then while showing that the other two satisfy this first equation is pretty straightforward so maybe I'll leave that as a homework exercise and that's a good place to stop