PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 101(115) (2017), 109–119 https://doi.org/10.2298/PIM1715109M

ON CONSTRUCTION OF ORTHOGONAL d-ARY OPERATIONS

Smile Markovski and Aleksandra Mileva

In Memory of Prof. G. B. Belyavskaya

Abstract. A d-hypercube of order n is an n × ⋯× n _{d} (d times) array with n^{d} elements from a set Q of cardinality n. We recall several connections between d-hypercubes of order n and d-ary operations of order n. We give constructions of orthogonal d-ary operations that generalize a result of Belyavskaya and Mullen. Our main result is a general construction of d-orthogonal d-ary operations from d-ary quasigroups.

1. Introduction

In this paper we work with positive integers and we assume that d ⩾ 2. A hypercube of order n and dimension d (or d-hypercube of order n, or d-dimensional hypercube of order n) is an n × ⋯× n _{d} (d times) array with n^{d} elements obtained from the set of n distinct symbols. For 1 ⩽ t ⩽ d, a t-subarray is a subset of a d-hypercube of order n which is obtained by fixing d − t of the coordinates and allowing the other t coordinates to vary. Given d-hypercube of order n has type t, 0 ⩽ t ⩽ d−1, if each symbol occurs exactly n^{d−t−1} times in each (d−t)-dimensional subarray [12]. It is clear that every d-hypercube of order n and type t, has also type i, for each 0 ⩽ i ⩽ t − 1. A Latin square of order n is a 2-hypercube of order n and type 1.

A d-ary operation f on a nonempty set Q is a mapping f: Q^{d} → Q defined by f: (x_{1}, …, x_{d}) ↦ x_{d+1} , for which we write f(x_{1}, …, x_{d}) = x_{d+1} . A d-ary groupoid (d ⩾ 1) is an algebra (Q, f) on a nonempty set Q as its universe and with one d-ary operation f. A d-ary groupoid (Q, f) is called a d-ary quasigroup if any d of the elements a_{1}, a_{2}, …, a_{d+1} ∈ Q, satisfying f(a_{1}, a_{2}, …, a_{d}) = a_{d+1} , uniquely specifies the remaining one.

2010 Mathematics Subject Classification: 05B15; 20N05; 20N15.

Key words and phrases: Latin hypercube, orthogonal hypercubes, orthogonal functions, recursively differentiable quasigroups.

Communicated by Žarko Mijajlović.

A d-ary operation f defined on Q is said to be i-invertible if the equation

f(a_{1}, …, a_{i−1} , x, a_{i+1} , …, a_{d}) = a_{d+1}

has a unique solution x for each d-tuple (a_{1}, …, a_{i−1} , a_{i+1} , …, a_{d}, a_{d+1} ) of Q^{d}. Equivalently, we can define a d-ary quasigroup to be a d-ary groupoid (Q, f) such that the d-ary operation f is i-invertible for each i = 1, …, d.

Given a d-ary quasigroup (Q, f), d new d-ary operations ^{(i)}f, i = 1, 2, …, d, can be defined by

(i)f(x_{1}, x_{2}, …, x_{d}) = x_{d+1} ⇔ f(x_{1}, …, x_{i−1} , x_{d+1} , x_{i+1} , …, x_{d}) = x_{i}.

Then (Q,^{(i)}f) are d-ary quaisgroups too. The operation ^{(i)}f is called the i-th inverse operation of f [1]. We note that the following equalities are identities in the algebra (Q, f, ^{(i)}f):

f(x_{1}, …, x_{i−1} ,^{(i)}f(x_{1}, x_{2}, …, x_{d}), x_{i+1} , …, x_{d}) = x_{i},
(i)f(x_{1}, …, x_{i−1} , f(x_{1}, x_{2}, …, x_{d}), x_{i+1} , …, x_{d}) = x_{i}.

A d-ary groupoid (Q, f) is of order n when |Q| = n. Belyavskaya and Mullen [4] proved that a d-ary quasigroup of order n is an algebraic equivalent of a dhypercube of order n and type d − 1.

In this paper we give generalizations of some results given in [4]. In Section 2 we survey the definitions that can be found in the literature of orthogonality and connections between d-ary hypercubes, d-ary operations and d-ary quasigroups. The main results are given in Section 3, where several new constructions of orthogonal d-tuple are presented.

2. d-ary hypercubes, d-ary operations, d-ary quasigroups and orthogonality

The usual definition of orthogonality states that two d-hypercubes of order n are orthogonal if each ordered pair occurs exactly n^{d−2} times upon superimposition. Similarly, two d-ary operations f and h defined on a set Q of cardinality n are said to be orthogonal if the pair of equations f(x_{1}, …, x_{d}) = u and h(x_{1}, …, x_{d}) = v has exactly n^{d−2} solutions for any given elements u, v ∈ Q.

