MAT 338 Day 34 2011

2347 days ago by kcrisman

Remember, from now on we call $\sigma_0=\tau$ and $\sigma_1=\sigma$.  There are so many interesting things to be said about these functions!

Here is one.  $$\left(\sum_{d\mid n}\tau(d)\right)^2=\sum_{d\mid n}\tau(d)^3$$

@interact def _(n = 24): divs = divisors(n) html("The divisors of $%s$ are $%s$"%(n,divs)) html("And $\\tau$ of each of them is $%s$"%([sigma(div,0) for div in divs])) html("The sums are $%s$ and $%s$, respectively!"%(sum([sigma(div,0)^3 for div in divs]),sum([sigma(div,0) for div in divs])^2)) 
       

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

The easiest way to prove this is this:

  • First note that it's clearly true for a prime power $n=p^e$, for which $\tau(p^f)=f+1$, and all divisors of $n$ look like such a power of $p$.  
  • Then use the remarks from last time in the proof that $\sigma_i$ is multiplicative about what the divisors of $mn$ look like, and how a sum over divisors $d\mid mn$ can be a product of two different sums over divisors of $m$ and $n$.

Here's another largely open question which seems like it should be easy...  what rational numbers can be gotten as $\frac{\sigma(n)}{n}$? (Sometimes this ratio is called the abundancy index of $n$.)

@interact def _(n=(20,[1..200])): cols = (n//10)+1 T = [cols*['$n$','$\sigma(n)/n$']] list = [[i,(sigma(i)/i)] for i in range(1,n+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

There are some interesting theorems about this out there.  For one thing, the abundancy is also the same thing as $\sigma_{-1}(n)$; this is not hard to prove, but instructive.

  • We have that $$\sigma(n)/n=\left(\sum_{d\mid n}d\right)/n$$
  • But note that for every $d\mid n$, the quotient is also an integer divisor $d'$ of $n$.  So $$\sigma(n)/n=\sum_{d\mid n}\frac{1}{d'}$$
  • This is the same list as the original divisor list, so reordering gives $$\sigma(n)/n=\sum_{d\mid n}\frac{1}{d}=\sigma_{-1}(n)$$

A more nuanced view will ask what rational numbers are possible for the abundancy.  Clearly all such numbers are in the interval $\left[1,\infty\right)$!  Here are some more facts.

  • If $m\mid n$, then  $\sigma_{-1}(n)\geq \sigma_{-1}(m)$.
  • If $\sigma_{-1}(n)=\frac{a}{b}$ in lowest terms, then $b\mid n$.
  • If $r$ is 'caught' between $\sigma(n)$ and $n$ (such that $n<r<\sigma(n)$) and is relatively prime to $n$, then $r/n$ is not an abundancy index. (J. Holdener picturesquely calls rational numbers which are not abundancies abundancy outlaws.)
  • The end of this paper has a nice list of which numbers thus far have been found, and which have not.

What is particularly interesting about this is the connection to something we silently omitted last time - the question whether there are odd perfect numbers!

Fact:  $$\text{If }\frac{5}{3}\text{ is the abundancy index of }N\text{, then }5N\text{is an odd perfect number.}$$

However, we don't know whether this is ever true.

Open Question:  $$\text{Does there exist an odd perfect number?}$$

Yikes!  This question is still open after two and a half millennia.  We do know some things about the question, though.  First, recall that $$\frac{\sigma(n)}{n}=\prod_{i=1}^k\frac{p_i-1/p_i^{e_i}}{p_i-1}< \prod_{i=1}^k\frac{p_i}{p_i-1}$$ when $n$ is a product of the prime powers $p_i^{e_i}$.

  • An odd perfect number cannot be a prime power.  
    • This is easy; $2=\frac{\sigma(n)}{n}<\frac{p}{p-1}$ isn't possible, even for $p=2$; since we are looking for an odd perfect number, it definitely won't be possible!
  • An odd perfect number cannot be a product of exactly two prime powers.
    • Use the same idea, but now with the biggest possible values for odd primes.
  • An odd perfect number cannot be a product of exactly three prime powers unless the first two are $3^e$ and $5^f$.
    • Suppose that $3$ is not the smallest prime involved.  Then the biggest that $$\frac{p_1}{p_1-1}\frac{p_2}{p_2-1}\frac{p_3}{p_3-1}$$ can be is $$\frac{5}{4}\frac{7}{6}\frac{11}{10}=\frac{77}{48}<2\; .$$
    • Suppose that $5$ is not the second-smallest prime involved (assuming $3$ is the smallest).  We again get a contradiction.

