
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\def\udcs{???.?} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{??X??} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{144}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]  %Headings in Russian
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}} %Volume, pages in Russian,
                                                                                    %filled by Editorial board
     \newline
         {\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\renewcommand{\figurename}{Fig.}


\thispagestyle{empty}

\title[Completely regular codes]{Completely regular codes \\
in the $n$-Dimensional Rectangular Grid}
\author{{S.V. Avgustinovich}}%
\address{Sergey Vladimirovich Avgustinovich
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{avgust@math.nsc.ru}%

\thanks{\sc Avgustinovich, S.V.,
Completely regular codes
in the $n$-Dimensional Rectangular Grid}
\thanks{\copyright \ 2022 Avgustinovich S.V}
\thanks{\it Received  January, 1, 2015, published  March, 1,  2015.}%

\author{{A.Yu. Vasil'eva}}%
\address{Anastasia Yurievna Vasil'eva
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia%}%
\newline\hphantom{iii} Novosibirsk State University,
\newline\hphantom{iii} Pirogova str., 1,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{vasilan@math.nsc.ru}%

\thanks{\sc Vasil'eva, A.Yu.,
Completely regular codes
in the $n$-Dimensional Rectangular Grid}
\thanks{\copyright \ 2022 Vasil'eva A.Yu}
%\thanks{\rm The work is supported by RFFI (grant 03-01-11111)}
\thanks{\it Received  January, 1, 2015, published  March, 1,  2015.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }
It is proved that two sequences of the intersection array
of an arbitrary completely regular code in
the $n$-dimensional rectangular grid are monotonic.
It is shown that the minimal distance of an arbitrary
completely regular code is at most 4 and the covering radius
of an irreducible completely regular code in the grid
is at most $2n$.
\medskip

\noindent{\bf Keywords:}
$n$-dimensional rectangular grid, completely regular code,
intersection array, covering radius, perfect coloring
 \end{quote}
}


\section{Introduction} \label{introd}
\label{prelim}
A vertex coloring of a graph is perfect if any two vertices of the same color
``see'' \ the same number of vertices of any fixed color.
If in addition the vertices are colored by distance
from some initial set of vertices then the coloring is distance regular
and this set is a completely regular code.
These notions are closely related with distance regular graphs.
In fact, in a distance regular graph a distance coloring
with respect to an arbitrary vertex is perfect
and parameters of the cor\-res\-pon\-ding distance regular coloring
do not depend on the choice of the vertex.
But this property does not hold for the graph
of the $n$-dimensional rectangular grid in case $n>1$.
Completely regular codes in distance regular graphs
are extensively investigated.

In \cite{MartinThesis}, it was conjectured that two sequences
of the intersection array of a completely regular code
in a distance regular graph are monotonic.
In \cite{KoolenBSg}, it was shown that this conjecture is not true in general,
but is true for most of the classical graphs.
First, we prove (Theorem \ref{mon}) that the conjecture
is true for the $n$-dimensional rectangular grid.
Second, we obtain an upper bound  $2n$ for the covering radius
of an arbitrary completely regular code in  the $n$-dimensional rectangular grid
and show that this bound is attainable (Theorem \ref{irr}).
Third, we prove that the upper bound for the minimal code distance
of such a code is equal to $4$ (Theorem \ref{mindis}).
Earlier the results of this paper were presented in part in \cite{AV2012}.

The complete classification of perfect colorings of the 2-dimensional rectangular grid
into 2, 3 and up to 9 colors can be found in \cite{Ax}, \cite{Puz} and \cite{Krotov-prep}
respectively.
All feasible parameters of distance regular colorings of the 2-dimensional rectangular grid
were described in \cite{AV}.
Completely regular codes of infinite hexagonal and triangular grids were investigated in
\cite{AKV} and \cite{V3g} respectively.
Parameters of perfect colorings with two colors
of infinite circulant graphs were studied in \cite{Khor1, Khor2, Par}.

Let us pass to precise definitions.
An $r$-\emph{coloring} of the vertices of a graph
is a function $\varphi$ over the graph vertices with values in the set
$\{0,1,\ldots,r-1\}$ and it can be presented as a partition
$\Phi=\{\Phi_0,\Phi_1,\ldots,\Phi_{r-1}\}$ of
the graph vertices, where
$$\Phi_i= \{{\bf x} \ : \ \varphi({\bf x})=i\}, \ i=0,1,\ldots,r-1.$$
An $r$-coloring is \emph{ perfect} (in other terms,
the corresponding partition is \emph{ equitable})
with the \emph{parameter matrix} $P =(p_{ij})_{r\times r}$
if any vertex of the color $i$ has exactly
$p_{ij}$ adjacent vertices of color $j$ for all $i,j\in\{0,1,...,r-1\}$.

A~vertex set $D$ is the {\it completely regular code} if the distance coloring
$$\Phi=(\Phi_0=D,\Phi_1,\ldots,\Phi_{r-1}), \ \ \ \Phi_i=\{{\bf x} \ : \
\rho(D,{\bf x})=i\} , \ i=0,\ldots,r-1,$$
with respect to $D$ is perfect (here $\rho( \ , \ )$ denotes the graph distance),
then $r-1$ is the {\it covering radius} of $D$
and $\min\{\rho({\bf x},{\bf y}) \ : \ {\bf x},{\bf y}\in D\}$ is the
{\it code distance} of $D$.
The code $\Phi_{r-1}$ is also completely regular.
A vertex of the color $i, \ 0\leq i\leq r-1$,
``sees'' vertices of colors $i-1, i$ and $i+1$ only and
then the parameter matrix $P$ of the partition $\Phi$ is three-diagonal.
We denote its nonzero elements as follows:
$$\begin{bmatrix}
a_0 & b_0 & & & & \\
c_1 & a_1 & b_1 & & & \\
 & c_2 & a_2 & b_2 & &  \\
 & & \ddots & \ddots & \ddots &  \\
 & & & c_{r-2} & a_{r-2} & b_{r-2} \\
 & & & & c_{r-1} & a_{r-1}
\end{bmatrix} ,$$
%Here \\
$a_i=p_{i,i}  \ (i=0,1,\ldots,r-1) $ -- the \emph{ inner degree} of the
$i$-th color;\\
$b_i=p_{i,i+1}  \ (i=0,1,\ldots,r-2) $ -- the \emph{ upper degree} of
the $i$-th color;\\
$c_i=p_{i,i-1}  \ (i=1,2,\ldots,r-1)$ -- the \emph{ lower degree} of the
$i$-th color.

\noindent
In these terms, any vertex of color $i$ ``sees'' $c_i$ vertices of color $i-1$, \
$a_i$ vertices of color $i$ and $b_i$ vertices of color $i+1$.
We will say that the color $i$ has the \emph{ degree triple}  $(c_i,a_i,b_i)$
and will write the parameter matrix as follows:
$$ [a_0,b_0 | c_1,a_1,b_1 |\ldots| c_i,a_i,b_i |\ldots| c_{r-1},a_{r-1}] .$$
Only distance colorings with respect to a completely regular code will be studied further,
so the parameter matrices will be three-diagonal and all their nonzero
elements are contained in degree triples.

The ordered pair $(b_0,\ldots, b_{r-2}; c_1,\ldots, c_{r-1})$ of sequences
of upper and lower degrees is called as the \emph{ intersection array}
of the completely regular code $D$.

The $n$-\emph{dimensional rectangular grid} is the graph $G_n$ with the vertex set
$$\mathbb{Z}^n = \{{\bf x}=(x_1,\ldots,x_n) \ : \ \ x_i\in \mathbb{Z}, \ i=1,\ldots,n\}$$
and with the edge set
$$\{({\bf x},{\bf y}) \ :  \ \ \sum_{i=1}^n|x_i-y_i|=1\}.$$
Then the graph distance between vertices ${\bf x}$ and ${\bf y}$ can be written as
$\rho({\bf x},{\bf y})= \sum_{i=1}^n|x_i-y_i|$.
Let ${\bf e}^i\in\mathbb{Z}^n, \ i=1,\ldots,n$, \ be the
$(0,1)$-vector with the unique one at the $i$-th position.

Further in the paper $D$ denotes a completely regular code
in the $n$-dimensional rectangular grid, $\varphi=\varphi_D$ denotes
the distance coloring
$$\varphi({\bf x})=\rho(D,{\bf x}), \ \ {\bf x}\in\mathbb{Z}^n,$$
with respect to~$D$ and
$$\Phi=(\Phi_0=D,\Phi_1,\ldots,\Phi_{r-1}), \ \ \
\Phi_i=\{{\bf x}\in\mathbb{Z}^n \ : \ \varphi({\bf x})=i\} , \ i=0,\ldots,r-1,$$
denotes the corresponding partition of $\mathbb{Z}^n$ by colors.
For an arbitrary vertex ${\bf x}\in \mathbb{Z}^n$
let us introduce the following sets of unit vectors:
\begin{eqnarray*}
A_{\varphi}({\bf x}) = \left\{{\bf y}-{\bf x} \ : \
\varphi({\bf y})=\varphi({\bf x}), \ \rho({\bf x},{\bf y})=1 \right\} , \phantom{vvii} \\
B_{\varphi}({\bf x}) = \left\{{\bf y}-{\bf x} \ : \
\varphi({\bf y})=\varphi({\bf x})+1, \ \rho({\bf x},{\bf y})=1 \right\} , \\
C_{\varphi}({\bf x}) = \left\{{\bf y}-{\bf x} \ : \
\varphi({\bf y})=\varphi({\bf x})-1, \ \rho({\bf x},{\bf y})=1 \right\} .
\end{eqnarray*}
We will omit the subscript $\varphi$ if the coloring $\varphi$ is clear from the context.
We will call vectors from the sets $A_{\varphi}({\bf x}),
B_{\varphi}({\bf x}), C_{\varphi}({\bf x})$ as \emph{inner, upper} and \emph{lower directions}
of the vertex ${\bf x}$ with respect to $\varphi$.
Obviously,
\begin{eqnarray*}
|A_{\varphi}({\bf x})|=a_i, \ \ |B_{\varphi}({\bf x})|=b_i, \ \
|C_{\varphi}({\bf x})|=c_i , \\
A_{\varphi}({\bf x})\cup B_{\varphi}({\bf x})\cup
C_{\varphi}({\bf x})= \{\pm {\bf e}^i : \ \ i=1,\ldots,n\}.
\end{eqnarray*}
For any set $L$ of directions,
we denote $-L = \{-l \ : \ l\in L\}$.

We say that two colorings $\varphi$ and $\psi$ are \emph{ equivalent}
if $\psi$ can be obtained from $\varphi$ by some graph automorphism
and some color renumbering.
In particular, for a distance regular coloring $\varphi$,
the coloring $\psi$ with the inverse order of colors is equivalent and
\begin{equation}\label{L=U}
B_{\varphi}({\bf x})=C_{\psi}({\bf x}), \ \ \ \
C_{\varphi}({\bf x})=B_{\psi}({\bf x}), \ \ \ \
A_{\varphi}({\bf x})=A_{\psi}({\bf x}), \ \ \ \ {\bf x}\in \mathbb{Z}^n .
\end{equation}
We say that two codes $D_1$ and $D_2$ are \emph{ equivalent}
if $D_2$ can be obtained from $D_1$ by some graph automorphism.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Reducible colorings} \label{reducible}
For an arbitrary $r$, there exist only three nonequivalent
completely regular codes in the 1-dimensional grid $G_1$
with the covering radius $r-1$:
$$\{2(r-1)t \ : \ t\in\mathbb{Z}\}, $$
$$\{(2r-1)t \ : \ t\in\mathbb{Z}\}, $$
$$\{2rt, \ 2rt-1 \ : \ t\in\mathbb{Z}\}. $$%\cup\{1+(2(r-1)+1)t,  \ : \ t\in\mathbb{Z}\}.$$
The corresponding distance colorings are periodical,
here theirs periods are presented as sequences of colors
together with the parameter matrices:
$$0,1,2,\ldots,r-2,r-1,r-2,\ldots,1; \ \ \ \ \ \ \ \ \ \ \ \ \ [02|101|101|\ldots|101|20],$$
$$0,0,1,2,\ldots,r-2,r-1,r-2,\ldots,1; \ \ \ \ \ \ \ \ \ \ \ [11|101|101|\ldots|101|20],$$
$$0,0,1,2,\ldots,r-2,r-1,r-1,r-2,\ldots,1; \ \ \ [11|101|101|\ldots|101|11].$$

A code $D$ in the $n$-dimensional rectangular grid $G_n$
is called \emph{reducible} if %it can be reduced to the 1-dimensional code, i.e.
there exists a completely regular code $D'$ of $G_1$ and
$\delta_1,\ldots,\delta_n\in\{0,1,-1\}$ such that
\begin{equation}\label{nDfrom1}
D=\left\{{\bf x}=(x_1,x_2,\ldots,x_n) \ :
\left(\delta_1x_1+\delta_2x_2+\ldots+\delta_nx_n\right)\in D'\right\} .
\end{equation}
The parameter matrix is referred to as
\emph{reducible} if it admits a reducible coloring $\varphi_D$.
Obviously, each color of the distance regular coloring with respect to
the reducible completely regular code $D$ is an union of sets
$$\left\{{\bf x}=(x_1,x_2,\ldots,x_n) \ :
\left(\delta_1x_1+\delta_2x_2+\ldots+\delta_nx_n\right)= const\right\} .$$
So,
the corresponding coloring $\varphi_D$ of the $n$-dimensional grid
is also called \emph{reducible} and it means
there exists an $r$-coloring $\varphi'$ of $G_1$ and
$\delta_1,\ldots,\delta_n\in\{0,1,-1\}$ such that
for any $(x_1,x_2,\ldots,x_n)\in \mathbb{Z}^n$,
\begin{equation}\label{nfrom1}
\varphi(x_1,x_2,\ldots,x_n) =
\varphi_1\left(\delta_1x_1+\delta_2x_2+\ldots+\delta_nx_n\right) .
\end{equation}
If $t$ denotes the number of nonzero
coefficients $\delta_k, 1\leq k\leq n,$
then an arbitrary vertex of the color $i, 1\leq i\leq r-2,$ \ ``sees''
precisely $t$ vertices of the color $i-1$ and precisely $t$ vertices of the color $i+1$.
As a result, we obtain
\begin{lemma} \label{redpmat}
Let $P$ be an arbitrary reducible matrix of a distance regular coloring of $G_n$.
Then there exists $t\in\{0,1,\ldots,n\}$ such that
$$P=\left[ 2n-\varepsilon_1 q, \varepsilon_1 q \ | \ q, 2n-2q, q \ | \ \ldots \ |
 q, n-2q, q \ | \ \varepsilon_2 q, 2n-\varepsilon_2 q \right] ,$$
where  $\varepsilon_1,\varepsilon_2\in\{1,2\}$
 \ (the colorings with $(\varepsilon_1,\varepsilon_2)=(1,2)$ and
$(2,1)$ are equivalent).
\end{lemma}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Upper and lower degrees} \label{degrees}
Throughout this section $r\geq 3$ and
a fixed distance regular $r$-coloring of $G_n$ is denoted~by~$\varphi$ .
We are going to prove the monotonicity of the upper degrees
(and the lower degrees) of the coloring $\varphi$.

\begin{lemma} \label{incl}
Let %$0\leq i\leq r-2$,
${\bf x}$ and ${\bf y}$ be two adjacent vertices and
$\varphi({\bf y})= \varphi({\bf x})+1$. Then
$$C({\bf x})\subseteq C({\bf y}), \ \ \ B({\bf x})\supseteq B({\bf y}).$$
\end{lemma}
\begin{proof}
If $\varphi({\bf x})=0$ then $\emptyset=C({\bf x})\subseteq C({\bf y})$.

Now $i=\varphi({\bf x})\geq 1$ and then $C({\bf x})\neq \emptyset$.
Let us take $d\in C({\bf x})$.
If $d={\bf x}-{\bf y}$ then obviously $d\in C({\bf y})$.
Then consider the case $d\neq {\bf x}-{\bf y}$.
The color of the vertex ${\bf x}+d$ equals $i-1$.
The color of the vertex ${\bf y}+d$ is equal to $i$,
because $\varphi({\bf y})=i+1$ and
the vertex ${\bf x}+d=({\bf y}+d)+({\bf x}-{\bf y})$ has the color $i-1$.
Then $d\in C({\bf y})$.

Finally, $C({\bf x})\subseteq C({\bf y})$.
Further, (\ref{L=U}) gives $B({\bf x})\supseteq B({\bf y})$.
\end{proof}
Lemma \ref{incl} immediately gives us the monotonicity
of the lower degrees and the upper degrees
of an arbitrary distance regular $r$-coloring of $G_n$:
\begin{theorem} \label{mon}
Let $D$ be an arbitrary completely regular code in the $n$-dimensional
rectangular grid with the intersection array
$(b_0,\ldots, b_{r-2}; c_1,\ldots, c_{r-1})$. Then
$$\phantom{c_0\leq}c_1\leq\ldots\leq c_{r-2}\leq c_{r-1}, $$
$$b_0\geq b_1\geq\ldots\geq b_{r-2}.\phantom{\geq b_{r-1}}$$
\end{theorem}
It follows from Theorem \ref{mon} that there exist
two colors $I=I(\varphi)$ and $J=J(\varphi)$ such that
\begin{eqnarray}\label{IJ}
I(\varphi)=\max\{i \ : \ c_{i+1}\geq b_{i+1}\},\\
J(\varphi)=\min\{i \ : \ c_{i-1}\leq b_{i-1}\}.
\end{eqnarray}
Thus, all colors of a distance regular coloring $\varphi$
are partitioned into three segments: \\
$\{0,\ldots, I(\varphi)\}\neq \emptyset$, here $c_i<b_i$ for any $i, 0<i\leq I(\varphi)$; \\
$ \{I(\varphi)+1,\ldots,J(\varphi)-1\}$, here $c_i=b_i$ for any $i, I(\varphi)\leq i\leq J(\varphi)$; \\
$\{J(\varphi),\ldots,r-1\}\neq \emptyset$, here $c_i>b_i$ for any $i, J(\varphi)\leq i < r-1$.

Lower degrees in the first segment
and upper degrees in the last segment are considered in the following
\begin{lemma} \label{non-eq-ty}
a) If $i\leq I(\varphi)$ then $c_i\neq c_{i+1}$.
b) If $i\geq J(\varphi)$ then $b_i\neq b_{i-1}$.
\end{lemma}
\begin{proof}
a) Let us suppose $i\leq I(\varphi)$ and $c_i= c_{i+1}$.
We take an arbitrary vertex ${\bf x}$ of the color $i$ and
an arbitrary direction $d\in B({\bf x})$. It means that $-d\in C({\bf x}+d)$.
By assumption, $c_i=c_{i+1}$, then it follows from Lemma \ref{incl}
that $-d\in C({\bf x})$. Hence, $-B({\bf x})\subseteq C({\bf x})$ and
$b_i\leq c_i$ in contrary to the choice of $i$.
Therefore a) is true.
Now (\ref{L=U}) gives b).
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Colors with the same degree triple} \label{s-triples}

