I’m trying to understand the answer to exercise 4.5.2-10(c) in Knuth’s The Art of Computer Programming. Let $q_n$ denote the number of ordered pairs of integers $(u,v)$ in the range $1\leq u,v \leq n$ such that $u$ and $v$ are relatively prime. We’re trying to prove that

$$ \lim_{n\rightarrow\infty} \frac{q_n}{n^2} = \sum_{k\geq 1} \frac{\mu (k)}{k^2} $$

where $\mu$ denotes the Möbius function. We already showed in part (b) that $q_n = \sum_{k\geq 1} \mu (k)\lfloor n/k \rfloor ^2$.

I’ve already read the (rather terse) answer that Knuth provides, in which he asserts that

$$q_n - \sum_{k\geq 1} \mu (k) (n/k)^2 = O(n H_n) - O(n).$$

I have convinced myself on paper that this is true, but I’m having trouble understanding how this proves the limit. Since $nH_n$ increases as a function of $n$, it seems to me that this should imply the two functions only get further apart as $n$ increases. Any insight would be much appreciated :)

  • 3
    $\begingroup$ $H_n = o(n)$, so $O(nH_n) = o(n^2)$; also $O(n) = o(n^2)$. Then you get the claim dividing both sides of the last equality by $n^2$. $\endgroup$ – zhoraster Jul 24 '19 at 7:34
  • 1
    $\begingroup$ In other words, your worry is that the absolute error is large—but that's not a problem, because the relative error is small. $\endgroup$ – Greg Martin Jul 24 '19 at 8:27
  • $\begingroup$ @zhoraster Thanks for your help! I just need another nudge for the VERY last step. The equality can be manipulated to become $q_n/n^2 - \sum_{k\geq 1} \mu(k) / k^2 = o(1)$, which implies that the the difference $\leq c$ for some positive real $c$. Now given an $\epsilon > 0$ how do I use this to get $q_n/n^2$ within $\epsilon$ of $\sum_{k\geq 1}\mu(k) / k^2$? Thanks and sorry if I'm not catching something that is entirely obvious! $\endgroup$ – marcelgoh Jul 24 '19 at 10:14
  • $\begingroup$ Sorry about my last comment, I mixed up my definitions of big-o and little-o. Little-o means that for any choice of $c$ the inequality holds, i.e. for all $\epsilon > 0$ we have the difference $\leq \epsilon$, which proves the limit. Edit: @zhoraster Would you be able to post the comment as an answer so I can accept it? (I think this is how it works -- I'm new to the site.) $\endgroup$ – marcelgoh Jul 24 '19 at 10:24

$H_n=o(n)$, so $O(nH_n)=o(n^2)$; also $O(n)=o(n^2)$. Then you get the claim dividing both sides of the last equality by $n^2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.