
\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}
\define\W{\overline W}
\redefine\l{\lambda}

\document
\centerline
{A. Belov-Kanel, M. Gerver}
\head
LINES ON GRID PAPER AND SUPERWORDS
\endhead

\head
Main Problems
\endhead

\subhead
{\quad Completion of class $S$. Class $S_0$: Sturm sequences}
\endsubhead
When we were defining class~$S$, we were drawing lines on grid paper 
not passing through knots.  Let us now draw a line 
$L$ with {\it irrational } slope $k_L$ {\it 
through a knot }.  As usually, we write letters $v$ and $h$ on each 
intersection of $L$ with verticals and horizontals and put a question 
mark '?' on the knot.  Substituting $vh$ for '?' gives superword 
$W=W_L$; substituting $hv$ for '?' gives superword  
$\W=\W_L$.

3.1.1. Prove that the resulting superwords are carefully mixed:
$W, \W \in S_1$.

3.1.2. Prove that $W, \W \not\in S$.

Add to $S$ all resulting superwords $W_L$, $\W_L$ (for all
irrational slopes~$k_L$) and denote by $S_0$ so completed class
of superwords. Superwords $W \in S_0$
are called {\it Sturm sequences } or {\it Sturm superwords }
after French mathematician Jacques Sturm (1803--1855).

3.1.3. Find all carefully mixed superwords not in $S_0$.

{\it Hint:\/} make use of the following construction. Draw a line 
$L$ with {\it rational } slope $k_L$ {\it 
through a knot}.  Write $v$'s and $h$'s on all intersections of $L$ 
with verticals and horizontals and question marks on all knots. 
Substitute $vh$'s for some question marks and $hv$'s for the others.  
Find out which substitutions result in 
(a) superwords $W \in S$, (b) superwords $W \in 
S_1$, (c) superwords $W \not\in S_1$.

\subhead
{\quad Exceptional superwords. Superword magnification}
\endsubhead
Consider three superwords:
$W_0=\{\dots v v v \dots\}$, $W_1=\{\dots v v v h v v v \dots\}$,
$W_2=\{\dots v v v h h h \dots\}$.

3.2.1. Check that

$W_0 \in S_0\subset S_1, W_0 \not\in S_2$; \,\,\,
$W_1 \in S_1, W_1 \in S_2, W_1 \not\in S_0$; \,\,\,
$W_2 \in S_2, W_2 \not\in S_0, W_2 \not\in S_1$ \,\,\,

\noindent
(that is, $W_0$ is a carefully mixed Sturm sequence but is not a 
superword with slowly growing subword sets; $W_1$ is a 
carefully mixed superword with slowly growing subword sets but 
is not a Sturm sequence; $W_2$ is a superword with slowly 
growing subword sets but is neither carefully mixed nor a Sturm 
sequence).

3.2.2. Is it true that there exists the only superword in $S_2$ 
(namely, superword $W_2$) that contains subword $v v h h$?

Superwords $W$ which (like $W_0$, $W_1$ and $W_2$) have one of 
the following three properties:

$W \in S_0\subset S_1, W \not\in S_2$, \quad
$W \in S_1, W \in S_2, W \not\in S_0$, \quad
$W \in S_2, W \not\in S_0, W \not\in S_1$,

\noindent
are called {\it exceptional}.
Consider two operations with superwords:
{\it regular $n$-substitution}: $hv^n\to v, hv^{n+1}\to h$
(each $v$ is replaced by $hv^n$,
each $h$ -- by $hv^{n+1}$, where $n$ is any nonnegative integer) 
and {\it inversion}: $h\ar v$. 

Successive application of (finitely many of) these operations to a word 
or a superword is called {\it magnification\/}; 
for different $n$-substitutions $n$ need not be the same.

3.3. Prove that any exceptional superword is magnification of one of 
our $W_j$, $j = 0, 1, 2$.  

\vfill

\subhead {\quad 
Farey series \footnote {These  series were invented in 1816 
by British geologist John Farey (1766-1826).}, basic parallelograms 
and exceptional $W \in S_2$} \endsubhead

