Realization of aperiodic subshifts and densities in groups

Nathalie Aubrun, Sebastián Barbieri, Stéphan Thomassé

Published 2015-07-13Version 1

A Theorem of Gao, Jackson and Seward, originally conjectured to be false by Glasner and Uspenskij, asserts that every countable group admits a 2-coloring. A direct consequence of this result is that every countable group has a strongly aperiodic subshift on the alphabet $\{0,1\}$. In this article, we use Lov\'asz local lemma to first give a new simple proof of this result, and second to prove the existence of a $G$-effective strongly aperiodic subshift for any finitely generated group $G$. We also study the problem of realizing densities in groups as a way of generalizing Sturmian sequences. This problem surprisingly turned out to be harder. We provide subshifts realizing any density only in the case of finitely generated amenable groups.