A set of d hypercubes of order n and dimension d is said to be d-orthogonal (or d-wise orthogonal) if, when superimposed, each of the n^{d} ordered d-tuples occurs exactly once. (This is the concept of dimensional orthogonality in [8, 9] and of variational cube in [10]). The set of m ⩾ d hypercubes of order n and dimension d is called mutually d-orthogonal (MdOH) if, given any d hypercubes from the set, they are d-orthogonal (also known as d-dimensional variational set in [7]).

One can define a general form of orthogonality that includes standard form of d-orthogonality. For 2 ⩽ k ⩽ d, a set of k hypercubes of order n and dimension d is said to be k-orthogonal if, when superimposed, each of the n^{k} ordered k-tuples occurs exactly n^{d−k} times. A set of j ⩾ k hypercubes of order n and dimension d is called mutually k-orthogonal if, given any k hypercubes from the set, they are k-orthogonal.

For d-ary operations we have the following definitions.

ORTHOGONAL d-ARY OPERATIONS 111

Definition 2.1 ([2, 3] for k = d, [4]). A k-tuple ⟨f_{1}, f_{2}, …, f_{k}⟩, 1 ⩽ k ⩽ d, of distinct d-ary operations defined on a set Q is orthogonal if the system of equations {f_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{k} has exactly n^{d−k} solutions for any a_{1}, …, a_{k} ∈ Q^{n}.

Definition 2.2. [4] A set Σ = {f_{1}, f_{2}, …, f_{s}} of d-ary operations is k-ortho-

gonal, 1 ⩽ k ⩽ d, k ⩽ s, if every k-tuple f_{i_{1}} , f_{i_{2}} , …, f_{i_{k}} of distinct d-ary operations of Σ is orthogonal.

A set of k-orthogonal d-hypercubes of order n correspond to a set of k-orthog-onal d-ary operations of order n.

Let ⟨f_{1}, f_{2}, …, f_{d}⟩ be a d-tuple of d-ary operations defined on a set Q. Then a unique mapping θ = (f_{1}, f_{2}, …, f_{d}): Q^{n} → Q^{n} is defined by

θ: (x_{1}, …, x_{d}) ↦ (f_{1}(x_{1}, …, x_{d}), f_{2}(x_{1}, …, x_{d}), …, f_{d}(x_{1}, …, x_{d})).

The following proposition gives a connection between the orthogonal d-tuple of d-ary operations and the permutations on Q^{d}.

Proposition 2.1. [3] A d-tuple ⟨f_{1}, f_{2}, …, f_{d}⟩ of different d-ary operations on Q is orthogonal if and only if the mapping θ = (f_{1}, f_{2}, …, f_{d}) is a permutation on Q^{n}.

Further, we give another connection between d-ary hypercubes of order n and d-ary operations of order n. The d-ary operation I_{j}, 1 ⩽ j ⩽ d, defined on Q by I_{j} (x_{1}, x_{2}, …, x_{d}) = x_{j}, is called the j-th selector or the j-th projection.

Definition 2.3. [3] A set Σ = {f_{1}, f_{2}, …, f_{r}} of distinct d-ary operations

defined on a set Q is strong orthogonal (or strong d-wise orthogonal) if the set {I_{1}, …, I_{d}, f_{1}, f_{2}, …, f_{r}} is d-orthogonal, where each I_{j} , 1 ⩽ j ⩽ d, is the j-th selector.

It follows that each operation of a strong orthogonal set, which is not a selector, is a quasigroup operation. Clearly, if r ⩾ d, a strong d-orthogonal set is d-orthogonal, as well.

Similarly, a set of r hypercubes of order n and dimension d is called mutually strong d-orthogonal (MSdOH) if upon superimposition of corresponding j-sub-arrays of any j hypercubes in the set, 1 ⩽ j ⩽ min(d, r), each ordered j-tuple appears exactly once [8]. Letting j = 1, it implies that each hypercube in the set is of type d − 1, and for d = 2 and r ⩾ 2, this definition is equivalent to the definition of MOLS (mutually orthogonal Latin squares). Additionally, if r ⩾ d, strong d-orthogonality implies d-orthogonality. There are at most n − 1 mutually strong d-orthogonal hypercubes of dimension d and order n.

A set of r mutually strong d-orthogonal d-hypercubes of order n corresponds to a set of r mutually strong d-orthogonal d-ary operations of order n.

3. Constructions of orthogonal d-ary operations

The main motivation for our first construction is the following theorem.

Theorem 3.1. [4] Let ⟨f_{1}, f_{2}, …, f_{d}⟩ be a d-tuple of d-ary operations defined on a set Q and let f_{i}, 1 ⩽ i ⩽ d, be (d − i + 1)-invertible d-ary operation. Then the d-tuple ⟨F_{1}, F_{2}, …, F_{d}⟩, defined by

F_{1}(x_{1}, …, x_{d}) = f_{1}(x_{1}, …, x_{d}),
F_{2}(x_{1}, …, x_{d}) = f_{2}(x_{1}, …, x_{d−1} , F_{1}(x_{1}, …, x_{d})),
F_{3}(x_{1}, …, x_{d}) = f_{3}(x_{1}, …, x_{d−2} , F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d})),
⋮
F_{d}(x_{1}, …, x_{d}) = f_{d}(x_{1}, F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d}), …, F_{d−1} (x_{1}, …, x_{d})),