Lemma \ref{non-eq-ty} establishes that
only the degree triple of form $(t,2n-2t,t)$ can be repeated
in the intersection matrix of a completely regular code.
Everywhere in this section $\varphi$ denotes an arbitrary distance regular coloring,
moreover, we suppose $r\geq 4$ and $J(\varphi) > I(\varphi)+2$;
i.e., the different colors $I(\varphi)+1$ and $J(\varphi)-1$
have the same degree triple.

\begin{lemma} \label{opp}
Let the colors $i$ and $i+1$ have the same degree triple. Then for
any two adjacent vertices ${\bf x}$ and ${\bf y}$ of colors $i$ and $i+1$,
respectively, we have
\begin{equation}\label{LUxy}
C({\bf x})= C({\bf y})= -B({\bf x})= -B({\bf y}) ,
\end{equation}
\begin{equation}\label{IIxy}
A({\bf x})= A({\bf y})= -A({\bf x})= -A({\bf y}) .
\end{equation}
\end{lemma}
\begin{proof}
Equalities $C({\bf x})= C({\bf y})$
and $B({\bf x})= B({\bf y})$ follow from Lemma \ref{incl}.
Further, we put the direction $d\in B({\bf x})$.
It means that $-d\in C({\bf x}+d)$.
Then $-d\in C({\bf x})$ by Lemma \ref{incl} provided $c_i=c_{i+1}$.
Hence $-B({\bf x})\subseteq C({\bf x})$.
But we have $b_i=c_i$, so $-B({\bf x})= C({\bf x})$.
Finally, (\ref{IIxy}) follows from (\ref{LUxy}).
\end{proof}
We emphasize that according to Lemma \ref{opp},
two opposite directions, $d$ and $-d$, belong or do not belong
to the set $A({\bf x})$ of inner directions of a vertex ${\bf x}$ of a color
$i, \ i=I(\varphi)+1,\ldots J(\varphi)-1,$ \ simultaneously.

