\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}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