Farey series $F_j$ are defined as the sets of all fractions on $[0,1]$ 
in lowest terms whose denominators do not exceed $j$, arranged in 
order of magnitude:
\smallpagebreak

\centerline
{$F_1=\{0, 1\}$, \quad
$F_2=\{0, \dsize\frac 12, 1\}$, \quad
$F_3=\{0, \dsize\frac 13, \dsize\frac 12, \dsize\frac 23, 1\}$,}

\medpagebreak
\centerline
{$F_4=\{0, \dsize\frac 14, \dsize\frac 13, \dsize\frac 12, 
\dsize\frac 23, \dsize\frac 34, 1\}$, \quad
$F_5=\{0, \dsize\frac 15, \dsize\frac 14, \dsize\frac 13, 
\dsize\frac 25, \dsize\frac 12, \dsize\frac 35, 
\dsize\frac 23, \dsize\frac 34, \dsize\frac 45, 1\}$, \, \dots}
\smallpagebreak

Expressing $0$ and $1$ as $\dsize\frac 01$ and 
$\dsize\frac 11$ guarantees that for any two adjacent fractions 
$\dsize\frac{x_1}{y_1} < \dsize\frac{x_2}{y_2}$ of any $F_j$ 
the condition $x_2y_1-x_1y_2=1$ holds. It means (check it!) that 
the parallelogram~$\p$ spanned by vectors $\{x_1, y_1\}$ 
$\{x_2, y_2\}$ has unit area. 

Such parallelograms $\p$ with vertices at knots are called  
{\it basic}. 

3.4.1. Relate to each pair of rational numbers $k_1, k_2$ such 
that \smallpagebreak

\centerline
{$0\le k_1=\dsize\frac{x_1}{y_1}<k_2=\dsize\frac{x_2}{y_2}\le 1$,} 
\smallpagebreak

a) parallelogram $\p$, spanned by vectors $\{x_1, y_1\}$ 
and $\{x_2, y_2\}$, 

b) two periodic superwords $W_1=W_{L_1}, W_2=W_{L_2}\in S$ 
for lines with slopes $k_1, k_2$ and hence a superword
$W$ composed (as in 2.7) from two periodic parts $W_1$, $W_2$. 

Prove that $W \in S_2$ if and only if parallelogram $\p$ is basic
(or, equivalently, when $k_1, k_2$ are adjacent fractions in  
a certain $F_j$). 

3.4.2. Explain why all $W \in S_2$, related to basic 
parallelograms in 3.4.1, are exceptional: they are not in $S_1$. 

3.4.3. Prove that each exceptional superword $W \in S_2$ is related to 
a basic parallelogram~$\p$: two rays parallel to the sides of $\p$, 
cross strip polygon $M_w$ for each subword $w\in W$ 
(perhaps after applying to $w$ inversion $v \ar h$). 

\subhead
\quad Canonical representation of periodic superwords $W_L$ 
\endsubhead
We know that, for lines with rational slopes 
$k_L$,  superwords $W_L\in S_0$ are periodic. 
If $k_L=m/n$, where $m/n$ is in lowest terms, then period $P$ 
of superword $W_L$ has $m$ letters $h$ and $n$ letters $v$, but 
arranging these letters in right order is not an easy task for large 
$m$ and $n$. Farey series help find the following {\it 
canonical\/} representation of period $P$ as a word~$f_{m,n}$ of  
$m$~letters~$h$ and $n$~letters~$v$ (we calls such words $(m,n)-${\it 
fareys}): by definition $(0,1)-$farey~$f_{0,1}$ is one-letter word 
$v$, $(1,1)-$farey~$f_{1,1}$ is two-letter word $vh$.  
If $(m,n)-$fareys are already defined for all $m \le n < q$, 
then $(m,q)-$fareys are derived from $(i,j)-$fareys, $j < q$, by
means of the following operation called 
{\it concatenation}:  each fraction $\frac mq$ in series $F_q$
has two adjacent fractions $\frac{x_1}{y_1}$ and $\frac{x_2}{y_2}$ for 
which $\frac mq$ is {\it the mediant}:  $x_1+x_2=m$, $y_1+y_2=q$.  
Denominators of these two fractions are smaller than $q$, so 
$f_{x_1,y_1}$ and $f_{x_2,y_2}$ are already defined. Then $f_{m,j}$ 
is derived by writing  $f_{x_2,y_2}$ next to $f_{x_1,y_1}$. 
Here are some examples:  $f_{1,2}=f_{0,1}\cup f_{1,1}=vvh$, \,\, 
$f_{1,3}=f_{0,1}\cup f_{1,2}=vvvh$, $f_{2,3}=f_{1,2}\cup 
f_{1,1}=vvhvh$, \,\, $f_{1,4}=f_{0,1}\cup f_{0,3}=vvvvh$, 
$f_{3,4}=f_{2,3}\cup f_{1,1}=vvhvhvh$. 