For any set $V\subseteq\mathbb{Z}^n$ of vertices
$G(V)$ denotes the subgraph of %$G_n$
the $n$-dimensional rectangular grid generated by $V$.
Let $V_i^{i+1}$ be the vertex set of an arbitrary
connected component of the graph $G(\Phi_i\cup\Phi_{i+1})$.

\begin{lemma} \label{Ci-opp}
Let the colors $i$ and $i+1$ have the same degree triples. %Then for
Then for
any two vertices ${\bf x}, {\bf y}\in V_i^{i+1}$
the equalities (\ref{LUxy}) and (\ref{IIxy}) hold.
\end{lemma}
\begin{proof}
It is sufficient to prove %the equalities
(\ref{LUxy}) and (\ref{IIxy}) for two adjacent vertices
of the same color $i$ or $i+1$, without loss of generality of the color $i$.
Let ${\bf x,y}\in\Phi_i$ be two adjacent vertices.
Then ${\bf x} - {\bf y}\in A({\bf y})$ and by Lemma~\ref{opp} also ${\bf y} - {\bf x}\in A({\bf y})$,
whence we have
\begin{equation}\label{2y-x}
2{\bf y}-{\bf x}= {\bf y}+({\bf y}-{\bf x})\in \Phi_i .
\end{equation}

