Dirichlet Convolution: Arithmetic Functions as an Algebraic Ring

[00:00:00]in this video we're going to be talking about dirk clay convolution first i want us to consider some more examples of arithmetic functions so at the very end of the last video we ran into this function which i called e of n which was defined to be one if n equals one and zero else for another function i want to consider something i'm just going to call the one function which is just going to be constantly equal to one next i want us to consider the identity function which is just going to be equal to n and it can be seen that um well these two functions in particular are completely multiplicative uh but that doesn't really matter all three of these functions are multiplicative um actually i guess the identity yeah the identity is multiplicative i guess two um but anyway that's not really important um these are just going to be some sort of simple functions that we're going to use in this in this new exploration so what dear clay convolution is is an operation on the set of arithmetic functions so if we take two arithmetic functions f and g we can sort of multiply them by taking the sum over divisors of n of f of d times g of n over d so let's take an example really this sum just depends on what n is right the divisor structure so first let's just take an example n value let's say six so this is going to be f of 1 times g of 6 plus f of 2 g of 3 plus f of 3 g of 2.

[00:02:36]plus f of 6 g of 1.

[00:02:42]right so we're just adding sort of you take take two pairs of opposite pairs of divisors of n right so they multiply together to n and you take f on one value g on the other multiply that together and then sum over all of those and so it turns out that these functions these three functions here are really helpful for understanding uh sort of dear clay convolution so for instance as we explored in the last video for sums over divisors right so this a sum over divisors like this is really just um the dirac deer clay convolution of f with the one function evaluated at n so for instance we saw on the last video that the sum over the divisors of n of phi of d was equal to n and so uh sorry so what this means in terms of um dear clay convolution is that um we have fee convoluted with 1 equals i right because this is the function that evaluates turns into n and then here we're summing over just divisors of n of phi of d for another example we can consider let's say oh right let's consider the identity convoluted with one so this is the sum over divisors of n and then the identity of d is just d and then times one right so just we're summing over the divisors of n so this is the sum of the divisors of n right so we call that sigma of d or sorry sigma of n in in the last video or i guess two videos ago okay so this is the uh definition of deer clay convolution now it actually gives us some structure for arithmetic functions in particular uh deer clay convolution which i'll just write as dc together with addition so i'll just write plus makes the arithmetic functions into a ring and if you haven't studied any algebra uh a ring is just um an algebraic structure which generalizes uh sort of multiplication and addition together on some set in particular this is going to be a commutative ring with unity in other words uh we have some identity and i won't write one i guess so the function e of n uh which we defined up here is going to be our identity for dear clay convolution and in addition so in addition and not like the math addition just in addition the multiplicative functions form a sub-ring all right so let's see how this all comes together so first let's show that um right that dear clay convolution is commutative and this is you know pretty easy because this sum is very obviously symmetrical right uh sorry this should be a d i was thinking about six so in our example here right f right if we read it this direction right the numbers uh that f is being applied to go one two three six right but if we read it in this direction the numbers g is applied to is one two three six right so there's the symmetry and this is essentially what the tier clay convolution being commutative means right and essentially the way to formalize this is to say that d divides n if and only if n over d divides n and then you can essentially use a substitution in this sum saying okay i'm going to sum over n over d dividing n so we get f of n over d and then n divided by n over d is just going to be d and this is g deer clay f all right next we want to show that this dear clay convolution is associative so in particular if we take two arithmetic functions we want to show that if we take the if we convolute f and g and then convolute h it's the same as if we took f and convoluted it with the convolution of g and h so if we write this down right here we have d sum over divisors of n and then on the inside we're going to have uh a a sum over the divisors of d so i'll call that a dividing d so f of a g of d over a and then this is multiplied by h over n over d now if we take this uh term and in fact i'm going to write it sort of differently i'm going to start instead of starting with f of d i'm just going to start with f f of n over d which is valid right because it doesn't matter which way i do it and then here i'm going to have the sum over the divisors of d um of g over g of d over a times h of a so again this is convolution of g with h and then this is f so we want to show that these two things are equal to each other and the way to see this and and in particular the reason why i wrote uh there's some sort of choices i made in writing this um valid choices of course here we have this common term of g of d over a and this allows us to see that if we basically the numbers a d over a and n over d right we could see they all multiply to n and these two of course multiply to d because they can they come from the convolution of um of f of g applied at d so these numbers have to of course multiply to d um but essentially these are in terms of n right these are sort of independent in other words like this this double sum is going to run over all triples of numbers that multiply to all triples of positive integers that multiply to n and so when we write it like this we can just focus on d over a and essentially these two things are going to be independent of each other right so if we fix d over a then we see that the other terms f of n over d and h of a and then here we have f of a and h of n over d and so clearly what's happening there is that you have um f convoluted with h applied at n a over d right because that's just the multiple of these two which is of course just n over d over a where d over a is the number that we were fixing so this is a fixed number if we were to if if we consider if we fix d over a so we're factoring out g of d over a from both sides because we have that common term and then we see what's left over is f f convoluted with h applied at n divided by d over a so dear clay convolution is associative next we want to show again a ring combines multiplication with addition so uh one important thing that comes with that is that we have a distributive rule and thankfully this one is not as complicated as the associativity so [Music] here we just have f of d and then on the inside here we're going to have g with n over d plus h n over d and here we just have like regular number multiplication right so we can distribute and then of course the sum is going to distribute over this addition sign so we have f d g of n over d plus f of d h of n over d so um right this these are obviously just straight definitions of f composed with g and f composed with h now we want to show again as i said that e of n serves as an identity so let's just consider f compose or f convoluted with e this is going to be a sum over divisors of n f of d g of n over d sorry not g but e e of n over d and since n i mean e is going to be zero only um it's only going to be non-zero when e when n over d is one so n over d equals one is the only time that we're going to have a non-zero term in this sum right in other words d equals n so this whole thing is just going to equal f of n all right so here we should technically write this as being evaluated at at n this is going to be f of n times e of 1 right which is just 1.

