% В тираж
\documentstyle{amsppt}
\loadbold
\NoBlackBoxes
\TagsAsMath
\TagsOnRight
\magnification 1200

\topmatter
\leftheadtext{Lines on Grid Paper and Superwords}
\rightheadtext{Lines on Grid Paper and Superwords}
\address
\endaddress
\email
kanel\@mccme.ru \,\, M.L\@gerver.mccme.ru
\endemail
\endtopmatter

\define\ar{\rightleftarrows}
\define\a{\alpha}
\redefine\b{\beta}
\define\f{\varphi}
\define\p{\Pi}
\redefine\l{\lambda}

\document
\centerline
{A. Belov-Kanel, M. Gerver}
\head
Lines on Grid Paper and Superwords
\endhead

Let line $L$ on the grid paper not pass through its knots.
let us write letters $v$ and $h$ on all intersections of $L$ with
verticals and horizontals of the grid, respectively.

Now we have {\it words \/} composed of letters $v$ and $h$ on all finite
segments of $L$; on the entire line $L$ there appears a sequence $W_L$
which is infinite both ways.

Such sequences $W_L$ are called {\it superwords}.

We consider line $L$ {\it oriented}: a direction on $L$ is chosen.
If we switch it then superword $W_L$ will read in the opposite direction.
For example, {$\{\dots vvh\, vvh\, vh\dots\}$
will look like $\{\dots hv\, hvv\, hvv\dots\}$.} \smallpagebreak

{\bf Main questions:} What singles $W_L$ out of all two-letter superwords?
And how combinatorial properties of $W_L$ are related
to geometric properties of line~$L$ and arithmetical properties of
slope and intercept of $L$?

{\bf Announcement:} Shortly we will present a procedure that relates
superword $W_L$ with the continued fraction expansion of the slope of line
$L$.

The following examples give an idea of what a continued fraction is:

\eightpoint
$$
\frac{11}{25}=
\dsize\frac{1}{2+\dsize\frac{1}{3+\dsize\frac{1}{1+\frac{1}{2}}}},
\quad
\frac{5}{8}=
\dsize\frac{1}{1+\dsize\frac{1}{1+\dsize\frac{1}{1+\frac{1}{2}}}},
\quad
\frac{\sqrt5-1}{2} =
\dsize\frac{1}{1+\dsize\frac{1}{1+\dsize\frac{1}{1+\dots}}},
$$
$$
\frac{8}{5} = 1+\dsize\frac{1}{1+\dsize\frac{1}{1+\frac{1}{2}}}, \quad
\frac{\sqrt5+1}{2} =
1+\dsize\frac{1}{1+\dsize\frac{1}{1+\dsize\frac{1}{1+\dots}}}, \quad
\sqrt2+1 =
2+\dsize\frac{1}{2+\dsize\frac{1}{2+\dsize\frac{1}{2+\dots}}}.
$$
\tenpoint

A little later we will talk about continued fractions and their geometric
interpretation ({\it nose stretching} algorithm) in more detail.
Now concentrate on the following question: if the slope of $L$ equals one
of the above {\it periodic\/} continued fraction, how can this periodicity
be seen in $W_L$?

\subhead{\quad Terminology}\endsubhead
The following terminology helps us to be concise and precise. %\newline %
A {\it word} is a finite sequence of characters; a {\it superword} is
an infinite (both ways) sequence of characters. A {\it subword} is a
word that is a fragment of another word (or superword).
The {\it length\/} of a word is the number of characters in it.
For example, words  $vv$, $vh$, $aba$, $001$ are some of the subwords
of length 2 and 3 in superwords $\{\dots vvhvvhv\dots\}$, $\{\dots
aabaaba\dots\}$, $\{\dots 0010010\dots\}$.

\subhead{\quad Class $S$}\endsubhead By $S$ denote the class of all
superwords $W=W_L$ corresponding to all oriented lines $L$ that pass
through no knots on the grid paper.

Alongside with $S$ we consider a few more classes of superwords:
carefully mixed superwords,
superwords with slowly growing subword sets, and others.

Comparing these classes with $S$ we will find that $W_L$ exhibit
a number of beautiful properties.

