Search

Krieger's embedding theorem provides necessary and sufficient conditions for an arbitrary subshift to embed in a given topologically mixing $\mathbb{Z}$-subshift of finite type. For some $\mathbb{Z}^d$-subshifts of finite type, Lightwood characterized the \emph{aperiodic} subsystems. In the current paper we prove a new embedding theorem for a class of subshifts of finite type over any countable abelian group. Our main theorem provides necessary and sufficient conditions for an arbitrary subshift $X$ to embed inside a given subshift of finite type $Y$ that satisfies a certain condition. For the particular case of $\mathbb{Z}$-subshifts, our new theorem coincides with Krieger's theorem. In particular, our result gives the first complete characterization of the subsystems of the multidimensional full shift $Y= A^{\mathbb{Z}^d}$. The natural condition on the target subshift $Y$, introduced explicitly for the first time in the current paper, is called the map extension property. It was introduced implicitly by Mike Boyle in the early 1980's for $\mathbb{Z}$-subshifts, and is closely related to the notion of an absolute retract, introduced by Borsuk in the 1930's. A $\mathbb{Z}$-subshift has the map extension property if and only if it is a topologically mixing subshift of finite type. Over abelian groups, a subshift has the map extension property if and only if it is a contractible SFT as shown in work of Poirier and Salo. We also establish a new theorem regarding lower entropy factors of multidimensional subshifts, that extends Boyle's lower entropy factor theorem from the one-dimensional case., Comment: 50 pages

Classical theorems from the early 20th century state that any Haar measurable homomorphism between locally compact groups is continuous. In particular, any Lebesgue-measurable homomorphism $\phi:\mathbb{R} \to \mathbb{R}$ is of the form $\phi(x)=ax$ for some $a \in \mathbb{R}$. In this short note, we prove that any Lebesgue measurable function $\phi:\mathbb{R} \to \mathbb{R}$ that vanishes under any $d+1$ ``difference operators'' is a polynomial of degree at most $d$. More generally, we prove the continuity of any Haar measurable polynomial map between locally compact groups, in the sense of Leibman. We deduce the above result as a direct consequence of a theorem about the automatic continuity of cocycles., Comment: 7 pages. Few minor corrections and a reference added

We prove an equivariant version of the classical Menger-Nobeling theorem regarding topological embeddings: Whenever a group $G$ acts on a finite-dimensional compact metric space $X$, a generic continuous equivariant function from $X$ into $([0,1]^r)^G$ is a topological embedding, provided that for every positive integer $N$ the space of points in $X$ with orbit size at most $N$ has topological dimension strictly less than $\frac{rN}{2}$. We emphasize that the result imposes no restrictions whatsoever on the acting group $G$ (beyond the existence of an action on a finite-dimensional space). Moreover, if $G$ is finitely generated then there exists a finite subset $F\subset G$ so that for a generic continuous map $h:X\to [0,1]^{r}$, the map $h^{F}:X\to ([0,1]^{r})^{F}$ given by $x\mapsto (f(gx))_{g\in F}$ is an embedding. This constitutes a generalization of the Takens delay embedding theorem into the topological category., Comment: 23 pages. Minor corrections to proof of Theorem 1.6

We introduce a novel framework for implementing error-correction in constrained systems. The main idea of our scheme, called Quantized-Constraint Concatenation (QCC), is to employ a process of embedding the codewords of an error-correcting code in a constrained system as a (noisy, irreversible) quantization process. This is in contrast to traditional methods, such as concatenation and reverse concatenation, where the encoding into the constrained system is reversible. The possible number of channel errors QCC is capable of correcting is linear in the block length $n$, improving upon the $O(\sqrt{n})$ possible with the state-of-the-art known schemes. For a given constrained system, the performance of QCC depends on a new fundamental parameter of the constrained system - its covering radius. Motivated by QCC, we study the covering radius of constrained systems in both combinatorial and probabilistic settings. We reveal an intriguing characterization of the covering radius of a constrained system using ergodic theory. We use this equivalent characterization in order to establish efficiently computable upper bounds on the covering radius., Comment: 24 pages, 5 figures

