# On forced periodicity of perfect colorings

Pyry Herva and Jarkko Kari

###### Abstract

We study forced periodicity of two-dimensional configurations under certain
constraints and use an algebraic approach to multidimensional symbolic
dynamics in which $d$-dimensional configurations and finite patterns are
presented as formal power series and Laurent polynomials, respectively, in $d$
variables. We consider perfect colorings that are configurations such that the
number of points of a given color in the neighborhood of any point depends
only on the color of the point for some fixed relative neighborhood, and we
show that by choosing the alphabet suitably any perfect coloring has a non-
trivial annihilator, that is, there exists a Laurent polynomial whose formal
product with the power series presenting the perfect coloring is zero. Using
known results we obtain a sufficient condition for forced periodicity of two-
dimensional perfect colorings. As corollaries of this result we get simple new
proofs for known results of forced periodicity on the square and the
triangular grids. Moreover, we obtain a new result concerning forced
periodicity of perfect colorings in the king grid. We also consider perfect
colorings of a particularly simple type: configurations that have low abelian
complexity with respect to some shape, and we generalize a result that gives a
sufficient condition for such configurations to be necessarily periodic. Also,
some algorithmic aspects are considered.

##  1 Introduction

We say that a $d$-dimensional configuration $c\in\mathcal{A}^{\Z^{d}}$, that
is, a coloring of the $d$-dimensional integer grid $\Z^{d}$ using colors from
a finite set $\mathcal{A}$ is a perfect coloring with respect to some finite
relative neighborhood $D\subseteq\Z^{d}$ if the number of any given color of
$\mathcal{A}$ in the pattern $c|_{\mathbf{u}+D}$ depends only on the color
$c(\mathbf{u})$ for any $\mathbf{u}\in\Z^{d}$. There is a similar version of
this definition for general graphs: a vertex coloring $\varphi\colon
V\rightarrow\mathcal{A}$ of a graph $G=(V,E)$ with a finite set $\mathcal{A}$
of colors is a perfect coloring of radius $r$ if the number of any given color
in the $r$-neighborhood of a vertex $u\in V$ depends only on the color
$\varphi(u)$ of $u$ [28, 29]. More generally, the definition of perfect
colorings is a special case of the definition of equitable partitions [8].

If $\varphi\colon V\rightarrow\\{0,1\\}$ is a binary vertex coloring of a
graph $G=(V,E)$ then we can define a subset $C\subseteq V$ of the vertex set –
a code – such that it contains all the vertices with color $1$. If $\varphi$
is a perfect coloring of radius $r$, then the code $C$ has the property that
the number of codewords of $C$ in the $r$-neighborhood of a vertex $u\in V$ is
$a$ if $u\not\in C$ and $b$ if $u\in C$ for some fixed non-negative integers
$a$ and $b$. This kind of code is called a perfect $(r,b,a)$-covering or
simply just a perfect multiple covering [1, 5]. This definition is related to
domination in graphs and covering codes [11, 5].

Let $D\subseteq\Z^{d}$ be a finite set and $\mathcal{A}$ a finite set of
colors. Two finite patterns $p,q\in\mathcal{A}^{D}$ are abelian equivalent if
the number of occurrences of each symbol in $\mathcal{A}$ is the same in them.
The abelian complexity of a configuration $c\in\mathcal{A}^{\Z^{d}}$ with
respect to a finite shape $D$ is the number of abelian equivalence classes of
patterns of shape $D$ in $c$ [30]. We note that if $c\in\mathcal{A}^{\Z^{d}}$
is a perfect coloring with respect to $D$ and $|\mathcal{A}|=n$, then the
abelian complexity of $c$ with respect to $D$ is at most $n$. Abelian
complexity is a widely studied concept in one-dimensional symbolic dynamics
and combinatorics on words [22].

In this paper we study forced periodicity of two-dimensional perfect
colorings, that is, we study conditions under which all the colorings are
necessarily periodic. We give a general condition for forced periodicity. As
corollaries of this result we get new proofs for known results [1, 28, 29]
concerning forced periodicity of perfect colorings in the square and the
triangular grid and a new result for forced periodicity of perfect colorings
in the king grid. Moreover, we study two-dimensional configurations of low
abelian complexity, that is, configurations that have abelian complexity 1
with respect to some shape: we generalize a statement of forced periodicity
concerning this type of configurations. We use an algebraic approach [17] to
multidimensional symbolic dynamics, i.e., we present configurations as formal
power series and finite patterns as Laurent polynomials. This approach was
developed to make progress in a famous open problem in symbolic dynamics –
Nivat’s conjecture [27] – concerning forced periodicity of two-dimensional
configurations that have a sufficiently low number of $m\times n$ rectangular
patterns for some $m,n$. The Nivat’s conjecture thus claims a two-dimensional
generalization of the Morse-Hedlund theorem [24].

This article is an extended version of the conference paper [12] where we
considered forced periodicity of perfect coverings, that is, perfect colorings
with only two colors.

### The structure of the paper

We begin in Section 2 by introducing the basic concepts of symbolic dynamics,
cellular automata and graphs, and defining perfect colorings formally. In
Section 3 we present the relevant algebraic concepts and the algebraic
approach to multidimensional symbolic dynamics, and in Section 4 we describe
an algorithm to find the line polynomial factors of a given two-dimensional
Laurent polynomial. In Section 5 we consider forced periodicity of perfect
coverings, i.e., perfect colorings with only two colors and then in Section 6
we extend the results from the previous section to concern perfect colorings
using arbitrarily large alphabets. After this we prove a statement concerning
forced periodicity of two-dimensional configurations of low abelian complexity
in Section 7. In Section 8 we consider some algorithmic questions concerning
perfect colorings.

##  2 Preliminaries

### Basics on symbolic dynamics

Let us review briefly some basic concepts of symbolic dynamics relevant to us.
For a reference see _e.g._ [4, 19, 21]. Although our results concern mostly
two-dimensional configurations, we state our definitions in an arbitrary
dimension.

Let $\mathcal{A}$ be a finite set (the _alphabet_) and let $d$ be a positive
integer (the _dimension_). A $d$-dimensional _configuration_ over
$\mathcal{A}$ is a coloring of the infinite grid $\Z^{d}$ using colors from
$\mathcal{A}$, that is, an element of $\mathcal{A}^{\Z^{d}}$ – the _$d$
-dimensional configuration space_ over the alphabet $\mathcal{A}$. We denote
by $c_{\mathbf{u}}=c(\mathbf{u})$ the symbol or color that a configuration
$c\in\mathcal{A}^{\Z^{d}}$ has in cell $\mathbf{u}$. The _translation_
$\tau^{\mathbf{t}}$ by a vector $\mathbf{t}\in\Z^{d}$ shifts a configuration
$c$ such that $\tau^{\mathbf{t}}(c)_{\mathbf{u}}=c_{\mathbf{u}-\mathbf{t}}$
for all $\mathbf{u}\in\Z^{d}$. A configuration $c$ is _$\mathbf{t}$ -periodic_
if $\tau^{\mathbf{t}}(c)=c$, and it is _periodic_ if it is
$\mathbf{t}$-periodic for some non-zero $\mathbf{t}\in\Z^{d}$. Moreover, we
say that a configuration is _periodic in direction_
$\mathbf{v}\in\Q^{d}\setminus\\{\mathbf{0}\\}$ if it is $k\mathbf{v}$-periodic
for some $k\in\Z$. A $d$-dimensional configuration $c$ is _strongly periodic_
if it has $d$ linearly independent vectors of periodicity. A strongly periodic
configuration is periodic in every rational direction. Two-dimensional
strongly periodic configurations are called _two-periodic_.

A finite _pattern_ is an assignment of symbols on some finite shape
$D\subseteq\Z^{d}$, that is, an element of $\mathcal{A}^{D}$. In particular,
the finite patterns in $\mathcal{A}^{D}$ are called _$D$ -patterns_. Let us
denote by $\mathcal{A}^{*}$ the set of all finite patterns over $\mathcal{A}$
where the dimension $d$ is known from the context. We say that a finite
pattern $p\in\mathcal{A}^{D}$ _appears_ in a configuration
$c\in\mathcal{A}^{\Z^{d}}$ or that $c$ _contains_ $p$ if
$\tau^{\mathbf{t}}(c)|_{D}=p$ for some $\mathbf{t}\in\Z^{d}$. For a fixed
shape $D$, the set of all $D$-patterns of $c$ is the set
$\mathcal{L}_{D}(c)=\\{\tau^{\mathbf{t}}(c)|_{D}\mid\mathbf{t}\in\Z^{d}\\}$
and the set of all finite patterns of $c$ is denoted by $\mathcal{L}(c)$ which
is called the _language of $c$_. For a set
$\mathcal{S}\subseteq\mathcal{A}^{\Z^{d}}$ of configurations we define
$\mathcal{L}_{D}(\mathcal{S})$ and $\mathcal{L}(\mathcal{S})$ as the unions of
$\mathcal{L}_{D}(c)$ and $\mathcal{L}(c)$ over all $c\in\mathcal{S}$,
respectively.

The _pattern complexity_ $P(c,D)$ of a configuration
$c\in\mathcal{A}^{\Z^{d}}$ with respect to a shape $D$ is the number of
distinct $D$-patterns that $c$ contains. For any $a\in\mathcal{A}$ we denote
by $|p|_{a}$ the number of occurrences of the color $a$ in a finite pattern
$p$. Two finite patterns $p,q\in\mathcal{A}^{D}$ are called _abelian
equivalent_ if $|p|_{a}=|q|_{a}$ for all $a\in\mathcal{A}$, that is, if the
number of occurrences of each color is the same in both $p$ and $q$. The
_abelian complexity_ $A(c,D)$ of a configuration $c\in\mathcal{A}^{\Z^{2}}$
_with respect to a finite shape $D$_ is the number of different $D$-patterns
in $c$ up to abelian equivalence [30]. Clearly $A(c,D)\leq P(c,D)$. We say
that $c$ has _low complexity_ with respect to $D$ if

$P(c,D)\leq|D|$

and that $c$ has _low abelian complexity_ with respect to $D$ if

$A(c,D)=1.$

The configuration space $\mathcal{A}^{\Z^{d}}$ can be made a compact
topological space by endowing $\mathcal{A}$ with the discrete topology and
considering the product topology it induces on $\mathcal{A}^{\Z^{d}}$ – the
_prodiscrete topology_. This topology is induced by a metric where two
configurations are close if they agree on a large area around the origin. So,
$\mathcal{A}^{\Z^{d}}$ is a compact metric space.

A subset $\mathcal{S}\subseteq\mathcal{A}^{\Z^{d}}$ of the configuration space
is a _subshift_ if it is topologically closed and translation-invariant
meaning that if $c\in\mathcal{S}$, then for all $\mathbf{t}\in\Z^{d}$ also
$\tau^{\mathbf{t}}(c)\in\mathcal{S}$. Equivalently, subshifts can be defined
using forbidden patterns: Given a set $F\subseteq\mathcal{A}^{*}$ of
_forbidden_ finite patterns, the set

$X_{F}=\\{c\in\mathcal{A}^{\Z^{d}}\mid\mathcal{L}(c)\cap F=\emptyset\\}$

of configurations that avoid all forbidden patterns is a subshift. Moreover,
every subshift is obtained by forbidding some set of finite patterns. If
$F\subseteq\mathcal{A}^{*}$ is finite, then we say that $X_{F}$ is a _subshift
of finite type_ (SFT).

The _orbit_ of a configuration $c$ is the set
$\mathcal{O}(c)=\\{\tau^{\mathbf{t}}(c)\mid\mathbf{t}\in\Z^{d}\\}$ of its
every translate. The _orbit closure_ $\overline{\mathcal{O}(c)}$ is the
topological closure of its orbit under the prodiscrete topology. The orbit
closure of a configuration $c$ is the smallest subshift that contains $c$. It
consists of all configurations $c^{\prime}$ such that
$\mathcal{L}(c^{\prime})\subseteq\mathcal{L}(c)$.

### Cellular automata

Let us describe briefly an old result of cellular automata theory that we use
in Section 6. See [13] for a more thorough survey on the topic.

A $d$-dimensional _cellular automaton_ or a _CA_ for short over a finite
alphabet $\mathcal{A}$ is a map
$F\colon\mathcal{A}^{\Z^{d}}\longrightarrow\mathcal{A}^{\Z^{d}}$ determined by
a neighborhood vector $N=(\mathbf{t}_{1},\ldots,\mathbf{t}_{n})$ and a local
rule $f\colon\mathcal{A}^{n}\longrightarrow\mathcal{A}$ such that

$F(c)(\mathbf{u})=f(c(\mathbf{u}+\mathbf{t}_{1}),\ldots,c(\mathbf{u}+\mathbf{t}_{n})).$

A CA is _additive_ or _linear_ if its local rule is of the form

$f(x_{1},\ldots,x_{n})=a_{1}x_{1}+\ldots+a_{n}x_{n}$

where $a_{1},\ldots,a_{n}\in R$ are elements of some finite ring $R$ and
$\mathcal{A}$ is an $R$-module.

In Section 6 we consider the surjectivity of cellular automata and use a
classic result called the _Garden-of-Eden theorem_ proved by Moore and Myhil
that gives a characterization for surjectivity in terms of injectivity on
“finite” configurations. Two configurations $c_{1}$ and $c_{2}$ are called
_asymptotic_ if the set $\text{diff}(c_{1},c_{2})=\\{\mathbf{u}\mid
c_{1}(\mathbf{u})\neq c_{2}(\mathbf{u})\\}$ of cells where they differ is
finite. A cellular automaton $F$ is _pre-injective_ if $F(c_{1})\neq F(c_{2})$
for any distinct asymptotic configurations $c_{1}$ and $c_{2}$. Clearly
injective CA are pre-injective. The Garden-of-Eden theorem states that pre-
injectivity of a CA is equivalent to surjectivity:

######  Theorem (Garden-of-Eden theorem, [23, 25]).

A CA is surjective if and only if it is pre-injective.

In the one-dimensional setting the Garden-of-Eden theorem yields the following
corollary:

######  Corollary.

For a one-dimensional surjective CA every configuration has only a finite
number of pre-images.

### Graphs

