Search

We establish a connection between percolation on the Cayley graphs of a group and the dynamical diversity of cellular automata on that group. Specifically, we demonstrate that Gilman's dichotomy between equicontinuity and sensitivity with respect to Bernoulli measures holds on a finitely generated group if and only if the group has a trivial percolation threshold. Consequently, we show that a countable group satisfies Gilman's dichotomy if and only if it is locally virtually cyclic., Comment: 23 pages, 1 cute picture

The Medvedev degree of a subshift is a dynamical invariant of computable origin that can be used to compare the complexity of subshifts that contain only uncomputable configurations. We develop theory to describe how these degrees can be transferred from one group to another through algebraic and geometric relations, such as quotients, subgroups, translation-like actions and quasi-isometries. We use the aforementioned tools to study the possible values taken by this invariant on subshifts of finite type on some finitely generated groups. We obtain a full classification for some classes, such as virtually polycyclic groups and branch groups with decidable word problem. We also show that all groups which are quasi-isometric to the hyperbolic plane admit SFTs with nonzero Medvedev degree. Furthermore, we provide a classification of the degrees of sofic subshifts for several classes of groups., Comment: 25 pages

Using tools from computable analysis we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type., Comment: 40 pages, 1 gorgeous figure. Comments are welcome!

Let $G$ be a group and $H\leqslant G$ a subgroup. The free extension of an $H$-subshift $X$ to $G$ is the $G$-subshift $\widetilde{X}$ whose configurations are those for which the restriction to every coset of $H$ is a configuration from $X$. We study the case of $G = H \times K$ for infinite and finitely generated groups $H$ and $K$: on the one hand we show that if $K$ is nonamenable and $H$ has decidable word problem, then the free extension to $G$ of any $H$-subshift which is effectively closed is a sofic $G$-subshift. On the other hand we prove that if both $H$ and $K$ are amenable, there are always $H$-subshifts which are effectively closed by patterns whose free extension to $G$ is non-sofic. We also present a few applications in the form of a new simulation theorem and a new class of groups which admit strongly aperiodic SFTs., Comment: 6 pretty pictures

We study an abstract group of reversible Turing machines. In our model, each machine is interpreted as a homeomorphism over a space which represents a tape filled with symbols and a head carrying a state. These homeomorphisms can only modify the tape at a bounded distance around the head, change the state and move the head in a bounded way. We study three natural subgroups arising in this model: the group of finite-state automata, which generalizes the topological full groups studied in topological dynamics and the theory of orbit-equivalence; the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates; and the group of elementary Turing machines, which are the machines which are obtained by composing finite-state automata and oblivious Turing machines. We show that both the group of oblivious Turing machines and that of elementary Turing machines are finitely generated, while the group of finite-state automata and the group of reversible Turing machines are not. We show that the group of elementary Turing machines has undecidable torsion problem. From this, we also obtain that the group of cellular automata (more generally, the automorphism group of any uncountable one-dimensional sofic subshift) contains a finitely-generated subgroup with undecidable torsion problem. We also show that the torsion problem is undecidable for the topological full group of a full $\mathbb{Z}^d$-shift on a non-trivial alphabet if and only if $d \geq 2$., Comment: 42 pages, 9 figures. arXiv admin note: text overlap with arXiv:1603.08715

We construct a finite-range potential on a bidimensional full shift on a finite alphabet that exhibits a zero-temperature chaotic behavior as introduced by van Enter and Ruszel. This is the phenomenon where there exists a sequence of temperatures that converges to zero for which the whole set of equilibrium measures at these given temperatures oscillates between two sets of ground states. Br\'emont's work shows that the phenomenon of non-convergence does not exist for finite-range potentials in dimension one for finite alphabets; Leplaideur obtained a different proof for the same fact. Chazottes and Hochman provided the first example of non-convergence in higher dimensions $d\geq3$; we extend their result for $d=2$ and highlight the importance of two estimates of recursive nature that are crucial for this proof: the relative complexity and the reconstruction function of an extension. We note that a different proof of this result was found by Chazottes and Shinoda, at around the same time that this article was initially submitted and that a strong generalization has been found by Gayral, Sablik and Taati., Comment: Final version. Accepted for publication in Advances in Mathematics