An old theorem of Newman asserts that any tiling of $\mathbb{Z}$ by a finite set is periodic. Few years ago Bhattacharya proved the periodic tiling conjecture in $\mathbb{Z}^2$. Namely, he proved that for a finite subset $F$ of $\mathbb{Z}^2$, if there exists $A \subseteq \mathbb{Z}^d$ such that $F \oplus A = \mathbb{Z}^d$ then there exists a periodic $A' \subseteq \mathbb{Z}^d$ such that $F \oplus A' = \mathbb{Z}^d$. The recent refutation of the periodic tiling conjecture in high dimensions due to Greenfeld and Tao motivates finding different generalizations of Newman's theorem and of Bhattacharya's theorem that hold in arbitrary dimension $d$. In this paper, we formulate and prove such generalizations. We do so by studying the structure of joint co-tiles in $\mathbb{Z}^d$. Our generalization of Newman's theorem states that for any $d \ge 1$, any joint co-tile for $d$ independent tiles is periodic. For a $(d-1)$-tuple of finite subsets of $\mathbb{Z}^d$ that satisfy a certain technical condition that we call property $(\star)$, we prove that any joint co-tile decomposes into disjoint $(d-1)$-periodic sets. Consequently, we show that for a $(d-1)$-tuple of finite subsets of $\mathbb{Z}^d$ that satisfy property $(\star)$, the existence of a joint co-tile implies the existence of periodic joint co-tile. Conversely, we prove that if a finite subset $F$ in $\mathbb{Z}^d$ admits a periodic co-tile $A$, then there exist $(d-1)$ additional tiles that together with $F$ are independent and admit $A$ as a joint co-tile, and $(d-2)$ additional tiles that together with $F$ satisfy the property $(\star)$. Combined, our results give a new necessary and sufficient condition for a subset of $\mathbb{Z}^d$ to tile periodically. We also discuss tilings and joint tilings in other countable abelian groups., Comment: Minor updates

We show that translational tiling problems in a quotient of $\mathbb{Z}^d$ can be effectively reduced or ``simulated'' by translational tiling problems in $\mathbb{Z}^d$. In particular, for any $d \in \mathbb{N}$, $k < d$ and $N_1,\ldots,N_k \in \mathbb{N}$ the existence of an aperiodic tile in $\mathbb{Z}^{d-k} \times (\mathbb{Z} / N_1\mathbb{Z} \times \ldots \times \mathbb{Z} / N_k \mathbb{Z})$ implies the existence of an aperiodic tile in $\mathbb{Z}^d$. Greenfeld and Tao have recently disproved the well-known periodic tiling conjecture in $\mathbb{Z}^d$ for sufficiently large $d \in \mathbb{N}$ by constructing an aperiodic tile in $\mathbb{Z}^{d-k} \times (\mathbb{Z} / N_1\mathbb{Z} \times \ldots \times \mathbb{Z} / N_k \mathbb{Z})$ for suitable $d,N_1,\ldots,N_k \in \mathbb{N}$., Comment: 10 pages, 4 figures

Weyl's classical equidistribution theorem states that real-valued polynomial sequences are uniformly distributed modulo 1, unless all non-constant coefficients are rational. A continuous function between two topological groups is called a \emph{polynomial map} of degree at most $d$ if it vanishes under any $d+1$ difference operators. Leibman, and subsequently Green and Tao, formulated and proved equidistribution theorems about polynomial sequences that take values in a nilmanifold. We formulate and prove some general equidistribution theorems regarding polynomial maps from a locally compact group into a compact abelian group., Comment: 18 pages. Incorrect statements from the previous version changed

In this paper we study the action of a countable group $\Gamma$ on the space of orders on the group. In particular, we are concerned with the invariant probability measures on this space, known as invariant random orders. We show that for any countable group the space of random invariant orders is rich enough to contain an isomorphic copy of any free ergodic action, and characterize the non-free actions realizable. We prove a Glasner-Weiss dichotomy regarding the simplex of invariant random orders. We also show that the invariant partial order on $\mathrm{SL}_3(\mathbf{Z})$ corresponding to the semigroup of positive matrices cannot be extended to an invariant random total order. We thus provide the first example for a partial order (deterministic or random) that cannot be randomly extended., Comment: 20 pages, 3 figures