Suppose (\ref{IIxy}) is not true for the vertices ${\bf x}$ and ${\bf y}$.
Then there exists $d\in A({\bf x})\setminus A({\bf y})$.
In this case $d\in B({\bf y})\cup C({\bf y})$.
First let $d\in B({\bf y})$. Then ${\bf y}+d\in \Phi_{i+1}$ and
${\bf x}-{\bf y}=({\bf x}+d)-({\bf y}+d)\in C({\bf y}+d)$.
By Lemma \ref{opp},  ${\bf y}-{\bf x}\in B({\bf y}+d)$
from which we have
$$2{\bf y}-{\bf x}+d= ({\bf y}+d)+({\bf y}-{\bf x})\in \Phi_{i+2}$$
that contradicts (\ref{2y-x}).
It remains to consider the case  $d\in C({\bf y})$. Here $-d\in B({\bf y})$ and analogously
we obtain the contradiction.
Thus, (\ref{IIxy}) holds for the vertices  ${\bf x}$ and ${\bf y}$.

The equation (\ref{LUxy}) follows from (\ref{IIxy}) and Lemma \ref{opp}.
\end{proof}

Now we will recognize that
an arbitrary connected component $V_i^{i+1}$
of the graph $G(\Phi_i\cup \Phi_{i+1}), \ I(\varphi)<i<J(\varphi)$,
consists of two hyperplanes.
Let $\gamma\in\mathbb{Z}$ and $\delta=(\delta_1,\delta_2,\ldots,\delta_n)\in\{0,1,-1\}^n$.
Let us denote %by $M(\delta,\gamma)$ the hyperplane
\begin{equation}\label{Mdc}
M(\delta,\gamma) = \left\{{\bf x} = (x_1,x_2,\ldots,x_n)\in \mathbb{Z}^n \ : \
\delta_1x_1+\delta_2x_2+\ldots+\delta_nx_n = \gamma\right\} .
\end{equation}

