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.11; 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.