is orthogonal.

Similarly, we can go one step further.

Theorem 3.2. Let ⟨f_{1}, f_{2}, …, f_{d}⟩ be d-ary operations defined on a set Q and let f_{i}, 1 ⩽ i ⩽ d, be i-invertible d-ary operation. Then the d-tuple ⟨F_{1}, F_{2}, …, F_{d}⟩, defined by

F_{1}(x_{1}, …, x_{d}) = f_{1}(x_{1}, …, x_{d}),
F_{2}(x_{1}, …, x_{d}) = f_{2}(F_{1}(x_{1}, …, x_{d}), x_{2}, …, x_{d}),
F_{3}(x_{1}, …, x_{d}) = f_{3}(F_{2}(x_{1}, …, x_{d}), F_{1}(x_{1}, …, x_{d}), x_{3}, …, x_{d}),
⋮
F_{d}(x_{1}, …, x_{d}) = f_{d}(F_{d−1} (x_{1}, …, x_{d}), …, F_{1}(x_{1}, …, x_{d}), x_{d}),

is orthogonal.

Proof. Consider the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{d} and substitute the values of F_{1}, …, F_{d−1} into the last of previous equalities

F_{d}(x_{1}, …, x_{d}) = a_{d} = f_{d}(a_{d−1} , a_{d−2} , …, a_{1}, x_{d}).

We obtain a unique solution x_{d} = b_{d} since the f_{d} is d-invertible operation, and so the F_{d} is d-invertible operation. Next, we substitute this value of x_{d} and the values of F_{1}, …, F_{d−2} into the (d − 1)-th equation

F_{d−1} (x_{1}, …, x_{d−1} , b_{d}) = f_{d−1} (a_{d−2} , a_{d−3} , …, a_{1}, x_{d−1} , b_{d}) = a_{d−1} ,

and we obtain a unique x_{d−1} = b_{d−1} using the (d − 1)-invertibility of f_{d−1} ; F_{d−1} is (d − 1)-invertible too. So, we do similar substitutions in all equalities till the first one, in which we would obtain

F_{1}(x_{1}, b_{2}, …, b_{d}) = f_{1}(x_{1}, b_{2}, …, b_{d}) = a_{1},

and again we obtain a unique x_{1} = b_{1} from 1-invertibility of f_{1}.

So, the given system has a unique solution x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} and the d-tuple F_{1}, …, F_{d} is orthogonal. □

Now, we give the following generalization of the previous result.

Theorem 3.3. Let ⟨f_{1}, f_{2}, …, f_{d}⟩ be d-ary operations defined on a set Q and let f_{i}, 1 ⩽ i ⩽ d, be p_{i}-invertible d-ary operations, where p_{1}, …, p_{d} is a permutation of the positions 1, …, d. Let the d-tuple ⟨F_{1}, F_{2}, …, F_{d}⟩ be defined by the procedure

F_{1}(x_{1}, …, x_{d}) = f_{1}(x_{1}, …, x_{d}),

F_{2}(x_{1}, …, x_{d}) = f_{2}(x_{1}, …, x_{p_{1} −1} , F_{1}(x_{1}, …, x_{d}), x_{p_{1} +1} , …, x_{d}),
F_{i}(x_{1}, …, x_{d}) = f_{i}(y_{1}, …, y_{d}), i = 3, …, d,

where y_{p_{i−1}} = F_{1}(x_{1}, …, x_{d}), y_{p_{i−2}} = F_{2}(x_{1}, …, x_{d}),…, y_{p_{1}} = F_{i−1} (x_{1}, …, x_{d}), and y_{j} = x_{j} for j ∉ {p_{1}, …, p_{i−1} }. Then, the d-tuple ⟨F_{1}, F_{2}, …, F_{d}⟩ is orthogonal.

Proof. Consider the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{d} and substitute the values of F_{1}, …, F_{d−1} into the last equation:

F_{d}(x_{1}, …, x_{d}) = f_{d}(y_{1}, …, y_{d}) = a_{d}

where y_{p_{d−1}} = a_{1}, y_{p_{d−2}} = a_{2}, …, y_{p_{1}} = a_{d−1} , and y_{p_{d}} = x_{p_{d}}. We obtain a unique x_{p_{d}} = b_{p_{d}} since the f_{d} is p_{d}-invertible operation, and so the F_{d} is p_{d}-invertible operation. Next, we substitute this value of x_{p_{d}} and the values of F_{1}, …, F_{d−2} into the (d − 1)-th equation:

F_{d−1} (x_{1}, …, x_{p_{d} −1} , b_{p_{d}} , x_{p_{d} +1} , …, x_{d}) = f_{d−1} (y_{1}, …, y_{d}) = a_{d−1} ,

