Universal finitary codes with exponential tails

In 1977, Keane and Smorodinsky showed that there exists a finitaryhomomorphism from any finite-alphabet Bernoulli process to anyother finite-alphabet Bernoulli process of strictly lower entropy.In 1996, Serafin proved the existence of a finitary homomorphismwith finite expected coding length. In this paper, we constructsuch a homomorphism in which the coding length has exponentialtails. Our construction is source-universal, in the sense thatit does not use any information on the source distribution otherthan the alphabet size and a bound on the entropy gap betweenthe source and target distributions. We also indicate how ourmethods can be extended to prove a source-specific version ofthe result for Markov chains.     

Hyperbolic structure preserving isomorphisms of Markov shifts. II

This paper is a continuation of [14] and deals with metric isomorphisms of Markov shifts which are finitary and hyperbolic structure preserving. We prove that theβ-function introduced by S. Tuncel in [15] is an invariant of such isomorphisms. Following [5] this result is extended to Gibbs measures arising from functions with summable variation. Finally we prove that, for anyC ² Axiom A diffeomorphism on a basic set Ω, and for any equilibrium state associated with a Hölder continuous function on Ω, the Markov shifts arising from different Markov partitions of Ω are isomorphic via a finitary, hyperbolic structure preserving isomorphism. This fact leads to a rich class of examples of such isomorphisms (other examples are provided by finitary isomorphisms of Markov shifts with finite expected code lengths — cf. [14]).     

The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm.     

Almost topological dynamical systems

For the notion of finitary isomorphism, which arises in many examples in ergodic theory, we prove some basic theorems about invariants, representations and the central limit theorem in shift spaces.     

The finitary coding of two Bernoulli schemes with unequal entropies has finite expectation

It is well known that for any two Bernoulli schemes with a finite number of states and unequal entropies, there exists a finitary homomorphism from the scheme with the larger entropy to the one with smaller entropy. We prove that the average number of coordinates in the larger entropy scheme needed to determine one coordinate in the image point is finite.     

Reduced Gröbner Bases of Certain Toric Varieties; A New Short Proof

We prove that every additively-idempotent semiring can be embedded in a finitary complete semiring. From this we obtain, among other results, that the classical identities of Kleene semirings over idempotent semirings are independent.     

On Using the Join Operation to Define Classes of Algebras

We call a class of algebras a finitary prevariety if the class is closed under the formation of subalgebras and finitary direct products, and contains the one-element algebra. The join of two finitary prevarieties and a concept of a join-irreducible finitary prevariety may be introduced naturally. We develop techniques for proving that a finitary prevariety of semigroups is join-irreducible, and find many examples of join-irreducible finitary prevarieties of semigroups. For example, we prove that if a class of finite semigroups is defined by ω-identities and contains the class J, then it is a join-irreducible finitary prevariety.     

Equivariant deformations of the affine multicone over a flag variety

We prove that the invariant Hilbert scheme parameterising the equivariant deformations of the affine multicone over a flag variety is, under certain hypotheses, an affine space. More specifically, we obtain that the isomorphism classes of equivariant deformations of such a multicone are in correspondence with the orbits of a well-determined wonderful variety.     

Entropy theory for sofic groupoids I: The foundations

This is the first part in a series in which sofic entropy theory is generalized to class-bijective extensions of sofic groupoids. Here we define topological and measure entropy and prove invariance. We also establish the variational principle, compute the entropy of Bernoulli shift actions and answer a question of Benjy Weiss pertaining to the isomorphism problem for non-free Bernoulli shifts. The proofs are independent of previous literature.     

Any two irreducible Markov chains of equal entropy are finitarily Kakutani equivalent

We show here that any two finite state irreducible Markov chains of the same entropy are finitarily Kakutani equivalent. By this we mean they are orbit equivalent by an invertible measure preserving mapping that is almost continuous and monotone in time when restricted to some cylinder set. Smorodinsky and Keane have shown that any two irreducible Markov chains of equal entropy and period are finitarily isomorphic. Hence, all that is necessary to obtain our result is to show that for every entropy h > 0 and period p ∈ ℕ there exists two irreducible Markov chains σ ₁, σ ₂ both of entropy h, where (1) σ ₁ is mixing (2) ς ₂ has period p and (3) σ1 and σ ₂ are finitarily Kakutani equivalent.     

Constructing finitary isomorphisms with finite expected coding times

This paper is motivated by the question of whether the invariants β, Δ,cΔ completely characterize isomorphism of Markov chains by finitary isomorphisms that have finite expected coding times (fect). We construct a finitary isomorphism with fect under an additional condition. Whether coincidence of β, Δ,cΔ implies the required condition remains open.     

Lie isomorphisms of reflexive algebras