In this paper we consider graphs that are _simple_ , _undirected_ and
_connected_. A graph $G$ that has vertex set $V$ and edge set $E$ is denoted
by $G=(V,E)$. The _distance_ $d(u,v)$ of two vertices $u\in V$ and $v\in V$ of
a graph $G=(V,E)$ is the length of a shortest path between them in $G$. The
$r$-neighborhood of $u\in V$ in a graph $G=(V,E)$ is the set $N_{r}(u)=\\{v\in
V\mid d(v,u)\leq r\\}$. The graphs we consider has vertex set $V=\Z^{2}$ and a
translation invariant edge set
$E\subseteq\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u},\mathbf{v}\in\Z^{2},\mathbf{u}\neq\mathbf{v}\\}$.
This implies that for all $r$ and for any two points $\mathbf{u}\in\Z^{2}$ and
$\mathbf{v}\in\Z^{2}$ their $r$-neighborhoods are the same up to translation,
that is, $N_{r}(\mathbf{u})=N_{r}(\mathbf{v})+\mathbf{u}-\mathbf{v}$.
Moreover, we assume that all the vertices of $G$ have only finitely many
neighbors, i.e., we assume that the _degree_ of $G$ is finite. We call these
graphs two-dimensional _(infinite) grid graphs_ or just _(infinite) grids_. In
a grid graph $G$, let us call the $r$-neighborhood of $\mathbf{0}$ the
_relative $r$-neighborhood_ of $G$ since it determines the $r$-neighborhood of
any vertex in $G$. Indeed, for all $\mathbf{u}\in\Z^{2}$ we have
$N_{r}(\mathbf{u})=N_{r}+\mathbf{u}$ where $N_{r}$ is the relative
$r$-neighborhood of $G$. Given the edge set of a grid graph, the relative
$r$-neighborhood is determined for every $r$. We specify three 2-dimensional
infinite grid graphs:

  * •

The _square grid_ is the infinite grid graph $(\Z^{2},E_{\mathcal{S}})$ with

$E_{\mathcal{S}}=\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,\pm 1)\\}\\}.$

  * •

The _triangular grid_ is the infinite grid graph $(\Z^{2},E_{\mathcal{T}})$
with

$E_{\mathcal{T}}=\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,\pm 1),(1,1),(-1,-1)\\}\\}.$

  * •

The _king grid_ is the infinite grid graph $(\Z^{2},E_{\mathcal{K}})$ with

$E_{\mathcal{K}}=\\{\\{\mathbf{u},\mathbf{v}\\}\mid\mathbf{u}-\mathbf{v}\in\\{(\pm
1,0),(0,\pm 1),(\pm 1,\pm 1)\\}\\}.$

The relative $2$-neighborhoods of these grid graphs are pictured in Figure 1.

Figure 1: The relative $2$-neighborhoods of the square grid, the triangular
grid and the king grid, respectively.

### Perfect colorings

Let $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$ be a finite alphabet of $n$ colors
and let $D\subseteq\Z^{d}$ be a finite shape. A configuration
$c\in\mathcal{A}^{\Z^{d}}$ is a _perfect coloring with respect to
$D\subseteq\Z^{d}$_ or a _$D$ -perfect coloring_ if for all
$i,j\in\\{1,\ldots,n\\}$ there exist numbers $b_{ij}$ such that for all
$\mathbf{u}\in\Z^{d}$ with $c_{\mathbf{u}}=a_{j}$ the number of occurrences of
color $a_{i}$ in the $D$-neighborhood of $\mathbf{u}$, i.e., in the pattern
$c|_{\mathbf{u}+D}$ is exactly $b_{ij}$. The _matrix of a $D$-perfect
coloring_ $c$ is the matrix $\mathbf{B}=(b_{ij})_{n\times n}$ where the
numbers $b_{ij}$ are as above. A $D$-perfect coloring with matrix $\mathbf{B}$
is called a (perfect) _$(D,\mathbf{B})$ -coloring_. Any $D$-perfect coloring
is called simply a perfect coloring. In other words, a configuration is a
perfect coloring if the number of cells of a given color in the given
neighborhood of a vertex $\mathbf{u}$ depends only on the color of
$\mathbf{u}$.

Perfect colorings are defined also for arbitrary graphs $G=(V,E)$. Again, let
$\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$ be a finite set of $n$ colors. A vertex
coloring $\varphi\colon V\rightarrow\mathcal{A}$ of $G$ is an $r$-perfect
coloring with matrix $\mathbf{B}=(b_{ij})_{n\times n}$ if the number of
vertices of color $a_{i}$ in the $r$-neighborhood of a vertex of color $a_{j}$
is exactly $b_{ij}$. Clearly if $G$ is a translation invariant graph with
vertex set $\Z^{d}$, then the $r$-perfect colorings of $G$ are exactly the
$D$-perfect colorings in $\mathcal{A}^{\Z^{d}}$ where $D$ is the relative
$r$-neighborhood of the graph $G$.

##  3 Algebraic concepts

We review the basic concepts and some results relevant to us concerning an
algebraic approach to multidimensional symbolic dynamics introduced and
studied in [17]. See also [14] for a short survey of the topic.

Let $c\in\mathcal{A}^{\Z^{d}}$ be a $d$-dimensional configuration. The power
series presenting $c$ is the formal power series

$c(X)=c(x_{1},\ldots,x_{d})=\sum_{\mathbf{u}=(u_{1},\ldots,u_{d})\in\Z^{d}}c_{\mathbf{u}}x_{1}^{u_{1}}\cdots
x_{d}^{u_{d}}=\sum_{\mathbf{u}\in\Z^{d}}c_{\mathbf{u}}X^{\mathbf{u}}$

in $d$ variables $X=(x_{1},\ldots,x_{d})$. We denote the set of all formal
power series in $d$ variables $X=(x_{1},\ldots,x_{d})$ over a domain $M$ by
$M[[X^{\pm 1}]]=M[[x_{1}^{\pm 1},\ldots,x_{d}^{\pm 1}]]$. If $d=1$ or $d=2$,
we denote $x=x_{1}$ and $y=x_{2}$. A power series is _finitary_ if it has only
finitely many distinct coefficients and _integral_ if its coefficients are all
integers, i.e., if it belongs to the set $\Z[[X^{\pm 1}]]$. A configuration is
always presented by a finitary power series and a finitary power series always
presents a configuration. So, from now on we may call any finitary power
series a configuration.

We consider also Laurent polynomials which we may call simply just
polynomials. We denote the set of Laurent polynomials in $d$ variables
$X=(x_{1},\ldots,x_{d})$ over a ring $R$ by $R[X^{\pm 1}]=R[x_{1}^{\pm
1},\ldots,x_{d}^{\pm 1}]$. The term “proper” is used when we talk about proper
(i.e., non-Laurent) polynomials and denote the proper polynomial ring over $R$
by $R[X]$ as usual.

We say that two Laurent polynomials have no common factors if all their common
factors are units in the polynomial ring under consideration and that they
have a common factor if they have a non–unit common factor. For example, in
$\C[X^{\pm 1}]$ two polynomials have no common factors if all their common
factors are constants or monomials, and two proper polynomials in $\C[X]$ have
no common factors if all their common factors are constants. The _support_ of
a power series $c=c(X)=\sum_{\mathbf{u}\in\Z^{d}}c_{\mathbf{u}}X^{\mathbf{u}}$
is the set $\text{\rm supp}(c)=\\{\mathbf{u}\in\Z^{d}\mid c_{\mathbf{u}}\neq
0\\}$. Clearly a polynomial is a power series with a finite support. The $k$th
dilation of a polynomial $f(X)$ is the polynomial $f(X^{k})$. See Figure 2 for
an illustration of dilations.

Figure 2: The supports of the polynomial
$f(X)=1+x^{-1}y^{-1}+x^{-1}y^{1}+x^{1}y^{-1}+x^{1}y^{1}$ and its dilations
$f(X^{2})$ and $f(X^{3})$.

The $x_{i}$-resultant $\text{\rm Res}_{x_{i}}(f,g)$ of two proper polynomials
$f,g\in R[x_{1},\ldots,x_{d}]$ is the determinant of the _Sylvester matrix_ of
$f$ and $g$ with respect to variable $x_{i}$. We omit the details which the
reader can check from [6], and instead we consider the resultant $\text{\rm
Res}_{x_{i}}(f,g)\in R[x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{d}]$ for every
$i\in\\{1,\ldots,d\\}$ as a certain proper polynomial that has the following
two properties:

  * •

$\text{\rm Res}_{x_{i}}(f,g)$ is in the ideal generated by $f$ and $g$, i.e.,
there exist proper polynomials $h$ and $l$ such that

$hf+lg=\text{\rm Res}_{x_{i}}(f,g).$

  * •

If two proper polynomials $f$ and $g$ have no common factors in
$R[x_{1},\ldots,x_{d}]$, then $\text{\rm Res}_{x_{i}}(f,g)\neq 0$.

Let $R$ be a ring and $M$ a (left) $R$-module. The formal product of a
polynomial $f=f(X)=\sum_{i=1}^{m}a_{i}X^{\mathbf{u}_{i}}\in R[X^{\pm 1}]$ and
a power series
$c=c(X)=\sum_{\mathbf{u}\in\Z^{d}}c_{\mathbf{u}}X^{\mathbf{u}}\in M[X^{\pm
1}]$ is well-defined as the formal power series

$fc=f(X)c(X)=\sum_{\mathbf{u}\in\Z^{d}}(fc)_{\mathbf{u}}X^{\mathbf{u}}\in
M[X^{\pm 1}]$

where

$(fc)_{\mathbf{u}}=\sum_{i=1}^{m}a_{i}c_{\mathbf{u}-\mathbf{u}_{i}}.$

We say that a polynomial $f=f(X)$ _annihilates_ (or _is an annihilator of_) a
power series $c=c(X)$ if $fc=0$, that is, if their product is the zero power
series.

In a typical setting, we assume that $\mathcal{A}\subseteq\Z$ and hence
consider any configuration $c\in\mathcal{A}^{\Z^{d}}$ as a finitary and
integral power series $c(X)$. Since multiplying $c(X)$ by the monomial
$X^{\mathbf{u}}$ produces the power series presenting the translation
$\tau^{\mathbf{u}}(c)$ of $c$ by $\mathbf{u}$, we have that $c$ is
$\mathbf{u}$-periodic if and only if $c(X)$ is annihilated by the _difference
polynomial_ $X^{\mathbf{u}}-1$. (By a difference polynomial we mean a
polynomial $X^{\mathbf{u}}-1$ for any $\mathbf{u}\neq 0$.) This means that it
is natural to consider multiplication of $c$ by polynomials in $\C[X^{\pm
1}]$. However, note that the product of $c$ and a polynomial $f\in\C[X^{\pm
1}]$ may not be integral, but it is still finitary, hence a configuration. We
say that a polynomial $f$ _periodizes_ (or _is a periodizer of_) a
configuration $c$ if $fc$ is strongly periodic, that is, periodic in $d$
linearly independent directions. We denote the set of all periodizers with
complex coefficients of a configuration $c$ by $\text{\rm Per}(c)$ which is an
ideal of $\C[X^{\pm 1}]$ and hence we call it the _periodizer ideal_ of $c$.
Note that annihilators are periodizers. Note also that if $c$ has a periodizer
$f$, then $(X^{\mathbf{u}}-1)f$ is an annihilator of $c$ for some
$\mathbf{u}$. Thus, $c$ has a non-trivial (= non-zero) annihilator if and only
if it has a non-trivial periodizer. The following theorem states that if a
configuration has a non-trivial periodizer, then it has in fact an annihilator
of a particular simple form – a product of difference polynomials.

######  Theorem 1 ([17]).

Let $c\in\Z[[X^{\pm 1}]]$ be a configuration in any dimension and assume that
it has a non-trivial periodizer. Then there exist $m\geq 1$ and pairwise
linearly independent vectors $\mathbf{t}_{1},\ldots,\mathbf{t}_{m}$ such that

$(X^{\mathbf{t}_{1}}-1)\cdots(X^{\mathbf{t}_{m}}-1)$

annihilates $c$.

A _line polynomial_ is a polynomial whose support contains at least two points
and the points of the support lie on a unique line. In other words, a
polynomial $f$ is a line polynomial if it is not a monomial and there exist
vectors $\mathbf{u},\mathbf{v}\in\Z^{d}$ such that $\text{\rm
supp}(f)\subseteq\mathbf{u}+\Q\mathbf{v}$. In this case we say that $f$ is a
line polynomial in direction $\mathbf{v}$. We say that non-zero vectors
$\mathbf{v},\mathbf{v}^{\prime}\in\Z^{d}$ are _parallel_ if
$\mathbf{v}^{\prime}\in\Q\mathbf{v}$, and clearly then a line polynomial in
direction $\mathbf{v}$ is also a line polynomial in any parallel direction. A
vector $\mathbf{v}\in\Z^{d}$ is _primitive_ if its components are pairwise
relatively prime. If $\mathbf{v}$ is primitive, then
$\Q\mathbf{v}\cap\Z^{d}=\Z\mathbf{v}$. For any non-zero $\mathbf{v}\in\Z^{d}$
there exists a parallel primitive vector $\mathbf{v}^{\prime}\in\Z^{d}$. Thus,
we may assume the vector $\mathbf{v}$ in the definition of a line polynomial
$f$ to be primitive so that $\text{\rm
supp}(f)\subseteq\mathbf{u}+\Z\mathbf{v}$. In the following our preferred
presentations of directions are in terms of primitive vectors.

Any line polynomial $\phi$ in a (primitive) direction $\mathbf{v}$ can be
written uniquely in the form

$\phi=X^{\mathbf{u}}(a_{0}+a_{1}X^{\mathbf{v}}+\ldots+a_{n}X^{n\mathbf{v}})=X^{\mathbf{u}}(a_{0}+a_{1}t+\ldots+a_{n}t^{n})$

where $\mathbf{u}\in\Z^{d},n\geq 1,a_{0}\neq 0,a_{n}\neq 0$ and
$t=X^{\mathbf{v}}$. Let us call the single variable proper polynomial
$a_{0}+a_{1}t+\ldots+a_{n}t^{n}\in\C[t]$ the _normal form_ of $\phi$.
Moreover, for a monomial $aX^{\mathbf{u}}$ we define its normal form to be
$a$. So, two line polynomials in the direction $\mathbf{v}$ have the same
normal form if and only if they are the same polynomial up to multiplication
by $X^{\mathbf{u}}$, for some $\mathbf{u}\in\Z^{d}$.