where y_{p_{d−2}} = a_{1}, y_{p_{d−3}} = a_{2}, …, y_{p_{1}} = a_{d−2} , y_{p_{d}} = b_{p_{d}}, and y_{p_{d−1}} = x_{p_{d−1}} . We obtain a unique x_{p_{d−1}} = b_{p_{d−1}} using the p_{d−1} -invertibility of f_{d−1} . So, we do similar substitutions in all equalities till the first one, in which we would obtain

F_{1}(b_{1}, …, b_{p_{1} −1} , x_{p_{1}} , b_{p_{1} +1} , …, b_{d}) = f_{1}(b_{1}, …, b_{p_{1} −1} , x_{p_{1}} , b_{p_{1} +1} , …, b_{d}) = a_{1},

and again we obtain a unique x_{p_{1}} = b_{p_{1}} from p_{1}-invertibility of f_{1}.

So, the given system has a unique solution x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} and the d-tuple F_{1}, …, F_{d} is orthogonal. □

The systems from Theorem 3.1 and Theorem 3.2 are special cases of Theorem 3.3, where we use the permutation d, d−1, …, 1 in the first case, and 1, 2, …, d in the second case.

Another special case of Theorem 3.3 is when f_{1} = ⋯= f_{d} = f, where f is d-ary quasigroup operation.

Corollary 3.1. Let f be a d-ary quasigroup operation, and let p_{1}, …, p_{d} be a permutation of the positions 1, …, d. Then the system of operations ⟨F_{1}, …, F_{d}⟩:

F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}),
F_{2}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{p_{1} −1} , F_{1}(x_{1}, …, x_{d}), x_{p_{1} +1} , …, x_{d}),
F_{i}(x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}), i = 3, …, d,

where y_{p_{i−1}} = F_{1}(x_{1}, …, x_{d}), y_{p_{i−2}} = F_{2}(x_{1}, …, x_{d}),…, y_{p_{1}} = F_{i−1} (x_{1}, …, x_{d}), and y_{j} = x_{j} for j ∉ {p_{1}, …, p_{i−1} } is orthogonal.

Example 3.1. Let (Q, f) be the 4-ary quasigroup on Q = {0, 1, 2, 3} defined by f(x_{1}, x_{2}, x_{3}, x_{4}) = x_{1} + x_{2} + x_{3} + x_{4} mod 4. Take in Corollary 3.1 the permutation 3, 1, 2, 4 of the positions 1, 2, 3, 4. Then the following 4-tuple ⟨F_{1}, F_{2}, F_{3}, F_{4}⟩ of orthogonal 4-ary operations is obtained, where F_{2}, F_{3}, and F_{4} are not 4-ary quasigroup operations:

F_{1}(x_{1}, x_{2}, x_{3}, x_{4}) = f(x_{1}, x_{2}, x_{3}, x_{4}) = x_{1} + x_{2} + x_{3} + x_{4} mod 4,
F_{2}(x_{1}, x_{2}, x_{3}, x_{4}) = f(x_{1}, x_{2}, F_{1}(x_{1}, x_{2}, x_{3}, x_{4}), x_{4}) = 2x_{1} + 2x_{2} + x_{3} + 2x_{4} mod 4,

F_{3}(x_{1}, x_{2}, x_{3}, x_{4}) = f(F_{1}(x_{1}, x_{2}, x_{3}, x_{4}), x_{2}, F_{2}(x_{1}, x_{2}, x_{3}, x_{4}), x_{4})
= 3x_{1} + 2x_{3} mod 4,
F_{4}(x_{1}, x_{2}, x_{3}, x_{4}) = f(F_{2}(x_{1}, x_{2}, x_{3}, x_{4}), F_{1}(x_{1}, x_{2}, x_{3}, x_{4}), F_{3}(x_{1}, x_{2}, x_{3}, x_{4}), x_{4})
= 2x_{1} + 3x_{2} mod 4.

One can see that F_{2} is 3-invertible, F_{3} is 1-invertible and F_{4} is 2-invertible 4-ary operation.

We will prove that this system of functions can not be obtained from some other set of linear 4-ary operations by using Belyavskaya and Mullen method from Theorem 3.1. Let suppose the opposite - that the system F_{1}, F_{2}, F_{3}, F_{4} can be obtained by a set ⟨g_{1}, g_{2}, g_{3}, g_{4}⟩ of linear 4-ary operations using Theorem 3.1, where g_{1} is 4-invertible, g_{2} is 3-invertible, g_{3} is 2-invertible, and g_{4} is 1-invertible operation. In other words, we suppose that ⟨G_{1}, G_{2}, G_{3}, G_{4}⟩ = ⟨F_{1}, F_{2}, F_{3}, F_{4}⟩, where G_{i} are got from g_{i} as in Theorem 3.1. It is clear from Theorem 3.1 that if g_{i} is k-invertible, then G_{i} is k-invertible too. Then, the following system with unknown linear functions g_{i} on (ℤ_{4}, +) should be satisfied:

