chap4.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\enddisplay
Furthermore, since $m_p$ and $n_p$ are nonnegative, we can rewrite this as
\g The dot product is zero, like orthogonal vectors.\g
\begindisplay
m\rp n\qquad\iff\qquad m_p n_p=0\quad\hbox{for all $p$}.
\eqno\eqref|rp-exp-zero|
\enddisplay
And now we can prove an important law by which we can
split and combine two $\rp$ relations with the same left-hand side:
\begindisplay
k\rp m\And k\rp n\qquad\iff\qquad k\rp mn\,.
\eqno\eqref|rp-split|
\enddisplay
In view of \eq(|rp-exp-zero|), this law is another way of saying
that $k_pm_p=0$ and $k_pn_p=0$ if and only if $k_p(m_p+n_p)=0$,
when $m_p$ and $n_p$ are nonnegative.

\smallskip
There's a beautiful way to construct the set of all nonnegative fractions
$m/n$ with $m\rp n$, called the {\it "Stern--Brocot tree"\/} because it
\g Interesting how mathematicians will say ``discovered'' when absolutely
 anyone else would have said ``invented.\qback''\g
was discovered independently by
Moriz "Stern"~[|stern|], a German mathematician,
and Achille "Brocot"~[|brocot|], a French clockmaker.
The idea is to start with the two fractions $({0\over1},{1\over0})$
and then to repeat the following operation as many times as desired:
\begindisplay
\hbox{Insert \ }{m+m'\over n+n'}\hbox{ \ between two adjacent fractions \ }
{m\over n}\hbox{ and }{m'\over n'}\,.
\enddisplay
The new fraction $(m+m')/(n+n')$ is called the {\it"mediant"\/} of
$m/n$ and $m'/n'$. For example, the first step gives us one new
entry between $0\over1$ and $1\over0$,
\begindisplay
\textstyle {0\over1},\,{1\over1},\,{1\over0}\,;
\enddisplay
and the next gives two more:
\begindisplay
\textstyle {0\over1},\,{1\over2},\,{1\over1},\,{2\over1},\,{1\over0}\,.
\enddisplay
The next gives four more,
\begindisplay
\textstyle {0\over1},\,{1\over3},\,{1\over2},\,{2\over3},\,{1\over1},\,
 {3\over2},\,{2\over1},\,{3\over1},\,{1\over0}\,;
\enddisplay
and then we'll get 8, 16, and so on. The entire array can be regarded as
an infinite "binary tree" structure whose top levels look like this:
"!tree"
\g I guess $1/0$ is infinity, ``in lowest terms.\qback''\g
\begindisplay
\unitlength=0.65pt
\def\\#1#2{\makebox(0,0){$#1\over#2$}}
\beginpicture(330,200)(0,0)
\put(5,190){\\01} \put(325,190){\\10}
\multiput(13,189)(8,-1){18}{\disk{.5}}
\multiput(317,189)(-8,-1){18}{\disk{.5}}
\put(165,170){\\11}
\put(93,134){\line(2,1){64}}
\put(237,134){\line(-2,1){64}}
\put(85,130){\\12} \put(245,130){\\21}
\multiput(53,98)(160,0){2}{\line(1,1){24}}
\multiput(277,98)(-160,0){2}{\line(-1,1){24}}
\put(45,90){\\13} \put(125,90){\\23} \put(205,90){\\32} \put(285,90){\\31}
\multiput(30,60)(80,0){4}{\line(1,2){9}}
\multiput(300,60)(-80,0){4}{\line(-1,2){9}}
\put(25,50){\\14} \put(65,50){\\25} \put(105,50){\\35} \put(145,50){\\34}
 \put(185,50){\\43} \put(225,50){\\53} \put(265,50){\\52} \put(305,50){\\41}
