MAT 338 Day 32 2011

2357 days ago by kcrisman

Last time we defined some new functions, and asked some questions about them.  

More precisely, we let $\sigma_k(n)$ be defined as the sum of the $k$th power of the (positive) divisors of $n$, so: $$\sigma_k(n)=\sum_{d\mid n}d^k\, .$$  Recall that $\sigma_0$ was also called $\tau$, and is simply the number of divisors of $n$, while $\sigma_1$ is usually called $\sigma$ and is the sum of all divisors of $n$ (including $n$ itself!)

Here is where things stood in our experimentation, as conjectures.

  • $\sigma_1(p)=p+1$ if $p$ is prime.
  • $\sigma_0(p^e)=e+1$ if $p^e$ is a prime power.
  • $\sigma_i$ is in fact multiplicative for $i=0,1$.
  • $\sigma_1(p^e)=1+p+p^2+\cdots +p^e$ for $p^e$ a prime power.
  • $\sigma_1(2^e)=2^{e+1}-1$.
  • $\sigma_0(n)$ is odd precisely if $n$ is a perfect square.

We'll start today by actually proving the most important of these things, as well as mentioning a few other useful formulas.

Fact:  If $p^e$ is a perfect prime power, then: $$\sigma_0(p^e)=e+1\text{ and }\sigma_1(p^e)=1+p+p^2+\cdots +p^e=\frac{p^{e+1}-1}{p-1}\; .$$

You'll note that this fact reduces to the formula already discovered when $p=2$.  

There isn't much to prove here, once discovered.  The only possible divisors of a prime power must have only that prime as divisors, by the FTA, so they are just other (smaller) powers of that prime, of which there are $e+1$, the ones summed up in the $\sigma_1$ formula.  The fraction formula is just the usual geometric summation formula familiar from precalculus and calculus.

More difficult is proving the following.

Fact:  For any $i$, $\sigma_i(n)$ is multiplicative, in the sense that $$\sigma_i(mn)=\sigma_i(m)\sigma_i(n)\text{ when }gcd(m,n)=1\; .$$

This would automatically lead to formulas like the following: $$\text{If }n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\; ,\text{ then}$$ $$\sigma_0(n)=\prod_{i=1}^k\left(e^i+1\right)\text{ and }\sigma_1(n)=\prod_{i=1}^k\left(\frac{p_i^{e_i+1}-1}{p_i-1}\right)\; .$$

I will not prove this directly!  Instead, we will prove a theorem that exemplifies the fact that, in the long run, it is better to prove general lemmas for sums of arithmetic functions than to do each one by itself.  Otherwise we do an endless line of proofs like the ones we did for $\phi$, but for every arithmetic function.

Let $\sum_{d\mid n}$ be a sum over all positive divisors (including $1$ and $n$) of $n$.  Then we have the following.

Theorem:  

If $g$ is multiplicative and $f(n)$ is defined as $$f(n)=\sum_{d\mid n}g(d)$$ then $f$ is also multiplicative.

Proof:

Luckily, this will be easier than proving the same for Euler's $\phi$ function.  

Let $m$ and $n$ be coprime; we are interested in $f(mn)$.  Basically, this all boils down to asking what the divisors of $mn$ look like.  Any divisor of $mn$ must be the product of some divisor $a$ of $m$ and some divisor $b$ of $n$; this is just about multiplication and divisibility, not even coprimeness.  But that guarantees that $a$ and $b$ are coprime as well.

So each divisor $d\mid mn$ gives us a (unique) pair of divisors $a$ and $b$ of $m$ and $n$.  So instead of summing over all divisors of $mn$, we can instead sum over each divisor of $n$ for each divisor of $m$.  In symbols, $$f(mn)=\sum_{a\mid m}\sum_{b\mid n}g(ab)\; .$$  Now we can use all the facts we have at hand - coprimeness, multiplicativity, etc. - to finish it off: $$f(mn)=\sum_{a\mid m}\sum_{b\mid n}g(ab)=\sum_{a\mid m}\sum_{b\mid n}g(a)g(b)$$ $$=\left(\sum_{a\mid m}g(a)\right)\left(\sum_{b\mid n}g(b)\right)=f(m)f(n)\; , \text{ Q.E.D.}$$

Corollary:

Since $g(n)=n^i$ is clearly multiplicative, it is true that $$\sum_{d\mid n}g(d)=\sum_{d\mid n}d^i=\sigma_i(n)$$ is also multiplicative.