G_{1}(x_{1}, x_{2}, x_{3}, x_{4}) = g_{1}(x_{1}, x_{2}, x_{3}, x_{4}) = F_{1}(x_{1}, x_{2}, x_{3}, x_{4})
= x_{1} + x_{2} + x_{3} + x_{4} mod 4,
G_{2}(x_{1}, x_{2}, x_{3}, x_{4}) = g_{2}(x_{1}, x_{2}, x_{3}, G_{1}(x_{1}, x_{2}, x_{3}, x_{4})) = F_{2}(x_{1}, x_{2}, x_{3}, x_{4})
= 2x_{1} + 2x_{2} + x_{3} + 2x_{4} mod 4,
G_{3}(x_{1}, x_{2}, x_{3}, x_{4}) = g_{3}(x_{1}, x_{2}, G_{1}(x_{1}, …, x_{4}), G_{2}(x_{1}, …, x_{4}))
= F_{3}(x_{1}, …, x_{4}) = 3x_{1} + 2x_{3} mod 4,
G_{4}(x_{1}, x_{2}, x_{3}, x_{4}) = g_{4}(x_{1}, G_{1}(x_{1}, …, x_{4}), G_{2}(x_{1}, …, x_{4}), G_{3}(x_{1}, …, x_{4}))
= F_{4}(x_{1}, …, x_{4}) = 2x_{1} + 3x_{2} mod 4.

It can be easily seen that this system has no 4-ary linear function solutions g_{1}, g_{2}, g_{3}, g_{4}. Hence, we conclude that our generalization of Theorems 1 and 2 is sound.

Proposition 3.1. Every d-ary quasigroup (Q, f) of order n can rise at most d! different d-tuples ⟨F_{1}, F_{2}, …, F_{d}⟩ of orthogonal d-ary operations generated by the procedure given in Corollary 3.1, where f_{1} = ⋯= f_{d} = f.

The following proposition is a generalization of Proposition 7 in [4].

Proposition 3.2. Let (Q, f) be a d-ary quasigroup of order n. Then the (d+1)- tuple ⟨F_{1}, F_{2}, …, F_{d+1} ⟩, defined by

F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}),
F_{2}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d−1} , F_{1}(x_{1}, …, x_{d})),
F_{3}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d−2} , F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d})),
⋮
F_{d}(x_{1}, …, x_{d}) = f(x_{1}, F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d}), …, F_{d−1} (x_{1}, …, x_{d})),
F_{d+1} (x_{1}, …, x_{d}) = f(F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d}), …, F_{d}(x_{1}, …, x_{d})),

is d-orthogonal.

Proof. Orthogonality of the d-tuple ⟨F_{1}, F_{2}, …, F_{d}⟩ follows from Theorem 3.1. Consider the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=2}^{d+1} . From the last equation a_{d+1} =

F_{d+1} (x_{1}, …, x_{d}), we have f(f(x_{1}, …, x_{d}), a_{2}, …, a_{d}) = a_{d+1} and it follows that

F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}) =^{(1)} f(a_{d+1} , a_{2}, …, a_{d}) = a_{1}

for some a_{1} ∈ Q, where (Q,^{(1)}f) is the 1-th inverse d-ary quasigroup for (Q, f).

Now, as before, the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{d} has a unique solution x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} over Q. Since

F_{d+1} (b_{1}, …, b_{d})= f(F_{1}(b_{1}, …, b_{d}), F_{2}(b_{1}, …, b_{d}), …, F_{d}(b_{1}, …, b_{d}))
= f(^{(1)}f(a_{d+1} , a_{2}, …, a_{d}), a_{2}, …, a_{d}) = a_{d+1} ,

we have that x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} is the unique solution of the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=2}^{d+1} as well, meaning the system is orthogonal.

Finally, for 2 ⩽ j ⩽ d, consider the system

{F_{i}(x_{1}, …, x_{d}) = a_{i} | i ∈ {1, …, j − 1, j + 1, …, d + 1}}.

We have F_{j} (x_{1}, …, x_{d}) = f(x_{1}, …, x_{d−j+1} , a_{1}, …, a_{j−1} ). By replacing the values for F_{t}, 1 ⩽ t ⩽ d, in the equation F_{d+1} (x_{1}, …, x_{d}) = a_{d+1} , we obtain

a_{d+1} = f(a_{1}, …, a_{j−1} , f(x_{1}, …, x_{d−j+1} , a_{1}, …, a_{j−1} ), a_{j+1} , …, a_{d}),

which implies

f(x_{1}, …, x_{d−j+1} , a_{1}, …, a_{j−1} ) =^{(j)} f(a_{1}, …, a_{j−1} , a_{d+1} , a_{j+1} , …, a_{d}) = a_{j} ,

for some a_{j} ∈ Q. As before, the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{d} has a unique solution x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} over Q. Now we compute

F_{d+1} (b_{1}, …, b_{d}) = f(F_{1}(b_{1}, …, b_{d}), F_{2}(b_{1}, …, b_{d}), …, F_{d}(b_{1}, …, b_{d}))

= f(a_{1}, …, a_{j−1} ,^{(j)} f(a_{1}, …, a_{j−1} , a_{d+1} , a_{j+1} , …, a_{d}), a_{j+1} , …, a_{d}) = a_{d+1} .

We conclude that the system

