On the number of n-ary quasigroups of finite order∗

arXiv:0912.5453v2 [math.CO] 8 Feb 2016

V. N. Potapov? , D. S. Krotov?

? Sobolev

Institute of Mathematics, prospect Akademika Koptyuga 4, Novosibirsk
Mechanics and Mathematics Department of the Novosibirsk State University, Pirogova 2,
Novosibirsk
Abstract
Let Q(n, k) be the number of n-ary quasigroups of order k. We derive a recurrent formula for Q(n, 4). We prove that for all n ≥ 2 and k ≥ 5 the following inequalities hold:
n
n
k−3 2 k−1 2
< log2 Q(n, k) ≤ ck (k − 2)n , where ck does not depend on n. So, the upper
2
2
asymptotic bound for Q(n, k) is improved for any k ≥ 5 and the lower bound is improved
for odd k ≥ 7.
Keywords: n-ary quasigroup, latin cube, loop, asymptotic estimate, component, latin
trade.

UDC: 519.143
MSC2010: 20N15, 05B15

1. Introduction
An algebraic system from a set Σ of cardinality |Σ| = k and n-ary operation f : Σn → Σ
is called an n-ary quasigroup of order k iff the unary operation obtained by fixing any n − 1
arguments of f by any values from Σ is always bijective. The corresponding function f is often
also called an n-ary quasigroup (the value table of such a function is known as latin hypercube;
if n = 2, latin square).
Let us fix the set Σ = {0, 1, . . . , k − 1}. Denote by Q(n, k) the number of different n-ary
quasigroups of order k (for fixed Σ)1 . It is known that for every n there exist only two n-ary
quasigroups of order 2. There are exactly Q(n, 3) = 3 · 2n different n-ary quasigroups of order
n
3, which form one equivalence class. In [9] it is proved that Q(n, 4) = 3n+1 22 +1 (1 + o(1)) as
n → ∞. In Section 4 we suggest a recurrent way to calculate the numbers Q(n, 4) and list the
first 8 values. Before, only five values of Q(n, 4) where known; furthermore the numbers Q(n, 5)
and Q(n, 6) are known for n ≤ 5 and n ≤ 3 respectively, see [7], and the number Q(2, k) for
k ≤ 11, see [6] and references there.
The asymptotics of the number and even of the logarithm of the number (and even of
the logarithm of the logarithm of the number) of n-ary quasigroups of orders more than 4 is
n/3
unknown. In [5], the following lower bounds are derived: Q(n, 5) ≥ 23 −c , where c < 0.072;
n
n
n
Q(n, k) ≥ 2(k/2) if k is even; Q(n, k) ≥ 2n(k/3) if k ≡ 0 mod 3; Q(n, k) ≥ 21.5bk/3c for an
n
n−1
arbitrary k. The following upper bound was established in [8]: Q(n, k) ≤ 3(k−2) 2n(k−2) .
∗

This work was partially supported by the Federal Target Program “Scientific and Educational Personnel of
Innovation Russia” for 2009-2013 (contract No. 02.740.11.0429) and the Russian Foundation for Basic Research
(grants 08-01-00671, 08-01-00673).
1
Sometimes by the number of quasigroups one mean the number of mutually nonisomorphic quasigroups.

1

In this paper we improve the upper bound (Section 2) on the number of n-ary quasigroups
of finite order and the lower bound (Section 3) on the number of n-ary quasigroups of odd order:


k−3
2

n 
2

k−1
2

n
2

< log2 Q(n, k) ≤ ck (k − 2)n ,

where ck does not depend on n; explicitly, ck =

log2 k!
k−2

+

k
k−4 .

2. An upper bound
We will say that a set M ⊆ Σn satisfies Property (A) iff for every element x̄ ∈ M and every
position i = 1, . . . , n there is another element ȳ ∈ M differing from x̄ only in the position i. By
induction it is easy to get the following:
Proposition 1. Any nonempty subset C ⊆ Σn that satisfies Property (A) has the cardinality
at least 2n .
A function g : Ω → Σ where Ω ⊂ Σn is called a partial n-ary quasigroup of order |Σ| if
g(x) 6= g(y) for any two tuples x, y ∈ Ω differing in exactly one position. We will say that an
n-ary quasigroup f : Σn → Σ is an extension of a partial n-ary quasigroup g : Ω → Σ where
Ω ⊂ Σn if f |Ω ≡ g.
Lemma 1. Let |Σ| = k, B = Σ \ {a, b}, k ≥ 3, a, b ∈ Σ. Then a partial n-ary quasigroup
n−1
g : Σn−1 × B → Σ has at most 2(k/2)
different extensions.

Proof. Denote by P the set of the unordered pairs of elements of Σ. Consider a partial
n-ary quasigroup g : Σn−1 × B → Σ. Define the function G : Σn−1 → P by the equality
G(x) = Σ \ {g(xc) : c ∈ Σ \ {a, b}}. Define the graph Γ = hΣn−1 , Ei where two vertices x and y
are adjacent if and only if the tuples x and y differ in exactly one position and G(x) ∩ G(y) 6= ∅.
It is easy to see that connected components of Γ satisfy Property (A).
Let n-ary quasigroups f1 and f2 be extensions of g. It is not difficult to see that {f1 (xa), f1 (xb)} =
G(x) for every x ∈ Σn−1 ; moreover, if f1 (xa) = f2 (xa), then f1 and f2 coincide on the whole
connected component of Γ containing x ∈ Σn−1 . So, to define an extension of g uniquely it is
sufficient to choose one from the two possible values for every connected component of Γ. It
follows from Proposition 1 that every connected component has cardinality at least 2n−1 . Then
the number of connected components of Γ does dot exceed (k/2)n−1 . Hence g has not more than
n−1
2(k/2)
extensions. N
n

Theorem 1. If k ≥ 5 and n ≥ 2 then Q(n, k) ≤ 2ck (k−2) , where ck =

log2 k!
k−2

+

k
k−4 .

Proof. The number of partial n-ary quasigroups g : Σn−1 × B → Σ, where |Σ| = k,
B = Σ \ {a, b}, does not exceed Q(n, k)k−2 . From Lemma 1 we have
n

Q(n + 1, k) ≤ Q(n, k)k−2 2(k/2) .

(1)

Denote αn = log2 Q(n, k)/(k − 2)n . Then from (1) we have
n

k
.
αn+1 ≤ αn +
2(k − 2)
Since α1 =

log2 k!
k−2

and

∞ 
P

n=1

k
2(k−2)

n

=

k
k−4 ,

we get αn ≤

2

log2 k!
k−2

+

k
k−4 .

N

3. A lower bound
Let a and b be two different elements of Σ. By {a, b}-component of an n-ary quasigroupf
we will mean such a set S ⊂ Σn that 1) f (S) = {a, b} and 2) the function


f (x̄) whenever x̄ 6∈ S,
g(x̄) = b
whenever x̄ ∈ S and f (x̄) = a,


a
whenever x̄ ∈ S and f (x̄) = b

is also an n-ary quasigroup. In this case we will say that g is obtained from f by switching
the component S. We note that in the definition of an {a, b}-component the condition 2) can
be replaced by Property (A) from the previous section. It is obvious that switching disjoint
components can be performed independently:
Proposition 2. Let S and S 0 be disjoint {a, b}- and {c, d}- (respectively) components of an
n-ary quasigroup f . Let an n-ary quasigroup g is obtained from f by switching S. Then S 0 is
a {c, d}-component of g too.
The following proposition can be easily derived from the definition of an {a, b}-component;
similar statement can be found in [5].

Proposition 3. Let C = {c1 , d1 } × {c2 , d2 } be an {a, b}-component of a 2-ary quasigroup g.
Let Ci be a {ci , di }-component of an ni -ary quasigroup qi , i = 1, 2. Then the set C1 × C2 is an
{a, b}-component of the (n1 + n2 )-ary quasigroup f , where f (x̄1 , x̄2 ) ≡ g(q1 (x̄1 ), q2 (x̄2 )).

A 2-ary quasigroup ϕ : Σ → Σ is called idempotent iff ϕ(x, x) = x for every x ∈ Σ. It is
known (see, e.g., [1]) that
Proposition 4. For every m ≥ 3 there exists an idempotent 2-ary quasigroup of order m.

