On the reconstruction of N-quasigroups of order 4 and
the upper bounds on their numbers 1

Krotov D.S.
Sobolev Institute of Mathematics, Novosibirsk

Potapov V.N.
Sobolev Institute of Mathematics, Novosibirsk

Abstract:

The number of ways for partial $n$-quasigroups of order $4$ to be extended to $n$-quasigroups is investigated. The upper bound on the number of $n$-quasigroups of order $4$ is arrived. The asimptotic $3^{n+1}2^{2^n+1}$ of that number is established.

Let $n$ be an arbitrary natural number, $A$ be a finite 2 set of cardinality $m>0$, and $G\subseteq A^n$. Let $q$ be a mapping from $G$ to $A$. If $q(c)\neq q(c')$ holds for every $c, c'\in G$ that differ in exactly one coordinate then the triple $(A,G,q)$ is called partial $n$-quasigroup (of order $m$). If in addition $G=A^n$ then the pair $(A,q)$ is called $n$-quasigroup (of order $m$).

It is naturally to think of a $n$-quasigroup $(A,q)$ as a value array of $q$. In such $n$-dimensional array of size $\vert A\vert\times\ldots\times \vert A\vert$ every row (column) of every direction contains all elements of $A$ (see, for example, Figure 2).

Two $n$-quasigroups $(A,q)$ and $(A,\hat q)$ are called equivalent if there exist permutations $\rho_0,\rho_1,\ldots,\rho_n:A\to A$ and $\pi:\{1,\ldots,n\}\to \{1,\ldots,n\}$ such that $\hat q(x_1,\ldots,x_n)=\rho_0q(\rho_1x_{\pi(1)},\ldots,\rho_nx_{\pi(n)})$.

The $n$-quasigroup $(A,q)$ is called extension of the partial $n$-quasigroup $(A,G,p)$ if $p=q\big\vert _{G}$. Note that a partial $n$-quasigroup may have more than one extension, as well as it may have no extensions at all.

There are exactly two $n$-quasigroups of order $2$. All $n$-quasigroups of order $3$ are equivalent, and their number is $3\cdot 2^n$. The order $4$ is the first nontrivial from the view-point of variability case. Let $A=\{0,1,2,3\}$ and $Q(n)$ be the number of different $n$-quasigroups $(A,q)$. It was shown in [1] that


\begin{displaymath}Q(n)\geq L(n)\stackrel{df}=3^{n+1}2^{2^n+1}-2^{n+3}3^n.\eqno(1)\end{displaymath}

The upper estimations (2)-(6) on $Q(n)$ are based on the number of extensions of special-purpose partial $n$-quasigroups.

The trivial bound

Let $G'_n=\{1,2,3\}^n$ (see, f.i., Fig.1a), and $(A,G'_n,p)$ be a partial $n$-quasigroup.

Figure 1: Subsets of $\{0,1,2,3\}^3$: a) $G'_3$, b) $G''_3$, c) $G'''_3$, d) $G^1_3$.
\begin{figure} \begin{center} \epsfxsize=170mm \epsfysize=70mm \epsfbox{k1.gif} \end{center} \end{figure}

Lemma 1   Partial $n$-quasigroup $(A,G'_n,p)$ has at most one extension.

Since the number of different maps from $G'_n$ to $A$ is $4^{3^n}$, it is true that

\begin{displaymath}Q(n)\leq 4^{3^n}=2^{2^{\log_2\vspace{-0.2ex}3\cdot n+1}}.\eqno{(2)}\end{displaymath}



The asimptotic of ${\log\log Q(n)}$

Let $G''_n=A^{n-1}\times \{0,1\}$ (see, f.i., Fig.1b), and $(A,G''_n,p)$ be a partial $n$-quasigroup.

Lemma 2   The partial $n$-quasigroup $(A,G''_n,p)$ has at most $2^{2^{n-1}}$ extensions.

The mapping $p$ is uniquely defined by two subfunctions $p^{(0)}(x_1,\ldots,x_{n-1})\stackrel{df}=p(x_1,\ldots,x_{n-1},0)$ and $p^{(1)}(x_1,\ldots,x_{n-1})\stackrel{df}=p(x_1,\ldots,x_{n-1},1)$. The pairs $(A,p^{(0)})$ and $(A,p^{(1)})$ are $(n-1)$-quasigroups. Therefore Lemma 2 implies

\begin{displaymath}Q(n)\leq 2^{2^{n-1}}(M(n-1))^2 \end{displaymath}

and, by induction,

\begin{displaymath}Q(n)\leq 2^{(n+const)2^{n-1}}=2^{2^{n+\log_2n-1+o(1)}}.\eqno(3)\end{displaymath}

The bounds (1) and (3) give the asimptotic of $\log\log Q(n)$:

\begin{displaymath}\log_2\log_2 Q(n)=n+O(\log_2n).\end{displaymath}


The asimptotic of ${\log Q(n)}$

Let $G'''_n=A^n \backslash \{1,2,3\}^n$ (see, f.i., Fig.1c), and $(A,G'''_n,p)$ be a partial $n$-quasigroup.

