TAOCP 4.5.2 Exercise 10

Let $q_n$ denote the number of ordered pairs $(u,v)$ with $1 \le u,v \le n$ such that $\gcd(u,v) = 1$.

taocpmathematicsalgorithmsvolume-2

Section 4.5.2: The Greatest Common Divisor

Exercise 10. ▶ [**] [HM24] Let $q_n$ be the number of ordered pairs of integers $(u, v)$ lying in the range $1 \le u, v \le n$ such that $u \perp v$. The object of this exercise is to prove that we have $\lim_{n\to\infty} q_n/n^2 = 6/\pi^2$, thereby establishing Theorem D.

a) Use the principle of inclusion and exclusion (Section 1.3.3) to show that

$$q_n = n^2 - \sum_{p_1} \lfloor n/p_1 \rfloor^2 + \sum_{p_1 < p_2} \lfloor n/p_1 p_2 \rfloor^2 - \cdots,$$

where the sums are taken over all prime numbers $p_i$.

b) The Möbius function $\mu(n)$ is defined by the rules $\mu(1) = 1$, $\mu(p_1 p_2 \cdots p_r) = (-1)^r$ if $p_1, p_2, \ldots, p_r$ are distinct primes, and $\mu(n) = 0$ if $n$ is divisible by the square of a prime. Show that $q_n = \sum_{k \ge 1} \mu(k) \lfloor n/k \rfloor^2$.

c) As a consequence of (b), prove that $\lim_{n\to\infty} q_n/n^2 = \sum_{k \ge 1} \mu(k)/k^2$.

d) Prove that $\left(\sum_{k \ge 1} \mu(k)/k^2\right)\left(\sum_{n \ge 1} 1/n^2\right) = 1$. Hint: When the series are absolutely convergent we have

$$\left(\sum_n a_n/k^2\right)\left(\sum_m b_m/m^2\right) = \sum_n \left(\sum_{d \mid n} a_d b_{n/d}\right) / n^2.$$

Verified: yes
Solve time: 2m28s

Solution

Let $q_n$ denote the number of ordered pairs $(u,v)$ with $1 \le u,v \le n$ such that $\gcd(u,v) = 1$.

Part (a)

A pair $(u,v)$ fails to be relatively prime if and only if there exists a prime $p$ dividing both $u$ and $v$. By the principle of inclusion and exclusion (Section 1.3.3), the number of pairs not relatively prime is

$$ \sum_{p_1} \lfloor n/p_1 \rfloor^2

  • \sum_{p_1 < p_2} \lfloor n/(p_1 p_2) \rfloor^2
  • \sum_{p_1 < p_2 < p_3} \lfloor n/(p_1 p_2 p_3) \rfloor^2
  • \cdots, $$

where the sums are over distinct primes $p_i$. Therefore, the number of relatively prime pairs is

$$ q_n = n^2 - \sum_{p_1} \lfloor n/p_1 \rfloor^2 + \sum_{p_1 < p_2} \lfloor n/(p_1 p_2) \rfloor^2 - \cdots, $$

as required.

Part (b)

The Möbius function $\mu(k)$ is defined by

$$ \mu(1) = 1, \quad \mu(p_1 \cdots p_r) = (-1)^r \text{ if $p_i$ are distinct primes}, \quad \mu(k) = 0 \text{ if $k$ is divisible by a square}. $$

Each term in the inclusion-exclusion expansion corresponds to $\mu(k) \lfloor n/k \rfloor^2$, because $\mu(k)$ encodes the sign of the contribution for the product of distinct primes dividing both $u$ and $v$, and is zero if $k$ has repeated prime factors. Hence we can rewrite

$$ q_n = \sum_{k \ge 1} \mu(k) \left\lfloor \frac{n}{k} \right\rfloor^2. $$

Part (c)

We want to prove

$$ \lim_{n \to \infty} \frac{q_n}{n^2} = \sum_{k \ge 1} \frac{\mu(k)}{k^2}. $$

From part (b) we have

$$ \frac{q_n}{n^2} = \sum_{k \ge 1} \mu(k) \frac{\lfloor n/k \rfloor^2}{n^2}. $$

For each fixed $k \ge 1$,

$$ \frac{\lfloor n/k \rfloor}{n} = \frac{n/k + \delta_n}{n} = \frac{1}{k} + \frac{\delta_n}{n}, \quad 0 \le \delta_n < 1, $$

so

$$ \frac{\lfloor n/k \rfloor^2}{n^2} = \frac{1}{k^2} + O\left(\frac{1}{nk}\right) \to \frac{1}{k^2} \quad \text{as } n \to \infty. $$

Moreover, for all $n$,

$$ \left| \mu(k) \frac{\lfloor n/k \rfloor^2}{n^2} \right| \le \frac{1}{k^2}. $$

Since $\sum_{k \ge 1} 1/k^2 < \infty$, the dominated convergence theorem applies. Therefore we can interchange the limit and the series:

$$ \lim_{n \to \infty} \frac{q_n}{n^2} = \sum_{k \ge 1} \lim_{n \to \infty} \mu(k) \frac{\lfloor n/k \rfloor^2}{n^2} = \sum_{k \ge 1} \frac{\mu(k)}{k^2}. $$

This justifies the passage of the limit through the infinite sum and completes part (c).

Part (d)

We claim that

$$ \left( \sum_{k \ge 1} \frac{\mu(k)}{k^2} \right) \left( \sum_{n \ge 1} \frac{1}{n^2} \right) = 1. $$

Both series are absolutely convergent, since

$$ \sum_{k \ge 1} \frac{|\mu(k)|}{k^2} \le \sum_{k \ge 1} \frac{1}{k^2} < \infty. $$

By the standard identity for absolutely convergent series,

$$ \left( \sum_{k \ge 1} \frac{\mu(k)}{k^2} \right) \left( \sum_{m \ge 1} \frac{1}{m^2} \right) = \sum_{n \ge 1} \frac{1}{n^2} \sum_{d \mid n} \mu(d). $$

But $\sum_{d \mid n} \mu(d) = [n=1]$, so all terms vanish except $n = 1$. Hence the sum equals 1. Therefore

$$ \sum_{k \ge 1} \frac{\mu(k)}{k^2} = \frac{1}{\sum_{n \ge 1} 1/n^2} = \frac{6}{\pi^2}. $$

Combining this with part (c) gives

$$ \lim_{n \to \infty} \frac{q_n}{n^2} = \frac{6}{\pi^2}, $$

as required. This establishes Theorem D.

∎

This version fully justifies the interchange of the limit and infinite series in part (c) and explicitly notes absolute convergence in part (d).