Arithmetic Functions

note

This is Lab 17 from Clint by Hugh Montgomery, edited by Codex and Elad Zelingher. All rights reserved to Hugh Montgomery.

A function is called an arithmetic function if its domain is the set of positive integers (or perhaps the set Z of all integers). Among the most important and useful arithmetic functions are the following: The number $\omega(n)$ of distinct primes dividing $n$, $\omega(n)=\sum_{p\mid n}1$. The number $\Omega(n)$ of primes dividing $n$, counting multiplicity, $\Omega(n)=\sum_{p^a\mathbin\Vert n}a$. The Möbius $\mu$-function, which is defined to be $(-1)^{\Omega(n)}$ if $n$ is squarefree, and 0 otherwise. The divisor function $d(n)$, which is the number of positive divisors of $n$, $d(n)=\sum_{d\mid n}1$. By the Chinese Remainder Theorem, we may show that $d(n)=\prod_{p^k\mathbin\Vert n}(k+1)$. The Euler $\phi$-function, which counts the number of reduced residues modulo $n$. By using the Chinese Remainder Theorem we know that $\phi(n)=n\prod_{p\mid n}(1-1/p)$. The $\sigma$-function is the sum of the positive divisors of $n$, $\sigma(n)=\sum_{d\mid n}d$. By using the Chinese Remainder Theorem we may show that $\sigma(n)=n\prod_{p^a\mathbin\Vert n}(1-1/p^{a+1})/(1-1/p)$.

Problem 1

The program ArFcnTab provides a table of the six arithmetic functions defined above. You may use the pagination controls to page up or page down through the table. By entering a number in “Jump to $n=$,” you may jump to a different part of the table. By scrolling down through the table, make a list of those $n\leq200$ for which $d(n)$ is odd. Formulate a conjecture. Can you prove it? (Theorem 4.3 of NZM is usefl here.)

Problem 2

For $1\leq n\leq10$, compute a table of values of the function $\sum_{d\mid n}\mu(d)$. Choose an $n$ at random, $1\leq n\leq10^9$. Use the program Factor to factor $n$, and then list the divisors of $n$. For each $d$ dividing $n$, use the factorization of $d$ to determine the value of $\mu(d)$, and confirm that ArFcnTab provides the same values. For this $n$, evaluate $\sum_{d\mid n}\mu(d)$. Formulate a conjecture concerning the values of this sum. (See Theorem 4.7 of NZM.)

Problem 3

For $1\leq n\leq10$, construct a table of the values of $\sum_{d\mid n}\phi(d)$. Choose a large $n$ at random, $1\leq n\leq10^9$. Use Factor to factor $n$, and construct a list of the divisors of $n$. Use ArFcnTab to provide the values of $\phi(d)$ for these divisors, and hence evaluate the sum $\sum_{d\mid n}\phi(d)$. Formulate a conjecture regarding the values of this sum. (See Theorem 4.6 of NZM.)

Problem 4

Make a list of those $n$, $1\leq n\leq50$, for which $\omega(n)=\Omega(n)$. What do you notice about the prime factorizations of these $n$? Describe these $n$ in some other way.

Problem 5

Using ArFcnTab, look for small values of $\omega(n)$. Other than $\omega(1)=0$, what is the smallest value you find? When does it take this small value? Does it take this value infinitely many times? Why? Now look for large values of $\omega(n)$. Make a list of those $n$, $1\leq n\leq500$, for which $\omega(n)$ is larger than any previous values. That is, if $1\leq m<n$ then $\omega(m)<\omega(n)$. Give the prime factorization of each of these $n$. Formulate a conjecture regarding these $n$. Can you prove your conjecture? (See Theorem 8.30 in NZM.)

Problem 6

Proceed as in the preceding problem, but with $\omega(n)$ replaced by $\Omega(n)$. (Problem 10 at the end of §8.3 is relevant here.)

Problem 7

