Questions tagged [symbolic-dynamics]

Symbolic dynamics is the study of dynamical systems defined in terms of shift transformations on spaces of sequences. Examples of topics in this area include shifts of finite type, sofic shifts, Toeplitz shifts, Markov partitions and symbolic coding of dynamical systems.

Filter by
Sorted by
Tagged with
42
votes
2answers
3k views

Can one "hear" the shape of a polygon via external reflections?

This question is a rough analog of Kac's "Can One Hear the Shape of a Drum?" A closer analog is the recent "Bounce Theorem" that says, roughly, the shape of a polygon is determined by its billiard-...
29
votes
5answers
3k views

What is the effect of adding 1/2 to a continued fraction?

Is there a simple answer to the question "what happens to the continued fraction expansion of an irrational number when you add 1/2?" A closely related question is "what happens to such an expansion ...
21
votes
5answers
2k views

Are there uncountably many cube-free infinite binary words?

In Cube-free infinite binary words it was established that there are infinitely many cube-free infinite binary words (see the earlier question for definitions of terms). The construction given in ...
19
votes
2answers
541 views

Sequences with 3 letters

For a positive integer $n$ I would like to construct long sequences consisting of 0, 1 and 2's such that for any two subsequences consisting of $n$ consecutive elements the number of 0's , 1's or 2'...
18
votes
2answers
1k views

Nice sign-expansions of special surreal numbers

What is the "right" surreal generalization of the fact that a real number $r$ is rational if and only if its sign-expansion is eventually periodic? I can think of more than one natural way to ...
14
votes
2answers
616 views

Is the following series consisting of equally distributed $\pm 1$ bounded?

Apologise in advance if this problem isn't research-level (I'm quite certain it isn't). It's just I found it quite intriguing because it turned out to be much more subtle than it appeared at my first ...
13
votes
1answer
512 views

Is the set of cube-free binary sequences perfect?

This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \...
13
votes
2answers
630 views

On the boundary of the twindragon

Let $\mathcal T$ be the famous twindragon, i.e., $$ \mathcal T=\left\{\sum_{n=0}^\infty a_n\left(\frac{1+i}2\right)^n : a_n\in\{0,1\}\right\}. $$ Then, as is well known, $\mathcal T$ has a non-empty ...
12
votes
2answers
2k views

Perron-Frobenius theory for reducible matrices

Can someone suggest some sources/references dealing with the Perron-Frobenius theory for nonnegative matrices that are reducible? Specifically, if $A\ge 0$ is a $d\times d$ matrix with no assumptions ...
11
votes
2answers
631 views

Open problems in symbolic dynamics

I would like to know which are some noticeable open problems in symbolic dynamics, including substitution dynamics. I'm especially interested in connections with topological chaos of various forms. ...
11
votes
0answers
1k views

Weak$^*$ convergence of measures vs. convergence of supports

Let $X$ be a compact metric space and let $\mathcal M(X)$ denote the set of probability measures on $X$. For $\mu\in\mathcal M(X)$ we write $\text{supp} \mu$ for the support of $\mu$. It is easy to ...
9
votes
3answers
2k views

How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem : On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}. Is there a rule ...
9
votes
1answer
170 views

Can the full shift be embedded in a flow?

Write $I=[0,1]$, and let $S$ be the shift on $X=\{ (x_n)_{n\in\mathbb Z} : x_n\in I^k \}$. Is there a flow $\phi_t$ on $X$ with $\phi_1=S$? Here I require that $\phi_t$, for fixed $t$, is at least a ...
9
votes
0answers
317 views

If $(Y,T)$ is a connected minimal system with a symbolic extension of linear word complexity, is $(Y,T)$ equicontinuous?

Let $(Y,S)$ be a minimal topological dynamical system such that $Y$ is connected. A simple example of a system like this is an irrational rotation of the circle, and it is known that Sturmian ...
9
votes
0answers
99 views

Factor map between subshifts preserving topological pressure (or measure-theoretic entropy)

Let $G$ be a countable amenable group and let $X,Y$ be subshifts with finite alphabet over $G$. Suppose that $h(X) = h(Y)$ (equal topological entropy). I am interested in continuous factor maps $\pi: ...
8
votes
2answers
672 views

Decidability of periodic tilings of the plane

