\documentclass{endm}
\usepackage{endmmacro}
\usepackage{graphicx}
\usepackage{amsmath,amssymb}

% The following is enclosed to allow easy detection of differences in
% ascii coding.
% Upper-case    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
% Lower-case    a b c d e f g h i j k l m n o p q r s t u v w x y z
% Digits        0 1 2 3 4 5 6 7 8 9
% Exclamation   !           Double quote "          Hash (number) #
% Dollar        $           Percent      %          Ampersand     &
% Acute accent  '           Left paren   (          Right paren   )
% Asterisk      *           Plus         +          Comma         ,
% Minus         -           Point        .          Solidus       /
% Colon         :           Semicolon    ;          Less than     <
% Equals        =           Greater than >          Question mark ?
% At            @           Left bracket [          Backslash     \
% Right bracket ]           Circumflex   ^          Underscore    _
% Grave accent  `           Left brace   {          Vertical bar  |
% Right brace   }           Tilde        ~

\newcommand{\Nat}{{\mathbb N}}
\newcommand{\Real}{{\mathbb R}}
%\def\lastname{Kormos 1, Iv\'anyi 2, Madar\'asz 3}

\begin{document}

% DO NOT REMOVE: Creates space for Elsevier logo, ScienceDirect logo
% and ENDM logo
\begin{verbatim}\end{verbatim}\vspace{2.5cm}

\begin{frontmatter}

\title{Perfect hypercubes}
\author[Budapest]{Antal Iv\'anyi\thanksref{myemail}\thanksref{TAMOP}}
\author[Budapest]{J\'anos Madar\'asz\thanksref{coemail}\thanksref{TAMOP}}
\address[Budapest]{Department of Computer Algebra\\ E\"otv\"os Lor\'and University\\ 
Budapest, Hungary}
\thanks[myemail]{Email:\href{mailto:tony@compalg.inf.elte.hu} {\texttt{\normalshape
   tony@compalg.inf.elte.hu}}} 
\thanks[coemail]{Email:
   \href{mailto:deusmadjan@gmail.com} {\texttt{\normalshape deusmadjan@gmail.com}}}
\thanks[TAMOP]{The European Union and the European Social Fund have provided financial support 
   to the project under the grant agreement no. T\'AMOP 4.2.1/B-09/1/KMR-2010-0003. The paper is dedicated to 
   the 70th birthday of Gyula Katona.}



\begin{abstract}
An $(n,d,\mathbf{a},\mathbf{b})$-perfect array is a $d$-dimensional $b_1 \times b_2 \times \cdots \times b_d$ 
sized $n$-ary periodic array containing all possible $a_1 \times a_2 \times \cdots \times a_d$ sized $n$-ary array 
exactly once as subarray. If $a_1 = a_2 = \cdots = a_d$ and $b_1 = b_2 = \cdots = b_d,$ then the notation 
$(n,d,a,b)$ and term double cube are used. If $d \geq 4$, then the double cube is called double hypercube. 
We prove the existence of $(N,d,a,b)$-perfect double cubes for arbitrary $d \geq 1$, $a \geq 2$ and $n \geq 2$, 
where $N = kn$ with a suitable $k \geq 1$. Further we illustrate the main theorem constructing 4 and 
5-dimensional hypercubes.
\end{abstract}


\begin{keyword}
De Bruijn arrays, perfect cubes, four- and five-dimensional perfect arrays.
\end{keyword}

\end{frontmatter}


\section{Introduction}\label{intro}
Cyclic sequences in which every possible subsequence of fixed length occurs exactly once have been studied 
for more than a hundred years. The problem later was extended to two- and more-dimensional arrays.

Let $\Zset$ be the set of integers. For $u, \ v \in \Zset$ we
denote the set $\{j \in \Zset \ | \ u \leq j \leq v \}$ by
$[u..v]$ and the set $\{j \in \Zset \ | \ j \geq u\}$ by
$[u..\infty]$. Let $d \in [1..\infty]$, $b_i, \ c_i, \ j_i \in [1..\infty]  \ (i \in
[1..d])$ and $a_i \in [2..\infty] \ (i \in [1..d]).$ Let
$\mathbf{a} = \langle a_1,a_2,\ldots,a_d\rangle,$ $\mathbf{b} =
\langle b_1,b_2,\ldots,b_d\rangle,$ $\mathbf{c} = \langle
c_1,c_2,\ldots,c_d \rangle, \ \mathbf{j} = \langle j_1,j_2,\ldots,j_d \rangle$.

A $d$-dimensional $n$-ary array $A$ is a mapping $A : [1..\infty]^d \rightarrow$ \linebreak$
[0,n-1]$.  If there exist a vector $\mathbf{b}$ and an array $M$ such that
$$\forall \mathbf{j} \in [1..\infty]^d :
A[\mathbf{j}]=M[(j_1 \ \mathrm{mod} \ b_1)+1, (j_2 \ \mathrm{mod}
\ b_2)+1,\ldots,(j_d \ \mathrm{mod} \ b_d)+1],$$ then A is a
$\mathbf{b}$\textbf{-periodic} array and $M$ is a period of $A.$
 The possible $\mathbf{a}$-sized \textbf{subarrays} of $A$ are the
$\mathbf{a}$-periodic $n$-ary arrays.

Although our arrays are infinite we say that a $\mathbf{b}$-periodic array is $\mathbf{b}$-sized.

A $d$-dimensional $\mathbf{b}$-periodic $n$-ary array $A$ is called
$(n,d,\mathbf{a},\mathbf{b})$\textbf{-perfect}, if
all possible $n$-ary arrays of size $\mathbf{a}$ appear in
$A$ exactly once as a subarray. Here $n$ is the alphabet size, $d$ gives the number of dimensions
of the "window" (or "pattern") and the perfect array $M$, the vector $\mathbf{a}$
characterizes the size of the window,  and the vector $\mathbf{b}$
is the size of the perfect array $M.$

If $b_1 = b_2 = \cdots = b_d,$ then the $(n,d,\mathbf{a},\mathbf{b})$-perfect
array $A$ is called \textbf{symmetric}. If $A$ is symmetric and
$a_1 = a_2 = \cdots = a_d,$ then $A$ is called \textbf{doubly
symmetric.} If $A$ is doubly symmetric and $d = 1$, then $A$ is called a \textbf{double sequence} 
(here the size $b_1$ means $1 \times b_1$);
$d = 2$, then $A$ is called a \textbf{double square}; 
$d = 3$, then $A$ is called a \textbf{double cube};
$d \geq 4$, then $A$ is called a \textbf{double hypercube}.


According to this definition, all perfect sequences are doubly
symmetric. In the case of symmetric arrays we use the notion
$(n,d,\mathbf{a},b)$ and in the case of doubly symmetric arrays we
use $(n,d,a,b)$ instead of $(n,d,\mathbf{a},\mathbf{b})$.

One-dimensional perfect arrays are often called de Bruijn or Good
sequences. Two-dimensional perfect arrays are called also perfect maps or de Bruijn tori.

Even de Bruijn sequences are useful in construction of perfect
arrays when the size of the alphabet is an even number and the
window size is $2 \times 2$. If $n$ is an even integer then an $(n,1,2,n^2)$-perfect sequence
$M = (m_1,m_2,$ $\ldots,m_{n^2})$ is called \textbf{even}, if $m_i = x, \ m_{i + 1} = y, \ x \neq y, m_j = y$ 
and $m_{j + 1} = x$ imply $j - i$ is even.

The concept of perfectness can be extended to infinite arrays in
various ways. In \textbf{growing arrays} 
the window size is fixed, the alphabet size is increasing and the
prefixes grow in all $d$ directions. In \textbf{superperfect arrays} the 
alphabet size is perfect and the window size is growing. 

\section{Necessary condition and earlier results}
Since in the period $M$ of a perfect array $A$ each element is the
head of a pattern, the volume of $M$ equals the number of the
possible patterns. Since each pattern---among others the pattern
containing only zeros---can appear only once, any size of $M$ is
greater then the corresponding size of the window. So we have the
following necessary condition \cite{HurlbertIsaak94,Ivanyi11,IvanyiT88}: If
$M$ is an $(n,d,\mathbf{a},\mathbf{b})$-perfect array, then
\begin{equation}
|\mathbf{b}| = n^{|\mathbf{a}|} \label{eq:volume}
\end{equation}
and
\begin{equation}
b_i > a_i \ \mathrm{for} \ i \in [1..d].\label{eq:size}
\end{equation}

The first known result originates from Flye-Sainte \cite{Flye94}
who in 1884 proved the existence of $(2,1,a,2^a)$-perfect sequences for
all possible values of $a$ and gave an explicit formula for the number of $(2,1,a,2^a)$-perfect sequences.


It is known \cite{Flye94} that in the one-dimensional
case the necessary condition (\ref{eq:volume}) is sufficient too.
There are many construction algorithms, like the ones of
Fan, Fan, Ma and Siu \cite{FanFanMaSiu85}, Martin \cite{Martin34}
 or any algorithm for the construction of directed Euler cycles . 
 The most popular algorithm is probably due to H. M. Martin. It has several implementations 
 having different time complexity \cite{Anisiu11,Ivanyi08,Ivanyi11}.
  
 N. V\"or\"os \cite{Voros84} in 1984, Cummings and Wiedemann in 1986 \cite{Cummings86} and Iv\'anyi in 1987  
 \cite{Ivanyi87,Ivanyi11} proposed algorithms for $n \geq 3$ to construct superperfect sequences. It is known 
 \cite{Ivanyi87,Ivanyi11} that it does not exist superperfect sequence for $n = 2$.
Iv\'anyi and T\'oth \cite{IvanyiT88} and later Hurlbert and
Isaak \cite{HurlbertIsaak94} provided a constructive proof of the
existence of even sequences. 
The conditions (\ref{eq:volume}) and (\ref{eq:size}) are sufficient for the existence of
$(2,2,\textbf{a},\textbf{b})$-perfect arrays \cite{FanFanMaSiu85}. Paterson in
\cite{Paterson96} supplied further sufficient conditions.

Hurlbert and Isaak \cite{HurlbertIsaak94} gave a construction for one- and two-dimensional growing arrays.
Iv\'anyi \cite{Ivanyi90} constructed $(n,d,\mathbf{a},\mathbf{b})$-perfect arrays for arbitrary $n \geq 2$, 
$d \geq 1$ and $\mathbf{a}$, but his arrays are rarely symmetric. 

Different construction algorithms and other results concerning one- and two-dimensional perfect arrays
can be found in the fourth volume of \textit{The Art of Computer Programming} \cite{Knuth11},  
e.g. a (2,1,5,32)-perfect array, a (2,2,2,4)-perfect array
and a (4,2,2,16)-perfect array. 

\section{Construction of hypercubes}
In the talk---using the algorithms \textsc{Cellular}, \textsc{Optimal-Martin}, \textsc{Even}, \textsc{Mesh}, 
\textsc{Shift}, \textsc{Colour}  \cite{Ivanyi88,Ivanyi90,Ivanyi08,Ivanyi11,IvanyiT88,Knuth11}---we 
prove the following theorem and illustrate it  by the construction of two hypercubes.
\begin{thm} If\label{thm:main} $n \geq 2$, $d \geq 1$, $a \geq 2$, and $b \geq 2$ satisfy \ref{eq:volume} and

a) $d \ | \ a^d$ and $(un)^{a^d/d}\geq n^{a^d} - a^{d - 1}$, then there exists 
a $(un,d,a,(un)^{a^d/d})$-perfect array;

b) $(vn)^{a^d} \geq n^{a^d - a^{d - 1}}$, then there exists a 
$\left ( (vn)^d,d,a,(vn)^{a^d}\right )$-perfect array,where 
$u$ and $v$ are suitable positive integers. 
\end{thm}  

At first we compute the minimal $k$, then construct an $(n,d,a,\mathbf{b})$-perfect array, where 
$$
\mathbf{b} = \langle n^a, n^{a^2 - a}, n^{a^3 - a^2} ,\ldots,n^{a^n - a^{n - 1}} \rangle. 
$$

Finally we fill an empty hypercube with such prisms and using \textsc{Colour} we get the requuired hypercube.

\subsection{Construction of a 4-dimensional double hypercube}  
In 4 dimensions the smallest $b$'s satisfying (\ref{eq:volume}) are $b = 16$ and 
$b = 81$. But we do not know algorithm which can construct $(2,4,2,16)$-perfect or 
$(3,4,2,81)$-perfect hypercube. The third chance is the $(4,4,2,256)$-perfect hypercube. 
Let $n = 2$ and $a = 2$. \textsc{Cellular} calculates $N = 2$, then calls 
\textsc{Optmial-Martin} receiving the cellular $(2,1,2,4)$-perfect sequence $0 0 | 1 1.$ 
Then \textsc{Cellular} calls \textsc{Mesh} which constructs the cellular 
$(2,2,2,4)$-perfect square shown in Table \ref{tab:perf2244}a. 
\begin{table}
\begin{center}
\begin{tabular}{|c||c|c|c|c|}  \hline
column/row & 1   &  2   &  3 & 4  \\ \hline \hline
1          & 0   &  0   & 0 & 1    \\ \hline
2          & 0   &  0  & 1  & 0    \\ \hline
3          & 1   & 0   & 1  & 1      \\ \hline
4          & 0   & 1   & 1  & 1   \\ \hline
\end{tabular}
\caption{A (2,2,4,4)-square\label{tab:perf2244}}
\end{center}
\end{table}

Now \textsc{Shift} calls \textsc{Optimal-Martin} with $n = 1$ and $a = 1$ to get the shift sizes for the layers of 
the $(2,3,2,\mathbf{b})$-perfect output $P$ of \textsc{Cellular}, where $\mathbf{b} = \langle 4,4,16\rangle$.  
\textsc{Shift} uses $P$ as zeroth layer and the $j$th layer is generated by cyclic shifting of the previous layer downwards 
by $w_i$ (div 4) and right by $w_i$ (mod 4), where \textbf{w} = $\langle 0 \ 15 \ 14 \ 13 \ 12 11 \ 10 \ 9 \ 8 \ 7 
\ 6 \ 5 \ 4 \ 3 \ 2 \ 1 \rangle$. The layers of the $(2,3,2,\langle 4 \ 4 \ 16 \rangle)$-perfect array are shown 
in Table \ref{tab:4416}. 
\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \hline
Layer 0 & Layer 1 & Layer 2 & Layer 3 & Layer 4 & Layer 5 & Layer 6 & Layer 7 \\ \hline 
0 0 0 1 & 0 0 0 1 & 0 1 0 0 & 1 1 0 1 & 1 1 0 1 & 0 1 0 0 & 1 1 0 1 & 0 0 1 0 \\ \hline 
0 0 1 0 & 0 0 1 0 & 0 1 1 1 & 1 0 1 1 & 0 1 0 0 & 1 0 0 0 & 1 0 1 1 & 0 1 0 0 \\ \hline 
1 0 1 1 & 1 0 1 1 & 1 1 1 0 & 1 0 0 0 & 1 0 0 0 & 1 1 1 0 & 1 0 0 0 & 0 1 1 1 \\ \hline 
0 1 1 1 & 0 1 1 1 & 0 0 1 0 & 0 0 0 1 & 1 1 1 0 & 1 1 0 1 & 0 0 0 1 & 1 1 1 0\\ \hline
Layer 8 & Layer 9 & Layer 10& Layer 11& Layer 12 & Layer 13 & Layer 14 & Layer 15 \\ \hline 
1 0 1 1 & 0 0 0 1 & 1 1 1 0 & 1 1 0 1 & 1 0 0 0 & 0 1 0 0 & 1 0 0 0 & 0 0 1 0 \\ \hline 
0 1 1 1 & 0 0 1 0 & 0 0 1 0 & 1 0 1 1 & 1 1 1 0 & 1 0 0 0 & 0 0 0 1 & 0 1 0 0 \\ \hline 
0 0 0 1 & 1 0 1 1 & 0 1 0 0 & 1 0 0 0 & 1 1 0 1 & 1 1 1 0 & 1 1 0 1 & 0 1 1 1  \\ \hline 
0 0 1 0 & 0 1 1 1 & 0 1 1 1 & 0 0 0 1 & 0 1 0 0 & 1 1 0 1 & 1 0 1 1 & 1 1 1 0\\ \hline
\end{tabular}
\caption{16 layers of the $(2,3,2,16)$-perfect output of \textsc{Shift}}\label{tab:4416}
\end{table}

Up to this point the construction is the same as in \cite{Ivanyi08}, but now $d = 4$, therefore we use 
\textsc{Shift} again to get a $(2,4,2,256)$-perfect prism, then we fill an empty 
$256 \times 256 \times 256 \times 256$ cube with $4 \times 4 \times 16 \times 256$-sized prisms and 
finally colouring results the required 4-dimensional hypercube. 

\subsection{Construction of a 5-dimensional double hypercube}
If $d = 5$, then $a = 2$, $n = 2^5$ and $b = 2^{32}$ satisfy (\ref{eq:volume}), and $3$ is the smallest 
value of $v,$ corresponding to part b) of Theorem \ref{thm:main}. Therefore we start with 
a $(2^5,5,2,2^{32})$-perfect prism and finish with a 
$(2^{15},5,2,2^{96})$-perfect hypercube.

The remaining used auxiliary arrays for both construction and the constructed 
$256 \times 256 \times 256 \times 256$ sized 
$(4,4,2,256)$-perfect double hypercube can be found in \cite{Ivanyi11} and its supplements.


\begin{thebibliography}{10}\label{bibliography}

\bibitem{Anisiu11} Anisiu, M.-C., and Z. K\'asa, \emph{The complexity of words}, in (ed. A. Iv\'anyi) 
Algorithms of Informatics, AnTonCom, Budapest, 2011, 1292--1330 (to appear). URL: 
\href{http://compalg.inf.elte.hu/~tony/Education/FirstExpert}
{http://compalg.inf.elte.hu/$\sim$tony/Education/FirstExpert}. 

\bibitem{Cummings86} Cummings, L. J.. and D. Wiedemann, \emph{Embedded de Bruijn sequences}, Congr. Numer. 
\textbf{53} (1986), 155-160. 
 
\bibitem{FanFanMaSiu85} Fan, C. T., S. M. Fan, S. L. Ma, and M. K. Siu, \emph{On de Bruijn arrays}, 
 Ars Comb. \textbf{19A} (1985), 205--213.

\bibitem{Flye94} Flye-Sainte, T. Marie, \emph{Solution of problem 58}, Intermediare des Mathematiciens 
\textbf{1} (1894), 107--110.

\bibitem{HurlbertIsaak94} Hurlbert, G., and G. Isaak, \emph{A meshing technique for de Bruijn tori}, 
 Contemporary Math. \textbf{178} (1994), 153--160.

\bibitem{Ivanyi87} Iv\'anyi, A. \emph{On the $d$-complexity of words},  
Ann. Univ. Sci. Budapest. Comp. \textbf{8} (1987), 69--90. 
URL: \href{http://ac.inf.elte.hu}{http://ac.inf.elte.hu}. 

\bibitem{Ivanyi88} Iv\'anyi, A. \emph{Construction of infinite de Bruijn arrays}, 
Discrete Appl. Math. \textbf{22} (1988/89), 289--293.

\bibitem{Ivanyi90} Iv\'anyi, A. \emph{Construction of three-dimensional perfect matrices},
Ars Combinatoria \textbf{29C} (1990), 33--40. 

\bibitem{Ivanyi08} Iv\'anyi, A., \emph{Growing perfect cubes},  
Discrete Math. \textbf{308} (19) (2008), 4378--4388. 
URL: \href{http://www.sciencedirect.com/science/journal/0012365X}{http://www.sciencedirect.com/science/journal/0012365X}

\bibitem{Ivanyi11} Iv\'anyi, A., \emph{Perfect arrays}, in (ed. A. Iv\'anyi) Algorithms of Informatics, AnTonCom, 
Budapest, 2011, 175--210 (to appear). URL: \newline
\href{http://compalginf.elte.hu/~tony/Education/FirstExpert}
{http://compalginf.elte.hu/$\sim$tony/Education/FirstExpert}.  

\bibitem{IvanyiT88} Iv\'anyi, A., and Z. T\'oth, \emph{Existence of de Bruijn words}, 
 in I. Pe\'ak, ed., Automata, Languages and Programming Systems (Salgótarján, 1988),
 1988, 88-4, 1407--1435.
  
\bibitem{Knuth11} Knuth, D. E., ''The Art of Computer Programming, Volume 4A``,   
Addison-Wesley, Upper Saddle River, N.J., 2011.

\bibitem{Martin34} Martin, M. H., \emph{A problem in arrangements}, Bull. American Math. Soc.
\textbf{40} (1934), 859--864.

\bibitem{Paterson96} Paterson, K. G., \emph{New classes of perfect maps. II.},
 J. Comb. Theory, Series A \textbf{73} (1996), 335--345.
 
\bibitem{Voros84} V\"or\"os, N., \emph{On the complexity of symbol-sequences}, in (ed. A. Iv\'anyi)  
Conf. of Young Programmers and Mathematicians (Budapest, 1984), 
E\"otv\"os Lor\'and University, Budapest, 1984, 43--50.  

\end{thebibliography}

\end{document}