\multiput(18,20)(40,0){8}{\line(1,4){3.84615}}
\multiput(312,20)(-40,0){8}{\line(-1,4){3.84615}}
\put(15,9){\\15} \put(35,9){\\27} \put(55,9){\\38} \put(75,9){\\37}
  \put(95,9){\\47} \put(115,9){\\58} \put(135,9){\\57} \put(155,9){\\45}
 \put(175,9){\\54} \put(195,9){\\75} \put(215,9){\\85} \put(235,9){\\74}
  \put(255,9){\\73} \put(275,9){\\83} \put(295,9){\\72} \put(315,9){\\51}
\endpicture
\enddisplay
Each fraction is $m+m'\over n+n'$, where $m\over n$ is the nearest ancestor
above and to the left, and $\smash{m'\over n'}$
 is the nearest ancestor above and to
the right. (An ``"ancestor"'' is a fraction that's
 reachable by following the branches
upward.) Many patterns can be observed in this tree.

Why does this construction work? Why, for example, does each
mediant fraction $(m+m')/(n+n')$
turn out to be in lowest terms when it appears in this tree?
(If $m$, $m'$, $n$, and $n'$ were all odd, we'd get even/even; somehow
\g Conserve parody.\g
the construction guarantees that fractions with odd numerators and
denominators never appear next to each other.) And why do all possible
fractions $m/n$ occur exactly once? Why can't a particular fraction occur
twice, or not at all?

All of these questions have amazingly simple answers, based on the
following fundamental fact:
{\sl If\/ $m/n$ and\/ $m'/n'$ are consecutive fractions at any stage of
the construction, we have}
\begindisplay
m'n-mn'=1\,.
\eqno\eqref|sp-inv|
\enddisplay
This relation is true initially ($1\cdt1-0\cdt0=1$);
 and when we insert a new mediant
