Growth degree classification for finitely generated semigroups of integer matrices

Abstract

Let $\mathcal{A}$ be a finite set of $d\times d$ matrices with integer entries and let $m_n(\mathcal{A})$ be the maximum norm of a product of $n$ elements of $\mathcal{A}$. In this paper, we classify gaps in the growth of $m_n(\mathcal{A})$; specifically, we prove that ${\lim }_{n\to \infty }\log m_n(\mathcal{A})/\log n\in {\mathbb{Z}}_{⩾0}\cup \{\infty \}.$ This has applications to the growth of regular sequences as defined by Allouche and Shallit.

18 pages