Prerequirements:

In the previous post we introduced a new kind of summation, the one extended to the divisors of a positive integer number. Summations of this kind are often used in number theory, so it’s worth to analyse them in more details. The most interesting case is the one of *double* summations extended to divisors: we’ll see that they can be written in simpler ways, especially when the Möbius function comes into play.

## Comparison between “classical” summations and the ones extended to divisors

We know that, when we have to sum up many numbers, the sum can be written concisely by using the summation symbol. For example, the sum of the squares of the integers from 1 to n, where n \geq 1 is an integer, can be written as follows:

or, equivalently:

Generally the summation terms, that are the addends of the sum, can be the result of any function f of the variable i, which is the index (or variable) of the summation:

For computing this sum, we have to compute f(i) for all i = 1, \ldots, n, and sum up all the values obtained. In fact (1) can be written in full as f(1) + \ldots + f(n). This notation is often useful for understanding what’s going on, but it’s unpractical for making calculations.

In the previous post we saw that, in some summations used in number theory, the summation index does not vary among all the integers between 1 and n, but only among the divisors of n, and so by convention it’s indicated with the variable d:

That means computing f(d) only for the positive integers d which divide n, and summing up the values obtained, as we saw in Definition N.19.

In order to clarify the difference between summation (1) and summation (2), let’s see an example. For n = 6, summation (1) becomes:

while summation (2) becomes:

The next step is to consider *double summations*, in which there are two variables, each of which varies within an own set of values. There are several kinds of double summations, but we are most interested in those ones where the variable of the inner summation is limited by the variable of the outer summation, like in the following case:

For computing this summation, we have to let i vary between 1 and n, for each value of i let j vary between 1 and i, compute the value of f(i, j) for each couple (i, j) so obtained, and finally sum up everything.

Considering only the divisors of n, we’ll obtain the following summation, analogous to (1′):

For computing this summation, we have to let d vary within the set of divisors of n, for each value of d let d^{\prime} vary within the set of divisors of d, compute for each couple (d, d^{\prime}) the value of f(d, d^{\prime}), and finally sum up everything.

For n = 6, summation (1′) becomes:

while summation (2′) becomes:

## Alternative forms for summations extended to divisors

Now let’s leave the comparison with “classical” summations, like (2), and let’s focus on summations extended to divisors, like (1′) and (2′). In fact, the summations of this kind can be written in several ways, which are worth to point out because they will be used often in the next posts.

Let’s start from single summations. In number theory there is often a version of summation (1′) where in the summation term, along with the divisor d, there is also its “complementary” with respect to n, that is the ratio \frac{n}{d}:

It’s important to know that, in this kind of summations, and also for the corresponding productions, the roles of d and \frac{n}{d} can be exchanged:

In fact, making the calculations, you can see that the final sum is the same, up to the order of the addends.

For n = 6 we’ll have:

while

Indeed, we’ve obtained the same product as before, but in reverse order.

Generally we can state the following property, which considers also the case of productions:

Exchange between d and \frac{n}{d} in summations extended to the divisors of a positive integer

Let n be a positive integer. Let f any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter^{(*)}). Then:

(*) To be precise, it’s necessary that the operations of sum and product are defined on the codomain, and they must be commutative. However in this context there is no problem at all, because this is true for the numerical sets we are interested in (\mathbb{N}, \mathbb{Z} and \mathbb{R}).

Let’s prove the first equation:

For proving (a), since sum is commutative, it’s sufficient to prove that every term on the right appears also on the left, and vice versa.

Let’s consider a divisor a of n (we may call it d, but for clarity we avoid using the same symbol of the variable of the two summations). It’s clear that on the left there is the term f\left(a, \frac{n}{a}\right), because it’s enough to set d := a. Let’s see if this term appears also on the right. We can note that, if a is a divisor of n, also \frac{n}{a} is a divisor of n (by Definition N.2 (Divisibility), this comes from the equality a \cdot \frac{n}{a} = n). Then \frac{n}{a} is one of the values of d in the right summation. So one of the terms of the right summation can be obtained by putting \frac{n}{a} in place of d within the generic term f\left(\frac{n}{d}, d\right), obtaining f\left(\frac{n}{\frac{n}{a}}, \frac{n}{a}\right) = f\left(a, \frac{n}{a}\right), which is the same term we located on the left. Repeating this argument as a varies within the divisors of n, we’ll have that all the terms on the right appear also on the left.