We show that any finite-entropy, countable-valued finitary factor of an i.i.d process can also be expressed as a finitary factor of a finite-valued i.i.d process whose entropy is arbitrarily close to the target process. As an application, we give an affirmative answer to a question of van den Berg and Steif about the critical Ising model on $\mathbb{Z}^d$. En route, we prove several results about finitary isomorphisms and finitary factors. Our results are developed in a new framework for processes invariant to a permutation group of a countable set satisfying specific properties. This new framework includes all ``classical'' processes over countable amenable groups and all invariant processes on transitive amenable graphs with ``uniquely centered balls''. Some of our results are new already for $\mathbb{Z}$-processes. We prove a relative version of Smorodinsky's isomorphism theorem for finitely dependent $\mathbb{Z}$-processes. We also extend the Keane--Smorodinsky finitary isomorphism theorem to countable-valued i.i.d processes and to i.i.d processes taking values in a Polish space., Comment: 37 pages, 1 figure

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

The collection $\mathcal{M}_n$ of all metric spaces on $n$ points whose diameter is at most $2$ can naturally be viewed as a compact convex subset of $\mathbb{R}^{\binom{n}{2}}$, known as the metric polytope. In this paper, we study the metric polytope for large $n$ and show that it is close to the cube $[1,2]^{\binom{n}{2}} \subseteq \mathcal{M}_n$ in the following two senses. First, the volume of the polytope is not much larger than that of the cube, with the following quantitative estimates: \[ \left(\tfrac{1}{6}+o(1)\right)n^{3/2} \le \log \mathrm{Vol}(\mathcal{M}_n)\le O(n^{3/2}). \] Second, when sampling a metric space from $\mathcal{M}_n$ uniformly at random, the minimum distance is at least $1 - n^{-c}$ with high probability, for some $c > 0$. Our proof is based on entropy techniques. We discuss alternative approaches to estimating the volume of $\mathcal{M}_n$ using exchangeability, Szemer\'edi's regularity lemma, the hypergraph container method, and the K\H{o}v\'ari--S\'os--Tur\'an theorem., Comment: 64 pages, 2 figures. v2: Swapped Sections 5 and 6 and added a reader's guide

Given a finite generating set $A$ for a group $\Gamma$, we study the map $W \mapsto WA$ as a topological dynamical system -- a continuous self-map of the compact metrizable space of subsets of $\Gamma$. If the set $A$ generates $\Gamma$ as a semigroup and contains the identity, there are precisely two fixed points, one of which is attracting. This supports the initial impression that the dynamics of this map is rather trivial. Indeed, at least when $\Gamma= \mathbb{Z}^d$ and $A \subseteq \mathbb{Z}^d$ a finite positively generating set containing the natural invertible extension of the map $W \mapsto W+A$ is always topologically conjugate to the unique "north-south" dynamics on the Cantor set. In contrast to this, we show that various natural "geometric" properties of the finitely generated group $(\Gamma,A)$ can be recovered from the dynamics of this map, in particular, the growth type and amenability of $\Gamma$. When $\Gamma = \mathbb{Z}^d$, we show that the volume of the convex hull of the generating set $A$ is also an invariant of topological conjugacy. Our study introduces, utilizes and develops a certain convexity structure on subsets of the group $\Gamma$, related to a new concept which we call the sheltered hull of a set. We also relate this study to the structure of horoballs in finitely generated groups, focusing on the abelian case., Comment: 41 pages, 8 figures. Question about non-Busemann Horoballs from previous version has been answered (see arXiv:2010.07645)

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

A Borel system $(X,S)$ is `almost Borel universal' if any free Borel dynamical system $(Y,T)$ of strictly lower entropy is isomorphic to a Borel subsystem of $(X,S)$, after removing a null set. We obtain and exploit a new sufficient condition for a topological dynamical system to be almost Borel universal. We use our main result to deduce various conclusions and answer a number of questions. Along with additional results, we prove that a `generic' homeomorphism of a compact manifold of topological dimension at least two can model any ergodic transformation, that non-uniform specification implies almost Borel universality, and that $3$-colorings in $\mathbb Z^d$ and dimers in $\mathbb Z^2$ are almost Borel universal, Comment: Revised after Referee's comments; 70 pages