I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (...
8
votes
1answer
564 views

A regularity property of transition matrices for the cat map

I've noticed a rather strange phenomenon (not important for my particular research, but interesting) and wouldn't be surprised if someone more versed in symbolic dynamics (i.e., just about anyone who ...
8
votes
1answer
291 views

Über theorem on unavoidable patterns?

Let $A$ be an alphabet of $k$ symbols, and $p$ a pattern. An example of a pattern is $p=XX$, where $X$ is any finite string of symbols from $A^+$. Avoiding $p$ is avoiding any subword repeated twice ...
8
votes
1answer
241 views

Connection between entropy and the set of factors of a sequence

Let $a = (a_n)_{n=0}^\infty$ be a bounded real-valued sequence. By a factor of $a$ I mean a finite block $w \in \mathbb R^l$ that appears in $a$, that is, there exists $n \geq 0$ such that $a_n a_{n+1}...
8
votes
1answer
348 views

The graph of Rule 110 and vertices degree

Consider the elementary cellular automaton called Rule 110 (famous for being Turing complete): It induces a map $R: \mathbb{N} \to \mathbb{N}$ such that the binary representation of $R(n)$ is ...
8
votes
1answer
398 views

Breaking efficiently a binary sequence into given strings

Suppose we are given a finite collection of finite binary strings $\mathcal{S}$, of various lengths. Our task is to express any binary sequence $x\in 2^\mathbb{N}$ as juxtaposition of strings taken ...
8
votes
0answers
203 views

Shift on trivalent directed tree, operator and von Neumann algebra

Let $\mathcal{T}$ be the trivalent directed tree, with two parents and one child for each vertex (see below). Let $\mathcal{V}$ be the set of vertices of $\mathcal{T}$ and $H$ be the Hilbert space $\...
8
votes
0answers
559 views

Topological entropy and periodic sequences of a subshift

Let $\Sigma$ be a two-sided subshift on a finite alphabet $A$. Let $\Sigma_n$ denote all words $x_{-n}\dots x_n\in A^{2n+1}$ such that $(x_k)_{-\infty}^\infty \in \Sigma$ for some $x_k, |k|>n$. ...
7
votes
3answers
645 views

A weak-mixing, zero entropy measure on the 2-shift which gives equal weight to both symbols

I am currently sketching a paper in the general area of symbolic dynamics in which I would like to be able to use the following fact: Proposition (proposed): there exists a shift-invariant ...
7
votes
1answer
181 views

Is the density of 1's in the Fibonacci word uniform?

The Fibonacci word is the limit of the sequence of words starting with $0$ and satisfying rules $0 \to 01, 1 \to 0$. Equivalently, it is obtained from the recursion $S_n= S_{n-1}S_{n-2}$ under ...
7
votes
3answers
176 views

Besicowitch distance between sets of invariant measures, ergodic vs non-ergodic

When working with Dominik Kwietniak and Jakub Konieczny, the question appeared: Let $X$ and $Y$ be two subshifts on the same alphabet, $M(X)$, $M(Y)$ the sets of shift-invariant measures on $X$ and $...
7
votes
1answer
190 views

When do automorphisms of subshifts extend to automorphisms of the full shift?

Let $A$ be a finite alphabet, $X$ = $(A^\mathbb{Z}, \sigma)$ the full shift, and $Y \subset X$ a subshift. Question: Are there any general results characterizing whether automorphisms of $(Y, \sigma)$...
6
votes
5answers
2k views

How can generic closed geodesics on surfaces of negative curvature be constructed?

As far as I understand it the closing lemma implies that closed geodesics on surfaces of negative curvature are dense. So: how can they be constructed in general? A concrete answer that dovetails ...
6
votes
3answers
312 views

Ruelle-Perron-Frobenius theorem for shift of finite type

I know a version of Ruelle's theorem for expansive transformations in a compact metric space that says there is a single equilibrium state for a potential holder. In this Ruelle-Perron-Frobenius ...
6
votes
4answers
858 views

Subshifts with the same entropy

It is known that two Markov subshifts with the same entropy are "almost isomorphic" (up to a subset of measure 0) if the entropy is a logarithm of an integer (see R. L. Adler, L. W. Goodwyn, and B....
6
votes
1answer
220 views

What is the simplest SFT on $\mathbb{Z}^2$ that has no periodic points?

An SFT (shift of finite type) is a set of maps to some finite alphabet that is defined by a finite number of disallowed finite words. By simple I mean has a small alphabet and a small number of ...
6
votes
1answer
1k views

Intuition of Kolmogorov-Sinai entropy

For a measurable entropy of measurable transformation $T$ from $(X,\mathcal{B},m)$ to itself. For each finite measurable partition $\mathcal{A}=\{A_i\}_{i=1}^{m}$ of $X$, we can define $h(\mathcal{A},...
6
votes
2answers
976 views

topologically mixing subshifts without ergodic measures

Are there examples of subshifts (that is, closed shift-invariant subsets of the full shift {$1...n$}${}^{\mathbb{Z}}$) on which the shift is topologically mixing, which admit a shift-invariant ...
6
votes
1answer
577 views

Aproximating dynamical systems by intrinsically ergodic systems

Let $X$ be a compact metric space and $f:X \to X$ a continuous map. We say that $(X,f)$ is approximated from below by a sequence of compact metric spaces $(X_i)_{i \geq 1}$ and a sequence of ...
6
votes
1answer
277 views

Renewal systems: Intrinsic ergodicity and a question related to the Adler's conjecture

Consider the alphabet $\mathcal{A} = \{0,1\}$ and consider a finite set of words $W = \{\omega_1, \ldots , \omega_n\}$ over $\mathcal{A}$. Then the renewal system $\Sigma_{W}$ generated by $W$ is ...
6
votes
1answer
115 views

Sliding block code on irreducible sofic shift

I was looking at the following exercise from Lind/Marcus book An Introduction to Symbolic Dynamics and Coding that I cannot solve. Can someone give me a hint? Find an example of a pair of irreducible ...
6
votes
2answers
277 views

Uniqueness of "Limit" of Cyclic Binary Strings

Set-up: By abuse, let $\sigma$ represent both the left shift operator on infinite bi-infinite strings and the cyclic left shift operator on finite strings. (Thus, for example, $\sigma(...01\bar{0}10......
6
votes
1answer
320 views

Relative irreducibility

Let $X$ be a one-dimensional one-step irreducible shift of finite type and let $\pi$ be a one-block factor code from $X$ to a sofic $Y$. Suppose $y$ is a right transitive point of $Y$ and $\pi(u)=y$ ...
6
votes
0answers
124 views

Difficulty of homeomorphism of effective Cantor dynamics

Let $X = \{0,1\}^{\mathbb{N}}$ with the product topology. Given a Turing machine $M$ and $x \in X$, define $M(x) \in \{0,1\}^* \cup X$ as the sequence of bits output by $M$ when given an oracle for $x$...
6
votes
0answers
258 views

$C^{1+\epsilon}$ conjugacy of expanding map on circle

A continuously differentiable map $f:S^{1}\rightarrow S^{1}$ is called expanding if $|f^{'}(x)|>1$ for all $x\in S^{1}$. We can define the degree of f, def(f) to be number of preimage $f^{-1}(x)$, ...
6
votes
0answers
324 views

Had this theorem in Tresser's article been proven somewhere?

The article in question is About Some Theorems by L.P. Sil'nikov by Charles Tresser. I am interested in the theorem C from page 453 and a particular application of such theorem which is illustrated ...
5
votes
1answer
338 views

Limits of intrinsically ergodic systems

Let $(X_i)$ be a sequence of compact metric spaces and $(f_i)$ a sequence of transitive transformations $f_i:X_i \to X_i$ with $0 < h_{top}(f_i) < \infty$. The sequence of dynamical systems ...
5
votes
3answers
690 views

Periodic sequences in symbolic dynamics

I'm an REU student who has just recently been thrown into a dynamical system problem without basically any background in the subject. My project advisor has told me that I should represent regions of ...
5
votes
1answer
138 views

A unique equilibrium state which does not have Gibbs property

Let $T:\Sigma \rightarrow \Sigma$ be a topologically mixing subshift of finite type and let $f:\Sigma \rightarrow \mathbb{R}$ be a continuous functions over $(T, \Sigma)$. Assume that there is a ...
5
votes
1answer
242 views

The spectral radius of a binary matrix - polynomial growth?

(This is a follow-up to The spectral radius of a binary matrix) Let $\mathcal B_n$ denote the set of $n\times n$ matrices with entries in $\{0,1\}$. QUESTION. Is there a $\delta\in\bigl(0,\frac12\...
5
votes
1answer
385 views

When is the time one map of a suspension flow ergodic?

I'm sure the answer to the following question is well known but I couldn't find the answer I needed. Let $(\Sigma,\sigma)$ denote the full shift on $k$ symbols and let $\mu$ be an invariant measure ...
5
votes
2answers
183 views

Ferenczi: minimal, uniquely ergodic, sublinear complexity systems are not strongly mixing

The following result is on page 26 of this paper by Ferenczi [PDF]. Corollary 3. A minimal and uniquely ergodic system of sub-affine complexity cannot be strongly mixing (i.e., $\mu(T^nA \cap B) \...
5
votes
1answer
287 views

continuity entropy with respect gibbs measures

Let $X=\{0,1\}^{\mathbb{N}}$. For simplicity I consider Bernoulli measures on $X$ only. Let $f:X\to \mathbb{R}$ be Holder continuous. The measure $\mu$ is a Gibbs measure with potential $f$ if there ...
5
votes
0answers
180 views

Completeness of the space of measures under $d$-bar metric

Does anybody know the reference to a proof of the following fact (which is not hard to prove, but seems to be well-known, see here): The space of shift-invariant measures under Ornstein's d-bar metric ...
5
votes
0answers
133 views

Growth in families of trees

I'm hoping that the question below is simple thermodynamic formalism, but I can't quite make it work. Any help would be very welcome. Let $\Sigma:=\{0,1\}^{\mathbb N}$ and let $\Sigma^*$ be the set ...