Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 2, 495-502.

On Full Partial Quasigroups of Finite Order and Local Cardinal Maximum Codes

Jörn Quistorff

Speckenreye 48, D-22119 Hamburg, Germany

Abstract. Stojaković/Ušan’s result on the minimal size of a full partial quasigroup of a given finite order is improved and generalized to full partial n-quasigroups: An implicite lower bound is proved, some upper bounds are given. The minimal size of a full partial quasigroup is determined. Some cases for full partial n-quasigroups are also solved. The correspondence between full partial n-quasigroups of finite order and local cardinal maximum codes is used.

1. Introduction

Stojaković/Ušan [10] consider partial quasigroups of finite order, they introduce the notion of a full partial quasigroup and prove a first lower bound on the minimal size of a full partial quasigroup of a given order.

Dörnte [4] generalizes the notion of a group to an n-group. The notion of a quasigroup can be generalized to an n-quasigroup in the same way.

A correspondence between quasigroups of finite order respectively Latin squares and codes is developed especially by Golomb/Posner [6], Dénes/Gergely [1] and Ušan [11]. Golomb/ Posner [6] show for the first time the relation between systems of n − 2 mutually orthogonal Latin squares and (n, 2)-MDS-codes.

Because of these well-known connections, confer also Dénes/Keedwell [2], [3] and Heise/ Quattrocchi [7], each n-quasigroup corresponds to a code of length n + 1. Every full partial n-quasigroup of finite order corresponds to a local cardinal maximum code.

In the present work, Stojaković/Ušan’s [10] mentioned result is considerably improved and generalized to the case of full partial n-quasigroups: An implicite lower bound on the minimal size of a full partial n-quasigroup is proved. Some upper bounds are also given.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1999 Heldermann Verlag

Thus, it is possible to determine the minimal size of a full partial quasigroup. Some special cases for full partial n-quasigroups can also be solved.

Because of the correspondence between full partial n-quasigroups and local cardinal maximum codes, this note shows some results in the language of coding theory. MDS-codes will be used in order to construct local cardinal maximum codes and, thereby, also full partial n-quasigroups.

2. Foundations

Let Q be a non-empty set and A : Q × Q → Q a mapping. (Q, A) is called quasigroup iff for all x, z ∈ Q there exists exactly one y ∈ Q and exactly one y′ ∈ Q with A(x, y) = z and A(y′, x) = z. If Q is finite, “exactly” can be substituted by “at least” or “at most” and |Q| is called the order of the quasigroup.

If ∅ ≠ D ⊆ Q × Q and A : D → Q is a mapping, (Q, D, A) is called partial quasigroup iff for all x, z ∈ Q there exists at most one y ∈ Q and at most one y′ ∈ Q with A(x, y) = z and A(y′, x) = z. In the finite case, |D| is called the size of the partial quasigroup.

A partial quasigroup (Q, D, A) is called full iff for all partial quasigroups (Q, \overline{D}, \overline{A}) with D ⊆ \overline{D} and with the condition that the restriction res(\overline{A}, D) is equal to A, neccessarily D = \overline{D} holds true.

Stojaković/Ušan [10] prove the following statement: If (Q, D, A) is a full partial quasigroup of order q ∈ N \ {1, 2} then

|D| ≥ 2q − 1.  (1)

Let Q be a set, ∅ ≠ D ⊆ Q^{n} with n ∈ N and A : D → Q. Preparing for the n-dimensional case, let Z_{n} := {i ∈ N|i ≤ n} as well as x^{(i)}#y := (x_{1}, ..., x_{i−1}, y, x_{i+1}, ..., x_{n}) ∈ Q^{n} for x^{(i)} = (x_{1}, ..., x_{i−1}, x_{i+1}, ..., x_{n}) ∈ Q^{n−1} and y ∈ Q. The triple (Q, D, A) is called a partial n-quasigroup iff for all i ∈ Z_{n}, all x^{(i)} ∈ Q^{n−1} and all z ∈ Q there exists at most one y ∈ Q with x^{(i)}#y ∈ D and A(x^{(i)}#y) = z. Analogous to the twodimensional case, (Q, D, A) is called a full partial n-quasigroup iff for every partial n-quasigroup (Q, \overline{D}, \overline{A}) with D ⊆ \overline{D} and with the conditon that the restriction res(\overline{A}, D) is equal to A, neccessarily D = \overline{D} holds true.