Further questions await an interested reader, among them there are
unsolved problems.

\head {Preparatory problems} \endhead
Some of the following problems are really simple, others are more
difficult.

Hint: if you get stuck with a problem, move on and come back when you
have more problems solved.

0.1. Give an example of word~$W$ of letters $v$, $h$,
that certainly does not belong to $S$.

0.2.1. For which lines~$L$ superwords~$W_L$ from class $S$ are
periodic?

0.2.2. For which lines $L$ letters $v$ come in superwords $W_L\in S$
more often than letters~$h$?

0.2.3. Substitute $h \ar v$ in a superword~$W_L$ from
$S$. Will the resulting superword $W^{\prime}$ remain in $S$?
In other words, is it always true that $W^{\prime} = W_{L^{\prime}}$ for
some line $L^{\prime}$? If so, how is line $L^{\prime}$
related to $L$?

\subhead
{\quad
Strip polygons $M_w$}
\endsubhead
Fix a square $K_0$ on grid paper
and to each word $w$ of $n$ letters~$w_j$

\centerline
{$w = \{w_1, \dots, w_n\}$ \,
(each letter $w_j$ is either $v$ or $h$),}

\noindent
relate a polygon $M_w$ that consists of $n+1$ squares
$K_0, K_1, \dots, K_n$, according to the following rule.
Square $K_1$ is adjacent to $K_0$ from above if
$w_1=h$ and from right if $w_1=v$. Similarly, if $j-$th
letter is $w_j=h$ then $K_j$ is adjacent to $K_{j-1}$ from above
(their common side is {\it horizontal}) and if $w_j=v$ then $K_j$
is adjacent to $K_{j-1}$ from right (their common side is {\it vertical}).

We will call such polygons $M_w$ {\it strip polygons}.
Polygon $M_w$ lies in several consecutive rows on the grid paper.
In any of these rows squares that belong to $M_w$ form a {\it strip}
(i.e., quadrangle $1 \times \l,\, \l\ge 1$; values $\l=\l_s$ depend on
the row number). For strips in two consecutive rows the
{\it rightmost\/} square of the lower strip lies under the {\it
leftmost\/} square of the upper strip.

There is a one-to-one correspondence between strip polygons
$M_w$ and words $w$ of letters~$v$~and~$h$:
not only does $M_w$ uniquely determine $w$, but vice versa
as well.  Therefore we can {\it identify \/} words $w$ with
polygons $M_w$ and speak about properties of words and superwords
geometrically - as properties of strip polygons.

\subhead
{\quad Permitted and Forbidden Words}
\endsubhead

We call a word $w$ of letters $v$~and~$h$ {\it permitted} if it is
a subword of a certain superword $W_L \in S$ and  {\it
forbidden} otherwise.

Geometrically, if  $w$ is a {\it permitted} word then one can cross
all squares of $M_w$ by a single line $L$ that contains no knots;
if $w$ is a {\it forbidden} word then there exists no such line.

0.3. Prove thaT $\{ h\, v\, v\, v\, h\, v\, v\, h \}$ is a permitted
word and hence there exists a superword
$W = \{\dots h\, v\, v\, v\, h\, v\, v\, h \dots\} \in S$.

0.3.1. How many letters $v$ can $W$ have between {\it consecutive\/}
letters $h$, i.e., letters $h$ between which there are no other
letters $h$? Is it true that either $2$ or $3$?

0.3.2. List all possible subwords of lengths 2, 3 and 4 in
$W$.

0.3.3. Find two lines $L$ and $L^*$,
such that $W_L$ and $W_{L^*}$ contain subword
$ h v v v h v v h $ (as in 0.3).

0.3.4. Is it true that for all $W_L$ and $W_{L^*}$
sets of all subwords (a) of length 5; (b) of length 6; (c) of length 7
necessarily coincide?

0.4.1. Can it happen that all subwords of a certain superword $W$
are permitted, but $W \not\in S$?

0.4.2. Can $W_L$ and $W_{L^*}$ coincide while $L$ and $L^*$ do not?

0.4.3. Can the sets of all subwords of superwords $W_L$ and $W_{L^*}$
coincide, while $W_L$ and $W_{L^*}$ do not?

