Minoration of the complexity function associated to a translation on the torus (Q368519)

The authors study the combinatorics of minimal translations on the \(k\)-dimensional torus \(\mathbb{T}^k=\mathbb{R}^k/ \mathbb{Z}^k\), that is, maps given by \(\mathbf{x}\mapsto \mathbf{x}+\mathbf{a}\mod 1\), where \(\mathbf{a}=(a_1,\ldots,a_k)\in\mathbb{R}^k\) are such that the numbers \(1,a_1,\ldots,a_k\) are rationally independent. To present the main result, we need to introduce some notation. Recall that a ``fundamental domain'' is a set \(\mathcal{D}\subset\mathbb{R}^k\) such that the union of all its translations by integer vectors, \(\mathcal{D}+\mathbb{Z}^k\), covers \(\mathbb{R}^k\) modulo a Lebesgue null set. Let \(\{\mathcal{D}_1,\ldots,\mathcal{D}_m\}\) be a Lebesgue measurable partition of a fundamental domain \(\mathcal{D}\). A ``piecewise translation'' \(T\) associated to a minimal translation by a vector \(\mathbf{a}\) and \(\mathcal{D}_1,\ldots,\mathcal{D}_m\) is a map given by \(T(x)=x+a+\varphi(x)\), where \(\varphi:\mathcal{D}\to\mathbb{Z}^k\) is a measurable map such that for each \(i=1,\ldots,m\) there is a vector \(q_i\in\mathbb{Q}^k\) with \[ \int_{\mathcal{D}_i}\varphi(x)\text{d}\!\lambda(x)=\lambda(\mathcal{D}_i) r_i, \] where \(\lambda\) denotes the Lebesgue measure on \(\mathbb{R}^k\). The orbit of each point with respect to a piecewise translation \(T\) can be coded using the partition \(\mathcal{D}_1,\ldots,\mathcal{D}_m\) of the fundamental domain \(\mathcal{D}\). The coding map \(\mathsf{Cod}:\mathcal{D}\to\{1,\ldots,m\}\) is defined by \[ \mathsf{Cod}(x)_n=i \text{ if and only if }T^n(x)\in\mathcal{D}_i. \] The simplest example is the natural coding associated with an irrational rotation of the circle \(\mathbb{T}^1\). The complexity function \(p_k(n)\) counts the number of finite words \(\alpha_p\ldots\alpha_{p+n-1}\) of length \(n\) occurring in the sequence \(\mathsf{Cod}(x)=\alpha_0\alpha_1\alpha_2\ldots\). It is independent of the choice of \(x\). For \(k=2\) it is known that \(p_2(n)\) is bounded below by \(2n+1\), see [\textit{J.-F. Bertazzon}, Bull. Lond. Math. Soc. 44, No. 6, 1155--1168 (2012; Zbl 1280.68146)], and there exists a partition of the torus, called the ``Rauzy fractal'', such that the complexity function is equal to \(2n+1\) for any positive integer \(n\); see [\textit{G. Rauzy}, Bull. Soc. Math. Fr. 110, 147--178 (1982; Zbl 0522.10032)]. The main result states that the above result holds in full generality: the complexity function for the coding sequence of a piecewise translation of the \(k\)-dimensional torus satisfies \[ p_k(n)\geq nk+1 \text{ for all } n\geq 1. \] Furthermore, the authors show that for each positive integer \(k\), there exist a minimal translation on the \(k\)-dimensional torus and, associated to it, a piecewise translation with the complexity function \(p(n)=kn+1\) for \(n=1,2,\dots\).