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.
189 questions
42
votes
2
answers
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-...
- 151k
29
votes
5
answers
4k
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 ...
- 3,547
21
votes
6
answers
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 ...
- 39.9k
19
votes
2
answers
581
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'...
- 2,286
18
votes
2
answers
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 ...
- 19.7k
15
votes
2
answers
648
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 ...
- 253
15
votes
0
answers
3k
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 ...
- 1,658
14
votes
2
answers
955
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. ...
14
votes
2
answers
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 ...
- 421
13
votes
2
answers
776
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 ...
- 2,135
12
votes
1
answer
544
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 \...
- 3,992
11
votes
1
answer
521
views
Cohomology for extension problems in symbolic/topological dynamics?
Context: I know essentially nothing about cohomology of any kind, but I have a problem involving classifying obstructions to extensions of certain maps or covers, and I have heard that cohomology is ...
- 695
11
votes
0
answers
212
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: ...
- 695
10
votes
3
answers
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 ...
10
votes
2
answers
1k
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 (...
- 2,519
10
votes
0
answers
475
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 ...
- 151
9
votes
1
answer
210
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 ...
- 24.2k
9
votes
0
answers
602
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$.
...
- 2,135
8
votes
1
answer
2k
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},...
- 1,706
8
votes
1
answer
605
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 ...
- 15.4k
8
votes
1
answer
631
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 ...
8
votes
1
answer
319
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 ...
- 151k
8
votes
1
answer
280
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}...
- 1,914
8
votes
1
answer
436
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
1
answer
414
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 ...
- 60.6k
8
votes
0
answers
269
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 $\...
7
votes
3
answers
792
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 ...
- 6,206
7
votes
1
answer
273
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 ...
- 1,322
7
votes
1
answer
245
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 ...
- 785
7
votes
1
answer
231
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)$...
7
votes
3
answers
217
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 $...
- 330
7
votes
1
answer
292
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
5
answers
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 with ...
- 15.4k
6
votes
3
answers
533
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 ...
- 677
6
votes
3
answers
319
views
Approximating Subshifts From Below
I'm looking to understand how to approximate certain countable alphabet subshifts by Markov shifts, and realised that I don't know how to do it even in the finite alphabet case. My guess is that the ...
- 717
6
votes
2
answers
383
views
Topological dynamical systems with only zero-entropy factors
Suppose the dynamical system $(X,T)$ has only proper factors (i.e. not $(X,T)$ itself) of zero topological entropy. Does the system $(X,T)$ also have zero entropy?
- 675
6
votes
4
answers
943
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....
user6976
6
votes
2
answers
1k
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 ...
- 18.7k
6
votes
1
answer
148
views
Subshifts with special property
I am looking how to prove the following fact:
If $ X \subseteq A^\mathbb{Z}$ is an infinite minimal subshift, then for any $N\ge 1$, $X$ is conjugate to a minimal subshift $Y\subseteq B^\mathbb{Z}$ ...
- 1,378
6
votes
1
answer
266
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 ...
- 1,043
6
votes
1
answer
383
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 ...
6
votes
1
answer
222
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 ...
- 61
6
votes
2
answers
148
views
Decidability of (restricted) periodicity of Wang tilings
Consider a Wang tiling (given a subset of $C^4$ for a finite set $C$ of colours, e.g.). It's well-known to be undecidable whether there exists a tiling, and also whether there exists a periodic tiling....
- 2,519
6
votes
2
answers
319
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......
- 115
6
votes
1
answer
327
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
2
answers
238
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) \...
- 206
6
votes
1
answer
168
views
Number of periodic points of subshift of finite type
Let $(X, \sigma)\subset (\{0, 1, 2, 3\}^\mathbb{N},\sigma)$ be a subshift of finite type. Let $P_n$ be the set of $n$-periodic points. If $|P_n|=2^n$ for all $n\ge 1$, then it is true that $(X, \sigma)...
- 675
6
votes
1
answer
361
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 ...
- 199
6
votes
0
answers
94
views
Automorphism groups of subshifts and factor maps
Let $\pi : X \to Y$ be a factor map between subshifts over finite alphabets.
Let $\operatorname{Aut}(X)$ and $\operatorname{Aut}(Y)$ stand for automorphism groups of these shifts.
We say that $\varphi ...
- 1,658
6
votes
0
answers
348
views
Examples of expansive homeomorphisms with the specification property that are neither symbolic nor factors of mixing SFT nor product of thereof
I am looking for nontrivial examples of expansive homeomorphisms with the specification property on compact metric spaces. Here, by a ``trivial'' example I understand a subshift with the specification ...
- 1,658