\begin{lemma} \label{subsp}
Let the colors $i$ and $i+1$ have the same degree triple.
Then there exist integer $\gamma$ and $(0,1,-1)$-valued
vector $\delta=(\delta_1,\ldots,\delta_n)$ such that
$$\Phi_{i+\varepsilon}\cap V_i^{i+1}=M(\delta,\gamma+\varepsilon), \ \ \ \ \ \varepsilon\in\{0,1\}.$$
\end{lemma}
\begin{proof}
Let $0\leq t\leq n$, the repeated degree triple be $(t,2n-2t,t)$ and
${\bf v}=(v_1,v_2,\ldots,v_n)\in V_i^{i+1}$ be the vertex of color $i$.
Lemma \ref{Ci-opp} follows that
$$B({\bf v}) = \{ {\bf e}^1,\ldots,{\bf e}^s,-{\bf e}^{s+1},\ldots,-{\bf e}^t\} ,$$
$$C({\bf v}) = \{ -{\bf e}^1,\ldots,-{\bf e}^s,{\bf e}^{s+1},\ldots,{\bf e}^t\} ,$$
$$A({\bf v}) = \{ \pm {\bf e}^{t+1},\ldots,\pm {\bf e}^n\} ,$$
up to the numbering of unit vectors.
Then let us put: \\ %define the following constants: \\
$$\delta_1 =\ldots=\delta_s=1,$$
$$\delta_{s+1}=\ldots=\delta_t=-1,$$
$$\delta_{t+1}=\ldots=\delta_n=0,$$
$$\gamma=v_1+\ldots+v_s-v_{s+1}-\ldots-v_t.$$
Under this choice of constants, ${\bf v}\in M(\delta,\gamma)$ obviously.
For an arbitrary vertex ${\bf x}\in V_i^{i+1}$,
one can easily check by induction on distance between ${\bf x}$ and ${\bf v}$
that ${\bf x}\in M(\delta,\gamma)$ in case ${\bf x}\in \Phi_i$
and  ${\bf x}\in M(\delta,\gamma+1)$ in case ${\bf x}\in \Phi_{i+1}$.
\end{proof}