0.5.1. Erase one letter $v$ in front of each $h$ in $W \in S$ from 0.3.

Will the resulting superword
$\{\dots h v v h v h \dots\}$ still belong to class $S$?

0.5.2. Erase one letter $v$ in front of each $h$
in any superword~$W$ from $S$.

Will the resulting superword still belong to $S$?

0.6. Insert one $v$ in front of each $h$ in any
superword~$W$ from $S$.

Will the resulting superword still belong to $S$?

\subhead{\quad Classification of Superwords $W \in S$}\endsubhead

Ascribe $W=W_L \in S$ to $S^h$ if line~$L$ is {\it slanting}:
its slope is less than one; if instead~$L$ is {\it
steep} (i.e., its slope is above one) ascribe
$W=W_L \in S$ to $S^v$.
Isolate superword $\{\dots v\, h\, v\, h \dots\}$, for which
the slope is equal to one, to a special class~$E$.

Ascribe superword
$W \in S^h$ to $S^h_n$, $n = 1,\, 2,\, 3, \dots$,
if one of the following holds:

a) between any two consecutive letters $h$ in $W$
there are $n$ letters $v$,

b) between any two consecutive letters $h$ in $W$ there are either
$n+1$ or $n$ letters $v$.

Similarly,
ascribe $W \in S^v$ to $S^v_n$, $n = 1,\, 2,\, 3, \dots$,
if between any two consecutive letters $v$ in $W$ there are
(a) $n$ letters $h$, \,\, (b) either $n+1$ or $n$ letters $h$.

Isolate $\{\dots v\, v\, v\, \dots\}$ and
 $\{\dots h\, h\, h \dots\}$
to subclasses $S^h_{\infty}$ and $S^v_{\infty}$.

\smallpagebreak

0.7. Prove that the union of all $S^h_n$, $1 \le n \le {\infty}$,
coincides with $S^h$ and the union of all $S^v_n$, $1 \le n \le {\infty}$,
coincides $S^v$.

Equivalently: prove that each superword $W \in S$ belongs to exactly
one subclass:

\centerline
{either $E$, \, or $S^h_n$ or $S^v_n$, $1 \le n < {\infty}$, \,
or $S^h_{\infty}$ or $S^v_{\infty}$.}

0.7.1. Interpret 0.7  geometrically in terms of strip polygons:
what values can take lengths $\l_s$ of strips of polygon
$M_w$ for permitted word $w$ which is a subword of
superword $W \in S^h$?

0.7.2. Give a periodic forbidden word $w$,
for which all strips of $M_w$ are of lengths 2~and~3.

\subhead{\quad 0.8. Reorganization of superwords $W$,
series of numbers $a_j$ and continued fractions}\endsubhead

We take a word $W\in S$ and start to
{\it reorganize } it, turning it successively into superwords $W_j$,
$j\ge 1$: \,\, $W \to W_1 \to W_2 \to \dots$,
and simultaneously constructing a  {\it series of numbers
$a_j$} according to the following rules.

Any superword $W$ from $S$ belongs to either $E$ or $S^h$ or
$S^v$. Assume $W \in S^h$. Then, by 0.7,
$W \in S^h_n$ for some $n$, \, $1 \le n \le {\infty}$.

If $n = {\infty}$ (i.e., if $W \in S^h_{\infty}$), no reorganization is
made.

If $n = a_1 < {\infty}$ erase $a_1$ letters $v$
in front of each $h$ and call the resulting superword~$W_1$.
Clearly $W_1$ belongs to $S^v$ (why?), and, therefore,
belongs to $S^v_n$ for some $n$.

If $n = {\infty}$ the reorganization is finished.

If $n = a_2 < {\infty}$,
erase $a_2$ letters $h$ in front of each $v$. We get $W_2$ and so on.
\pagebreak

0.8.1. Let the slope of line $L$ be equal to a
{\it finite\/} continued fraction, for instance, one of the following:

