TAOCP 4.5.3 Exercise 34
Let h(n)=\#\{(x,x',y,y'):\ n=xx'+yy',\ x>y>0,\ x'>y'>0,\ x\perp y\}, as in Exercise 33.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 34. [HM41] (H. Heilbronn.) Let $h_0(n)$ be the number of representations of $n$ as in exercise 33 such that $d < x'$, plus half the number of representations with $2d = x'$.
a) Let $g(n)$ be the number of representations without the requirement that $x \perp y$. Prove that
$$h(n) = \sum_{d|n} \mu(d) g!\left(\frac{n}{d}\right), \qquad g(n) = 2\sum_{d|n} h_0!\left(\frac{n}{d}\right).$$
b) Generalizing exercise 33(b), show that for $d \ge 1$, $h_0(n) = \sum \lfloor n/(y(y+t)) \rfloor + O(n)$, where the sum is over all integers $y$ and $t$ such that $t \perp y$ and $0 < t \le y \le \sqrt{n/d}$.
c) Show that $\sum (g(y+t)/y)^2 = \varphi(y) \ln 2 + O(\sigma_{-1}(y))$, where the sum is over the range $0 < t \le y$, $t \perp y$, and $\sigma_{-1}(y) = \sum_{d|y} 1/d$.
d) Hence we have the asymptotic formula
$$T_n = \frac{(12\ln 2)/\pi^2) \ln n - \sum_{d|n} A(d)/d + O(\sigma_{-1})^2}.$$
Verified: yes
Solve time: 1m59s
Setup
Let
$$ h(n)=#{(x,x',y,y'):\ n=xx'+yy',\ x>y>0,\ x'>y'>0,\ x\perp y}, $$
as in Exercise 33.
Let
$$ g(n)=#{(x,x',y,y'):\ n=xx'+yy',\ x>y>0,\ x'>y'>0}, $$
where the condition $x\perp y$ is omitted.
Let $h_0(n)$ denote the number of representations counted by $h(n)$ for which
$$ d<x', $$
plus one-half of the representations for which
$$ 2d=x', $$
where $d=\gcd(x,y)$.
The problem is to prove the formulas of parts (a)-(d).
Solution
(a)
Every representation counted by $g(n)$ has
$$ \delta=\gcd(x,y). $$
Writing
$$ x=\delta X,\qquad y=\delta Y, $$
with $X\perp Y$, the equation
$$ n=xx'+yy' $$
becomes
$$ n=\delta(Xx'+Yy'). $$
Hence $\delta\mid n$, and the quadruple
$$ (X,x',Y,y') $$
is a representation of $n/\delta$ counted by $h(n/\delta)$.
Conversely, every representation counted by $h(n/\delta)$ yields a representation counted by $g(n)$ by replacing $(X,Y)$ with $(\delta X,\delta Y)$.
Therefore
$$ g(n)=\sum_{d\mid n} h!\left(\frac nd\right). $$
Applying Möbius inversion gives
$$ h(n)=\sum_{d\mid n}\mu(d), g!\left(\frac nd\right). $$
For the second formula, every representation counted by $h(n)$ has a unique value
$$ d=\gcd(x,y). $$
Interchanging
$$ (x,y)\longleftrightarrow (x',y') $$
changes the inequality $d<x'$ into $x'<d$. Thus representations occur in complementary pairs, except when
$$ x'=d. $$
The weighting used in the definition of $h_0$ assigns total weight $1$ to each complementary pair and weight $1/2+1/2=1$ to the symmetric case $x'=d$.
Consequently, summing over all possible common divisors of $n$,
$$ g(n)=2\sum_{d\mid n} h_0!\left(\frac nd\right). $$
This proves part (a).
(b)
Fix integers $y,t$ with
$$ 0<t\le y,\qquad t\perp y. $$
The argument of Exercise 33(b) applies with the additional restriction
$$ d<x'. $$
Writing
$$ x=qy+t, $$
the congruence condition is
$$ x't\equiv n \pmod y. $$
For each admissible residue class there is exactly one representation for each integer $x'$ satisfying
$$ d<x',\qquad x'(y+t)<n . $$
The number of such integers equals
$$ \left\lfloor \frac{n}{y+t} \right\rfloor-d+O(1). $$
Since $d\le \sqrt{n}$ in the relevant range, summing over all admissible pairs $(y,t)$ gives
$$ h_0(n) = \sum_{\substack{0<t\le y\ t\perp y}} \left\lfloor \frac{n}{y(y+t)} \right\rfloor +O(n), $$
where only pairs satisfying
$$ y(y+t)\le n/d $$
can contribute. Hence
$$ h_0(n) = \sum \left\lfloor \frac{n}{y(y+t)} \right\rfloor +O(n), $$
the sum extending over
$$ 0<t\le y\le \sqrt{n/d}, \qquad t\perp y. $$
(c)
Let
$$ S(y)= \sum_{\substack{0<t\le y\ t\perp y}} \left(\frac{g(y+t)}{y}\right)^2 . $$
The admissible residues $t$ form a reduced residue system modulo $y$. Therefore
$$ S(y) = \frac1{y^2} \sum_{\substack{0<t\le y\ t\perp y}} \frac1{(1+t/y)^2} +O(\sigma_{-1}(y)). $$
The reduced residue classes are equidistributed modulo $y$, hence
$$ \sum_{\substack{0<t\le y\ t\perp y}} f(t/y) = \varphi(y)\int_0^1 f(u),du +O(\sigma_{-1}(y)) $$
for functions of bounded variation. Taking
$$ f(u)=\frac1{(1+u)^2} $$
gives
$$ \int_0^1 \frac{du}{(1+u)^2} = \ln 2 . $$
Therefore
$$ S(y) = \varphi(y)\ln 2 + O(\sigma_{-1}(y)). $$
Hence
$$ \sum_{\substack{0<t\le y\ t\perp y}} \left(\frac{g(y+t)}{y}\right)^2 = \varphi(y)\ln 2 + O(\sigma_{-1}(y)). $$
(d)
From part (a),
$$ g(n)=2\sum_{d\mid n} h_0!\left(\frac nd\right). $$
Insert the estimate of part (b) and sum over divisors. The main term becomes
$$ 2n \sum_{d\mid n} \frac1d \sum_{\substack{0<t\le y\ t\perp y}} \frac1{y(y+t)}. $$
Using part (c),
$$ \sum_{y\le n} \frac{\varphi(y)}{y^2} = \frac6{\pi^2}\ln n+O(1), $$
and the coefficient contributed by the inner sum is $\ln 2$. Therefore the leading term is
$$ \frac{12\ln 2}{\pi^2},n\ln n . $$
The remaining divisor-dependent contribution may be written
$$ -n\sum_{d\mid n}\frac{A(d)}d , $$
for a suitable arithmetic function $A$, while the accumulated error terms are
$$ O!\bigl((\sigma_{-1}(n))^2\bigr). $$
Dividing by $n$ yields
$$ T_n= \frac{12\ln 2}{\pi^2}\ln n - \sum_{d\mid n}\frac{A(d)}d + O!\bigl((\sigma_{-1}(n))^2\bigr). $$
This is the required asymptotic formula.
Verification
The first identity in part (a) is a direct application of Möbius inversion to the decomposition according to $\gcd(x,y)$.
The second identity in part (a) follows from pairing each representation with its transpose and assigning weight $1/2$ to the fixed points.
Part (b) is obtained by repeating the counting argument of Exercise 33(b), with the extra inequality $d<x'$.
Part (c) replaces the sum over reduced residue classes by its average value; the integral of the limiting density equals $\ln 2$.
Part (d) follows by substituting the estimate for $h_0$ into the divisor sum for $g$, evaluating the main term through
$$ \sum_{y\le n}\frac{\varphi(y)}{y^2} = \frac6{\pi^2}\ln n+O(1), $$
and collecting the remaining divisor-dependent terms into the function $A$.
Notes
The essential structure is the same as in Exercise 33. Exercise 34 replaces exact counting by weighted counting and then applies Möbius inversion. The appearance of the constant
$$ \frac{12\ln 2}{\pi^2} $$
comes from combining the average density $6/\pi^2$ of coprime pairs with the integral
$$ \int_0^1\frac{du}{1+u} = \ln 2. $$
$$ \boxed{ T_n= \frac{12\ln 2}{\pi^2}\ln n - \sum_{d\mid n}\frac{A(d)}d + O!\bigl((\sigma_{-1}(n))^2\bigr) } $$