We prove that a topologically predictable action of a countable amenable group has zero topological entropy, as conjectured by Hochman. On route, we investigate invariant random orders and formulate a unified Kieffer-Pinsker formula for the Kolmogorov-Sinai entropy of measure preserving actions of amenable groups. We also present a proof due to Weiss for the fact that topologically prime actions of sofic groups have non-positive topological sofic entropy., Comment: 15 pages. Added reference to Ben Hayes's papers regarding "relative sofic entropy" of finite-to-one or compact extensions and regarding the "Abramov-Rokhlin sub-addition formula for sofic entropy"

Ma\~n\'e (1979) proved that if a compact metric space admits an expansive homeomorphism then it is finite dimensional. We generalize this theorem to multiparameter actions. The generalization involves mean dimension theory, which counts "averaged dimension" of a dynamical system. We prove that if $T:\mathbb{Z}^k\times X\to X$ is expansive and if $R:\mathbb{Z}^{k-1}\times X\to X$ commutes with $T$ then $R$ has finite mean dimension. When $k=1$, this statement reduces to Ma\~{n}\'{e}'s theorem. We also study several related issues, especially the connection with entropy theory., Comment: 27 pages

We find a new formula for the limit of the capacity of certain sequences of multidimensional semiconstrained systems as the dimension tends to infinity. We do so by generalizing the notion of independence entropy, originally studied in the context of constrained systems, to the study of semiconstrained systems. Using the independence entropy, we obtain new lower bounds on the capacity of multidimensional semiconstrained systems in general, and $d$-dimensional axial-product systems in particular. In the case of the latter, we prove our bound is asymptotically tight, giving the exact limiting capacity in terms of the independence entropy. We show the new bound improves upon the best-known bound in a case study of $(0,k,p)$-RLL., Comment: 31 pages

We study implications of expansiveness and pointwise periodicity for certain groups and semigroups of transformations. Among other things we prove that every pointwise periodic finitely generated group of cellular automata is necessarily finite. We also prove that a subshift over any finitely generated group that consists of finite orbits is finite, and related results for tilings of Euclidean space., Comment: 23 pages

Consider a countable amenable group acting by homeomorphisms on a compact metrizable space. Chung and Li asked if expansiveness and positive entropy of the action imply existence of an off-diagonal asymptotic pair. For algebraic actions of polycyclic-by-finite groups, Chung and Li proved it does. We provide examples showing that Chung and Li's result is near-optimal in the sense that the conclusion fails for some non-algebraic action generated by a single homeomorphism, and for some algebraic actions of non-finitely generated abelian groups. On the other hand, we prove that every expansive action of an amenable group with positive entropy that has the pseudo-orbit tracing property must admit off-diagonal asymptotic pairs. Using Chung and Li's algebraic characterization of expansiveness, we prove the pseudo-orbit tracing property for a class of expansive algebraic actions. This class includes every expansive principal algebraic action of an arbitrary countable group., Comment: 21 pages, some minor errors corrected

Semiconstrained systems were recently suggested as a generalization of constrained systems, commonly used in communication and data-storage applications that require certain offending subsequences be avoided. In an attempt to apply techniques from constrained systems, we study sequences of constrained systems that are contained in, or contain, a given semiconstrained system, while approaching its capacity. In the case of contained systems we describe to such sequences resulting in constant-to-constant bit-rate block encoders and sliding-block encoders. Surprisingly, in the case of containing systems we show that a "generic" semiconstrained system is never contained in a proper fully-constrained system., Comment: 15 pages

Alexopoulos proved that on a finitely generated virtually nilpotent group, the restriction of a harmonic function of polynomial growth to a torsion-free nilpotent subgroup of finite index is always a polynomial in the Mal'cev coordinates of that subgroup. For general groups, vanishing of higher-order discrete derivatives gives a natural notion of polynomial maps, which has been considered by Leibman and others. We provide a simple proof of Alexopoulos's result using this notion of polynomials, under the weaker hypothesis that the space of harmonic functions of polynomial growth of degree at most k is finite dimensional. We also prove that for a finitely generated group the Laplacian maps the polynomials of degree k surjectively onto the polynomials of degree k - 2. We then present some corollaries. In particular, we calculate precisely the dimension of the space of harmonic functions of polynomial growth of degree at most k on a virtually nilpotent group, extending an old result of Heilbronn for the abelian case, and refining a more recent result of Hua and Jost., Comment: 24 pages