\eightpoint
$$
\frac{11}{25}=
\dsize\frac{1}{2+\dsize\frac{1}{3+\dsize\frac{1}{1+\frac{1}{2}}}},
\quad
\frac{7}{24}=
\dsize\frac{1}{3+\dsize\frac{1}{2+\dsize\frac{1}{3}}},
\quad
\frac{4}{19}=
\dsize\frac{1}{4+\dsize\frac{1}{1+\dsize\frac{1}{3}}},
\quad
\frac{5}{8}=
\dsize\frac{1}{1+\dsize\frac{1}{1+\dsize\frac{1}{1+\frac{1}{2}}}}.
$$

\tenpoint

For each of the above fractions find the series $a_1,\, a_2,\, \dots, a_n$
for superword $W=W_L$ corresponding to line $L$.

0.8.2. It follows from 0.8.1. that for certain $L$
reorganizations of $W=W_L$ may stop after finitely many steps:
$W \to W_1 \to W_2 \to \dots \to W_n$.

Classify {\it all\/} such~$L$ and for them state explicitly how
series $a_1,\, a_2,\, \dots, a_n$ are related to expansion of
the slope $k_L$ into continued fraction.

We will soon come back to studying relationship between continued
fractions and series $a_j$ but before we analyze some properties of
superwords.

\subhead
{ \quad 1. Class $S_1$: Carefully Mixed Words and Superwords}
\endsubhead

Just for a change in the following problems we assume that superwords
$W$ consist of letters $a$~and~$b$. When relating to superwords from class
$S$ one can substitute $a \ar h, \,\, b \ar v$.

Let a word (or a superword) $W$ be such that for every two its
subwords $U$~and~$V$ of the same length the number of letters $a$
in~$U$~and in~$V$ is different by at most one (the same then
applies to the number of letters $b$).  We call such $W$ {\it
carefully mixed\/} words (superwords) and ascribe them to class $S_1$.

1.1. Give an example of carefully mixed superword.

Our immediate goal is to study the following two questions:

I. Is it true that every permitted word is carefully mixed?

II. Is it true that $S \subset S_1$?

The following exercises will help.

1.2.1. Is it true that every permitted word is a subword for
infinitely many different superwords $W_L$ from~S?

1.2.2. Is it true that every permitted word is a subword of a
superword $W_L$ from~$S$ for a line $L$ with rational slope $k_L$?

1.2.3. Is it true that superword $W$ is carefully mixed if every its
subword is carefully mixed?

1.3. Let a word (or a superword) $W$ be splittable into subwords of the
following two types:

$ab^n$~(a letter $a$ is followed by $n$ letters $b$) and
$ab^{n+1}$ (a letter $a$ is followed by $n+1$ letters $b$).

Perform the following {\it renaming}: substitute $b$ for each $ab^{n+1}$
and $a$ for each $ab^{n}$.
The resulting word (or superword) denote by $W^*$.

1.3.1. Is it true that after renaming permitted words go to
permitted words and forbidden words go to forbidden words?
What happens to strip polygons?

Hint: on the grid paper introduce coordinates $x, y$ and consider mapping
$F$ sending point $\{x,y\}$ to $\{x-ny, -x+(n+1)y\}$.

1.3.2. Is it true that after renaming

words $W\in S_1$ go to $W^*\in S_1$,
while words $W \not\in S_1$  go to $W^*\not\in S_1$?

1.4.1. Prove that every permitted word is carefully mixed.

1.4.2. Prove that every superword $W \in S$ is carefully mixed.

1.4.3. Give an example of carefully mixed superword $W \not\in S$.

1.5. Is it true that in alphabet \{$a$; $b$\} for every positive
integers $m$ and $n$ there exists a periodic carefully mixed
superword such that its period has $m$ letters $a$ and $n$ letters $b$?

1.6.1. Does there exist a carefully mixed finite word that can
not be a subword of a carefully mixed superword?

1.6.2. Is it true that any carefully mixed word is permitted?

1.7. Find all superwords $W$ such that {$W \in S_1$ and $W \not\in S$.}

1.8. Generalize the definition of carefully mixed words onto words
over alphabets of more that two letters. Is it true that no carefully
mixed word of letters $a,b,c$ contains subword $aa$?

\subhead
{ \quad 2. Class $S_2$: Superwords with Slowly Growing Subword
Sets} \endsubhead

2.1. Let $W$ be any superword of two letters and let $T_W(n)$ be the
number of different subwords of length $n$ in
$W$. What is the maximum possible value of $T_W(n)$?

