intro & Euler’s and…
I am going to look at several arithmetic functions, and we will see how Mathematica knows them. We will see the convolution product of arithmetic functions for dealing with particularly appropriate summations, the Möbius Inversion Formula, and we will see a conceptual basis for the Möbius function, which basis is part of a useful more conceptual way to deal with all these summations.
If you get bogged down along the way, skip to the final section entitled “Way too Easy!”
In fact, I have filed this post under “abstract algebra” because we’ll be doing just a little algebra to get a good grip on these functions. And yet that little will go a long, long way.
A function defined on the positive integers – which we would usually call a sequence! – is said to be multiplicative if
whenever m and n are relatively prime. (That is, whenever the greatest common divisor (GCD) of m and n is 1: we often use (m,n) for the GCD and write that condition as (m,n) = 1.) Be careful: we require that the function of a product be the product of the functions only when the integers are relatively prime, not for all pairs of integers m and n.
In fact, I’ll even warn you more specifically: since p and p^2 are not relatively prime, we cannot compute even for a prime p.
Now let me be a little more precise: the definition of a function requires that we specify domain and codomain. In the context of number theory, a function from the positive integers to the complex numbers is called either an arithmetic function or a number-theoretic function.
From now on, let m, n, k, whatever be a positive integer – if it’s an integer in this post, then it’s positive. Euler’s totient function, also called Euler’s phi function, is the number of (positive) integers less than or equal to m that are relatively prime to m.
(I can’t say “less than”, because although (m,m) = m, that’s 1 for m = 1… and I need to include that case. To put that another way, “less than” would be fine… except for m = 1.)
Mathematica® knows this function, as EulerPhi. Here are its values for m = 1, .. 20:
Note that Mathematica has … as it should, since (1,1) = 1.
You may know another arithmetic function: the number of positive primes less than or equal to a positive integer. Mathematicians use for this function, but Mathematica knows this it as PrimePi. For example, we have
That is, there are three primes less than or equal to 6, namely 2,3 5. Here are its values for m = 1, .., 20:
is 1, counting 2 itself.
Let’s take a closer look at multiplicative functions. By definition, the term multiplicative applies only to arithmetic functions, so if I say is multiplicative then is implicitly an arithmetic function.
Here’s one key fact. If a function is multiplicative, then either or , since
i.e. : solutions are x = 0 and x = 1. Furthermore, if is multiplicative and , then for all n: the function is identically zero. Let’s see that. If p is prime, then is zero:
(edited 10/22/12) By the same argument , and
and then any integer n, being a product of powers of primes, is also zero:
This means that you may see the hypothesis “If is multiplicative and not identically zero” in texts; we might just as well say “ is multiplicative and non-trivial”.
Although we applied this technique in a trivial case, we will see that it works more generally: if a function is multiplicative, we find its values on primes, then on powers of primes, and thence on all integers.
Now is a good time to recall that PrimePi(1) = 0. Ah ha! I infer that PrimePi is not multiplicative. (If it were, it would have to be identically zero.)
Let us return to Euler’s function. We have they key fact that is multiplicative. And because it’s multiplicative, if we can find its values for powers of primes, then we can find its values for any integer n.
First, if p is prime, then .
(because 1, 2, … , p-1 are all relatively prime to p.)
Then. if p is prime and k is a positive integer,
(Here, the key is that p is not relatively prime to p^2, etc.)
For k =1 that reduces to our previous result, . I’ll go ahead and state the final result, just for completeness:
if n is a product of k distinct prime numbers to powers , then
(The powers are implicit in the “n” that multiplies the expression.)
To illustrate that is multiplicative, we compute directly:
But we may also compute it by using powers of primes (since the powers are relatively prime):
We may also confirm the explicit formula for each power of a prime:
One reason for mentioning PrimePi is that
PrimePi is not multiplicative.
For example, take the two primes 2 and 3. PrimePi of 6 is 3, but PrimePi of 3 and of 2 are 2 and 1, so PrimePi of the product is not equal to the product of the PrimePi’s:
sum over divisors
It is some interest to consider the sum of all the numbers as d ranges over all the positive divisors of n. We write this as
It is a useful fact that whether we sum , we get the same answer:
because as d ranges over the divisors of n, so does n/d – just in reverse order.
Let me also point out that the sum always includes d=1 and d=n.
We have an interesting application to Euler’s function:
if n is a positive integer, then
Let me see if I can find a nice proof of that.
Mathematica knows this sum as DivisorSum. That last theorem is:
That is, DivisorSum is , and the second entry is written as a pure function.
Let’s define infinitely many more multiplicative functions. If n is a positive integer, we define
= the number of positive divisors of n
) = the sum of the positive divisors of n.
In symbols, we have defined
Perhaps it will not seem too much of a stretch to define the sum of the kth powers of divisors of n:
Then what we called could be written , and is . You will see both notations. More importantly, if you are using Mathematica, it knows this infinite collection of functions as , and calls them DivisorSigma:
As I implied before I defined them, it is true that the functions and (and , in general) are multiplicative.
Just as for , we can evaluate these functions if we know their values for prime powers… so we need to find those.
Here’s the answers for a power k of a single prime p:
if p is prime then
We can ask Mathematica to check these formulas, for example, for p = 2.
matches – that is, for k = 1, .. 20, p^k = k+1:
… and so does :
Shockley has a few examples; let me check them. Here are and of 10:
Here are and of 1,274,000:
Here are and of 76:
Good. Mathematica agrees with my text.
(Yes, the same name as in a Möbius strip.) There is a fascinating arithmetic function written and called Möbius Mu (written by Mathematica, as often happens, with oe instead of ö):
The most common definition – well, the definition in Mathematica, in MathWorld, in Hardy & Wright, and in Rose, and in Ireland & Rosen (see the end of the post) – is this:
- +1 if n = 1
- +1 if n is the product of an even number of distinct primes
- –1 if n is the product of an odd number of distinct primes
- 0 if n has a multiple prime factor (equivalently, if n is not squarefree)
and that’s what we see in the previous table.
I hate that definition. Yes, it’s simple enough – but where the hell did it come from? I would overcome my aversion if there were no choice, but there is a beautiful alternative. (I’m not saying you will find it beautiful, just that I did. I myself get annoyed when people tell me that I will like something.)
The function arises when we answer the following question. I will eventually write this in a much, much simpler manner, but for now…
If we have arithmetic functions and related by
can we invert that equation and “solve for” ?
Yes we can… the answer is called the Möbius Inversion Formula… and it can be written
So that’s what the function is for. Still, this is looking messy, and doesn’t give us any idea how was obtained.
So let’s use some modern algebra to take a higher-level look at this. We can do so much better.
Let and be arithmetic functions. We define the convolution product of and as
I claim that the convolution product is a binary operation… that is, the product of two arithmetic functions is again an arithmetic function. Furthermore – being sums of products of complex numbers – the convolution product is associative.
More interestingly, it is commutative. I’m not going to put many proofs into this post, but let me show you this one. We write the definition of …
Let D = n/d, so d = n/D…
But each product term is commutative (they’re complex numbers, in general)…
(The proof of associativity is messier, but similar. Ultimately they boil down to commutativity and/or associativity of complex multiplication.)
Most interestingly, if are multiplicative, then so is their convolution product.
Finally, Mathematica knows this product as the Dirichlet convolution:
My text has an example asking for , for n= 1,2,3,4. Let’s see what Mathematica gets. In general,
Interesting. In our convolution notation, that says that . Let’s return to this toward the end of the post.
In the meantime, let’s compute those specific values:
Those are the answers in the book.
And here’s :
They do seem to be equal.
Now hold on a second. We have an associative binary operation defined on the set of arithmetic functions. I don’t suppose we have an identity, too?
Sure we do. (That’s the real reason I wrote this post.) The function defined by
for all n > 1
acts as an identity for the convolution product. Let me emphasize that except for n = 1.
Let me confirm that it is an identity. Our general formula
Well, if we have an identity, might we have inverses? They should be defined in the obvious way: is called the inverse of (under convolution multiplication) if
We don’t have a group yet, but the same proof applies here to show that if an inverse exists, it is unique. And it would be both a left and right inverse – if only because this product is commutative.
We can be even more precise. We can identify arithmetic functions – all, not just multiplicative ones – which have inverses:
the arithmetic function has an inverse if and only if .
That in turn is enough to let me assert than any multiplicative function which is not identically zero , has an inverse and the inverse is also multiplicative.
So: the set of non-zero multiplicative arithmetic functions is an abelian group under convolution.
This tells us – if we didn’t already know it – that PrimePi is not invertible. Hell, if it were, then its inverse would give us the kth prime for any k. We could simply enumerate the primes!
Let us return to the inversion problem. If we define
for each positive integer n
could be wrewritten as
and we should then have
Since , has an inverse. And it’s clear that is multiplicative… and therefore its inverse is multiplicative.
So, why don’t we just give a name to ? Guess what? That’s the definition of that I really, really like:
That is, the equation
which in more gory detail is
Yes, that is the Möbius Inversion Formula again.
Now, it takes about half a page to derive the properties of . But first I need an explicit formula for the inverse of . It will be convenient to call it , so .
It’s clear that . Right? We have
For n = 2, first recall that , and then we have
so solve for :
I’ll write that more generally shortly. But we know , and we just got .
so solve for :
Now it’s time to solve for in general. What we’ve been doing is pulling one term, specifically d=n, out of the sum… so let’s write that in general by adding the constraint d < n to the summation sign:
Once again, solve for , n > 1; here’s our general formula for :
For completeness, recall that
For the fun of it, let's check that against the identity. Let … then
(etc.) so the identity is its own inverse.
Now, can we use this inverse formula to work out ? Of course we can!
it is immediate that , because it's multiplicative, because it's the inverse of the multiplicative function .
The explicit formula for inverse gives us
because for all n and for all d.
So if n is a prime p, then the sum collapses to d =1, so
Since is multiplicative, , for distinct primes . In particular, is +1 for an even number of distinct primes, -1 for an odd number of distinct primes.
For a repeated prime p, the explicit inverse gives us
For a cubed prime, we get
So now we know why is what it is. I strongly prefer thinking of it as
with explicit values computed using our general formula for .
Way too Easy!
Let me show you other uses for the abstract approach. So far we have
the Euler phi:
the number of divsiors:
the sum of the divisors:
the sum of the kth powers of the divisors:
the identity: , ….
the constant: , ….
the inverse of .
Let's add one more:
Well, can we rewrite some things? For starters,
translates to , and
Next, that unproved assertion
translates to . (Which also gives us . Which we'll see again in a moment.)
Shockley asks us to prove a few things.
First, show that
for n > 1. But that translates to for n > 1… which is true because and for n > 1. This question is nothing more than
Incidentally, Mathematica knew this. It catches the fact that the sum is 1 for n = 1:
I would hate to try proving that from the usual definition!
Second, show that
Well, that translates to , which we saw just a moment ago. I would be crying over this if all I had was the usual definition of .
Third, prove that observation we made earlier that .
Well, we have and , so
(Associativity lets me drop parentheses, commutativity puts next to a , , and the identity drops out.)
As if this ease of manipulation weren’t enough…. The set of arithmetic functions, with pointwise addition and convolution multiplication is a ring… it's even an integral domain. Recalling our picture from this post
… I just have to ask: is it a UFD?
Yes, it is. (That is a free download.)
And I am utterly fascinated that the set of arithmetic functions is a UFD.
Oh, what are the units? Every invertible function… that is, every arithmetic function .
OK, what are the primes and the irreducibles?
I don't know….
My main resource for this post has been James E. Shockley, “Introduction to Number Theory”, Holt Rinehart Winston, 1967, 0-03-059760-9.
My other books, mostly heavy guns, do not have this approach to the Möbius function, they just define it by its values….
Hardy & Wright, “An Introduction to the Theory of Numbers”, Oxford Science Publications, 5th ed. 1979, 0-19-853171-0 is a famous book… I also own Rose, “A Course in Number Theory”, Oxford Science Publications, 2nd ed. 1994, 0-19-852376-9. The other prominent text is Ireland & Rosen, “A Classical Introduction to Modern Number Theory”, Springer-Verlag, 1982, 0-387-90625-8.