Lemma 3   If $n\geq 2$ then the partial $n$-quasigroup $(A,G'''_n,p)$ has at most four extensions.

For $n$-ary mapping $q$ we call $k$-ary minorant the mapping obtained by the substituting zeros for some $n-k$ arguments of $q$. Lemma 3 implies that $k$-ary minorant of $q$ can be reconstructed from $(k-1)$-ary minorants by at most four ways, provided $(A,q)$ is a $n$-quasigroup and $k>1$.

Let $G^1_n=\cup_{i=1}^n A_i$, where $A_i=\{x=(x_1,...,x_n)\in A^n : x_j=0\ {\rm if}\ j\neq i\}$ (see, f.i., Fig.1d). Let $(A,q)$ be $n$-quasigroup. The partial $n$-quasigroup $(A,G^1_n,p)$, where $p=q\big\vert _{G^1_n}$, specifies all the $1$-ary minorants of $q$. The number of minorants is $2^n$, of which $n+1$ are $0$- and $1$-ary. Therefore, assuming $p$ is specified, the number of ways for $q$ to be reconstructed is at most $4^{2^{n}-n-1}$. The number of ways to specify $p$ is $4\cdot 6^n$, therefore

\begin{displaymath}Q(n)\leq 4\cdot 6^n\cdot 4^{2^n-n-1}=2^{2^{n+1}+O(n)}. \eqno(4)\end{displaymath}

Let the mapping $\oplus:A^2\to A$ be defined by the value table

\begin{displaymath}\begin{array}{c\vert cccc} \oplus &0&1&2&3\cr\hline 0&0&1&2&3\cr 1&1&0&3&2\cr 2&2&3&0&1\cr 3&3&2&1&0 \end{array}\end{displaymath}

Let the mapping $b:A\to\{0,1\}$ be defined by the equalities $b(0)=b(1)=0$, $b(2)=b(3)=1$.

Call the $n$-quasigroup $(A,q)$ bicubical if it is equivalent to the $n$-quasigroup $(A,q'')$ with $q''(x_1,\ldots,x_n)=x_1\oplus\ldots\oplus x_n$.

Call $n$-quasigroup $(A,q)$ cubical if it is equivalent to some $n$-quasigroup $(A,q')$ such that $b(q'(x_1,\ldots,x_n))=b(x_1\oplus\ldots\oplus x_n)$. Figure 2 gives examples of bicubical, cubical, and non-cubical $3$-quasigroups.

Figure 2: Examples of $3$-quasigroups:
a) bicubical $3$-quasigroup $(A,q'')$; the value array by three ways can be divided into $2\times 2\times 2$-subarrays each of them containing exactly two different elements;
b) cubical $3$-quasigroup obtained from $(A,q'')$ by "switching" one $2\times 2\times 2$-subarray;
c) decomposed $3$-quasigroup $(A,q)$ which is not cubical; $q(x,y,z)=q_{out}(q_{in}(x,y),z)$; in the figure the value arrays of $q_{out}$ and $q_{in}$ are marked by the outer and inner circles respectively.
\begin{figure} \begin{center} \epsfxsize=170mm \epsfysize=70mm \epsfbox{k2.gif} \end{center} \end{figure}

Proposition 1   The number of cubical $n$-quasigroups is $L(n)$ (see (1)).

Lemma 4   Let $n\geq 2$, and $(A,G''',p)$ be a partial $n$-quasigroup. Then
a) if $(A,G''',P)$ has more than one extension then all the extensions are cubical;
b) if $(A,G''',P)$ has more than two extensions then it has a bicubical extension.

Lemma 4 allows to strengthen the previous bound:

\begin{displaymath}Q(n)\leq 4\cdot 6^n\cdot 3^{n\choose \lfloor n/2\rfloor}\cdot 2^{2^n}= 2^{2^n(1+O(1/\sqrt{n}))}. \eqno(5)\end{displaymath}