A Lie isomorphism ? between algebras is called trivial if ?=ψ+τ, where ψ is an (algebraic) isomorphism or a negative of an (algebraic) anti-isomorphism, and τ is a linear map with image in the center vanishing on each commutator. In this paper, we investigate the conditions for the triviality of Lie isomorphisms from reflexive algebras with completely distributive and commutative lattices (CDCSL). In particular, we prove that a Lie isomorphism between irreducible CDCSL algebras is trivial if and only if it preserves I-idempotent operators (the sum of an idempotent and a scalar multiple of the identity) in both directions. We also prove the triviality of each Lie isomorphism from a CDCSL algebra onto a CSL algebra which has a comparable invariant projection with rank and corank not one. Some examples of Lie isomorphisms are presented to show the sharpness of the conditions.     

K-theory of equivariant quantization

Using an equivariant version of Connes? Thom isomorphism, we prove that equivariant K-theory is invariant under strict deformation quantization for a compact Lie group action.     

Entropy in the cusp and phase transitions for geodesic flows

In this paper we study the geodesic flow for a particular class of Riemannian non-compact manifolds with variable pinched negative sectional curvature. For a sequence of invariant measures we are able to prove results relating the loss of mass and bounds on the measure entropies. We compute the entropy contribution of the cusps. We develop and study the corresponding thermodynamic formalism. We obtain certain regularity results for the pressure of a class of potentials. We prove that the pressure is real analytic until it undergoes a phase transition, after which it becomes constant. Our techniques are based on the one hand on symbolic methods and Markov partitions, and on the other on geometric techniques and approximation properties at the level of groups.     

Families of type III0 ergodic transformations in distinct orbit equivalent classes

A new isomorphism invariant of certain measure preserving flows, using sequences of integers, is introduced. Using this invariant, we are able to construct large families of type III₀ systems which are not orbit equivalent. In particular we construct an uncountable family of nonsingular ergodic transformations, each having an associated flow that is approximately transitive (and therefore of zero entropy), with the property that the transformations are pairwise not orbit equivalent.     

Families of type III<Subscript>0</Subscript> ergodic transformations in distinct orbit equivalent classes

A new isomorphism invariant of certain measure preserving flows, using sequences of integers, is introduced. Using this invariant, we are able to construct large families of type III₀ systems which are not orbit equivalent. In particular we construct an uncountable family of nonsingular ergodic transformations, each having an associated flow that is approximately transitive (and therefore of zero entropy), with the property that the transformations are pairwise not orbit equivalent.     

On the mean square of the remainder for the euclidean lattice point counting problem

We study an invariant of dynamical systems called naive entropy, which is defined for both measurable and topological actions of any countable group. We focus on nonamenable groups, in which case the invariant is two-valued, with every system having naive entropy either zero or infinity. Bowen has conjectured that when the acting group is sofic, zero naive entropy implies sofic entropy at most zero for both types of systems. We prove the topological version of this conjecture by showing that for every action of a sofic group by homeomorphisms of a compact metric space, zero naive entropy implies sofic entropy at most zero. This result and the simple definition of naive entropy allow us to show that the generic action of a free group on the Cantor set has sofic entropy at most zero. We observe that a distal Γ-system has zero naive entropy in both senses, if Γ has an element of infinite order. We also show that the naive entropy of a topological system is greater than or equal to the naive measure entropy of the same system with respect to any invariant measure.     

On entropy of dynamical systems with almost specification

We construct a family of shift spaces with almost specification and multiple measures of maximal entropy. This answers a question from Climenhaga and Thompson [Israel J. Math. 192 (2012), 785–817]. Elaborating on our examples we prove that sufficient conditions for every shift factor of a shift space to be intrinsically ergodic given by Climenhaga and Thompson are in some sense best possible; moreover, the weak specification property neither implies intrinsic ergodicity, nor follows from almost specification. We also construct a dynamical system with the weak specification property, which does not have the almost specification property. We prove that the minimal points are dense in the support of any invariant measure of a system with the almost specification property. Furthermore, if a system with almost specification has an invariant measure with non-trivial support, then it also has uniform positive entropy over the support of any invariant measure and cannot be minimal.     

Hyperbolic structure preserving isomorphisms of Markov shifts

In this paper we consider metric isomorphisms of Markov shifts which are also isomorphisms of the hyperbolic structures of the shift spaces. We prove that such isomorphisms need not be finitary, and that finitary isomorphisms need not preserve the hyperbolic structures unless they have finite expected code lengths. In particular we show that certain explicity computable invariants previously associated with finitary isomorphisms with finite expected code lengths are, in fact, invariants of the hyperbolic structure of the Markov shifts.     

Six signed Petersen graphs,and their automorphisms

Up to switching isomorphism, there are six ways to put signs on the edges of the Petersen graph. We prove this by computing switching invariants, especially frustration indices and frustration numbers, switching automorphism groups, chromatic numbers, and numbers of proper 1-colorations, thereby illustrating some of the ideas and methods of signed graph theory. We also calculate automorphism groups and clusterability indices, which are not invariant under switching. In the process, we develop new properties of signed graphs, especially of their switching automorphism groups.