Difference polynomials are line polynomials and hence the annihilator provided
by Theorem 1 is a product of line polynomials. Annihilation by a difference
polynomial means periodicity. More generally, annihilation of a configuration
$c$ by a line polynomial in a primitive direction $\mathbf{v}$ can be
understood as the annihilation of the one-dimensional _$\mathbf{v}$ -fibers_
$\sum_{k\in\Z}c_{\mathbf{u}+k\mathbf{v}}X^{\mathbf{u}+k\mathbf{v}}$ of $c$ in
direction $\mathbf{v}$, and since annihilation in the one-dimensional setting
implies periodicity with a bounded period, we conclude that a configuration is
periodic if and only if it is annihilated by a line polynomial. It is known
that if $c$ has a periodizer with line polynomial factors in at most one
primitive direction, then $c$ is periodic:

######  Theorem 2 ([18]).

Let $c\in\Z[[x^{\pm 1},y^{\pm 1}]]$ be a two-dimensional configuration and let
$f$ be a periodizer of $c$. Then the following conditions hold.

  * •

If $f$ does not have any line polynomial factors, then $c$ is two-periodic.

  * •

If all line polynomial factors of $f$ are in the same primitive direction,
then $c$ is periodic in this direction.

_Proof sketch._ The periodizer ideal $\text{\rm Per}(c)=\\{g\in\C[x^{\pm
1},y^{\pm 1}]\mid gc\text{ is two-periodic}\\}$ of $c$ is a principal ideal
generated by a polynomial $g=\phi_{1}\cdots\phi_{m}$ where
$\phi_{1},\ldots,\phi_{m}$ are line polynomials in pairwise non-parallel
directions [18]. Because $f\in\text{\rm Per}(c)$, we know that $g$ divides
$f$. If $f$ does not have any line polynomial factors, then $g=1$ and hence
$c=gc$ is two-periodic. If $f$ has line polynomial factors, and they are in
the same primitive direction $\mathbf{v}$, then $g$ is a line polynomial in
this direction. Since $gc$ is two-periodic, it is annihilated by
$(X^{k\mathbf{v}}-1)$ for some $k\in\Z$. This implies that the configuration
$c$ is annihilated by the line polynomial $(X^{k\mathbf{v}}-1)g$ in direction
$\mathbf{v}$. We conclude that $c$ is periodic in direction $\mathbf{v}$. ∎

The proof of the previous theorem sketched above relies heavily on the
structure of the ideal $\text{\rm Per}(c)$ developed in [17]. We give an
alternative proof sketch that mimics the usage of resultants in [16]:

_Second proof sketch of Theorem 2._ The existence of a non-trivial periodizer
$f$ implies by Theorem 1 that $c$ has a special annihilator
$g=\phi_{1}\cdots\phi_{m}$ that is a product of (difference) line polynomials
$\phi_{1},\ldots,\phi_{m}$ in pairwise non-parallel directions. All
irreducible factors of $g$ are line polynomials. If $f$ does not have any line
polynomial factors, then the periodizers $f$ and $g$ do not have common
factors. We can assume that both are proper polynomials as they can be
multiplied by a suitable monomial if needed. Because $f,g\in\text{\rm
Per}(c)$, also their resultant $\text{\rm Res}_{x}(f,g)\in\text{\rm Per}(c)$,
implying that $c$ has a non-trivial annihilator containing only variable $y$
since $\text{\rm Res}_{x}(f,g)\neq 0$ because $f$ and $g$ have no common
factors. This means that $c$ is periodic in the vertical direction.
Analogously, the _$y$ -resultant_ $\text{\rm Res}_{y}(f,g)$ shows that $c$ is
horizontally periodic, and hence two-periodic.

The proof for the case that $f$ has line polynomial factors only in one
direction $\mathbf{v}$ goes analogously by considering $\phi c$ instead of
$c$, where $\phi$ is the greatest common line polynomial factor of $f$ and $g$
in the direction $\mathbf{v}$. We get that $\phi c$ is two-periodic, implying
that $c$ is periodic in direction $\mathbf{v}$. ∎

In this paper we also consider configurations over alphabets $\mathcal{A}$
that are finite subsets of $\Z^{n}$, that is, the set of length $n$ integer
vectors, and hence study finitary formal power series from the set
$\Z^{n}[[X^{\pm 1}]]$ for $n\geq 2$. In particular, we call this kind of
configurations _integral vector configurations_. Also in this setting we
consider multiplication of power series by polynomials. The coefficients of
the polynomials are $n\times n$ integer matrices, i.e., elements of the ring
$\Z^{n\times n}$. Since $\Z^{n}$ is a (left) $\Z^{n\times n}$-module where we
consider the vectors of $\Z^{n}$ as column vectors, the product of a
polynomial $f=f(X)\in\Z^{n\times n}[X^{\pm 1}]$ and a power series
$c=c(X)\in\Z^{n}[[X^{\pm 1}]]$ is well-defined. Consequently, we say that
$c(X)\in\Z^{n}[[X^{\pm 1}]]$ is $\mathbf{t}$-periodic if it is annihilated by
the polynomial $\mathbf{I}X^{\mathbf{t}}-\mathbf{I}$ and that it is periodic
if it is $\mathbf{t}$-periodic for some non-zero $\mathbf{t}$.

There is a natural way to present configurations over arbitrary alphabets as
integral vector configurations. Let $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$ be
a finite alphabet with $n$ elements. The _vector presentation_ of a
configuration $c\in\mathcal{A}^{\Z^{d}}$ is the configuration
$c^{\prime}\in\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{n}\\}^{\Z^{d}}$ (or the
power series $c^{\prime}(X)\in\Z^{n}[[X^{\pm 1}]]$ presenting $c^{\prime}$)
defined such that $c^{\prime}_{\mathbf{u}}=\mathbf{e}_{i}$ if and only if
$c_{\mathbf{u}}=a_{i}$. Here by $\mathbf{e}_{i}\in\Z^{n}$ we denote the $i$th
natural base vector, i.e., the vector whose $i$th component is 1 while all the
other components are 0. Clearly $c$ is $\mathbf{t}$-periodic if and only if
its vector presentation is $\mathbf{t}$-periodic. Thus, to study the
periodicity of a configuration it is sufficient to study the periodicity of
its vector presentation.

The $i$th _layer_ of
$c=\sum\mathbf{c}_{\mathbf{u}}X^{\mathbf{u}}\in\Z^{n}[[X^{\pm 1}]]$ is the
power series

$\text{layer}_{i}(c)=\sum c_{\mathbf{u}}^{(i)}X^{\mathbf{u}}\in\Z[[X^{\pm
1}]]$

where $c_{\mathbf{u}}^{(i)}$ is the $i$th component of
$\mathbf{c}_{\mathbf{u}}$. Clearly $c\in\Z^{n}[[X^{\pm 1}]]$ is periodic in
direction $\mathbf{v}$ if and only if for all $i\in\\{1,\ldots,n\\}$ the $i$th
layer of $c$ is periodic in direction $\mathbf{v}$.

Finally, let $R$ be a finite ring and $\mathcal{A}$ a finite $R$-module. A
polynomial $f(X)=\sum_{i=1}^{n}a_{i}X^{-\mathbf{u}_{i}}\in R[x_{1}^{\pm
1},\ldots,x_{d}^{\pm 1}]$ defines an additive CA that has neighborhood vector
$(\mathbf{u}_{1},\ldots,\mathbf{u}_{n})$ and local rule
$f^{\prime}(y_{1},\ldots,y_{n})=a_{1}y_{1}+\ldots+a_{n}y_{n}$. More precisely,
the image of a configuration $c$ under the CA determined by $f$ is the
configuration $fc$.

##  4 Finding the line polynomial factors of a given two-variate Laurent
polynomial

In this section we have $d=2$ and hence all our polynomials are in two
variables $x$ and $y$. The open and closed _discrete half planes_ determined
by a non-zero vector $\mathbf{v}\in\Z^{2}$ are the sets
$H_{\mathbf{v}}=\\{\mathbf{u}\in\Z^{2}\mid\langle\mathbf{u},\mathbf{v}^{\perp}\rangle>0\\}$
and
$\overline{H}_{\mathbf{v}}=\\{\mathbf{u}\in\Z^{2}\mid\langle\mathbf{u},\mathbf{v}^{\perp}\rangle\geq
0\\}$, respectively, where $\mathbf{v}^{\perp}=(v_{2},-v_{1})$ is orthogonal
to $\mathbf{v}=(v_{1},v_{2})$. Let us also denote by
$l_{\mathbf{v}}=\overline{H}_{\mathbf{v}}\setminus H_{\mathbf{v}}$ the
discrete line parallel to $\mathbf{v}$ that goes through the origin. In other
words, the half plane determined by $\mathbf{v}$ is the half plane “to the
right” of the line $l_{\mathbf{v}}$ when moving along the line in the
direction of $\mathbf{v}$. We say that a finite set $D\subseteq\Z^{2}$ has an
_outer edge_ in direction $\mathbf{v}$ if there exists a vector
$\mathbf{t}\in\Z^{2}$ such that
$D\subseteq\overline{H}_{\mathbf{v}}+\mathbf{t}$ and
$|D\cap(l_{\mathbf{v}}+\mathbf{t})|\geq 2$. We call
$D\cap(l_{\mathbf{v}}+\mathbf{t})$ the outer edge of $D$ in direction
$\mathbf{v}$. An outer edge corresponding to $\mathbf{v}$ means that the
convex hull of $D$ has an edge in direction $\mathbf{v}$ in the clockwise
orientation around $D$.

If a finite non-empty set $D$ does not have an outer edge in direction
$\mathbf{v}$, then there exists a vector $\mathbf{t}\in\Z^{2}$ such that
$D\subseteq\overline{H}_{\mathbf{v}}+\mathbf{t}$ and
$|D\cap(l_{\mathbf{v}}+\mathbf{t})|=1$, and then we say that $D$ has a vertex
in direction $\mathbf{v}$. We call $D\cap(l_{\mathbf{v}}+\mathbf{t})$ the
vertex of $D$ in direction $\mathbf{v}$. We say that a polynomial $f$ has an
outer edge or a vertex in direction $\mathbf{v}$ if its support has an outer
edge or a vertex in direction $\mathbf{v}$, respectively. Note that every non-
empty finite shape $D$ has either an edge or a vertex in any non-zero
direction. Note also that in this context directions $\mathbf{v}$ and
$-\mathbf{v}$ are not the same: a shape may have an outer edge in direction
$\mathbf{v}$ but no outer edge in direction $-\mathbf{v}$. The following lemma
shows that a polynomial can have line polynomial factors only in the
directions of its outer edges.

######  Lemma 3 ([16]).

Let $f$ be a non-zero polynomial with a line polynomial factor in direction
$\mathbf{v}$. Then $f$ has outer edges in directions $\mathbf{v}$ and
$-\mathbf{v}$.

Let $\mathbf{v}\in\Z^{2}\setminus\\{\mathbf{0}\\}$ be a non-zero primitive
vector and let $f=\sum f_{\mathbf{u}}X^{\mathbf{u}}$ be a polynomial. Recall
that a _$\mathbf{v}$ -fiber_ of $f$ is a polynomial of the form

$\sum_{k\in\Z}f_{\mathbf{u}+k\mathbf{v}}X^{\mathbf{u}+k\mathbf{v}}$

for some $\mathbf{u}\in\Z^{2}$. Thus, a non-zero $\mathbf{v}$-fiber of a
polynomial is either a line polynomial or a monomial. Let us denote by
$\mathcal{F}_{\mathbf{v}}(f)$ the set of different normal forms of all non-
zero $\mathbf{v}$-fibers of a polynomial $f$, which is hence a finite set of
one-variate proper polynomials. The following simple example illustrates the
concept of fibers and their normal forms.

######  Example 4.

Let us determine the set $\mathcal{F}_{\mathbf{v}}(f)$ for
$f=f(X)=f(x,y)=3x+y+xy^{2}+xy+x^{3}y^{3}+x^{4}y^{4}$ and $\mathbf{v}=(1,1)$.
By grouping the terms we can write

$f=3x+y(1+xy)+xy(1+x^{2}y^{2}+x^{3}y^{3})=X^{(1,0)}\cdot
3+X^{(0,1)}(1+t)+X^{(1,1)}(1+t^{2}+t^{3})$

where $t=X^{(1,1)}=xy$. Hence,
$\mathcal{F}_{\mathbf{v}}(f)=\\{3,1+t,1+t^{2}+t^{3}\\}$. See Figure 3 for a
pictorial illustration. ∎

$3x$$y$$xy^{2}$$xy$$x^{3}y^{3}$$x^{4}y^{4}$ Figure 3: The support of
$f=3x+y+xy^{2}+xy+x^{3}y^{3}+x^{4}y^{4}$ and its different $(1,1)$-fibers.

As noticed in the example above, polynomials are linear combinations of their
fibers: for any polynomial $f$ and any non-zero primitive vector $\mathbf{v}$
we can write

$f=X^{\mathbf{u}_{1}}\psi_{1}+\ldots+X^{\mathbf{u}_{n}}\psi_{n}$

for some $\mathbf{u}_{1},\ldots,\mathbf{u}_{n}\in\Z^{2}$ where
$\psi_{1},\ldots,\psi_{n}\in\mathcal{F}_{\mathbf{v}}(f)$. We use this in the
proof of the next theorem.

######  Theorem 5.

A polynomial $f$ has a line polynomial factor in direction $\mathbf{v}$ if and
only if the polynomials in $\mathcal{F}_{\mathbf{v}}(f)$ have a common factor.

###### Proof.

For any line polynomial $\phi$ in direction $\mathbf{v}$, and for any
polynomial $g$, the $\mathbf{v}$-fibers of the product $\phi g$ have a common
factor $\phi$. In other words, if a polynomial $f$ has a line polynomial
factor $\phi$ in direction $\mathbf{v}$, then the polynomials in
$\mathcal{F}_{\mathbf{v}}(f)$ have the normal form of $\phi$ as a common
factor.

For the converse direction, assume that the polynomials in
$\mathcal{F}_{\mathbf{v}}(f)$ have a common factor $\phi$. Then there exist
vectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n}\in\Z^{2}$ and polynomials
$\phi\psi_{1},\ldots,\phi\psi_{n}\in\mathcal{F}_{\mathbf{v}}(f)$ such that

$f=X^{\mathbf{u}_{1}}\phi\psi_{1}+\ldots+X^{\mathbf{u}_{n}}\phi\psi_{n}.$

