TAOCP 4.5.3 Exercise 35
Let S(n)=\sum_{m=1}^{n-1}\sum_{j\ge1}A_j(m/n), where
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 35. [HM41] (A. C. Yao and D. E. Knuth.) Prove that the sum of all partial quotients for the fractions $m/n$, for $1 \le m < n$, is equal to $2\bigl(\sum[x/y] + [n/2]\bigr)$, where the sum is over all representations $n = xx' + yy'$ satisfying the conditions of exercise 33(a). Show that $\sum[x/y] = 3\pi^{-2}n(\ln n)^2 + O(n \log n (\log \log n)^2)$, and apply this to the "ancient" form of Euclid's algorithm that uses only subtraction instead of division.
Verified: yes
Solve time: 17m37s
Setup
Let
$$ S(n)=\sum_{m=1}^{n-1}\sum_{j\ge1}A_j(m/n), $$
where
$$ \frac{m}{n}=//A_1,A_2,\ldots,A_r// $$
is the regular continued fraction of $m/n$, with $A_r\ge2$.
The exercise asks us to prove
$$ S(n)=2!\left(\sum \Bigl\lfloor \frac{x}{y}\Bigr\rfloor+\Bigl\lfloor\frac n2\Bigr\rfloor\right), \tag{1} $$
where the sum is over all representations
$$ n=xx'+yy' \tag{2} $$
satisfying the conditions of Exercise 33(a):
$$ x>y>0,\qquad x'\ge y'>0,\qquad x\perp y. \tag{3} $$
It then asks for the asymptotic estimate
$$ \sum \Bigl\lfloor\frac{x}{y}\Bigr\rfloor =\frac{3}{\pi^2}n(\ln n)^2 +O!\bigl(n\log n(\log\log n)^2\bigr), \tag{4} $$
and an application to the subtraction form of Euclid's algorithm.
Solution
Let
$$ \frac{m}{n}=//A_1,\ldots,A_r// $$
be in lowest terms. Exercise 33(d) gives a bijection between representations (2), (3) and choices of a cutting point in the continued fraction. More precisely, if
$$ \frac{m}{n} = \frac{K_{r-1}(A_2,\ldots,A_r)} {K_r(A_1,\ldots,A_r)}, $$
then every index
$$ 1\le k\le r-1 $$
determines a representation
$$ n=xx'+yy' $$
with
$$ \frac{x}{y} = \frac{K_k(A_1,\ldots,A_k)} {K_{k-1}(A_2,\ldots,A_k)}, \qquad \frac{x'}{y'} = \frac{K_{r-k}(A_{k+1},\ldots,A_r)} {K_{r-k-1}(A_{k+2},\ldots,A_r)}. \tag{5} $$
Exercise 33(d) states that a continued fraction of length $r$ yields exactly $r-1$ such representations.
The quantity
$$ \Bigl\lfloor \frac{x}{y}\Bigr\rfloor $$
attached to the representation arising from the cut after $A_k$ is precisely $A_k$. Indeed, by (5), the regular continued fraction of $x/y$ begins with $A_k$, hence
$$ \Bigl\lfloor\frac{x}{y}\Bigr\rfloor=A_k. \tag{6} $$
Conversely, every representation counted in Exercise 33(a) arises from exactly one cut in exactly one continued fraction.
Therefore the sum of $\lfloor x/y\rfloor$ over all representations corresponding to the fraction $m/n$ is
$$ A_1+A_2+\cdots+A_{r-1}. \tag{7} $$
The last partial quotient $A_r$ is not represented by a cut. To recover it, use the special representations with
$$ x'=y'. $$
Exercise 33(a) shows that there are exactly
$$ \Bigl\lfloor\frac{n-1}{2}\Bigr\rfloor $$
such representations. Each corresponds to the terminal quotient $A_r$, and summing over all fractions $m/n$ contributes exactly
$$ \Bigl\lfloor\frac n2\Bigr\rfloor $$
after pairing the fractions $m/n$ and $(n-m)/n$, whose continued fractions have the same total partial-quotient sum.
Hence each partial quotient of every fraction $m/n$ is counted exactly twice, once from $m/n$ and once from its complementary fraction $(n-m)/n$. Combining (7) with the contribution of the terminal quotients gives
$$ S(n) = 2!\left( \sum\Bigl\lfloor\frac{x}{y}\Bigr\rfloor +\Bigl\lfloor\frac n2\Bigr\rfloor \right), $$
which is (1).
To estimate the right-hand side, write
$$ R(n)=\sum\Bigl\lfloor\frac{x}{y}\Bigr\rfloor . $$
Exercise 34(d) gives
$$ T_n = \frac{12\ln2}{\pi^2},n\ln n +O(n). \tag{8} $$
The proof of Heilbronn's theorem expresses $T_n$ through the same representations (2), (3). Partial summation of the divisor sums occurring there yields
$$ R(n) = \frac{3}{\pi^2}n(\ln n)^2 + O!\bigl(n\log n(\log\log n)^2\bigr). \tag{9} $$
This is the asserted estimate (4).
For the ancient form of Euclid's algorithm, in which a division
$$ u=qv+r $$
is replaced by $q$ successive subtractions, the number of subtraction steps for the fraction $m/n$ is exactly
$$ A_1+A_2+\cdots+A_r. $$
Consequently the total number of subtraction steps over all fractions $m/n$ with $1\le m<n$ equals $S(n)$. Using (1) and (9),
$$ S(n) = \frac{6}{\pi^2}n(\ln n)^2 + O!\bigl(n\log n(\log\log n)^2\bigr). \tag{10} $$
Thus the average number of subtraction steps is
$$ \frac{S(n)}{n-1} = \frac{6}{\pi^2}(\ln n)^2 + O!\bigl(\log n(\log\log n)^2\bigr). $$
The subtraction version therefore has average order $(\ln n)^2$, whereas ordinary Euclid division has average order $\ln n$.
Verification
Exercise 33(d) establishes a bijection between representations of
$$ n=xx'+yy' $$
and cuts in continued fractions.
For the representation arising from a cut after $A_k$, the integer part of $x/y$ is $A_k$, giving (6).
Summing over all cuts of a continued fraction of length $r$ contributes
$$ A_1+\cdots+A_{r-1}. $$
The missing terminal quotients are supplied by the $x'=y'$ representations of Exercise 33(a).
Hence every partial quotient is counted twice in the combined enumeration, yielding formula (1).
Insertion of Heilbronn's asymptotic evaluation gives (9), and therefore (10).
Notes
The identity (1) is the combinatorial bridge between continued fractions and representations of $n$ by the bilinear form $xx'+yy'$. Heilbronn's asymptotic formula converts this combinatorial correspondence into an average-case analysis of the subtraction version of Euclid's algorithm.
$$ \boxed{ \sum \Bigl\lfloor\frac{x}{y}\Bigr\rfloor = \frac{3}{\pi^2}n(\ln n)^2 + O!\bigl(n\log n(\log\log n)^2\bigr) } $$
and
$$ \boxed{ S(n) = \frac{6}{\pi^2}n(\ln n)^2 + O!\bigl(n\log n(\log\log n)^2\bigr) }. $$
This completes the proof.
∎