The following proposition presents a construction of 2-ary quasigroups, which will be used
to establish a lower bound on the number of n-ary quasigroups of odd order.

Proposition 5. For any m ≥ 3 there exists a 2-ary quasigroup ψ of order 2m + 1 that has m
{2i, 2i + 1}-components for every i ∈ {0, . . . , m − 1}; moreover, all except one {2i, 2i + 1}-components have form {2j, 2j + 1} × {2l, 2l + 1}.

Proof. By Proposition 4 there exists an idempotent 2-ary quasigroup ϕm of order m. For
each a, b ∈ {0, . . . , m − 1}, a 6= b, and δ, σ ∈ {0, 1} define
ψ(2a + δ, 2b + σ) = 2ϕm (a, b) + (δ + σ mod 2);
ψ(2a + δ, 2a + δ) = 2a + 1 − δ;
ψ(2a + δ, 2a + 1 − δ) = k − 1;
ψ(k − 1, 2a + δ) = ψ(2a + δ, k − 1) = 2a + δ;
ψ(k − 1, k − 1) = k − 1.
Straightforwardly, ψ is a 2-ary quasigroup that satisfied the desired properties. N
The following is examples of the value tables of a 2-ary quasigroup ϕ4 and the corresponding
ψ:

3

1 8 4 5 6 7 2 3
8 0 5 4 7 6 3 2
6 7 3 8 0 1 4 5
0 2 3 1
7 6 8 2 1 0 5 4
3 1 0 2
2 3 6 7 5 8 0 1
ϕ4 :
ψ:
1 3 2 0
3 2 7 6 8 4 1 0
2 0 1 3
4 5 0 1 2 3 7 8
5 4 1 0 3 2 8 6
0 1 2 3 4 5 6 7
From Proposition 1 it is easy to conclude that the odd-order
in Proposition 5 has the maximal number of mutually disjoint
quasigroups of the same order.

0
1
2
3
4
5
6
7
8
2-ary quasigroup constructed
components among all 2-ary