Hence, $\phi$ is a line polynomial factor of $f$ in direction $\mathbf{v}$. ∎

Note that Lemma 3 actually follows immediately from Theorem 5: A vertex
instead of an outer edge in direction $\mathbf{v}$ or $-\mathbf{v}$ provides a
non-zero monomial $\mathbf{v}$-fiber, which implies that the polynomials in
$\mathcal{F}_{\mathbf{v}}(f)$ have no common factors.

So, to find out the line polynomial factors of $f$ we first need to find out
the possible directions of the line polynomials, that is, the directions of
the (finitely many) outer edges of $f$, and then we need to check for which of
these possible directions $\mathbf{v}$ the polynomials in
$\mathcal{F}_{\mathbf{v}}(f)$ have a common factor. There are clearly
algorithms to find the outer edges of a given polynomial and to determine
whether finitely many line polynomials have a common factor. If such a factor
exists, then by Theorem 5 the polynomial $f$ has a line polynomial factor in
this direction. We have proved the following theorem.

######  Theorem 6.

There is an algorithm to find the line polynomial factors of a given (Laurent)
polynomial in two variables.

##  5 Forced periodicity of perfect colorings with two colors

In this section we consider forced periodicity of two-dimensional perfect
colorings with only two colors. Without loss of generality we may assume that
$\mathcal{A}=\\{a_{1},a_{2}\\}=\\{0,1\\}$ ($a_{1}=0,a_{2}=1$) and consider
perfect colorings $c\in\mathcal{A}^{\Z^{2}}$ since the names of the colors do
not matter in our considerations. So, let $c\in\\{0,1\\}^{\Z^{2}}$ be a
perfect coloring with respect to $D\subseteq\Z^{2}$ and let
$\mathbf{B}=(b_{ij})_{2\times 2}$ be the matrix of $c$. Let us define a set
$C=\\{\mathbf{u}\in\Z^{2}\mid c_{\mathbf{u}}=1\\}$. This set has the property
that the neighborhood $\mathbf{u}+D$ of a point $\mathbf{u}$ contains exactly
$a=b_{21}$ points of color $1$ if $\mathbf{u}\not\in C$ and exactly $b=b_{22}$
points of color $1$ if $\mathbf{u}\in C$. In fact, $C$ is a _perfect
(multiple) covering_ of the infinite grid $G$ determined by the relative
neighborhood $D$. More precisely, the set $C$ is a (perfect) _$(D,b,a)$
-covering_ of $G$. This is a variant of the following definition: in any graph
a subset $C$ of its vertex set is an _$(r,b,a)$ -covering_ if the number of
vertices of $C$ in the $r$-neighborhood of a vertex $u$ is $a$ if $u\not\in C$
and $b$ if $u\in C$. See [1] for a reference. Clearly in translation invariant
graphs the $(r,b,a)$-coverings correspond to $(D,b,a)$-coverings where $D$ is
the relative $r$-neighborhood of the graph. Thus, it is natural to call any
perfect coloring with only two colors a perfect covering. Note that a
$(D,b,a)$-covering is a $D$-perfect coloring with the matrix

$\mathbf{B}=\begin{pmatrix}|D|-a&|D|-b\\\ a&b\end{pmatrix}.$

The following theorem by Axenovich states that “almost every”
$(1,b,a)$-covering in the square grid is two-periodic.

######  Theorem 7 ([1]).

If $b-a\neq 1$, then every $(1,b,a)$-covering in the square grid is two-
periodic.

For a finite set $D\subseteq\Z^{2}$ we define its _characteristic polynomial_
to be the polynomial $f_{D}(X)=\sum_{\mathbf{u}\in D}X^{-\mathbf{u}}$. We
denote by $\mathbbm{1}(X)$ the constant power series
$\sum_{\mathbf{u}\in\Z^{2}}X^{\mathbf{u}}$. If $c\in\\{0,1\\}^{\Z^{2}}$ is a
$(D,b,a)$-covering, then from the definition we get that
$f_{D}(X)c(X)=(b-a)c(X)+a\mathbbm{1}(X)$ which is equivalent to
$\left(f_{D}(X)-(b-a)\right)c(X)=a\mathbbm{1}(X)$. Thus, if $c$ is a
$(D,b,a)$-covering, then $f_{D}(X)-(b-a)$ is a periodizer of $c$. Hence, by
Theorem 2 the condition that the polynomial $f_{D}(X)-(b-a)$ has no line
polynomial factors is a sufficient condition for forced periodicity of a
$(D,b,a)$-covering. Hence, we have the following corollary of Theorem 2:

######  Corollary 8.

Let $D\subseteq\Z^{2}$ be a finite shape and let $b$ and $b$ be non-negative
integers. If $g=f_{D}-(b-a)$ has no line polynomial factors, then every
$(D,b,a)$-covering is two-periodic.

Using our formulation and the algebraic approach we get a simple proof for
Theorem 7:

######  Reformulation of Theorem 7.

Let $D$ be the relative 1-neighborhood of the square grid and assume that
$b-a\neq 1$. Then every $(D,b,a)$-covering is two-periodic.

###### Proof.

Let $c$ be an arbitrary $(D,b,a)$-covering. The outer edges of
$g=f_{D}-(b-a)=x^{-1}+y^{-1}+1-(b-a)+x+y$ are in directions
$(1,1),(-1,-1),(1,-1)$ and $(-1,1)$ and hence by Lemma 3 any line polynomial
factor of $g$ is either in direction $(1,1)$ or $(1,-1)$. For
$\mathbf{v}\in\\{(1,1),(1,-1)\\}$ we have
$\mathcal{F}_{\mathbf{v}}(g)=\\{1+t,1-(b-a)\\}$. See Figure 4 for an
illustration. Since $1-(b-a)$ is a non-trivial monomial, by Theorem 5 the
periodizer $g\in\text{\rm Per}(c)$ has no line polynomial factors and hence
the claim follows by corollary 8. ∎

We also get a similar proof for the following known result concerning the
forced periodicity perfect coverings in the square grid with radius $r\geq 2$.

######  Theorem 9 ([29]).

Let $r\geq 2$ and let $D$ be the relative $r$-neighborhood of the square grid.
Then every $(D,b,a)$-covering is two-periodic. In other words, all
$(r,b,a)$-coverings in the square grid are two-periodic for all $r\geq 2$.

###### Proof.

Let $c$ be an arbitrary $(D,b,a)$-covering. By Lemma 3 any line polynomial
factor of $g=f_{D}-(b-a)$ has direction $(1,1)$ or $(1,-1)$. So, assume that
$\mathbf{v}\in\\{(1,1),(1,-1)\\}$. We have
$\phi_{1}=1+t+\ldots+t^{r}\in\mathcal{F}_{\mathbf{v}}(g)$ and
$\phi_{2}=1+t+\ldots+t^{r-1}\in\mathcal{F}_{\mathbf{v}}(g)$. See Figure 4 for
an illustration in the case $r=2$. Since $\phi_{1}-\phi_{2}=t^{r}$, the
polynomials $\phi_{1}$ and $\phi_{2}$ have no common factors, and hence by
Theorem 5 the periodizer $g$ has no line polynomial factors. Corollary 8 gives
the claim. ∎

$1+t$$1-(b-a)$$1+t+t^{2}$$1+t$$1+t+t^{2}+t^{3}+t^{4}$$1+t+(1-(b-a))t^{2}+t^{3}+t^{4}$$1+t$$1+(1-(b-a))t+t^{2}$$1+t+t^{2}$$1+t+t^{2}+t^{3}$
Figure 4: Pictorial illustrations for the proofs of Theorems 7, 9, 10, 11 and
12. The constellation on the left of the upper row illustrates the proof of
Theorem 7. The constellation in the center of the upper row illustrates the
proof of Theorem 9 with $r=2$. The constellation on the right of the upper row
illustrates the proof of Theorem 12 with $r=2$. The constellation on the left
of the lower row illustrates the proof of Theorem 10. The constellation on the
right of the lower row illustrates the proof of Theorem 11 with $r=2$. In each
of the constellations we have pointed out two normal forms with no common
factors in $\mathcal{F}_{\mathbf{v}}(g)$ from the points of $\text{\rm
supp}(g)$ for one of the outer edges $\mathbf{v}$ of $\text{\rm supp}(g)$.

There are analogous results in the triangular grid, and we can prove them
similarly using Corollary 8.

######  Theorem 10 ([29]).

Let $D$ be the relative 1-neighborhood of the triangular grid and assume that
$b-a\neq-1$. Then every $(D,b,a)$-covering in the triangular grid is two-
periodic. In other words, all $(1,b,a)$-coverings in the triangular grid are
two-periodic whenever $b-a\neq-1$.

###### Proof.

Let $c$ be an arbitrary $(D,b,a)$-covering. The outer edges of
$g=f_{D}-(b-a)=x^{-1}y^{-1}+x^{-1}+y^{-1}+1-(b-a)+x+y+xy$ have directions
$(1,1),(-1,-1),(1,0),(-1,0)$, $(0,1)$ and $(0,-1)$ and hence by Lemma 3 any
line polynomial factor of $g$ has direction $(1,1)$, $(1,0)$ or $(0,1)$. So,
let $\mathbf{v}\in\\{(1,1),(1,0),(0,1)\\}$. We have
$\mathcal{F}_{\mathbf{v}}(g)=\\{1+t,1+(1-(b-a))t+t^{2}\\}$. See Figure 4 for
an illustration. Polynomials $\phi_{1}=1+t$ and $\phi_{2}=1+(1-(b-a))t+t^{2}$
satisfy $\phi_{1}^{2}-\phi_{2}=(1+b-a)t$. Thus, they do not have any common
factors if $b-a\neq-1$ and hence by Theorem 5 the polynomial $g$ has no line
polynomial factors. The claim follows by Corollary 8. ∎

######  Theorem 11 ([29]).

Let $r\geq 2$ and let $D$ be the relative $r$-neighborhood of the triangular
grid. Then every $(D,b,a)$-covering is two-periodic. In other words, every
$(r,b,a)$-covering in the triangular grid is two-periodic for all $r\geq 2$.

###### Proof.

Let $c$ be an arbitrary $(D,b,a)$-covering. The outer edges of $g=f_{D}-(b-a)$
have directions $(1,1)$, $(-1,-1)$, $(1,0)$, $(-1,0)$, $(0,1)$ and $(0,-1)$,
and hence by Lemma 3 any line polynomial factor of $g$ has direction $(1,1)$,
$(1,0)$ or $(0,1)$. So, let $\mathbf{v}\in\\{(1,1),(1,0),(0,1)\\}$. There
exists $n\geq 1$ such that $1+t+\ldots+t^{n}\in\mathcal{F}_{\mathbf{v}}(g)$
and $1+t+\ldots+t^{n+1}\in\mathcal{F}_{\mathbf{v}}(g)$. See Figure 4 for an
illustration with $r=2$. Since these two polynomials have no common factors,
by Theorem 5 the polynomial $g$ has no line polynomial factors. Again,
Corollary 8 yields the claim. ∎

If $a\neq b$, then for all $r\geq 1$ any $(r,b,a)$-covering in the king grid
is two-periodic:

######  Theorem 12.

Let $r\geq 1$ be arbitrary and let $D$ be the relative $r$-neighborhood of the
king grid and assume that $a\neq b$. Then any $(D,b,a)$-covering is two-
periodic. In other words, all $(r,b,a)$-coverings in the king grid are two-
periodic whenever $a\neq b$.

###### Proof.

Let $c$ be an arbitrary $(D,b,a)$-covering. The outer edges of $g=f_{D}-(b-a)$
are in directions $(1,0),(-1,0),(0,1)$ and $(0,-1)$. Hence, by Lemma 3 any
line polynomial factor of $g$ has direction $(1,0)$ or $(0,1)$. Let
$\mathbf{v}\in\\{(1,0),(0,1)\\}$. We have
$\phi_{1}=1+t+\ldots+t^{r-1}+(1-(b-a))t^{r}+t^{r+1}+\ldots+t^{2r}\in\mathcal{F}_{\mathbf{v}}(g)$
and $\phi_{2}=1+t+\ldots+t^{2r}\in\mathcal{F}_{\mathbf{v}}(g)$. See Figure 4
for an illustration in the case $r=2$. Since $\phi_{2}-\phi_{1}=(b-a)t^{r}$ is
a non-trivial monomial, $\phi_{1}$ and $\phi_{2}$ have no common factors.
Thus, by Theorem 5 the polynomial $g$ has no line polynomial factors and the
claim follows by Corollary 8. ∎

In the above proofs we used the fact that two Laurent polynomials in one
variable have no common factors if and only if they generate the entire ideal
$\C[t^{\pm 1}]$, and they do this if and only if they generate a non-zero
monomial. This is known as the _weak Nullstellensatz_ [6].

A shape $D\subseteq\Z^{2}$ is _convex_ if it is the intersection $D=\text{\rm
conv}(D)\cap\Z^{2}$ where $\text{\rm conv}(D)\subseteq\R^{2}$ is the real
convex hull of $D$. Above all our shapes were convex. Next we generalize the
above theorems and give a sufficient condition for forced periodicity of
$(D,b,a)$-coverings for convex $D$.

So, let $D\subseteq\Z^{2}$ be a finite convex shape. Any $(D,b,a)$-covering
has a periodizer $g=f_{D}-(b-a)$. As earlier, we study whether $g$ has any
line polynomial factors since if it does not, then Corollary 8 guarantees
forced periodicity. For any $\mathbf{v}\neq\mathbf{0}$ the set
$\mathcal{F}_{\mathbf{v}}(f_{D})$ contains only polynomials
$\phi_{n}=1+\ldots+t^{n-1}$ for different $n\geq 1$ since $D$ is convex: if
$D$ contains two points, then $D$ contains every point between them. Thus,
$\mathcal{F}_{\mathbf{v}}(g)$ contains only polynomials $\phi_{n}$ for
different $n\geq 1$ and, if $b-a\neq 0$, it may also contain a polynomial
$\phi_{n_{0}}-(b-a)t^{m_{0}}$ for some $n_{0}\geq 1$ such that
$\phi_{n_{0}}\in\mathcal{F}_{\mathbf{v}}(f_{D})$ and for some $m_{0}\geq 0$.
If $b-a=0$, then $g=f_{D}$ and thus
$\mathcal{F}_{\mathbf{v}}(g)=\mathcal{F}_{\mathbf{v}}(f_{D})$.