Now we should repeat the same argument in the opposite direction, in order to prove that each term on the right appears also on the left. But we can avoid to do that, by noting that the number of terms of the two summations is the same, and it’s equal to the number of divisors of n. We have seen that all the terms on the left appear also on the right, but the right summation cannot contain additional terms which don’t appear on the left, just because the total number of terms is the same. This completes the proof.

The proof of the second equality is analogous to the first: the only difference is that instead of the sum there is the product.

By applying Property N.13, starting from Property N.12 (logarithmic form) we can obtain immediately that \sum_{d \mid n} \mu\left(\frac{n}{d}\right) \log d = \Lambda(n).

In the previous example we can note that, after all, summation (3) is reduced to compute the function f for all the ordered couples of positive integers the product of which is n. In fact, if n = 6 these couples are (1, 6), (2, 3), (3, 2) and (6, 1), which are exactly the couples of values for which the function f was computed in the example. In order to highlight that, we can write summation (3) in the following form:

where the symbol \sum_{ab = n} is defined as follows:

Summations and productions extended to couples of variables with constant product

Let n be a positive integer. We define the following symbols:

So we can state the following Property:

Equivalent form for summations with d and \frac{n}{d}

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter^{(*)}). Then:

(*) The same observations made about Property N.13 are also valid now

Let’s prove the first equality, the one with summation, because the other one can be proved in the same manner.

Like we did for Property N.13, the proof consists in showing that all the terms in the summation on the left appear also in the summation on the right, and vice versa.

Let’s consider a term of the left summation, i.e. f\left(d, \frac{n}{d}\right), for some fixed d, divisor of n. Setting a := d and b := \frac{n}{d}, we’ll have that a and b are two positive integers such that ab = n, so the right summation will contain the term f(a,b). But f(a, b) = f\left(d, \frac{n}{d}\right), i.e. f(a,b) is just the term he had chosen on the left. Since this argument can be repeated for every value of the variable d of the left summation, we’ll have that all the terms of the left summation appear also in the right one.

Now let’s consider a term of the right summation, i.e. f(a, b), where a and b are two positive integers such that ab = n. We can note that, by the latter equality, a is a divisor of n and b = \frac{n}{a}. Then, by setting d := a, we’ll have that f(a, b) = f\left(a, \frac{n}{a}\right) = f\left(d, \frac{n}{d}\right), so the term f(a, b) we had chisen in the right summation appears also in the left one. Since this argument can be repeated for each term of the right summation, we’ll have that all the terms of the right summation appear also in the left one. This completes the proof.

If in summation (3′) we replace the equality sign by the divisibility symbol, we’ll obtain another kind of summation rather common in number theory:

As you may expect, this kind of summation is defined by putting \mid in place of = in Definition N.20:

Summations and productions extended to couples of variables the product of which divides a constant

Let n be a positive integer. We define the following symbols:

As interesting aspect is that there is a double summation which appears complicated at first sight, but can be reduced to form (4):

Let’s see an example with n = 12:

Finally we have obtained the sum of all the possible terms of the kind g(a) h(b), where ab is a divisor of n, so the initial summation is reduced to

If we put f(a, b) := g(a) h(b), this summation will be just in the form (4).

Generally, the following Property is true:

Equivalent form for double summations with d and \frac{n}{d}

Let n be a positive integer. Let g and h any two functions defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter^{(*)}). Then:

(*) The same observations made about Property N.13 are also valid now

We’ll follow the same principle of the previous proofs: in order to prove that the two summations are equal, we have to show that each term which appears on the right also appears on the left, and vice versa.