\begin{theorem} \label{reduc}
Let $\varphi: \mathbb{Z}^n\longrightarrow\{0,1,\ldots,r-1\}$ be an arbitrary
distance regular coloring,  $2\leq i < j\leq r-2,$ the
colors $i$ and $j$ have the same degree triple. Then the  degree
triples coincide for all colors from 1 to $r-2$ and the coloring is reducible.
\end{theorem}
\begin{proof}
We will show that any color consists of hyperplanes of form (\ref{Mdc}).
All colors from $i$ to $j$, in particular, the colors $i$ and $i+1$
have the same degree triple.
By Lemma~\ref{subsp}, there exists $\gamma\in\mathbb{Z}$ and
$\delta\in \{0,1,-1\}^n$ such that
$M(\delta,\gamma+\varepsilon)\subseteq \Phi_{i+\varepsilon}, \ \varepsilon\in\{0,1\}$.
Then for any $k\in \{0,\ldots,r-1\}$ by induction on $|k-i|$ one can easily check that
$M(\delta,\gamma+k-i)\subseteq \Phi_{k}$ because the coloring is distance regular.
In particular, for the initial and the last colors it holds
$M(\delta,\gamma-i)\subseteq \Phi_0$ and $M(\delta,\gamma+r-i-1)\subseteq \Phi_{r-1}$.
By distance regularity of the coloring,
$M(\delta,\gamma-i-1)\subseteq \Phi_1$ or $M(\delta,\gamma-i-1)\subseteq \Phi_0$ and
$M(\delta,\gamma+r-i)\subseteq \Phi_{r-2}$ or $M(\delta,\gamma+r-i)\subseteq \Phi_{r-1}$.