Construct a list of those $n$, $1\leq n\leq100$ for which $\phi(n)$ is larger than any preceding value. That is, if $1\leq m<n$ then $\phi(m)<\phi(n)$. Formulate a conjecture regarding these $n$. What information would you need concerning the distribution of prime numbers in order to prove your conjecture?

Problem 8

Construct a table of those $n$, $1\leq n\leq50$, for which $\phi(n)/n$ is smaller than any preceding value. That is, if $1\leq m<n$ then $\phi(m)/m>\phi(n)/n$. Formulate a conjecture concerning this set of integers $n$. Can you prove your conjecture? (Problem 15 at the end of §8.3 of NZM is relevant here.)

Problem 9

Construct a table of the values of $\sum_{d^2\mid n}\mu(d)$, for $1\leq n\leq20$. Formulate a conjecture concerning the values taken by this sum. Can you prove your conjecture? (See the proof of Theorem 8.25 in NZM.)

Problem 10

Construct a table of the values of $2^{\omega(n)}$, of $d(n)$, and of $2^{\Omega(n)}$, for $1\leq n\leq20$. Formulate a conjecture concerning the relative sizes of these three functions. Can you prove your conjecture? (See the discussion in the middle of p. 395 of NZM.)

Problem 11

A number $n$ is called perfect if $\sigma(n)=2n$. That is, $n$ is the sum of its proper divisors. What perfect numbers do you find in the interval $1\leq n\leq50$? It has long been conjectured that there are no odd perfect numbers—indeed, this is very probably the oldest unsolved problem in all of mathematics. By examining the values provided by ArFcnTab, confirm that the numbers $496$, $8128$, and $33550336$ are also perfect. Factor these numbers, and note that their prime decompositions exhibit a common pattern. Can you show that all even perfect numbers are of this shape?

Problem 12

The values of some of our six arithmetic functions tend to be correlated. For example, $\omega(n)$ tends to be large (but is not always large) when $\Omega(n)$ is large. In the case of $\phi(n)$ and $\sigma(n)$, the correlation is negative: $\sigma(n)$ tends to be large when $\phi(n)$ is small. To investigate this principle in a quantitative form, tabulate the values of $\phi(n)\sigma(n)/n^2$ for $1\leq n\leq10$, and also for several large values of $n$. Do all the values observed lie in the interval $[6/\pi^2,1]$? If so, why should they?

Problem 13

Although $d(n)$ takes on some large values for large $n$, these values are small compared with fractional powers of $n$. More precisely, for any $\delta>0$ there is a constant $C_{\delta}$ such that $d(n)\leq C_\delta n^\delta$ for all positive integers $n$. Tabulate the values of $d(n)/\sqrt n$ for $1\leq n\leq15$. What is the largest value observed? This is the unique maximum of this function. The unique maximum of $d(n)/n^{1/3}$ is attained at $n=2520$. What is this maximum value? The maximum of $d(n)/n^{1/4}$ is attained at $n=21621600$. What is this maximum? The maximum of $d(n)/n^{1/5}$ occurs at $n=6064949221531200$. What is this maximum? Here $n>10^9$, so you are now beyond the range of ArFcnTab. To calculate $d(n)$ you must factor $n$ and use the formula. The maximum of $d(n)/n^{1/6}$ occurs at $n=2^6\cdot3^4\cdot5^3\cdot7^2\cdot11^2\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47\cdot53\cdot59\cdot61$. What is this maximum? To understand how these $n$ are found, see the discussion leading to (8.54) on pp. 395–396 of NZM. This analysis goes back to S. Ramanujan, Highly Composite Numbers, Proc. London Math. Soc. 2 1915, 347–409; Collected Papers pp. 78–128. The set of $n$ for which $d(n)$ assumes a record-breaking value is not so easy to describe completely, although Ramanujan determined many of its properties.

Problem 14