3.5.1. Check that

$f_{1,5}=vvvvvh$, $f_{2,5}=vvvhvvh$, 
$f_{3,5}=vvhvvhvh$, $f_{4,5}=vvhvhvhvh$. 

3.5.2. Prove that $(m,n)-$fareys are well defined: 
when $k_L=m/n$ superwords $W=W_L$ indeed have period 
$P=f_{m,n}$. 

3.5.3. Let $\frac{x_1}{y_1} < \frac{x_2}{y_2}$ be two
adjacent fractions for a certain series $F_j$ and $y_1<y_2$. 
Prove that in this case $f_{x_1,y_1}$ is a subword of $f_{x_2,y_2}$ 
(likewise, if $y_1>y_2$ then $f_{x_2,y_2}$ is a subword of 
$f_{x_1,y_1}$). 

\subhead
\quad Golden ratio 
\endsubhead
{\it Golden ratio\/} is the split of a segment into two such 
that the ratio of the length of the {\it entire} segment to 
the length of the {\it bigger} part is equal to that for the 
{\it bigger} to the {\it smaller} part: 
($\frac{\sqrt{5}+1}{2}:1=1:\frac{\sqrt{5}-1}{2}$). 

3.6.1. Draw ray~$\ell$ with slope~$\frac{\sqrt{5}-1}{2}$ through the 
origin. 

Write $v$'s and $h$'s on all intersections of~$\ell$ with verticals and 
horizontals; we get {\it half of a superword\/} 
$w_{\ell}=\{v\, v\, h\, v\, v\, h\, v\, h\, \dots\}$ 
(i.e., sequence $w_{\ell}$ infinite to the right). Prove that  
$w_{\ell}$ can be constructed in the following way:

In three-letter word $v\, v\, h$ substitute 

\centerline{$v\, v\, h \to v, \,\,\, v\, h \to h$.} 

\noindent
(each $v$ is replaced by $v\, v\, h$,
each $h$ --- by $v\, h$). repeat the same substitution for the 
resulting word $v\, v\, h\, v\, v\, h\, v\, h$:  
{$v\, v\, h\, v\, v\, h\, v\, h\,\, v\, v\, h\, v\, v\, h\, v\, h\,\, 
v\, v\, h\, v\, h$ \, and so on.} 

{\it Remark:} one may start even from the single letter $v$ and still 
get $w_{\ell}$ after {\it infinitely many} (compare to 3.3) 
substitutions.

3.6.2. Formulate and solve similar problem for ray~$\ell$ 
with slope~$k_{\ell}={\sqrt{2}-1}$. 

3.6.3. Expand the result onto slopes 
$k_{\ell}$ equal to periodic continued fractions $[a_1, 
\dots, a_n \dots]$, $[[b_1, \dots, b_n \dots]]$ with periods $\{a_1, 
\dots, a_n\}$, $\{b_1, \dots, b_n\}$.  