Two polynomials $\phi_{m}$ and $\phi_{n}$ have a common factor if and only if
$\gcd(m,n)>1$. More generally, the polynomials
$\phi_{n_{1}},\ldots,\phi_{n_{r}}$ have a common factor if and only if
$d=\gcd(n_{1},\ldots,n_{r})>1$ and, in fact, their greatest common factor is
the $d$th _cyclotomic polynomial_

$\prod_{\begin{subarray}{c}1\leq k\leq d\\\
\gcd(k,d)=1\end{subarray}}(t-e^{i\cdot\frac{2\pi k}{d}}).$

Let us introduce the following notation. For any polynomial $f$, we denote by
$\mathcal{F}^{\prime}_{\mathbf{v}}(f)$ the set of normal forms of the non-zero
fibers $\sum_{k\in\Z}f_{\mathbf{u}+k\mathbf{v}}X^{\mathbf{u}+k\mathbf{v}}$ for
all $\mathbf{u}\not\in\Z\mathbf{v}$. In other words, we exclude the fiber
through the origin. Let us also denote $\text{\rm fib}_{\mathbf{v}}(f)$ for
the normal form of the fiber $\sum_{k\in\Z}f_{k\mathbf{v}}X^{k\mathbf{v}}$
through the origin. We have
$\mathcal{F}_{\mathbf{v}}(f)=\mathcal{F}^{\prime}_{\mathbf{v}}(f)\cup\\{\text{\rm
fib}_{\mathbf{v}}(f)\\}$ if $\text{\rm fib}_{\mathbf{v}}(f)\neq 0$ and
$\mathcal{F}_{\mathbf{v}}(f)=\mathcal{F}^{\prime}_{\mathbf{v}}(f)$ if
$\text{\rm fib}_{\mathbf{v}}(f)=0$.

Applying Theorems 2 and 5 we have the following theorem that gives sufficient
conditions for every $(D,b,a)$-covering to be periodic for a finite and convex
$D$. This theorem generalizes the results proved above. In fact, they are
corollaries of the theorem. The first part of the theorem was also mentioned
in [7] in a slightly different context and in a more general form.

######  Theorem 13.

Let $D$ be a finite convex shape, $g=f_{D}-(b-a)$ and let $E$ be the set of
the outer edge directions of $g$.

  * •

Assume that $b-a=0$. For any $\mathbf{v}\in E$ denote
$d_{\mathbf{v}}=\gcd(n_{1},\ldots,n_{r})$ where
$\mathcal{F}_{\mathbf{v}}(g)=\\{\phi_{n_{1}},\ldots,\phi_{n_{r}}\\}$. If
$d_{\mathbf{v}}=1$ holds for all $\mathbf{v}\in E$, then every
$(D,b,a)$-covering is two-periodic. If $d_{\mathbf{v}}=1$ holds for all but
some parallel $\mathbf{v}\in E$, then every $(D,b,a)$-covering is periodic.

  * •

Assume that $b-a\neq 0$. For any $\mathbf{v}\in E$ denote
$d_{\mathbf{v}}=\gcd(n_{1},\ldots,n_{r})$ where
$\mathcal{F}^{\prime}_{\mathbf{v}}(g)=\\{\phi_{n_{1}},\ldots,\phi_{n_{r}}\\}$.
If the $d_{\mathbf{v}}$’th cyclotomic polynomial and $\text{\rm
fib}_{\mathbf{v}}(g)$ have no common factors for any $\mathbf{v}\in E$, then
every $(D,b,a)$-covering is two-periodic. If the condition holds for all but
some parallel $\mathbf{v}\in E$, then every $(D,b,a)$-covering is periodic.
(Note that the condition is satisfied, in particular, if $d_{\mathbf{v}}=1$.)

###### Proof.

Assume first that $b-a=0$. If $d_{\mathbf{v}}=1$ for all $\mathbf{v}\in E$,
then the $\mathbf{v}$-fibers of $g$ have no common factors and hence by
Theorem 5 $g$ has no line polynomial factors. If $d_{\mathbf{v}}=1$ holds for
all but some parallel $\mathbf{v}\in E$, then all the line polynomial factors
of $g$ are in parallel directions. Thus, the claim follows by Theorem 2.

Assume then that $b-a\neq 0$. If the $d_{\mathbf{v}}$’th cyclotomic polynomial
and $\text{\rm fib}_{\mathbf{v}}(g)$ have no common factors for all
$\mathbf{v}\in E$, then by Theorem 5 $g$ has no line polynomial factors. If
the condition holds for all but some parallel $\mathbf{v}\in E$, then all the
line polynomial factors of $g$ are in parallel directions. Thus, by Theorem 2
the claim holds also in this case. ∎

##  6 Forced periodicity of perfect colorings over arbitrarily large alphabets

In this section we prove a theorem that gives a sufficient condition for
forced periodicity of two-dimensional perfect colorings over an arbitrarily
large alphabet. As corollaries of the theorem and theorems from the previous
section we obtain conditions for forced periodicity of perfect colorings in
two-dimensional infinite grid graphs.

We start by proving some lemmas that work in any dimension. We consider the
vector presentations of perfect colorings because this way we get a non-
trivial annihilator for any such vector presentation:

######  Lemma 14.

Let $c$ be the vector presentation of a $D$-perfect coloring over an alphabet
of size $n$ with matrix $\mathbf{B}=(b_{ij})_{n\times n}$. Then $c$ is
annihilated by the polynomial

$f(X)=\sum_{\mathbf{u}\in D}\mathbf{I}X^{-\mathbf{u}}-\mathbf{B}.$

_Remark._ Note the similarity of the above annihilator to the periodizer
$\sum_{\mathbf{u}\in D}X^{-\mathbf{u}}-(b-a)$ of a $(D,b,a)$-covering.

###### Proof.

Let $\mathbf{v}\in\Z^{d}$ be arbitrary and assume that
$c_{\mathbf{v}}=\mathbf{e}_{j}$. Then
$(\mathbf{B}c)_{\mathbf{v}}=\mathbf{B}\mathbf{e}_{j}$ is the $j$th column of
$\mathbf{B}$. On the other hand, from the definition of $\mathbf{B}$ we have
$((\sum_{\mathbf{u}\in
D}\mathbf{I}X^{-\mathbf{u}})c)_{\mathbf{v}}=\sum_{\mathbf{u}\in
D}c_{\mathbf{v}+\mathbf{u}}=\sum_{i=1}^{n}b_{ij}\mathbf{e}_{i}$ which is also
the $j$th column of $\mathbf{B}$. Thus, $(fc)_{\mathbf{v}}=0$ and hence $fc=0$
since $\mathbf{v}$ was arbitrary. ∎

The following lemma shows that as in the case of integral configurations with
non-trivial annihilators, also the vector presentation of a perfect coloring
has a special annihilator which is a product of difference polynomials. By
congruence of two polynomials with integer matrices as coefficients (mod $p$)
we mean that their corresponding coefficients are congruent (mod $p$) and by
congruence of two integer matrices (mod $p$) we mean that their corresponding
components are congruent (mod $p$).

######  Lemma 15.

Let $c$ be the vector presentation of a $D$-perfect coloring over an alphabet
of size $n$ with matrix $\mathbf{B}=(b_{ij})_{n\times n}$. Then $c$ is
annihilated by the polynomial

$g(X)=(\mathbf{I}X^{\mathbf{v}_{1}}-\mathbf{I})\cdots(\mathbf{I}X^{\mathbf{v}_{m}}-\mathbf{I})$

for some vectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{m}$.

###### Proof.

By Lemma 14 the power series $c$ is annihilated by $f(X)=\sum_{\mathbf{u}\in
D}\mathbf{I}X^{-\mathbf{u}}-\mathbf{B}$. Let $p$ be a prime larger than
$nc_{\text{max}}$ where $c_{\text{max}}$ is the maximum absolute value of the
components of the coefficients of $c$. Since the coefficients of $f$ commute
with each other, we have for any positive integer $k$ using the binomial
theorem that

$f^{p^{k}}=f^{p^{k}}(X)\equiv\sum_{\mathbf{u}\in
D}\mathbf{I}X^{-p^{k}\mathbf{u}}-\mathbf{B}^{p^{k}}\ \ (\text{mod }p).$

We have $f^{p^{k}}(X)c(X)\equiv 0\ \ (\text{mod }p)$. There are only finitely
many distinct matrices $\mathbf{B}^{p^{k}}\ \ (\text{mod }p)$. So, let $k$ and
$k^{\prime}$ be distinct and such that
$\mathbf{B}^{p^{k}}\equiv\mathbf{B}^{p^{k^{\prime}}}\ \ (\text{mod }p)$. Then
the coefficients of $f^{\prime}=f^{p^{k}}-f^{p^{k^{\prime}}}\ \ (\text{mod
}p)$ are among $\mathbf{I}$ and $-\mathbf{I}$. Since $f^{p^{k}}c\equiv 0\ \
(\text{mod }p)$ and $f^{p^{k^{\prime}}}c\equiv 0\ \ (\text{mod }p)$, also

$f^{\prime}c\equiv 0\ \ (\text{mod }p).$

The components of the configuration $f^{\prime}c$ are bounded in absolute
value by $nc_{\text{max}}$. Since we chose $p$ larger than $nc_{\text{max}}$,
this implies that

$f^{\prime}c=0.$

Because $f^{\prime}=\sum_{\mathbf{u}\in
P_{1}}\mathbf{I}X^{\mathbf{u}}-\sum_{\mathbf{u}\in
P_{2}}\mathbf{I}X^{\mathbf{u}}$ for some finite subsets $P_{1}$ and $P_{2}$ of
$\Z^{d}$, the annihilation of $c$ by $f^{\prime}$ is equivalent to the
annihilation of every layer of $c$ by $f^{\prime\prime}=\sum_{\mathbf{u}\in
P_{1}}X^{\mathbf{u}}-\sum_{\mathbf{u}\in P_{2}}X^{\mathbf{u}}$. Thus, every
layer of $c$ has a non-trivial annihilator and hence by Theorem 1 every layer
of $c$ has a special annihilator which is a product of difference polynomials.
Let

$g^{\prime}=(X^{\mathbf{v}_{1}}-1)\cdots(X^{\mathbf{v}_{m}}-1)$

be the product of all these special annihilators. Since $g^{\prime}$
annihilates every layer of $c$, the polynomial

$g=(\mathbf{I}X^{\mathbf{v}_{1}}-\mathbf{I})\cdots(\mathbf{I}X^{\mathbf{v}_{m}}-\mathbf{I})$

annihilates $c$. ∎

######  Lemma 16.

Let $p$ be a prime and let $H$ be an additive CA over $\Z_{p}^{n}$ determined
by a polynomial
$h=\sum_{i=0}^{k}\mathbf{A}_{i}X^{\mathbf{u}_{i}}\in\Z_{p}^{n\times n}[X^{\pm
1}]$ whose coefficients $\mathbf{A}_{i}$ commute with each other. Assume that
there exist $M\in\Z_{p}\setminus\\{0\\}$ and matrices
$\mathbf{C}_{0},\ldots,\mathbf{C}_{k}$ that commute with each other and with
every $\mathbf{A}_{i}$ such that

$\mathbf{C}_{0}\mathbf{A}_{0}+\ldots+\mathbf{C}_{k}\mathbf{A}_{k}=M\cdot\mathbf{I}$

holds in $\Z_{p}^{k\times k}$. Then $H$ is surjective.

###### Proof.

Assume the contrary that $H$ is not surjective. By the Garden-of-Eden theorem
$H$ is not pre-injective and hence there exist two distinct asymptotic
configurations $c_{1}$ and $c_{2}$ such that $H(c_{1})=H(c_{2})$, that is,
$h(X)c_{1}(X)=h(X)c_{2}(X)$. Thus, $h$ is an annihilator of $e=c_{1}-c_{2}$.
Without loss of generality we may assume that $c_{1}(\mathbf{0})\neq
c_{2}(\mathbf{0})$, i.e., that $e(\mathbf{0})=\mathbf{v}\neq\mathbf{0}$. Let
$l$ be such that the support $\text{\rm supp}(e)=\\{\mathbf{u}\in\Z^{d}\mid
e(\mathbf{u})\neq\mathbf{0}\\}$ of $e$ is contained in a $d$-dimensional
$p^{l}\times\ldots\times p^{l}$ hypercube. Note that in $\Z_{p}^{k\times k}$
we have

$f^{p^{l}}=\sum_{i=0}^{k}\mathbf{A}_{i}^{p^{l}}X^{p^{l}\mathbf{u}_{i}}$

which is also an annihilator of $e$. Hence, by the choice of $l$ we have
$\mathbf{A}_{i}^{p^{l}}\mathbf{v}=\mathbf{0}$ for all $i\in\\{1,\ldots,k\\}$.
By raising the identity

$\mathbf{C}_{0}\mathbf{A}_{0}+\ldots+\mathbf{C}_{k}\mathbf{A}_{k}=M\cdot\mathbf{I}$

to power $p^{l}$ and multiplying the result by the vector $\mathbf{v}$ from
the right we get

$M^{p^{l}}\cdot\mathbf{v}=\mathbf{C}_{0}^{p^{l}}\mathbf{A}_{0}^{p^{l}}\mathbf{v}+\ldots+\mathbf{C}_{k}^{p^{l}}\mathbf{A}_{k}^{p^{l}}\mathbf{v}=\mathbf{0}+\ldots+\mathbf{0}=\mathbf{0}.$

However, this is a contradiction because $M^{p^{l}}\mathbf{v}\neq\mathbf{0}$.
Thus, $H$ must be surjective as claimed. ∎

######  Theorem 17.

Let $D\subseteq\Z^{2}$ be a finite shape and assume that there exists an
integer $t_{0}$ such that the polynomial $f_{D}-t=\sum_{\mathbf{u}\in
D}X^{-\mathbf{u}}-t$ has no line polynomial factors whenever $t\neq t_{0}$.
Then any $D$-perfect coloring with matrix $\mathbf{B}$ is two-periodic
whenever $\det(\mathbf{B}-t_{0}\mathbf{I})\neq 0$. If $f_{D}-t$ has no line
polynomial factors for any $t$, then every $D$-perfect coloring is two-
periodic.

###### Proof.