Theorem 2. If k is an odd integer ,k ≥ 5, and n ≥ 2, then
n−1
n+1
k−3 b 2 c k−1 d 2 e
k−3 n/2 k−1 n/2
(
)
)
(
2
2
Q(n, k) ≥ 2
> 2( 2 ) ( 2 ) .

Proof. Let ψ be the 2-ary quasigroup of order k constructed in Proposition 5. Define the
n-ary quasigroup Ψn by the following recurrent equalities:
Ψ2 ≡ ψ;
Ψ2m+1 (x, y) = ψ(Ψ2m (x), y);
Ψ2m+2 (x, y, z) = ψ(Ψ2m (x), ψ(y, z)).
Denote by αn the number of {2i, 2i + 1}-components of Ψn where i ∈ {0, . . . , k−3
2 }. From
k−1
k−1
k−3
Propositions 3 and 5 we have the relations α2 = 2 , α2m+1 ≥ α2m 2 , α2m+2 ≥ α2m k−3
2
2 .




k−3 m−1 k−1 m
k−3 m k−1 m
Then α2m ≥ 2
and α2m+1 ≥ 2
.
2
2
Since {2i, 2i+1}-components with different i are disjoint, the number of disjoint components
is at least k−1
2 αn . From Proposition 2 we deduce that we can get the desired number of different
n-ary quasigroups of order k by switching disjoint components in Ψn . N

4. The number of different n-ary quasigroups of order 4
Denote [n] = {1, . . . , n}. An n-ary quasigroup f is called an n-ary loop iff there exists
an element e ∈ Σ, which is called an identity, such that for all i ∈ [n] and a ∈ Σ it is true
f (e . . . eae . . . e) = a. In what follows we always assume that 0 is an identity of an n-ary loop (in
i

general, an n-ary loop can have more than one identities provided n ≥ 3). Especially we note
that this agreement is essential in the treatment of the concept of the number of n-ary loops.
In particular, we have the following simple and well-known fact:
Proposition 6. Let Q0 (n, k) be the number of n-ary loops of order k. Then
Q(n, k) = k · ((k − 1)!)n Q0 (n, k).
An n-ary quasigroop f is called permutably reducible (we will omit “permutably”) iff there
exist an integer m, 2 ≤ m < n, an (n − m + 1)-ary quasigroup h, an m-ary quasigroup g ,
and a permutation σ : [n] → [n] such that

f (x1 , . . . , xn ) ≡ h g(xσ(1) , . . . , xσ(m) ), xσ(m+1) , . . . , xσ(n) .
In this section we will assume that Σ = {0, 1, 2, 3}; i.e., we will consider only the n-ary
quasigroups of order 4. It is known (see, e.g., [1]) that there are exactly four binary loops of
order 4 (one is isomorphic to the group Z2 × Z2 and three, to the group Z4 ).
4

The following statement is straightforward from the theorem in [3].
Lemma 2. Every reducible n-ary loop f of order 4 admits exactly one of the following two
representations.
f (x) = q0 (q1 (x̃1 ), ..., qm (x̃m ))
(2)
where qj are nj -ary loops; x̃j are tuples of variables xi , i ∈ Ij , where {Ij } is a partition of [n],
j = 1, . . . , m; q0 is an irreducible m-ary loop, m ≥ 3. Moreover, the partition {Ij } in such a
representation is unique for every f .
f (x) = q1 (x̃1 ) ∗ ... ∗ qk (x̃k )

(3)

where ∗ is a binary operation in one of the 4 loops, qj , j = 1, . . . , k, are nj -ary loops that are
not representable in the form qj (x̃j ) = q 0 (x̃0j ) ∗ q 00 (x̃00j ), x̃j are tuples of variables xi , i ∈ Ij , where
{Ij } is a partition of [n]. Moreover, the partition {Ij } in such a representation is unique for
every f .
By the root operation of an n-ary quasigroup f we will mean the m-ary quasigroup q0 if (2)
holds, and the binary operation ∗ if (3) holds.
Simple combinatorial calculations give the following formula for the number Fj,k of different
partitions of [n] into k subsets from which exactly ki subsets have cardinality ji , 1 ≤ i ≤ t,
0 < j1 < · · · < jt :
Fj,k =

1
n!
,
(j1 !)k1 . . . (jt !)kt k1 ! . . . kt !

(4)

where k1 + k2 + · · · + kt = k, k1 j1 + k2 j2 + · · · + kt jt = n.
Let f : Σn → Σ be an n-ary quasigroup; define the set
Sa,b (f ) , ∪{x̄ ∈ Σn : f (x̄) ∈ {a, b}}.
An n-ary loop f will be called a-semilinear, where a ∈ {1, 2, 3}, if the characteristic function
χS0,a (f ) of the set S = S0,a (f ) has the form
χS0,a (f ) (x1 , . . . , xn ) ≡

n
X
i=1

χ{0,a} (xi ) mod 2.

(5)

An n-ary loop f is called linear if it is a-semilinear and b-semilinear for some different a and b
from {1, 2, 3}. It is not difficult to check the following:
Proposition 7. One of the four binary loops of order 4 is linear (the one that is isomorphic to
Z2 × Z2 ); the other three are 1-, 2-, and 3- semilinear respectively.
It is known (see [9]) that

Proposition 8. A linear n-ary loop is unique and is 1-, 2-, and 3- semilinear.
It is not difficult to see (see also [9]) the following:
Proposition 9. Let f be a reducible a-semilinear n-ary loop; then f can be represented as the
composition (2) or (3) of a-semilinear loops.
Let us denote by `an the number of the a-semilinear n-ary loops and by `n the number of the
semilinear n-ary loops.
As established in [9], the number of the n-ary loops asymptotically coincides with `n , which
can be easily calculated:
5

Lemma 3 ([9]). `n = 3 · 22

n −n−1

n −n−1

− 2, `an = 22

for a ∈ {1, 2, 3}.

In [4] the set of n-ary quasigroups of order 4 was characterized in the terms defined above;
namely, the following was proved:
Theorem 3. Every n-ary loop of order 4 is reducible or semilinear.
This fact gives a base for deriving a recurrent formula for the number of n-ary loops (and
quasigroups) of order 4.
We will use the following notation:
vn is the number of the n-ary loops (of order 4);
rn∗ is the number of the n-ary loops with the binary root operation ∗ (all of them are reducible
except ∗ itself);
rn0 is the number of the reducible n-ary loops with the root operation of arity at least 3;
rna∗ is the number of the a-semilinear n-ary loops with the a-semilinear binary root operation
∗ (all of them are reducible except ∗ itself);
rna0 is the number of the reducible a-semilinear n-ary loops with the root operation of arity
at least 3;
pan is the number of irreducible a-semilinear n-ary loops;
pn is the number of irreducible n-ary loops.
From Lemma 2 and Proposition 9, the following relations follow:
rna∗

=

n X
X

Fj,k (`aj1 − rja∗
)k1 · · · (`ajt − rja∗
)kt ,
t
1

n X
X

Fj,k (vj1 − rj∗1 )k1 · · · (vjt − rj∗t )kt ,

i=2 j̄,k̄

rn∗

=

i=2 j̄,k̄

rna0

=

n−1
X

pai

i=3

rn0

=

n−1
X
i=3

pi

X
j̄,k̄

X
j̄,k̄

Fj,k (`aj1 )k1 · · · (`ajt )kt ,

Fj,k (vj1 )k1 · · · (vjt )kt ,

where the second sum os over the tuples k̄ = (k1 , . . . , kt ) and j̄ = (j1 , . . . , jt ) of positive integers
satisfying k1 + · · · + kt = i, k1 j1 + k2 j2 + · · · + kt jt = n and j1 < · · · < jt . From Theorem 3
and Proposition 8 we have vn = pn + rn0 + 4rn∗ , pan = `an − rna0 − 2rna∗ , pn = 3pan . From Lemma 3,
n
`an = 22 −n−1 for a ∈ {1, 2, 3}.
The initial values are trivial: r1a∗ = r1∗ = r1a0 = r10 = 0. We see that the equalities above and
Proposition 6 provide a recurrent way of calculation of the number of the n-ary quasigroups of
order 4.
Finally, we list the first eight values of Q0 (n, 4):
1,
4,
64,
7132,
201538000,
432345572694417712,
3987683987354747642922773353963277968,
6

678469272874899582559986240285280710364867063489779510427038722229750276832,
and of Q(n, 4):
24,
576,
55296,
36972288,
6268637952000,
80686060158523011084288,
4465185218736554544676917926460256725000192,
4558271384916189349044295395852008182480786230841798008741684281906576963885826048.
The program on python to calculate these numbers can be found in the appendix.

5. Conclusion
We will briefly discuss a connection of our topic with the known concept of latin traid. A
partial n-ary quasigroup t : Ω → Σ, Ω ⊂ Σn is called a multidimensional latin trade, here for
briefity simply trade iff there exist another partial n-ary quasigroup t0 : Ω → Σ such that
1) t(x̄) 6= t0 (x̄) for all x̄ ∈ Ω;
2) for any i from 1 to n and any admissible values x1 , . . . , xi−1 , xi−1 , . . . , xn the sets
{t(x1 , . . . , xi−1 , y, xi−1 , . . . , xn ) | y ∈ Σ} and {t0 (x1 , . . . , xi−1 , y, xi−1 , . . . , xn ) | y ∈ Σ} coincide.
In this case the pair (t, t0 ) is called a bitrade (depending on the context, bitrades are considered either as ordered, or as unordered pairs); the trade t0 is called a mate of t. In the case
n = 2 bitrades (latin bitrades) are widely studied, see the survey [2].
We will say that an n-ary quasigroup f has a trade t iff t = f |Ω for some Ω. As follows
from the definitions, replacing of the values of f in Ω by the values of a mate t0 of t results in
another n-ary quasigroup. We will say that trades t = f |Ω and s = f |Θ are independent iff their
supports Ω and Θ are disjoint. The maximal number of mutually independent trades of an n-ary
quasigroup f will be called its trade number trd(f ). Denote by Trd(n, k) the maximum of trd(f )
over the all n-ary quasigroups f of order k. Since independent trades of an n-ary quasigroup
can be independently replaced by mates, the number Q(n, k) of different n-ary quasigroups of
order k satisfies
Q(n, k) ≥ 2Trd(n,k) .
(6)
It is easy to understand that the lower bound in Section 3 (as well as all the bounds in [5]) is
derived by this way: {a, b}-component is the support of some trade by definitions. Since the
support of a trade satisfies Property (A), Proposition 1 implies Trd(n, k) ≤ k n /2n = 2(log2 k−1)n ;
moreover, for even k the equality is easily proved. For odd k, as follows from the results of
Section 3, we have Trd(n, k) ≥ 2c(k)n where c(k) −→ log2 k − 1. But for fixed k, in particular,
k→∞

for the small values 5, 7, . . . , the question about the asymptotics of Trd(n, k) remains open.

Problem 1. Establish the asymptotics of the logarithm and the asymptotics of the value
Trd(n, k) as n → ∞ for odd k ≥ 5.

Another question is how the estimation (6) close to the real value. For the order 4 it is
asymptotically tight in logarithms. For any larger fixed order the asymptotics of log log Q(n, k)
is unknown. It is natural to conjecture that the asymptotics of log log Q(n, k) and log Trd(n, k)
coincide.




Problem 2. Is it true that lim log2 logn2 Q(n,k) = lim log2 Trd(n,k)
? In particular, is it true
n
n→∞

n→∞

7

that lim

n→∞



log2 log2 Q(n,k)
n



≤ log2 k − 1?

Even the existence of these limits is not proved yet.

References
1. V. D. Belousov. Foundations of Quasigroup and Loop Theory. Nauka, Moscow, 1967. In
Russian.
2. N. J. Cavenagh. The theory and application of latin bitrades: A survey. Mathematica Slovaca,
58(6):691–718, 2008. DOI: 10.2478/s12175-008-0103-2.
3. A. V. Cheremushkin. Canonical decomposition of n-ary quasigroups. volume 102 of Mat.
Issled., pages 97–105. Shtiintsa, Kishinev, 1988. In Russian.
4. D. S. Krotov and V. N. Potapov. n-Ary quasigroups of order 4. SIAM J. Discrete Math.,
23(2):561–570, 2009. DOI: 10.1137/070697331.
5. D. S. Krotov, V. N. Potapov, and P. V. Sokolova. On reconstructing reducible n-ary quasigroups and switching subquasigroups. Quasigroups Relat. Syst., 16(1):55–67, 2008.
6. B. D. McKay and I. M. Wanless. On the number of Latin squares. Ann. Comb., 9(3):335–334,
2005. DOI: 10.1007/s00026-005-0261-7.
7. B. D. McKay and I. M. Wanless. A census of small Latin hypercubes. SIAM J. Discrete
Math., 22(2):719–736, 2008. DOI: 10.1137/070693874.
8. V. N. Potapov. An upper estimation of the number of n-quasigroups of finite order. In Proceedings of the XVII International School-Seminar “Synthesis and Complexity of Controlling
Systems”, pages 136–137, Novosibirsk, Russia, October–November 2008. In Russian.
9. V. N. Potapov and D. S. Krotov. Asymptotics for the number of n-quasigroups of order
4. Sib. Math. J., 47(4):720–731, 2006. DOI: 10.1007/s11202-006-0083-9 translated from Sib.
Mat. Zh. 47(4) (2006), 873-887.

8

A. Appendix. The numbers Q(n, 4) and Q0 (n, 4): program
# PYTHON program
# do not forget leading spaces!
N=12 \# the maximum arity to calculate
P=[[{}]]+[[] for x in [0]*N]
for n in range(N):
for Po in P[n]:
for j in range(N-n-sum(Po.values())+1):
Pn={i+1:Po[i] for i in Po}
if j>0: Pn.update({1:j})
if n+j>0: P[n+sum(Po.values())+j]+=[Pn]
\# now P[n] is a list of partitions of n into positive summands:
\# E.g., 16==1*3+2*4+5*1==(1+1+1)+(2+2+2+2)+(5) is saved as P[16][51]=={1:3, 2:4, 5:1}
for Pn in P: Pn.pop()

\# remove trivial 1-partitions

from math import factorial
mul = lambda a,b:a*b
Aut = lambda Pt:reduce(mul,[factorial(Pt[nu])*factorial(nu)**Pt[nu] for nu in Pt], 1)
F=[[factorial(n)/Aut(Pt) for Pt in P[n]] for n in range(N+1)]
\# F[n][i] is the number of partitions of an n-set
\# that correspond to the partition P[n][i] of n.
La=[2L**(2**n-n-1) for n in range(N+1)]
Ras,Ra0,R_0,R_s,P_a,V,T = [0,0L],[0, 0L],[0,0L],[0,0L],[0,0L],[1,1L],[4,24L]
for n in range(2, N+1):
V+=[0L]; T+=[0L]; P_a+=[0L]; Ras+=[0L]; Ra0+=[0L]; R_0+=[0L]; R_s+=[0L]
for i in range(len(P[n])):
R_0[n], Ra0[n], R_s[n], Ras[n] = map(lambda A, B, C :
A[n] + reduce(mul,[(B[nu]-C*A[nu])**P[n][i][nu] for nu in P[n][i]],1)
*((1-C)*P_a[sum(P[n][i].values())]+C)*F[n][i],
(R_0, Ra0, R_s, Ras), (V, La, V, La), (0, 0, 1, 1))
R_0[n] *= 3
P_a[n] = La[n] - Ra0[n] - 2*Ras[n]
V[n] = 3*P_a[n] + R_0[n] + 4*R_s[n]
T[n] = 4*(6**n)*V[n]
print "\n Reduced (A211214):", V
print "\n Total (A211215):", T

9

О числе 𝑛-арных квазигрупп конечного порядка*

arXiv:0912.5453v2 [math.CO] 8 Feb 2016

В. Н. Потапов⋆ , Д. С. Кротов⋆

⋆ Институт

математики им. С. Л. Соболева СО РАН,
проспект Академика Коптюга 4, Новосибирск
Механико-математический факультет, Новосибирский государственный университет,
ул. Пирогова 2, Новосибирск
Аннотация
Пусть 𝑄(𝑛, 𝑘) — число 𝑛-арных квазигрупп порядка 𝑘. Получена рекуррентная формула для чисел 𝑄(𝑛, 4). Доказано, что при любых 𝑛 ≥ 2 и 𝑘 ≥ 5 справедливы неравен(︀
)︀ 𝑛2 (︀ 𝑘−1 )︀ 𝑛2
ства 𝑘−3
< log2 𝑄(𝑛, 𝑘) ≤ 𝑐𝑘 (𝑘 − 2)𝑛 , где 𝑐𝑘 не зависит от 𝑛. Таким образом,
2
2
верхняя асимтотическая граница для чисел 𝑄(𝑛, 𝑘) улучшена при любых 𝑘 ≥ 5, нижняя — при нечётных 𝑘 ≥ 7.
Ключевые слова: 𝑛-арная квазигруппа, латинский куб, лупа, асимптотика, компонента, латинский трэйд.

УДК: 519.143
MSC2010: 20N15, 05B15

1. Введение
Алгебраическая система из множества Σ мощности |Σ| = 𝑘 и 𝑛-арной операции
𝑓 : Σ𝑛 → Σ называется 𝑛-арной квазигруппой порядка 𝑘, если унарная операция, полученная фиксацией любых 𝑛 − 1 аргументов операции 𝑓 любыми значениями из Σ, всегда
является биекцией. Принято называть 𝑛-арной квазигруппой порядка 𝑘 или 𝑛-квазигруппой
порядка 𝑘 также и соответствующую функцию 𝑓 (таблица значений такой функции известна
под названием латинский гиперкуб, в случае 𝑛 = 2 — латинский квадрат).
Зафиксируем множество элементов Σ = {0, 1, . . . , 𝑘 − 1}. Обозначим через 𝑄(𝑛, 𝑘) число
различных 𝑛-арных квазигрупп порядка 𝑘 (при фиксированном Σ)1 . Известно, что для
каждого 𝑛 существует только две 𝑛-арных квазигруппы порядка 2. Имеется 𝑄(𝑛, 3) = 3 ·
2𝑛 различных 𝑛-арных квазигрупп порядка 3, которые составляют единственный класс
𝑛
эквивалентности. В [1] доказано асимптотическое равенство 𝑄(𝑛, 4) = 3𝑛+1 22 +1 (1 + 𝑜(1))
при 𝑛 → ∞. В настоящей работе (раздел 4) предложен рекуррентный способ вычисления
чисел 𝑄(𝑛, 4), выписаны первые 8 значений этой величины. Ранее были известны только
пять первых значений 𝑄(𝑛, 4), кроме того, известны числа 𝑄(𝑛, 5) и 𝑄(𝑛, 6) для 𝑛 ≤ 5 и
𝑛 ≤ 3 соответственно, см. [9], и число 𝑄(2, 𝑘) при 𝑘 ≤ 11, см. работу [8] и библиографию в
ней.
*

Работа выполнена при поддержке ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009–2013 гг. (гос. контракт № 02.740.11.0429) и Российского фонда фундаментальных исследований
(проекты 08-01-00671, 08-01-00673).
1
Иногда под числом квазигрупп подразумевают число попарно неизоморфных квазигрупп.

1

Асимптотика числа и даже логарифма числа (и даже логарифма логарифма числа)
𝑛-арных квазигрупп порядков больше 4 неизвестна. В [7] получены следующие нижние
𝑛/3
𝑛
𝑛
оценки 𝑄(𝑛, 5) ≥ 23 −𝑐 , где 𝑐 < 0.072; 𝑄(𝑛, 𝑘) ≥ 2(𝑘/2) если 𝑘 чётно; 𝑄(𝑛, 𝑘) ≥ 2𝑛(𝑘/3) если
𝑛
𝑘 кратно трём; 𝑄(𝑛, 𝑘) ≥ 21.5⌊𝑘/3⌋ для произвольного 𝑘. В [4] была предложена верхняя
𝑛
𝑛−1
оценка числа 𝑛-арных квазигрупп порядка 𝑘: 𝑄(𝑛, 𝑘) ≤ 3(𝑘−2) 2𝑛(𝑘−2) .
В настоящей статье усилена верхняя оценка (раздел 2) числа 𝑛-арных квазигрупп конечного порядка и нижняя оценка (раздел 3) числа 𝑛-арных квазигрупп нечётного порядка:
)︂ 𝑛 (︂
)︂ 𝑛
(︂
𝑘−3 2 𝑘−1 2
< log2 𝑄(𝑛, 𝑘) ≤ 𝑐𝑘 (𝑘 − 2)𝑛 ,
2
2
где 𝑐𝑘 не зависит от 𝑛, точнее, 𝑐𝑘 =

log2 𝑘!
𝑘−2

+

𝑘
𝑘−4 .

2. Верхняя оценка
Будем говорить, что множество 𝑀 ⊆ Σ𝑛 удовлетворяет свойству (A), если для любого элемента 𝑥
¯ из 𝑀 и каждой позиции 𝑖 = 1, . . . , 𝑛 найдется другой элемент 𝑦¯ из 𝑀 ,
отличающийся от 𝑥
¯ только в позиции 𝑖. По индукции легко получить следующее:
Предложение 1. Любое непустое подмножество 𝐶 ⊆ Σ𝑛 , удовлетворяющее свойству (A),
имеет мощность не менее 2𝑛 .
Частичной 𝑛-арной квазигруппой порядка |Σ| называется функция 𝑔 : Ω → Σ, где Ω ⊂
𝑛
Σ , удовлетворяющая следующему свойству: 𝑔(𝑥) ̸= 𝑔(𝑦) для любых двух наборов 𝑥, 𝑦 ∈ Ω,
отличающихся ровно в одной позиции. Будем говорить, что 𝑛-арная квазигруппа 𝑓 : Σ𝑛 → Σ
является продолжением частичной 𝑛-арной квазигруппы 𝑔 : Ω → Σ, где Ω ⊂ Σ𝑛 , если
𝑓 |Ω ≡ 𝑔.

Лемма 1. Пусть |Σ| = 𝑘, 𝐵 = Σ ∖ {𝑎, 𝑏}, 𝑘 ≥ 3, 𝑎, 𝑏 ∈ Σ. Тогда частичная 𝑛-арная квазиг𝑛−1
руппа 𝑔 : Σ𝑛−1 × 𝐵 → Σ имеет не более чем 2(𝑘/2)
различных продолжений.
Доказательство.
Пусть 𝑃 — множество неупорядоченных пар элементов множества Σ. Рассмотрим частичную 𝑛-арную квазигруппу 𝑔 : Σ𝑛−1 × 𝐵 → Σ. Определим функцию 𝐺 : Σ𝑛−1 → 𝑃
равенством 𝐺(𝑥) = Σ ∖ {𝑔(𝑥𝑐) : 𝑐 ∈ Σ ∖ {𝑎, 𝑏}}. Определим граф Γ = ⟨Σ𝑛−1 , 𝐸⟩, в котором
две вершины 𝑥 и 𝑦 соединены ребром тогда и только тогда, когда наборы 𝑥 и 𝑦 отличаются
только в одной позиции и 𝐺(𝑥) ∩ 𝐺(𝑦) ̸= ∅. Нетрудно видеть, что компоненты связности
графа Γ удовлетворяют свойству (A).
Пусть 𝑛-арные квазигруппы 𝑓1 и 𝑓2 являются продолжениями частичной 𝑛-арной квазигруппы 𝑔. Нетрудно видеть, что {𝑓1 (𝑥𝑎), 𝑓1 (𝑥𝑏)} = 𝐺(𝑥) для любого 𝑥 ∈ Σ𝑛−1 , причём если
𝑓1 (𝑥𝑎) = 𝑓2 (𝑥𝑎), то продолжения 𝑓1 и 𝑓2 совпадают на всей компоненте связности графа Γ,
содержащей вершину 𝑥 ∈ Σ𝑛−1 . Таким образом, для однозначного определения продолжения частичной 𝑛-арной квазигруппы 𝑔 достаточно зафиксировать одно из двух возможных
значений в каждой компоненте связности графа Γ. Из предложения 1 следует, что каждая
компонента связности имеет мощность не менее 2𝑛−1 . Тогда число компонент связности
𝑛−1
графа Γ не превосходит (𝑘/2)𝑛−1 . А значит, 𝑔 имеет не более 2(𝑘/2)
продолжений. N
𝑛

Теорема 1. Если 𝑘 ≥ 5 и 𝑛 ≥ 2, то 𝑄(𝑛, 𝑘) ≤ 2𝑐𝑘 (𝑘−2) , где 𝑐𝑘 =

log2 𝑘!
𝑘
𝑘−2 + 𝑘−4 .
: Σ𝑛−1 ×𝐵 →

Доказательство. Число частичных 𝑛-арных квазигрупп 𝑔
𝐵 = Σ ∖ {𝑎, 𝑏} не превосходит 𝑄(𝑛, 𝑘)𝑘−2 . Из леммы 1 следует неравенство
𝑛

𝑄(𝑛 + 1, 𝑘) ≤ 𝑄(𝑛, 𝑘)𝑘−2 2(𝑘/2) .
2

Σ, где |Σ| = 𝑘,
(1)

Введём обозначение 𝛼𝑛 = log2 𝑄(𝑛, 𝑘)/(𝑘 − 2)𝑛 . Тогда из неравенства (1) имеем
)︂𝑛
(︂
𝑘
.
𝛼𝑛+1 ≤ 𝛼𝑛 +
2(𝑘 − 2)
Поскольку 𝛼1 =

log2 𝑘!
𝑘−2

и

∞ (︁
∑︀

𝑛=1

𝑘
2(𝑘−2)

)︁𝑛

=

𝑘
𝑘−4 ,

имеем 𝛼𝑛 ≤

log2 𝑘!
𝑘−2

+

𝑘
𝑘−4 .

N

3. Нижняя оценка
Пусть 𝑎 и 𝑏 — два различных элемента из Σ. {𝑎, 𝑏}-Компонентой 𝑛-арной квазигруппы
𝑓 будем называть такое множество 𝑆 ⊂ Σ𝑛 , что 1) 𝑓 (𝑆) = {𝑎, 𝑏} и 2) функция
⎧
⎪
𝑥) при 𝑥
¯ ̸∈ 𝑆,
⎨𝑓 (¯
𝑔(¯
𝑥) = 𝑏
при 𝑥
¯ ∈ 𝑆 и 𝑓 (¯
𝑥) = 𝑎,
⎪
⎩
𝑎
при 𝑥
¯ ∈ 𝑆 и 𝑓 (¯
𝑥) = 𝑏.

также является 𝑛-арной квазигруппой. В этом случае будем говорить, что 𝑔 получена из
𝑓 свитчингом компоненты 𝑆. Заметим, что в определении {𝑎, 𝑏}-компоненты условие 2)
можно заменить свойством (A) из предыдущего раздела. Очевидно, что свитчинг непересекающихся компонент можно производить независимо:
Предложение 2. Пусть 𝑆 и 𝑆 ′ — непересекающиеся {𝑎, 𝑏}- и {𝑐, 𝑑}- (соответственно) компоненты 𝑛-арной квазигруппы 𝑓 и 𝑛-арная квазигруппа 𝑔 получена из 𝑓 свитчингом компоненты 𝑆. Тогда 𝑆 ′ также является {𝑐, 𝑑}-компонентой квазигруппы 𝑔.
Следующее предложение нетрудно получить из определения {𝑎, 𝑏}-компоненты, аналогичное утверждение имеется в [7].

Предложение 3. Пусть множество 𝐶 = {𝑐1 , 𝑑1 } × {𝑐2 , 𝑑2 } является {𝑎, 𝑏}-компонентой
2-квазигруппы 𝑔. Пусть множество 𝐶𝑖 является {𝑐𝑖 , 𝑑𝑖 }-компонентой 𝑛𝑖 -арной квазигруппы 𝑞𝑖 при 𝑖 = 1, 2. Тогда множество 𝐶1 × 𝐶2 является {𝑎, 𝑏}-компонентой (𝑛1 + 𝑛2 )-арной
квазигруппы 𝑓 , где 𝑓 (¯
𝑥1 , 𝑥
¯2 ) ≡ 𝑔(𝑞1 (¯
𝑥1 ), 𝑞2 (¯
𝑥2 )).
2-Квазигруппа 𝜙 : Σ → Σ называется идемпотентной, если 𝜙(𝑥, 𝑥) = 𝑥 для любого
𝑥 ∈ Σ. Известно (см., например, [2]), что верно
Предложение 4. Для любого 𝑚 ≥ 3 имеется идемпотентная 2-квазигруппа порядка 𝑚.

В следующем предложении приведена конструкция 2-квазигрупп, которая будет использована при доказательстве нижней оценки числа 𝑛-арных квазигрупп нечётного порядка.
Предложение 5. Для любого 𝑚 ≥ 3 найдётся 2-квазигруппа 𝜓 порядка 2𝑚 + 1, имеющая
𝑚 {2𝑖, 2𝑖 + 1}-компонент для каждого 𝑖 ∈ {0, . . . , 𝑚 − 1}, причём все кроме одной {2𝑖, 2𝑖 + 1}компоненты имеют вид {2𝑗, 2𝑗 + 1} × {2𝑙, 2𝑙 + 1}.

Доказательство. По предложению 4 найдётся идемпотентная 2-квазигруппа 𝜙𝑚 порядка 𝑚. Для любых 𝑎, 𝑏 ∈ {0, . . . , 𝑚 − 1}, 𝑎 ̸= 𝑏, и 𝛿, 𝜎 ∈ {0, 1} определим
𝜓(2𝑎 + 𝛿, 2𝑏 + 𝜎) = 2𝜙𝑚 (𝑎, 𝑏) + (𝛿 + 𝜎 mod 2);
𝜓(2𝑎 + 𝛿, 2𝑎 + 𝛿) = 2𝑎 + 1 − 𝛿;
𝜓(2𝑎 + 𝛿, 2𝑎 + 1 − 𝛿) = 𝑘 − 1;
𝜓(𝑘 − 1, 2𝑎 + 𝛿) = 𝜓(2𝑎 + 𝛿, 𝑘 − 1) = 2𝑎 + 𝛿;
𝜓(𝑘 − 1, 𝑘 − 1) = 𝑘 − 1.
3

Непосредственная проверка показывает, что 𝜓 есть 2-квазигруппа, обладающая требуемыми свойствами. N
Ниже приведён пример таблиц значений 2-квазигруппы 𝜙4 и соответствующей 𝜓:
1 8 4 5 6 7 2 3 0
8 0 5 4 7 6 3 2 1
6 7 3 8 0 1 4 5 2
0 2 3 1
7 6 8 2 1 0 5 4 3
3 1 0 2
2 3 6 7 5 8 0 1 4
𝜙4 :
𝜓:
1 3 2 0
3 2 7 6 8 4 1 0 5
2 0 1 3
4 5 0 1 2 3 7 8 6
5 4 1 0 3 2 8 6 7
0 1 2 3 4 5 6 7 8
Из предложения 1 нетрудно заключить, что 2-квазигруппа нечётного порядка 𝑘, построенная в предложении 5, имеет максимальное число непересекающихся компонент среди всех
2-квазигрупп порядка 𝑘.
Теорема 2. Если 𝑘 ≥ 5 — нечётное и 𝑛 ≥ 2, то
𝑛−1
𝑛+1
𝑘−3 ⌊ 2 ⌋ 𝑘−1 ⌈ 2 ⌉
𝑘−3 𝑛/2 𝑘−1 𝑛/2
( 2 )
𝑄(𝑛, 𝑘) ≥ 2( 2 )
> 2( 2 ) ( 2 ) .

Доказательство. Пусть 𝜓 – 2-квазигруппа порядка 𝑘, построенная в предложении 5.
Определим рекуррентно 𝑛-арную квазигруппу Ψ𝑛 равенствами:
Ψ2 ≡ 𝜓;
Ψ2𝑚+1 (𝑥, 𝑦) = 𝜓(Ψ2𝑚 (𝑥), 𝑦);
Ψ2𝑚+2 (𝑥, 𝑦, 𝑧) = 𝜓(Ψ2𝑚 (𝑥), 𝜓(𝑦, 𝑧)).
Обозначим через 𝛼𝑛 — число {2𝑖, 2𝑖 + 1}-компонент 𝑛-арной квазигруппы Ψ𝑛 , где 𝑖 ∈
𝑘−3
{0, . . . , 𝑘−3
3 и 5 имеем соотношения 𝛼2 = 𝑘−1
2 }. Из предложений
2 , 𝛼)︀2𝑚+1 ≥ 𝛼2𝑚 2 , 𝛼2𝑚+2 ≥
(︀
)︀
(︀
)︀
(︀
)︀
(︀
𝑚−1
𝑚
𝑚
𝑚
𝑘−1
𝑘−3
𝑘−1
𝑘−1
и 𝛼2𝑚+1 ≥ 𝑘−3
.
𝛼2𝑚 𝑘−3
2
2 . Тогда 𝛼2𝑚 ≥
2
2
2
2
Поскольку {2𝑖, 2𝑖 + 1}-компоненты при различных 𝑖 не пересекаются, всего непересекающихся компонент не меньше, чем 𝑘−1
2 𝛼𝑛 . Из предложения 2 следует, что из 𝑛-арной квазигруппы Ψ𝑛 свитчингами непересекающихся компонент можно получить требуемое число
различных 𝑛-арных квазигрупп порядка 𝑘. N

4. Число 𝑛-арных квазигрупп порядка 4
Введём обозначение [𝑛] = {1, . . . , 𝑛}. 𝑛-Арная квазигруппа 𝑓 называется 𝑛-арной лупой,
если существует такой элемент 𝑒 ∈ Σ, называемый единичным, что для всех 𝑖 ∈ [𝑛] и
𝑎 ∈ Σ имеет место равенство 𝑓 (𝑒 . . . 𝑒𝑎𝑒 . . . 𝑒) = 𝑎. Далее мы всегда будем подразумевать,
𝑖

что 0 является единичным элементом 𝑛-арной лупы (в общем случае могут быть и другие
единичные элементы). Особо отметим, что данное соглашение существенно в интерпретации
понятия числа 𝑛-арных луп. В частности, имеем следующий простой и хорошо известный
факт:
Предложение 6. Пусть 𝑄′ (𝑛, 𝑘) — число 𝑛-арных луп порядка 𝑘. Тогда
𝑄(𝑛, 𝑘) = 𝑘 · ((𝑘 − 1)!)𝑛 𝑄′ (𝑛, 𝑘).

4

𝑛-Арная квазигруппа 𝑓 называется разделимой (приводимой), если найдутся: целое число 𝑚, 2 ≤ 𝑚 < 𝑛, (𝑛 − 𝑚 + 1)-арная квазигруппа ℎ, 𝑚-арная квазигруппа 𝑔 и перестановка 𝜎 : [𝑛] → [𝑛] — такие, что
(︀
)︀
𝑓 (𝑥1 , . . . , 𝑥𝑛 ) ≡ ℎ 𝑔(𝑥𝜎(1) , . . . , 𝑥𝜎(𝑚) ), 𝑥𝜎(𝑚+1) , . . . , 𝑥𝜎(𝑛) .

В дальнейшем будем предполагать, что Σ = {0, 1, 2, 3}, т. е. речь пойдёт только об 𝑛арных квазигруппах порядка 4. Известно (см., например, [2]), что имеется ровно четыре
бинарные лупы порядка 4 (одна изоморфна группе 𝑍2 × 𝑍2 и три — группе 𝑍4 ).
Следующее утверждение является прямым следствием теоремы из [3].
Лемма 2. Для разделимой 𝑛-арной лупы 𝑓 порядка 4 справедливо одно и только одно из
двух представлений.
𝑓 (𝑥) = 𝑞0 (𝑞1 (˜
𝑥1 ), ..., 𝑞𝑚 (˜
𝑥𝑚 )),
(2)

где 𝑞𝑗 есть 𝑛𝑗 -арные лупы при 𝑗, 1 ≤ 𝑗 ≤ 𝑚, 𝑞0 есть неразделимая 𝑚-арная лупа, 𝑚 ≥ 3,
𝑥
˜𝑗 — некоторые наборы переменных 𝑥𝑖 , 𝑖 ∈ 𝐼𝑗 , где {𝐼𝑗 } — разбиение множества [𝑛]. Причём
в данном представлении разбиение {𝐼𝑗 } единственно.
𝑓 (𝑥) = 𝑞1 (˜
𝑥1 ) * ... * 𝑞𝑘 (˜
𝑥𝑘 ),

(3)

где * есть бинарная операция в одной из 4 луп, 𝑞𝑗 есть 𝑛𝑗 -арные лупы при 𝑗, 1 ≤ 𝑗 ≤
𝑘, непредставимые в виде 𝑞𝑗 (˜
𝑥𝑗 ) = 𝑞 ′ (˜
𝑥′𝑗 ) * 𝑞 ′′ (˜
𝑥′′𝑗 ), 𝑥
˜𝑗 — некоторые наборы переменных 𝑥𝑖 ,
𝑖 ∈ 𝐼𝑗 , где {𝐼𝑗 } — разбиение множества [𝑛]. Причём в данном представлении разбиение {𝐼𝑗 }
единственно.
Корневой операцией 𝑛-арной квазигруппы 𝑓 будем называть 𝑚-арную квазигруппу 𝑞0 ,
если имеет место представление (2), и бинарную операцию *, если имеет место представление (3).
Простой комбинаторный подсчёт показывает, что число 𝐹𝑗,𝑘 различных разбиений множества [𝑛] на 𝑘 подмножеств, из которых 𝑘𝑖 подмножеств имеет мощность 𝑗𝑖 , 1 ≤ 𝑖 ≤ 𝑡,
0 < 𝑗1 < · · · < 𝑗𝑡 , удовлетворяет равенству
𝐹𝑗,𝑘 =

(𝑗1

!)𝑘1

1
𝑛!
,
𝑘
𝑡
. . . (𝑗𝑡 !) 𝑘1 ! . . . 𝑘𝑡 !

(4)

где 𝑘1 + 𝑘2 + · · · + 𝑘𝑡 = 𝑘, 𝑘1 𝑗1 + 𝑘2 𝑗2 + · · · + 𝑘𝑡 𝑗𝑡 = 𝑛.
Пусть 𝑓 : Σ𝑛 → Σ — 𝑛-арная квазигруппа, определим множество
𝑆𝑎,𝑏 (𝑓 ) , {¯
𝑥 ∈ Σ𝑛 : 𝑓 (¯
𝑥) ∈ {𝑎, 𝑏}}.
𝑛-Арную лупу 𝑓 назовём 𝑎-полулинейной, где 𝑎 ∈ {1, 2, 3} если характеристическая функция
𝜒𝑆0,𝑎 (𝑓 ) множества 𝑆 = 𝑆0,𝑎 (𝑓 ) имеет вид
𝜒𝑆0,𝑎 (𝑓 ) (𝑥1 , . . . , 𝑥𝑛 ) ≡

𝑛
∑︁
𝑖=1

𝜒{0,𝑎} (𝑥𝑖 ) mod 2.

(5)

𝑛-Арная лупа 𝑓 называется линейной, если она одновременно является 𝑎-полулинейной и
𝑏-полулинейной, где 𝑎 ̸= 𝑏, 𝑎, 𝑏 ∈ {1, 2, 3}. Непосредственой проверкой нетрудно убедиться,
что справедливо
Предложение 7. Из четырёх бинарных луп порядка 4 одна (изоморфная группе 𝑍2 × 𝑍2 )
является линейной, а три остальных 1-, 2- и 3- полулинейными соответственно.
5

Известно (см. [1]), что
Предложение 8. Линейная 𝑛-арная лупа единственна и является одновременно 1-, 2- и 3полулинейной.
Нетрудно видеть (см., также, [1]), что справедливо
Предложение 9. Пусть 𝑓 — разделимая 𝑎-полулинейная 𝑛-арная лупа, тогда 𝑓 можно
представить как суперпозицию 𝑎-полулинейных луп вида (2) или (3).
Обозначим через ℓ𝑎𝑛 мощность множества 𝑎-полулинейных 𝑛-арных луп и через ℓ𝑛 мощность множества полулинейных 𝑛-арных луп.
Как было установлено в [1], мощность множества всех 𝑛-арных луп асимптотически
совпадает с мощностью множества полулинейных 𝑛-арных луп, которая легко вычисляется:
𝑛 −𝑛−1

Лемма 3 ([1]). ℓ𝑛 = 3 · 22

𝑛 −𝑛−1

− 2, ℓ𝑎𝑛 = 22

при 𝑎 ∈ {1, 2, 3}.

В [6] получено описание 𝑛-арных квазигрупп порядка 4 в определённых выше терминах,
а именно, доказана
Теорема 3. Каждая 𝑛-арная лупа порядка 4 является разделимой или полулинейной.
На этом описании по-существу основывается вывод рекуррентной формулы для числа
𝑛-арных луп (и квазигрупп) порядка 4.
Введём следующие обозначения:
𝑣𝑛 — число 𝑛-арных луп (порядка 4);
𝑟𝑛* — число 𝑛-арных луп с бинарной корневой операцией * (все такие лупы разделимы,
за исключением собственно бинарной операции *);
𝑟𝑛0 — число разделимых 𝑛-арных луп с корневой операцией арности большей либо равной
3;
𝑟𝑛𝑎* — число 𝑎-полулинейных 𝑛-арных луп с 𝑎-полулинейной бинарной корневой операцией * (все такие лупы разделимы, за исключением собственно бинарной операции *);
𝑟𝑛𝑎0 — число разделимых 𝑎-полулинейных 𝑛-арных луп с корневой операцией арности
большей либо равной 3;
𝑝𝑎𝑛 — число неразделимых 𝑎-полулинейных 𝑛-арных луп;
𝑝𝑛 — число неразделимых 𝑛-арных луп.
Из леммы 2 и предложения 9 вытекают следующие соотношения:
𝑟𝑛𝑎*

=

𝑛 ∑︁
∑︁

𝐹𝑗,𝑘 (ℓ𝑎𝑗1 − 𝑟𝑗𝑎*
)𝑘1 · · · (ℓ𝑎𝑗𝑡 − 𝑟𝑗𝑎*
)𝑘𝑡 ,
𝑡
1

𝑛 ∑︁
∑︁

𝐹𝑗,𝑘 (𝑣𝑗1 − 𝑟𝑗*1 )𝑘1 · · · (𝑣𝑗𝑡 − 𝑟𝑗*𝑡 )𝑘𝑡 ,

¯
𝑖=2 ¯
𝑗,𝑘

𝑟𝑛*

=

¯
𝑖=2 ¯
𝑗,𝑘

𝑟𝑛𝑎0

=

𝑛−1
∑︁

𝑝𝑎𝑖

𝑖=3

𝑟𝑛0

=

𝑛−1
∑︁
𝑖=3

𝑝𝑖

∑︁
¯
¯
𝑗,𝑘

∑︁
¯
¯
𝑗,𝑘

𝐹𝑗,𝑘 (ℓ𝑎𝑗1 )𝑘1 · · · (ℓ𝑎𝑗𝑡 )𝑘𝑡 ,

𝐹𝑗,𝑘 (𝑣𝑗1 )𝑘1 · · · (𝑣𝑗𝑡 )𝑘𝑡 ,

где вторая сумма берётся по наборам 𝑘¯ = (𝑘1 , . . . , 𝑘𝑡 ) и ¯𝑗 = (𝑗1 , . . . , 𝑗𝑡 ) положительных целых
чисел, удовлетворяющим равенствам 𝑘1 +· · ·+𝑘𝑡 = 𝑖, 𝑘1 𝑗1 +𝑘2 𝑗2 +· · ·+𝑘𝑡 𝑗𝑡 = 𝑛 и неравенствам
6

𝑗1 < · · · < 𝑗𝑡 . Из теоремы 3 и предложения 8 вытекают соотношения 𝑣𝑛 = 𝑝𝑛 + 𝑟𝑛0 + 4𝑟𝑛* ,
𝑛
𝑝𝑎𝑛 = ℓ𝑎𝑛 − 𝑟𝑛𝑎0 − 2𝑟𝑛𝑎* , 𝑝𝑛 = 3𝑝𝑎𝑛 . Из леммы 3 имеем ℓ𝑎𝑛 = 22 −𝑛−1 при 𝑎 ∈ {1, 2, 3}.
Начальные значения для перечисленных выше величин тривиальны: 𝑟1𝑎* = 𝑟1* = 𝑟1𝑎0 =
0
𝑟1 = 0. Нетрудно видеть, что приведённые выше равенства и предложение 6 обеспечивают
рекуррентный способ вычисления числа 𝑛-арных квазигрупп порядка 4.
Наконец, выпишем первые восемь значений величины 𝑄′ (𝑛, 4): 1, 4, 64,
7132,
201538000,
432345572694417712,
3987683987354747642922773353963277968,
678469272874899582559986240285280710364867063489779510427038722229750276832, — и
величины
𝑄(𝑛, 4):
24,
576,
55296,
36972288,
6268637952000,
80686060158523011084288,
4465185218736554544676917926460256725000192,
4558271384916189349044295395852008182480786230841798008741684281906576963885826048.
Программа на python для вычисления этих чисел приведена в приложении.

5. Заключение
В заключении скажем несколько слов о связи тематики настоящей статьи с известным понятием латинского трэйда (latin trade). Частичная 𝑛-арная квазигруппа 𝑡 : Ω → Σ,
Ω ⊂ Σ𝑛 называется многомерным латинским трэйдом, далее просто трэйдом, если существует другая частичная 𝑛-арная квазигруппа 𝑡′ : Ω → Σ такая, что
1) 𝑡(¯
𝑥) ̸= 𝑡′ (¯
𝑥) для всех 𝑥
¯ ∈ Ω;
2) для любого 𝑖, 𝑖 = 1, . . . , 𝑛, и для любых допустимых значений 𝑥1 , . . . , 𝑥𝑖−1 , 𝑥𝑖−1 , . . . , 𝑥𝑛
множества {𝑡(𝑥1 , . . . , 𝑥𝑖−1 , 𝑦, 𝑥𝑖−1 , . . . , 𝑥𝑛 ) | 𝑦 ∈ Σ} и {𝑡′ (𝑥1 , . . . , 𝑥𝑖−1 , 𝑦, 𝑥𝑖−1 , . . . , 𝑥𝑛 ) | 𝑦 ∈ Σ}
совпадают.
В этом случае пара (𝑡, 𝑡′ ) называется битрейдом (в зависимости от контекста, битрейд
рассматривают как упорядоченную, либо как неупорядоченную пару), а трэйд 𝑡′ называется партнёром трэйда 𝑡. Исследованию битрэйдов в случае 𝑛 = 2 (латинских битрэйдов)
уделяется значительное внимание, см. обзор [5].
Будем говорить, что 𝑛-арная квазигруппа 𝑓 содержит трэйд 𝑡, если 𝑡 = 𝑓 |Ω для некоторого Ω. При этом из определений следует, что замена значений 𝑓 на множестве Ω значениями партнёра 𝑡′ трэйда 𝑡 приводит к другой 𝑛-арной квазигруппе. Трэйды 𝑡 = 𝑓 |Ω и
𝑠 = 𝑓 |Θ назовём независимыми, если их носители (области определения) Ω и Θ не пересекаются. Максимальное число попарно независимых трэйдов, которые содержит 𝑛-арная
квазигруппа 𝑓 , назовём её трэйдовым числом trd(𝑓 ). Максимум trd(𝑓 ) по всем 𝑛-арным
квазигруппам 𝑓 порядка 𝑘 обозначим через Trd(𝑛, 𝑘). Поскольку независимые трэйды в
𝑛-арной квазигруппе можно независимо заменять на партнёров, число 𝑄(𝑛, 𝑘) различных
𝑛-арных квазигрупп порядка 𝑘 удовлетворяет неравенству
𝑄(𝑛, 𝑘) ≥ 2Trd(𝑛,𝑘) .

(6)

Легко понять, что нижняя оценка в разделе 3 (как и все оценки в [7]) получена именно
таким образом: {𝑎, 𝑏}-компонента по определению является носителем некоторого трэйда.
Поскольку носитель трэйда обладает свойством (A), из предложения 1 вытекает Trd(𝑛, 𝑘) ≤
𝑘 𝑛 /2𝑛 = 2(log2 𝑘−1)𝑛 , причем для чётных 𝑘 легко доказать равенство. Для нечётных 𝑘 из
результатов раздела 3 следует оценка Trd(𝑛, 𝑘) ≥ 2𝑐(𝑘)𝑛 , где 𝑐(𝑘) −→ log2 𝑘 − 1. Однако для
𝑘→∞

фиксированных 𝑘, в частности, для малых значений 5, 7, . . . вопрос об асимптотическом
поведении величины Trd(𝑛, 𝑘) остаётся открытым.

Проблема 1. Вычислить асимптотику логарифма и асимптотику величины Trd(𝑛, 𝑘) при
𝑛 → ∞ для нечётных 𝑘 ≥ 5.
7

Другой вопрос состоит в том, насколько оценка (6) близка к истинной. Для порядка
4 оценка (6) асимптотически точна после логарифмирования. Для большего фиксированного порядка асимптотика двукратного логарифма величины 𝑄(𝑛, 𝑘) неизвестна. Кажется
естественным предположить, что асимптотика двукратного логарифма величины 𝑄(𝑛, 𝑘) и
логарифма величины Trd(𝑛, 𝑘) совпадают.
(︁
)︁
(︁
)︁
Проблема 2. Верно ли, что lim log2 log𝑛2 𝑄(𝑛,𝑘) = lim log2 Trd(𝑛,𝑘)
? В частности, верно
𝑛
𝑛→∞
(︁
)︁ 𝑛→∞
ли, что lim log2 log𝑛2 𝑄(𝑛,𝑘) ≤ log2 𝑘 − 1?
𝑛→∞

Существование этих пределов также не доказано.

Список литературы
1. Потапов В. Н., Кротов Д. С. Асимптотика числа 𝑛-квазигрупп порядка 4 // Сибирский
математический журнал. — 2006. — Т. 47, № 4. — С. 873–887.
2. Белоусов В. Д. Основы теории квазигрупп и луп. — Москва: Наука, 1967.
3. Черемушкин А. В. Каноническая декомпозиция 𝑛-арных квазигрупп. — Кишинев: Штиинца, 1988. — Т. 102 из Мат. Исслед. — С. 97–105.
4. Потапов В. Н. Верхняя оценка числа 𝑛-квазигрупп конечного порядка // Труды XVII
международной школы-семинара “Синтез и сложность управляющих систем”. — Новосибирск, Россия: 2008. — октябрь–ноябрь. — С. 136–137.
5. Cavenagh N. J. The theory and application of latin bitrades: A survey // Mathematica
Slovaca. — 2008. — Vol. 58, no. 6. — Pp. 691–718. — DOI: 10.2478/s12175-008-0103-2.
6. Krotov D. S., Potapov V. N. 𝑛-Ary quasigroups of order 4 // SIAM J. Discrete Math. —
2009. — Vol. 23, no. 2. — Pp. 561–570. — DOI: 10.1137/070697331.
7. Krotov D. S., Potapov V. N., Sokolova P. V. On reconstructing reducible n-ary quasigroups
and switching subquasigroups // Quasigroups Relat. Syst. — 2008. — Vol. 16, no. 1. — Pp. 55–
67.
8. McKay B. D., Wanless I. M. On the number of Latin squares // Ann. Comb. — 2005. — Vol. 9,
no. 3. — Pp. 335–334. — DOI: 10.1007/s00026-005-0261-7.
9. McKay B. D., Wanless I. M. A census of small Latin hypercubes // SIAM J. Discrete Math. —
2008. — Vol. 22, no. 2. — Pp. 719–736. — DOI: 10.1137/070693874.

8

A. Приложение. Программа для вычисления 𝑄(𝑛, 4) и 𝑄′ (𝑛, 4)
# PYTHON program
# do not forget leading spaces!
N=12 \# the maximum arity to calculate
P=[[{}]]+[[] for x in [0]*N]
for n in range(N):
for Po in P[n]:
for j in range(N-n-sum(Po.values())+1):
Pn={i+1:Po[i] for i in Po}
if j>0: Pn.update({1:j})
if n+j>0: P[n+sum(Po.values())+j]+=[Pn]
\# now P[n] is a list of partitions of n into positive summands:
\# E.g., 16==1*3+2*4+5*1==(1+1+1)+(2+2+2+2)+(5) is saved as P[16][51]=={1:3, 2:4, 5:1}
for Pn in P: Pn.pop()

\# remove trivial 1-partitions

from math import factorial
mul = lambda a,b:a*b
Aut = lambda Pt:reduce(mul,[factorial(Pt[nu])*factorial(nu)**Pt[nu] for nu in Pt], 1)
F=[[factorial(n)/Aut(Pt) for Pt in P[n]] for n in range(N+1)]
\# F[n][i] is the number of partitions of an n-set
\# that correspond to the partition P[n][i] of n.
La=[2L**(2**n-n-1) for n in range(N+1)]
Ras,Ra0,R_0,R_s,P_a,V,T = [0,0L],[0, 0L],[0,0L],[0,0L],[0,0L],[1,1L],[4,24L]
for n in range(2, N+1):
V+=[0L]; T+=[0L]; P_a+=[0L]; Ras+=[0L]; Ra0+=[0L]; R_0+=[0L]; R_s+=[0L]
for i in range(len(P[n])):
R_0[n], Ra0[n], R_s[n], Ras[n] = map(lambda A, B, C :
A[n] + reduce(mul,[(B[nu]-C*A[nu])**P[n][i][nu] for nu in P[n][i]],1)
*((1-C)*P_a[sum(P[n][i].values())]+C)*F[n][i],
(R_0, Ra0, R_s, Ras), (V, La, V, La), (0, 0, 1, 1))
R_0[n] *= 3
P_a[n] = La[n] - Ra0[n] - 2*Ras[n]
V[n] = 3*P_a[n] + R_0[n] + 4*R_s[n]
T[n] = 4*(6**n)*V[n]
print "\n Reduced (A211214):", V
print "\n Total (A211215):", T

9