{F_{i}(x_{1}, …, x_{d}) = a_{i} | i ∈ {1, …, j − 1, j + 1, …, d + 1}}

has the unique solution x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} over Q. This completes the proof of the theorem. □

Now we can give the second main construction, which is a generalization of Proposition 3.2.

Theorem 3.4. Let (Q, f) be a d-ary quasigroup of order n. Let p_{1}, …, p_{d} be a permutation of the positions 1, …, d. Then the (d + 1)-tuple ⟨F_{1}, F_{2}, …, F_{d+1} ⟩, defined by

F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}),
F_{2}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{p_{1} −1} , F_{1}(x_{1}, …, x_{d}), x_{p_{1} +1} , …, x_{d}),
F_{i}(x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}), i = 3, …, d + 1,

where y_{p_{i−1}} = F_{1}(x_{1}, …, x_{d}), y_{p_{i−2}} = F_{2}(x_{1}, …, x_{d}),…, y_{p_{1}} = F_{i−1} (x_{1}, …, x_{d}), and y_{j} = x_{j} for j ∉ {p_{1}, …, p_{i−1} }, is d-wise orthogonal.

Proof. Orthogonality of the d-tuple ⟨F_{1}, F_{2}, …, F_{d}⟩ follows from Proposition 3.2.

Consider the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=2}^{d+1} . From the last equation, we have F_{d+1} (x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{d+1} , where y_{p_{k}} = a_{d+1−k} for k = 1, …, d − 1 and y_{p_{d}} = F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}).

It follows that a_{d+1} = f(y_{1}, …, y_{p_{d} −1} , f(x_{1}, …, x_{d}), y_{p_{d} +1} , …, y_{d}), and that implies f(x_{1}, …, x_{d}) =^{(p_{d})} f(y_{1}, …, y_{p_{d} −1} , a_{d+1} , y_{p_{d} +1} , …, y_{d}) ∈ Q, since y_{t} ∈ Q. So, F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}) = a_{1} for some a_{1} ∈ Q.

