Strongly orthogonal and uniformly orthogonal many-placed operations
In [3] we have studied connection between orthogonal hypercubes and many-placed (d-ary) operations, have considered different types of orthogonality and their relationships. In this article we continue study of orthogonality of many-placed operations, considering special types of orthogonality such...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2006 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/157373 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Strongly orthogonal and uniformly orthogonal many-placed operations / G. Belyavskaya, G.L. Mullen // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 1. — С. 1–17. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-157373 |
|---|---|
| record_format |
dspace |
| spelling |
Belyavskaya, G. Mullen, G.L. 2019-06-20T03:08:03Z 2019-06-20T03:08:03Z 2006 Strongly orthogonal and uniformly orthogonal many-placed operations / G. Belyavskaya, G.L. Mullen // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 1. — С. 1–17. — Бібліогр.: 6 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20N05, 20N15, 05B15. https://nasplib.isofts.kiev.ua/handle/123456789/157373 In [3] we have studied connection between orthogonal hypercubes and many-placed (d-ary) operations, have considered different types of orthogonality and their relationships. In this article we continue study of orthogonality of many-placed operations, considering special types of orthogonality such as strongly orthogonality and uniformly orthogonality. We introduce distinct types of strongly orthogonal sets and of uniformly orthogonal sets of d-ary operations, consider their properties and establish connections between them. The research described in this article was made possible in part by Award No. MM1-3040-CH-02 of the Moldovan Research and Development Association (MRDA) and the U.S. Civilian Research & Development Foundation for the Independent States of the Former Soviet Union (CRDF). en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Strongly orthogonal and uniformly orthogonal many-placed operations Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Strongly orthogonal and uniformly orthogonal many-placed operations |
| spellingShingle |
Strongly orthogonal and uniformly orthogonal many-placed operations Belyavskaya, G. Mullen, G.L. |
| title_short |
Strongly orthogonal and uniformly orthogonal many-placed operations |
| title_full |
Strongly orthogonal and uniformly orthogonal many-placed operations |
| title_fullStr |
Strongly orthogonal and uniformly orthogonal many-placed operations |
| title_full_unstemmed |
Strongly orthogonal and uniformly orthogonal many-placed operations |
| title_sort |
strongly orthogonal and uniformly orthogonal many-placed operations |
| author |
Belyavskaya, G. Mullen, G.L. |
| author_facet |
Belyavskaya, G. Mullen, G.L. |
| publishDate |
2006 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
In [3] we have studied connection between orthogonal hypercubes and many-placed (d-ary) operations, have considered different types of orthogonality and their relationships. In this
article we continue study of orthogonality of many-placed operations, considering special types of orthogonality such as strongly
orthogonality and uniformly orthogonality. We introduce distinct
types of strongly orthogonal sets and of uniformly orthogonal sets
of d-ary operations, consider their properties and establish connections between them.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/157373 |
| citation_txt |
Strongly orthogonal and uniformly orthogonal many-placed operations / G. Belyavskaya, G.L. Mullen // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 1. — С. 1–17. — Бібліогр.: 6 назв. — англ. |
| work_keys_str_mv |
AT belyavskayag stronglyorthogonalanduniformlyorthogonalmanyplacedoperations AT mullengl stronglyorthogonalanduniformlyorthogonalmanyplacedoperations |
| first_indexed |
2025-11-24T02:44:02Z |
| last_indexed |
2025-11-24T02:44:02Z |
| _version_ |
1850838572255412224 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2006). pp. 1 – 17
c© Journal “Algebra and Discrete Mathematics”
Strongly orthogonal and uniformly orthogonal
many-placed operations
G. Belyavskaya, Gary L. Mullen
Communicated by A. I. Kashu
Abstract. In [3] we have studied connection between orthog-
onal hypercubes and many-placed (d-ary) operations, have consid-
ered different types of orthogonality and their relationships. In this
article we continue study of orthogonality of many-placed opera-
tions, considering special types of orthogonality such as strongly
orthogonality and uniformly orthogonality. We introduce distinct
types of strongly orthogonal sets and of uniformly orthogonal sets
of d-ary operations, consider their properties and establish connec-
tions between them.
1. Introduction
In the article [3] it was established a connection between d-dimentional
hypercubes of different types and many-placed (the same d-ary, polyadic
or multary ) operations. Distinct types of orthogonality of many-placed
operations (of d-dimentional hypercubes) and relationship between them
were considered. In this article we continue study of orthogonality of
many-placed operations, in particular, we consider special types of or-
thogonality such that strongly orthogonality and uniformly orthogonality.
We introduce distinct types of strongly orthogonal sets and of uniformly
Acknowledgment: The research described in this article was made possible in part
by Award No. MM1-3040-CH-02 of the Moldovan Research and Development Asso-
ciation (MRDA) and the U.S. Civilian Research & Development Foundation for the
Independent States of the Former Soviet Union (CRDF).
2000 Mathematics Subject Classification: 20N05, 20N15, 05B15.
Key words and phrases: hypercube, orthogonal hypercubes, d-ary operation, d-
ary quasigroup, orthogonal d-ary operations, strongly orthogonal operations, uniformly
orthogonal operations.
2 Strongly orthogonal and uniformly orthogonal...
orthogonal sets of many-placed (d-ary) operations and establish connec-
tions between them. In parallel, types of orthogonality are considered for
sets of polynomial d-operations over a field and some examples of such
sets are given.
Note, that taking into account the connection these results with d-
dimentional hypercubes and with the results of the paper [3], we use the
letter d for designation of an arity and the letter n is used for designation
of an order of an operation.
2. Necessary notions and results
We recall some notations, concepts and results which are used in the
article. At first remember the following denotes and notes from [2]. By
x
j
i we will denote the sequence xi, xi+1, . . . , xj , i ≤ j. If j < i, then x
j
i is
the empty sequence, 1, n = {1, 2, ..., n} . Let Q be a finite or an infinite
set, d ≥ 1 be a positive integer, and let Qd denote the Cartesian power
of the set Q.
A d-ary operation A (briefly, a d-operation) on a set Q is a mapping
A : Qd → Q defined by A(xd
1) → xd+1, and in this case we write A(xd
1) =
xd+1. Thus, an 1-ary (unary) operation is simply a mapping from Q into
Q.
A d-groupoid (Q, A) of order n is a set Q with one d-ary operation A
defined on Q, where |Q| = n.
A d-ary quasigroup is a d-groupoid such that in the equality
A(xd
1) = xd+1
each of d elements from xd+1
1 uniquely defines the (d + 1)-th element.
Usually a quasigroup d-operation A is itself considered as a d-quasigroup.
The d-operation Ei, 1 ≤ i ≤ d, on Q with Ei(x
d
1) = xi is called the
i-th identity operation (or the i-th selector) of arity d.
Let j be a fixed number, 0 ≤ j ≤ d − 1, {i1, i2, ..., ij} ⊆ 1, d,
(ai1 , ai2 , ..., aij ) ∈ Qj .
By Ij we denote the set of all C
j
d· | Q |j , 2j-tuples
ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij )
when the set {i1, i2, ..., ij} runs trough over all C
j
d, j-subsets of 1, d and
(ai1 , ai2 , ..., aij ) runs trough all | Q |j , j-tuples of elements of Q, that is
Ij = {(i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) | {i1, i2, ..., ij} ⊆ 1, d, (ai1 , ai2 , ..., aij ) ∈ Qj},
if j > 0 and put I0 = ∅ (the empty set).
G. Belyavskaya, G. L. Mullen 3
Let A be a d-ary operation, ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij .
Changing j variables xi1 , xi2 , ..., xij in A on fixed elements ai1 , ai2 , ..., aij
of Q respectively we obtain a new operation
A(xi1−1
1 , ai1 , x
i2−1
i1+1, ai2 , . . . , x
ij−1
ij−k, aij , x
d
ij+1) =
Aā(x
i1−1
1 , xi2−1
i1+1, . . . , x
ij−1
ij−k, x
d
ij+1) = Bā(y
d−j
1 ),
if we rename the remaining d − j variables in the following way:
(xi1−1
1 , xi2−1
i1+1, . . . , x
d
ij+1) = (yi1−1
1 , yi2−1
i1
, ..., yd
ij
) = (yd−j
1 ).
Then Bā is a (d− j)-ary operation, which is called the (d− j)-ary retract
(shortly, the (d − j)-retract) of A, defined by the 2j-tuple ā ∈ Ij . If
ā ∈ I0 = ∅, then Bā = A.
Recall (see [4],[5]) that for d ≥ 2 a d-dimentional hypercube (briefly,
a d-hypercube) of order n is a n × n × · · · × n
︸ ︷︷ ︸
d
array with nd points based
upon n distinct symbols. Such a d-hypercube has type j with 0 ≤ j ≤ d−1
if, whenever any j of the d coordinates are fixed, each of the n symbols
appears nd−j−1 times in that subarray.
A hypercube is a generalization of a latin square, which in the case
of a square of order n, is a n × n array in which n distinct symbols are
arranged so that each symbol occurs once in each row and each column.
A latin square is a 2-dimensional hypercube of type 1.
Some d-ary algebraic operation AH on a set Q of type j corresponds
to a d-hupercube H of type j based on the set Q and conversely [3].
By Proposition 1 of [3] a d-hypercube (a d-operation AH) defined on
a set Q of order n has type j with 0 ≤ j ≤ d − 1 if and only if for each
(d − j)-retract Bā(y
d−j
1 ), ā ∈ Ij , of the corresponding d-operation AH ,
the equation Bā(y
d−j
1 ) = b has exactly nd−j−1 solutions for each b ∈ Q.
A d-hypercube H (a d-operation AH) has type j = d − 1 if and only
if the d-operation AH is a d-quasigroup ([3], Corollary 1).
Two d-hypercubes H1 and H2 of order n are orthogonal if when su-
perimposed, each of the n2 ordered pairs appears nd−2 times, and a set
of t ≥ 2, d-hypercubes is orthogonal if every pair of distinct d-hypercubes
is orthogonal; see [4],[5].
Two d-operations A and B of order n defined on a set Q are said to be
orthogonal if the pair of equations A(xd
1) = a and B(xd
1) = b has exactly
nd−2 solutions for any elements a, b ∈ Q ([3], Definition 4).
A set Σ = {A1, A2, . . . , At} of d-operations with t ≥ 2 is called or-
thogonal if every pair of distinct d-operations from Σ is orthogonal ([3],
Definition 5).
4 Strongly orthogonal and uniformly orthogonal...
Two d-hypercubes H1 and H2 are orthogonal if and only if the re-
spective d-operations AH1
and AH2
are orthogonal. A set of (pairwise)
orthogonal d-operations corresponds to a set of (pairwise) orthogonal d-
hypercubes.
In [3] this notion of orthogonality was generalized in the following
way.
Definition 1 ([3]). A k-tuple < A1, A2, . . . , Ak >, 1 ≤ k ≤ d, of
distinct d-operations defined on a set Q of order n is called orthogonal if
the system
{Ai(x
d
1) = ai}
k
i=1
has exactly nd−k solutions for each ak
1 ∈ Qk.
For k = 1 we say that a d-operation A is itself orthogonal . Such
d-operation of order n is called complete ( for this operation the equa-
tion A(xd
1) = a has exactly nd−1 solutions for any a ∈ Q, that is the
corresponding hypercube has type 0 ).
Definition 2 ([3]). A set Σ = {A1, A2, . . . , At} of d-operations is called
k-wise orthogonal, 1 ≤ k ≤ d, k ≤ t, if every k-tuple < Ai1 , Ai2 , . . . , Aik >
of distinct d-operations of Σ is orthogonal.
Each set of complete d-operations is 1-wise orthogonal.
Theorem 1 ([3]). If a set Σ = {A1, A2, . . . , At}, t ≥ k, of d-operations
of order n defined on a set Q is k-wise orthogonal with 1 ≤ k ≤ d, then
the set Σ is l-wise orthogonal for any l with 1 ≤ l ≤< k.
Theorem 2 ([3]). A d-operation A has type j with 0 ≤ j ≤ d − 1 if and
only if the set Σ = {A, Ed
1} is (j + 1)-wise orthogonal.
Corollary 1 ([3]). A d-operation of type j with 0 ≤ j ≤ d − 1 has type
j1 for all j1, 0 ≤ j1 < j.
In connection with this statement we can consider the maximal type
jmax(A) ≤ d − 1 of a d-operation A (of a corresponding d-hypercube
). Using Theorem 2 we conclude that for a d-operation A, jmax(A) is
the largest j from 0, 1, ..., d − 1 such that the set {A, Ed
1} is (j + 1)-wise
orthogonal. By Corollary 1 of [3] jmax(A) = d − 1 for a d-operation A if
and only if A is a d-quasigroup.
G. Belyavskaya, G. L. Mullen 5
3. Orthogonal sets of d-ary polynomial operations
Consider more detail orthogonality of a special kind of d-operations,
namely, orthogonality of polynomial d-operations of the form
A(xd
1) = a1x1 + a2x2 + ... + adxd
over a field GF (q) (such polynomials are called multilinear).
Let a set Σ = {A1, A2, . . . , At}, d ≥ 2, t ≥ d, be a set of d-operations
each of which is polynomial d-operations over a fields GF (q), that is
A1(x
d
1) = a11x1 + a12x2 + ... + a1dxd,
A2(x
d
1) = a21x1 + a22x2 + ... + a2dxd,
...
At(x
d
1) = at1x1 + at2x2 + ... + atdxd.
(1)
And let A be the determinant of order t×d, defined by these d-operations.
It is easy to see from Definition 2 that the following statement is valid,
where a k-minor is the determinant of (k×k)-sub-array of a determinant
A.
Proposition 1. A set Σ = {At
1}, d ≥ 2, t ≥ d, of polynomial d-
operations of (1) is d-wise orthogonal if and only if all d-minors of the
determinant A, defined by these d-operations are different from 0.
For construction of d-wise orthogonal sets of polynomial d-operations
over a field we can use a Vandermonde determinant of order q − 1 with
elements of a field GF (q) [6]. A Vandermonde determinant of order n,
2 ≤ n ≤ q − 1, is defined in the following way:
∆n(a1, a2, ..., an) =
∣
∣
∣
∣
∣
∣
∣
∣
1 a1 a2
1 ... an−1
1
1 a2 a2
2 ... an−1
2
. . . ... .
1 an a2
n ... an−1
n
∣
∣
∣
∣
∣
∣
∣
∣
=
∏
n≥i>j≥2
(ai − aj).
Such determinant is not equal 0 if ai 6= aj , i 6= j, and ai 6= 0 for each
i ∈ 1, n. The determinant ∆q−1(a1, a2, ..., aq−1) in this case defines an
orthogonal (q − 1)-tuple of polynomial (q − 1)-operations.
In particular, if a is a primitive element (that is a generating element
of multiplicative group of a field), then the determinant
∆q−1(1, a, a2, ..., aq−2) =
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
1 1 1 ... 1
1 a a2 ... aq−2
1 a2 a4 ... a2(n−2)
. . . ... .
1 aq−2 a2(q−2) ... a(q−2)(q−2)
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
6 Strongly orthogonal and uniformly orthogonal...
is not equal 0 and defines an (q − 1)-tuple of polynomial (q − 1)-
operations.
From the considered (q−1)-tuples of (q−1)-operations we can obtain
sets Σ = {Aq−1
1 } of d-operations for each d, 2 ≤ d < q − 1, if to take
q − 1 of the d-operations corresponding to the first d columns of the
determinant ∆q−1(a1, a2, ..., aq−1) or ∆q−1(1, a, a2, ..., aq−2). These sets
of d-operations will be d-wise orthogonal by Proposition 4, since all (d×d)-
minors are also Vandermonde determinants different from 0.
For an illustration, consider the field GF (5) with elements 0,1,2,3,4,
then the q − 1)=4-tuple of (q − 1)=4-ary polynomial operations over
GF (5) corresponding to the Vandermonde determinant ∆4(1, 2, 3, 4) will
be the following:
A1(x
4
1) = x1 + x2 + x3 + x4,
A2(x
d
1) = x1 + 2x2 + 4x3 + 3x4,
A3(x
d
1) = x1 + 3x2 + 4x3 + 2x4,
A4(x
d
1) = x1 + 4x2 + x3 + 4x4.
This 4-tuple defines the 3-wise orthogonal set Σ1 = {B4
1} of ternary
operations with B1(x
3
1) = x1+x2+x3, B2(x
3
1) = x1+2x2+4x3, B3(x
3
1) =
x1+3x2+4x3, B4(x
3
1) = x1+4x2+x3 and the 2-wise orthogonal set Σ2 =
{C4
1} of binary operations where C1(x
2
1) = x1 + x2, C2(x
2
1) = x1 + 2x2,
C3(x
2
1) = x1 + 3x2, C4(x
2
1) = x1 + 4x2.
Now we give one useful sufficient condition for k-wise orthogonality
of a set of polynomial d-operations.
Proposition 2. Let Σ = {At
1}, be a set of polynomial d-operations over
a field GF (q), k be a fixed number, 2 ≤ k ≤ d k ≤ t. The set Σ is k-wise
orthogonal if in the determinant of order k × d, defined by each k-tuple
of d-operations of Σ there exists at least one k-minor different from 0.
Proof. Let A be the determinant corresponding to the d-operations of Σ
and < Ai1 , Ai2 , . . . , Aik > be a k-tuple of distinct d-operations from Σ.
Let in k rows of A corresponding to this k-tuple there exists a k-minor A
(for simplicity let its k columns are the first ones) which is not equal 0:
A =
∣
∣
∣
∣
∣
∣
∣
∣
ai11 ai12 ... ai1k
ai21 ai22 ... ai2k
. . . ...
aik1 aik2 ... aikk
∣
∣
∣
∣
∣
∣
∣
∣
6= 0
.
G. Belyavskaya, G. L. Mullen 7
Then the system of k equations
ai11x1 + ai12x2 + ...ai1kxk = a1 − ai1,k+1xk+1 − ... − ai1dxd,
ai21x1 + ai22x2 + ...ai2kxk = a2 − ai2,k+1xk+1 − ... − ai2dxd,
. . .
aik1x1 + aik2x2 + ...aikkxk = ak − aik,k+1xk+1 − ... − aikdxd
has exactly one solution for all a1, a2, ..., ak ∈ GF (q) and for each of qd−k,
(d−k)-tuples of values of the variables xd
k+1. This means that the system
{Ai1(x
d
1) = a1, Ai2(x
d
1) = a2, ..., Aik(xd
1) = ak}
has exactly qd−k solutions. The set Σ is k-wise orthogonal since
i1, i2, ..., ik by the condition are arbitrary distinct elements of 1, t.
Corollary 2. If a set Σ = {At
1} of polynomial d-operations satisfies
the condition of Proposition 2, then a set Σ = {Bt
1} of polynomial s-
operations, s > d, where
Bi(x
s
1) = Ai(x
d
1) + ai,d+1xd+1 + ... + ai,sxs, i ∈ 1, t,
with arbitrary ai,d+1, ai,d+2, ..., ai,s ∈ GF (q) is also k-wise orthogonal
set.
Proof. In this case the same k-minors different from 0 of the determinant
A, defined by Σ, can be used, then the corresponding system of k equa-
tions with s− k variables on the right side has a unique solution for qs−k
values of these variables. It means that the set Σ of s-ary operations is
k-wise orthogonal.
Example 1. Consider the set Σ = {A4
1} with the following polyno-
mial 4-ary operations over a field GF (p) of a prime order p ≥ 7:
A1(x
4
1) = x1 + 2x2 + 3x3 + 4x4,
A2(x
d
1) = 2x1 + 3x2 + 4x3 + 4x4,
A3(x
d
1) = x1 + 3x2 + 6x3 + 3x4,
A4(x
d
1) = x1 + x2 + x3 + 5x4.
This set of t=4, 4-operations is 3-wise orthogonal. Indeed, it easy to check
that in every three rows of the determinant defined by these operations
there exists 3-minor different from 0 by p ≥ 7. Namely, in the triples
< 1, 2, 3 >, < 1, 3, 4 >, < 2, 3, 4 > of rows these 3-minors include the
first three columns, and in the triple < 1, 2, 4 > it is 3-minor including
the first, the third and the fourth columns. Thus, by Proposition 2 the
set Σ is 3-wise orthogonal for any p ≥ 7.
From this set of four polynomial 4-operations over a field of a prime
order p ≥ 7 by according to Corollary 2 a 3-wise orthogonal set of four
polynomial s-operations over the same field can be constructed for s > 4.
8 Strongly orthogonal and uniformly orthogonal...
4. Strongly orthogonal sets of d-ary operations
In [1] it was introduced the notion of a strongly orthogonal set of d-
operations. Using Definition 2 we can reformulate this notion of [1] in
the following way.
Definition 3. A set Σ = {At
1}, t ≥ 1, of d-ary operations, given on
a set Q, is called strongly orthogonal if the set Σ = {At
1, E
d
1} is d-wise
orthogonal.
Note that in the case of a strongly orthogonal set Σ = {At
1} of d-ary
operations the number t of d-operations in Σ can be smaller than arity
d.
By Theorem 2 each d-operation Ai, i = 1, 2, ..., t, of a strongly or-
thogonal set Σ = {At
1} is a d-quasigroup, has type jmax(Ai) = d− 1 and
any type j1, 0 ≤ j1 < d − 1, by Corollary 1. Moreover, a d-operation A
is a d-quasigroup if and only if the set Σ = {A} is strongly orthogonal.
A set of d-quasigroups by d > 2, t ≥ d can be d-wise orthogonal but not
strongly orthogonal in contrast to the binary case (d=2).
By Theorem 1 for a strongly orthogonal set Σ of d-operations the set
Σ = {At
1, E
d
1} is k-wise orthogonal for any k, 1 ≤ k ≤ d.
Now we generalize the notion of Definition 3 in the following way.
Definition 4. Let k be a fixed number, 1 ≤ k ≤ d. A set Σ = {At
1}, t ≥ 1,
of d-operations is called k-wise strongly orthogonal if the set Σ = {At
1, E
d
1}
is k-wise orthogonal.
By k = d we have Definition 3. From the definition of a k-wise
strongly orthogonal set and Theorem 2 it follows
Corollary 3. Let jmax(A) be the maximal type of a d-operation A. Then
k − 1 ≤ jmax(Ai) ≤ d − 1 for each d-operation Ai of a k-wise strongly
orthogonal set Σ = {At
1}. For every d-operation Ai of a 2-wise strongly
orthogonal set 1 ≤ jmax(Ai) ≤ d − 1.
From Theorem 1 it immediately follows
Proposition 3. A k-wise strongly orthogonal set of d-operations is l-wise
strongly orthogonal for each l, 1 ≤ l < k.
Let < A1, A2, ..., Ak > be a k-tuple of distinct d-operations. By <
B1, B2, ..., Bk >ā we denote the k-tuple of (d − j)-retracts, defined by a
2j-tuple ā ∈ Ij , of the d-operations A1, A2, ..., Ak respectively.
G. Belyavskaya, G. L. Mullen 9
Lemma 1. Let k be a fixed number, 1 ≤ k ≤ d, j be a fixed number,
0 ≤ j ≤ k − 1, {i1, i2, ..., ij} be a fixed subset of 1, d . A k-tuple
T =< A1, A2, ..., Ak−j , Ei1 , Ei2 , ..., Eij >
of distinct d-operations, defined on a set Q, is orthogonal if and only if the
(k−j)-tuple < B1, B2, ..., Bk−j >ā of the (d−j)-retracts of A1, A2, ..., Ak−j
respectively defined by a tuple ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) is orthogo-
nal for each of | Q |j tuples ā ∈ Ij with the subset {i1, i2, ..., ij} ⊆ 1, d.
Proof. At first we note, that if k > 1, j = 0, then T =< A1, A2, ..., Ak >.
By k = 1 we have j = 0 and orthogonality of the 1-tuple < A1 > means
that the d-operation A1 is complete. When j = k − 1 we have a k-tuple
T =< A1, Ei1 , Ei2 , ..., Eik−1
> and orthogonality of T means that the
(d − k + 1)-retract of A1 is complete.
Let T be an orthogonal k-tuple of d-operations of order n, then by
Definition 1 the system
{A1(x
d
1) = a1, A2(x
d
1) = a2, . . . , Ak−j(x
d
1) = ak−j ,
Ei1(x
d
1) = ai1 , Ei2(x
d
1) = ai2 , . . . , Eij (x
d
1) = aij} (2)
has nd−k solutions for all a1, a2, ...ak−j , ai1 , ai2 , ..., aij ∈ Q. From this
system it follows that
xi1 = ai1 , xi2 = ai2 , ..., xij = aij
by the definition of the selectors. Substituting these values in Ai, i =
1, 2, ..., k−j, we obtain the (d−j)-retracts B1, B2, ..., Bk−j of A1, A2, ..., Ak−j
respectively defined by the tuple ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij .
The (k − j)-tuple
< B1, B2, ..., Bk−j >ā is orthogonal since the system
{B1(y
d−j
1 ) = a1, B2(y
d−j
1 ) = a2, . . . , Bk−j(y
d−j
1 ) = ak−j}
has nd−k = n(d−j)−(k−j) solutions for all a1, a2, ..., ak−j ( since the k-
tuple T is orthogonal). It is true for all (ai1 , ai2 , ..., aij ) ∈ Qj by the fixed
{i1, i2, ..., ij} ⊆ 1, d.
Converse, let each (k − j)-tuple < B1, B2, ..., Bk−j >ā of (d − j)-
retracts of d-operations A1, A2, ..., Ak−j , defined by a tuple
ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij
with a fixed subset {i1, i2, ..., ij} ⊆ 1, d for some elements ai1 , ai2 , ..., aij ∈
Q is orthogonal. This means that the system
{B1(y
d−j
1 ) = a1, B2(y
d−j
1 ) = a2, . . . , Bk−j(y
d−j
1 ) = ak−j}
10 Strongly orthogonal and uniformly orthogonal...
has n(d−j)−(k−j) = nd−k solutions for all a1, a2, ..., ak−j ∈ Q and the
system (2) has nd−k solutions for all a1, a2, ...ak−j ∈ Q and the fixed
ai1 , ai2 , ..., aij ∈ Q. The same we have fixing any another j-tuple
(a′i1 , a
′
i2
, ..., a′ij ) ∈ Qj and obtaining another (k − j)-tuple of (d − j)-
retracts defined by the tuple ā′ = (i1, i2, ..., ij ; a
′
i1
, a′i2 , ..., a
′
ij
) ∈ Ij . Thus,
the k-tuple T is orthogonal.
Let k (j) be a fixed number, 1 ≤ k ≤ d (0 ≤ j ≤ k − 1). Denote by
Σā = {B1, B2, ..., Bt} the set of the (d − j)-retracts of d-operations from
a set Σ = {A1, A2, ..., At}, defined by a fixed tuple
ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij .
Theorem 3. Let k be a fixed number, 1 ≤ k ≤ d. A set Σ = {At
1} of
d-operations, defined on a set Q, is k-wise strongly orthogonal if and only
if for each j, 0 ≤ j ≤ k−1, if t ≥ k (for each j, k−t ≤ j ≤ k−1, if t < k)
and for each ā ∈ Ij the set Σā = {B1, B2, ..., Bt} of the (d − j)-retracts
of A1, A2, ..., At, defined by ā, is (k − j)-wise orthogonal.
Proof. Let a set Σ = {At
1} be k-wise strongly orthogonal, that is the set
Σ = {At
1, E
d
1} is k-wise orthogonal by Definition 3. It means that each
k-tuple
< Al1 , Al2 , ..., Alk−j
, Ei1 , Ei2 , ..., Eij >
is orthogonal for each j, 0 ≤ j ≤ k−1, if t ≥ k (for each j, k−t ≤ j ≤ k−1,
if t < k) and for each subset {l1, l2, ..., lk−j} ⊆ 1, t. By Lemma 1 it
follows that the (k − j)-tuple < Bl1 , Bl2 , ..., Blk−j
>ā of the (d − j)-
retracts of Al1 , Al2 , ..., Alk−j
is orthogonal for each ā ∈ Ij and for each
{l1, l2, ..., lk−j} ⊆ 1, t. It means that the set Σā is (k− j)-wise orthogonal
for each ā ∈ Ij and for each j, 0 ≤ j ≤ k − 1 if t ≥ k (for each j,
k − t ≤ j ≤ k − 1, if t < k).
Converse, let each set Σā of (d − j)-retracts of the d-operations from
Σ is (k − j)-wise orthogonal for each j, 0 ≤ j ≤ k − 1, if t ≥ k (for each
j, k − t ≤ j ≤ k − 1, if t < k) and each ā ∈ Ij . Then each k-tuple
< Al1 , Al2 , ..., Alk−j
, Ei1 , Ei2 , ..., Eij >
is orthogonal by Lemma 1 for any suitable j and any l1, l2, ..., lk−j ⊆ 1, t.
It means that the set Σ = {At
1, E
d
1} is k-wise orthogonal and the set Σ is
k-wise strongly orthogonal.
For a d-wise strongly orthogonal set according to Theorem 3 by k = d
and Theorem 1 we have
G. Belyavskaya, G. L. Mullen 11
Corollary 4. If a set Σ = {At
1} of d-operations is d-wise strongly or-
thogonal, then the set Σā = {Bt
1} of the (d−j)-retracts of A1, A2, ..., At is
(d−j)-wise orthogonal (and j1-wise orthogonal for each j1, 1 ≤ j1 ≤ d−j)
for each j, 0 ≤ j ≤ d− 1, if t ≥ d (for each j, d− t ≤ j ≤ d− 1, if t < d)
and for each ā ∈ Ij.
As it was said above, all d-operations of a strongly orthogonal set are
d-quasigroups, so we shall consider only sets of polynomial d-quasigroups
(in this case all mappings xj → aijxj are permutations) by establishment
of criterion for strongly orthogonality of a set of polynomial operations.
Proposition 4. A set Σ = {At
1} of polynomial d-quasigroups, d ≥ 2,
with the determinant A over a field is strongly orthogonal if and only if
all k-minors for each k, 2 ≤ k ≤ d, if t ≤ d (for each k, 2 ≤ k ≤ t, if
t < d) of A is not equal 0.
Proof. By Definition 3 and Theorem 3 a set Σ is strongly orthogonal if
and only if for each j, 0 ≤ j ≤ d−1, if t ≥ d (for each j, d−t ≤ j ≤ d−1, if
t < d) the set Σā = {B1, B2, ..., Bt} of the (d−j)-retracts of A1, A2, ..., At,
defined by a ∈ Ij is (d − j)-wise orthogonal. By Proposition 1 this holds
by d− j ≥ 2 if and only if all (d− j)-minors of the determinant A are not
equal 0. For j = d− 1 (d− j = 1) we have the set Σā of 1-ary operations
which are permutations in the case of d-quasigroups, so composes an
1-wise orthogonal set.
Example 2. Let (Q,+, ·) be the field of a prime order p = 17 or
p > 19. Consider the polynomial ternary quasigroups
A1(x
3
1) = 2x1 + 2x2 + 3x3,
A2(x
3
1) = 5x1 + 4x2 + 3x3,
A3(x
3
1) = x1 + 6x2 + 5x3.
By Proposition 4 the set Σ = {A1, A2, A3} is strongly orthogonal,
since it is easy to check that the 3-minor and all 2-minors of the respective
determinant are different from 0.
Now we consider k-wise strongly orthogonal sets of polynomial d-
operations. At first we remind that from Theorem 3 it follows that each
(d − k + 1)-retract of each d-operation of k-wise strongly orthogonal set
is complete. Taking this into account, we shall consider only such d-
operations by establishment the following sufficient condition for k-wise
strongly orthogonal set of polynomial d-operations.
12 Strongly orthogonal and uniformly orthogonal...
Proposition 5. Let k be a fixed number, 2 ≤ k ≤ d, Σ = {At
1} be a set
of polynomial d-operations over a field with the determinant A. The set
Σ is k-wise strongly orthogonal if
(i) all (d − k + 1)-retracts of each d-operations of Σ are complete;
(ii) for each j, 0 ≤ j ≤ k− 2 , if t ≥ k (for each j, k− t ≤ j ≤ k− 2,
if
t < k ) in every k − j rows of the determinant A without any j columns
there exists a (k − j)-minor different from 0.
Proof. Let ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij and Σā = {B1, B2, ..., Bt}
be the set of the (d − j)-retracts of A1, A2, ..., At, then the set Σā corre-
sponds to the determinant A of order t× (d−j) which is the determinant
A without fixed j columns i1, i2, ..., ij (by any ai1 , ai2 , ..., aij , since the
corresponding system must be solved for any right parts of the equa-
tions). If in each k − j rows of the determinant A there exists at least
one (k − j)-minor different from 0, then by Proposition 2 the set Σā is
(k − j)-wise orthogonal for j, 0 ≤ j ≤ k − 2. If j = k − 1, Σā consists of
(d − k + 1)-retracts which by (i) are complete and so 1-wise orthogonal.
Thus , by Theorem 3 Σ is k-wise strongly orthogonal.
Example 3. We shall illustrate Proposition 13 at the set Σ =
{A1, A2, A3} of the following three polynomial 4-ary operations (quasi-
groups):
A1(x
4
1) = x1 + 2x2 + 3x3 + 4x4,
A2(x
4
1) = 2x1 + 3x2 + 4x3 + 4x4,
A3(x
4
1) = x1 + 3x2 + 6x3 + 3x4
over the field GF (p) of a prime order p ≥ 7. Check by Proposition 5
that the set Σ is 3-wise strongly orthogonal.
In this case d = 4, k = t = 3, 0 ≤ j ≤ 1. All (d − k + 1) = 2-
retracts of every 4-operation of Σ are complete since these operations are
4-quasigroups.
If j = 0, then k− j = 3 and the 3-minor in the determinant A defined
by Σ with the first three columns is different from 0.
If j = 1, then k − j = 2. In this case it is easy to check that in A
without any one of four columns, in each two rows there exists a 2-minor
different from 0.
Thus, be Proposition 5 the set Σ is 3-wise strongly orthogonal.
G. Belyavskaya, G. L. Mullen 13
5. Uniformly orthogonal sets of d-ary operations
Two d-hypercubes, d ≥ 2, H1 and H2 is called j-uniformly orthogonal if
when superimposed and any j, 0 ≤ j ≤ d − 2, coordinates are fixed, the
resulting subarrays of dimention d − j are themselves orthogonal. This
notion of the j-uniformly orthogonality of two d-hypercubes naturally
leads to the following concept for d-operations, if we take into account
that an fixation of coordinates in a hypercube H leads to a retract of the
corresponding operation AH .
Definition 5 . Two d-operations A1 and A2 of order n is called j-
uniformly orthogonal for fixed j, 0 ≤ j ≤ d − 2, if the pair (B1, B2)ā of
the (d − j)-retracts of operations A1,A2 respectively, defined a tuple ā =
(i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij is orthogonal (that is, by the definition,
the system {Bl(y
d−j
1 ) = a1, B2(y
d−j
1 ) = a2} has n(d−j)−2 solutions for all
a1, a2 ∈ Q and for each tuple ā ∈ Ij).
Definition 5. A set Σ = {At
1}, t ≥ 2, of d-operations is called (2-wise)
j-uniformly orthogonal, 0 ≤ j ≤ d − 2, if any two operations of Σ are
j-uniformly orthogonal.
Proposition 6. A set Σ = {At
1} of d-operations is (2-wise) j-uniformly
orthogonal if and only if the (2 + j)-tuple < Al1 , Al2 , Ei1 , Ei2 , ..., Eij >
is orthogonal for each subset {i1, i2, ..., ij} ⊆ 1, d and for all l1, l2 ∈ 1, t,
l1 6= l2.
Proof. This follows from Definitions 5 and 6 and Lemma 1.
Now we generalize the notion of Definitions 5 and 6 in the following
way.
Definition 6. Let k be a fixed number, 1 ≤ k ≤ d, and j be a fixed num-
ber, 0 ≤ j ≤ d − k. A k-tuple < A1, A2, ..., Ak > of distinct d-operations
is called j-uniformly orthogonal if the k-tuple < B1, B2, ..., Bk >ā of the
(d − j)-retracts of A1, A2, ..., Ak, defined by a tuple
ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈ Ij ,
is orthogonal for each ā ∈ Ij.
Definition 7. Let k, j be fixed numbers, 1 ≤ k ≤ d, 0 ≤ j ≤ d− k. A set
Σ = {At
1}, t ≥ k, of d-operations is called k-wise j-uniformly orthogonal
if each k-tuple of distinct d-operations from Σ is j-uniformly orthogonal
(the same, if the set Σa of the (d − j)-retracts of d-operations from Σ is
k-wise orthogonal for any a ∈ Ij).
14 Strongly orthogonal and uniformly orthogonal...
It is easy to see that 0-uniformly orthogonality of a k-tuple < Ak
1 >
means that this k-tuple is itself orthogonal (I0 = ∅) and a k-wise 0-
uniformly orthogonal set is simply k-wise orthogonal.
If k = d, then j=0 and a set Σ is d-wise orthogonal.
In the case j = d − k we have
Id−k = {(i1, i2, ..., id−k; ai1 , ai2 , ..., aid−k
)}
and all k-tuples of (d − (d − k)) = k- retracts
< B1(y
k
1 ), B2(y
k
1 ), . . . , Bk(y
k
1 ) >ā
of A1, A2, ..., Ak are orthogonal , when ā ∈ Id−k. Taking this into account,
we obtain that if Σ = {At
1}, t ≥ k, of d-operations is a k-wise (d − k)-
uniformly orthogonal set, then the set Σā = {B1, B2, ..., Bt} of the k-
retracts of A1, A2, ..., At, defined by ā, is k-wise orthogonal for each ā ∈
Id−k.
By k=1 we obtain an 1-wise j-uniformly orthogonal set Σ = {At
1},
t ≥ 1, of d-operations, it means that every operation Ai of Σ has type
j and j ≤ jmax(Ai) ≤ d − 1 (see Theorem 2).
Proposition 7. Let k, j be fixed numbers, 1 ≤ k ≤ d, 0 ≤ j ≤ d − k. A
set Σ = {At
1}, t ≥ k, of d-operations is k-wise j-uniformly orthogonal if
and only if the (k + j)-tuple (1 ≤ k + j ≤ d)
< As1
, As2
, ..., Ask
, Ei1 , Ei2 , ..., Eij >
is orthogonal for all {s1, s2, ..., sk} ⊆ 1, t and for all {i1, i2, ..., ij} ⊆ 1, d.
Proof. Let a set Σ be k-wise j-uniformly orthogonal. Then by Defi-
nitions 7 and 8 each k-tuple < Bs1
, Bs2
, ..., Bsk
>ā of the operations
As1
, As2
, ..., Ask
from Σ, defined by a tuple ā = (i1, i2, ..., ij ; ai1 , ai2 , ..., aij ) ∈
Ij , is orthogonal for each subset {i1, i2, ..., ij} ⊆ 1, d and for each tuple
(ai1 , ai2 , ..., aij ) ∈ Qj . Now use Lemma 1.
Converse, if a (k + j)-tuple < As1
, As2
, ..., Ask
, Ei1 , Ei2 , ..., Eij > is
orthogonal for all subsets S = {s1, s2, ..., sk} ⊆ 1, t and for all I =
{i1, i2, ..., ij} ⊆ 1, d, then by Lemma 1 each (k + j − j) = k-tuple
< Bs1
, Bs2
, ..., Bsk
>ā of the (d− j)-retracts of As1
, As2
, ..., Ask
is orthog-
onal for all subsets S of 1, t , for all subsets I of 1, d and all ā ∈ Ij . Thus,
the set Σ is k-wise j-uniformly orthogonal by Definitions 7 and 8.
Corollary 5. Each k-wise j-uniformly orthogonal set is l-wise j1-uniformly
orthogonal for each l, 1 ≤ l ≤ k, and for each j1, 0 ≤ j1 ≤ j.
G. Belyavskaya, G. L. Mullen 15
Proof. From Theorem 1 it follows that each (l + j1)-tuple
< As1
, As2
, ..., Asl
, Ei1 , Ei2 , ..., Eij1
>
is orthogonal for all l, 1 ≤ l ≤ k, for all j1, 0 ≤ j1 ≤ j, for all
{s1, s2, ..., sl} ⊆ 1, t and for all {i1, i2, ..., ij1} ⊆ 1, d. Now use Propo-
sition 7 for the (l + j1)-tuples.
Corollary 6. Let jmax(A) denote the maximal type of a d-operation A,
1 ≤ k ≤ d, 0 ≤ j ≤ d − k, Σ = {At
1} be a k-wise j-uniformly orthogonal
set of d-operations. Then
j ≤ jmax(Ai) ≤ d − 1
for each d-operation Ai of Σ.
Proof. From Proposition 7 and Corollary 5 it follows that (1 + j)-tuple
< As1
, Ei1 , Ei2 , ..., Eij > is orthogonal for each d-operation As1
∈ Σ and
each
{i1, i2, ..., ij} ⊆ 1, d. Thus, the set {As1
, Ed
1} is (j + 1)-wise orthogonal
and by Theorem 2 the operation As1
has at least type j.
Corollary 7. For each d-operation Ai of an 1-wise (d − 1)-uniformly
orthogonal set Σ = {At
1}, jmax(Ai) = d− 1, that is Ai is a d-quasigroup.
Proof. In this case k = 1, j = d − 1 and jmax(Ai) = d − 1 by Corollary
6. But by Corollary 1 of [3] a d-operation has type j = d − 1 if and only
if it is a d-quasigroup.
For a set of polynomial d-operations over a field the following sufficient
condition of k-wise j-uniformly orthogonality can be given.
Proposition 8. Let Σ = {At
1}, d ≥ 2, be a set of polynomial d-operations
over a field GF (q) with the determinant A, k, j be an fixed number, 2 ≤
k ≤ d, 0 ≤ j ≤ d − k k ≤ t. Then Σ is k-wise j-uniformly orthogonal if
in each k rows of A without any j columns there exists k-minor different
from 0.
Proof. According to Definition 8 the set Σ is k-wise j-uniformly orthog-
onal if and only if the set Σa of (d − j)-retracts of the d-operations from
Σ is k-wise orthogonal by any a ∈ Ij . Now use Proposition 2 for the set
Σa, which corresponds to the determinant A without j columns.
Example 4. Using this proposition we give an example of 3-wise
1-uniformly orthogonal set 5-ary operations over a field GF (q) with a
prime q ≥ 7. Let Σ = {A1, A2, A3, A4}, where
16 Strongly orthogonal and uniformly orthogonal...
A1(x
5
1) = x1 + x2 + x3 + x4 + x5,
A2(x
5
1) = 2x1 + 3x2 + 5x3 + 4x4 + x5,
A3(x
4
1) = 3x1 + 2x2 + 4x3 + x4 + 2x5,
A4(x
4
1) = x1 + 4x2 + 3x3 + 2x4 + 3x5.
In this case d = 5, t = 4,j = 1. It is easy to check that by fixation the
columns with numbers 1,2,4 and 5 in the corresponding determinant A
of Σ the 3-minors in any three rows with the first three possible columns
is not equal 0. By fixation the column with number 3 in rows 1,2,3 the
3-minor in columns 1,2,5 is not equal 0, whereas for rows 1,3,4 and 2,3,4
the 3-minors in columns 1,2,4 are not equal 0.
The following theorem establishes a connection between k-wise strongly
orthogonal and l-wise j-uniformly orthogonal sets.
Theorem 4. Let k be a fixed number, 1 ≤ k ≤ d. A k-wise strongly
orthogonal set of d-operations is l-wise j-uniformly orthogonal for each l,
1 ≤ l ≤ k, and for each j, 0 ≤ j ≤ k − l.
Proof. Let a set Σ = {At
1}, k ≤ t, be k-wise strongly orthogonal. Then
by Definition 4 the set Σ = {At
1, E
d
1} is k-wise orthogonal, so each k-tuple
< As1
, As2
, ..., Asl
, Ei1 , Ei2 , ..., Eik−l
>
is orthogonal for all l, 1 ≤ l ≤ k, for each subset {s1, s2, ..., sl} ⊆ 1, t and
for each subset {i1, i2, ..., ik−l} ⊆ 1, d. By Proposition 7 the set Σ is l-
wise (k− l)-uniformly orthogonal and by Corollary 5 is l-wise j-uniformly
orthogonal for each j, 0 ≤ j < k − l.
Thus, from Theorem 4 it follows that a k-wise strongly orthogonal set
Σ is
1-wise 0−, 1−, ... and (k − 1)-uniformly orthogonal,
2-wise 0−, 1−, ... and (k − 2)-uniformly orthogonal,
3-wise 0−, 1−, ... and (k − 3)-uniformly orthogonal,...,
(k − 2)-wise 0-,1- and 2-uniformly orthogonal,
(k − 1)-wise 0- and 1-uniformly orthogonal,
k-wise 0-uniformly orthogonal.
So, for the 3-wise strongly orthogonal set Σ = {A1, A2, A3} of the
4-ary operations in Example 3 we have that Σ is
1-wise 0-,1- and 2-uniformly orthogonal,
2-wise 0- and 1-uniformly orthogonal,
3-wise 0-uniformly orthogonal.
From Theorem 4 by k = d immediately it follows
G. Belyavskaya, G. L. Mullen 17
Corollary 8. A strongly orthogonal set of d-operations is l-wise j-uniformly
orthogonal for each l, 1 ≤ l ≤ d, and for each j, 0 ≤ j ≤ d − l.
So, in Example 2 the strongly orthogonal set Σ = {A1, A2, A3} of
ternary operations is
1-wise 0-,1- and 2-uniformly orthogonal,
2-wise 0- and 1-uniformly orthogonal,
3-wise 0-uniformly orthogonal.
References
[1] A.S. Bektenov and T. Yacubov, Systems of orthogonal n-ary operations (In Rus-
sian). Izv. AN Moldavskoi SSR, Ser. fiz.-teh. i mat. nauk, no. 3, 1974, 7–14.
[2] V.D. Belousov, n-Ary quasigroups. Shtiintsa, Kishinev, 1972.
[3] G. Belyavskaya, Gary L. Mullen, Orthogonal hypercubes and n-ary operations.
Quasigroups and related systems, no.13, 2005 (to appear).
[4] K. Kishen, On the construction of latin and hyper-graeco-latin cubes and hyper-
cubes. J. Ind. Soc. Agric. Statist. 2, (1950), 20–48.
[5] C.F. Laywine, G.L. Mullen, and G. Whittle, D-Dimensional hypercubes and the
Euler and MacNeish conjectures. Monatsh. Math. 111 (1995), 223–238.
[6] D.K. Faddeev, Lections on algebra (In Russian). Nauka, Moscow, 1984.
Contact information
G. Belyavskaya Institute of Mathematics and Computer Sci-
ence, Academy of Sciences, Academiei str. 5
MD-2028, Chisinau, Moldova
E-Mail: gbel@math.md
G. L. Mullen Department of Mathematics, The Pennsyl-
vania State University, University Park, PA
16802, USA
E-Mail: mullen@math.psu.edu
|