Let $c$ be the vector presentation of a $D$-perfect coloring with matrix
$\mathbf{B}$. By Lemmas 14 and 15 it has two distinct annihilators:
$f=\sum_{\mathbf{u}\in D}\mathbf{I}X^{-\mathbf{u}}-\mathbf{B}$ and
$g=(\mathbf{I}X^{\mathbf{v}_{1}}-\mathbf{I})\cdots(\mathbf{I}X^{\mathbf{v}_{m}}-\mathbf{I})$.
Let us replace $\mathbf{I}$ by 1 and $\mathbf{B}$ by a variable $t$ and
consider the corresponding integral polynomials
$f^{\prime}=\sum_{\mathbf{u}\in D}X^{-\mathbf{u}}-t=f_{D}-t$ and
$g^{\prime}=(X^{\mathbf{v}_{1}}-1)\cdots(X^{\mathbf{v}_{m}}-1)$ in
$\C[x,y,t]$. Here $X=(x,y)$.

Without loss of generality we may assume that $f^{\prime}$ and $g^{\prime}$
are proper polynomials. Indeed, we can multiply $f^{\prime}$ and $g^{\prime}$
by monomials such that the obtained polynomials $f^{\prime\prime}$ and
$g^{\prime\prime}$ are proper polynomials and that they have a common factor
if and only if $f^{\prime}$ and $g^{\prime}$ have a common factor. So, we may
consider $f^{\prime\prime}$ and $g^{\prime\prime}$ instead of $f^{\prime}$ and
$g^{\prime}$ if they are not proper polynomials.

We consider the $y$-resultant $\text{\rm Res}_{y}(f^{\prime},g^{\prime})$ of
$f^{\prime}$ and $g^{\prime}$, and write

$\text{\rm
Res}_{y}(f^{\prime},g^{\prime})=f_{0}(t)+f_{1}(t)x+\ldots+f_{k}(t)x^{k}.$

By the properties of resultants $\text{\rm Res}_{y}(f^{\prime},g^{\prime})$ is
in the ideal generated by $f^{\prime}$ and $g^{\prime}$, and it can be the
zero polynomial only if $f^{\prime}$ and $g^{\prime}$ have a common factor.
Since $g^{\prime}$ is a product of line polynomials, any common factor of
$f^{\prime}$ and $g^{\prime}$ is also a product of line polynomials. In
particular, if $f^{\prime}$ and $g^{\prime}$ have a common factor, then they
have a common line polynomial factor. However, by the assumption $f^{\prime}$
has no line polynomial factors if $t\neq t_{0}$. Thus, $f^{\prime}$ and
$g^{\prime}$ may have a common factor only if $t=t_{0}$ and hence $\text{\rm
Res}_{y}(f^{\prime},g^{\prime})$ can be zero only if $t=t_{0}$. On the other
hand, $\text{\rm Res}_{y}(f^{\prime},g^{\prime})=0$ if and only if
$f_{0}(t)=\ldots=f_{k}(t)=0$. We conclude that
$\gcd(f_{0}(t),\ldots,f_{k}(t))=(t-t_{0})^{m}$ for some $m\geq 0$. Thus,

$\text{\rm
Res}_{y}(f^{\prime},g^{\prime})=(t-t_{0})^{m}(f^{\prime}_{0}(t)+f^{\prime}_{1}(t)x+\ldots+f^{\prime}_{k}(t)x^{k})$

where the polynomials $f^{\prime}_{0}(t),\ldots,f^{\prime}_{k}(t)$ have no
common factors.

By the Euclidean algorithm there are polynomials $a_{0}(t),\ldots,a_{k}(t)$
such that

$a_{0}(t)f_{0}^{\prime}(t)+\ldots+a_{k}(t)f_{k}^{\prime}(t)=1.$ (1)

Moreover, the coefficients of the polynomials $a_{0}(t),\ldots,a_{k}(t)$ are
rational numbers because the polynomials
$f^{\prime}_{0}(t),\ldots,f^{\prime}_{k}(t)$ are integral. Note that if
$f^{\prime}$ has no line polynomial factors for any $t$, then $m=0$ and hence
$f_{i}^{\prime}(t)=f_{i}(t)$ for every $i\in\\{1,\ldots,k\\}$.

Let us now consider the polynomial

$(\mathbf{B}-t_{0}\mathbf{I})^{m}(f_{0}^{\prime}(\mathbf{B})+f_{1}^{\prime}(\mathbf{B})x+\ldots+f^{\prime}_{k}(\mathbf{B})x^{k})$

which is obtained from $\text{\rm Res}_{y}(f^{\prime},g^{\prime})$ by plugging
back $\mathbf{I}$ and $\mathbf{B}$ in the place of $1$ and $t$, respectively.
Since $\text{\rm Res}_{y}(f^{\prime},g^{\prime})$ is in the ideal generated by
$f^{\prime}$ and $g^{\prime}$, the above polynomial is in the ideal generated
by $f$ and $g$. Thus, it is an annihilator of $c$ because both $f$ and $g$ are
annihilators of $c$.

Assume that $\det(\mathbf{B}-t_{0}\mathbf{I})\neq 0$ or that $m=0$. Now also

$h=f_{0}^{\prime}(\mathbf{B})+f_{1}^{\prime}(\mathbf{B})x+\ldots+f^{\prime}_{k}(\mathbf{B})x^{k}$

is an annihilator of $c$. Since $f^{\prime}_{0}(t),\ldots,f^{\prime}_{k}(t)$
have no common factors, $h$ is non-zero, because otherwise it would be
$f_{0}^{\prime}(\mathbf{B})=\ldots=f_{k}^{\prime}(\mathbf{B})=0$ and the
minimal polynomial of $\mathbf{B}$ would be a common factor of
$f^{\prime}_{0}(t),\ldots,f^{\prime}_{k}(t)$, a contradiction.

Plugging $t=\mathbf{B}$ to Equation 1 we get

$a_{0}(\mathbf{B})f_{0}^{\prime}(\mathbf{B})+\ldots+a_{k}(\mathbf{B})f_{k}^{\prime}(\mathbf{B})=\mathbf{I}.$

Let us multiply the above equation by a common multiple $M$ of all the
denominators of the rational numbers appearing in the equation and let us
consider it (mod $p$) where $p$ is a prime that does not divide $M$. We obtain
the following identity

$a_{0}^{\prime}(\mathbf{B})f_{0}^{\prime}(\mathbf{B})+\ldots+a_{k}^{\prime}(\mathbf{B})f_{k}^{\prime}(\mathbf{B})=M\cdot\mathbf{I}\not\equiv
0\ \ (\text{mod }p)$

where all the coefficients in the equation are integer matrices.

By Lemma 16 the additive CA determined by
$h=\sum_{i=0}^{k}f_{i}^{\prime}(\mathbf{B})x^{i}$ is surjective. Since $h$ is
a polynomial in variable $x$ only, it defines a 1-dimensional CA $H$ which is
surjective and which maps every horizontal fiber of $c$ to 0. Hence, every
horizontal fiber of $c$ is a pre-image of 0. Let $c^{\prime}$ be a horizontal
fiber of $c$. The Garden-of-Eden theorem implies that $0$ has finitely many,
say $N$, pre-images under $H$. Since also every translation of $c^{\prime}$ is
a pre-image of $0$, we conclude that $c^{\prime}=\tau^{i}(c^{\prime})$ for
some $i\in\\{0,\ldots,N-1\\}$. Thus, $(N-1)!$ is a common period of all the
horizontal fibers of $c$ and hence $c$ is horizontally periodic.

Repeating the same argumentation for the $x$-resultant of $f^{\prime}$ and
$g^{\prime}$ we can show that $c$ is also vertically periodic. Thus, $c$ is
two-periodic. ∎

As corollaries of the above theorem and theorems from the previous section, we
obtain new proofs for forced periodicity of perfect colorings in the square
and the triangular grids, and a new result for forced periodicity of perfect
colorings in the king grid:

######  Corollary 18 ([29]).

Let $D$ be the relative 1-neighborhood of the square grid. Then any
$D$-perfect coloring with matrix $\mathbf{B}$ is two-periodic whenever
$\det(\mathbf{B}-\mathbf{I})\neq 0$. In other words, any $1$-perfect coloring
with matrix $\mathbf{B}$ in the square grid is two-periodic whenever
$\det(\mathbf{B}-\mathbf{I})\neq 0$.

###### Proof.

In our proof of Theorem 7 it was shown that the polynomial $f_{D}-t$ has no
line polynomial factors if $t\neq 1$. Thus, by Theorem 17 any
$(D,\mathbf{B})$-coloring is two-periodic whenever
$\det(\mathbf{B}-\mathbf{I})\neq 0$. ∎

######  Corollary 19 ([29]).

Let $D$ be the relative 1-neighborhood of the triangular grid. Then any
$D$-perfect coloring with matrix $\mathbf{B}$ is two-periodic whenever
$\det(\mathbf{B}+\mathbf{I})\neq 0$. In other words, any $1$-perfect coloring
with matrix $\mathbf{B}$ in the triangular grid is two-periodic whenever
$\det(\mathbf{B}+\mathbf{I})\neq 0$.

###### Proof.

In the proof of Theorem 10 it was shown that the polynomial $f_{D}-t$ has no
line polynomial factors if $t\neq-1$. Thus, by Theorem 17 any
$(D,\mathbf{B})$-coloring is two-periodic whenever
$\det(\mathbf{B}+\mathbf{I})\neq 0$. ∎

######  Corollary 20 ([29]).

Let $r\geq 2$ and let $D$ be the relative $r$-neighborhood of the square grid.
Then every $D$-perfect coloring is two-periodic. In other words, any
$r$-perfect coloring in the square grid is two-periodic for all $r\geq 2$.

###### Proof.

In the proof of Theorem 9 it was shown that the polynomial $f_{D}-t$ has no
line polynomial factors for any $t$. Thus, by Theorem 17 every $D$-perfect
coloring is two-periodic. ∎

######  Corollary 21 ([29]).

Let $r\geq 2$ and let $D$ be the relative $r$-neighborhood of the triangular
grid. Then every $D$-perfect coloring is two-periodic. In other words, any
$r$-perfect coloring in the triangular grid is two-periodic for all $r\geq 2$.

###### Proof.

In the proof of Theorem 11 it was shown that the polynomial $f_{D}-t$ has no
line polynomial factors for any $t$. Thus, by Theorem 17 every $D$-perfect
coloring is two-periodic. ∎

######  Corollary 22.

Let $r\geq 1$ and let $D$ be the relative $r$-neighborhood of the king grid.
Then every $D$-perfect coloring with matrix $\mathbf{B}$ is two-periodic
whenever $\det(\mathbf{B})\neq 0$. In other words, every $r$-perfect coloring
with matrix $\mathbf{B}$ in the king grid is two-periodic whenever
$\det(\mathbf{B})\neq 0$.

###### Proof.

In the proof of Theorem 12 we showed that the polynomial $f_{D}-t$ has no line
polynomial factors if $t\neq 0$. Thus, by Theorem 17 any
$(D,\mathbf{B})$-coloring is two-periodic whenever $\det(\mathbf{B})\neq 0$. ∎

_Remark._ Note that the results in Corollaries 18, 19, 20 and 21 were stated
and proved in [29] in a slightly more general form. Indeed, in [29] it was
proved that if a configuration $c\in\mathcal{A}^{\Z^{2}}$ is annihilated by

$\sum_{\mathbf{u}\in D}\mathbf{I}X^{-\mathbf{u}}-\mathbf{B}$

where $\mathbf{B}\in\Z^{n\times n}$ is an arbitrary integer matrix whose
determinant satisfies the conditions in the four corollaries and $D$ is as in
the corollaries, then $c$ is necessarily periodic. This kind of configuration
was called a _generalized centered function_. However, in Lemma 14 we proved
that the vector presentation of any $D$-perfect coloring with matrix
$\mathbf{B}$ is annihilated by this polynomial, that is, we proved that the
vector presentation of a perfect coloring is a generalized centered function.
By analyzing the proof of Theorem 17 we see that the theorem holds also for
generalized centered functions and hence the corollaries following it hold
also for generalized centered functions, and thus we have the same results as
in [29].

##  7 Forced periodicity of configurations of low abelian complexity

In this section we prove a statement concerning forced periodicity of two-
dimensional configurations of low abelian complexity which generalizes a
result in [7]. In fact, as in [7] we generalize the definition of abelian
complexity from finite patterns to polynomials and prove a statement of forced
periodicity under this more general definition of abelian complexity.

Let $c\in\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{n}\\}^{\Z^{d}}$ and let
$D\subseteq\Z^{d}$ be a finite shape. Consider the polynomial
$f=\mathbf{I}\cdot f_{D}(X)=\sum_{\mathbf{u}\in
D}\mathbf{I}X^{-\mathbf{u}}\in\Z^{n\times n}[X^{\pm 1}]$. The $i$th
coefficient of $(fc)_{\mathbf{v}}=\sum_{\mathbf{u}\in
D}\mathbf{I}\cdot\mathbf{c_{\mathbf{v}+\mathbf{u}}}$ tells the number of cells
of color $\mathbf{e}_{i}$ in the $D$-neighborhood of $\mathbf{v}$ in $c$ and
hence the abelian complexity of $c$ with respect to $D$ is exactly the number
of distinct coefficients of $fc$.

More generally, we define the abelian complexity $A(c,f)$ of an integral
vector configuration $c\in\mathcal{A}^{\Z^{d}}$ where $\mathcal{A}$ is finite
set of integer vectors _with respect to a polynomial $f\in\Z^{n\times
n}[X^{\pm 1}]$_ as

$A(c,f)=|\\{(fc)_{\mathbf{v}}\mid\mathbf{v}\in\Z^{d}\\}|.$

This definition can be extended to integral configurations and polynomials.
Indeed, we define the abelian complexity $A(c,f)$ of a configuration
$c\in\mathcal{A}^{\Z^{d}}$ where $\mathcal{A}\subseteq\Z$ with respect to a
polynomial $f=\sum f_{i}X^{\mathbf{u}_{i}}\in\Z[X^{\pm 1}]$ to be the abelian
complexity $A(c^{\prime},f^{\prime})$ of the vector presentation $c^{\prime}$
of $c$ with respect to the polynomial $f^{\prime}=\mathbf{I}\cdot f=\sum
f_{i}\cdot\mathbf{I}\cdot X^{\mathbf{u}_{i}}$. Consequently, we say that $c$
has low abelian complexity with respect to a polynomial $f$ if $A(c,f)=1$.
Clearly this definition is consistent with the definition of low abelian
complexity of a configuration with respect to a finite shape since if $c$ is
an integral configuration, then $A(c,D)=1$ if and only if $A(c,f_{D})=1$, and
if $c$ is an integral vector configuration, then $A(c,D)=1$ if and only if
$A(c,\mathbf{I}\cdot f_{D})=1$.