Since we'll use them later, we define $u(n)=1$ to be the unit function and $N(n)=n$ to be the identity function; these are the special cases $i=0$ and $i=1$ of the corollary, which show that $\sigma_0$ and $\sigma_1$ are multiplicative.

 

For the rest of today, we will focus on $\sigma_1=\sigma$ itself, since the sum of divisors function has a deep richness of its own.

@interact def _(n=range_slider(1,150,1,(1,20))): top = n[1] bottom = n[0] cols = ((top-bottom)//10)+1 T = [cols*['$n$','$\sigma(n)$','$\sigma(n)/n$']] list = [[i,sigma(i),(sigma(i)/i).n(digits=3)] for i in range(bottom,top+1)] list.extend((10-(len(list)%10))*['','']) for k in range(10): t = [item for j in range(cols) for item in list[k+10*j]] T.append(t) html.table(T,header=True) 
       

Click to the left again to hide and once more to show the dynamic interactive window

As you manipulate the Sagelet above, try to see what possibilities there are for the relative size of $\sigma(n)$ with respect to $n$ itself.   (Or, one can ask what the constant $C_n$ is such that $\sigma(n)=C_n\cdot n$.)

Quite a few certainly are above and below $2$.  If you look carefully, you will see that only one of the numbers above has a sum of divisors without 1 or 2 as the integer part.  What is it?

Another thing we can do is take big powers of numbers with lots of small prime divisors (and hence lots of factors).  Such numbers might get us big ratios.

@interact def _(n=[1..15]): html("Try $2^{%s}\cdot3^{%s}\cdot5^{%s}=%s$"%(n,n,n,2^n*3^n*5^n)) html("Then $\sigma(%s)=%s=%s\cdot %s\\approx %s\cdot %s$"%(2^n*3^n*5^n,sigma(2^n*3^n*5^n),sigma(2^n*3^n*5^n)/(2^n*3^n*5^n),2^n*3^n*5^n,(sigma(2^n*3^n*5^n)/(2^n*3^n*5^n)).n(digits=3),2^n*3^n*5^n)) 
       

Click to the left again to hide and once more to show the dynamic interactive window

You'll notice that although we quickly go above 3, but don't seem to get much further.  Why?

A helpful thing to think about with this is the following rewrite, using the formula for $\sigma(n)$: $$\frac{\sigma(n)}{n}=\frac{\prod_{i=1}^k \left(\frac{p_i^{e_i+1}-1}{p_i-1}\right)}{\prod_{i=1}^k p_i^{e_i}} = \prod_{i=1}^k\frac{p_i-1/p_i^{e_i}}{p_i-1} \approx \prod_{i=1}^k\frac{p_i}{p_i-1}\, ,$$ and we should expect this approximation to be very close when $e_i$ are all quite large.  So the idea is that since $\frac{p}{p-1}>1$, if we multiply by enough of these we will get very large numbers and so $\sigma(n)/n$ will be greater than any given $C$, and then $\sigma(n)>Cn$.  

Of course, $p=2$ is the best for this since $\frac{2}{2-1}=2$, but the others will hopefully be useful.  For instance, $n=2^{10} 3^{10}$ will have $$\sigma(n)/n=\frac{2-1/2^{10}}{2-1}\frac{3-1/3^{10}}{3-1} \approx \frac{2}{2-1}\frac{3}{3-1}=3$$ so certainly $\sigma(6^{10})$ will be nearly $3\cdot 6^{10}$.

If we multiply it by 5 as well that should do it, and that gives the results we saw in the previous cell. $$\frac{2-1/2^{10}}{2-1}\frac{3-1/3^{10}}{3-1}\frac{5-1/5}{5-1}\approx\frac{2}{2-1}\frac{3}{3-1}\frac{5}{5-1}=2\cdot \frac{3}{2}\cdot \frac{5}{4}=\frac{15}{4}=3.75\; .$$

(sigma(6^10)/(6^10)).n();(sigma(5*6^10)/(5*6^10)).n() 
       
2.99851822943128
3.59822187531753
2.99851822943128
3.59822187531753
(sigma(2^4*3^4*5^4*7)/(2^4*3^4*5^4*7)).n(digits=3) 
       
4.13
4.13
N = prod([p^4 for p in primes_first_n(100)]) (sigma(N)/N).n(digits=3) 
       
10.9
10.9

Continuing this for more primes suggests the following fact.

Fact:  For any positive $C$, there is a positive integer $n$ such that $$\sigma(n)>Cn\; .$$

The argument above not completely rigorous, but good enough for now.  It turns out that trying to prove it this way could bring the distribution of primes to the table.  Later we might see a more formal proof.

 

Now let's look for a moment at the perfect number question. We recall from last time's homework that when this ratio is exactly $2$, we say $n$ is a perfect number.  

This definition goes back quite a ways.  Euclid defines it at the beginning of his number-theoretic books, and only mentions it again over one hundred propositions later, where he proves that certain numbers are, in fact, perfect - a fitting end, as Dunham says in Journey through Genius

Theorem:

If $n$ is a number such that $2^n-1$ is prime, then the (even) number $2^{n-1}\left(2^n-1\right)$ is perfect.

Euclid's proof of this is worth looking at, in fact.

Many centuries later, Euler proved the converse.  

Theorem:

If $n$ is an even perfect number, it is the product of a power $2^{n-1}$ and a prime $2^n-1$.

Notice that these primes are precisely the Mersenne primes we discussed on Day 20! 

Proof:

First, assume that $2^n-1$ is prime.  Then the factors of $2^{n-1}\left(2^n-1\right)$ are coprime, so $$\sigma\left(2^{n-1}\left(2^n-1\right)\right)=\sigma\left(2^{n-1}\right)\sigma\left(2^n-1\right)=\left(2^n-1\right)\left(2^n-1+1\right)$$ The steps are because of multiplicativity and the formulas we had above for $\sigma$ of powers of two and primes.  But then $$\left(2^n-1\right)\left(2^n-1+1\right)=2^n\left(2^n-1\right)=2\left[2^{n-1}\left(2^n-1\right)\right]$$ so that the sum of divisors is exactly twice the original number.

Now for the converse, which is somewhat longer.  

If we have an even perfect number, then it is divisible by some power of two.  Let us (looking ahead!) call this the $n-1$th power!  So that our even perfect number is $2^{n-1}q$, where the $q$ is the (odd) quotient.  Let's divide the rest of the proof into steps.

  • We know that this number is perfect, so $$\sigma\left(2^{n-1}q\right)=2^nq$$
  • We also know how to compute $\sigma$, so $$\sigma\left(2^{n-1}q\right)=\sigma\left(2^{n-1}\right)\sigma(q)=\left(2^n-1\right)\sigma(q)$$
  • We can combine these to see that $$2^nq=\left(2^n-1\right)\sigma(q)$$ Note that this means $2^n-1\mid q$, since $q$ is the only odd part of the left-hand side.  Let's write $$\left(2^n-1\right)m=q\; .$$
  • But then $$2^n\left(2^n-1\right)m=\left(2^n-1\right)\sigma(q)\Rightarrow 2^nm=\sigma(q)$$
  • Notice that since $m$ and $q$ both divide $q$, by definition of $\sigma$ we have $$\sigma(q)\geq q+m=\left(2^n-1\right)m+m=2^nm$$ as well.
  • Since these two divisors alone add up to $\sigma(q)$, it must be true that $q$ has two divisors, so it is prime, and $m=1$, and $q=2^n-1$, and so the perfect number is $2^{n-1}\left(2^n-1\right)$. Great!

 

We will leave the question about whether there are odd perfect numbers to another day.

 

There are many things people have claimed about numbers of this type.  A Hellenistic Roman in the first century in Gerasa (the same place as the story of the demons called "Legion" who went into swine) named Nichomachus claimed that the $n$th perfect number had $n$ digits.  

He was more concerned with mystical claims about them (which many repeated), but this assertion continued to be made for over a thousand years; however, knowing what we do about Mersenne primes, we see that the fifth one is 13, so that the next perfect number, $$\left(2^{13}-1\right)\cdot 2^{12}\, ,$$ lay mysterious for a long time.  It was apparently discovered in the fifteenth century.

(2^13-1)*2^12 
       
33550336
33550336

Until the early modern period, such numbers were basically inaccessible.

It turns out that number theorists (often of the amateur variety, but certainly not always) have come up with all kinds of other names for similar things related to $\sigma(n)/n$.  

  • For instance, if $\sigma(n)=kn$ for some integer $k$, then we say that $n$ is k-perfect.  
  • Or, if $\sigma(n)>2n$, then $n$ is abundant.
  • If $\sigma(n)<2n$, we say $n$ is deficient.  
    • As it will turn out, these things are not really good characterizations of what it means to have "too many" or "too few" divisors, but in recognition of the Greeks' contributions we keep this allusive terminology.

These are all fairly standard terminology.  There are other ones that are less well-known, but nonetheless interesting.

  • A number is pseudoperfect if it is the sum of some of its divisors (other than itself).
  • A number $n$ is superabundant if $C_n=\sigma(n)/n$ is bigger than all $C_m$ for smaller $m$.
  • A number is weird if it is abundant but not pseudoperfect; see the handout.

One other interesting idea is that of amicable numbers, such that $\sigma(n)=\sigma(m)=m+n$.  Clearly any perfect number is amicable with itself.  The smallest pair of unequal amicable numbers is $(220,284)$; this was known to the ancient Greeks, cherished by some medieval Muslims, and apparently was not improved upon until the modern number-theoretic era.  Fermat, Descartes, and Euler all worked with this and found large examples, but it turns out that the next smallest pair was found by a sixteen-year old Italian boy in 1860!

sigma(1184);sigma(1210);1184+1210 
       
2394
2394
2394
2394
2394
2394

Apparently he came up with this by trial and error, though no one knows for sure.  Here is some of the most current data on these pairs.

There is a way to get as many amicable pairs as you like, discovered by Ibn Qurra and (later) Fermat, and used by Euler.

  • Make a list of numbers of the form $p_n=3\cdot 2^n-1$ and $q_n=9\cdot 2^{2n-1}-1$.  
  • Then check if $p_{n-1}$, $p_n$, and $q_n$ are all prime.  
  • If so, then $2^np_{n-1}p_n$ and $2^nq_n$ are an amicable pair.

Since only primes and powers of two are involved, it's easy to calculate $\sigma$ in this case, so proving it is left as an exercise.

@interact def _(n=[2..20]): html("We have $p_{%s}=%s$ and $p_{%s}=%s$"%(n,3*2^(n-1)-1,n,3*2^(n)-1)) html("And $q_{%s}=%s$ as well."%(n,9*2^(2*n-1)-1)) if is_prime(3*2^n-1) and is_prime(3*2^(n-1)-1) and is_prime(9*2^(2*n-1)-1): html("Then the pair $%s$ and $%s$ is amicable!"%(2^n*(3*2^(n-1)-1)*(3*2^(n)-1),2^n*(9*2^(2*n-1)-1))) else: html("Doesn't give an amicable pair") 
       

Click to the left again to hide and once more to show the dynamic interactive window

From now on, we will refer to $\sigma_0$ as $\tau$, just as we refer to $\sigma_1$ as $\sigma$.

Homework:

  1. Fill in details of Jones and Jones at the bottom of page 144 that the number of solutions of a (fixed) polynomial congruence modulo $n$ is a multiplicative function.
  2. Do Exercise 8.21 in Jones and Jones.
  3. Let $\tau_o(n)$ and $\sigma_o(n)$ be the same as $\tau$ and $\sigma$ but where only odd divisors of $n$ are considered; let $\tau_e$ and $\sigma_e$ be similar for even divisors of $n$.  Evaluate these functions for $n=1$ to $12$, and decide whether each of them is multiplicative or not (either proving it, or showing not by counterexample).
  4. Use the estimate above for $\sigma$ to find numbers for which $\sigma(n)>5n$ and $\sigma(n)>6n$.
  5. Discover and prove when $\tau(n)$ and $\sigma(n)$ are even and odd numbers.
  6. Show that if $n$ is odd then $\tau(n)$ and $\sigma(n)$ have the same parity.
  7. For which types of $n$ is $\tau(n)=4$?
  8. Prove that if $n\equiv 7$ mod (8), then $8\mid \sigma(n)$.
  9. Show that every prime power is deficient.
  10. Show that a multiple of an abundant number is abundant.
  11. Find a 4-perfect number.
  12. Computer $\sigma_{-1}$ for the numbers up to 30.  Come up with and prove a criterion for when $\sigma_{-1}=2$.
  13. Find three pseudoperfect numbers less than 100.
  14. Confirm what the article says about what the smallest weird number is.
  15. Confirm that if $p_n$, $p_{n-1}$, and $q_n$ are prime, then the numbers in question are amicable.