Search

In this paper, we obtain a combinatorial expression for the Perron root and eigenvectors of a non-negative integer matrix using techniques from symbolic dynamics. We associate such a matrix with a multigraph and consider the edge shift corresponding to it. This gives rise to a collection of forbidden words F which correspond to the non-existence of an edge between two vertices, and a collection of repeated words R with multiplicities which correspond to multiple edges between two vertices. In general, for given collections F of forbidden words and R of repeated words with pre-assigned multiplicities, we construct a generalized language as a multiset. A combinatorial expression that enumerates the number of words of fixed length in this generalized language gives the Perron root and eigenvectors of the adjacency matrix. We also obtain conditions under which such a generalized language is a language of an edge shift. [ABSTRACT FROM AUTHOR]

We look at constructions of aperiodic subshifts of finite type (SFTs) on fundamental groups of graph of groups. In particular, we prove that all generalized Baumslag-Solitar groups (GBS) admit a strongly aperiodic SFT. Our proof is based on a structural theorem by Whyte and on two constructions of strongly aperiodic SFTs on $\mathbb {F}_n\times \mathbb {Z}$ and $BS(m,n)$ of our own. Our two constructions rely on a path-folding technique that lifts an SFT on $\mathbb {Z}^2$ inside an SFT on $\mathbb {F}_n\times \mathbb {Z}$ or an SFT on the hyperbolic plane inside an SFT on $BS(m,n)$. In the case of $\mathbb {F}_n\times \mathbb {Z}$ , the path folding technique also preserves minimality, so that we get minimal strongly aperiodic SFTs on unimodular GBS groups. [ABSTRACT FROM AUTHOR]

The purpose of this article is to study the algorithmic complexity of the Besicovitch stability of noisy subshifts of finite type, a notion studied in a previous article [1]. First, we exhibit an unstable aperiodic tiling,and then see how it can serve as a building block to implement several reductions from classical undecidable problems on Turing machines. It will follow that the question of stability of subshifts of finite type is undecidable, and the strongest lower bound we obtain in the arithmetical hierarchy is Π 2 -hardness. Lastly, we prove that this decision problem,which requires to quantify over an uncountable set of probability measures,has a Π 4 upper bound. [ABSTRACT FROM AUTHOR]

We provide an example of a non-finitely generated group which admits a nonempty strongly aperiodic subshift of finite type. Furthermore, we completely characterize the groups with this property in terms of their finitely generated subgroups and the roots of their conjugacy classes. [ABSTRACT FROM AUTHOR]

The non-emptiness, called the Domino Problem, and the characterization of the possible entropies of $ \mathbb{Z}^2 $-subshifts of finite type are standard problems of symbolic dynamics. In this article we study these questions with horizontal constraints fixed beforehand as a parameter. We determine for which horizontal constraints the Domino Problem is undecidable and when all right-recursively enumerable numbers can be obtained as entropy, with two approaches: either the additional local rules added to the horizontal constraints can be of any shape, or they can only be vertical rules. [ABSTRACT FROM AUTHOR]

A new geometric criterion is derived for the existence of chaos in continuous-time autonomous systems in three-dimensional Euclidean spaces, where a type of Smale horseshoe in a subshift of finite type exists, but the intersection of stable and unstable manifolds of two points on a hyperbolic periodic orbit does not imply the existence of a Smale horseshoe of the same type on any cross section of these two points. This criterion is based on the existence of a hyperbolic periodic orbit, differing from the classical equilibrium-based Shilnikov criterion and the condition of transversal homoclinic or heteroclinic orbit of a Poincaré map. [ABSTRACT FROM AUTHOR]

We define a class of subshifts defined by a family of allowed patterns of the same shape where, for any contents of the shape minus a corner, the number of ways to fill in the corner is the same. For such a subshift, a locally legal pattern of convex shape is globally legal, and there is a measure that samples uniformly on convex sets. We show by example that these subshifts need not admit a group structure by shift-commuting continuous operations. Our approach to convexity is axiomatic, and only requires an abstract convex geometry that is "midpointed with respect to the shape". We construct such convex geometries on several groups, in particular strongly polycyclic groups and free groups. We also show some other methods for sampling finite patterns, and show a link to conjectures of Gottshalk and Kaplansky. [ABSTRACT FROM AUTHOR]

We study the periodicity of subshifts of finite type (SFT) on Baumslag-Solitar groups. We show that for residually finite Baumslag-Solitar groups there exist both strongly and weakly-but-not-strongly aperiodic SFTs. In particular, this shows that unlike Z 2 , but like Z 3 , strong and weak aperiodic SFTs are different classes of SFTs in residually finite BS groups. More precisely, we prove that a weakly aperiodic SFT on B S (m , n) due to Aubrun and Kari is, in fact, strongly aperiodic on B S (1 , n) ; and weakly but not strongly aperiodic on any other B S (m , n). In addition, we exhibit an SFT which is weakly but not strongly aperiodic on B S (1 , n) ; and we show that there exists a strongly aperiodic SFT on B S (n , n). [ABSTRACT FROM AUTHOR]

In this paper, we describe the relationship between the Perron root and eigenvectors of an irreducible subshift of finite type with the correlation between the forbidden words in the subshift. In particular, we derive an expression for the Perron eigenvectors of the associated adjacency matrix. As an application, we obtain the Perron eigenvectors for irreducible (0 , 1) matrices which are adjacency matrices for directed graphs. Moreover, we derive an alternate definition of the Parry measure in ergodic theory on an irreducible subshift of finite type. [ABSTRACT FROM AUTHOR]

Let G G be a countable monoid and let A A be an Artinian group (resp. an Artinian module). Let Σ ⊂ A G Σ ⊂ A G be a closed subshift which is also a subgroup (resp. a submodule) of A G A G. Suppose that Γ Γ is a finitely generated monoid consisting of pairwise commuting cellular automata Σ → Σ Σ → Σ that are also homomorphisms of groups (resp. homomorphisms of modules) with monoid binary operation given by composition of maps. We show that the natural action of Γ Γ on Σ Σ satisfies a natural intrinsic shadowing property. Generalizations are also established for families of endomorphisms of admissible group subshifts. [ABSTRACT FROM AUTHOR]

We develop a Galois theory for difference ring extensions, inspired by Magid's separable Galois theory for ring extensions and by Janelidze's categorical Galois theory. Our difference Galois theorem states that the category of difference ring extensions split by a chosen Galois difference ring extension is classified by actions of the associated difference profinite Galois groupoid. In particular, difference locally étale extensions of a difference ring are classified by its difference profinite fundamental groupoid. The emergence of difference profinite spaces, viewed as discrete dynamical systems in the realm of topological dynamics, leads us to investigate the interaction of difference algebra and symbolic dynamics. As an application of this interaction, we prove the near-rationality of a certain difference zeta function counting solutions of systems of difference algebraic equations over algebraic closures of finite fields with Frobenius. [ABSTRACT FROM AUTHOR]