We study forced periodicity of two-dimensional configurations of low abelian
complexity. Note that a configuration of low abelian complexity is not
necessarily periodic. Indeed, in [30] it was shown that there exist non-
periodic two-dimensional configurations that have abelian complexity
$A(c,D)=1$ for some finite shape $D$. However, in [7] it was shown that if
$A(c,f)=1$ and if the polynomial $f$ has no line polynomial factors, then $c$
is two-periodic assuming that the support of $f$ is convex. The following
theorem strengthens this result and shows that the convexity assumption of the
support of the polynomial is not needed. We obtain this result as a corollary
of Theorem 2.

######  Theorem 23.

Let $c$ be a two-dimensional integral configuration over an alphabet of size
$n$ and assume that it has low abelian complexity with respect to a polynomial
$f\in\Z[x^{\pm 1},y^{\pm 1}]$. If $f$ has no line polynomial factors, then $c$
is two-periodic. If $f$ has line polynomial factors in a unique primitive
direction $\mathbf{v}$, then $c$ is $\mathbf{v}$-periodic. Thus, if $f_{D}$
has no line polynomial factors or its line polynomial factors are in a unique
primitive direction, then any configuration that has low abelian complexity
with respect to $D$ is two-periodic or periodic, respectively.

###### Proof.

By the assumption that $A(c,f)=1$ we have
$f^{\prime}c^{\prime}=\mathbf{c}_{0}\mathbbm{1}$ for some
$\mathbf{c}_{0}\in\Z^{n}$ where $c^{\prime}$ is the vector presentation of $c$
and $f^{\prime}=\mathbf{I}\cdot f$. Thus, $f$ periodizes every layer of
$c^{\prime}$. If $f$ has no line polynomial factors, then by Theorem 2 every
layer of $c^{\prime}$ is two-periodic and hence $c^{\prime}$ is two-periodic.
If $f$ has line polynomial factors in a unique primitive direction
$\mathbf{v}$, then by Theorem 2 every layer of $c^{\prime}$ is
$\mathbf{v}$-periodic and hence also $c^{\prime}$ is $\mathbf{v}$-periodic.
Since $c$ is periodic if and only if its vector presentation $c^{\prime}$ is
periodic, the claim follows. ∎

_Remark._ In [7] a polynomial $f\in\Z[X^{\pm 1}]$ is called abelian rigid if
an integral configuration $c$ having low abelian complexity with respect to
$f$ implies that $c$ is strongly periodic. In the above theorem we proved that
if a polynomial $f\in\Z[x^{\pm 1},y^{\pm 1}]$ has no line polynomial factors
then it is abelian rigid. Also, the converse holds as proved in [7], that is,
if a polynomial $f\in\Z[x^{\pm 1},y^{\pm 1}]$ has a line polynomial factor
then it is not abelian rigid. This means that if $f$ has a line polynomial
factor then there exists a configuration which is not two-periodic but has low
abelian complexity with respect to $f$. In fact this direction holds for all
$d$, not just for $d=2$ as reported in [7].

In the following example we introduce an open problem related to
configurations of low abelian complexity.

######  Example 24 (Periodic tiling problem).

This example concerns _translational tilings_ by a single tile. In this
context by a tile we mean any finite subset $F\subseteq\Z^{d}$ and by a tiling
by the tile $F$ we mean such subset $C\subseteq\Z^{d}$ that every point of the
grid $\Z^{d}$ has a unique presentation as a sum of an element of $F$ and an
element of $C$. Presenting the tiling $C$ as its indicator function we obtain
a $d$-dimensional binary configuration $c\in\\{0,1\\}^{\Z^{d}}$ defined by

$c_{\mathbf{u}}=\begin{cases}1,\text{ if }\mathbf{u}\in C\\\ 0,\text{ if
}\mathbf{u}\not\in C\end{cases}.$

The configuration $c$ has exactly $|F|$ different patterns of shape $-F$,
namely the patterns with exactly one symbol 1. In other words, it has low
complexity with respect to $-F$. Let $f=f_{F}=\sum_{\mathbf{u}\in
F}X^{-\mathbf{u}}$ be the characteristic polynomial of $F$. Since $C$ is a
tiling by $F$, we have $fc=\mathbbm{1}$. In fact, $c$ has low abelian
complexity with respect to $f$ and $-F$. Thus, by Theorem 23 any tiling by
$F\subset\Z^{2}$ is two-periodic if $f_{F}$ has no line polynomial factors.

The periodic tiling problem claims that if there exists a tiling by a tile
$F\subseteq\Z^{d}$, then there exists also a periodic tiling by $F$ [20, 31].
By a simple pigeonholing argument it can be seen that in dimension $d=1$ all
translational tilings by a single tile are periodic and hence the periodic
tiling problem holds in dimension 1 [26]. For $d\geq 2$ the conjecture is much
trickier and only recently it was proved by Bhattacharya that it holds for
$d=2$ [3]. In [9] it was presented a slightly different proof in the case
$d=2$ with some generalizations. For $d\geq 3$ the conjecture is still partly
open. However, very recently it has been proved that for some sufficiently
large $d$ the periodic tiling conjecture is false [10].

##  8 Algorithmic aspects

All configurations in a subshift are periodic, in particular, if there are no
configurations in the subshift at all! It is useful to be able to detect such
trivial cases.

The set

$\mathcal{S}(D,b,a)=\\{c\in\\{0,1\\}^{\Z^{2}}\mid(f_{D}-(b-a))c=a\mathbbm{1}(X)\\}$

of all $(D,b,a)$-coverings is an SFT for any given finite shape $D$ and non-
negative integers $b$ and $a$. Hence, the question whether there exist any
$(D,b,a)$-coverings for a given neighborhood $D$ and covering constants $b$
and $a$ is equivalent to the question whether the SFT $\mathcal{S}(D,b,a)$ is
non-empty. The question of emptiness of a given SFT is undecidable in general,
but if the SFT is known to be not aperiodic, then the problem becomes
decidable as a classic argumentation by Hao Wang shows:

######  Lemma 25 ([32]).

If an SFT is either the empty set or it contains a strongly periodic
configuration, then its emptiness problem is decidable, that is, there is an
algorithm to determine whether there exist any configurations in the SFT.

In particular, if $g=f_{D}-(b-a)$ has line polynomial factors in at most one
direction, then the question whether there exist any $(D,b,a)$-coverings is
decidable:

######  Theorem 26.

Let a finite $D\subseteq\Z^{2}$ and non-negative integers $b$ and $a$ be given
such that the polynomial $g=f_{D}-(b-a)\in\Z[x^{\pm 1},y^{\pm 1}]$ has line
polynomial factors in at most one primitive direction. Then there exists an
algorithm to determine whether there exist any $(D,b,a)$-coverings.

###### Proof.

Let $\mathcal{S}=\mathcal{S}(D,b,a)$ be the SFT of all $(D,b,a)$-coverings.
Since $g$ has line polynomial factors in at most one primitive direction, by
Theorem 2 every element of $\mathcal{S}$ is periodic. Any two-dimensional SFT
that contains periodic configurations contains also two-periodic
configurations. Thus, $\mathcal{S}$ is either empty or contains a two-periodic
configuration and hence by Lemma 25 there is an algorithm to determine whether
$\mathcal{S}$ is non-empty. ∎

One may also want to design a perfect $(D,b,a)$-covering for given $D$, $b$
and $a$. This can be effectively done under the assumptions of Theorem 26: As
we have seen, if $\mathcal{S}=\mathcal{S}(D,b,a)$ is non-empty, it contains a
two-periodic configuration. For any two-periodic configuration $c$ it is easy
to check if $c$ contains a forbidden pattern. By enumerating two-periodic
configurations one-by-one one is guaranteed to find eventually one that is in
$\mathcal{S}$.

If the polynomial $g$ has no line polynomial factors, then the following
stronger result holds:

######  Theorem 27.

If the polynomial $g=f_{D}-(b-a)$ has no line polynomial factors for given
finite shape $D\subseteq\Z^{2}$ and non-negative integers $b$ and $a$, then
the SFT $\mathcal{S}=\mathcal{S}(D,b,a)$ is finite. One can then effectively
construct all the finitely many elements of $\mathcal{S}$.

The proof of the first part of above theorem relies on the fact that a two-
dimensional subshift is finite if and only if it contains only two-periodic
configurations [2]. If $g$ has no line polynomial factors, then every
configuration it periodizes (including every configuration in $\mathcal{S}$)
is two-periodic by Theorem 2, and hence $\mathcal{S}$ is finite. The second
part of the theorem, i.e., the fact that one can effectively produce all the
finitely many elements of $\mathcal{S}$ holds generally for finite SFTs in any
dimension:

######  Lemma 28.

Given a finite $F\subseteq\mathcal{A}^{*}$ such that $X_{F}$ is finite, one
can effectively construct the elements of $X_{F}$.

###### Proof.

Given a finite $F\subseteq\mathcal{A}^{*}$ and a pattern
$p\in\mathcal{A}^{D}$, assuming that strongly periodic configurations are
dense in $X_{F}$, one can effectively check whether $p\in\mathcal{L}(X_{F})$.
Indeed, we have a semi-algorithm for the positive instances that guesses a
strongly periodic configuration $c$ and verifies that $c\in X_{F}$ and
$p\in\mathcal{L}(c)$. A semi-algorithm for the negative instances exists for
any SFT $X_{F}$ and is a standard compactness argument: guess a finite
$E\subseteq\Z^{d}$ such that $D\subseteq E$ and verify that every
$q\in\mathcal{A}^{E}$ such that $q|_{D}=p$ contains a forbidden subpattern.

Consequently, given finite $F,G\subseteq\mathcal{A}^{*}$, assuming that
strongly periodic configurations are dense in $X_{F}$ and $X_{G}$, one can
effectively determine whether $X_{F}=X_{G}$. Indeed, $X_{F}\subseteq X_{G}$ if
and only if no $p\in G$ is in $\mathcal{L}(X_{F})$, a condition that we have
shown above to be decidable. Analogously we can test $X_{G}\subseteq X_{F}$.

Finally, let a finite $F\subseteq\mathcal{A}^{*}$ be given such that $X_{F}$
is known to be finite. All elements of $X_{F}$ are strongly periodic so that
strongly periodic configurations are certainly dense in $X_{F}$. One can
effectively enumerate all finite sets $P$ of strongly periodic configurations.
For each $P$ that is translation invariant (and hence a finite SFT) one can
construct a finite set $G\subseteq\mathcal{A}^{*}$ of forbidden patterns such
that $X_{G}=P$. As shown above, there is an algorithm to test whether
$X_{F}=X_{G}=P$. Since $X_{F}$ is finite, a set $P$ is eventually found such
that $X_{F}=P$. ∎

Let us now turn to the more general question of existence of perfect colorings
over alphabets of arbitrary size. Let $D\subseteq\Z^{2}$ be a finite shape and
let $\mathbf{B}$ be an $n\times n$ integer matrix. To determine whether there
exist any $(D,\mathbf{B})$-colorings is equivalent to asking whether the SFT

$\mathcal{S}(D,\mathbf{B})=\\{c\in\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{n}\\}^{\Z^{2}}\mid
gc=0\\}$

is non-empty where $g=\sum_{\mathbf{u}\in
D}\mathbf{I}X^{-\mathbf{u}}-\mathbf{B}$ since it is exactly the set of the
vector presentations of all $(D,\mathbf{B})$-colorings.

######  Theorem 29.

Let a finite shape $D\subseteq\Z^{2}$, a non-negative integer matrix
$\mathbf{B}$ and an integer $t_{0}$ be given such that the polynomial
$f_{D}(x,y)-t\in\Z[x^{\pm 1},y^{\pm 1}]$ has no line polynomial factors
whenever $t\neq t_{0}$ and $\det(\mathbf{B}-t_{0}\mathbf{I})\neq 0$. Then
there are only finitely many $(D,\mathbf{B})$-colorings and one can
effectively construct them. In particular, there is an algorithm to determine
whether there exist any $(D,\mathbf{B})$-colorings.

###### Proof.

Let $\mathcal{S}=\mathcal{S}(D,\mathbf{B})$ be the SFT of the vector
presentations of all $(D,\mathbf{B})$-colorings. By Theorem 17 all elements of
$\mathcal{S}$ are two-periodic. Hence, $\mathcal{S}$ is finite, and the claim
follows by Lemma 28. ∎

Corollaries 18, 19, 20, 21 and 22 together with above theorem yield the
following corollary.

######  Corollary 30.

The following decision problems are decidable for a given matrix $\mathbf{B}$
satisfying the given conditions.

  * •

The existence of $(D,\mathbf{B})$-colorings where $D$ is the relative
1-neighborhood of the square grid and $\det(\mathbf{B}-\mathbf{I})\neq 0$.

  * •

The existence of $(D,\mathbf{B})$-colorings where $D$ is the relative
1-neighborhood of the triangular grid and $\det(\mathbf{B}+\mathbf{I})\neq 0$.

  * •

The existence of $(D,\mathbf{B})$-colorings where $D$ is the relative
$r$-neighborhood of the square grid and $\mathbf{B}$ is arbitrary.

  * •

The existence of $(D,\mathbf{B})$-colorings where $D$ is the relative
$r$-neighborhood of the triangular grid and $\mathbf{B}$ is arbitrary.

  * •

The existence of $(D,\mathbf{B})$-colorings where $D$ is the relative
$r$-neighborhood of the king grid and $\det(\mathbf{B})\neq 0$.

######  Theorem 31.

Given a polynomial $f$ in two variables with line polynomial factors in at
most one parallel direction there is an algorithm to determine whether there
exist any two-dimensional configurations over an alphabet of size $n$ that
have low abelian complexity with respect to $f$. In fact, there are only
finitely many such configurations and one can effectively construct all of
them.

###### Proof.

The set
$\\{c\in\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{n}\\}^{\Z^{2}}\mid\mathbf{I}fc=0\\}$
of the vector presentations of all configurations over an alphabet of size $n$
with low abelian complexity with respect to $f$ is an SFT. By Theorem 23 it
contains only two-periodic configurations and hence it is finite. Thus, by
Lemma 28 we have the claim. ∎

##  9 Conclusions

