NTIC Products and Sums

Section 24.1 Products and Sums

In order to motivate bringing infinite processes to this part of number theory, let's step back a bit. Many functions we have already seen may be thought of in two ways – either as a product or as a sum.

🔗

Subsection 24.1.1 Products

🔗

Let

$p\mid n$ as an indexing tool denote the set of primes which divide

$n=\prod_{p\text{ prime }}p^e$ (recall Example 6.3.4). Then we have the following product representation of two familiar arithmetic functions. (Recall Theorem 19.2.5 and Fact 18.1.1.)

$\begin{equation*} \sigma(n)=\prod_{p\mid n}\left(\frac{p^{e+1}-1}{p-1}\right)=\prod_{p\mid n}\left(1+p+p^2+\cdots+p^e\right) \end{equation*}$

$\begin{equation*} \phi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right) \end{equation*}$

🔗

Both of these functions therefore may be thought of as (finite) products.

🔗

As a related example, we explicitly wrote out the product for the abundancy index in Section 19.3.

$\begin{equation*} \frac{\sigma(n)}{n}=\frac{\prod_{p\mid n} \left(\frac{p^{e+1}-1}{p-1}\right)}{\prod_{p\mid n} p^{e}} = \prod_{p\mid n}\frac{p-\left(1/p^{e}\right)}{p-1} \end{equation*}$

🔗

Alternately, to avoid fractions:

$\begin{equation*} \frac{\sigma(n)}{n}=\frac{\prod_{p\mid n}\left(1+p+p^2+\cdots+p^e\right)}{\prod_{p\mid n}p^e}=\prod_{p\mid n}\left(1+p^{-1}+p^{-2}+\cdots + p^{-e}\right) \end{equation*}$

🔗

Note that

$\frac{\phi(n)}{n} = \prod_{p\mid n} \left(1-\frac{1}{p}\right)\text{.}$

🔗

Subsection 24.1.2 Products that are sums

🔗

On the other hand, these products over primes are also sums over divisors; this is true either by definition or by theorem, depending on how you look at it.

🔗

It's clear with

$\sigma$ that this is the case, since we defined (in Definition 19.1.1)

$\begin{equation*} \sigma(n)=\sum_{d\mid n}d \end{equation*}$

🔗

We can even cleverly add up the divisors in the opposite order to get the slightly more felicitous

$\begin{equation*} \sigma(n)=\sum_{d\mid n}\frac{n}{d}=n\sum_{d\mid n}\frac{1}{d}\text{.} \end{equation*}$

🔗

This led us directly to writing

$\frac{\sigma(n)}{n}=\sum_{d\mid n}\frac{1}{d}$ in Fact 19.4.10; now we can also write it as

$\sum_{d\mid n}\frac{u(d)}{d}\text{.}$

🔗

With

$\phi$ we have something to prove to make this connection, but not much. In Fact 23.3.2 we saw that

$\phi\star u=N\Rightarrow \phi=N\star \mu\text{.}$ Equivalently, we have Möbius-inverted Fact 9.5.4 to obtain, from

$\sum_{d\mid n}\phi(d)=n\text{,}$ the formula

$\begin{equation*} \sum_{d\mid n}d\mu\left(\frac{n}{d}\right)=\phi(n) \end{equation*}$

🔗

By adding the divisors in the opposite order (alternately, by noting

$\star$ is commutative) we can write

$\begin{equation*} \phi(n)=\mu\star N=\sum_{d\mid n}\mu(d)\left(\frac{n}{d}\right)=n\sum_{d\mid n}\frac{\mu(d)}{d}\text{,} \end{equation*}$

🔗

which allows us to also write the fraction as

$\begin{equation*} \frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}\text{.} \end{equation*}$

🔗

Now, in some sense we already knew all this. Great, some arithmetic functions can be represented either as a sum over divisors or as a product over primes, depending on what you need from them. So what?

🔗

The genius of Euler was to directly connect these ideas.

🔗

Fact 24.1.1.

We can equate sums over divisors and products over primes to obtain special formulas. Given $n=\prod_{p\text{ prime }}p^e\text{,}$ we have

$\begin{equation*} \frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}=\prod_{p\mid n}\left(1-\frac{1}{p}\right) \end{equation*}$

$\begin{equation*} \frac{\sigma(n)}{n}=\prod_{p\mid n}\left(1+\frac{1}{p}+\frac{1}{p^{2}}+\cdots+ \frac{1}{p^{e}}\right)=\sum_{d\mid n}\frac{1}{d}\text{.} \end{equation*}$

🔗

Well, this was almost the genius; his real genius was to take these ideas to the limit!

🔗

One can't really take these expressions to infinity as they stand – one would get massive divergence. So what can we do? To analyze this, we will define new, related functions which preserve the summation, but allow for convergence.