Deterministic functions on amenable semigroups and a generalization of the Kamae-Weiss theorem on normality preservation

Abstract

A classical Kamae-Weiss theorem states that an increasing sequence $(n_i{)}_{i\in \mathbb{N}}$ of positive lower density is \emph{normality preserving}, i.e. has the property that for any normal binary sequence $(b_n{)}_{n\in \mathbb{N}}$, the sequence $(b_{n_i}{)}_{i\in \mathbb{N}}$ is normal, if and only if $(n_i{)}_{i\in \mathbb{N}}$ is a deterministic sequence. Given a countable cancellative amenable semigroup $G$, and a Følner sequence $\mathcal{F}=(F_n{)}_{n\in \mathbb{N}}$ in $G$, we introduce the notions of normality preservation, determinism and subexponential complexity for subsets of $G$ with respect to $\mathcal{F}$, and show that for sets of positive lower $\mathcal{F}$-density these three notions are equivalent. The proof utilizes the apparatus of the theory of tilings of amenable groups and the notion of tile-entropy. We also prove that under a natural assumption on $\mathcal{F}$, positive lower $\mathcal{F}$-density follows from normality preservation. Finally, we provide numerous examples of normality preserving sets in various semigroups

arXiv comment58 pages, 0 figures