2018 September 1
In this post, I will evaluate a few interesting sums involving the arithmetic functions $\tau,\sigma,\sigma_a,\mu,$ and $\varphi$, whose definitions and basic properties were described in the previous post.
I will consider first sums of the following form, in which the index of the sum ranges over the positive divisors of a positive integer $n$: For example, we have More generally, we shall consider sums in the form This type of sum is itself a function of $n$, and is called the Dirichlet Convolution of two arithmetic functions $f$ and $g$, or more briefly, $f$ convolved with $g$, and is written as $(f*g)(n)$.
There are a few properties of this "convolution" operation that are useful in finding the values of some of the sums. For example, we have the easy-to-prove property Which results from the fact that if $d$ is a divisor of $n$, then $n/d$ is also a divisor of $n$. We also have, trivially, that convolution distributes over addition: It is also true that convolution is associative, which can be demonstrated as follows:
There is one more basic but extremely useful property of Dirichlet convolution that remains to be proven; namely, that if $f,g$ are multiplicative, then $f*g$ is also multiplicative. This is proven as follows: if $m,n\in\mathbb N$ are coprime, then any divisor of $mn$ can be expressed uniquely as the product of a divisor of $m$ and a divisor of $n$. Thus, we have
and we are done. Let's put this result to use deriving a couple of summation formulae. Consider first the sum Because we know that this sum, as a function of $n$, is multiplicative (since $\varphi$ is multiplicative, as proven in my last post), we need only calculate it for $n$ a prime power, and then we may determine all of its other values using prime factorization. We know that where $p$ is prime and $k\gt 0$, so we have that if $n=p^k$ is a prime power, the sum is equal to since the divisors of any prime power are precisely the powers of that prime less than it. This sum then telescopes, giving simply a value of $p^k=n$, showing us that the value of this sum is simply the identity function for arguments that are powers of a prime. But since the sum must be a multiplicative function of $n$, it must be the identity function for all natural numbers $n$, so we have for all $n\in\mathbb N$.
If we define the function $\epsilon(n):=\delta_{1n}$, then we have the following identity as well: This can be proven even more easily, so I will omit the proof; simply calculate the sum for values of $n$ that are prime powers and exploit the multiplicativity of the sum and $\epsilon$.
By expressing the following two sums as $\varphi * 1$ and $\mu * 1$, and using the definition of $\sigma_a$ as $\text{id}_a*1$, where $\text{id}_a(n)=n^a$, and then applying the previously derived properties of convolution, we may derive the values of a few more interesting sums, such as I encourage the reader to pause for a moment and try to calculate this sum in terms of $n$.
The answer is, of course, $\sigma$. This sum is equal to $\varphi\tau=\varphi11=\text{id}1=\sigma$. Similarly, we have that $\varphi*\sigma_a=\sigma_{a+1}$.
As another interesting sum, consider This one can be done with a totally different strategy. Despite the strange nature of this sum, it can be evaluated using what is perhaps the most used tool in the evaluation of sums: telescoping. We may write this sum as And, since $n/d$ is a divisor of $n$ whenever $d$ is a divisor of $n$, we may make a substitution in one of these sums: By rewriting this as follows, the telescoping becomes apparent: By combining the sums, we have that this is equal to
Now for a more general formula, which returns to the non-telescoping techniques used earlier. Consider what would happen if we nested two of these sums, like this: More concisely written, this is $fg1$. Of course, with what we know so far, we can rearrange this by exploting the associativity and commutativity of convolution. However, there is a trick used in many of my previous blog posts when evaluating sums or integrals that would be nice to use here; namely, reversing the order of summation. It is unclear how to do this at first glance, since the indices of the inner sum are dependent on the index of the outer sum. However, it can be done, as we shall see in a moment. And, although doing so is not particularly useful for calculating these types of sums, it is handy for finding relationships between them.
Here is the sum under consideration again: To invert the order of summation, we would like to obtain something in the following form: To determine the coefficient of the $f(d')$ term in this sum, we must turn to the original double sum. We can see that $f(d')$ appears only when $d'|d$, or when $d=kd'$ for some natural number $k$. To find all $d$ corresponding to some $d'$, we must let $k$ vary in a way that ensures that $kd'$ still divides $n$, which is accomplished by imposing the restriction that $k|n/d'$. Thus, we have the following: or This can lead to some interesting formulae. For example, letting $g(n)=n^a$ and $f(n)=n^b$, we have Which can be simplified, through a simple substitution, to Some interesting special cases of this formula include the case of $b=0$ and $a=1$: Or the special case of $b=0$ and $a=-1$: There is another interesting formula that I discovered by using both the more general formula above and the value of the telescoping sum calculated earlier. By letting $f(n)=1$ and $g(n)=\ln(n)$ and making lots of cancellations, we get the following interesting identity: Now I would like to move on from sums in the form to number-theoretical sums in the following form: This notation is a bit confusing, so it warrants a bit of explanation; the sum ranges over all of the positive integer solutions $(a,b,x,y)$ to the diophantine equation $ax+by=n$, where $n$ is some fixed positive integer. This choice of sum may seem arbitrary, but as we will see, it can lead to some interesting results.
As I mentioned before, as our "trick" to evaluate sums of this sort we will use the beloved trick of telescoping once more - but it's a very complicated form of telescoping. Let's take this general sum and split it into three sums: Let us denote these three sums by $S_{a=b}$, $S_{a>b}$, and $S_{a< b}$, and the total sum, or the sum of the three smaller ones, as $S$. We have Now make the substitutions $x+y\to x$ and $b-a\to b$, resulting in the equality Then, by symmetry, we may swap $a$ with $x$ and $b$ with $y$, resulting in the sum Now compare this with the sum $S_{b< a}$: If we sum the two, we get Okay, you may be thinking: just great, so we've rearranged the sum. What do we have now? Looks like nothing significant.
Wrong! Notice that all this time, we've left $f$ as a totally ambiguous function, with no restrictions imposed on it whatsoever. So now, to make this sum telescope, let's choose $f$ satisfying the following function equation: That's right - if $f$ satisfies this, then the whole summand of the previous sum disappears, and we have Giving us the equality Let's take a closer look at this sum. We may write it as Which can be written, interestingly, as which can be found by making the substitution $ad=n$.
Thus, we have that if $f$ satisfies the functional equation Then we have the following equality: Still, who cares? We don't even know of any functions satisfying that.
Well, now it's time to actually put this formula to use. I will only use it to derive a single summation formula involving $\sigma$, and then provide another formula as a suggested exercise - perhaps too much work for only two formulae, but hey, they're pretty cool formulae.
First, let's define the function $\theta: \mathbb Z^4\mapsto \mathbb Z^4$ as follows: Then, the functional equation we have for $f$ can be written as Then, if you mess around with $\theta$, you'll see that a miracle has occurred - $\theta$ satisfies the beautiful property That's right - it is 12-involutory! More specifically, we have This is indeed a miracle! Because, if we let $g:\mathbb Z^4\mapsto \mathbb R$ be arbitrary, and we define $f$ as follows, $f$ is guaranteed to satisfy the desired functional equation:
You might be thinking "eww, gross." Don't worry, I'm thinking that as well. This seems too complicated and messy to produce in any nice results.
Wrong again! Let's choose, for example, $g(a,b,x,y)=ab$ as our function (luckily, we've found a solution to our functional equation in terms of arbitrary $g$, so we can just pick whatever $g$ we want and see what we get). If we plug $g(a,b,x,y)=ab$ into the above definition of $f$ (ewww!) and conveniently hop over to Wolfram to see what it turns out to be, we get Okay, that's less gross. Let's put this into our sum and see what we get: Seems pretty unremarkable, and gross to deal with... until you notice that, since $a$ and $x$ are interchangable in the diophantine equation that defines the sum, we may "rearrange" the sum to get Which cancels nicely to Now we may write this in terms of our beloved arithmetic functions using the following easily-established formula: Meaning that our sum becomes Now let's have a look at the other side of the equality: After evaluating $f$ and simplifying, we get Evaluating the inner sum, we have Now, using the formulae for the sum of the powers of the first $k$ natural numbers and the definition of $\sigma_a$, we may express this in terms of $\sigma_a$ as follows: Thus, we have the following equality: Now, dividing both sides by $-4$, we have our gem: Beautiful! As promised, here is another formula that can be similarly derived, as a suggested exercise for the reader: ...and with that, I conclude this blog post!