It follows from (1) and (5) that

\begin{displaymath}\log_2 Q(n)=2^n(1+O(1/\sqrt n)).\end{displaymath}




The asimptotic of ${Q(n)}$

The $n$-quasigroup $(A,q)$ is called decomposed if there exist $k\geq 2$, $k$-quasigroup $(A,\dot q)$, $(n-k+1)$-quasigroup $(A,\ddot q)$, and a permutation $\pi:\{1,\ldots,n\}\to \{1,\ldots,n\}$ such that $q(x_1,\ldots,x_n) =\dot q(x_{\pi(1)},\ldots,x_{\pi(k-1)},\ddot q(x_{\pi(k)},\ldots,x_{\pi(n)}))$. Figure 2c gives an example of decomposed $3$-quasigroup.

Let $D_n$ be the set of all decomposed $n$-quasigroups $(A,q)$, and $\overline C_n$ be the set of $n$-quasigroups $(A,q)$ which are not cubical.

By the inequality (5) there is no difficulty in proving that

Proposition 2   If $n\geq 6$ then $\vert D_n\vert\leq 2^{2^n}$.

The folowing statement is established by the total computer enumeration of $5$-quasigroups or order $4$.

Proposition 3   $\vert\overline C_5\vert=4\cdot 6^5\cdot 201538000-L(5)=4\cdot 6^5\cdot 211410\leq 2\cdot 2^{2^5}$.

Let $G''_n$, $p^{(0)}$ and $p^{(1)}$ are defined as in Section 2.

Lemma 5   Let $(A,q)\in \overline C_n\backslash D_n$, and $p=q\big \vert _{G''_n}$. Then
a) the partial $n$-quasigroup $(A,G''_n,p)$ has exactly two extensions;
b) the $(n-1)$-quasigroups $(A,p^{(0)})$ and $(A,p^{(1)})$ belong to $\overline C_{n-1}$.

Therefore, $\vert\overline C_n\backslash D_n\vert\leq 2\vert\overline C_{n-1}\vert^2$. Moreover, since $p^{(0)}(x)\neq p^{(1)}(x)$ for every $x\in G^1_{n-1}$, it is true that $\displaystyle\vert\overline C_n\backslash D_n\vert\leq \frac3{2^n}\vert\overline C_{n-1}\vert^2$, and $\displaystyle\vert\overline C_n\vert\leq \vert D_n\vert+\frac3{2^n}\vert\overline C_{n-1}\vert^2\leq 2^{2^n}+\frac3{2^n}\vert\overline C_{n-1}\vert^2$ if $n\geq 6$. Taking Proposition 3 as a base, it's now easy to prove by induction that $\vert\overline C_n\vert\leq 2\cdot 2^{2^n}$ provided $n\geq 5$. Since $Q(n)\leq L(n)+\vert\overline C_n\vert$ by Proposition 1, it holds

\begin{displaymath}Q(n)\leq (3^{n+1}+1)2^{2^n+1}. \eqno(6)\end{displaymath}

It follows from (1) and (6) that

\begin{displaymath}Q(n)=3^{n+1}2^{2^n+1}\left(1+O\left(\frac1{3^n}\right)\right).\end{displaymath}


Bibliography

1
Krotov D.S. Lower Estimates for the Number of $m$-quasigroups of Order $4$ and for the Number of Perfect Binary Codes. // Diskr. Analiz i Issled. Operatsii. Ser. 1. 2000. V.7, N2. P.47-53 (in Russian).

Footnote

... numbers 1
The work is supported by the RFBR grants 00-01-00822 and 99-01-00531.
... finite 2
For the case of infinite $A$ the definition of $n$-quasigroup should be given in another way.
Comments
[ICT SBRAS]
[Home]
[Conference]

©2001, Siberian Branch of Russian Academy of Science, Novosibirsk
©2001, United Institute of Computer Science SB RAS, Novosibirsk
©2001, Institute of Computational Techologies SB RAS, Novosibirsk
©2001, A.P. Ershov Institute of Informatics Systems SB RAS, Novosibirsk
©2001, Institute of Mathematics SB RAS, Novosibirsk
©2001, Institute of Cytology and Genetics SB RAS, Novosibirsk
©2001, Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk
©2001, Novosibirsk State University
Last modified Saturday, 06-Oct-2001 18:20:30 NOVST