Letter frequency in shifts of finite type with one forbidden word
Abstract
This work considers combinatorial and statistical aspects of {\em{shifts of finite type}}, which are families of words over a finite alphabet which avoid a fixed class of {\emph{forbidden}} sub-words. The overarching question we are interested in is: how do local statistics of a uniformly random element of the shift space depend on combinatorial features of the forbidden set? We focus on the binary alphabet {0,1}, the class of shift spaces where a single pattern is forbidden, and the average frequency of $1$s (equivalently, the probability of observing $1$ at a given position). In this case, the relevant combinatorial information is encoded by a two-variable auto-correlation polynomial associated to the forbidden word, which we call the {\em{border polynomial}}. We present several results and examples characterizing the ordering of all words by their letter frequencies: for example, we describe the set of patterns which, when forbidden, cause the frequency of $1$s to increase, decrease, or stay exactly 1/2. Our methodologies include novel explicit local injections and bijections, generating function analysis, and a connection with a probabilistic notion of letter frequency.
Related
- The Quadratic Easy Coefficients Conjecture via Finite-Type Shifts and Zeta Functions
- Maximal subgroups of topological full groups of shifts of finite type
- A finite forbidden family with superlinear surplus and non-join extremal graphs
- Finite-to-One Maps into Band-Limited Function Spaces and Cubical Shifts with a Hurewicz Bound
- The Beurling-type theorem for powers of weighted Bergman shifts
BibTeX
@misc{bona2026letter,
title = {{Letter frequency in shifts of finite type with one forbidden word}},
author = {Miklós Bóna and Balázs Maga and Jacob Richey},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.06655},
eprint = {2606.06655},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.06655},
}
RIS
TY - UNPB
TI - Letter frequency in shifts of finite type with one forbidden word
AU - Miklós Bóna
AU - Balázs Maga
AU - Jacob Richey
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2606.06655
UR - https://arxiv.org/abs/2606.06655
AB - This work considers combinatorial and statistical aspects of {\em{shifts of finite type}}, which are families of words over a finite alphabet which avoid a fixed class of {\emph{forbidden}} sub-words. The overarching question we are interested in is: how do local statistics of a uniformly random element of the shift space depend on combinatorial features of the forbidden set? We focus on the binary alphabet {0,1}, the class of shift spaces where a single pattern is forbidden, and the average frequency of $1$s (equivalently, the probability of observing $1$ at a given position). In this case, the relevant combinatorial information is encoded by a two-variable auto-correlation polynomial associated to the forbidden word, which we call the {\em{border polynomial}}. We present several results and examples characterizing the ordering of all words by their letter frequencies: for example, we describe the set of patterns which, when forbidden, cause the frequency of $1$s to increase, decrease, or stay exactly 1/2. Our methodologies include novel explicit local injections and bijections, generating function analysis, and a connection with a probabilistic notion of letter frequency.
ER -