We studied two-dimensional perfect colorings and proved a general condition
(Theorem 17) for their forced periodicity using an algebraic approach to
multidimensional symbolic dynamics. As corollaries of this theorem we obtained
new proofs for known results of forced periodicity in the square and the
triangular grid and a new result in the king grid. Moreover, we generalized a
statement of forced periodicity of two-dimensional configurations of low
abelian complexity. Also, some observations of algorithmic decidability were
made in the context of forced periodicity.

All our results of forced periodicity of perfect colorings used Theorem 2 and
hence concerned only two-dimensional configurations. However, a
$d$-dimensional version of Theorem 2 exists [15], and so we wonder whether an
analogous result to Theorem 17 exists that would give a sufficient condition
for forced periodicity of $d$-dimensional perfect colorings for arbitrary
dimension $d$. Note that clearly every one-dimensional perfect coloring is
necessarily periodic.

## References

##

  * [1] M. A. Axenovich.  On multiple coverings of the infinite rectangular grid with balls of constant radius.  Discrete Mathematics, 268(1):31 – 48, 2003.
  * [2] A. Ballier, B. Durand, and E. Jeandal.  Structural aspects of tilings.  In Susanne Albers and Pascal Weil, editors, 25th International Symposium on Theoretical Aspects of Computer Science, volume 1 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61–72, Dagstuhl, Germany, 2008. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [3] S. Bhattacharya.  Periodicity and decidability of tilings of $\mathbb{Z}^{2}$.  American Journal of Mathematics, 142, 02 2016.
  * [4] T. Ceccherini-Silberstein and M. Coornaert.  Cellular Automata and Groups.  Springer Monographs in Mathematics. Springer Berlin Heidelberg, 2010.
  * [5] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein.  Covering Codes.  Elsevier, 1997.
  * [6] D. A. Cox, J. Little, and D. O’Shea.  Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra.  Springer, 2015.
  * [7] N. Geravker and S. A. Puzynina.  Abelian Nivat’s conjecture for non-rectangular patterns.  arXiv:2111.04690, December 2021.
  * [8] C. Godsil.  Equitable partitions.  Paul Erdös is Eighty Vol. 1, pages 173–192, 1993.
  * [9] R. Greenfeld and T. Tao.  The structure of translational tilings in $\mathbb{Z}^{d}$.  Discrete Analysis, 2021.
  * [10] R. Greenfeld and T. Tao.  A counterexample to the periodic tiling conjecture, 2022.
  * [11] T. W. Haynes, S. Hedetniemi, and P. Slater.  Fundamentals of Domination in Graphs.  CRC Press, 1 edition, 1997.
  * [12] E. Heikkilä, P. Herva, and J. Kari.  On perfect coverings of two-dimensional grids.  In Volker Diekert and Mikhail Volkov, editors, Developments in Language Theory, pages 152–163, Cham, 2022. Springer International Publishing.
  * [13] J. Kari.  Theory of cellular automata: A survey.  Theoretical Computer Science, 334(1):3–33, 2005.
  * [14] J. Kari.  Low-complexity tilings of the plane.  In Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, volume 11612 of Lecture Notes in Computer Science, pages 35–45. Springer, 2019.
  * [15] J. Kari.  Expansivity and periodicity in algebraic subshifts.  Submitted for publication, 2022.
  * [16] J. Kari and E. Moutot.  Nivat’s conjecture and pattern complexity in algebraic subshifts.  Theoretical Computer Science, 777:379 – 386, 2019.
  * [17] J. Kari and M. Szabados.  An algebraic geometric approach to Nivat’s conjecture.  In Proceedings of ICALP 2015, part II, volume 9135 of Lecture Notes in Computer Science, pages 273–285, 2015.
  * [18] J. Kari and M. Szabados.  An algebraic geometric approach to Nivat’s conjecture.  Information and Computation, 271:104481, 2020.
  * [19] P. Kurka.  Topological and Symbolic Dynamics.  Collection SMF. Société mathématique de France, 2003.
  * [20] J. C. Lagarias and Y. Wang.  Tiling the line with translates of one tile.  Inventiones Mathematicae, 124:341–365, 1996.
  * [21] D. Lind and B. Marcus.  An Introduction to Symbolic Dynamics and Coding.  Cambridge University Press, 1995.
  * [22] M. Lothaire.  Combinatorics on Words.  Cambridge Mathematical Library. Cambridge University Press, 2 edition, 1997.
  * [23] E. F. Moore.  Machine models of self-reproduction.  1962\.
  * [24] M. Morse and G. A. Hedlund.  Symbolic dynamics.  American Journal of Mathematics, 60(4):815–866, 1938.
  * [25] J. R. Myhill.  The converse of Moore’s Garden-of-Eden theorem.  1963\.
  * [26] D. Newman.  Tesselation of integers.  J. Number Theory, 9(1):107–111, 1977.
  * [27] M. Nivat.  Invited talk at the 24th International Colloquium on Automata, Languages, and Programming (ICALP 1997), 1997.
  * [28] S. A. Puzynina.  Perfect colorings of radius $r>1$ of the infinite rectangular grid.  Èlektron. Mat. Izv., 5:283–292, 2008.
  * [29] S. A. Puzynina.  On periodicity of generalized two-dimensional infinite words.  Information and Computation, 207(11):1315–1328, 2009.
  * [30] S. A. Puzynina.  Aperiodic two-dimensional words of small abelian complexity.  The Electronic Journal of Combinatorics, 26(4), 2019.
  * [31] M. Szegedy.  Algorithms to tile the infinite grid with finite clusters.  Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 137–145, 1998.
  * [32] H. Wang.  Proving theorems by pattern recognition – II.  The Bell System Technical Journal, 40(1):1–41, 1961.


$100$ disjoint samples. This results in each partition being a sample of ~$2$
billion symbols for n-grams and ~$130$ million for tokens. We then calculate
the entropy for each partition and the KL divergence between the entropy of
the $0.5$, $0.50$, and $0.95$ quantile points and a uniform distribution.
These quantiles are then plotted on Fig. 9 to illustrate sampling noise—$90\%$
of sampled entropies fall within these bounds. The log scaling of Fig. 9 hides
some of the noise trends, namely that the noise grows with $n$ and that
settings like GZip and EqualInfoAC are noisier than AC and RNG. These trends
are seen in Fig. 12 where the entropy has been normalized based on the mean
entropy calculated across the partitions.

(a) N-Grams

(b) Tokens

Figure 13: Bias corrected KL divergence between the observed and uniform
distributions for different segmentations of the bitstream. This plot is
similar to Fig. 9, however, the KL divergence calculations use the entropy of
the observed distribution after applying the Miller-Madow bias correction.
After applying bias correction, we see that the expected $0$ KL divergence for
the RNG baseline is now within the 90th percentile bounds. However, this can
results in an, incorrect, negative KL divergence which is removed from the
graph. Thus the RNG 50th percentile is shown as a scatter plot rather than a
broken line. In this setting it is clear that the 50th percentile for
AC$[v\mathord{=}65\text{k}]$s above the 50th percentile for RNG, however, it
is hard to disentangle the two as their 5th percentile lines are similar.

The maximum likelihood, or plug-in, estimator of entropy,
$\hat{H}=-\sum_{x\in\mathcal{X}}\hat{p}(x)\log_{2}\hat{p}(x)$, is negatively
biased—in fact, all entropy estimators are biased [48]. The Miller-Madow
estimator attempts to correct for this bias by adding the approximate bias,
cased by sampling, to the plug-in estimator.252525There are other methods for
entropy bias correction such as [15] based on bootstrapping [20], however,
with the size of the C4 training data, the required resampling was not
possible. Thus, we use Miller-Madow in this work. The Miller-Madow estimator
is given by $\hat{H}_{MM}=\hat{H}+\frac{\hat{|V|}-1}{2m}$. In this case, $m$
is the size of the sample used to estimate entropy and $\hat{|V|}$ is the
estimated vocabulary size. In some applications, the vocabulary may often need
to be estimated—for example new words may be added to languages—but in this
case our vocabulary size is always $2^{n}$ where $n$ is the size of the
current segmentation.

When we plot the KL divergence between the Miller-Madow estimated entropy and
the uniform distribution, we see that the percentile interval for the RNG
baseline now includes $0$, the KL divergence we expect given the data was
generated from random and independent bits. As bias correction is approximate,
it is possible that, for a given sample, the correction will result in an
entropy greater than the maximum entropy possible for a given vocabulary size.
Given that KL divergence between a distribution $P$ and the uniform
distribution $U$ simplifies to the entropy of $U$ minus the entropy of $P$,
$\text{KL}(P||U)=H[U]-\hat{H}[P]=\log_{2}|V|-\hat{H}[p]$, this results in a
negative KL divergence, which is not allowed. These points get removed from
the graph during log scaling and the resulting $50\%$ percentile line for RNG
data looks strange. Therefore, we only plot points with positive KL divergence
in Fig. 13. The Miller-Madow estimation of entropy makes it clear that the
$0.5$ entropy quantile for AC compressed data is much higher than the $50\%$
percentile for RNG data. Additionally, for $n>2$, the AC entropy is
statistically significantly less than the RNG entropy; however, differences in
the mean entropy only start to appear after ~$8$ decimal places. This slight
difference in mean, coupled with the fact that the $5\%$ percentiles are
similar, means we cannot confidently assert the model will be able to easily
distinguish the AC compressed data from random data. Given that we care about
the differences between the entropy of data compressed with different
methods—which is invariant to bias—and the strange plots when values are less
than $0$, we opt to plot the plug-in estimator in Fig. 9 instead of the
Miller-Madow estimator.

##  Appendix K Analysis Implementation

Matplolib [33] and Seaborn [71] were used to make all the included graphs.

Statistical significance tests were done using Welch’s t-test [72] using the
function scipy.stats.ttest_ind_from_stats from SciPy [69]. We used $p<0.05$ as
the statistical significance threshold.

##  Appendix L Corner Cases of Tokenization lead to Unstable Mappings

There are some cases where SentencePiece does not have stable text
$\rightarrow$ token mappings when looking at various substrings. This
generally occurs when a singular and plural version of a noun are both common
enough to be tokenized into a single token. An example from the T5 vocabulary
[52] is “chair” $\rightarrow$ [3533] and “chairs” $\rightarrow$ [6406]. When
you look at the surface text substring “chair”, it seems to map to multiple
tokens, however when you look at the full surface term “chairs” the stability
returns. This is in contrast to a byte-level vocabulary where the text “chair”
always maps to [102, 107, 100, 108, 117], even as part of the text “chairs”
where an extra [118] is appended to the end. While the loss of shared
representations of clearly related concepts in unfortunate, the performance of
modern models based on this kind of tokenization shows that it is well handled
by the model. While these edge cases exist, they are rare enough that the
SentencePiece tokenizer should be considered stable.

Similarly, there are cases where the initial token $\rightarrow$ text mapping
in a EqualInfoAC window can be unstable. In the case where there is a
character whose bitstream crosses the token boundary—the purple characters in
Fig. 7—only the prefix that is part of the initial token will determine the
value of that token. It is possible that there may be other places in the
input text where the characters wholly contained within the initial token
match but the character that crosses the token boundary may be different. If
the prefix of that character’s bitstream, which is part of the initial token,
matches the previous case but of the bitstream, which is in the following
token, do not it is possible to have the same initial token while the
underlying text is different. When this happens, the text prefix is still
stable and the notion of mapping a compressed token to exact characters is not
well defined, as there are always cases there a character is spread across two
tokens. Note, this only occurs at token boundaries;
EqualInfoAC$[b\mathord{=}16,\,v\mathord{=}65\text{k}]$ is stable as no
characters cross windows. Therefore, we consider EqualInfoAC stable enough to
enable learnability by M2.

Interestingly, [40] point out this same issue, where a fixed size view of a
variable length stream can cause false equivalencies when prefixes match.
Similar to our findings, they find the models do have some limited ability to
deal with these situations.

##  Appendix M Window Text Patterns and Token Positions

We tokenize $20$ documents of length $1{,}024$ with
EqualInfoAC$[b\mathord{=}16,\,v\mathord{=}256]$ and find that all $256$
possible token values occur multiple times, both as the first and as the
second token within the window. When tokenized with
EqualInfoAC$[b\mathord{=}16,\,v\mathord{=}65\text{k}]$, $34.5\%$ of attested
tokens appear more than once. Table 16 shows all the window text for repeated
tokens.

Table 16: The deduplicated window text from all instances of tokens that appear multiple times when we tokenized $20$ documents of length $1{,}024$ ($20{,}480$ compressed tokens) with EqualInfoAC$[b\mathord{=}16,\,v\mathord{=}256]$. Token |  Window Position | Window Text
---|---|---
$185$ | $1$ | [or ] / [or a ] / [or ac] / [or al] / [or cr] / [or d] / [or f] / [or h]
|  | [or hi] / [or i] / [or k] / [or ma] / [or pr] / [or r] / [or s] / [or se]
|  | [or su] / [or t] / [or to] / [or v] / [or wha] / [or y] / [or yo] / [or, t]
|  | [or-] / [or.] / [ora] / [orc] / [orce ] / [ord] / [ord a] / [order]
|  | [ore a] / [ore e] / [ore ev] / [ore g] / [ore i]
| $2$ | [ 4] / [ of F] / [ records ] / [. Lo] / [Alt] / [OI] / [ase ] / [at y]
|  | [cian] / [cri] / [d. I] / [ery] / [h de] / [hen s] / [ides] / [n ne]
|  | [oft] / [om i] / [onte] / [opp] / [pir] / [rev] / [reve] / [s may]
|  | [tion a] / [y do] / [y t]
$151$ | $1$ | [le] / [le s] / [le t] / [le. ] / [lea] / [lec] / [led] / [led ]
|  | [led t] / [leg] / [lege] / [leh] / [lem ] / [leme] / [lems] / [len]
|  | [ler] / [les] / [less] / [let] / [lett] / [level] / [lew ] / [ley] / [lf ]
| $2$ | [ all ] / [ nut] / [ this] / [ un] / [. I w] / [Ni] / [as t] / [ceed ]
|  | [choos] / [e Mi] / [e-li] / [etti] / [imag] / [ion a] / [k a] / [ne a]
|  | [ng up] / [niversi] / [npo] / [nt pr] / [pi] / [rvices] / [s T] / [s your]
|  | [s?] / [so c] / [stag] / [thou] / [thoug] / [ust] / [ust ]