The multiplication table of a (2-)quasigroup of order q ∈ N is a Latin square of order q and vice versa. If (Q, A) is a quasigroup of order q then

C := {(x, y, A(x, y)) ∈ Q^{3}|x, y ∈ Q}

is a code of length 3 and order q consisting of u(C) = q^{2} codewords. In case q ≥ 2, this code has minimal distance d(C) = 2. Herewith,

d(C) = min{d(w, w′)|w, w′ ∈ C with w ≠ w′}

is the minimal Hamming distance d(w, w′) = |{i ∈ Z_{3}|w_{i} ≠ w′_{i}}| between different codewords. Conversely, a code with the mentioned parameters induces again a quasigroup.

The code C is a (3, 2)-MDS-code, a notion which will be used in the last part of the paper. It is a special case of the construction given by Golomb/Posner [6] and Singleton [9] who show the more general connection between a system of n − 2 mutually orthogonal Latin squares (or mutually orthogonal quasigroups) and an (n, 2)-MDS-code.

If (Q, D, A) is a partial quasigroup of order q and size |D| ≥ 2 then

C = {(x, y, A(x, y)) ∈ Q^{3}|(x, y) ∈ D}

is a code of length 3 and order q with u(C) = |D| and d(C) ≥ 2. Also in this situation, a code with the mentioned parameters induces conversely again a partial quasigroup.

In case of a partial n-quasigroup of order q and size |D| ≥ 2, a code

C = {(x, A(x)) ∈ Q^{n+1}|x ∈ D}

of length n + 1 and order q is induced with u(C) = |D| and d(C) ≥ 2. Also in this situation, the converse statement is true.

The three mentioned codes might be seen as check character systems, confer Ecker/Poch [5] and Schulz [8].

Let q, n, d ∈ N with 2 ≤ q and d ≤ n as well as Q a set with |Q| = q and C ⊆ Q^{n}. A code C is called a (q, n, d)-cardinal maximum code iff d(C) ≥ d holds true and for every code C′ ⊆ Q^{n} with d(C′) ≥ d, the statement u(C′) ≤ u(C) follows.

Weakening this notion, C is called a local (q, n, d)-cardinal maximum code iff d(C) ≥ d holds true and for every proper including set C′ ⊃ C the statement d(C′) < d follows. The minimal number of codewords of a local (q, n, d)-cardinal maximum code is called v(q, n, d).

Every full partial n-quasigroup of order q ∈ N \ {1} induces a local (q, n + 1, 2)-cardinal maximum code and vice versa. So, v(q, n + 1, 2) is also equal to the minimal size of a full partial n-quasigroup of order q.

3. Results

Trivially, a partial 1-quasigroup (Q, D, A) is full iff D = Q is valid.

In the following, the announced improvement and generalisation of the inequality (1) is treated. In order to prove an implicite lower bound on the minimal size of a full partial n-quasigroup, a helping statement will be used:

Let p ∈ N \ {1} and u ∈ N_{0}. Let u = ap + b = b(a + 1) + (p − b)a with a, b ∈ N_{0} and b < p. Let M := {(s_{1}, ..., s_{p}) ∈ (N_{0})^{p}| ∑_{l=1}^{p} s_{l} = u}. Then

∑_{l=1}^{p}(s_{l})^{2} ≥ b(a + 1)^{2} + (p − b)a^{2}  (2)

is valid for all (s_{1}, ..., s_{p}) ∈ M.

Proof of the helping statement. Let (s_{1}^{(0)}, ..., s_{p}^{(0)}) ∈ M and, without loss of generality, s_{l}^{(0)} ≥ s_{m}^{(0)} for l < m. In case of s_{1}^{(0)} − s_{p}^{(0)} ≤ 1, it follows that (s_{1}^{(0)}, ..., s_{p}^{(0)}) = (a + 1, .., a + 1, a, ..., a) and, hence,