We prove that for a measure preserving action of a sofic group with positive sofic entropy, the set of points with finite stabilizer have positive measure. This extends results of Weiss and Seward for amenable groups and free groups, respectively. It follows that the action of a sofic group on its subgroups by inner automorphisms has zero topological sofic entropy, and a faithful action with completely positive sofic entropy must be free., Comment: 14 Pages. Some typo corrections

In this work we study the structure of finitely generated groups for which a space of harmonic functions with fixed polynomial growth is finite dimensional. It is conjectured that such groups must be virtually nilpotent (the converse direction to Kleiner's theorem). We prove that this is indeed the case for solvable groups. The investigation is partly motivated by Kleiner's proof for Gromov's theorem on groups of polynomial growth.

This paper considers the general question of when a topological action of a countable group can be factored into a direct product of a nontrivial actions. In the early 1980's D. Lind considered such questions for $\mathbb{Z}$-shifts of finite type. We study in particular direct factorizations of subshifts of finite type over $\mathbb{Z}^d$ and other groups, and $\mathbb{Z}$-subshifts which are not of finite type. The main results concern direct factors of the multidimensional full $n$-shift, the multidimensional $3$-colored chessboard and the Dyck shift over a prime alphabet. A direct factorization of an expansive $\mathbb{G}$-action must be finite, but a example is provided of a non-expansive $\mathbb{Z}$-action for which there is no finite direct prime factorization. The question about existence of direct prime factorization of expansive actions remains open, even for $\mathbb{G}=\mathbb{Z}$., Comment: 21 pages, some changes and remarks added in response to suggestions by the referee. To appear in ETDS

When transmitting information over a noisy channel, two approaches, dating back to Shannon's work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code, or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this study. The first is proving closed-form bounds on the capacity which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained $(0,k)$-RLL tends to $1$ as $k$ grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems.

The well-known Hammersley-Clifford theorem states (under certain conditions) that any Markov random field is a Gibbs state for a nearest neighbor interaction. In this paper we study Markov random fields for which the proof of the Hammersley-Clifford theorem does not apply. Following Petersen and Schmidt we utilize the formalism of cocycles for the homoclinic equivalence relation and introduce "Markov cocycles", reparametrisations of Markov specifications. The main part of this paper exploits this to deduce the conclusion of the Hammersley-Clifford theorem for a family of Markov fields which are outside the theorem's purview where the underlying graph is $\mathbb{Z}^d$. This family includes all Markov random fields whose support is the d-dimensional "3-colored chessboard". On the other extreme, we construct a family of shift-invariant Markov random fields which are not given by any finite range shift-invariant interaction., Comment: 40 pages, 4 figures. Various typos corrected and proofs extended following suggestions by the referees

In this paper we show that any one-dimensional stationary, finite-valued Markov Random Field (MRF) is a Markov chain, without any mixing condition or condition on the support. Our proof makes use of two properties of the support $X$ of a finite-valued stationary MRF: 1) $X$ is non-wandering (this is a property of the support of any finite-valued stationary process) and 2) $X$ is a topological Markov field (TMF). The latter is a new property that sits in between the classes of shifts of finite type and sofic shifts, which are well-known objects of study in symbolic dynamics. Here, we develop the TMF property in one dimension, and we will develop this property in higher dimensions in a future paper. While we are mainly interested in discrete-time finite-valued stationary MRF's, we also consider continuous-time, finite-valued stationary MRF's, and show that these are (continuous-time) Markov chains as well., Comment: 15 pages