\subhead
\quad 4. Sturm sequences
\endsubhead
Split circle $C$ of unit length into two arches, $A$ and $B$,
with lengths $\a$ and $\b$, $\a+\b=1$. Choose an initial 
point~$P_0$ and construct sequence $P_0, P_1, P_2, \ldots$, where each 
point~$P_k$ is $P_{k-1}$ shifted by~$\b$ along circle $C$, 
and sequence $P_0, P_{-1}, P_{-2}, \ldots$, where each point~$P_{-k}$ 
is $P_{-(k-1)}$ shifted by $-\b$ along circle $C$.

In other words,
$P_n$ is $P_0$ shifted by~$n\b$ along $C$,
$n = \pm1, \pm2, \ldots, \pm{k}, \ldots$.

To points $P_n$ we relate sequence~$W=\{w_n\}$
of letters~$a$~and~$b$, where

\centerline
{$w_n=a$, \, if~$P_n \in A$, \, and \,
$w_n=b$, \, if~$P_n \in B$, \,\,
$n = 0, \pm1, \pm2, \ldots$.}

4.1. Prove that the class of such sequences~$W=\{w_n\}$ coincides 
(after replacing $a$ and $b$ by $v$ and $h$) with class 
$S_0$ of Sturm sequences $W=W_L$. 

{\it Hint 1: } You should view each of the arches $A$ and $B$ as {\it 
semiopen\/} --- containing one of the endpoints but not the other.

{\it Hint 2: } The following three (simpler) problems will help you 
with 4.1:

4.1.1. Which of subwords $aa, ab, ba, bb$ of length 2 can be contained
in $W$?

4.1.2. Can $W$ contain three-letter subword $abb$?

4.1.3. Let $0 \le s,t \le 1$, $w_n=[sn+t]-[s(n-1)+t]$, where square 
brackets represent the integer part of a number.

Check that $w_n$ can have only two values~$0$~and~$1$.

Is it true that for all $s$ and $t$ on~$[0,1]$
sequence~$W=\{w_n\}$ is the one corresponding to points
$P_n$ (after substituting $a$ for $0$ \,and\, $b$  for $1$),
and a subword from $S_0$
(with $0$ replaced by $v$ \,and\, $1$ by $h$)?


4.2. Describe Sturm sequences~$W\in S_0$ not in $S$ in terms of $\a$, 
$\b$ and $P_0$ . 

4.3. Prove that if $\b$ is irrational then the set of points
$P_n$ is {\it dense everywhere\/} and {\it evenly distributed\/}
on circle $C$. This means the following.

On circle $C$ take an arch $d$ of length $\delta$,
and find how many of any $N$ consecutive points from~$\{P_n\}$ 
hit arch $d$. Then the number of hits, divided by $N$, tends 
to $\delta$ as $N\to\infty$.

\subhead {\quad Superword equivalence} \endsubhead
Two superwords are called {\it equivalent}, if they have exactly 
the same subword sets.

4.4. Prove that for fixed $\a$ and $\b$, $\a+\b=1$ and varying
$P_0$ Sturm sequences~$W=\{w_n\}$ are equivalent.

4.5. Prove that for irrational $\a$ and $\b$, $\a+\b=1$, 
Sturm sequences~$W=\{w_n\}$ are  
{\it quasiperiodic}: 
%they contain arbitrary long congruent subwords.
if a subword occurs in such a sequence, it occurs there infinitely 
many times.

4.6. Prove that for fixed $\a$ and $\b$, 
$\a+\b=1$ and $P_0^* = P_0+k\b$ \linebreak 
(for integer $k$) Sturm sequences~$W$,~$W^*$ are shifts of each other.

4.7. Proved that for fixed irrational $\a$ and $\b$, 
$\a+\b=1$ and $P_0^* \ne P_0+k\b$ (for integer~$k$) 
Sturm sequences~$W$,~$W^*$ are neither congruent nor shifts of each 
other.

\subhead {\quad 5. Selfdeveloping superwords} \endsubhead

5.1. Consider two sequences of words $U_k$ and $V_k$ of letters $a$ and 
$b$:  
\smallpagebreak

$U_0=a, \, V_0=b$ \,\, � \,\,
$U_{k}=U_{k-1}^{2}\,V_{k-1}$, \,
$V_{k}=U_{k-1}\,V_{k-1}$ for all $k \ge 1$;