2.2. Prove that if $T_W(k)=T_W(k+1)$ for some $k$ then
superwordо $W$ is periodic with period $T_W(k)$.

2.3. Let $T_W(k)<k+1$ for some $k$ (compare to 2.1).
Prove that superword $W$ is periodic.

Therefore, minimum value of $T_W(n)$ for a nonperiodic word $W$
is $n+1$. If this minimum is reached (see 2.4.2) and $T_W(k)=k+1$ for
all $k$ we call $W$ {\it a superword with slowly growing {\rm
(when $k$ increases)} subword set\/} and ascribe such $W$ to class $S_2$.

2.4. Prove that for all superwords $W \in
S$ inequality

\centerline
{$T_W(k) \le k+1$}
holds for all $k$.

2.4.1. Describe function $T_W(k)$ for superword $W=W_L$ when
the slope $k_L$ of line $L$ is rational number $m/n$
(for relatively prime $m$ and $n$).

2.4.2. Let $k_L$ be irrational. Prove that in this case
$W=W_L$ satisfies $T_W(k)=k+1$ for all $k$, i.e.,
$W\in S_2$.

2.4.3. Give an example of superword $W$
with slowly growing subword set that belongs neither to $S$ nor to $S_1$.

2.4.4. Find all superwords $W\in S_2$ such that
%Give an example of nonperiodic superword $W$ such that
{$W \in S_1$ and $W \not\in S$.}

%\centerline
%{$W \in S_2$ and $W \not\in S$.}

%2.4.3. Приведите пример сверхслова $W$ с~медленно растущим
%запасом подслов, не принадлежащего ни $S$, ни $S_1$.

%2.4.4. Найдите все сверхслова $W\in S_2$, такие что
%{$W \in S_1$ и $W \not\in S$.}

%NEUE!!!!!!!!!!!!!!!!!!!!!!

\subhead
{\quad Class $S_2$. Singular Words, Branching to the Left or to
the Right} \endsubhead

By $\p_W(n)$ denote the set of all subwords of length
$n$ for a superword $W$.

2.5.1. Consider a superword $W \in S_2$. Erase the leftmost letter in
each of the $n+1$ different subwords of length $n$ belonging to $\p_W(n)$.
Prove that each subword $U \in \p_W(n-1)$ will appear among
$n+1$ resulting words of length~$n-1$.

Therefore, all words $U \in \p_W(n-1)$ except one will appear once and
only one subword --- we call it {\it singular\/} or
{\it branching to the left\/} --- will appear twice.

The intuition behind the word 'branching': over the alphabet
\{$v$,$h$\} one can add both $v$ and $h$ to subword $U$ from the left,
while to nonsingular words one can add -- {\it
either $v$~or~$h$}.

% Смысл выбранного названия: к подслову $U$ слева можно приписать и
% $v$, и $h$, а к неособым подсловам -- {\it либо $v$, либо $h$}.

Prove that singular {\it branching to the left} subwords $U_n$ of length
$n$ form an embedded sequence
$U_1 \subset U_2 \subset \dots \subset U_n \subset U_{n+1} \subset
\dots$ (in other words, for each $n$ singular $U_n$
can be obtained by erasing the rightmost letter of $U_{n+1}$).

2.5.2. Similarly to 2.5.1. define {\it singular\/}
{\it branching to the right } subwords $V_n$ of a superword $W \in S_2$.

Prove that, likewise, singular {\it branching to the right\/} subwords
$V_n$ of length $n$ form an embedded sequence
$\dots \supset V_{n+1} \supset V_n \supset \dots \supset V_2 \supset V_1$.


%2.5.2. По аналогии с 4.1.1. определите {\it особые\/}
%подслов\'а $V_n$ сверхсл\'ова $W \in S_2$, {\it ветвящиеся вправо\/}.

%Докажите, что особые {\it ветвящиеся вправо\/} подслова
%$V_n$ длины $n$ тоже образуют вложенную последовательность:
%$V_1 \subset V_2 \subset \dots \subset V_n \subset V_{n+1} \subset \dots$.

