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.
Related
- Pimp my fixpoint: sofic realization of multidimensional substitution-based shift spaces
- Differentiation and Shift Property Characterisations of the Group Fourier Transform on the Heisenberg Group
- Generic Sharp Shift Embedding for Amenable Group Actions with the Uniform Rokhlin Property and Comparison
- Profinite approach to S-adic shift spaces II: Invertible directive sequences
- Learning under Target Shift: Optimal Density Ratio Estimation and Importance-Weighted Regression
BibTeX
@article{berthe2026density,
title = {{Density of group languages in shift spaces}},
author = {Valérie Berthé and Herman Goulet-Ouellet and Carl-Fredrik Nyberg Brodda and Dominique Perrin and Karl Petersen},
journal = {Ergodic Theory and Dynamical Systems},
year = {2026},
month = jun,
doi = {10.1017/etds.2026.10318},
eprint = {2403.17892},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05858544v1},
note = {CC BY},
}
RIS
TY - JOUR
TI - Density of group languages in shift spaces
AU - Valérie Berthé
AU - Herman Goulet-Ouellet
AU - Carl-Fredrik Nyberg Brodda
AU - Dominique Perrin
AU - Karl Petersen
PY - 2026
DA - 2026/06/23
JO - Ergodic Theory and Dynamical Systems
DO - 10.1017/etds.2026.10318
UR - https://hal.science/hal-05858544v1
AB - 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.
SN - 0143-3857
SN - 1469-4417
ER -