\documentclass[12pt,a4paper]{article}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{latexsym}
\usepackage{indentfirst}
\usepackage{graphicx}
% \tolerance 8000
\oddsidemargin=2.0mm \textwidth=170mm \topmargin=-5.4mm \textheight=240mm
\advance\headsep by 6pt
\parskip=\smallskipamount
%\makeindex
\begin{document}
\def\nm{\mathversion{normal}}
\def\bm{\boldmath}
\def\mychapter#1{\section*{\Large#1}}
\def\mysection#1{\par\vglue-12pt\penalty0\subsection*{\large#1}\vglue-6pt}
\def\medskip{\vskip\medskipamount}
\def\smallskip{\vskip\smallskipamount}
\def\prenum{\llap{\hbox to \parindent{$\blacklozenge$\hfil}}}
\long\def\myempty#1{}
\def\task#1{\par\smallbreak\textbf{\textbf{\prenum#1.\enspace}}\begingroup
\sl\def\par{\endgraf\endgroup\smallbreak}\interlinepenalty9999 \ignorespaces}
\def\ui{\fontshape{ui}\selectfont}
\let\pt\it
\def\gen<#1>{\left<#1\right>}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$\mathsurround=0pt #1$}}{}}
\def\defis{\hskip 0em\nobreak-\hskip0em }
\def\risunok{\refstepcounter{figure}Pic.~\arabic{figure}}
\def\myfrac#1/#2{{}^{#1}\!/\!_{#2}}
\setcounter{figure}{6}
%\renewcommand{\baselinestretch}{0.85}
%\renewcommand{\labelenumi}{[\theenumi]}
\count0=9
\newbox\GGG
\setbox\GGG=\hbox{\includegraphics[scale=.3]{exlogo.2}}
\makeatletter
\def\@oddhead{\ifnum\count0>9
\vbox{\hbox to \hsize{\copy\GGG\hfil\it Группы и мозаики\hfil{\Huge\bf\the\count0}}\par\kern 6pt
\hrule
}
\fi}
\vbox to 0pt{\vss\noindent\includegraphics[scale=.7]{exlogo.2}\qquad\null\par\kern -24pt}
\hfil {\bf\LARGE Groups and mosaics}
\bigskip
\mysection{Corrections}
\bm
\task{B9} A group is presented by defining relations $U_1=1$, \dots, $U_k=1$.
Assume $W\equiv 1$ (i.e., the word $W$ may be reducedto the empty word). Then
words $X_1$, \dots, $X_n$ may be chosen in such a way that the word
$$X_1U_{i_1}^{\pm1}{X_1}^{-1}X_2U_{i_2}^{\pm1}{X_2^{-1}}\dots X_nU_{i_n}^{\pm1}{X_n^{-1}},$$
(here $1\leqslant i_j\leqslant k$),
may be reduced to $W$ by using cancellations of elements
adjacent to their inverses only.
\mysection{Additional Problems}
Problems of the cycle $D$ prepare the problems of the main cycle $E$.
\task{D1} We are given an infinite periodic sequence of minimal period~$n$.
Assume this sequence has two identical subwords of length $n-1$.
\vglue -12pt\penalty0
\begin{enumerate}
\item Show that the distance between initial letters of these subwords is
a multiple of $n$.
\item Does a similar statement hold for subwords of length $n-2$?
\end{enumerate}
\task{D2} We consider finite words over a finite alphabet.
There is a finite dictionary of forbidden words.
Assume that there exists an infinite sequence which does not contain forbidden subwords.
Prove that there exists an infinite periodic sequence which does not contain forbidden subwords.
\task{D3}
A finite word is called {\it cube-free} if it never contains
three consecutive entries of the same subword.
Show that there exist arbitrarily long cube-free words over the alphabet
of two letters.
{\bf Hint:} Consider the words
{\bm $a$, $ab$, $abba$, $abbabaab$, $\dots$}
Here the next word is obtained from the previous one by using the substitution
{\bm $a\rightarrow ab$, $b\rightarrow ba$}.
\task{D4} We are given two distinct periodic sequences, whose smallest periods are
$n$ and $m$ respectively. Assume that these sequences have a common subword of length $m+n-1$. Show that they have arbitrarily long common subwords.
\task{D5} Give a precise estimate in {\rm D4}.
Consider separately the cases when $m$ and $n$ are coprime and not coprime.
\task{D6} A triangle is partitioned into convex quadrilaterals.
Show that one of the quadrilaterals must have an angle of at least
$120^\circ$.
\task{D7} Does there exist a convex polyhedron whose every face
has at least $6$ edges?
\task{D8} A convex polyhedron has at least $7n$ faces. Show that at least $n$
faces have the same number of edges.
\task{D9} The plane is partitioned into convex $k$-gons.
The diameter of each $k$-gon is at most~1.
For a given point $O$, let $S_k(R)$ be the number of $k$-gons contained in the circle
of radius $R$ centred at $O$.
Show that there exists $R_0$ such that for
all $R>R_0$ we have $S_k(R) \geqslant {\lambda}^R$. Show that we may take $\lambda=k/10$. Try to obtain a better estimate for $\lambda$.
\task{D10}
The half-plane is partitioned into convex $k$-gons.
The diameter of each $k$-gon is at most~1.
We mark $L$ adjacent $k$-gons at the boundary of the half-plane.
We define {\it the first layer\/} to be the set of $k$-gons adjacent to
the marked ones. The set of $k$-gons adjacent to those of the first layer is defined to be {\it the second layer}.
Show that the number of $k$-gons in the second layer is at least $L(k/10)^2$.
\task{The Burnside Problem} We are given a positive integer $n$.
Does there exist a finitely generated infinite group such that its every element
$x$ satisfies the relation $x^n=1$ (``finitely generated'' here means that the group is defined over a finite alphabet).
А.\,Yu.\,Olshansky has constructed such a group for odd $n>10^{10}$.
We shall follow the main ideas of his construction.
\goodbreak
The solution to the Burnside problem is carried out in two steps. The first step is an inductive construction of defining relations. At each step we add several new relations of the form $A^n=1$. We must verify that every word eventually becomes periodic
(i.e., for any word $X$ the relation $X^n=1$ is deducible from defining relations introduced at some stage). Two words are declared {\it equal} if one may be reduced to the other using finitely many defining relations introduced.
We thus obtain a group whose every element is periodic.
The second part of the argument is the proof that the group we have obtained is {\bf infinite}. To this end we must show that after every step there exists a word not equal to $1$. For this we must show that there does not exist a chart all whose cells
are periodic words with a sufficiently large period and along the perimetre we have a word without periodic subwords with a larger period (e.g., square-free or cube-free). To establish this fact one investigates different cases of the adjacency of cells.
Cells correspond to defining relations introduced at various stages of the inductive process; at each consecutive stage the word is longer. Cells may thus be of different sizes.
First we show that ``large'' cells cannot have ``large adjacency''.
Then we consider the case when a large cell is adjacent to several layers
of small cells.
Here we use exponential growth of the number of polygons in problems D9 and A4.
$$
\vcenter{\halign{\hfil#\hfil\cr\includegraphics{earth.10}\cr
\risunok\label{ris:levels}\cr}}
$$
Thus according to problem D9, by carefully choosing $k$ one may achieve the effect that already the second layer already has hugely many cells.
The choice of $k$ (i.e., the number of sides of our polygons) is controlled by the choice of $n$ (the degree of periodicity of the group). I.e., at the first stage
the length of defining relations is $n$, at the $i$-th stage it is $ni$.
Polygons will thus have sufficiently many angles, and
the exponential growth will force a huge number of cells already in the second layer.
$$
\vcenter{\centering\includegraphics{earth.11}\par
\risunok\label{ris:bigsmalbig}\par
}$$
It remains to consider the case when there is a layer of small cells between two large cells. We shall need the following definition.
Cells $A$ and $B$ are called {\it reducible} if the following holds:\vadjust{\kern-6pt}
\begin{enumerate}\parsep=0pt \parskip=0pt
\item $A$ and $B$ either have common boundary or are joined by a chain of 0-cells ;
\item $A$ and $B$ have the same labels.
\end{enumerate}
If our diagram has two reducbile cells, we may carry out the following operation.
We cut out from our diagram the disk formed by the un ion of two cells and insert several $0$-cells. This operation reduces the number of nontrivial cells.
The diagram which does not contain reducible cells is said to be
{\it reduced}.
\task{E1} {\bf Example of a narrow strip for the even exponent.}
Show that there exists a reduced diagram $D$ all whose cells have the form $X^k=1$,
and, which, additionally, has the following structure:
\vglue-12pt\nobreak
\begin{enumerate}
\item $D$ contains two cells $A$ and $B$ such that all cells are adjacent to them;
\item The perimetres of cells $A$ and $B$ may be arbitrarily larger
than perimetres of all other cells (i.e., the ratio of these perimetres may be arbitrarily large.
\end{enumerate}
\task{E2} Assume that a reduced diagram has cells of two types:
<> cells of $m$ letters and <> cells of $n$ letters.
Each cell is labelled by a periodic word of the form $A^n$.
What largest common segment may the two large cells have?
\task{E3} Assume that perimetres of all cells of a reduced diagram are equal either to $m$ or to $n$, where $n\mathbin{>\!\!>}m$ and labels of all cells are periodic. Consider the cell
$A$ with perimetre $n$. Assume that all adjacent cells have perimetre $m$. As before, the {\it first layer} is the set of cells adjacent to $A$ . The $k$-th layer ($k>1$) is the set of cells adjacent to the $k-1$-th layer. Let $A_k$ be the number of cells at the $k$-th layer. Prove that $A_k \geqslant (m/100)^k$.
\task{E4}
Assume that perimetres of all cells of a reduced diagram are equal either to $m$ or to $n$, where $n\mathbin{>\!\!>}m$ and labels of all cells are periodic with an odd period.
Assume the layer of small cells is squeezed between two large cells
(see Pic.~\ref{ris:bigsmalbig}).
Is it true that the label of this contour is periodic?
%\end{eqnarray}
\end{document}