ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.09 / 301–307
https://doi.org/10.26493/1855-3974.2388.928
(Also available at http://amc-journal.eu)
On generalized strong complete mappings and
mutually orthogonal Latin squares*
Amela Muratović-Ribić †
University of Sarajevo, Faculty of Science,
Zmaja od Bosne 33-35, Sarajevo, Bosnia and Herzegovina
Received 20 July 2020, accepted 1 April 2021, published online 2 November 2021
Abstract
We present an application of generalized strong complete mappings to construction of
a family of mutually orthogonal Latin squares. We also determine a cycle structure of
such mapping which form a complete family of MOLS. Many constructions of generalized
strong complete mappings over an extension of finite field are provided.
Keywords: Strong complete mapping, group, finite field, mutually orthogonal Latin squares (MOLS).
Math. Subj. Class. (2020): 11T06, 12Y05
1 Introduction
Let G be an additive group. A mapping θ : G → G is called a complete mapping if both
θ(x) and θ(x)+x are 1-to-1 and onto. If both θ(x) and θ(x)−x are 1-to-1 and onto, θ(x) is
called an orthomorphism. A strong complete mapping is a complete mapping which is also
an orthomorphism. These mappings are used for a construction of Knut Vic designs and
they exist only for the groups of order n where gcd(n, 6) = 1. An Abelian group admits
strong complete mappings if and only if its Sylow 2-subgroup is trivial or noncyclic, and
also, its Sylow 3-group is trivial or noncyclic (see [2]).
Let p be a prime, m be a positive integer and q = pm. Let Fq be a finite field of or-
der q. We consider complete and strong complete mappings (and orthomorphisms) over
(Fq(x),+). Polynomials induced by these mappings are called complete and strong com-
plete polynomials, respectively. In [1], strong complete mappings over finite fields are
called very complete mappings. Many results have been established on this topic. In the
*Results in this article were partially presented on the Carleton Finite Fields Workshop, May 21 – 24, 2019.
†The author gratefully thanks the anonymous referee for the constructive comments and recommendations
which definitely helped to improve the quality of the paper.
E-mail address: amela@pmf.unsa.ba (Amela Muratović-Ribić)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
302 Ars Math. Contemp. 21 (2021) #P2.09 / 301–307
sequel, f0(x) = x, f2(x) = f ◦ f(x), fk(x) = f ◦ fk−1(x) for k > 0. Generalized
complete polynomials were introduced in [6] with applications to the check digit systems.
There were considered polynomials over finite fields with a property that f(x), f(x) ± x
and f2(x) ± x are all permutation polynomials. Note that there exist monomials of the
form xℓ
q−1
m where m | q − 1 with this property (see [5]).
We turn our attention to mappings θ(x) such that θk(x) are strong complete mappings
for all k = 1, 2, ..., t. Here, t is a positive integer. Our point of interest is an application
of these mappings to construction of mutually orthogonal Latin squares (MOLS). Many
constructions of such mappings over finite fields will be presented.
2 Construction of MOLS
Theorem 2.1. LetG be an additive finite Abelian group of order n, where n is odd. Assume
that θ : G→ G is such that θk(x) are strong complete mappings for k = 1, 2, . . . , t where
t is a positive integer. For 1 ≤ k ≤ t and i, j ∈ G define
aki,j = i+ θ
k(j)
a−ki,j = i− θ
k(j)
a0
+
i,j = i+ j; a
0−
i,j = i− j.
A family of Latin squares Lk = (aki,j) where k = −t, . . . ,−1, 0−, 0+, 1 . . . t is a family
of pairwise mutually orthogonal Latin squares. Therefore, a family of 2(t + 1) MOLS is
obtained.
Proof. We use the following convention θ0
±
(x) = x. Assume (aki,j , a
s
i,j) = (a
k
u,v, a
s
u,v)
for k ̸= s and consider the following cases:
• If (0 < s < k) or (s = 0+ and 0 < k) we have that
i+ θk(j) = u+ θk(v) (2.1)
and
i+ θs(j) = u+ θs(v).
Subtracting these equalities we obtain
θk(j)− θs(j) = θk(v)− θs(v).
Thus
θk−s(θs(j))− θs(j) = θk−s(θs(v))− θs(v).
By assumption, θk−s(y) − y is a permutation. Hence, θs(j) = θs(v) and j = v.
Inserting this in (2.1) we obtain i = u.
• If (k < s < 0) or (k < 0 and s = 0−) then we have
i− θ|k|(j) = u− θ|k|(v) (2.2)
and
i− θ|s|(j) = u− θ|s|(v).
A. Muratović-Ribić: On generalized strong complete mappings and mutually orthogonal . . . 303
Subtracting these equalities, we obtain
θ|k|(j)− θ|s|(j) = θ|k|(v)− θ|s|(v).
Thus
θ|k|−|s|(θ|s|(j))− θ|s|(j) = θ|k|−|s|(θ|s|(v))− θ|s|(v).
Reasoning as above, we get j = v and i = u.
• If (−s < 0 < k), (s = 0− and k > 0) or (s < 0 and k = 0+) then we have that
i+ θk(j) = u+ θk(v) (2.3)
and
i− θ|s|(j) = u− θ|s|(v)
which implies
θk(j) + θ|s|(j) = θk(v) + θ|s|(v).
Assume first k > |s|. Then θk−|s|(θ|s|(j)) + θ|s|(j) = θk−|s|(θ|s|(v)) + θ|s|(v).
As θk−|s|(y) + y is a permutation, it follows that θ|s|(j) = θ|s|(v). Thus j = v.
Using this in (2.3), we obtain i = u. If k ≤ |s| then θ|s|−k(θk(j)) + θk(j) =
θ|s|−k(θk(v)) + θk(v) similarly implies j = v and i = u.
• If k = 0+ and s = 0− then i+ j = u+ v and i− j = u− v which implies 2i = 2u.
Then 2ki = 2ku for all integers k. By assumption, the order of the group G is an
odd integer. Then n + 1 is even and thus (n + 1)i = (n + 1)u. However, ni = nu
by Lagrange’s theorem. Hence, i = u and further j = v.
Lemma 2.2. Let G be a group of order n. Assume that θ : G → G is such that all θk(x)
are strong complete mappings for k = 1, 2, . . . , t. Then the permutation θ has exactly one
fixed element and lengths of all other cycles are greater than t.
Proof. Assume that ℓ is the length of a cycle (a1, a2, . . . , aℓ) of the permutation θ, where
1 < ℓ ≤ t. Then θℓ(a1) = a1 and θℓ(a2) = a2. Therefore θℓ(a1)−a1 = θℓ(a2)−a2 = 0.
It follows that θℓ(x) − x is not a permutation which is a contradiction. Therefore, there is
no cycle of the length 1 < ℓ ≤ t. Since θ(x) − x is a permutation, there is exactly one
solution of the equation θ(x)− x = 0 and thus exactly one fixed element of θ.
Theorem 2.3. If θ generates a complete set of MOLS over a finite Abelian group of order
n as in the Theorem 2.1, then θ has either one fixed element and one cycle of the length
n− 1 or one fixed element and two cycles of the length n−12 .
Proof. In this case all θk(x) are strong complete mappings for k = 1, 2, . . . , n−12 − 1. By
the Lemma 2.2, there is one fixed element in the permutation θ and the lengths of nontrivial
cycles are greater than n−12 − 1. It follows that there can either one such cycle with the
length n− 1 or two cycles of the length n−12 .
Remark 2.4. Let Zp be a field of order p, where p > 2 is a prime. Let d be a generator of
Z∗p. Then θk(s) = dks is a strong complete mapping for k = 1, 2, . . . ,
p−3
2 . The mapping
θ(s) has a fixed element s = 0 and one full cycle (1, d, d2, ..., dp−2) of the length p−1. On
the other hand, θ2(s) = d2s has a property that θ2k(s) = d2ks is also a strong complete
mapping for all k = 1, 2, . . . , p−32 since
p−1
2 is odd. This mapping has a fixed element
s = 0 and two cycles of the length p−12 .
304 Ars Math. Contemp. 21 (2021) #P2.09 / 301–307
Proposition 2.5. Assume that Ψ : G → G, is a permutation such that Ψ(x ± y) =
Ψ(x)±Ψ(y) for all x, y ∈ G. If θ(x) generates a complete set of MOLS as in Theorem 2.1,
then η(x) = Ψ ◦ θ ◦Ψ−1(x) also generates a complete set of MOLS.
Note: An example of the mapping is Ψ(x) = kx where k is an integer, which prove its
existence.
Proof. Since ηk(x) = Ψ ◦ θk ◦ Ψ−1(x) is a permutation we need to show that ηk(x) + x
and ηk(x)− x are permutations for all k = 1, 2, . . . |G|−12 . Using substitution y = ψ
−1(x)
we get
ηk(x)±x = Ψ[θk(Ψ−1(x))]±Ψ(Ψ−1(x)) = Ψ[θk(Ψ−1(x))±Ψ−1(x)] = Ψ(θk(y)±y).
This is a permutation since Ψ(x) and θk(x)±x are permutations. Therefore, η(x) generates
a complete set of MOLS.
Let Fq be a field with a prime subfield Zp. Linearized polynomials over Fq are of the
form L(x) =
∑m
k=0 akx
pk and these polynomials have property that L(ax) = aL(x) for
all a ∈ Zp and L(x + y) = L(x) + L(y) for all x, y ∈ Fq . Thus, if we consider Fq as a
vector space over Zp, then L(x) is a linear operator on Fq .
Corollary 2.6. Let Fq be a finite field of order q = pn where p is a prime. Let d be a
primitive element of Fq and L(x) be a linearized permutation polynomial of Fq . Then the
polynomial f(x) = L(dL−1(x)) generates a complete set of MOLS as in Theorem 2.1.
Proof. It is easy to see that sx is strong complete polynomial for s ∈ Fq \ {0,±1}. There-
fore, for g(x) = dx, gk(x) = dkx are strong complete mappings for all k ̸= q−12 , q − 1.
Since, L(x ± y) = L(x) ± L(y) we have that f(x) = L ◦ g ◦ L−1(x) = L(dL−1(x))
generates a complete set of MOLS as in Theorem 2.1.
Remark 2.7. Consider a family of strong complete polynomials over finite field Fq which
generate a complete set of MOLS as in Theorem 2.1 and which have one fixed element
and one cycle of the length q − 1. Let d be a generator of F∗q . Then f(x) = dx is in this
family and considering the cycle structure, all other polynomials are conjugate with f(x).
Therefore, all polynomials in this family are of the form Ψ(dΨ−1(x)) for some permutation
polynomial Ψ(x) over Fq .
If q−12 is odd, then g(x) = d
2x is a strong polynomial which generate a complete
family of MOLS as in Theorem 2.1 and which have one fixed element and two cycles of
the length q−12 . Similarly, all other strong complete mappings with a same cycle structure
induce a polynomial of the form Ψ(d2Ψ−1(x)) for some permutation polynomial Ψ(x)
over Fq .
3 Construction of the strong complete mappings over extension fields
Let n be a positive integer and Fqn be an extension field of Fq . Let {α1, α2, . . . , αn} be
a basis of the vector space Fqn over Fq . We shall use similar technique as in the proof of
Theorem 2.1 in [3] to obtain the following recursive constructions of many strong complete
polynomials over the extension field.
A. Muratović-Ribić: On generalized strong complete mappings and mutually orthogonal . . . 305
Theorem 3.1. Let fi(x) be strong complete polynomials over Fq for i = 1, 2, . . . , n. Let
ψi : Fiq → Fq be arbitrary functions for i = 1, 2, . . . , n− 1. Denote X = x1α1 + x2α2 +
· · ·+ xnαn. Then the function
F (X) = f1(x1)α1 + [f2(x2) + ψ1(x1)]α2 + · · ·+ [fn(x) + ψn−1(x1, x2, . . . , xn−1)]αn
is a strong complete polynomial over Fqn .
Proof. In the proof of Theorem 1 in [3], it was shown that F (X) is a complete polynomial.
To show that it is a strong complete polynomial, lets check that F (X) −X is 1 − to − 1.
Assume that F (X) − X = F (Y ) − Y for X = x1α1 + x2α2 + · · · + xnαn and Y =
y1α1 + y2α2 + · · ·+ ynαn. Then the coefficients with the basis elements on the two sides
of equation are identical.
Looking at the coefficient with α1 we see that f1(x1)− x1 = f1(y1)− y1. As f1(x) is
orthomorphism it follows that x1 = y1 .
Now, equating the coefficients with α2 we get f2(x2) + ψ1(x1) − x2 = f2(y2) +
ψ1(y1) − y2. Taking into account x1 = y1, this implies f2(x2) − x2 = f2(y2) −
y2. Hence, x2 = y2 since f2(x) is an orthomorphism. We proceed by induction. As-
sume that x1 = y1, x2 = y2, . . . , xi−1 = yi−1 which imply ψi−1(x1, x2, . . . , xi−1) =
ψi−1(y1, y2, . . . , yi−1). Comparing the coefficients with αi, we obtain
fi(xi) + ψi−1(x1, x2, . . . , xi−1)− xi = fi(yi) + ψi−1(y1, y2, . . . , yi−1)− yi.
Thus fi(xi)− xi = fi(yi)− yi. So, xi = yi since fi(x) is an orthomorphism. Therefore,
xi = yi for all i = 1, 2, . . . , n and X = Y . Now, F (X)−X being 1− to− 1 on the finite
set Fqn it is a bijection, i.e. a permutation.
In the case of linearized polynomials, we extend the same technique to the compositions
of mappings. The proofs of the next theorems are similar to the proof of the Theorem 3.1.
So, we may omit a number of details.
Theorem 3.2. Let fi(x), i = 1, 2, . . . , n, be linearized strong complete polynomials over
Fq such that fki (x) are also strong complete polynomials for k = 1, 2, ..., t. Let ψi : Fiq →
Fq be arbitrary functions for i = 1, 2, . . . , n−1. Denote X = x1α1+x2α2+ · · ·+xnαn.
Then function
F (X) = f1(x1)α1 + [f2(x2) + ψ1(x1)]α2 + · · ·+ [fn(x) + ψn−1(x1, x2, . . . , xn−1)]αn
is a strong complete polynomial over Fqn such that F (k)(X) are also strong complete
mappings for all k = 2, 3, ..., t.
Proof. By Theorem 3.1, F (X) is a strong complete polynomial. Since F (X) is permu-
tation, it follows that F (k)(X) are permutations for all k = 2, · · · , t. Assume now that
F (2)(X) +X = F (2)(Y ) + Y (or F (2)(X)−X = F (2)(Y )− Y ).
Equating the coefficients with α1 on the both sides, we get f
(2)
1 (x1)+x1 = f
(2)
2 (y1)+
y1 (or f
(2)
1 (x1) − x1 = f
(2)
2 (y1) − y1). This implies x1 = y1 because f
(2)
1 (x) is a strong
complete polynomial. With α2 we have
f2[f2(x2) + ψ1(x1)] + ψ1(f1(x1))± x2 = f2[f2(y2) + ψ1(y1)] + ψ1(f1(y1))± y2.
306 Ars Math. Contemp. 21 (2021) #P2.09 / 301–307
Since f2 is linearized, we obtain
f2(f2(x2))+f2(ψ1(x1))+ψ1(f1(x1))±x2 = f2(f2(y2))+f2(ψ1(y1))+ψ1(f1(y1))±y2.
Taking into account that x1 = y1, we get f2(f2(x2)) ± x2 = f2(f2(y2)) ± y2.This yields
x2 = y2 since f
(2)
2 (x2) is a strong complete polynomial. Proceeding by induction, we can
prove that x3 = y3, ..., xn = yn and thus X = Y . Therefore, F (2)(X) is strong complete.
We can also prove by induction that F (k)(X) are strong complete for all k = 2, 3, ..., t.
Proposition 3.3. Assume that f(x) is a permutation and that f(dx)+ f(x), f(dx)− f(x)
are also permutations where d ∈ Fq , d ̸= 0, d ̸= ±1. Then the polynomial gd(x) =
f(df−1(x)) is strong complete.
Proof. Assume that f(x), f(dx) + f(x) and f(dx) − f(x) are permutations. Let x =
f−1(y). Then f(df−1(y)), f(df−1(y)) + y and f(df−1(y))− y are permutations. There-
fore, gd(x) = f(df−1(x)) is a strong complete polynomial.
Note that g(2)d (x) = gd(f(df
−1(x)) = f(df−1(fdf−1(x))) = f(d2f−1(x)) = gd2(x)
and, by induction g(k)d (x) = gdk(x).
A permutation polynomial f(x) such that f(dx) − f(x) is also a permutation for all
d ∈ Fq , d ̸= 1, is called a Costas polynomial. The only Costas polynomial over a field of
the prime order p is xs where gcd(s, p− 1) = 1. The only known Costas polynomial over
Fq is L(xs) where gcd(s, q − 1) = 1 and L is a linearized permutation polynomial (see
[4]). The polynomial L(xs) satisfies the conditions of Proposition 2.5. Indeed, L(dxs) ±
L(xs) = L((d ± 1)xs) is permutation polynomial whenever d ± 1 ̸= 0 and d ̸= 0. Thus,
gd(x) = L(d
sL−1(x)) is strong complete polynomial for all ds ̸∈ {0, 1,−1}. Then,
g
(k)
d (x) = gdk(x) is the strong complete polynomial whenever d
ks ̸∈ {0, 1,−1}. If dsk1 +
dsk2 + · · ·+ dskt ̸∈ {0, 1,−1} for a set of positive integers K = {k1, k2, ..., kt} then
t∑
i=1
gkid (x)± x =
t∑
i=1
L(dskiL−1(x))± x = L((
t∑
i=1
dski)L−1(x))± x
is also a permutation. It follows that gd(x) is the K-strong complete mapping (see [6] ).
This class of K-strong complete polynomials is linearized. Now, we will present one more
construction of the nonlinearized generalized strong complete polynomials over extension
fields.
Theorem 3.4. Let fi(x) be permutation polynomials over Fq such that fi(dkx) ± fi(x)
are permutation polynomials for d ∈ F∗q , k = 1, 2, ..., t < q − 1 and i = 1, 2, ..., n. Let
ψi : Fiq → Fq be arbitrary functions for i = 1, 2, . . . , n− 1. Denote X = x1α1 + x2α2 +
· · ·+ xnαn. Then the mapping
F (X) = f1(x1)α1 + [f2(x2) + ψ1(x1)]α2 + · · ·+ [fn(x) + ψn−1(x1, x2, . . . , xn−1)]αn
is a permutation polynomial such that F (dkX) ± F (X) are permutation polynomials for
all k = 1, 2, ..., t.
Note: For functions fi(x) we can take L(xs) as discussed above.
A. Muratović-Ribić: On generalized strong complete mappings and mutually orthogonal . . . 307
Proof. As dk ∈ F∗q we have that dkX = dkx1α1 + dkx2α2 + ... + dkxnαn. Assume
F (dkX) ± F (X) = F (dkY ) ± F (Y ). Then, equating the coefficients with the basis
elements, we get f1(dkx1) ± f1(x1) = f1(dky1) ± f1(y1). Thus x1 = y1. Further,
f2(d
kx2)+ψ1(d
kx1)± (f2(x2)+ψ1(x1)) = f2(dky2)+ψ1(dky1)± (f2(y2)+ψ1(y1)).
Since x1 = y1, we have f2(dkx2)± f2(x2) = f2(dky2)± f2(y2). It follows that x2 = y2.
By induction, x3 = y3, ..., xn = yn. Hence, X = Y . Therefore, F (dkX) ± F (X) are
permutations for all k = 1, 2, ..., t.
Corollary 3.5. For a function F (X) defined in Theorem 3.4, the function Gd(X) =
F (dF−1(X)) is strong complete mapping with a property that G(k)d (X) are strong com-
plete mappings for all d = 1, 2, ..., t.
Proof. The result follows from Proposition 3.3 and G(k)d (X) = Gdk(X).
Note: If we put x1 = x2 = . . . = xn−1 = 0 and xn = 1, then in all constructions
presented in Section 3 we will form a cycle whose elements are of the form (0, 0, . . . , 0, s).
The length of this cycle is less or equals to q. Using Lemma 2.2, we obtain t < q. There-
fore, by means of Theorem 2.1 we can not obtain more than 2q of MOLS over Fqn using
constructions in the Section 3.
ORCID iDs
Amela Muratović-Ribić https://orcid.org/0000-0001-7903-4884
References
[1] W.-S. Chou, Permutation polynomials on finite fields and their combinatorial applications,
Ph.D. thesis, Penn State Universit, 1990, https://www.proquest.com/openview/
24d2ca00f8f48ffe88a97a7c431a2096/1?pq-origsite=gscholar&cbl=
18750&diss=y.
[2] A. B. Evans, The existence of strong complete mappings of finite groups: a survey, Discrete
Math. 313 (2013), 1191–1196, doi:10.1016/j.disc.2011.11.040.
[3] A. Muratović-Ribić and E. Pasalic, A note on complete polynomials over finite fields and their
applications in cryptography, Finite Fields Appl. 25 (2014), 306–315, doi:10.1016/j.ffa.2013.10.
008.
[4] A. Muratović-Ribić, A. Pott, D. Thomson and Q. Wang, On the characterization of a semi-
multiplicative analogue of planar functions over finite fields, in: Topics in finite fields, Amer.
Math. Soc., Providence, RI, volume 632 of Contemp. Math., pp. 317–325, 2015, doi:10.1090/
conm/632/12635.
[5] A. Muratović-Ribić and S. Surdulli, On strong complete monomials and its multiplicative ana-
logue over finite fields, Sarajevo J. Math. 16(29) (2020), 137–144, doi:10.5644/sjm.
[6] A. Winterhof, Generalizations of complete mappings of finite fields and some applications, J.
Symbolic Comput. 64 (2014), 42–52, doi:10.1016/j.jsc.2013.12.006.