2.5.3. Give an example of a superword $W \in
S_2$ such that $U_n \ne V_n$ for all $n$.

2.5.4. Give an example of a superword $W \in S_2$ such that
$U_n = V_n$ for infinitely many lengths $n$:
$U_{n_k} = V_{n_k}, \,\, k = 1,\, 2,\, 3,\, \dots$.

2.6.1. Is it true that $W \in S_2$ if and only if
for each $n$ there exists exactly one branching to the left subword
$U\subset W$ of length $n$?

2.6.2. Is it true that $W \in S_2$ if and only if
for each $n$ there exists exactly one branching to the right subword
$V\subset W$ of length $n$?

2.7. Which of the following superwords, each combined from two
periodic parts, belong to $S_2$?

$\{\dots v v v, hv^n hv^n hv^n\dots\}$, $n \ge 0$;
$\{\dots hv^2 hv^2 hv^2, hv^5 hv^5 hv^5\dots\}$;

$\{\dots hv \, hv \, hv \, hv, \, hvhvhvv \, hvhvhvv \, hvhvhvv
\dots\}$;

$\{\dots hv \, hv \, hv \, hv, \, hvhvvhvv \, hvhvvhvv \, hvhvvhvv
\dots\}$.

2.8.1. Find all superwords $W\in S_2$ such that
$W \not\in S_1$.

2.8.2. Suppose $W\in S_2$, $W \not\in S_1$. Prove that for any
subword $w\in W$ strip polygon $M_w$ can be crossed by two half-lines
with rational slopes (possibly depending on $w$).

2.8.3. Suppose $W\in S_2$, $W \not\in S_1$. Is it true that there
exist two rational numbers $k_1$ and $k_2$ such that for any subword $w\in
W$ strip polygon $M_w$ can be crossed by two half-lines with slopes
$k_1$ and $k_2$?  (with same $k_1$ and $k_2$ for all $w$).

\head
{Preparatory Problems: Lagrange and Hirzebruch fractions}
\endhead
The problems below are intended to accompany problems on superwords.
\subhead{\quad A. Geometry of Continued Fractions}
\endsubhead
Consider a quadrangle $\p$ with sides $p, q$, where $p$ and $q$ --
are mutually prime integers such that $1<p<q$. Adjoin as many
squares with side $p$ to the smaller side as will fit inside the
quadrangle (see the figure) and denote the number of them by
$a_1$; therefore, $$a_1p<q<(a_1+1)p.  \tag 1$$
Cutting these squares off $\p$ gives a new quadrangle $\p_1$
with sides $p_1=q-a_1p, \,\, q_1=p$, where, by (1), $1\le p_1<q_1$.

If $p_1=1$, assume $a_2=q_1=p$ and stop. If $p_1<1$, continue with
$\p_1$ what we did with $\p$: adjoin as many squares with side $p_1$ as
will fit inside $\p_1$ and denote the number of them by $a_2$.
Cutting them off $\p_1$ gives quadrangle $\p_2$ with sides
$p_2=q_1-a_2p_1, \,\, q_2=p_1$ and so on.
%
%\noindent
The construction stops at step $k$ if
$p_k=1$; in this case $a_k=q_k=p_{k-1}>1$.

A0.1. Prove that

\eightpoint
$$
\frac{p}{q} =
\dsize\frac{1}{a_1+\dsize\frac{1}{a_2+\dsize\frac{1}{a_3+\dots+
\dsize\frac{1}{a_k}}}}. \tag 2
$$

\tenpoint
Numbers $a_j$ in (2) are called {\it partial quotients\/} or
{\it elements\/} of a continued fraction.

All $a_j$ in (2), except $a_n$, can be any positive integers
while $a_n>1$.

A0.1. Alongside with finite one can consider infinite continued
fractions with any integers $a_0$ and positive integers $a_n,~n>0$;
Such an infinite continued fraction $c$ is defined as {\it the
limit\/} of finite continued fractions $c_k$ when $k \to \infty$:

\eightpoint
$$
c = a_0 +
\dsize\frac{1}{a_1+\dsize\frac{1}{a_2+\dsize\frac{1}{a_3+\dots}}} =
\lim c_k, \quad
c_k = a_0 +
\dsize\frac{1}{a_1+\dsize\frac{1}{a_2+\dsize\frac{1}{a_3+\dots+
\dsize\frac{1}{a_k}}}}.
$$

