# Interval exchange transformations, Rauzy graphs, Universal sequences and factor-Dynamics.

Speaker
Alexei Kanel-Belov , Bar-Ilan University
Date
31/10/2021 - 01:30 - 00:00Add to Calendar 2021-10-31 00:00:00 2021-10-31 01:30:00 Interval exchange transformations, Rauzy graphs, Universal sequences and factor-Dynamics. Let $M$ be a compact metric space, $U\subset M$ be its open subspace, $f:M\to M$ be a homeomorphism of the compact into itself, and $x\in M$ be an initial point. It determines sequence of points $x,f(x),\ldots,f^{(n)}(x),\ldots$ With the sequence of iterations, one can associate an infinite binary word $w_n=a$ for $f^{(n)}(x_0)\in U$, $w_n=b$ for $f^{(n)}(x_0)\notin U$ which is called the {\it evolution} of point $x_0$. If $f$ is invertible then $n\in \mathbb{Z}$, otherwise $n\in \mathbb{N}$. Symbolic dynamics investigates the interrelation between the properties of the dynamical system $(M,f)$ and the combinatorial properties of the word $W_n$. For words over alphabets which comprise more symbols, several characteristic sets should be considered: $U_1,\ldots,U_n$.   The famous Sturmian sequences and some of their generalizations present situation of combinatorial paradise''.  It provides patterns for further investigation. Let us remind the classical result. {\bf Equivalence theorem} {\it Let $W$ be an infinite recurrent word over the binary alphabet $A=\{a,b\}$. The following conditions are equivalent: 1) The word $W$ is a {\em Sturmian word}, i.e., for any $n\geq 1$, the number of different subwords of length $n$ that occur in $W$ is equal to $T_n(W)=n+1$. 2) The word is not periodic and is {\em balanced}, i.e., any two subwords $u,v\subset W$ of the same length satisfy the inequality $||v|_a-|u|_a|\leq 1$, where $|w|_a$ denotes the number of occurrences of symbol $a$ in the word $w$. 3) The word $W=(w_n)$ is a {\em mechanical} word with irrational $\alpha$, i.e. there exist an irrational $\alpha$, $x_0 \in [0,1]$, and interval $U\subset \mathbb{S}^1$, $|U|=\alpha$, such that $w_n=a$ for $T_{\alpha}^n(x_0)\in U$, $w_n=b$ for $T_{\alpha}^n(x_0)\notin U$ 4) Word  $W$ can be obtained as a limit of the sequence of finite words $\{w_i\}_{i=1}^\infty$, such that $w_{i+1}$ can be obtained from $w_{i}$ via substitution of the following type $a^{k_i}b\to b, a^{k_i+1}b\to a$ or $b^{k_i}a\to a, b^{k_i+1}a\to b$.  Iff sequence of these substitutions is periodic, then $\alpha$ is a quadratic irrational.} There are several different ways of generalizing Sturmian words. One of the most important is interval exchange transformation.  It can be done in terms of {\em Rauzy graphs}.  The {\it Rauzy graph} of order $k$ (the {\it $k$-graph}) of the word $W$ is the directed graph whose vertices biuniquely correspond to the factors of length $k$ of the word $W$ and the vertex $A$ is connected to vertex $B$ by directed arc iff $W$ has a factor of length $k+1$ such that its first $k$ letters make the subword that corresponds to $A$ and the last $k$ symbols make the subword that corresponds to $B$. By the {\it follower} of the directed $k$-graph $G$ we call the directed graph $\Fol(G)$ constructed as follows: the vertices of graph $\Fol(G)$ are in one-to-one correspondence with the arcs of graph $G$ and there exists an arc from vertex $A$ to vertex $B$ if and only if the head of the arc $A$ in the graph $G$ is at the notch end of $B$. The $(k+1)$-graph is a subgraph of the follower of the $k$-graph; it results from the latter by removing some arcs. Vertices which are tails of (or heads of) at least two arcs correspond to {\it special factors}; vertices which are heads and tails of more than one arc correspond to {\it bispecial factors}. The sequence of the Rauzy $k$-graphs constitutes the {\it evolution} of the Rauzy graphs of the word $W$.   We discourse factor-dynamics properties,  universal sequences (for example language consisting all words which appear in $k$-interval exchange for some $k$, deformations of universal language  and the first digit sequence $2^{n^2}$.    Let $P(n)$ be a polynomial, having an irrational coefficient of the highest degree. A word $W=(w_n)$, (n\in \mathbb{N})$consists of a sequence of first binary numbers of$\{P(n)\}$i.e.$w_n=[2\{P(n)\}]$. Denote by$T(k)$the number of different subwords of$W$of length$k$. {\bf Theorem}. There exists a polynomial$Q(k)$, depending only on the power of the polynomial$P$, such that$T(k)=Q(k)$for all sufficiently great$k$. similar is true for the first digit sequence$2^{n^2}$. (Joint work with , I.Reshetnikov) https://us02web.zoom.us/j/89761638518 אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public Place https://us02web.zoom.us/j/89761638518 Abstract Let$M$be a compact metric space,$U\subset M$be its open subspace,$f:M\to M$be a homeomorphism of the compact into itself, and$x\in M$be an initial point. It determines sequence of points$x,f(x),\ldots,f^{(n)}(x),\ldots$With the sequence of iterations, one can associate an infinite binary word$w_n=a$for$f^{(n)}(x_0)\in U$,$w_n=b$for$f^{(n)}(x_0)\notin U$which is called the {\it evolution} of point$x_0$. If$f$is invertible then$n\in \mathbb{Z}$, otherwise$n\in \mathbb{N}$. Symbolic dynamics investigates the interrelation between the properties of the dynamical system$(M,f)$and the combinatorial properties of the word$W_n$. For words over alphabets which comprise more symbols, several characteristic sets should be considered:$U_1,\ldots,U_n$. The famous Sturmian sequences and some of their generalizations present situation of combinatorial paradise''. It provides patterns for further investigation. Let us remind the classical result. {\bf Equivalence theorem} {\it Let$W$be an infinite recurrent word over the binary alphabet$A=\{a,b\}$. The following conditions are equivalent: 1) The word$W$is a {\em Sturmian word}, i.e., for any$n\geq 1$, the number of different subwords of length$n$that occur in$W$is equal to$T_n(W)=n+1$. 2) The word is not periodic and is {\em balanced}, i.e., any two subwords$u,v\subset W$of the same length satisfy the inequality$||v|_a-|u|_a|\leq 1$, where$|w|_a$denotes the number of occurrences of symbol$a$in the word$w$. 3) The word$W=(w_n)$is a {\em mechanical} word with irrational$\alpha$, i.e. there exist an irrational$\alpha$,$x_0 \in [0,1]$, and interval$U\subset \mathbb{S}^1$,$|U|=\alpha$, such that$w_n=a$for$T_{\alpha}^n(x_0)\in U$,$w_n=b$for$T_{\alpha}^n(x_0)\notin U$4) Word$W$can be obtained as a limit of the sequence of finite words$\{w_i\}_{i=1}^\infty$, such that$w_{i+1}$can be obtained from$w_{i}$via substitution of the following type$a^{k_i}b\to b, a^{k_i+1}b\to a$or$b^{k_i}a\to a, b^{k_i+1}a\to
b$. Iff sequence of these substitutions is periodic, then$\alpha$is a quadratic irrational.} There are several different ways of generalizing Sturmian words. One of the most important is interval exchange transformation. It can be done in terms of {\em Rauzy graphs}. The {\it Rauzy graph} of order$k$(the {\it$k$-graph}) of the word$W$is the directed graph whose vertices biuniquely correspond to the factors of length$k$of the word$W$and the vertex$A$is connected to vertex$B$by directed arc iff$W$has a factor of length$k+1$such that its first$k$letters make the subword that corresponds to$A$and the last$k$symbols make the subword that corresponds to$B$. By the {\it follower} of the directed$k$-graph$G$we call the directed graph$\Fol(G)$constructed as follows: the vertices of graph$\Fol(G)$are in one-to-one correspondence with the arcs of graph$G$and there exists an arc from vertex$A$to vertex$B$if and only if the head of the arc$A$in the graph$G$is at the notch end of$B$. The$(k+1)$-graph is a subgraph of the follower of the$k$-graph; it results from the latter by removing some arcs. Vertices which are tails of (or heads of) at least two arcs correspond to {\it special factors}; vertices which are heads and tails of more than one arc correspond to {\it bispecial factors}. The sequence of the Rauzy$k$-graphs constitutes the {\it evolution} of the Rauzy graphs of the word$W$. We discourse factor-dynamics properties, universal sequences (for example language consisting all words which appear in$k$-interval exchange for some$k$, deformations of universal language and the first digit sequence$2^{n^2}$. Let$P(n)$be a polynomial, having an irrational coefficient of the highest degree. A word$W=(w_n)$, (n\in \mathbb{N})$ consists of a sequence of first binary numbers of $\{P(n)\}$ i.e. $w_n=[2\{P(n)\}]$. Denote by $T(k)$ the number of different subwords of $W$ of length $k$.

{\bf Theorem}. There exists a polynomial $Q(k)$, depending only on the power of the polynomial $P$, such that $T(k)=Q(k)$ for all sufficiently great $k$.

similar is true for the first digit sequence $2^{n^2}$. (Joint work with , I.Reshetnikov)

תאריך עדכון אחרון : 31/10/2021