Finitary coloring (Q1681594)

The topic of the article is the coloring of \({\mathbb{Z}^d}\), \(d\geq 1\), by \({q\in\mathbb{N}}\) colors and the study of asymptotic properties of some existing \(q\)-coloring. More precisely, a \(q\)-coloring of~\({\mathbb{Z}^d}\) is a random element~\(X=(X_v)_{v\in\mathbb{Z}^d}\) of a probability space \({(\{1,\ldots,q\}^{\mathbb{Z}^d},\mathbb{P})}\) such that \({\mathbb{P}(X_u\neq X_v)=1}\) whenever \({|u-v|=1}.\) The authors assume that coloring is a finitary factor of an i.i.d. process (ffiid), i.e., \({X=F(Y)},\) where \(F\) is a measurable functions invariant under shifts of~\(\mathbb{Z}^d\) and \({Y=(Y_v)_{v\in\mathbb{Z}^d}}\) are i.i.d. variables. Furthermore, for almost every \(y\) (under distribution of \(Y\)) there exists \({0\leq r<\infty}\) such that whenever \(\tilde{y}\) agrees with \(y\) on the ball \[ {B(r):=\{v\in\mathbb{Z}^d : |v|=|v_1|+\cdots+|v_d|\leq r\}}, \] the zero values agree: \({F(y)_0=F(\tilde(y))_0}\). In that case, \(R(y)\) is the minimum of \(r\) with such property and \(R(Y)\) is a coding radius. The main results are statements on asymptotic distribution of the coding radius. Let \(\mathrm{tower}(r)=\underbrace{\exp\exp\ldots\exp}_{\lfloor r\rfloor\;\text{times}}1,\) then in the cases \(d=1\), \(q\geq3\) and \(d\geq2\), \(q\geq4\) there exist constants \(c,C>0\) such that: {\parindent=0.7cm \begin{itemize}\item[(1)] for every ffiid \(q\)-coloring \({\mathbb{P}(R>r)>1/\mathrm{tower}(Cr)}\) for any~\({r\geq 0};\) \item[(2)] there exists a ffiid \(q\)-coloring with \({\mathbb{P}(R>r)<1/\mathrm{tower}(cr)}\) for any \({r\geq0}\). In the cases \(d\geq2\) \(q=3\); \item[(3)] for every ffiid 3-coloring \({\mathbb{E}(R^2)=\infty}\); \item[(4)] there exists ffiid 3-coloring with \({\mathbb{P}(R>r)<r^{-\alpha}}\) for any~\({r\geq0}\) and some \({\alpha=\alpha(d)>0}.\) \end{itemize}} Also in the case \(d=1\), a generalization using shifts of finite type is presented.