In this work, we study the problem of finding the asymptotic growth rate of the number of of $d$-dimensional arrays with side length $n$ over a given alphabet which avoid a list of one-dimensional "forbidden" words along all cardinal directions, as both $n$ and $d$ tend to infinity. Louidor, Marcus, and the second author called this quantity the "limiting entropy"; it is the limit of a sequence of topological entropies of a sequence of isotropic $\mathbb{Z}^d$ subshifts with the dimension $d$ tending to infinity. We find an expression for this limiting entropy which involves only one-dimensional words, which was implicitly conjectured earlier, and given the name "independence entropy." In the case where the list of "forbidden" words is finite, this expression is algorithmically computable and is of the form $\frac{1}{n} \log k$ for $k,n \in \mathbb{N}$. Our proof also characterizes the weak limits (as $d \rightarrow \infty$) of isotropic measures of maximal entropy; any such measure is a Bernoulli extension over some zero entropy factor from an explicitly defined set of measures. We also demonstrate how our results apply to various models previously studied in the literature, in some cases recovering or generalizing known results, but in other cases proving new ones., Comment: 25 pages

In this paper we study the Poisson process over a $\sigma$-finite measure-space equipped with a measure preserving transformation or a group of measure preserving transformations. For a measure-preserving transformation $T$ acting on a $\sigma$-finite measure-space $X$, the Poisson suspension of $T$ is the associated probability preserving transformation $T_*$ which acts on realization of the Poisson process over $X$. We prove ergodicity of the Poisson-product $T\times T_*$ under the assumption that $T$ is ergodic and conservative. We then show, assuming ergodicity of $T\times T_*$, that it is impossible to deterministically perform natural equivariant operations: thinning, allocation or matching. In contrast, there are well-known results in the literature demonstrating the existence of isometry equivariant thinning, matching and allocation of homogenous Poisson processes on $\mathbb{R}^d$. We also prove ergodicity of the "first return of left-most transformation" associated with a measure preserving transformation on $\mathbb{R}_+$, and discuss ergodicity of the Poisson-product of measure preserving group actions, and related spectral properties., Comment: Published in at http://dx.doi.org/10.1214/12-AOP824 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We consider a planar Poisson process and its associated Voronoi map. We show that there is a proper coloring with 6 colors of the map which is a deterministic isometry-equivariant function of the Poisson process. As part of the proof we show that the 6-core of the corresponding Delaunay triangulation is empty. Generalizations, extensions and some open questions are discussed., Comment: 21 pages, 1 figure

For SFTs, any equilibrium measure is Gibbs, as long a $f$ has $d$-summable variation. This is a theorem of Lanford and Ruelle. Conversely, a theorem of Dobru{\v{s}}in states that for strongly-irreducible subshifts, shift-invariant Gibbs-measures are equilibrium measures. Here we prove a generalization of the Lanford-Ruelle theorem: for all subshifts, any equilibrium measure for a function with $d$-summable variation is "topologically Gibbs". This is a relaxed notion which coincides with the usual notion of a Gibbs measure for SFTs. In the second part of the paper, we study Gibbs and equilibrium measures for some interesting families of subshifts: $\beta$-shifts, Dyck-shifts and Kalikow-type shifts (defined below). In all of these cases, a Lanford-Ruelle type theorem holds. For each of these families we provide a specific proof of the result., Comment: 19 pages

We discuss some numerical invariants of multidimensional shifts of finite type (SFTs) which are associated with the growth rates of the number of admissible finite configurations. Extending an unpublished example of Tsirelson, we show that growth complexities of the form $\exp(n^\alpha)$ are possible for non-integer $\alpha$'s. In terminology of Carvalho, such subshifts have entropy dimension $\alpha$. The class of possible $\alpha$'s are identified in terms of arithmetical classes of real numbers of Weihrauch and Zheng., Comment: 17 pages, 2 figures

This paper is a study of Glasner's definition of quasi-factors in the setting of infinite-measure preserving system. The existence of a system with zero Krengel entropy and a quasi-factor with positive entropy is obtained. On the other hand, relative zero-entropy for conservative systems implies relative zero-entropy of any quasi-factor with respect to its natural projection onto the factor. This extends (and is based upon) results of Glasner, Thouvenot and Weiss. Following and extending Glasner and Weiss, we also prove that any conservative measure preserving system with positive entropy in the sense of Danilenko and Rudolph admits any probability preserving system with positive entropy as a factor. Some applications and connections with Poisson-suspensions are presented., Comment: 13 pages