\tenpoint
Prove that $\lim c_k$ exists for any integer
$a_0$ and positive integers $a_n,~n>0$.

A1.1. We have just given a geometric interpretation of partial
quotients $a_1, \dots, a_k$ for the continued fraction expansion of a
rational number $p/q$. Give a similar interpretation for an irrational
number $\b$ expansion.

A1.2. Explain geometrically why $\b=\sqrt2+1$ or
$\b=(\sqrt5-1)/2$ give {\it periodic\/} continued fractions.

A1.3. Prove that a number $\b$ gives a {\it periodic\/} continued fraction
if and only if $\b$ is a {\it quadratic irrationality\/}, that is, $\b$ is
a root of a quadratic equation with integer coefficients.

Explain when the result is a periodic fraction with period
$\{a_1,\dots, a_p\}$ and when the period starts not from
$a_1$ but from $a_{k+1}$, i.e., looks like $\{a_{k+1}, \dots, a_{k+p}\}$.

A2. The continued fractions introduces above are called Lagrange
fractions  \footnote{Joseph Louis Lagrange (1736-1813) --
a great French mathematician.}.
Alongside with them we will be considering Hirzebruch continued fractions
\footnote{Friedrich Hirzebruch (born 1928) -- a prominent modern German
mathematician.}, finite or infinite:  \eightpoint

$$
\dsize\frac{1}{b_1-\dsize\frac{1}{b_2-\dsize\frac{1}{b_3-\dots-
\dsize\frac{1}{b_k}}}}, \quad
\dsize\frac{1}{b_1-\dsize\frac{1}{b_2-\dsize\frac{1}{b_3-\dots}}},
\quad \text{все }b_j \ge 2. \tag 3
$$

\tenpoint
Check the following examples:
\eightpoint
$$
\dsize\frac{4}{5} =
\dsize\frac{1}{2-\dsize\frac{1}{2-\dsize\frac{1}{2-
\dsize\frac{1}{2}}}}, \quad
\dsize\frac{5}{8} =
\dsize\frac{1}{2-\dsize\frac{1}{3-\dsize\frac{1}{2}}}, \quad
\dsize\frac{3-\sqrt5}{2} =
\dsize\frac{1}{3-\dsize\frac{1}{3-\dsize\frac{1}{3-\dots}}}. \tag 4
$$

\tenpoint
Give a geometric interpretation of {\it elements\/} $b_j$ for
expansions (3).

In (3) and (4) only numbers less than one are expanded into Hirzebruch
fractions. For numbers greater than or equal to one expansions look like
\eightpoint

$$
b_0 - \dsize\frac{1}{b_1-\dsize\frac{1}{b_2-\dsize\frac{1}{b_3-\dots-
\dsize\frac{1}{b_k}}}}, \quad
b_0 - \dsize\frac{1}{b_1-\dsize\frac{1}{b_2-\dsize\frac{1}{b_3-\dots}}},
\quad \text{все }b_j \ge 2. \tag 5
$$

$$
\text
{For instance,} \quad
\dsize\frac{5}{4} =
2-\dsize\frac{1}{2-\dsize\frac{1}{2-
\dsize\frac{1}{2}}}, \quad
\dsize\frac{8}{5} =
2-\dsize\frac{1}{3-\dsize\frac{1}{2}}, \quad
\dsize\frac{\sqrt5+3}{2} =
3 - \dsize\frac{1}{3-\dsize\frac{1}{3-\dsize\frac{1}{3-\dots}}}.
\tag 6
$$
\tenpoint
\subhead{\quad Remark} \endsubhead Condition {\it all} $b_j \ge 2$
in (3) and (5), guarantees {\it uniqueness\/} of Hirzebruch
continued fraction expansion for any real number.
If it were not imposed, one could
{\it erroneously\/} bring about the following expansions:
\eightpoint
$$
\dsize\frac{5+\sqrt5}{2} = 5 -
\dsize\frac{1}{1-\dsize\frac{1}{5-\dsize\frac{1}{1-\dots}}}, \quad
\dsize\frac{5-\sqrt5}{2} =
\dsize\frac{1}{1-\dsize\frac{1}{5-\dsize\frac{1}{1-\dots}}}. \tag 7
$$