$(m+m')/(n+n')$, the new cases that need to be checked are
\begindisplay
&(m+m')n-m(n+n')=1\,;\cr
&m'(n+n')-(m+m')n'=1\,.\cr
\enddisplay
Both of these equations
 are equivalent to the original condition \thiseq\ that they
replace. Therefore \thiseq\ is "invariant" at all stages of the construction.

Furthermore, if $m/n<m'/n'$ and if all values are nonnegative, it's easy to
verify that
\begindisplay
m/n<(m+m')/(n+n')<m'/n'\,.
\enddisplay
A mediant fraction isn't halfway between its progenitors, but it does lie
somewhere in between. Therefore the construction preserves order, and we
couldn't possibly get the same fraction in two different places.
\g True, but if you get a compound fracture you'd better go see a doctor.\g

One question still remains. Can any positive fraction $a/b$ with
$a\rp b$ possibly be omitted? The answer is no, because we can
confine the construction to the immediate neighborhood of $a/b$, and in this
region the behavior is easy to analyze: Initially we have
\begindisplay
\textstyle{m\over n}={0\over1}<\bigl({a\over b}\bigr)<{1\over 0}={m'\over n'}\,,
\enddisplay
where we put parentheses around $a\over b$ to indicate that it's not really
present yet. Then if at some stage we have
\begindisplay
\textstyle{m\over n}<\bigl({a\over b}\bigr)<{m'\over n'}\,,
\enddisplay
the construction forms $(m+m')/(n+n')$ and there are three cases.
Either $(m+m')/(n+n')=a/b$ and we win;
or $(m+m')/(n+n')<a/b$ and we can set $m\gets m+m'$, $n\gets n+n'$;
or $(m+m')/(n+n')>a/b$ and we can set $m'\gets m+m'$, $n'\gets n+n'$.
This process cannot go on indefinitely, because the conditions
\begindisplay
\textstyle {a\over b}-{m\over n}>0\qquad{\rm and}\qquad {m'\over n'}-{a\over b}>0
\enddisplay
imply that
\begindisplay
an-bm\ge1\qquad{\rm and}\qquad bm'-an'\ge1\,;
\enddisplay
hence
\begindisplay
(m'+n')(an-bm)+(m+n)(bm'-an')&\ge m'+n'+m+n\,;
\enddisplay
and this is the same as $a+b\ge m'+n'+m+n$ by \eq(|sp-inv|).
Either $m$ or $n$ or $m'$ or $n'$
increases at each step, so we must win after at most $a+b$~steps.

The {\it "Farey series"\/} of order $N$, denoted by $\Fscr_N$, is the set
of all reduced fractions between $0$ and~$1$ whose denominators are
$N$ or less, arranged in increasing order. For example, if $N=6$ we have
\begindisplay
\def\\#1#2{{#1\over#2}}
\textstyle\Fscr_6=
\\01,\\16,\\15,\\14,\\13,\\25,\\12,\\35,\\23,\\34,\\45,\\56,\\11\,.
\enddisplay
We can obtain $\Fscr_N$ in general by starting with $\Fscr_1={0\over1},{1\over1}$
and then inserting mediants whenever it's possible to do so without getting a
denominator that is too large. We don't miss any fractions in this way,
because we know that the Stern--Brocot construction doesn't miss any, and
because a mediant with denominator $\le N$ is never formed from a fraction
whose denominator is $>N$. (In other words, $\Fscr_N$ defines a {\it subtree\/}
of the Stern--Brocot tree, obtained by pruning off unwanted branches.)
It follows that $m'n-mn'=1$ whenever $m/n$ and $m'/n'$ are consecutive
elements of a Farey series.

This method of construction reveals that $\Fscr_N$ can be obtained in
a simple way from $\Fscr_{N-1}$: We simply insert the fraction $(m+m')/N$
between consecutive fractions $m/n$, $m'/n'$ of $\Fscr_{N-1}$ whose
denominators sum to~$N$. For example, it's easy to obtain $\Fscr_7$
from the elements of $\Fscr_6$, by inserting
$1\over7$, $2\over7$, \dots,~$6\over7$ according to the stated rule:
\begindisplay
\def\\#1#2{{#1\over#2}}
\textstyle\Fscr_7=
\\01,\\17,\\16,\\15,\\14,\\27,\\13,\\25,\\37,\\12,
 \\47,\\35,\\23,\\57,\\34,\\45,\\56,\\67,\\11\,.
\enddisplay
When $N$ is prime, $N-1$ new fractions will appear; but otherwise we'll
have fewer than $N-1$, because this process generates only numerators
that are relatively prime to~$N$.

Long ago in \eq(|''|) we proved\dash---in different words\dash---that
whenever $m\rp n$ and $0<m\le n$ we can find integers $a$ and~$b$ such
that
\begindisplay
ma-nb=1\,.
\eqno\eqref|''1|
\enddisplay
(Actually we said $m'm+n'n=\gcd(m,n)$, but we can write $1$~for~$\gcd(m,n)$,
$a$~for~$m'$, and $b$~for~$-n'$.) The Farey series gives us another proof of
\thiseq, because we
can let $b/a$ be the fraction that precedes $m/n$ in $\Fscr_n$.
Thus \eq(|''|) is just \eq(|sp-inv|) again.
For example, one solution to $3a-7b=1$ is $a=5$, $b=2$, since $2\over5$
precedes $3\over7$ in $\Fscr_7$. This construction implies that
we can always find a
solution to \thiseq\ with $0\le b<a<n$, if $0<m\le n$. Similarly,
if $0\le n<m$ and $m\rp n$, we can solve \thiseq\ with $0<a\le b\le m$
by letting $a/b$ be the fraction that {\it follows\/} $n/m$ in $\Fscr_m$.

Sequences of three consecutive terms in a Farey series have an amazing property
that is proved in exercise~|farey3|. But we had better not discuss the
Farey series any further,
\g Farey 'nough.\g
because the entire Stern--Brocot tree turns out to be even more interesting.

We can, in fact, regard the Stern--Brocot tree as a {\it"number system"\/}
for representing rational numbers, because each positive, reduced fraction
occurs exactly once.
Let's use the letters $L$ and $R$ to
stand for going down to the left or right branch as we proceed from
the root of the tree to a particular fraction; then a string of $L$'s and
$R$'s uniquely identifies a place in the tree. For example, $LRRL$ means
that we go left from $1\over1$ down to $1\over2$, then right to $2\over3$,
then right to~$3\over4$, then left to~$5\over7$. We can consider $LRRL$
to be a representation of~$5\over7$. Every positive fraction gets
represented in this way as a unique string of $L$'s and $R$'s.

Well, actually there's a slight problem: The fraction $1\over1$ corresponds
to the {\it empty\/} string, and we need a notation for that. Let's agree
to call it $I$, because that looks something like $1$ and it stands for
``identity.\qback''

This representation raises two natural questions: (1)~Given positive integers
$m$ and~$n$ with $m\rp n$, what is the string of $L$'s and $R$'s that
corresponds to~$m/n$? (2)~Given a string of $L$'s and $R$'s, what fraction
corresponds to it? Question~2 seems easier, so let's work on it first.
We define
\begindisplay
f(S)=\hbox{fraction corresponding to $S$}
\enddisplay
when $S$ is a string of $L$'s and $R$'s. For example, $f(LRRL)={5\over7}$.

According to the construction, $f(S)=(m+m')/(n+n')$ if $m/n$ and $m'/n'$
are the closest fractions preceding and following~$S$ in the upper levels
of the tree. Initially $m/n=0/1$ and $m'/n'=1/0$; then we successively
replace either $m/n$ or $m'/n'$ by the mediant $(m+m')/(n+n')$ as we move
right or left in the tree, respectively.

How can we capture this behavior in mathematical formulas that are easy to
deal with? A bit of experimentation suggests that the best way is to
maintain a $2\times2$ matrix
\begindisplay
M(S)=\pmatrix{n&n'\cr m&m'\cr}
\enddisplay
that holds the four quantities involved in the ancestral fractions $m/n$
and $m'/n'$
enclosing~$f(S)$. We could put the $m$'s on top and the $n$'s on the bottom,
fractionwise; but this upside-down arrangement works out more nicely because
we have
$M(I)={1\,0\choose 0\,1}$
when the process starts, and $1\,0\choose0\,1$ is traditionally called
the identity matrix~$I$.

A step to the left replaces $n'$ by $n+n'$ and $m'$ by $m+m'$; hence
\begindisplay
M(SL)=\pmatrix{n&n+n'\cr m&m+m'\cr}=
\pmatrix{n&n'\cr m&m'\cr}\pmatrix{1&1\cr0&1\cr}=
M(S)\pmatrix{1&1\cr0&1\cr}\,.
\enddisplay
(This is a special case of the general rule
\begindisplay
\pmatrix{a&b\cr c&d\cr}\pmatrix{w&x\cr y&z\cr}=
 \pmatrix{aw+by&ax+bz\cr cw+dy& cx+dz\cr}
\enddisplay
for multiplying $2\times2$ matrices.)
\g If you're clueless about matrices, don't panic; this book uses them
only here.\g
Similarly it turns out that
\begindisplay
M(SR)=\pmatrix{n+n'&n'\cr m+m'&m'\cr}=M(S)\pmatrix{1&0\cr1&1\cr}\,.
\enddisplay
Therefore if we define $L$ and $R$ as $2\times2$ matrices,
\begindisplay
L=\pmatrix{1&1\cr0&1\cr}\,,\qquad R=\pmatrix{1&0\cr1&1\cr}\,,
\eqno\eqref|LR|
\enddisplay
we get the simple formula $M(S)=S$, by induction on the length of~$S$. Isn't that
nice? (The letters $L$ and $R$ serve dual roles, as matrices and as
letters in the string representation.) For example,
\begindisplay
\textstyle M(LRRL)=LRRL={1\,1\choose0\,1}
{1\,0\choose1\,1}
{1\,0\choose1\,1}
{1\,1\choose0\,1}
={2\,1\choose1\,1}
{1\,1\choose1\,2}
={3\,4\choose2\,3}\,;
\enddisplay
the ancestral fractions that enclose $LRRL={5\over7}$ are $2\over3$ and
$3\over4$. And this construction gives us the answer to Question~2:
\begindisplay
f(S)=f\biggl(\pmatrix{n&n'\cr m&m'\cr}\biggr)={m+m'\over n+n'}\,.
\eqno\eqref|f-of-S|
\enddisplay