Let’s consider a term of the right summation. It’s given by g(a) h(b), where a and b are two positive integers such that ab \mid n. Let’s see if this term appears also in the left summation. If so, there should exist two positive integers d and d^{\prime} such that:

- d \mid n
- d^{\prime} \mid d
- d^{\prime} = a
- \frac{d}{d^{\prime}} = b

But these integers exist, because, as you can obtain from the last two equations, it’s sufficient to set:

In fact, these values of d and d^{\prime} satisfy the first two equations, since by hypothesis ab \mid n, and of course they satisfy also the other two ones from which they have been obtained. So the mapping (b) lets associate every possible couple of values of the variables (a, b) of the right summation, to a couple of values for the variables (d, d^{\prime}) which generate the same term in the left summation.

So we proved that all the terms of the right summation appear in the left one; now we have to prove the converse. So let’s consider a term of the left summation. It will be of the kind g(d^{\prime}) f\left(\frac{d}{d^{\prime}}\right), where d is a divisor of n and d^{\prime} is a divisor of d. Will we find this term also in the right summation? If so, there should exist two positive integers a and b such that:

- ab \mid n
- a = d^{\prime}
- b = \frac{d}{d^{\prime}}

The values of a and b are given by the last two equations:

These values, in addition, satisfy also the first equation, since ab = d^{\prime} \frac{d}{d^{\prime}} = d \mid n.

So, the mapping (c) lets associate every possible couple of values of the variables (d, d^{\prime}) of the left summation, to a couple of values for the variables (a, b) which generate the same term in the right summation. This guarantees that all the terms of the left summation appear in the right one, and it completes the proof.

A useful exercise would be resuming the comparison, which we suspended, between “classical” summations and the ones extended to divisors. In fact, the equivalent “classical” counterparts of the Properties N.13, N.14 and N.15 can be found, by making the following replacements:

Summations extended to divisors | “Classical” summations |
---|---|

Positive divisors | Positive integers |

\mid symbol | \leq symbol |

Product between summation variables | Sum between summation variables |

Ratio between n and one summation variable | Difference between n and one summation variable |

But why should we complicate our life with summation (5), if (4) is simpler, but equivalent by Property N.15?

The reason is that, in (5), the inner summation may be something already known. Let’s take as an example Property N.12 (logarithmic form):

If now we want to compute the summation:

we have to apply (6) by putting d in place of n, consequently choosing another name for the variable d, for example d^{\prime}:

Substituting into (7), we’ll have:

We have reduced to form (5), with g := \mu and f := \log. So we can apply Property N.15, obtaining:

So, roughly speaking, Property N.15 lets simplify summations when double ones are created as an effect of substitutions.

But that’s not all. The summation we have obtained, in fact, can be simplified further. More generally, all summations like this can be simplified:

In fact, by gathering the terms with the same argument of the function f, and by using Property N.11, the following property can be proved:

Simplification, by means of the Möbius function, of a double summation extended to the divisors of a positive integer, and to the divisors of the divisors

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} (the codomain does not matter^{(*)}). Then:

(*) The same observations made about Property N.13 are also valid now

An example of this Property, for n = 12, is illustrated in Figure 1, where, for each value of d, the summation \mu(d^{\prime}) f\left(\frac{d}{d^{\prime}}\right) is shown by arranging the values of f according to the Hasse diagram of d (recall that the Hasse diagram has been used in the previous post).

For n = 12, summation (9) becomes:

We can note that the same values of the function f are repeated many times, multiplicated by different values of \mu, so we can gather them. Doing so, each of them will be multiplied by a summation of values of \mu. For example, the value \boldsymbol{f(3)}, highlighted in bold, appears in three terms in which it’s multiplied respectively by \mu(4), \mu(2) and \mu(1), hence gathering these terms we’ll obtain \boldsymbol{f(3)}(\mu(1) + \mu(2) + \mu(4)).

Before proceeding with the simplification of (d), it’s useful to align the terms of different rows which have the same argument of the function f:

Now, in order to gather the repeated terms f(\cdot) we simply have to read this expression by columns instead of by rows. Doing so, we’ll obtain:

But, by Property N.11, all the summations of \mu(d) which we have obtained are zero, except for the last one which is 1, so the previous expression is reduced simply to f(12).

Like we did in the previous example, let’s gather in (10) all the terms of the kind f(b). First of all, the possible values of b are the divisors of n, by the relationship ab \mid n. In fact, from b \mid ab and ab \mid n it follows that b \mid n; moreover, if d is a divisor or n, we can set b := d and a := \frac{n}{d}, obtaining a couple of allowed values for the summation variables, because ab = \frac{n}{d} d = n, so ab \mid n).

So let’s fix a divisor d of n. Having established that d is one of the possible values of b, let’s ask ourselves now which are the summation terms with d as the value of the variable b. If the generic term of the summation is \mu(a) f(b), with ab \mid n, we have to look for all the values of a which generate terms of the kind \mu(a) f(d). Such a term appears in the summation if and only if ad \mid n, hence a \mid \frac{n}{d}. So, setting b := d, all the possible values of a are the divisors of \frac{n}{d}. Doing so, as d varies, we’ll exhaust all the summation terms, hence:

In the inner summation, we have gathered all the terms with f(d). The next step is to apply the distributive property:

By Property N.11, the inner summation is always zero, except when \frac{n}{d} = 1, that is when d = n. So:

By joining all the previous equalities, we’ll obtain (10).

Property N.16 is one of the reasons for which sums in number theory are more used than products: in fact, differently from Properties N.10 and N.12, there isn’t a product version of this Property (the reason is that the proof is based on Property N.11, which in turn exists only with sum).

For better clarity, we now summarise into a table the properties of summations that we have seen till now:

Summation | Equivalent form | Reference |
---|---|---|

\sum_{d \mid n} f\left(d, \frac{n}{d}\right) | \sum_{d \mid n} f\left(\frac{n}{d}, d\right) | Property N.13 |

\sum_{d \mid n} f\left(d, \frac{n}{d}\right) | \sum_{ab = n} f(a,b) | Property N.14 |

\sum_{d \mid n} \sum_{d^{\prime} \mid d} g(d^{\prime}) h\left(\frac{d}{d^{\prime}}\right) | \sum_{ab \mid n} g(a) h(b) | Property N.15 |

\sum_{ab \mid n} \mu(a) f(b) | f(n) | Property N.16 |

From formula (8), by applying Property N.16 with f := \log, we can obtain immediately a new property of the function \Lambda:

Expression of logarithm as a summation of \Lambda

Let n be a positive integer. Then:

This Property is a sample application of the Möbius function: the knowledge of this function and its properties allowed us to obtain it immediately, otherwise we should have proved it separately.

## The Möbius inversion formula

Comparing formulas (6) and (11), we can note that they are one the inverse of the other, meaning that:

- in the first formula, the function \Lambda is expressed as a summation of logarithms (with appropriate coefficients given by the Möbius function);
- in the second formula, the logarithm is expressed as a summation of the function \Lambda.

Since the passage from one formula to the other one is based on the properties of \mu, not of \Lambda, the same thing can be true for any function. Indeed, Properties N.15 and N.16 can be joined into a single one, called **Möbius inversion formula** (even if, rather than a formula, it’s a way for obtaining one formula from another):

Möbius inversion formula

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} (the codomain does not matter^{(*)}), and let g be the function defined for all n \in \mathbb{N}^{\star} as follows:

Then

for all n \in \mathbb{N}^{\star}.

(*) The same observations made about Property N.13 are also valid now

In order to prove that

we have to substitute into this equality the definition of g:

Though, before substituting, it’s convenient to rename the variable n within (f) into d, consequently using another name for the variable d within the same formula, renaming it into d^{\prime}:

This formula is perfectly equivalent to (f), but, differently from the latter, it can be put into (e) directly, obtaining:

The thesis follows by applying the Properties N.15 and N.16: