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 ∣ n

as an indexing tool denote the set of primes which divide

n = \prod_{p 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.)

σ (n) = \prod_{p ∣ n} (\frac{p^{e + 1} - 1}{p - 1}) = \prod_{p ∣ n} (1 + p + p^{2} + \dots + p^{e})

ϕ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})

🔗

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.

\frac{σ (n)}{n} = \frac{\prod_{p ∣ n} (\frac{p^{e + 1} - 1}{p - 1})}{\prod_{p ∣ n} p^{e}} = \prod_{p ∣ n} \frac{p - (1 / p^{e})}{p - 1}

🔗

Alternately, to avoid fractions:

\frac{σ (n)}{n} = \frac{\prod_{p ∣ n} (1 + p + p^{2} + \dots + p^{e})}{\prod_{p ∣ n} p^{e}} = \prod_{p ∣ n} (1 + p^{- 1} + p^{- 2} + \dots + p^{- e})

🔗

Note that

\frac{ϕ (n)}{n} = \prod_{p ∣ n} (1 - \frac{1}{p}) .

🔗

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

σ

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

σ (n) = \sum_{d ∣ n} d

🔗

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

σ (n) = \sum_{d ∣ n} \frac{n}{d} = n \sum_{d ∣ n} \frac{1}{d} .

🔗

This led us directly to writing

\frac{σ (n)}{n} = \sum_{d ∣ n} \frac{1}{d}

in Fact 19.4.9; now we can also write it as

\sum_{d ∣ n} \frac{u (d)}{d} .

🔗

With

ϕ

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

ϕ ⋆ u = N \Rightarrow ϕ = N ⋆ μ .

Equivalently, we have Möbius-inverted Fact 9.5.4 to obtain, from

\sum_{d ∣ n} ϕ (d) = n,

the formula

\sum_{d ∣ n} d μ (\frac{n}{d}) = ϕ (n)

🔗

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

⋆

is commutative) we can write

ϕ (n) = μ ⋆ N = \sum_{d ∣ n} μ (d) (\frac{n}{d}) = n \sum_{d ∣ n} \frac{μ (d)}{d},

🔗

which allows us to also write the fraction as

\frac{ϕ (n)}{n} = \sum_{d ∣ n} \frac{μ (d)}{d} .

🔗

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 prime} p^{e},$ we have

\frac{ϕ (n)}{n} = \sum_{d ∣ n} \frac{μ (d)}{d} = \prod_{p ∣ n} (1 - \frac{1}{p})

\frac{σ (n)}{n} = \prod_{p ∣ n} (1 + \frac{1}{p} + \frac{1}{p^{2}} + \dots + \frac{1}{p^{e}}) = \sum_{d ∣ n} \frac{1}{d} .

🔗

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.