\tenpoint
Though equalities (7) are correct, they are
{\it not\/} Hirzebruch expansions since the condition
$b_j \ge 2$ is not satisfied.

A3.1. Give Hirzebruch expansions for numbers $1$,\, $(\sqrt5 \pm1)/2$,\,
$(5 \pm\sqrt5)/2$,\, $\sqrt2$.

A3.2. Prove, under condition that {\it all}
$b_j \ge 2$, uniqueness of Hirzebruch expansion for any positive real
number.

A3.3. Solve problem A1.3 for Hirzebruch fractions.

\subhead{\quad Convergents of a Continued Fraction} \endsubhead
Introduce the following (more concise) notation for infinite Lagrange and
Hirzebruch continued fractions with elements $a_j$ and $b_j$:
$$ [a_0; a_1, a_2, \dots ], \quad [[b_0; b_1, b_2, \dots]]. \tag 8 $$
Finite continued fractions are denoted as follows:
$$ [a_0; a_1, a_2, \dots, a_k], \quad [[b_0; b_1, b_2, \dots, b_k]]. \tag 9 $$
If $a_0=0$ or $b_0=0$ in (8) or (9), we write
$$
[a_1, a_2, \dots ], \quad [[b_1, b_2, \dots]]; \quad
[a_1, a_2, \dots, a_k], \quad [[b_1, b_2, \dots, b_k]].
$$
Finite fractions
$$
[a_0;],\, [a_0; a_1],\, [a_0; a_1, a_2], \dots \quad \text {и} \quad
[[b_0;]],\, [[b_0; b_1]],\, [[b_0; b_1, b_2]], \dots
\tag 10
$$
which approximate fractions (8) and (9), are called
{\it convergents}. The following fractions, for instance, are 
convergents
for Lagrange expansion $[1; 1,1, \dots]$ of $(\sqrt5+1)/2$:
$$
[1;]=1/1,\,\, [1; 1]=2/1,\,\, [1; 1, 1]=3/2,\,\, [1; 1, 1, 1]=5/3,\,\,
\dots \tag 11
$$
while convergents for Hirzebruch expansion $[[3; 3, 3, \dots]]$ of
$(\sqrt5+3)/2$ are
$$
[[3;]]=3/1,\,\, [[3; 3]]=8/3,\,\, [[3; 3, 3]]=21/8,\,\,
[[3; 3, 3, 3]]=55/21,\,\, \dots \tag 12
$$
By (12), convergents for expansion of
$(\sqrt5+1)/2 = [[2; 3, 3, \dots]]$ would be
$$
[[2;]]=2/1,\,\, [[2; 3]]=5/3,\,\, [[2; 3, 3]]=13/8,\,\,
[[2; 3, 3, 3]]=34/21,\,\, \dots \tag 13
$$

A4.1. How are convergents (11)--(13) related to Fibonacci sequence

\centerline
{$f_{0}=0,\,\, f_{1}=1, \quad f_{k+1}=f_{k}+f_{k-1}?$}

A4.2. Find and compare to each other Lagrange and Hirzebruch
convergents of~$\frac{\sqrt5-1}{2}$.

\subhead{\quad B. Nose Stretching Algorithm} \endsubhead
For a ray $y=\b x$ going from the origin there exists a connection
between continued fraction expansion of its slope $\b$ and convex hulls of
the sets of all the knots {\it below\/} and {\it above\/} the ray.

Consider broken lines $\underline L$ and  $\overline L$ that bound these
convex hulls. Famous russian mathematician Boris Delone calls
$\underline L$ and $\overline L$ {\it noses stretching along ray} $y=\b x$.

B0. Show that vertices of $\underline L$ and $\overline L$ are points
$x_k, y_k$, where $y_k/x_k$ are convergents for Lagrange expansion of
the slope $\b$.

B1. Can you give a geometric interpretation for Hirzebruch expansion
of the slope $\b$?  Consider cases $\b < 1$ and $\b > 1$.

\enddocument