∑_{l=1}^{p}(s_{l}^{(0)})^{2} = ∑_{l=1}^{b}(a + 1)^{2} + ∑_{l=b+1}^{p} a^{2} = b(a + 1)^{2} + (p − b)a^{2}.

In case of s_{1}^{(0)} − s_{p}^{(0)} ≥ 2, put

s_{l}^{(1)} := \{ \begin{matrix}s_{1}^{(0)} − 1 & if l = 1, \\ s_{l}^{(0)} & if 1 < l < p, \\ s_{p}^{(0)} + 1 & if l = p. \end{matrix}

It holds true that (s_{1}^{(1)}, ..., s_{p}^{(1)}) ∈ M and ∑_{l=1}^{p}(s_{l}^{(0)})^{2} ≥ ∑_{l=1}^{p}(s_{l}^{(1)})^{2}. One also can get s_{l}^{(1)} ≥ s_{m}^{(1)} for l < m by renumbering. After a finite number k of such steps, (s_{1}^{(k)}, ..., s_{p}^{(k)}) = (a+1, .., a+ 1, a, ..., a) and

∑_{l=1}^{p}(s_{l}^{(0)})^{2} ≥ ∑_{l=1}^{p}(s_{l}^{(k)})^{2} = b(a + 1)^{2} + (p − b)a^{2}

are valid. □

Theorem 1. Let (Q, D, A) be a partial n-quasigroup of order q as well as u := |D| = aq^{n−1}+b with a, b ∈ N_{0} and b < q^{n−1}. If (Q, D, A) is full then

n(qu − b(a + 1)^{2} − (q^{n−1} − b)a^{2}) ≥ (q^{n} − u)q  (3)

and, equivalently,

(n + 1)qu ≥ q^{n+1} + n(au + ab + b)  (4)

are valid.

Proof. The case n = 1 is trivial. Let n ≥ 2 and n(qu − b(a + 1)^{2} − (q^{n−1} − b)a^{2}) < (q^{n} − u)q. For i ∈ Z_{n} and x^{(i)} ∈ Q^{n−1}, put φ_{i}(x^{(i)}) := |{y ∈ Q|x^{(i)}#y ∈ D}|. It holds true that

∑_{x^{(i)}∈Q^{n−1}} φ_{i}(x^{(i)}) = u = b(a + 1) + (q^{n−1} − b)a.  (5)

Remark that the left hand side of this chain of equations is a sum of q^{n−1} items. On the right hand side one can find b times the item (a + 1) and (q^{n−1} − b) times the item a. Hence, also this side is a sum of q^{n−1} items. Put

E_{i} := {(x, r) ∈ Q^{n} × Q|x^{(i)}#r ∈ D}

as well as

E′_{i} := {(x, r) ∈ E_{i}|x ∈ D}.

It holds true that |E_{i}| = q|D| = qu and

|E′_{i}| = ∑_{x∈D} φ_{i}(x^{(i)})
= ∑_{x^{(i)}∈Q^{n−1}}  ∑_{x_{i}∈{y∈Q|x^{(i)}#y∈D}} φ_{i}(x^{(i)})
= ∑_{x^{(i)}∈Q^{n−1}} φ_{i}(x^{(i)}) · |{y ∈ Q|x^{(i)}#y ∈ D}|
= ∑_{x^{(i)}∈Q^{n−1}}(φ_{i}(x^{(i)}))^{2}.

Hence, the number of elements of E′_{i} can be written as a sum of q^{n−1} items as above. By equation (5) and helping statement (2) with p = q^{n−1} and {s_{1}, ..., s_{p}} = {φ_{i}(x^{(i)})|x^{(i)} ∈ Q^{n−1}}, it follows that

|E′_{i}| ≥ b(a + 1)^{2} + (q^{n−1} − b)a^{2}.

Moreover, ∑_{x∈Q^{n}\D} φ_{i}(x^{(i)}) = |E_{i} \ E′_{i}| is valid. Hence, it follows that

∑_{x∈Q^{n}\D} ∑_{i∈Z_{n}} φ_{i}(x^{(i)}) = ∑_{i∈Z_{n}}(|E_{i}| − |E′_{i}|)|
≤ n(qu − b(a + 1)^{2} − (q^{n−1} − b)a^{2})
< (q^{n} − u)q

by the hypothesis. Because of |Q^{n}\D| = q^{n}−u, it exists a w ∈ Q^{n}\D with ∑_{i∈Z_{n}} φ_{i}(w^{(i)}) < q. Put

Q_{i} := {z ∈ Q| it exists a y ∈ Q with w^{(i)}#y ∈ D and A(w^{(i)}#y) = z}.

Because of

| ⋃_{i∈Z_{n}} Q_{i}| ≤ ∑_{i∈Z_{n}} |Q_{i}| = ∑_{i∈Z_{n}} φ_{i}(w^{(i)}) < q,

it exists a \overline{z} ∈ Q \ (⋃_{i∈Z_{n}} Q_{i}). Put \overline{D} := D ∪ \{w\} and

\overline{A} : \overline{D} → Q, x ↦ \{ \begin{matrix}A(x) & if x ∈ D, \\ \overline{z} & if x = w. \end{matrix}

Hence, (Q, \overline{D}, \overline{A}) is a partial n-quasigroup and, through construction, (Q, D, A) is not full. So for every partial n-quasigroup of order q, the inequality (3) and its equivalent (4) are valid. □

Corollary 1. Let k, n ∈ N and (Q, D, A) be a full partial n-quasigroup of order q := kn. Then |D| ≥ n^{n−1}k^{n} = kq^{n−1}.

Proof. Let (Q, D, A) be a partial n-quasigroup of order q. Let

u := |D| = kq^{n−1} − (lq^{n−1} + m)
= (k − l − 1)q^{n−1} + (q^{n−1} − m)
= (q^{n−1} − m)(k − l) + m(k − l − 1)

with l, m ∈ N_{0} and 0 < m ≤ q^{n−1} as well as lq^{n−1} + m < kq^{n−1}. Hence,

0 < q^{n−1}l(q − k + l) + m(q − k) + 2lm + m, since q ≥ k,
⇒ −q^{n}l + q^{n−1}l(k − l) − qm + km − 2lm − m < 0
⇒ n(q^{n}(k − l) − qm − q^{n−1}(k − l)^{2} + 2m(k − l) − m) < (q^{n}k − q^{n−1}k(k − l) + km)n
⇒ n(qu − (q^{n−1} − m)(k − l)^{2} − m(k − l)^{2} + 2m(k − l) − m) < (q^{n} − u)kn
⇒ n(qu − (q^{n−1} − m)(k − l)^{2} − m(k − l − 1)^{2}) < (q^{n} − u)q

follows. By Theorem 1 with a = k − l − 1 and b = q^{n−1} − m, the partial n-quasigroup (Q, D, A) is not full. □

Corollary 2. Let k ∈ N and (Q, D, A) a full partial quasigroup of order 2k + 1. Then |D| ≥ k(2k + 1) + (k + 1) = k^{2} + (k + 1)^{2}.

Proof. Let (Q, D, A) be a partial quasigroup of order 2k + 1. Let

u := |D| = a(2k + 1) + b < k(2k + 1) + (k + 1)

with a, b ∈ N_{0} and b < 2k + 1. So, either (a = k ∧ b ≤ k) or (a < k ∧ b ≤ 2k) is valid. Hence,

0 < 4(k − a)(3k − b) + 2k(2k(k − a) + k − b) +
+(k − a)(3 + 4k(k − a − 1) + 2(k − a)) + 3k − b + 1
⇒ 12ak^{2} + 12ak + 6bk + 3a + 3b < 8k^{3} + 12k^{2} + 6k + 1 + 4a^{2}k + 2a^{2} + 4ab + 2b
⇒ 3((2k + 1)(2ak + a + b)) < (2k + 1)^{3} + 2(a(a(2k + 1) + b) + ab + b)
⇒ 3qu < q^{3} + 2(au + ab + b)

follows. By Theorem 1, the partial quasigroup (Q, D, A) is not full. □

Examples. For every full partial quasigroup (Q, D, A) of order 5 respectively 6 the inequality |D| ≥ 9 respectively |D| ≥ 11 is valid by (1). The above corollaries show in these cases |D| ≥ 13 respectively |D| ≥ 18. Hence, v(5, 3, 2) ≥ 13 and v(6, 3, 2) ≥ 18. Furthermore, for full partial 3-quasigroups of order 5 respectively 6 the inequalities |D| ≥ 44 respectively |D| ≥ 72 hold true by Theorem 1 and Corollary 1. Hence, v(5, 4, 2) ≥ 44 and v(6, 4, 2) ≥ 72.

After these developments of lower bounds on the function v(q, n, d), upper bounds will be considered.

Theorem 2. Let Q = Q_{1} ⊎ Q_{2} be a set which consists of two disjunct subsets with |Q_{1}| = q_{1} and |Q_{2}| = q_{2} as well as q_{1}, q_{2} ∈ N. If (Q_{i}, A_{i}) are quasigroups for i ∈ {1, 2} then (Q, D, A) with D := (Q_{1})^{2} ∪ (Q_{2})^{2} and

A : D → Q, (x, y) ↦ \{ \begin{matrix}A_{1}(x, y) & if x, y ∈ Q_{1}, \\ A_{2}(x, y) & if x, y ∈ Q_{2}, \end{matrix}

is a full partial quasigroup. The statements

v(2k, 3, 2) ≤ 2k^{2}  (6)

and

v(2k + 1, 3, 2) ≤ k^{2} + (k + 1)^{2}  (7)

are valid for all k ∈ N.

Combining the Corollaries 1 and 2 with the above theorem, the minimal size of a full partial quasigroup of a given order and hence v(q, 3, 2) can be determined:

Theorem 3. For k ∈ N, the statements v(2k, 3, 2) = 2k^{2} and v(2k + 1, 3, 2) = k^{2} + (k + 1)^{2} hold true.

The determination of further upper bounds on the function v(q, n, d) is done in the language of coding theory. In order to do so, the following two notions are useful: Let q, n, k ∈ N with q ≥ 2 and K be a set with |K| = q. Then, B(w, k) := {x ∈ K^{n}|d(x, w) ≤ k} is called the closed ball around w ∈ K^{n} with radius k. Moreover, a code C ⊆ K^{n} is called an (n, k)-MDS-code of order q iff u(C) = q^{k} and d(C) = n − k + 1 are valid. If C ⊆ K^{n} is an (n, k)-MDS-code of order q, if I ⊆ Z_{n} with |I| = k and if y_{i} ∈ K for all i ∈ I then it exists exactly one w ∈ C with w_{i} = y_{i} for all i ∈ I.

Theorem 4. Let q_{1}, q_{2}, n, d ∈ N with 2 ≤ q_{1}, q_{2} and d ≤ n. Let C′ ⊆ (K′)^{n} be a code of order q_{1} with d(C′) ≥ d and ⋃_{w′∈C′} B(w′, d−1) = (K′)^{n}. Let C′′ ⊆ (K′′)^{n} be an (n, n−d+1)- MDS-code of order q_{2}. Then v(q_{1}q_{2}, n, d) ≤ u(C′)u(C′′) = u(C′)q_{2}^{n−d+1} holds true.

Proof. Put C := C′ × C′′ ⊆ (K′)^{n} × (K′′)^{n}. Identify (K′)^{n} × (K′′)^{n} with (K′ × K′′)^{n}. Then, C is a code of length n with u(C) = u(C′)u(C′′) and d(C) = min{d(C′), d(C′′)} = d since C′′ is an (n, n − d + 1)-MDS-code. Let

((x′_{1}, x′′_{1}), ..., (x′_{n}, x′′_{n})) ∈ (K′ × K′′)^{n} \ C.

It exists a w′ ∈ C′ with d(x′, w′) ≤ d − 1. Hence, for I′ := {i ∈ Z_{n}|x′_{i} = w′_{i}}, it holds true that |I′| ≥ n − d + 1. Let I′′ ⊆ I′ with |I′′| = n − d + 1. Then, it exists a w′′ ∈ C′′ with x′′_{i} = w′′_{i} for all i ∈ I′′. Hence,

d(C ∪ {((x′_{1}, x′′_{1}), ..., (x′_{n}, x′′_{n}))}) ≤ d − 1

is valid and C is a local (q_{1}q_{2}, n, d)-cardinal maximum code. □

Corollary 3. Let n, q ∈ N with n ≥ 3 and q ≥ 2. If an (n, n − 2)-MDS-code of order n − 1 and an (n, n − 1)-MDS-code of order q exist then

v((n − 1)q, n, 2) ≤ (n − 1)^{n−2}q^{n−1}.

Proof. Let C ⊆ K^{n} be an (n, n − 2)-MDS-code of order n − 1. For w ∈ C, it holds true that |B(w, 1)| = 1 + n(n − 2) = (n − 1)^{2}. For x, w ∈ C with x ≠ w, it holds true that B(x, 1) ∩ B(w, 1) = ∅ because of d(C) = 3. Hence,

(n − 1)^{n} = u(C)(n − 1)^{2} = | ⨄_{w∈C} B(w, 1)| ≤ |K^{n}| = (n − 1)^{n}.

So, ⨄_{w∈C} B(w, 1) = K^{n} follows. This means, by the way, that C is 1-perfect. Theorem 4 proves the corollary. □

Examples. The existence of a (3, 1)-MDS-code of order 2 and of a (3, 2)-MDS-code of order k ∈ N \ {1}, confer Heise/Quattrocchi [7], shows that v(2k, 3, 2) ≤ 2k^{2}. This is a proof of inequality (6) by coding theory. The existence of a (4, 2)-MDS-code of order 3 and of a (4, 3)-MDS-code of order k ∈ N \ {1} shows that v(3k, 4, 2) ≤ 9k^{3}. As an example, v(6, 4, 2) ≤ 72 is valid. If n is more general a power of a prime then the well-known existence of an (n + 1, n − 1)-MDS-code of order n and of an (n + 1, n)-MDS-code of order k ∈ N \ {1} implies the inequality v(nk, n + 1, 2) ≤ n^{n−1}k^{n}.

Combining the last mentioned inequality with Corollary 1, the minimal size of a full partial n-quasigroup of given order and hence the term v(q, n + 1, 2) can be determined in special cases:

Theorem 5. If n is a power of a prime then v(nk, n + 1, 2) = n^{n−1}k^{n} holds true for all k ∈ N.

The case k = 1 is included in this theorem because every (n+1, n−1)-MDS-code of order n is by the proof of Corollary 3 a local (n, n+1, 2)-cardinal maximum code. Hence, v(n, n+1, 2) ≤ n^{n−1} is valid if n is a power of a prime.

References

[1] Dénes, J.; Gergely, E.: Groupoids and Codes. Topics in Inform. Theory, (Second Colloq., Keszthely 1975), Amsterdam 1977.

[2] Dénes, J.; Keedwell, A. D.: Latin Squares and their Applications. Akadémiai Kiadó, Budapest 1974.

[3] Dénes, J.; Keedwell, A. D.: Latin Squares – New Developments in the Theory and Applications. Annals of Discrete Math. 46 (1991).

[4] Dörnte, W.: Untersuchungen über einen verallgemeinerten Gruppenbegriff. Math. Z. 29 (1929), 1–19.

[5] Ecker, A.; Poch, G.: Check Character Systems. Computing 37 (1986), 277–301.

[6] Golomb, S. W.; Posner, E. C.: Rook Domains, Latin Squares, Affine Planes, and Error-Distributing Codes. IEEE Trans. Inform. Theory 10 (1964), 196–208.

[7] Heise, W.; Quattrocchi, P.: Informations- und Codierungstheorie. 3. Auflage, Springer Verlag, Berlin Heidelberg 1995.

[8] Schulz, R.-H.: A Note on Check Character Systems Using Latin Squares. Discrete Math. 97 (1991), 371–375.

[9] Singleton, R. C.: Maximum Distance Q-Nary Codes. IEEE Trans. Inform. Theory 10 (1964), 116–118.

[10] Stojaković, Z.; Ušan, J.: A Classification of Finite Partial Quasigroups. Univ. u Novom Sadu Zb. rad. Prirod.-mat. fak., Serija za mat. 9 (1979), 185–190.

[11] Ušan, J.: Orthogonal Systems of n-ary Operations and Codes. Mat. Vestnik 2(15)(30) (1978), 91–93.

Received December 9, 1997