[00:16:22]so and since we already established that this is commutative right so we would have we would write like f star e is e star f which is f right because that's typically how you express that something is an identity uh in the general case where there's non-commutativity but since we have communicativity we don't really have to worry about that so this completes the statement that the arithmetic functions form a ring under addition and directly convolution now we also claim that the multiplicative functions form a sub ring and all we really have to do for that is to show that if we take two multiplicative functions then we need to show that their convolution is multiplicative and um so let's say we take two numbers as always um two co-prime numbers x and y so their gcd is one and so if we look at f star g applied at x y we get a sum of divisors of x y of f of d times g of x y over d now as we've argued over and over again a divisor of x y where x and y are co-prime is going to uniquely factor into a pair of divisors of x of a divisor of x and a divisor of y so d we can replace d by d1 and d1 times d2 right g of xy over d1 d2 and of course since x and y are coprime then d1 and d2 are going to be co-prime and x over d1 and y over d2 are going to be co-prime so this just means that um we can once rewrite this summation terms we can split the functions given that f and g are multiplicative as we are assuming so we can split the functions like this and now uh if we just pair up the d1 and d2 terms right the x and d1 and the y and d2 terms uh since these two uh summation uh i guess summation rules i i can't think of a better word to aptly describe them but these two condition conditions sorry summation conditions these two conditions are independent of each other which means we can simply uh write this double this is a double sum i should be writing a double sigma but i'm kind of lazy um this we can factor this double sum over two independent conditions as a product of the two sums this is d2 dividing y f of d2 g of y over d2 and of course these two sums are just f compose g of x and then f convoluted g of y so f convolute g is multiplicative because we started with evaluating at x times x times y and then we ended up with evaluated at x times evaluated at y so this means that the multiplicative functions do in fact form a sub ring of the arithmetic functions now one thing that rings can't do is division right uh basically division is when you add in division that's when you get a field a field is when you have unique inverses of elements but we will see in the next video that there is a way to perform a sort of inversion on uh arithmetic functions and that is the mobius inversion so i hope to see you then