One might expect that the Möbius function takes the values $+1$ and $-1$ with roughly equal frequency. To test this hypothesis, put $M(x)=\sum_{1\leq n\leq x}\mu(n)$, and tabulate $M(x)$ for integral values of $x\leq100$. Here only squarefree numbers are being counted, so it is natural to consider also $L(x)=\sum_{1\leq n\leq x}(-1)^{\Omega(n)}$. Form a similar table of this function. How do the values of these functions compare with $\sqrt x$? Here the numerical evidence may lead you to formulate false conjectures. It was conjectured by Mertens that $|M(x)|\leq\sqrt x$ for all $x\geq1$. Although it is now believed that $\limsup M(x)/\sqrt x=+\infty$, the first disprove of Mertens' conjecture was found only recently (A. M. Odlyzko and H. J. J. te Riele, Disproof of the Mertens Conjecture, J. Reine Angew. Math. 357 (1985), 138–160). The argument disproves Mertens' conjecture by showing that $\limsup M(x)/\sqrt x>1.06$. Concerning $L(x)$, Pólya conjectured that $L(x)<0$ for all $x\geq2$. This was disproved by C. B. Haselgrove, A disproof of a conjecture of Pólya, Mathematika 5 (1958), 141–145, and later R. Sherman Lehman, On Liouville's function, Math. Comp. 14 (1960), 311–320 showed more explicitly that $L(906180359)=1$. This is not necessarily the least counterexample, but it is known that Pólya's conjecture is true for all $x\leq6\cdot10^6$.

Problem 15

The program Pi calculates the number $\pi(x)$ of primes not exceeding $x$. The program operates by first sieving to construct a table of primes not exceeding $31607$. Since the next prime after this, namely $31621$, is larger than $\sqrt{10^9}$, it follows that primes up to $10^9$ can be determined by using these small primes for sieving. To limit the use of memory, the primes are constructed in intervals of length $10^4$, one interval at a time, until the limit $x$ is reached. The program is restricted to $x\leq10^6$, because the running time (which is roughly comparable to $x$) is too great for larger $x$. For $x=10^k$, $1\leq k\leq6$, how does $\pi(x)$ compare with $x/\log x$? A better approximation is given by

$$\operatorname{li}x=\int_2^x\frac{du}{\log u},$$

but numerical values of this integral are not so easy to compute.

Faster methods of computing $\pi(x)$ are discussed in the following papers.

J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi(x)$: The Meissel-Lehmer method, Math. Comp. 44 (1985), 537–560.

J. C. Lagarias and A. M. Odlyzko, New algorithms for computing $\pi(x)$, Number Theory: New York 1982, (D. V. Chudnovsky, G. V. Chudnovsky, H. Cohn and M. B. Nathanson, eds.), pp. 176–193; Lecture Notes in Mathematics 1052, Springer-Verlag (Berlin), 1984.

J. C. Lagarias and A. M. Odlyzko, Computing $\pi(x)$: an analytic method, J. Algorithms 8 (1987), 173–191.

Problem 16

G. H. Hardy and S. Ramanujan proved that for most integers $n$, both $\omega(n)$ and $\Omega(n)$ are approximately $\log\log n$. Their proof was complicated; the more elegant method used in proving Theorem 8.32 and Corollary 8.33 of NZM was found later by P. Turán. This has an interesting consequence: Since $2^{\omega(n)}\leq d(n)\leq2^{\Omega(n)}$ for all $n$, it follows that for most $n$, $(\log n)^{c-\epsilon}<d(n)<(\log n)^{c+\epsilon}$ where $c=\log2=0.693\ldots$. Using ArFcnTab, compute the averages of $\omega(n)$ and $\Omega(n)$ in the intervals $(10^k-50,10^k]$ for $1\leq k\leq9$, and compare these averages with $\log\log10^k$. (Remember, as always to use natural logarithms, i.e., logs to the base $e$.)

Problem 17

By borrowing code from the program Pi, construct a program to count the number $\pi_2(x)$ of twin primes not exceeding $x$. Does this function increase at a regular rate? For interesting information regarding the distribution of prime numbers, see Don Zagier, The First $50$ Million Prime Numbers, Math. Intell. 1 (1978), 7–19.