\noindent
the last formula means that to get $U_k$ one writes
$U_{k-1}$ twice and then $V_{k-1}$; to get $V_k$ 
one writes $U_{k-1}$ and then $V_{k-1}$.  Hence $U_{k}$ begins with
$U_{k-1}$ and $V_{k}$ ends with $V_{k-1}$ for all $k \ge 1$:

\qquad\qquad
$U_0 = a$,\,\, $U_1 = aab$,\,\, $U_2 = aab\,\,aab\,\,ab$, \dots \,
$V_0 = b$,\,\, $V_1 = ab$,\,\, $V_2 = aab\,\,ab$, \dots

\noindent
and therefore words $W_k = V_k\,U_k$ form an embedded sequence 
and {\it selfdevelop\/} to the superword $W$ which is the union of them 
all:

\noindent
$W_0 = b\,a \subset W_1 = ab\,aab \subset
W_2 = aab\,ab\,\,aab\,aab\,ab \subset \dots
\subset W = \dots aab\,ab\,\,aab\,aab\,ab \dots$.

Check that the resulting superword $W$ can be split into subwords 
$aab$ and $ab$:

\centerline
{$W = \dots aab\, aab\, ab\, aab\, ab \,\,
aab\, aab\, ab\, aab\, aab\, ab\, aab\, ab \dots$.}

5.1.1. Prove that superword $W$ is not periodic.

5.1.2. In $W$ replace each $aab$ by $v$ and then each
$ab$ by $h$: \,\,
{$W = \dots v\, v\, h\, v\, h \,\,
v\, v\, h\, v\, v\, h\, v\, h \dots $}

Is it true that $W$ is preserved if we substitute $vvh \to v$,  
and then $vh \to h$?

5.1.3. is it true that superword $W$ is equivalent to a 
superword from class~$S$, 
i.e., there exists a line $L$ such that $W \sim W_L$?
If so, what is its slope $k_L$?

5.2. Pick any sequence $\{n_k\}$ of positive integers and relate to
is two sequences of words $U_k$ and $V_k$ in which
\smallpagebreak

$U_0=a, \, V_0=b$,
$\, U_1=U_0^{n_1+1}V_0, \, V_1=U_0^{n_1}V_0$,
$\, U_2=U_1^{n_2+1}V_1, \, V_2=U_1^{n_2}V_1$, \, and, in general,
\smallpagebreak

\centerline
{$U_{k}=U_{k-1}^{n_k+1}\,V_{k-1}$, \,
$V_{k}=U_{k-1}^{n_k}\,V_{k-1}$ for all $k \ge 1$.}

\noindent
Prove that (as in 5.1) words $W_k=V_kU_k$, developing
"from the middle" to the left and to the right, form a 
both ways infinite selfdeveloping superword~$W$.

5.2.1. In 5.1, which is a special case of 5.2,
all $n_k \equiv 1$.

Consider another special case: 
check that for $n_k \equiv 2$
resulting superword $W$ can be split into words $a^3b=aaab$ and 
$a^2b=aab$:

\centerline
{$W = \dots aaab\, aaab\, aab \,\, aaab\, aaab\, aaab\, aab\,
\dots$.}

Prove that this  $W$ is not periodic.

In $W$ replace each $aaab$ by $v$ and then each
$aab$ by $h$:

\centerline
{$W = \dots v\, v\, h\, \,\, v\, v\, v\, h\, \dots $}

is it true that $W$ is preserved if we substitute
$vvvh \to v$ and then $vvh \to h$?
% ������� �� ��ਮ���᪨� ��᫥����⥫쭮�� $\{n_k\}$

Is it true that the resulting  $W$ is equivalent to a 
superword from class~$S$, i.e., there exists a line $L$, such that 
$W\sim W_L$? 

If so, what is the slope $k_L$ of $L$ and what is its equation?


5.2.2. Is it true that for any sequence $\{n_k\}$ 

a) $W$ is carefully mixed, 

b) $T_W(n) = n+1$ for all $n$,

c) $W$ is a Sturm sequence? 

\enddocument