Hence, by distance regularity of the coloring, for each $\gamma^\prime\in\mathbb{Z}$
all vertices of $M(\delta,\gamma^\prime)$ have the same color
which depends on $\gamma^\prime = \delta_1x_1+\delta_2x_2+\ldots+\delta_nx_n$ only.
It means that there exists a distance regular coloring $\varphi^\prime$
of the graph $G_1$ such that
$$\varphi(x_1,x_2,\ldots,x_n) =
\varphi'\left(\delta_1x_1+\delta_2x_2+\ldots+\delta_nx_n\right) ,$$
i.e., the coloring $\varphi$ of $G_n$ is distance regular.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Minimal distance and covering radius} \label{main}
The Hamming graph $H_N$ consists of the following vertex set and edge set:
$${\bf F}^N = \{\alpha=(\alpha_1,\ldots,\alpha_N) \ : \ \alpha_k\in\{ 0,1\}, k=1,\ldots,N\}, $$
$$\{(\alpha,\beta) \ : \ \alpha,\beta\in {\bf F}^N, \ \sum_{k=1}^N |\alpha_k-\beta_k|=1\} .$$
The Hamming graph $H_{2n}$ is covered by the graph $G_n$ of $n$-dimensional rectangular grid
and the covering mapping is %the Gray transform
$g:\mathbb{Z}^n\rightarrow {\bf F}^{2n}$,
such that for every ${\bf x}=(x_1,\ldots,x_n)\in \mathbb{Z}^n$
\begin{eqnarray*}
g(x_1,\ldots,x_n) = (g_0(x_1 \bmod 4),\ldots,g_0(x_n \bmod 4)), \\
g_0(0)=00, \ g_0(1)=01, \ g_0(2)=11, \ g_0(3)=10.
\end{eqnarray*}
Actually, this mapping preserves the adjacency: if two vertices ${\bf x}, {\bf y}$
of the $n$-dimen\-sio\-nal rectangular grid  differ in exactly one position,
then clearly the vertices $g({\bf x}), g({\bf y})$
of the $2n$-dimensional Hamming graph $H_{2n}$ also differ in exactly one position.

Let $\psi$ be a coloring of the Hamming graph $H_{2n}$.
Define the coloring $\varphi_{\psi}$ of the $n$-dimen\-sio\-nal rectangular grid $G_n$ as follows:
\begin{equation}\label{psi-g--1}
\varphi_{\psi}(x_1,\ldots,x_n) = \psi\left(g(x_1, \ \ldots \ ,x_n)\right), \ \
(x_1,\ldots x_n)\in \mathbb{Z}^n.
\end{equation}
Therefore the colorings $\psi$ and $\varphi_{\psi}$ are perfect
(respectively, distance regular) si\-mul\-ta\-neously and have the same parameter matrix.
We take as $\psi$ the distance coloring of $H_{2n}$
with respect to the all-zero vertex:
\begin{equation}\label{5raskr}
\psi(\alpha)=wt(\alpha) , \ \ \  \alpha\in{\bf F}^{2n},
\end{equation}
where $wt(\alpha)=
\sum_{i=1}^{2n} \alpha_i$ is the Hamming weight of the vertex $\alpha$.
In this case $\psi$ distance regular $(2n+1)$-coloring with the parameter matrix
$$[0, 2n | 1, 0, 2n-1 |\ldots|i, 0, 2n-i |\ldots| 2n-1, 0, 1 | 2n, 0].$$
Then $\varphi_{\psi}$ is also the distance regular $(2n+1)$-coloring
with the same parameter matrix, moreover,
it is not reducible because its parameter matrix is not reducible.

Finally, we can state the main theorem.

\begin{theorem} \label{irr}
For an arbitrary irreducible distance regular $r$-coloring of
$n$-dimen\-sio\-nal rectangular grid,
it holds $r\leq 2n+1$.
An irreducible distance regular $(2n+1)$-coloring exists.
\end{theorem}
\begin{proof}
Let $\varphi$ be an irreducible distance regular coloring
of the $n$-dimensional rectan\-gu\-lar grid.
By Theorem \ref{reduc},
every two colors have different degree triples.
This means that $J(\varphi)-I(\varphi)\leq 2$.
By definition (\ref{IJ}) of $I(\varphi)$, \  we have $c_{I(\varphi)}<b_{I(\varphi)}$,
and also we know that $c_{I(\varphi)}+b_{I(\varphi)}\leq 2n$.
It follows from Lemma \ref{non-eq-ty} that $\{c_1,\ldots,c_{I(\varphi)}\}$
are pairwise different.
Then
$I(\varphi)+1\leq n$.
Analogously, we obtain that $J(\varphi)\geq r-n$.
Finally, $r = (I(\varphi)+1)+(J(\varphi)-I(\varphi)-1)+(r-J(\varphi))\leq n+1+n=2n+1$.

The coloring $\varphi_\phi$ defined by (\ref{psi-g--1}), (\ref{5raskr})
gives us the example of the irreducible $(2n+1)$-coloring.
\end{proof}

Let us rewrite Theorem \ref{irr} in terms of completely regular codes:
\begin{corollary} \label{cov-radius}
The covering radius of an arbitrary completely regular code in the
$n$-dimensional rectangular grid is at most $2n$.
\end{corollary}