Two asymptotic configurations on a full $\mathbb{Z}^d$-shift are indistinguishable if for every finite pattern the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb{Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a "flip condition" are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together the two results provide a generalization to $\mathbb{Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$. Many open questions are raised by the current work and are listed in the introduction., Comment: v1: 46 pages, 13 delightful figures. v2: 48 pages (many fixes thanks to referee report). v3: 48 pages (improved proof of Lemma 5.9 and more fixes)

We provide an example of a non-finitely generated group which admits a nonempty strongly aperiodic SFT. Furthermore, we completely characterize the groups with this property in terms of their finitely generated subgroups and the roots of their conjugacy classes., Comment: Fixed some errors from the previous version

Let $\Gamma$ be a sofic group, $\Sigma$ be a sofic approximation sequence of $\Gamma$ and $X$ be a $\Gamma$-subshift with nonnegative sofic topological entropy with respect to $\Sigma$. Further assume that $X$ is a shift of finite type, or more generally, that $X$ satisfies the topological Markov property. We show that for any sufficiently regular potential $f \colon X \to \mathbb{R}$, any translation-invariant Borel probability measure on $X$ which maximizes the measure-theoretical sofic pressure of $f$ with respect to $\Sigma$, is a Gibbs state with respect to $f$. This extends a classical theorem of Lanford and Ruelle, as well as previous generalizations of Moulin Ollagnier, Pinchon, Tempelman and others, to the case where the group is sofic. As applications of our main result we present a criterion for uniqueness of an equilibrium measure, as well as sufficient conditions for having that the equilibrium states do not depend upon the chosen sofic approximation sequence. We also prove that for any group-shift over a sofic group, the Haar measure is the unique measure of maximal sofic entropy for every sofic approximation sequence, as long as the homoclinic group is dense. On the expository side, we present a short proof of Chung's variational principle for sofic topological pressure., Comment: Minor modifications from the last version

We say that a finitely generated group $\Gamma$ is (dynamically) self-simulable if every effectively closed action of $\Gamma$ on a closed subset of $\{\mathtt{0},\mathtt{1}\}^{\mathbb{N}}$ is the topological factor of a $\Gamma$-subshift of finite type. We show that self-simulable groups exist, that any direct product of non-amenable finitely generated groups is self-simulable, that under technical conditions self-simulability is inherited from subgroups, and that the subclass of self-simulable groups is stable under commensurability and quasi-isometries of finitely presented groups. Some notable examples of self-simulable groups obtained are the direct product $F_k \times F_k$ of two free groups of rank $k \geq 2$, non-amenable finitely generated branch groups, the simple groups of Burger and Mozes, Thompson's $V$, the groups $\operatorname{GL}_n(\mathbb{Z})$, $\operatorname{SL}_n(\mathbb{Z})$, $\operatorname{Aut}(F_n)$ and $\operatorname{Out}(F_n)$ for $n \geq 5$; The Braid groups $B_m$ for $m \geq 7$, and certain classes of RAAGs. We also show that Thompson's $F$ is self-simulable if and only if $F$ is non-amenable, thus giving a computability characterization of this well-known open problem. We also exhibit a few applications of self-simulability on the dynamics of these groups, notably, that every self-simulable group with decidable word problem admits a nonempty strongly aperiodic subshift of finite type., Comment: 55 pages, 4 pretty figures. Several improvements and simplifications from the previous version

We give a new characterization of biinfinite Sturmian sequences in terms of indistinguishable asymptotic pairs. Two asymptotic sequences on a full $\mathbb{Z}$-shift are indistinguishable if the sets of occurrences of every pattern in each sequence coincide up to a finitely supported permutation. This characterization can be seen as an extension to biinfinite sequences of Pirillo's theorem which characterizes Christoffel words. Furthermore, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and biinfinite characteristic Sturmian sequences. The proof is based on the well-known notion of derived sequences., Comment: v1: 22 pages, 2 figures. v2: 23 pages, 2 figures. v3: fixed few typos

The theorems of Kozlov and Sullivan characterize Gibbs measures as measures with positive continuous specifications. More precisely, Kozlov showed that every positive continuous specification on symbolic configurations of the lattice is generated by a norm-summable interaction. Sullivan showed that every shift-invariant positive continuous specification is generated by a shift-invariant interaction satisfying the weaker condition of variation-summability. These results were proven in the 1970s. An open question since that time is whether Kozlov's theorem holds in the shift-invariant setting, equivalently whether Sullivan's conclusion can be improved from variation-summability to norm-summability. We show that the answer is no: there exist shift-invariant positive continuous specifications that are not generated by any shift-invariant norm-summable interaction. On the other hand, we give a complete proof of an extension, suggested by Kozlov, of Kozlov's theorem to a characterization of positive continuous specifications on configuration spaces with arbitrary hard constraints. We also present an extended version of Sullivan's theorem. Aside from simplifying some of the arguments in the original proof, our new version of Sullivan's theorem applies in various settings not covered by the original proof. In particular, it applies when the support of the specification is the hard-core shift or the two-dimensional $q$-coloring shift for $q\geq 6$., Comment: 43 pages and 2 beautiful figures

We provide a unifying approach which links results on algebraic actions by Lind and Schmidt, Chung and Li, and a topological result by Meyerovitch that relates entropy to the set of asymptotic pairs. In order to do this we introduce a series of Markovian properties and, under the assumption that they are satisfied, we prove several results that relate topological entropy and asymptotic pairs (the homoclinic group in the algebraic case). As new applications of our method, we give a characterization of the homoclinic group of any finitely presented expansive algebraic action of (1) any elementary amenable group with an upper bound on the orders of finite subgroups or (2) any left orderable amenable group, using the language of independence entropy pairs., Comment: Minor changes. 37 pages. Adv. Math. to appear

Let $G,H$ be two countable amenable groups. We introduce the notion of group charts, which gives us a tool to embed an arbitrary $H$-subshift into a $G$-subshift. Using an entropy addition formula derived from this formalism we prove that whenever $H$ is finitely presented and admits a subshift of finite type (SFT) on which $H$ acts freely, then the set of real numbers attained as topological entropies of $H$-SFTs is contained in the set of topological entropies of $G$-SFTs modulo an arbitrarily small additive constant for any finitely generated group $G$ which admits a translation-like action of $H$. In particular, we show that the set of topological entropies of $G$-SFTs on any such group which has decidable word problem and admits a translation-like action of $\mathbb{Z}^2$ coincides with the set of non-negative upper semi-computable real numbers. We use this result to give a complete characterization of the entropies of SFTs in several classes of groups., Comment: 4 nicely drawn figures. Last update improves the results of Sec 3.2 and fixes a few typos

We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientable surface of genus at least 2., Comment: 18 spectacular figures

We formulate and prove a very general relative version of the Dobrushin-Lanford-Ruelle theorem which gives conditions on constraints of configuration spaces over a finite alphabet such that for every absolutely summable relative interaction, every translation-invariant relative Gibbs measure is a relative equilibrium measure and vice versa. Neither implication is true without some assumption on the space of configurations. We note that the usual finite type condition can be relaxed to a much more general class of constraints. By "relative" we mean that both the interaction and the set of allowed configurations are determined by a random environment. The result includes many special cases that are well known. We give several applications including (1) Gibbsian properties of measures that maximize pressure among all those that project to a given measure via a topological factor map from one symbolic system to another; (2) Gibbsian properties of equilibrium measures for group shifts defined on arbitrary countable amenable groups; (3) A Gibbsian characterization of equilibrium measures in terms of equilibrium condition on lattice slices rather than on finite sets; (4) A relative extension of a theorem of Meyerovitch, who proved a version of the Lanford--Ruelle theorem which shows that every equilibrium measure on an arbitrary subshift satisfies a Gibbsian property on interchangeable patterns., Comment: 37 pages and 3 beautiful figures

We define a hierarchy of systems with topological completely positive entropy in the context of continuous countable amenable group actions on compact metric spaces. For each countable ordinal we construct a dynamical system on the corresponding level of the aforementioned hierarchy and provide subshifts of finite type for the first three levels. We give necessary and sufficient conditions for entropy pairs by means of the asymptotic relation on systems with the pseudo-orbit tracing property, and thus create a bridge between a result by Pavlov and a result by Meyerovitch. As a corollary, we answer negatively an open question by Pavlov regarding necessary conditions for completely positive entropy., Comment: 26 pages and 11 gorgeous figures (new version fixes various typos and improves readability of figures in grayscale)

We show that every effectively closed action of a finitely generated group $G$ on a closed subset of $\{0,1\}^{\mathbb{N}}$ can be obtained as a topological factor of the $G$-subaction of a $(G \times H_1 \times H_2)$-subshift of finite type (SFT) for any choice of infinite and finitely generated groups $H_1,H_2$. As a consequence, we obtain that every group of the form $G_1 \times G_2 \times G_3$ admits a non-empty strongly aperiodic SFT subject to the condition that each $G_i$ is finitely generated and has decidable word problem. As a corollary of this last result we prove the existence of non-empty strongly aperiodic SFT in a large class of branch groups, notably including the Grigorchuk group., Comment: 27 pages, 4 very beautiful figures

We generalize a result of Hochman in two simultaneous directions: Instead of realizing an effectively closed $\mathbb{Z}^d$ action as a factor of a subaction of a $\mathbb{Z}^{d+2}$-SFT we realize an action of a finitely generated group analogously in any semidirect product of the group with $\mathbb{Z}^2$. Let $H$ be a finitely generated group and $G = \mathbb{Z}^2 \rtimes H$ a semidirect product. We show that for any effectively closed $H$-dynamical system $(Y,f)$ where $Y$ is a Cantor set, there exists a $G$-subshift of finite type $(X,\sigma)$ such that the $H$-subaction of $(X,\sigma)$ is an extension of $(Y,f)$. In the case where $f$ is an expansive action of a recursively presented group $H$, a subshift conjugated to $(Y,f)$ can be obtained as the $H$-projective subdynamics of a $G$-sofic subshift. As a corollary, we obtain that $G$ admits a non-empty strongly aperiodic subshift of finite type whenever the word problem of $H$ is decidable.

We consider Turing machines as actions over configurations in $\Sigma^{\mathbb{Z}^d}$ which only change them locally around a marked position that can move and carry a particular state. In this setting we study the monoid of Turing machines and the group of reversible Turing machines. We also study two natural subgroups, namely the group of finite-state automata, which generalizes the topological full groups studied in the theory of orbit-equivalence, and the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates. Our main results are that the group of Turing machines in one dimension is neither amenable nor residually finite, but is locally embeddable in finite groups, and that the torsion problem is decidable for finite-state automata in dimension one, but not in dimension two.

A theorem of Gao, Jackson and Seward, originally conjectured to be false by Glasner and Uspenskij, asserts that every countable group admits a $2$-coloring. A direct consequence of this result is that every countable group has a strongly aperiodic subshift on the alphabet $\{0,1\}$. In this article, we use Lov\'asz local lemma to first give a new simple proof of said theorem, and second to prove the existence of a $G$-effectively closed strongly aperiodic subshift for any finitely generated group $G$. We also study the problem of constructing subshifts which generalize a property of Sturmian sequences to finitely generated groups. More precisely, a subshift over the alphabet $\{0,1\}$ has uniform density $\alpha \in [0,1]$ if for every configuration the density of $1$'s in any increasing sequence of balls converges to $\alpha$. We show a slightly more general result which implies that these subshifts always exist in the case of groups of subexponential growth., Comment: minor typos corrected

We generalize the classical definition of effectively closed subshift to finitely generated groups. We study classical stability properties of this class and then extend this notion by allowing the usage of an oracle to the word problem of a group. This new class of subshifts forms a conjugacy class that contains all sofic subshifts. Motivated by the question of whether there exists a group where the class of sofic subshifts coincides with that of effective subshifts, we show that the inclusion is strict for several groups, including recursively presented groups with undecidable word problem, amenable groups and groups with more than two ends. We also provide an extended model of Turing machine which uses the group itself as a tape and characterizes our extended notion of effectiveness. As applications of these machines we prove that the origin constrained domino problem is undecidable for any group of the form $G \times \mathbb{Z}$ subject to a technical condition on $G$ and we present a simulation theorem which is valid in any finitely generated group.