Of course, this is pretty elementary.  There are many more criteria.  They keep on getting more complicated, so I can't list them all, but here is a selection, including information from two big searches going on right now.

  • Must be greater than $10^{1500}$.  (The proof of this is now nearly complete, at any rate; slightly smaller powers like 1250 are confirmed.)
  • Has at least 101 prime factors (not necessarily distinct).
  • At least 9 distinct prime factors.
  • Largest prime factor must be at least $10^8$.
  • Second largest prime exceeds $10000$.
  • The sum of the reciprocals of all odd perfect numbers is finite! (Though I cannot find a satisfactory reference for this - Dunham only references Klee and Wagon, which I don't have access to.)
  • Handout with yet another result - if $n$ is an odd perfect number, then $n\equiv 1\text{ mod }12$ or $n\equiv 9\text{ mod }36$.

Finally, here is the link to an article about Euler and his own criterion.  

  • An odd perfect number must be of the form $p^e m^2$, where $m$ is odd, $p$ is prime, and $p$ and $e$ are both $\equiv 1\text{ mod }(4)$.

Appropriate, since he finished the characterization of even perfect numbers.

Whew!  Fun, but at times overwhelming.

 

 

Well, we will now move on to think of a different way to think of these same functions.  We will examine, for the next week or so, different limits in number theory - and how integrals and calculus are inextricably bound up with this sort of question.  

Our motivational example was the one we discussed a few times ago.  Let $r(n)$ denote the number of ways to represent $n$ as a sum of squares - so that $r(3)=0$ but $r(9)=4$ and $r(5)=8$.  Then we saw, more or less rigorously, that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n r(k)=\pi\, .$$

But we can say more.  One intermediate step in our proof was the following:  $$\pi \left(1-\sqrt{\frac{2}{n}}+1/2n\right)\leq \frac{1}{n}\sum_{k=0}^{n}r(k)\leq \pi \left(1+\sqrt{\frac{2}{n}}+1/2n\right)\, ,$$ which we may think of in terms of an error (so using absolute values):  $$\left|\frac{1}{n}\sum_{k=0}^{n}r(k)-\pi\right|\leq \pi \left(\frac{\sqrt{2}}{\sqrt{n}}+1/2n\right)\leq Cn^{-1/2}\, ,\text{ for large enough }n,$$ where of course the value of $C$ is not just $\pi\sqrt{2}$, but something a little bigger because of the $1/2n$ term.

def r2(n): n = prime_to_m_part(n,2) F = factor(n) ret = 4 for a,b in F: if a%4==3: if b%2==1: return 0 else: n = prime_to_m_part(n,a) else: ret = ret * (b+1) return ret def L(n): ls = [] out = 0 for i in range(1,n+1): out += r2(i) ls.append((i,out/i)) return ls 
       
@interact def _(n=100): P = line(L(n)) P += plot(pi+pi*sqrt(2)/sqrt(x),x,3,n,color='red') P += plot(pi-pi*sqrt(2)/sqrt(x),x,3,n,color='red') P += plot(pi,x,3,n,color='red',linestyle='--') show(P) 
       

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

(As often happens with such things, the constant we proved is a lot bigger than it needs to be.)

It turns out there is a nice notation for this.  

Definition:

We say that $f(x)$ is $O(g(x))$ (eff of eks is Big Oh of gee of eks) if there is some constant for which $$|f(x)|\leq Cg(x)\text{ for all large enough }x\, .$$  So the average number of representations of an integer as a sum of squares is $\pi$, and if you do the average up to $N$, then the error will be no worse than some constant times $1/\sqrt{N}$, or Big Oh of $1/\sqrt{N}$.

(This is known as Landau notation.  It is unknown in this case, by the way, just how small that error term really is.  In 1906 it was shown that you could make it $O(x^{-2/3})$, but it is also known that you cannot make it $O(x^{-3/4})$.)  

@interact def _(n=100,C=pi): P = line(L(n)) P += plot(pi+C/x^(2/3),x,3,n,color='red') P += plot(pi-C/x^(2/3),x,3,n,color='red') P += plot(pi,x,3,n,color='red',linestyle='--') show(P) 
       

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

Now we want to apply these same ideas to the $\tau$ and $\sigma$ functions.

Questions: What is the "average" number of divisors of a positive integer?  What is the "average" sum of divisors of a positive integer?

It turns out that clever combinations of many ideas from the semester as well as calculus ideas will help us solve these questions!  And they will motivate us to ask the (much harder) similar questions one can ask about prime numbers.

def L(n): ls = [] out = 0 for i in range(1,n+1): out += sigma(i,0) ls.append((i,out/i)) return ls @interact def _(n=100): P = line(L(n)) show(P) 
       

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

This graphic shows how the average value of $\tau$ up to $n$ changes as we let $n$ get bigger.  This just isn't enough data to tell whether there is a limiting value for the average value of $\tau(n)$, even if you look out to the first 1000 integers.   Remember, every prime number contributes just 2 to the total (and so reduces the average value)!  But thinking about this might lead us to look a little deeper.

At the very least I can tell that the average value is Big Oh of a certain function.  We go right back to the sieve of Eratosthenes for this.  

  • Recall that we proved that in order to test whether $n$ is prime, you just have to check all numbers up through $\sqrt{n}$.
    • This is because any divisor $\sqrt{n}<d<n$ implies the existence of a divisor $\frac{n}{d}$ such that $$1=\frac{n}{n}<\frac{n}{d}<\frac{n}{\sqrt{n}}=\sqrt{n}\, .$$ 
  • So the absolute most number of divisors possible is if every number $d$ less than $\sqrt{n}$ was a divisor, and then all the $\frac{n}{d}>\sqrt{n}$ you get were also divisors - which is silly except for very small $n$, but let's go with it.  
  • Then you would have that $$\tau(n)\leq 2\sqrt{n}\text{, (so that }\tau(n)\text{ is }O(\sqrt{n}))\, .$$

But that is very important!  This means we can get a sense of what the average value of $\tau$ might be.  We certainly have that $$\frac{1}{n}\sum_{k=1}^n \tau(k)\leq \frac{1}{n}\sum_{k=1}^n 2\sqrt{k}=\sum_{k=1}^n \frac{1}{n}2\sqrt{n(k/n)}$$  You might wonder why I wrote the sum in this way.  The answer is that this looks an awful lot like a Riemann sum with $\Delta x=\frac{1}{n}$.  

You may likely recall writing a Riemann sum for $\int_0^1 x^2\; dx$ in the form $$\frac{1}{n}\left(\frac{1}{n}\right)^2+\frac{1}{n}\left(\frac{2}{n}\right)^2+\cdots+\frac{1}{n}\left(\frac{n}{n}\right)^2\; ;$$ this is the same thing for the function $2\sqrt{nx}$.   That would give.

$$\sum_{k=1}^n \frac{1}{n}2\sqrt{n(k/n)}\approx \int_0^1 2\sqrt{nx}dx=2\sqrt{n}\int_0^1 \sqrt{x}\; dx=\frac{4}{3}\sqrt{n}\, .$$  (See Appendix for rigorous version.)  Then one can write $$\frac{1}{n}\sum_{k=1}^n \tau(k)\text{ is }\frac{1}{n}\sum_{k=1}^n O(\sqrt{k})=O(\sqrt{n})\, ,$$ so that the average value is also bounded by a constant time $\sqrt{n}$ - implying perhaps that the average number of divisors goes steadily up! 

But how does it go up?  

line(L(1000000)) 
       

Here, out to one million, is once again our graph of $\tau$ versus $n$.  Certainly this looks sort of like some kind of fractional exponent function, though a very slowly growing one - probably slower than $\sqrt{x}$, our first estimate.   We'll see what happens next time.

 

Homework:

  1. Do Exercise 8.21 in Jones and Jones.
  2. 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 by proving it, or by showing it's not by counterexample).
  3. Use the estimate above for $\sigma$ to find numbers for which $\sigma(n)>5n$ and $\sigma(n)>6n$.
  4. Discover and prove when $\tau(n)$ and $\sigma(n)$ are even and odd numbers.
  5. Show that if $n$ is odd then $\tau(n)$ and $\sigma(n)$ have the same parity.
  6. For which types of $n$ is $\tau(n)=4$?
  7. Show that a multiple of an abundant number is abundant.
  8. Find a 4-perfect number.
  9. Do one of the following:
    • Find three pseudoperfect numbers less than 100.
    • Confirm what the article says about what the smallest weird number is.
  10. Confirm that if the numbers (from last time's notes) $p_n$, $p_{n-1}$, and $q_n$ are prime, then the numbers in question are amicable.
  11. Do one of the following:
    • Do the first step in the proof that $\left(\sum_{d\mid n}\tau(d)\right)^2=\sum_{d\mid n}\tau(d)^3$.
    • Do the second step in the proof that $\left(\sum_{d\mid n}\tau(d)\right)^2=\sum_{d\mid n}\tau(d)^3$.
  12. Prove the first and second facts about the abundancy index.
  13. Find five numbers that must be abundancy outlaws based on the facts (don't just copy from the list).
  14. Do one of the following:
    • Fill in the details in the proof of odd perfect numbers needing at least three prime divisors and that $3$ and $5$ would need to be the first two if that were the case.
    • Read the article about Euler and odd perfect numbers, and restate and reprove his criterion in modern notation.
 
       

Appendix:

To make the calculation of $O(\sqrt{n})$ rigorous, we will need to make a slight change of point of view in order to ensure it will be viewed as a left-hand sum of an increasing function (and hence the Riemann sum is less than the actual value of the integral): $$\frac{1}{n}\sum_{k=1}^n 2\sqrt{k}=\sum_{k=0}^{n-1}\left(\frac{1}{n}\right)2\sqrt{k+1}=\sum_{k=0}^{n-1}\left(\frac{1}{n}\right)2\sqrt{n(k/n)+1}\leq \int_0^1 2\sqrt{nx+1}\; dx$$  And then, since this $$=\frac{4}{3}\sqrt{n}\left[\left(1+\frac{1}{n}\right)^{3/2}-\left(\frac{1}{n}\right)^{3/2}\right]$$ and since the big fudge factor on the right can be shown to be decreasing using derivatives, and is always less than $2$ for integers, it will always be less than $\frac{8}{3}\sqrt{n}$ and so our calculation that the average value of $\tau$ is $O(\sqrt{n})$ is correct.