We also can obtain the upper bound for the minimal distance
of the completely regular code in $n$-dimensional rectangular grid.
\begin{theorem} \label{mindis}
The minimal distance of an arbitrary completely regular code in
$n$-dimensional rectangular grid is at most $4$.
\end{theorem}
\begin{proof}
Let $D$ be an arbitrary completely regular code
with minimal distance $d=d(D)\geq 5$ in the graph $G_n$, and ${\bf x}\in D$.
Let us consider the corresponding distance regular $r$-coloring
$\Phi=(\Phi_0=D,\ldots,\Phi_{r-1})$. Here $r-1$ is equal to the covering radius of the code $D$,
and $r-1\geq 2$ as far as $d\geq 5$.
Then any vertex of the sphere $S_2({\bf x})$ (of radius 2 centered in the vertex ${\bf x}$)
is of the color 2 and has ajacent vertices of color 1 only in the sphere
$S_1({\bf x})$ (of radius 1 centered in the vertex ${\bf x}$).

We consider the vertices
${\bf x}+2{\bf e}^1$ and ${\bf x}+{\bf e}^1+{\bf e}^2$ in the sphere $S_2({\bf x}).$
Theirs sets of lower directions are
$C({\bf x}+2{\bf e}^1)=\{{\bf e}^1\}$
and  $C({\bf x}+{\bf e}^1+{\bf e}^2)=\{{\bf e}^1,{\bf e}^2\}$
and have different cardinalities.
This lead us to the contradiction.
\end{proof}


\begin{thebibliography}{7}
\bibitem{AKV}
{\em Avgustinovich S.V. , Krotov D.S., Vasil'eva A. Yu.}
Completely regular codes in the infinite hexagonal grid,
Siberian Electronic Mathematical Reports, 2016, V.13, 987–1016.
DOI:10.17377/semi.2016.13.079

\bibitem{AV}
{\em Avgustinovich S.V., Vasil'eva A.Yu, Sergeeva I.V.}
Distance regular colorings of an infinite rectangular grid,
Journal of Applied and Industrial Mathematics, 2012, V.6, No.3, 280-285.
DOI:10.1134/S1990478912030027

\bibitem{AV2012}
{\em Avgustinovich S.V., Vasil'eva A.Yu.}
Distance regular colorings of n-dimensional rectangular grid,
Proceedings of 13th International Workshop on Algebraic
and Combinatorial Coding Theory -- Sofia: Inst. of Math. and Informatics, 2012, 35-40.
http://www.moi.math.bas.bg/moiuser/~ACCT2012/b6.pdf

\bibitem{Ax}
{\em Axenovich M.} On multiple coverings of the infinite
rectangular grid with balls of constant radius, Discrete Math.
2003. V.268, No.1-3. P. 31-49.
DOI:10.1016/S0012-365X(02)00744-6

 \bibitem{Khor1}
 {\em Khoroshilova D.B.} On two-colour perfect colourings of circular graphs,
Discretn. Anal. Issled. Oper., 2009. V.16, No.1, 80-92. (in Russian)

 \bibitem{Khor2}
{\em Khoroshilova D.B.}  On parameters of 2-colorings of circulant graphs,
Diskretn. Anal. Issled. Oper., 2011, V. 18, No.6, 82-89 (in Russian)

 \bibitem{KoolenBSg}
{\em Koolen J. H.} On a conjecture of Martin on the parameters of completely regular codes
and the classification of the completely regular codes in the Biggs-Smith graph,
Linear and Multilinear Algebra, 1995, V.39, No.1-2, 3-17. DOI:10.1080/03081089508818376

\bibitem{Krotov-prep}
{\em Krotov D.S.}, Perfect colorings of $\mathbb{Z}^2$: Nine colors, E-print 0901.0004, arXiv.org, 2009.
https://arxiv.org/abs/0901.0004

\bibitem{MartinThesis}
{\em Martin W. J.} Completely Regular Subsets, Ph.D. thesis, Univ. Waterloo, 1992.
https://users.wpi.edu/~martin/RESEARCH/THESIS/t1.pdf

 \bibitem{Par}
 {\em Parshina O. G.} Perfect 2-colorings of infinite circulant graphs
 with continuous set of distances, Diskretn. Anal. Issled. Oper., 2014, V.21, No.2. 76-83 (in Russian)

\bibitem{Puz}
 {\em S.A. Puzynina} Perfect colorings of vertices
 of the graph $G(\mathbb{Z}^2)$ in three colors, Diskretn.
Anal. Issled. Oper. Ser. 2, 2005, V.12, No.1, 37–54. (in Russian).

\bibitem{V3g}
{\em Vasil’eva  A.Yu.} Completely regular codes in the triangular grid,
Proceedings of MIPT, 2022, V.14, No.2(54), 14-42  (in Russian).
https://mipt.ru/upload/medialibrary/4f7/01.pdf


\end{thebibliography}

\end{document}