Next we replace the value a_{1} of F_{1}(x_{1}, …, x_{d}) in the equation for F_{d}, obtaining F_{d}(x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{d}, where y_{p_{d}} = x_{p_{d}} , y_{p_{d−1}} = a_{1} and y_{p_{k}} = a_{d−k} for k = 1, …, d − 2. Because f is p_{d}-invertible operation, we obtain a unique x_{p_{d}} = b_{p_{d}} ∈ Q.

For i = d−1, …, 2, we substitute the value a_{1} of F_{1}(x_{1}, …, x_{d}) and the already obtained unique new values b_{p_{d}} , …, b_{p_{i+1}} of F_{d}, …, F_{i+1} , respectively, and we obtain F_{i}(x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{i}, where y_{p_{i}} = x_{p_{i}} , y_{p_{i−1}} = a_{1}, y_{p_{k}} = b_{p_{k}} for k = d, …, i + 1, and y_{p_{k}} = a_{i−k} for k = 1, …, i − 1. Because f is p_{i}-invertible operation, this leads to a unique x_{p_{i}} = b_{p_{i}} .

Finally, in the equation F_{1}(x_{1}, …, x_{d}) = f(x_{1}, …, x_{d}) = a_{1}, we replace x_{p_{k}} with b_{p_{k}} for k = 2, …, d, and because f is p_{1}-invertible operation, we obtain a unique x_{p_{1}} = b_{p_{1}} . So, the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=2}^{d+1} is orthogonal.

To complete the proof, we have to show that the d-tuples ⟨F_{i} | i ≠ j, i = 1, …, d + 1⟩ for each j, 2 ⩽ j ⩽ d, are orthogonal. For that aim, consider the systems of equations {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1,i≠j}^{d+1} for each j, 2 ⩽ j ⩽ d. We have

F_{d+1} (x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{d+1} ,

where y_{p_{d+1−k}} = a_{k} for k ≠ j and k = 1, …, d, and y_{p_{d+1−j}} = F_{j} (x_{1}, …, x_{d}).

From the equality f(y_{1}, …, y_{p_{d+1−j} −1} , F_{j} (x_{1}, …, x_{d}), y_{p_{d+1−j} +1} , …, y_{d}) = a_{d+1} , since y_{t} ∈ Q, it follows that

F_{j} (x_{1}, …, x_{d}) =^{(p_{d+1−j} )} f(y_{1}, …, y_{p_{d+1−j} −1} , a_{d+1} , y_{p_{d+1−j} +1} , …, y_{d}) ∈ Q,

hence we have F_{j} (x_{1}, …, x_{d}) = a_{j} for some a_{j} ∈ Q.

There are two cases to consider. Case j = d. We have F_{d}(x_{1}, …, x_{d}) = a_{d}, and the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{d} has a unique solution b_{1}, b_{2}, …, b_{d} according to Theorem 4. We compute

F_{d+1} (b_{1}, …, b_{d}) = f(y_{1}, …, y_{d}),

where y_{p_{d+1−k}} = F_{k}(b_{1}, …, b_{d}) = a_{k} for k = 1, …, d − 1 and

y_{p_{1}} = F_{d}(b_{1}, …, b_{d}) =^{(p_{1} )} f(y_{1}, …, y_{p_{1} −1} , a_{d+1} , y_{p_{1} +1} , …, y_{d}).

The last equation implies f(y_{1}, …, y_{d}) = a_{d+1} , i.e., F_{d+1} (b_{1}, …, b_{d}) = a_{d+1} , hence b_{1}, …, b_{d} is the unique solution of the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i≠d,i=1}^{d+1} . So, the d-tuple ⟨F_{i}| i = 1, …, d − 1, d + 1⟩ is orthogonal. Case j < d. We replace the value a_{j} of F_{j} (x_{1}, …, x_{d}) in the equation for F_{d}, obtaining F_{d}(x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{d}, where y_{p_{d}} = x_{p_{d}}, y_{p_{d−j}} = a_{j} and y_{p_{d−k}} = a_{k} for k ≠ j and k = 1, …, d − 1. Because f is p_{d}-invertible operation, we obtain a unique x_{p_{d}} = b_{p_{d}}.

In the same way, from F_{d−1} (x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{d−1} , where y_{p_{d}} = x_{p_{d}} = b_{p_{d}}, y_{p_{d−1}} = x_{p_{d−1}} , y_{p_{d−1−j}} = a_{j} and y_{p_{d−1−k}} = a_{k} for k ≠ j and k = 1, …, d − 2, we can compute the value x_{p_{d−1}} = b_{p_{d−1}} , since f is p_{d−1} -invertible. Continuing, we can compute the values x_{p_{d}} = b_{p_{d}}, x_{p_{d−1}} = b_{p_{d−1}} , …, x_{p_{j+1}} = b_{p_{j+1}} .

For i = j − 1, …, 1, we substitute obtained new values in the equation for F_{i} and we obtain F_{i}(x_{1}, …, x_{d}) = f(y_{1}, …, y_{d}) = a_{i}, where y_{p_{i}} = x_{p_{i}} , y_{p_{i−k}} = b_{p_{k}} for k = d, …, i + 1, and y_{p_{k}} = a_{k} for k = 1, …, i − 1. Because f is p_{i}-invertible operation, this leads to a unique x_{p_{i}} = b_{p_{i}} .

Finally, in the equation F_{j} (x_{1}, …, x_{d}) = a_{j}, we replace x_{p_{k}} with b_{p_{k}} for k ≠ j and k = 1, …, d, and because f is p_{j} -invertible operation, we obtain a unique x_{p_{j}} = b_{p_{j}} .

We compute F_{d+1} (b_{1}, …, b_{d}) = f(y_{1}, …, y_{d}), where y_{p_{d+1−k}} = F_{k}(b_{1}, …, b_{d}) = a_{k} for k = 1, …, d, k ≠ j, and

y_{p_{d+1−j}} = F_{j} (b_{1}, …, b_{d}) =^{(p_{d+1−j} )} f(y_{1}, …, y_{p_{d+1−j} −1} , a_{d+1} , y_{p_{d+1−j} +1} , …, y_{d}).

The last equation implies f(y_{1}, …, y_{d}) = a_{d+1} , i.e., F_{d+1} (b_{1}, …, b_{d}) = a_{d+1} , hence b_{1}, …, b_{d} is the unique solution of the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i≠d,i=1}^{d+1} . So, the d-tuple ⟨F_{i} | i = 1, …, j − 1, j + 1, …, d + 1⟩ is orthogonal. □

At the end, we give one more construction.

Theorem 3.5. Let ⟨f_{1}, f_{2}, …, f_{d}⟩ be d-ary operations defined on a set Q and let f_{i}, 1 ⩽ i ⩽ d, be 1-invertible d-ary operation. Then the d-tuple ⟨F_{1}, F_{2}, …, …, F_{d}⟩, defined by

F_{1}(x_{1}, …, x_{d}) = f_{1}(x_{1}, …, x_{d}),
F_{2}(x_{1}, …, x_{d}) = f_{2}(x_{2}, …, x_{d}, F_{1}(x_{1}, …, x_{d})),
F_{3}(x_{1}, …, x_{d}) = f_{3}(x_{3}, …, x_{d}, F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d})),
⋮
F_{d}(x_{1}, …, x_{d}) = f_{d}(x_{d}, F_{1}(x_{1}, …, x_{d}), F_{2}(x_{1}, …, x_{d}), …, F_{d−1} (x_{1}, …, x_{d})),

is orthogonal.

Proof. Consider the system {F_{i}(x_{1}, …, x_{d}) = a_{i}}_{i=1}^{d} and substitute the values of F_{1}, …, F_{d−1} into the last equation:

F_{d}(x_{1}, …, x_{d}) = f_{d}(x_{d}, a_{1}, a_{2}, …, a_{d−1} ) = a_{d}.

We obtain a unique x_{d} = b_{d} since the f_{d} is 1-invertible operation, and so the F_{d} is d-invertible operation. Next, we substitute this value of x_{d} and the values of F_{1}, …, F_{d−2} into the (d − 1)-th equation:

F_{d−1} (x_{1}, …, x_{d−1} , b_{d}) = f_{d−1} (x_{d−1} , b_{d}, a_{1}, a_{2}, …, a_{d−2} ) = a_{d−1} ,

and we obtain a unique x_{d−1} = b_{d−1} using the 1-invertibility of f_{d−1} ; again, we have that F_{d−1} is a (d − 1)-invertible operation. Proceeding in the same way, we do similar substitution in all equations till the first one,

F_{1}(x_{1}, b_{2}, …, b_{d}) = f_{1}(x_{1}, b_{2}, …, b_{d}) = a_{1}.

We obtain a unique x_{1} = b_{1} from 1-invertibility of f_{1}.

So, the given system has a unique solution x_{1} = b_{1}, x_{2} = b_{2}, …, x_{d} = b_{d} and the d-tuple ⟨F_{1}, …, F_{d}⟩ is orthogonal. □

A special case of Theorem 3.5 is when f_{1} = ⋯= f_{d} = f, where (Q, f) is an arbitrary d-ary quasigroup (this special case of Theorem 3.5 is firstly proved in [11]). The operations F_{1}, F_{2}, …, F_{d} are known as recursive derivatives of f [5, 6]. Recursive derivatives are also the functions defined by F_{i+d} (x_{1}, …, x_{d}) = f(F_{i}(x_{1}, …, x_{d}), …, F_{i+d−1} (x_{1}, …, x_{d})), i ⩾ 1. A d-ary quasigroup (Q, f) is called recursively r-differentiable if all recursive derivatives F_{2}, …, F_{r+1} are quasigroup operations.

Example 3.2. Let (Q, f) be the 4-ary quasigroup on Q = {0, 1, 2, 3, 4} with the operation

f(x_{1}, x_{2}, x_{3}, x_{4}) = x_{1} + x_{2} + x_{3} + x_{4} mod 5.

We compute by Theorem 3.5 the 4-ary operations

F_{2}(x_{1}, x_{2}, x_{3}, x_{4}) = x_{1} + 2x_{2} + 2x_{3} + 2x_{4} mod 5,
F_{3}(x_{1}, x_{2}, x_{3}, x_{4}) = 2x_{1} + 3x_{2} + 4x_{3} + 4x_{4} mod 5,
F_{4}(x_{1}, x_{2}, x_{3}, x_{4}) = 4x_{1} + x_{2} + 2x_{3} + 3x_{4} mod 5.

All of the operations F_{2}, F_{3}, F_{4} are quasigroup operations, so (Q, f) is an example of a recursively 3-differentiable quasigroup.

References

1. V. D. Belousov, M. D. Sandik, n-ary Quasi-groups and Loops, Sib. Math. J. 7(1) (1966), 24–42.

2. V. D. Belousov, T. Yakubov, On orthogonal n-ary operations, Vopr. Kibern., Mosk. 16 (1975), 3–17. (in Russian)

3. A. S. Bektenov, T. Yakubov, Systems of orthogonal n-ary operations, Izv. Akad. Nauk Mold. SSR, Ser. Fiz.-Tekh. Mat. Nauk 3 (1974), 7–14. (in Russian)

4. G. B. Belyavskaya, G. L. Mullen, Orthogonal hypercubes and n-ary operations, Quasigroups Relat. Syst. 13 (2005), 73–86.

5. E. Couselo, S. Gonsales, V. Markov, A. Nechaev, Recursive MDS-codes and recursively differentiable quasigroup, Discrete Math. 10(2) (1998), 3–29.

6. , The parameters of recursive MDS-codes, Discrete Math. 12(4) (2000), 3–24.

7. J. Dénes, A. D. Keedwell, Latin Squares and Their Applications, Academic Press, New York, 1974.

8. J. T. Ethier, Strong Forms of Orthogonality for Sets of Hypercubes, PhD thesis, Pennsylvania State University, 2008.

9. J. T. Ethier, G. L. Mullen, Strong forms of orthogonality for sets of hypercubes, Discrete Math. 312(12–13) (2012), 2050–2061.

10. A. Heppes, P. Révész, A new generalization of the method of latin squares and orthogonal latin squares and its application to the design of experiments, Magyar Tud. Akad. Mat. Int. Közl. 1 (1956), 379–390.

11. V. I. Izbash, P. Syrbu, Recursively differentiable quasigroups and complete recursive codes, Comment. Math. Univ. Carolinae 45 (2004), 257–263.

12. C. F. Laywine, G. L. Mullen, G. Whittle, D-dimensional hypecubes and the Euler and Mac-Neish conjectures, Monatsh. Math. 111 (1995), 223–238.

Faculty for Computer Science and Engineering (Received 04 03 2016) Ss Cyril and Methodius University Skopje, Macedonia

smile.markovski@gmail.com

Faculty for Infromatics Goce Delcev University Stip, Macedonia

aleksandra.mileva@ugd.edu.mk