The Poisson entropy of an infinite-measure-preserving transformation is defined as the Kolmogorov entropy of its Poisson suspension. In this article, we relate Poisson entropy with other definitions of entropy for infinite transformations: For quasi-finite transformations we prove that Poisson entropy coincides with Krengel's and Parry's entropy. In particular, this implies that for null-recurrent Markov chains, the usual formula for the entropy $-\sum q_i p_{i,j}\log p_{i,j}$ holds in any of the definitions for entropy. Poisson entropy dominates Parry's entropy in any conservative transformation. We also prove that relative entropy (in the sense of Danilenko and Rudolph) coincides with the relative Poisson entropy. Thus, for any factor of a conservative transformation, difference of the Krengel's entropy is equal to the difference of the Poisson entropies. In case there exists a factor with zero Poisson entropy, we prove the existence of a maximum (Pinsker) factor with zero Poisson entropy. Together with the preceding results, this answers affirmatively the question raised in arXiv:0705.2148v3 about existence of a Pinsker factor in the sense of Krengel for quasi-finite transformations., Comment: 25 pages, a final section with some more results and questions added

We prove that multiple-recurrence and polynomial-recurrence of invertible infinite measure preserving transformations are both properties which pass to extensions., Comment: 4 pages. Replaces "Extensions and Multiple Recurrence of infinite measure preserving systems", plus a result about polynomial recurrence

We show that the values of entropies of multidimensional shifts of finite type (SFTs) are characterized by a certain computation-theoretic property: a real number $h\geq 0$ is the entropy of such an SFT if and only if it is right recursively enumerable, i.e. there is a computable sequence of rational numbers converging to $h$ from above. The same characterization holds for the entropies of sofic shifts. On the other hand, the entropy of an irreducible SFT is computable., Comment: 27 pages, 2 figures

Let $X=S^G$ where $G$ is a countable group and $S$ is a finite set. A cellular automaton (CA) is an endomorphism $T : X \to X$ (continuous, commuting with the action of $G$). Shereshevsky (1993) proved that for $G=Z^d$ with $d>1$ no CA can be forward expansive, raising the following conjecture: For $G=Z^d$, $d>1$ the topological entropy of any CA is either zero or infinite. Morris and Ward (1998), proved this for linear CA's, leaving the original conjecture open. We show that this conjecture is false, proving that for any $d$ there exist a $d$-dimensional CA with finite, nonzero topological entropy. We also discuss a measure-theoretic counterpart of this question for measure-preserving CA's. Our main tool is a construction of a CA by Kari (1994)., Comment: 17 pages, 11 figures; Added references, proposition 3.5 and correction of minor mistake in section 2

We show that a dissipative, ergodic measure preserving transformation of a sigma-finite, non-atomic measure space always has many non-proportional, absolutely continuous, invariant measures and is ergodic with respect to each one of these., Comment: example and reference added

In a previous paper by the author, it was shown that the One sided Dyck is uniquely ergodic with respect to the one sided-tail relation, where the tail invariant probability is also shift invariant and obtains the topological entropy. In this paper we show that the two sided Dyck has a double-tail invariant probability, which is also shift invariant, with entropy strictly less than the topological entropy. We also prove that this probability, along with the two equilibrium probabilities of the Dyck shift are the only ergodic double-tail invariant probabilities for the Dyck shift.

We show that the one-sided Dyck shift has a unique tail invariant topologically $\sigma$-finite measure (up to scaling). This invariant measure of the one sided Dyck turns out to be a shift-invariant probability. Furthermore, it is one of the two ergodic probabilities obtaining maximal entropy. For the two sided Dyck shift we show that there are exactly three ergodic double-tail invariant probabilities. We show that the two sided Dyck has a double-tail invariant probability, which is also shift invariant, with entropy strictly less than the topological entropy., Comment: Replaces old version of this article and also of math.DS/0408201. To appear in Israel J. of Math. This article is a part of the author's M.Sc. thesis, written under the supervision of J. Aaronson, Tel-Aviv University