Density of group languages in shift spaces

Abstract

The density of a rational language can be understood as the frequency of some pattern in the shift space, for example, a pattern like ‘words with an even number of a given letter’. We study the density of group languages, that is, rational languages recognized by morphisms onto finite groups, inside shift spaces. We show that the density with respect to any given ergodic measure on a shift space exists for every group language, because it can be computed by using any ergodic lift of the given measure to a skew product between the shift space and the recognizing group. We then further study densities in shifts of finite type (with a suitable notion of irreducibility) and then in minimal shifts. In the latter case, we obtain a closed formula for the density under the condition that the aforementioned skew product has minimal closed invariant subsets that are ergodic under the product of the original measure and the uniform probability measure on the group. The formula is derived in part from a characterization of minimal closed invariant subsets for skew products between shifts and finite groups relying on notions of cocycles and coboundaries. In the case where the whole skew product is ergodic under the product measure, then the density is just the cardinality of the subset of the group that defines the language divided by the cardinality of the group. Moreover, we provide sufficient conditions for the skew product to have minimal closed invariant subsets that are ergodic under the product measure. Finally, we investigate the link between minimal closed invariant subsets, return words, and bifix codes.