Distance preserving mappings from ternary
vectors to permutations
Jyh-Shyan Lin, Jen-Chun Chang, Rong-Jaye Chen,∗Torleiv Kløve †
November 2, 2018
Abstract
Distance-preserving mappings (DPMs) are mappings from the set
of all q-ary vectors of a fixed length to the set of permutations of
the same or longer length such that every two distinct vectors are
mapped to permutations with the same or even larger Hamming dis-
tance than that of the vectors. In this paper, we propose a construc-
tion of DPMs from ternary vectors. The constructed DPMs improve
the lower bounds on the maximal size of permutation arrays.
Key words: distance-preserving mappings, distance-increasing mappings,
permutation arrays, Hamming distance
1 Introduction
A mapping from the set of all q-ary vectors of length m to the set of all
permutations of {1, 2, . . . , n} is called a distance-preserving mapping (DPM)
if every two distinct vectors are mapped to permutations with the same or
even larger Hamming distance mutual than that of the vectors. A distance-
increasing mapping (DIM) is a special DPM such that the distances are
strictly increased except when that is obviously not possible. DPMs and
∗Jyh-Shyan Lin, Jen-Chun Chang, and Rong-Jaye Chen are with the Dept. of Com-
puter Science and Inform. Engineering, National Taipei University, Taipei, Taiwan.
†Torleiv Kløve is with the Department of Informatics, University of Bergen, Bergen,
Norway.
http://arxiv.org/abs/0704.1358v1
DIMs are useful for the construction of permutation arrays (PAs) which are
applied to various applications, such as trellis code modulations and power
line communications [7], [8], [9], [10], [11], [13], [21], [22], [23], [24]. All
DPMs and DIMs proposed so far are from binary vectors: [2], [3], [4], [5],
[6], [12], [14], [15], [16], [17], [19], [20]. In this paper we propose a general
construction method to construct DPMs or DIMs from ternary vectors. By
using this method, we construct DIMs for n = m + 2 for m ≥ 3, DPMs for
n = m+ 1 for m ≥ 9, and DPMs for n = m for m ≥ 13.
The paper is organized as follows. In the next section we introduce some
notations and state our main results. In Section 3 we introduce a general
recursive construction of DPMs and DIMs. In Sections 4 and 5 we introduce
mappings that can be used to start the recursion in the three cases we con-
sider. Finally, in an appendix, we give explicit listings of the values of some
mappings that are used as building blocks to construct the mappings given
in Sections 4 and 5.
2 Notations and main results
Let Sn denote the set of all n! permutations of Fn = {1, 2, . . . , n}. A per-
mutation π : Fn → Fn is represented by an n-tuple π = (π1, π2, . . . , πn)
where πi = π(i). Let Z
denote the set of all ternary vectors of length
n. The Hamming distance between two n-tuples a = (a1, a2, . . . , an) and
b = (b1, b2, . . . , bn) is denoted by dH(a,b) and is defined as
dH(a,b) = |{j ∈ Fn : aj 6= bj}|.
Let Fn,k be the set of injective functions from Z
to Sn+k. Note that Fn,k
is empty if (n + k)! < 3n.
For k ≥ 0, let Pn,k be the set of functions in Fn,k such that
dH(f(x), f(y)) ≥ dH(x,y)
for all x,y ∈ Zn
. These mappings are called distance preserving mappings
(DPM).
For k ≥ 1, let In,k be the set of functions in Fn,k such that
dH(f(x), f(y)) > dH(x,y) (1)
for all distinct x,y ∈ Zn
. These mappings are called distance increasing
mappings (DIM).
Our main result is the following theorem.
Theorem 1 a) In,2 is non-empty for n ≥ 3.
b) Pn,1 is non-empty for n ≥ 9.
c) Pn,0 is non-empty for n ≥ 13.
The proof of the theorem is constructive. A relatively simple recursive
method is given (in the next section) to construct a mapping of length n+1
from a mapping of length n. Explicit mappings that start the recursion in
the three cases are given in last part of the paper, including the appendix.
An (n, d) permutation array (PA) is a subset of Sn such that the Hamming
distance between any two distinct permutations in the array is at least d. An
(n, d; q) code is a subset of vectors (codewords) of length n over an alphabet
of size q and with distance at least d between distinct codewords. One
construction method of PAs is to construct an (n, d′)-PA from an (m, d; q)
code using DPMs or DIMs. More precisely, if C is an (m, d; q) code and there
exists an DPM f from Zmq to Sn, then f(C) is an (n, d) PA. If f is DIM, then
f(C) is an (n, d+1) PA. This has been a main motivation for studying DPMs.
Let P (n, d) denote the largest possible size of an (n, d)-PA. The exact value
of P (n, d) is still an open problem in most cases, but we can lower bound
this value by the maximal size of a suitable code provided a DPM (or DIM)
is known. Let Aq(n, d) denote the largest possible size of an (n, d) code over
a code alphabet of size q. In [5], Chang et al. used this approach to show
that for n ≥ 4 and 2 ≤ d ≤ n, we have P (n, d) ≥ A2(n, d − 1). In [17],
Chang further improved the bound to P (n, d) ≤ A2(n, d− δ) for n ≥ nδ and
δ + 1 ≤ d ≤ n where δ ≥ 2 and nδ is a positive integer determined by δ, e.g.
n2 = 16.
From Theorem 1 we get the following bounds.
Theorem 2 a) For n ≥ 5 and 2 ≤ d ≤ n, we have
P (n, d) ≥ A3(n− 2, d− 1).
b) For n ≥ 10 and 2 ≤ d ≤ n, we have
P (n, d) ≥ A3(n− 1, d).
c) For n ≥ 13 and 2 ≤ d ≤ n, we have
P (n, d) ≥ A3(n, d).
Bounds on A2(n, d) and A3(n, d) have been studied by many researchers,
see e.g. [18, Ch.5] and [1]. In general, the lower bounds on P (n, d) obtained
from use of ternary codes are better than those obtained from binary codes.
For example, using Chang’s bound [17], we get P (16, 5) ≥ A2(16, 3) ≥ 2720,
whereas Theorem 2 gives P (16, 5) ≥ A3(16, 5) ≥ 19683. Similarly, we get
P (16, 9) ≥ A2(16, 7) ≥ 36 and P (16, 9) ≥ A3(16, 9) ≥ 243.
3 The general recursive construction.
For any array u = (u1, u2, . . . , un), we use the notation ui = ui.
We start with a recursive definition of functions from Zn
to Sn+k. For
f ∈ Fn,k, define g = H(f) ∈ Fn+1,k as follows. Let x = (x1, x2, . . . , xn) ∈ Z
and f(x) = (ϕ1, ϕ2, . . . , ϕn+k). Suppose that the element n+ k− 4 occurs in
position r, that is ϕr = n + k − 4. Then
g(x|0)n+k+1 = n+ k + 1,
g(x|0)i = ϕi otherwise;
g(x|1)r = n+ k + 1,
g(x|1)n+k+1 = n+ k − 4,
g(x|1)i = ϕi otherwise;
if n is odd or xn < 2, then
g(x|2)n+k = n + k + 1,
g(x|2)n+k+1 = ϕn+k,
g(x|2)i = ϕi otherwise;
if n is even and xn = 2, then
g(x|2)n+k−1 = n+ k + 1,
g(x|2)n+k+1 = ϕn+k−1,
g(x|2)i = ϕi otherwise.
We note that g(x|a)i 6= f(x)i for at most one value of i ≤ n+ k.
For f ∈ Fm,k, we define a sequence of functions f ∈ Fn,k, for all n ≥ m,
recursively by
fm = f and fn+1 = H(fn) for n ≥ m.
Theorem 3 If fm ∈ Pm,k where k ≥ 0, m is odd, and
fm(x)m+k 6∈ {m+ k − 4, m+ k − 3} for all x ∈ Z
then fn ∈ Pn,k for all n ≥ m.
Theorem 4 If fm ∈ Im,k, where k > 0 and m is odd, and
fm(x)m+k 6∈ {m+ k − 4, m+ k − 3} for all x ∈ Z
then fn ∈ In,k for all n ≥ m.
Proof: We prove Theorem 4; the proof of Theorem 3 is similar (and a little
simpler). The proof is by induction. First we prove that g = fm+1 ∈ Im+1,k.
Let x,y ∈ Zm
f(x) = (ϕ1, ϕ2, . . . , ϕm+k), ϕr = m+ k − 4,
f(y) = (γ1, γ2, . . . , γm+k), γs = m+ k − 4.
We want to show that
dH(g(x|a), g(y|b)) > dH((x|a), (y|b))
if (x|a) 6= (y|b).
First, consider x = y and a 6= b. Since ϕm+k 6= m + k − 4, it follows
immediately from the definition of g that
dH(g(x|a), g(x|b)) ≥ 2 > 1 = dH((x|a), (x|b)).
For x 6= y, we want to show that
dH(g(x|a), g(y|b))− dH(f(x), f(y)) ≥ dH(a, b) (2)
for all a, b ∈ Z3 since this implies
dH(g(x|a), g(y|b)) ≥ dH(f(x), f(y)) + dH(a, b)
> dH(x,y) + dH(a, b)
= dH((x|a), (y|b)).
The condition (2) is equivalent to the following.
m+k+1∑
(∆g,i −∆f,i) ≥ dH(a, b), (3)
where
∆g,i = dH(g(x|a)i, g(y|b)i)
∆f,i = dH(f(x)i, f(y)i),
and where, for technical reasons, we define
∆f,n+k+1 = 0.
The point is at most three of the terms ∆g,i − ∆f,i are non-zero. We look
at one combination of a and b in detail as an illustration, namely a = 1 and
b = 2. Then g(x|a)i = f(x)i and g(y|b)i = f(y)i and so ∆g,i = ∆f,i for all
i ≤ m+ k + 1, except in the following three cases
i f(x)i f(y)i g(x|a)i g(y|b)i)
r m+ k − 4 γr m+ k + 1 γr
m+ k ϕm+k γm+k ϕm+k m+ k + 1
m+ k + 1 − − m+ k − 4 γm+k
i ∆f,i ∆g,i ∆g,i −∆f,i
r 0 or 1 1 0 or 1
m+ k 0 or 1 1 0 or 1
m+ k + 1 0 1 1
Note that we have used the fact that γm+k 6= m + k − 4. We see that∑
(∆g,i −∆f,i) ≥ 1 = dH(a, b).
The other combinations of a and b are similar. This proves that fm+1 =
g ∈ Im+1,k.
Now, let h = H(g) = fm+2. A similar analysis will show that h ∈ Im+2,k.
We first give a table of the last three symbols in h(x|a1a2) as these three
symbols are the most important in the proof. Let ϕs = m + k − 3. By
assumption, s < m+ k.
a1a2 h(x|a1a2)m+k h(x|a1a2)m+k+1 h(x|a1a2)m+k+2
00 ϕm+k m+ k + 1 m+ k + 2
10 ϕm+k m+ k − 4 m+ k + 2
20 m+ k + 1 ϕm+k m+ k + 2
01 ϕm+k m+ k + 1 m+ k − 3
11 ϕm+k m+ k − 4 m+ k − 3
21 m+ k + 1 ϕm+k m+ k − 3
02 ϕm+k m+ k + 2 m+ k + 1
12 ϕm+k m+ k + 2 m+ k − 4
22 m+ k + 2 ϕm+k m+ k + 1
In addition,
h(x|1a2)r = m+ k + 1 and h(x|a11)s = m+ k + 2.
Note that we have used the fact that ϕm+k 6= m + k − 3 here, since if we
had ϕm+k = m+ k − 3, then we would for example have had h(x|01)m+k =
m+ k + 2. From the table we first see that
dH(h(x|a1a2), h(x|b1b2)) > dH(a1a2, b1b2)
if a1a2 6= b1b2. For example h(x|10) and h(x|21) differ in positions r, s, m+k,
m+ k+ 1 and m+ k+ 2. As another example, h(x|02) and h(x|22) differ in
positions m+ k and m+ k + 1.
Next, consider dH(h(x|a1a2), h(y|b1b2)) for x 6= y. We see that
dH(h(x|a1a2)i, h(y|b1b2)i) ≥ dH(f(x)i, f(y)i)
for i < m+ k: from the table above, we can see that
dH(h(x|a1a2)m+kh(x|a1a2)m+k+1h(x|a1a2)m+k+2,
h(y|b1b2)m+kh(y|b1b2)m+k+1h(y|b1b2)m+k+2)
≥ dH(ϕm+k, γm+k) + dH(a1a2, b1b2).
As an example, let a1a2 = 10 and b1b2 = 02. Then
h(x|10)m+k, h(x|10)m+k+1, h(x|10)m+k+2
= ϕm+k, m+ k − 4, m+ k + 2
h(y|02)m+k, h(y|02)m+k+1, h(y|02)m+k+2
= γm+k, m+ k + 2, m+ k + 1.
The distance between the two is 2 (if ϕm+k = γm+k) or 3 (otherwise). The
other combinations of a1a2 and b1b2 are similar. From this we can conclude
that h ∈ Im+2,k in a similar way we showed that g ∈ Im+1,k above.
Further, we note that
h(x|a1a2)m+k+2 6∈ {(m+ 2) + k − 4, (m+ 2) + k − 3}.
Therefore, we can repeat the argument and, by induction, obtain fn ∈ In,k
for all n ≥ m.
A function F is given by an explicit listing in the appendix. It belongs
to I3,2 and satisfy F (x)5 6∈ {1, 2}. This, combined with Theorem 4, proves
Theorem 1 a).
4 Proof of Theorem 1, second part
To prove Theorem 1 b), using Theorem 3, we need some f ∈ P9,1 such that
f(x)10 6∈ {6, 7} for all x ∈ Z
. (4)
An extensive computer search has been unsuccessful in coming up with such a
mapping. However, an indirect approach has been successful. The approach
is to construct f from two simpler mappings found by computer search.
For a vector ρ = (ρ1, ρ2, . . . , ρn) and a set X ⊂ {1, 2, . . . , n}, let ρ\X
denote the vector obtained from ρ by removing the elements with subscript
in X . For example,
(ρ1, ρ2, ρ3, ρ4, ρ5, ρ6)\{1,5} = (ρ2, ρ3, ρ4, ρ6).
By computer search we have found mappings G ∈ F5,2 and H ∈ F4,2 that
satisfy the following conditions
a) for every x ∈ Z5
, 6 ∈ {G(x)1, G(x)2, G(x)3},
b) for every x ∈ Z5
, 7 ∈ {G(x)4, G(x)5, G(x)6},
c) for every distinct x,y ∈ Z5
dH(G(x)\{7}, G(y)\{7}) ≥ dH(x,y),
d) for every u ∈ Z4
, 1 ∈ {H(u)1, H(u)2, H(u)3},
e) for every distinct u,v ∈ Z4
dH(H(u)\{5,6}, H(v)\{5,6}) ≥ dH(u,v).
The mappings G and H are listed explicitly in the appendix. We will now
show how these mappings can be combined to produce a mapping f ∈ P9,1
satisfying (4).
Let x ∈ Z9
. Then x = (xL,xR), where xL ∈ Z
and xR ∈ Z
. Let
(ϕ1, ϕ2, ϕ3, ϕ4, ϕ5, ϕ6, ϕ7) = G(xL),
(γ1, γ2, γ3, γ4, γ5, γ6) = H(xR) + (4, 4, 4, 4, 4, 4).
We note that Condition d) implies that γ5 ≥ 6 and γ6 ≥ 6. Similarly,
Conditions a) and b) imply that ϕ7 ≤ 5.
Define ρ = (ρ1, ρ2, . . . , ρ10) as follows.
ρi = γ5 if 1 ≤ i ≤ 3 and ϕi = 6,
ρi = γ6 if 4 ≤ i ≤ 6 and ϕi = 7,
ρi = ϕi if 1 ≤ i ≤ 6 and ϕi ≤ 5,
ρi = ϕ7 if 7 ≤ i ≤ 9 and γi−6 = 5,
ρi = γi−6 if 7 ≤ i ≤ 10 and γi−6 ≥ 6.
In ρ, swap 1 and 6 and also swap 2 and 7, and let the resulting array be
denoted by π. More formally,
πi = 1 if ρi = 6,
πi = 2 if ρi = 7,
πi = 6 if ρi = 1,
πi = 7 if ρi = 2,
πi = ρi otherwise.
Then define
f(x) = π.
We will show that f has the stated properties. We first show that π ∈ S10.
We have ϕ ∈ S7 and γ is a permutation of (5, 6, 7, 8, 9, 10). In particular, 5,6,
and 7 appear both in ϕ and γ. The effect of the first line in the definition of ρ
is to move another elements (γ5) into the position where ϕ has a 6. Similarly,
the second line overwrites the 7 in ρ, and the fourth line overwrites the 5 in
γ. The definition of ρ is then the concatenation of the six first (overwritten)
elements of ϕ and the five first (overwritten) elements of γ. Therefore, ρ
contains no duplicate elements, that is, ρ ∈ S10.
The element 1 in ρ must be either in one of the first six positions, coming
from ϕ, or in one of the positions 7− 9 (if ϕ7 = 1). Similarly, the element 2
must be in one of the first nine positions of ρ. Therefore, both 6 and 7 must
be among the first nine elements of π, that is π10 6∈ {6, 7}.
Finally, we must show that f is distance preserving. Let x 6= x′, and let
the arrays corresponding to x′ be denoted by ϕ′, γ′, ρ′ and π′. By assumption,
dH(x,x
′) = dH(xL,x
L) + dH(xR,x
≤ dH(ϕ\{7}, ϕ
\{7}) + dH(γ\{5,6}, γ
\{5,6}). (5)
For 1 ≤ i ≤ 6 we have
dH(ϕi, ϕ
i) ≤ dH(ρi, ρ
i). (6)
If ϕi = ϕ
i this is obvious. Otherwise, we may assume without loss of gener-
ality that ϕ′i < ϕi and we must show that ρi 6= ρ
i. If ϕi ≤ 5, then
ρ′i = ϕ
i < ϕi = ρi.
If ϕi = 6, then
ρ′i = ϕ
i ≤ 5 and ρi = γ5 ≥ 6.
If ϕi = 7, then 4 ≤ i ≤ 6 and so ϕ
i 6= 6. Hence
ρ′i = ϕ
i ≤ 5 and ρi = γ6 ≥ 6.
This completes that proof of (6). A similar arguments show that for 7 ≤ i ≤
10 we have
dH(γi−6, γ
i−6) ≤ dH(ρi, ρ
i), (7)
and that for 1 ≤ i ≤ 10 we have
dH(ρi, ρ
i) ≤ dH(πi, π
i). (8)
Combining (5)–(8), we get
dH(x,x
′) ≤ dH(ϕ\{7}, ϕ
\{7}) + dH(γ\{5,6}, γ
\{5,6})
≤ dH(ρ, ρ
′) ≤ dH(π, π
Hence, f is distance preserving.
5 Proof of Theorem 1, last part
The construction of a mapping f ∈ P13,0 which proves Theorem 1 c) is similar
to the construction in the previous section. However, the construction is more
involved and contains several steps. We will describe the constructions and
properties of the intermediate mappings. The details of proofs are similar to
the proof in the previous section and we omit these details.
We start with three mappings R, S ∈ F3,2 and T ∈ F4,2. These were
found by computer search and are listed explicitly in the appendix. They
have the following properties:
• for every x ∈ Z3
, 1 ∈ {R(x)1, R(x)2, R(x)3},
• for every x ∈ Z3
, R(x)5 6= 5,
• for every distinct x,y ∈ Z3
dH(R(x)\{4,5}, R(y)\{4,5}) ≥ dH(x,y),
• for every x ∈ Z3
, 2 ∈ {S(x)1, S(x)2, S(x)3},
• for every x ∈ Z3
, S(x)5 6= 1,
• for every distinct x,y ∈ Z3
dH(S(x)\{4,5}, S(y)\{4,5}) ≥ dH(x,y),
• for every x ∈ Z4
, 2 ∈ {T (x)1, T (x)2, T (x)3},
• for every x ∈ Z4
, T (x)6 6= 1,
• for every distinct x,y ∈ Z4
dH(T (x)\{5,6}, T (y)\{5,6}) ≥ dH(x,y).
These mappings are used as building blocks similarly to what was done in
the previous section.
Construction of U ∈ F6,2
Let x ∈ Z6
and let
(ϕ1, ϕ2, ϕ3, ϕ4, ϕ5) = R(x1, x2, x3),
(γ1, γ2, γ3, γ4, γ5) = S(x4, x5, x6) + (3, 3, 3, 3, 3).
Define ρ = (ρ1, ρ2, . . . , ρ8) as follows.
ρi = γ5 if 1 ≤ i ≤ 4 and ϕi = 5,
ρi = ϕi if 1 ≤ i ≤ 4 and ϕi 6= 5,
ρi = ϕ5 if 5 ≤ i ≤ 8 and γi−4 = 4,
ρi = γi−4 if 5 ≤ i ≤ 8 and γi−4 6= 4.
In ρ, swap 1 and 7 and also swap 5 and 8, and let the resulting array be
U(x). It has the following properties:
• for every x ∈ Z6
, 7 ∈ {U(x)1, U(x)2, U(x)3},
• for every x ∈ Z6
, 8 ∈ {U(x)5, U(x)6, U(x)7},
• for every distinct x,y ∈ Z6
dH(U(x)\{4,8}, U(y)\{4,8}) ≥ dH(x,y).
Construction of V ∈ F7,2
Let x ∈ Z7
and let
(ϕ1, ϕ2, ϕ3, ϕ4, ϕ5) = R(x1, x2, x3),
(γ1, γ2, γ3, γ4, γ5, γ6) = T (x4, x5, x6, x7) + (3, 3, . . . , 3).
Define ρ = (ρ1, ρ2, . . . , ρ8, ρ9) as follows.
ρi = γ6 if 1 ≤ i ≤ 4 and ϕi = 5,
ρi = ϕi if 1 ≤ i ≤ 4 and ϕi 6= 5,
ρi = ϕ5 if 5 ≤ i ≤ 9 and γi−4 = 4,
ρi = γi−4 if 5 ≤ i ≤ 9 and γi−4 6= 4.
In ρ, swap 2 and 5, and let the resulting array be V (x). It has the
following properties:
• for every x ∈ Z7
, 1 ∈ {V (x)1, V (x)2, V (x)3},
• for every x ∈ Z7
, 2 ∈ {V (x)5, V (x)6, V (x)7},
• for every distinct x,y ∈ Z7
dH(V (x)\{4,9}, V (y)\{4,9}) ≥ dH(x,y).
Construction of f ∈ P13,0
Let x ∈ Z13
and let
(ϕ1, ϕ2, . . . , ϕ8) = U(x1, x2, . . . , x6),
(γ1, γ2, . . . , γ9) = V (x7, x8, . . . , x13) + (4, 4, . . . , 4).
Define ρ = (ρ1, ρ2, . . . , ρ13) as follows.
ρi = γ4 if 1 ≤ i ≤ 3 and ϕi = 7,
ρi = ϕi if 1 ≤ i ≤ 3 and ϕi 6= 7,
ρi = γ9 if 4 ≤ i ≤ 6 and ϕi+1 = 8,
ρi = ϕi+1 if 4 ≤ i ≤ 6 and ϕi+1 6= 8,
ρi = ϕ4 if 7 ≤ i ≤ 9 and γi−6 = 5,
ρi = γi−6 if 7 ≤ i ≤ 9 and γi−6 6= 5,
ρi = ϕ8 if 10 ≤ i ≤ 13 and γi−5 = 6,
ρi = γi−5 if 10 ≤ i ≤ 13 and γi−5 6= 6.
In ρ, swap 1 and 9 and also swap 2 and 10, and let the resulting array be
f(x). Then
f ∈ P13,0 and f(x)13 6∈ {9, 10}.
References
[1] A.E. Brouwer, Heikki O. Hämäläinen, Patric R.J. Österg̊ard, N.J.A.
Sloane, “Bounds on mixed binary/ternary codes”, IEEE Trans. on In-
form. Theory, vol. 44, no. 1, pp. 140–161, Jan. 1998.
[2] J.-C. Chang, “Distance-increasing mappings from binary vectors to per-
mutations”, IEEE Trans. on Inform. Theory, vol. 51, no. 1, pp. 359–363,
Jan. 2005.
[3] J.-C. Chang, “New algorithms of distance-increasing mappings from bi-
nary vectors to permutations by swaps”, Designs, Codes and Cryptog-
raphy, vol. 39, pp. 335–345, Jan. 2006.
[4] J.-C. Chang, “Distance-increasing mappings from binary vectors to per-
mutations that increase Hamming distances by at least two”, IEEE
Trans. on Inform. Theory, vol. 52, no. 4, pp. 1683–1689, April 2006.
[5] J.-C. Chang, R.-J. Chen, T. Kløve, and S.-C. Tsai, “Distance-preserving
mappings from binary vectors to permutations”, IEEE Trans. on In-
form. Theory, vol. 49, pp. 1054–1059, Apr. 2003.
[6] C. J. Colbourn, T. Kløve, and A. C. H. Ling, “Permutation arrays for
powerline communication and mutually orthogonal latin squares”, IEEE
Trans. on Inform. Theory, vol. 50, no. 6, pp. 1289–1291, June 2004.
[7] C. Ding, F.-W. Fu, T. Kløve, and V. K. Wei, “Constructions of permu-
tation arrays”, IEEE Trans. on Inform. Theory, vol. 48, pp. 977–980,
Apr. 2002.
[8] H. C. Ferreira and A. J. H. Vinck, “Inference cancellation with per-
mutation trellis arrays”, Proc. IEEE Vehicular Technology Conf., pp.
2401–2407, 2000.
[9] H. C. Ferreira, A. J. H. Vinck, T. G. Swart, and A. L. Nel, “Permutation
trellis codes”, Proc. IEEE Trans. on Communications, vol. 53, no. 11,
pp. 1782–1789, Nov. 2005.
[10] H. C. Ferreira, D Wright, and A. L. Nel, “Hamming distance preserv-
ing mappings and trellis codes with constrained binary symbols”, IEEE
Trans. on Inform. Theory, vol. 35, no. 5, pp. 1098–1103, Sept. 1989.
[11] F.-W. Fu and T. Kløve, “Two constructions of permutation arrays”,
IEEE Trans. on Inform. Theory, vol. 50, pp. 881–883, May. 2004.
[12] Y.-Y. Huang, S.-C. Tsai, H.-L. Wu, “On the construction of permutation
arrays via mappings from binary vectors to permutations”, Designs,
Codes and Cryptography, vol. 40, pp. 139–155, 2006.
[13] T. Kløve, “Classification of permutation codes of length 6 and minimum
distance 5”, Proc. Int. Symp. Information Theory and Its Applications,
2000, pp. 465–468.
[14] K. Lee, “New distance-preserving maps of odd length”, IEEE Trans. on
Inform. Theory, vol. 50, no. 10, pp. 2539–2543, Oct. 2004.
[15] K. Lee, “Cyclic constructions of distance-preserving maps”, IEEE
Trans. on Inform. Theory, vol. 51, no. 12, pp. 4292–4396, Dec. 2005.
[16] K. Lee, “Distance-increasing maps of all length by simple mapping al-
gorithms”, arXiv:cs.IT/0509073, 23 Sept. 2005.
[17] J.-S. Lin, J.-C. Chang, and R.-J. Chen, “New simple constructions of
distance-increasing mappings from binary vectors to permutations”, In-
formation Processing Letters, vol. 100, no. 2, pp. 83–89, Oct. 2006.
[18] V. S. Pless and W. C. Huffman, Eds., Handbook of Coding Theory.
Amsterdam, The Netherlands: Elsevier, 1998.
[19] T. G Swart, I. de Beer, H. C. Ferreira, “On the distance optimality of
permutation mappings”, Proc. IEEE Int. Symp. Information Theory,
Adelaide, Australia, September 2005, pp. 1068–1072.
[20] T. G Swart and H. C. Ferreira, “A multilevel construction for map-
pings from binary sequences to permutation sequences”, Proc. IEEE Int.
Symp. Information Theory, Seattle, USA, July 2006, pp. 1895–1899.
[21] A. J. H. Vinck, “Coding and modulation for powerline communications”,
A.E.Ü . Int. J. Electron. Commun., vol. 54, no. 1, pp. 45–49, Oct. 2000.
[22] A. J. H. Vinck and J. Häring, “Coding and modulation for power-line
communications”, Proc. Int. Symp. Power Line Communication, Lim-
erick, Ireland, Apr. 57, 2000.
[23] A. J. H. Vinck, J. Häring, and T. Wadayama, “Coded M-FSK for power-
line communications”, Proc. IEEE Int. Symp. Information Theory, Sor-
rento, Italy, June 2000, p. 137.
[24] T. Wadayama and A. J. H. Vinck, “A multilevel construction of permu-
tation codes”, IEICE Trans. Fundamentals Electron., Commun. Comp.
Sci., vol. 84, pp. 2518–2522, 2001.
Appendix
Listing of the elements x ∈ Z3
and the corresponding values of F (x) ∈ S5.
(0,0,0)(1,2,3,4,5), (0,0,1)(1,2,5,4,3), (0,0,2)(1,2,3,5,4),
(0,1,0)(4,2,3,1,5), (0,1,1)(4,2,5,1,3), (0,1,2)(5,2,3,1,4),
(0,2,0)(1,4,3,2,5), (0,2,1)(1,4,5,2,3), (0,2,2)(1,5,3,2,4),
(1,0,0)(2,3,1,4,5), (1,0,1)(2,5,1,4,3), (1,0,2)(2,3,1,5,4),
(1,1,0)(2,3,4,1,5), (1,1,1)(2,5,4,1,3), (1,1,2)(2,3,5,1,4),
(1,2,0)(4,3,1,2,5), (1,2,1)(4,5,1,2,3), (1,2,2)(5,3,1,2,4),
(2,0,0)(3,1,2,4,5), (2,0,1)(5,1,2,4,3), (2,0,2)(3,1,2,5,4),
(2,1,0)(3,4,2,1,5), (2,1,1)(5,4,2,1,3), (2,1,2)(3,5,2,1,4),
(2,2,0)(3,1,4,2,5), (2,2,1)(5,1,4,2,3), (2,2,2)(3,1,5,2,4)
Listing of the elements x ∈ Z5
and the corresponding values of G(x) ∈ S7.
(0,0,0,0,0)(6,1,2,7,3,4,5), (0,0,0,0,1)(6,3,2,7,1,5,4),
(0,0,0,0,2)(6,3,2,7,4,5,1), (0,0,0,1,0)(6,2,1,7,5,3,4),
(0,0,0,1,1)(6,1,2,7,5,3,4), (0,0,0,1,2)(6,3,2,7,5,4,1),
(0,0,0,2,0)(6,1,2,7,3,5,4), (0,0,0,2,1)(6,3,1,7,2,5,4),
(0,0,0,2,2)(6,3,1,7,4,5,2), (0,0,1,0,0)(6,2,5,7,1,4,3),
(0,0,1,0,1)(6,2,5,7,3,4,1), (0,0,1,0,2)(6,3,5,7,4,1,2),
(0,0,1,1,0)(6,2,5,7,1,3,4), (0,0,1,1,1)(6,5,1,7,2,3,4),
(0,0,1,1,2)(6,2,5,7,4,3,1), (0,0,1,2,0)(6,4,5,7,1,3,2),
(0,0,1,2,1)(6,2,4,7,1,5,3), (0,0,1,2,2)(6,1,5,7,4,2,3),
(0,0,2,0,0)(6,4,2,7,3,1,5), (0,0,2,0,1)(6,3,4,7,2,1,5),
(0,0,2,0,2)(6,3,2,7,4,1,5), (0,0,2,1,0)(6,4,1,7,5,3,2),
(0,0,2,1,1)(6,5,4,7,2,3,1), (0,0,2,1,2)(6,5,2,7,4,3,1),
(0,0,2,2,0)(6,4,1,7,5,2,3), (0,0,2,2,1)(6,5,4,7,3,2,1),
(0,0,2,2,2)(6,5,3,7,4,2,1), (0,1,0,0,0)(6,1,3,2,7,5,4),
(0,1,0,0,1)(6,3,2,4,7,5,1), (0,1,0,0,2)(6,3,2,5,7,4,1),
(0,1,0,1,0)(6,4,2,5,7,3,1), (0,1,0,1,1)(6,2,1,5,7,3,4),
(0,1,0,1,2)(6,5,2,1,7,4,3), (0,1,0,2,0)(6,2,1,3,7,5,4),
(0,1,0,2,1)(6,3,1,4,7,5,2), (0,1,0,2,2)(6,5,2,3,7,4,1),
(0,1,1,0,0)(6,3,5,2,7,1,4), (0,1,1,0,1)(6,2,3,5,7,4,1),
(0,1,1,0,2)(6,3,5,2,7,4,1), (0,1,1,1,0)(6,2,5,4,7,3,1),
(0,1,1,1,1)(6,2,5,1,7,3,4), (0,1,1,1,2)(6,3,5,1,7,4,2),
(0,1,1,2,0)(6,2,5,3,7,1,4), (0,1,1,2,1)(6,5,1,3,7,2,4),
(0,1,1,2,2)(6,4,5,3,7,2,1), (0,1,2,0,0)(6,5,4,2,7,1,3),
(0,1,2,0,1)(6,4,3,2,7,1,5), (0,1,2,0,2)(6,5,3,2,7,4,1),
(0,1,2,1,0)(6,4,2,1,7,3,5), (0,1,2,1,1)(6,5,4,1,7,3,2),
(0,1,2,1,2)(6,3,4,5,7,2,1), (0,1,2,2,0)(6,5,4,3,7,1,2),
(0,1,2,2,1)(6,5,4,3,7,2,1), (0,1,2,2,2)(6,4,3,1,7,2,5),
(0,2,0,0,0)(6,4,1,5,3,7,2), (0,2,0,0,1)(6,3,2,4,1,7,5),
(0,2,0,0,2)(6,3,2,5,4,7,1), (0,2,0,1,0)(6,1,4,2,5,7,3),
(0,2,0,1,1)(6,2,4,1,5,7,3), (0,2,0,1,2)(6,3,2,1,5,7,4),
(0,2,0,2,0)(6,4,2,3,5,7,1), (0,2,0,2,1)(6,1,2,3,5,7,4),
(0,2,0,2,2)(6,3,1,5,4,7,2), (0,2,1,0,0)(6,3,5,2,1,7,4),
(0,2,1,0,1)(6,5,1,4,2,7,3), (0,2,1,0,2)(6,3,5,2,4,7,1),
(0,2,1,1,0)(6,1,5,4,2,7,3), (0,2,1,1,1)(6,2,5,1,3,7,4),
(0,2,1,1,2)(6,4,5,1,2,7,3), (0,2,1,2,0)(6,2,5,3,1,7,4),
(0,2,1,2,1)(6,5,1,3,2,7,4), (0,2,1,2,2)(6,3,5,1,4,7,2),
(0,2,2,0,0)(6,5,3,4,1,7,2), (0,2,2,0,1)(6,5,1,4,3,7,2),
(0,2,2,0,2)(6,5,3,2,4,7,1), (0,2,2,1,0)(6,4,2,1,3,7,5),
(0,2,2,1,1)(6,5,4,1,3,7,2), (0,2,2,1,2)(6,5,3,1,4,7,2),
(0,2,2,2,0)(6,5,4,3,1,7,2), (0,2,2,2,1)(6,5,4,3,2,7,1),
(0,2,2,2,2)(6,5,2,3,4,7,1), (1,0,0,0,0)(2,6,1,7,3,5,4),
(1,0,0,0,1)(1,6,3,7,2,5,4), (1,0,0,0,2)(3,6,2,7,1,4,5),
(1,0,0,1,0)(4,6,1,7,5,3,2), (1,0,0,1,1)(4,6,2,7,5,3,1),
(1,0,0,1,2)(1,6,2,7,5,3,4), (1,0,0,2,0)(4,6,1,7,5,2,3),
(1,0,0,2,1)(4,6,1,7,3,2,5), (1,0,0,2,2)(3,6,4,7,1,2,5),
(1,0,1,0,0)(2,6,5,7,4,1,3), (1,0,1,0,1)(2,6,3,7,1,4,5),
(1,0,1,0,2)(1,6,3,7,5,4,2), (1,0,1,1,0)(2,6,5,7,1,3,4),
(1,0,1,1,1)(4,6,5,7,2,3,1), (1,0,1,1,2)(1,6,2,7,4,3,5),
(1,0,1,2,0)(4,6,5,7,1,2,3), (1,0,1,2,1)(4,6,5,7,3,2,1),
(1,0,1,2,2)(1,6,5,7,4,3,2), (1,0,2,0,0)(2,6,4,7,3,1,5),
(1,0,2,0,1)(5,6,3,7,2,1,4), (1,0,2,0,2)(5,6,3,7,4,1,2),
(1,0,2,1,0)(2,6,4,7,5,1,3), (1,0,2,1,1)(2,6,4,7,5,3,1),
(1,0,2,1,2)(5,6,3,7,4,2,1), (1,0,2,2,0)(3,6,1,7,5,2,4),
(1,0,2,2,1)(1,6,5,7,3,2,4), (1,0,2,2,2)(5,6,1,7,4,2,3),
(1,1,0,0,0)(3,6,5,4,7,1,2), (1,1,0,0,1)(3,6,2,5,7,4,1),
(1,1,0,0,2)(3,6,5,2,7,4,1), (1,1,0,1,0)(4,6,1,2,7,3,5),
(1,1,0,1,1)(3,6,2,4,7,5,1), (1,1,0,1,2)(4,6,3,1,7,5,2),
(1,1,0,2,0)(4,6,1,2,7,5,3), (1,1,0,2,1)(4,6,1,3,7,5,2),
(1,1,0,2,2)(4,6,2,3,7,5,1), (1,1,1,0,0)(4,6,5,2,7,1,3),
(1,1,1,0,1)(5,6,2,4,7,1,3), (1,1,1,0,2)(4,6,3,5,7,1,2),
(1,1,1,1,0)(5,6,2,1,7,3,4), (1,1,1,1,1)(4,6,5,1,7,3,2),
(1,1,1,1,2)(3,6,4,1,7,5,2), (1,1,1,2,0)(4,6,5,3,7,1,2),
(1,1,1,2,1)(4,6,5,3,7,2,1), (1,1,1,2,2)(5,6,1,3,7,4,2),
(1,1,2,0,0)(5,6,3,2,7,1,4), (1,1,2,0,1)(5,6,3,4,7,1,2),
(1,1,2,0,2)(5,6,3,2,7,4,1), (1,1,2,1,0)(5,6,4,1,7,3,2),
(1,1,2,1,1)(5,6,3,4,7,2,1), (1,1,2,1,2)(5,6,4,1,7,2,3),
(1,1,2,2,0)(5,6,4,2,7,3,1), (1,1,2,2,1)(5,6,4,3,7,1,2),
(1,1,2,2,2)(5,6,4,3,7,2,1), (1,2,0,0,0)(3,6,5,4,1,7,2),
(1,2,0,0,1)(4,6,1,5,3,7,2), (1,2,0,0,2)(3,6,5,2,4,7,1),
(1,2,0,1,0)(4,6,1,2,5,7,3), (1,2,0,1,1)(4,6,2,1,5,7,3),
(1,2,0,1,2)(4,6,3,1,5,7,2), (1,2,0,2,0)(4,6,1,3,5,7,2),
(1,2,0,2,1)(4,6,2,3,5,7,1), (1,2,0,2,2)(5,6,1,3,4,7,2),
(1,2,1,0,0)(4,6,5,2,1,7,3), (1,2,1,0,1)(5,6,2,4,1,7,3),
(1,2,1,0,2)(4,6,3,5,1,7,2), (1,2,1,1,0)(5,6,2,1,3,7,4),
(1,2,1,1,1)(4,6,5,1,3,7,2), (1,2,1,1,2)(5,6,2,1,4,7,3),
(1,2,1,2,0)(4,6,5,3,1,7,2), (1,2,1,2,1)(4,6,5,3,2,7,1),
(1,2,1,2,2)(5,6,2,3,4,7,1), (1,2,2,0,0)(5,6,3,2,1,7,4),
(1,2,2,0,1)(5,6,3,4,1,7,2), (1,2,2,0,2)(5,6,3,2,4,7,1),
(1,2,2,1,0)(5,6,4,1,3,7,2), (1,2,2,1,1)(5,6,3,4,2,7,1),
(1,2,2,1,2)(5,6,4,1,2,7,3), (1,2,2,2,0)(5,6,4,2,3,7,1),
(1,2,2,2,1)(5,6,4,3,1,7,2), (1,2,2,2,2)(5,6,4,3,2,7,1),
(2,0,0,0,0)(2,1,6,7,3,5,4), (2,0,0,0,1)(1,5,6,7,3,4,2),
(2,0,0,0,2)(2,3,6,7,4,5,1), (2,0,0,1,0)(2,4,6,7,3,5,1),
(2,0,0,1,1)(4,2,6,7,5,3,1), (2,0,0,1,2)(3,1,6,7,2,4,5),
(2,0,0,2,0)(4,1,6,7,5,2,3), (2,0,0,2,1)(4,1,6,7,3,2,5),
(2,0,0,2,2)(3,1,6,7,5,4,2), (2,0,1,0,0)(3,2,6,7,4,1,5),
(2,0,1,0,1)(4,2,6,7,3,1,5), (2,0,1,0,2)(3,2,6,7,1,4,5),
(2,0,1,1,0)(2,5,6,7,1,3,4), (2,0,1,1,1)(4,5,6,7,2,3,1),
(2,0,1,1,2)(2,3,6,7,5,4,1), (2,0,1,2,0)(4,5,6,7,1,2,3),
(2,0,1,2,1)(4,5,6,7,3,2,1), (2,0,1,2,2)(3,1,6,7,4,2,5),
(2,0,2,0,0)(2,5,6,7,4,1,3), (2,0,2,0,1)(5,3,6,7,2,1,4),
(2,0,2,0,2)(5,3,6,7,4,1,2), (2,0,2,1,0)(3,4,6,7,2,1,5),
(2,0,2,1,1)(3,4,6,7,2,5,1), (2,0,2,1,2)(5,3,6,7,4,2,1),
(2,0,2,2,0)(3,4,6,7,5,1,2), (2,0,2,2,1)(3,4,6,7,5,2,1),
(2,0,2,2,2)(5,1,6,7,4,2,3), (2,1,0,0,0)(3,5,6,4,7,1,2),
(2,1,0,0,1)(4,1,6,5,7,3,2), (2,1,0,0,2)(3,5,6,2,7,4,1),
(2,1,0,1,0)(4,1,6,2,7,5,3), (2,1,0,1,1)(4,2,6,1,7,5,3),
(2,1,0,1,2)(4,3,6,1,7,5,2), (2,1,0,2,0)(4,1,6,3,7,5,2),
(2,1,0,2,1)(4,2,6,3,7,5,1), (2,1,0,2,2)(5,1,6,3,7,4,2),
(2,1,1,0,0)(4,5,6,2,7,1,3), (2,1,1,0,1)(5,2,6,4,7,1,3),
(2,1,1,0,2)(4,3,6,5,7,1,2), (2,1,1,1,0)(5,2,6,1,7,3,4),
(2,1,1,1,1)(4,5,6,1,7,3,2), (2,1,1,1,2)(5,2,6,1,7,4,3),
(2,1,1,2,0)(4,5,6,3,7,1,2), (2,1,1,2,1)(4,5,6,3,7,2,1),
(2,1,1,2,2)(5,2,6,3,7,4,1), (2,1,2,0,0)(5,3,6,2,7,1,4),
(2,1,2,0,1)(5,3,6,4,7,1,2), (2,1,2,0,2)(5,3,6,2,7,4,1),
(2,1,2,1,0)(5,4,6,1,7,3,2), (2,1,2,1,1)(5,3,6,4,7,2,1),
(2,1,2,1,2)(5,4,6,1,7,2,3), (2,1,2,2,0)(5,4,6,2,7,3,1),
(2,1,2,2,1)(5,4,6,3,7,1,2), (2,1,2,2,2)(5,4,6,3,7,2,1),
(2,2,0,0,0)(3,5,6,4,1,7,2), (2,2,0,0,1)(4,1,6,5,3,7,2),
(2,2,0,0,2)(3,5,6,2,4,7,1), (2,2,0,1,0)(4,1,6,2,5,7,3),
(2,2,0,1,1)(4,2,6,1,5,7,3), (2,2,0,1,2)(4,3,6,1,5,7,2),
(2,2,0,2,0)(4,1,6,3,5,7,2), (2,2,0,2,1)(4,2,6,3,5,7,1),
(2,2,0,2,2)(5,1,6,3,4,7,2), (2,2,1,0,0)(4,5,6,2,1,7,3),
(2,2,1,0,1)(5,2,6,4,1,7,3), (2,2,1,0,2)(4,3,6,5,1,7,2),
(2,2,1,1,0)(5,2,6,1,3,7,4), (2,2,1,1,1)(4,5,6,1,3,7,2),
(2,2,1,1,2)(5,2,6,1,4,7,3), (2,2,1,2,0)(4,5,6,3,1,7,2),
(2,2,1,2,1)(4,5,6,3,2,7,1), (2,2,1,2,2)(5,2,6,3,4,7,1),
(2,2,2,0,0)(5,3,6,2,1,7,4), (2,2,2,0,1)(5,3,6,4,1,7,2),
(2,2,2,0,2)(5,3,6,2,4,7,1), (2,2,2,1,0)(5,4,6,1,3,7,2),
(2,2,2,1,1)(5,3,6,4,2,7,1), (2,2,2,1,2)(5,4,6,1,2,7,3),
(2,2,2,2,0)(5,4,6,2,3,7,1), (2,2,2,2,1)(5,4,6,3,1,7,2),
(2,2,2,2,2)(5,4,6,3,2,7,1)
Listing of the elements x ∈ Z4
and the corresponding values ofH(x) ∈ S6.
(0,0,0,0)(1,2,3,4,5,6), (0,0,0,1)(1,2,3,6,4,5),
(0,0,0,2)(1,2,3,5,4,6), (0,0,1,0)(1,4,2,6,5,3),
(0,0,1,1)(1,4,2,3,6,5), (0,0,1,2)(1,4,2,5,6,3),
(0,0,2,0)(1,3,4,6,5,2), (0,0,2,1)(1,3,4,5,6,2),
(0,0,2,2)(1,3,4,2,6,5), (0,1,0,0)(1,5,3,4,6,2),
(0,1,0,1)(1,2,5,3,4,6), (0,1,0,2)(1,5,3,2,4,6),
(0,1,1,0)(1,5,2,4,6,3), (0,1,1,1)(1,5,2,3,4,6),
(0,1,1,2)(1,4,5,2,6,3), (0,1,2,0)(1,3,5,4,6,2),
(0,1,2,1)(1,5,4,3,6,2), (0,1,2,2)(1,5,4,2,6,3),
(0,2,0,0)(1,6,3,4,5,2), (0,2,0,1)(1,2,6,3,4,5),
(0,2,0,2)(1,6,3,2,4,5), (0,2,1,0)(1,6,2,4,5,3),
(0,2,1,1)(1,6,2,3,4,5), (0,2,1,2)(1,4,6,2,5,3),
(0,2,2,0)(1,3,6,4,5,2), (0,2,2,1)(1,6,4,3,5,2),
(0,2,2,2)(1,6,4,2,5,3), (1,0,0,0)(4,1,3,5,6,2),
(1,0,0,1)(4,1,3,6,5,2), (1,0,0,2)(4,1,3,2,6,5),
(1,0,1,0)(3,1,2,4,6,5), (1,0,1,1)(3,1,2,6,4,5),
(1,0,1,2)(3,1,2,5,4,6), (1,0,2,0)(2,1,4,5,6,3),
(1,0,2,1)(2,1,4,3,6,5), (1,0,2,2)(2,1,4,6,5,3),
(1,1,0,0)(6,1,3,4,5,2), (1,1,0,1)(4,1,5,3,6,2),
(1,1,0,2)(6,1,3,2,4,5), (1,1,1,0)(3,1,5,4,6,2),
(1,1,1,1)(6,1,5,3,4,2), (1,1,1,2)(6,1,5,2,4,3),
(1,1,2,0)(2,1,5,4,6,3), (1,1,2,1)(6,1,4,3,5,2),
(1,1,2,2)(6,1,4,2,5,3), (1,2,0,0)(5,1,3,4,6,2),
(1,2,0,1)(4,1,6,3,5,2), (1,2,0,2)(5,1,3,2,4,6),
(1,2,1,0)(5,1,2,4,6,3), (1,2,1,1)(5,1,6,3,4,2),
(1,2,1,2)(5,1,6,2,4,3), (1,2,2,0)(2,1,6,4,5,3),
(1,2,2,1)(5,1,4,3,6,2), (1,2,2,2)(5,1,4,2,6,3),
(2,0,0,0)(4,2,1,5,6,3), (2,0,0,1)(4,2,1,3,6,5),
(2,0,0,2)(4,2,1,6,5,3), (2,0,1,0)(3,4,1,5,6,2),
(2,0,1,1)(3,4,1,6,5,2), (2,0,1,2)(3,4,1,2,6,5),
(2,0,2,0)(2,3,1,4,6,5), (2,0,2,1)(2,3,1,6,4,5),
(2,0,2,2)(2,3,1,5,4,6), (2,1,0,0)(6,2,1,4,5,3),
(2,1,0,1)(6,2,1,3,4,5), (2,1,0,2)(4,5,1,2,6,3),
(2,1,1,0)(3,5,1,4,6,2), (2,1,1,1)(6,4,1,3,5,2),
(2,1,1,2)(6,5,1,2,4,3), (2,1,2,0)(6,3,1,4,5,2),
(2,1,2,1)(2,5,1,3,4,6), (2,1,2,2)(6,3,1,2,4,5),
(2,2,0,0)(5,2,1,4,6,3), (2,2,0,1)(5,2,1,3,4,6),
(2,2,0,2)(4,6,1,2,5,3), (2,2,1,0)(3,6,1,4,5,2),
(2,2,1,1)(5,4,1,3,6,2), (2,2,1,2)(5,6,1,2,4,3),
(2,2,2,0)(5,3,1,4,6,2), (2,2,2,1)(2,6,1,3,4,5),
(2,2,2,2)(5,3,1,2,4,6)
Listing of the elements x ∈ Z3
and the corresponding values of R(x) ∈ S5.
(0,0,0)(1,2,3,5,4), (0,0,1)(1,4,3,5,2), (0,0,2)(1,5,3,4,2),
(0,1,0)(1,2,4,5,3), (0,1,1)(1,4,2,5,3), (0,1,2)(1,5,4,3,2),
(0,2,0)(1,2,5,4,3), (0,2,1)(1,4,5,3,2), (0,2,2)(1,3,5,4,2),
(1,0,0)(4,1,3,5,2), (1,0,1)(5,1,3,4,2), (1,0,2)(2,1,3,5,4),
(1,1,0)(3,1,4,5,2), (1,1,1)(5,1,4,3,2), (1,1,2)(2,1,4,5,3),
(1,2,0)(4,1,5,3,2), (1,2,1)(5,1,2,4,3), (1,2,2)(2,1,5,4,3),
(2,0,0)(4,2,1,5,3), (2,0,1)(5,4,1,3,2), (2,0,2)(2,5,1,4,3),
(2,1,0)(3,2,1,5,4), (2,1,1)(3,4,1,5,2), (2,1,2)(3,5,1,4,2),
(2,2,0)(4,3,1,5,2), (2,2,1)(5,3,1,4,2), (2,2,2)(2,3,1,5,4)
Listing of the elements x ∈ Z3
and the corresponding values of S(x) ∈ S5.
(0,0,0)(2,1,3,4,5), (0,0,1)(2,4,3,1,5), (0,0,2)(2,5,3,1,4),
(0,1,0)(2,1,4,5,3), (0,1,1)(2,4,1,5,3), (0,1,2)(2,5,4,1,3),
(0,2,0)(2,1,5,4,3), (0,2,1)(2,4,5,1,3), (0,2,2)(2,3,5,1,4),
(1,0,0)(4,2,3,1,5), (1,0,1)(5,2,3,1,4), (1,0,2)(1,2,3,5,4),
(1,1,0)(3,2,4,1,5), (1,1,1)(5,2,4,1,3), (1,1,2)(1,2,4,5,3),
(1,2,0)(4,2,5,1,3), (1,2,1)(5,2,1,4,3), (1,2,2)(1,2,5,4,3),
(2,0,0)(4,1,2,5,3), (2,0,1)(5,4,2,1,3), (2,0,2)(1,5,2,4,3),
(2,1,0)(3,1,2,5,4), (2,1,1)(3,4,2,1,5), (2,1,2)(3,5,2,1,4),
(2,2,0)(4,3,2,1,5), (2,2,1)(5,3,2,1,4), (2,2,2)(1,3,2,5,4)
Listing of the elements x ∈ Z4
and the corresponding values of T (x) ∈ S6.
(0,0,0,0)(2,4,3,1,5,6), (0,0,0,1)(2,4,3,6,1,5),
(0,0,0,2)(2,4,3,5,1,6), (0,0,1,0)(2,1,4,6,5,3),
(0,0,1,1)(2,1,4,3,6,5), (0,0,1,2)(2,1,4,5,6,3),
(0,0,2,0)(2,3,1,6,5,4), (0,0,2,1)(2,3,1,5,6,4),
(0,0,2,2)(2,3,1,4,6,5), (0,1,0,0)(2,5,3,1,6,4),
(0,1,0,1)(2,4,5,3,1,6), (0,1,0,2)(2,5,3,4,1,6),
(0,1,1,0)(2,5,4,1,6,3), (0,1,1,1)(2,5,4,3,1,6),
(0,1,1,2)(2,1,5,4,6,3), (0,1,2,0)(2,3,5,1,6,4),
(0,1,2,1)(2,5,1,3,6,4), (0,1,2,2)(2,5,1,4,6,3),
(0,2,0,0)(2,6,3,1,5,4), (0,2,0,1)(2,4,6,3,1,5),
(0,2,0,2)(2,6,3,4,1,5), (0,2,1,0)(2,6,4,1,5,3),
(0,2,1,1)(2,6,4,3,1,5), (0,2,1,2)(2,1,6,4,5,3),
(0,2,2,0)(2,3,6,1,5,4), (0,2,2,1)(2,6,1,3,5,4),
(0,2,2,2)(2,6,1,4,5,3), (1,0,0,0)(1,2,3,5,6,4),
(1,0,0,1)(1,2,3,6,5,4), (1,0,0,2)(1,2,3,4,6,5),
(1,0,1,0)(3,2,4,1,6,5), (1,0,1,1)(3,2,4,6,1,5),
(1,0,1,2)(3,2,4,5,1,6), (1,0,2,0)(4,2,1,5,6,3),
(1,0,2,1)(4,2,1,3,6,5), (1,0,2,2)(4,2,1,6,5,3),
(1,1,0,0)(6,2,3,1,5,4), (1,1,0,1)(1,2,5,3,6,4),
(1,1,0,2)(6,2,3,4,1,5), (1,1,1,0)(3,2,5,1,6,4),
(1,1,1,1)(6,2,5,3,1,4), (1,1,1,2)(6,2,5,4,1,3),
(1,1,2,0)(4,2,5,1,6,3), (1,1,2,1)(6,2,1,3,5,4),
(1,1,2,2)(6,2,1,4,5,3), (1,2,0,0)(5,2,3,1,6,4),
(1,2,0,1)(1,2,6,3,5,4), (1,2,0,2)(5,2,3,4,1,6),
(1,2,1,0)(5,2,4,1,6,3), (1,2,1,1)(5,2,6,3,1,4),
(1,2,1,2)(5,2,6,4,1,3), (1,2,2,0)(4,2,6,1,5,3),
(1,2,2,1)(5,2,1,3,6,4), (1,2,2,2)(5,2,1,4,6,3),
(2,0,0,0)(1,4,2,5,6,3), (2,0,0,1)(1,4,2,3,6,5),
(2,0,0,2)(1,4,2,6,5,3), (2,0,1,0)(3,1,2,5,6,4),
(2,0,1,1)(3,1,2,6,5,4), (2,0,1,2)(3,1,2,4,6,5),
(2,0,2,0)(4,3,2,1,6,5), (2,0,2,1)(4,3,2,6,1,5),
(2,0,2,2)(4,3,2,5,1,6), (2,1,0,0)(6,4,2,1,5,3),
(2,1,0,1)(6,4,2,3,1,5), (2,1,0,2)(1,5,2,4,6,3),
(2,1,1,0)(3,5,2,1,6,4), (2,1,1,1)(6,1,2,3,5,4),
(2,1,1,2)(6,5,2,4,1,3), (2,1,2,0)(6,3,2,1,5,4),
(2,1,2,1)(4,5,2,3,1,6), (2,1,2,2)(6,3,2,4,1,5),
(2,2,0,0)(5,4,2,1,6,3), (2,2,0,1)(5,4,2,3,1,6),
(2,2,0,2)(1,6,2,4,5,3), (2,2,1,0)(3,6,2,1,5,4),
(2,2,1,1)(5,1,2,3,6,4), (2,2,1,2)(5,6,2,4,1,3),
(2,2,2,0)(5,3,2,1,6,4), (2,2,2,1)(4,6,2,3,1,5),
(2,2,2,2)(5,3,2,4,1,6)
	Introduction
	Notations and main results
	The general recursive construction.
	Proof of Theorem ??, second part
	Proof of Theorem ??, last part

  Distance-preserving mappings (DPMs) are mappings from the set of all q-ary
vectors of a fixed length to the set of permutations of the same or longer
length such that every two distinct vectors are mapped to permutations with the
same or even larger Hamming distance than that of the vectors. In this paper,
we propose a construction of DPMs from ternary vectors. The constructed DPMs
improve the lower bounds on the maximal size of permutation arrays.

Introduction
A mapping from the set of all q-ary vectors of length m to the set of all
permutations of {1, 2, . . . , n} is called a distance-preserving mapping (DPM)
if every two distinct vectors are mapped to permutations with the same or
even larger Hamming distance mutual than that of the vectors. A distance-
increasing mapping (DIM) is a special DPM such that the distances are
strictly increased except when that is obviously not possible. DPMs and
∗Jyh-Shyan Lin, Jen-Chun Chang, and Rong-Jaye Chen are with the Dept. of Com-
puter Science and Inform. Engineering, National Taipei University, Taipei, Taiwan.
†Torleiv Kløve is with the Department of Informatics, University of Bergen, Bergen,
Norway.
http://arxiv.org/abs/0704.1358v1
DIMs are useful for the construction of permutation arrays (PAs) which are
applied to various applications, such as trellis code modulations and power
line communications [7], [8], [9], [10], [11], [13], [21], [22], [23], [24]. All
DPMs and DIMs proposed so far are from binary vectors: [2], [3], [4], [5],
[6], [12], [14], [15], [16], [17], [19], [20]. In this paper we propose a general
construction method to construct DPMs or DIMs from ternary vectors. By
using this method, we construct DIMs for n = m + 2 for m ≥ 3, DPMs for
n = m+ 1 for m ≥ 9, and DPMs for n = m for m ≥ 13.
The paper is organized as follows. In the next section we introduce some
notations and state our main results. In Section 3 we introduce a general
recursive construction of DPMs and DIMs. In Sections 4 and 5 we introduce
mappings that can be used to start the recursion in the three cases we con-
sider. Finally, in an appendix, we give explicit listings of the values of some
mappings that are used as building blocks to construct the mappings given
in Sections 4 and 5.
2 Notations and main results
Let Sn denote the set of all n! permutations of Fn = {1, 2, . . . , n}. A per-
mutation π : Fn → Fn is represented by an n-tuple π = (π1, π2, . . . , πn)
where πi = π(i). Let Z
denote the set of all ternary vectors of length
n. The Hamming distance between two n-tuples a = (a1, a2, . . . , an) and
b = (b1, b2, . . . , bn) is denoted by dH(a,b) and is defined as
dH(a,b) = |{j ∈ Fn : aj 6= bj}|.
Let Fn,k be the set of injective functions from Z
to Sn+k. Note that Fn,k
is empty if (n + k)! < 3n.
For k ≥ 0, let Pn,k be the set of functions in Fn,k such that
dH(f(x), f(y)) ≥ dH(x,y)
for all x,y ∈ Zn
. These mappings are called distance preserving mappings
(DPM).
For k ≥ 1, let In,k be the set of functions in Fn,k such that
dH(f(x), f(y)) > dH(x,y) (1)
for all distinct x,y ∈ Zn
. These mappings are called distance increasing
mappings (DIM).
Our main result is the following theorem.
Theorem 1 a) In,2 is non-empty for n ≥ 3.
b) Pn,1 is non-empty for n ≥ 9.
c) Pn,0 is non-empty for n ≥ 13.
The proof of the theorem is constructive. A relatively simple recursive
method is given (in the next section) to construct a mapping of length n+1
from a mapping of length n. Explicit mappings that start the recursion in
the three cases are given in last part of the paper, including the appendix.
An (n, d) permutation array (PA) is a subset of Sn such that the Hamming
distance between any two distinct permutations in the array is at least d. An
(n, d; q) code is a subset of vectors (codewords) of length n over an alphabet
of size q and with distance at least d between distinct codewords. One
construction method of PAs is to construct an (n, d′)-PA from an (m, d; q)
code using DPMs or DIMs. More precisely, if C is an (m, d; q) code and there
exists an DPM f from Zmq to Sn, then f(C) is an (n, d) PA. If f is DIM, then
f(C) is an (n, d+1) PA. This has been a main motivation for studying DPMs.
Let P (n, d) denote the largest possible size of an (n, d)-PA. The exact value
of P (n, d) is still an open problem in most cases, but we can lower bound
this value by the maximal size of a suitable code provided a DPM (or DIM)
is known. Let Aq(n, d) denote the largest possible size of an (n, d) code over
a code alphabet of size q. In [5], Chang et al. used this approach to show
that for n ≥ 4 and 2 ≤ d ≤ n, we have P (n, d) ≥ A2(n, d − 1). In [17],
Chang further improved the bound to P (n, d) ≤ A2(n, d− δ) for n ≥ nδ and
δ + 1 ≤ d ≤ n where δ ≥ 2 and nδ is a positive integer determined by δ, e.g.
n2 = 16.
From Theorem 1 we get the following bounds.
Theorem 2 a) For n ≥ 5 and 2 ≤ d ≤ n, we have
P (n, d) ≥ A3(n− 2, d− 1).
b) For n ≥ 10 and 2 ≤ d ≤ n, we have
P (n, d) ≥ A3(n− 1, d).
c) For n ≥ 13 and 2 ≤ d ≤ n, we have
P (n, d) ≥ A3(n, d).
Bounds on A2(n, d) and A3(n, d) have been studied by many researchers,
see e.g. [18, Ch.5] and [1]. In general, the lower bounds on P (n, d) obtained
from use of ternary codes are better than those obtained from binary codes.
For example, using Chang’s bound [17], we get P (16, 5) ≥ A2(16, 3) ≥ 2720,
whereas Theorem 2 gives P (16, 5) ≥ A3(16, 5) ≥ 19683. Similarly, we get
P (16, 9) ≥ A2(16, 7) ≥ 36 and P (16, 9) ≥ A3(16, 9) ≥ 243.
3 The general recursive construction.
For any array u = (u1, u2, . . . , un), we use the notation ui = ui.
We start with a recursive definition of functions from Zn
to Sn+k. For
f ∈ Fn,k, define g = H(f) ∈ Fn+1,k as follows. Let x = (x1, x2, . . . , xn) ∈ Z
and f(x) = (ϕ1, ϕ2, . . . , ϕn+k). Suppose that the element n+ k− 4 occurs in
position r, that is ϕr = n + k − 4. Then
g(x|0)n+k+1 = n+ k + 1,
g(x|0)i = ϕi otherwise;
g(x|1)r = n+ k + 1,
g(x|1)n+k+1 = n+ k − 4,
g(x|1)i = ϕi otherwise;
if n is odd or xn < 2, then
g(x|2)n+k = n + k + 1,
g(x|2)n+k+1 = ϕn+k,
g(x|2)i = ϕi otherwise;
if n is even and xn = 2, then
g(x|2)n+k−1 = n+ k + 1,
g(x|2)n+k+1 = ϕn+k−1,
g(x|2)i = ϕi otherwise.
We note that g(x|a)i 6= f(x)i for at most one value of i ≤ n+ k.
For f ∈ Fm,k, we define a sequence of functions f ∈ Fn,k, for all n ≥ m,
recursively by
fm = f and fn+1 = H(fn) for n ≥ m.
Theorem 3 If fm ∈ Pm,k where k ≥ 0, m is odd, and
fm(x)m+k 6∈ {m+ k − 4, m+ k − 3} for all x ∈ Z
then fn ∈ Pn,k for all n ≥ m.
Theorem 4 If fm ∈ Im,k, where k > 0 and m is odd, and
fm(x)m+k 6∈ {m+ k − 4, m+ k − 3} for all x ∈ Z
then fn ∈ In,k for all n ≥ m.
Proof: We prove Theorem 4; the proof of Theorem 3 is similar (and a little
simpler). The proof is by induction. First we prove that g = fm+1 ∈ Im+1,k.
Let x,y ∈ Zm
f(x) = (ϕ1, ϕ2, . . . , ϕm+k), ϕr = m+ k − 4,
f(y) = (γ1, γ2, . . . , γm+k), γs = m+ k − 4.
We want to show that
dH(g(x|a), g(y|b)) > dH((x|a), (y|b))
if (x|a) 6= (y|b).
First, consider x = y and a 6= b. Since ϕm+k 6= m + k − 4, it follows
immediately from the definition of g that
dH(g(x|a), g(x|b)) ≥ 2 > 1 = dH((x|a), (x|b)).
For x 6= y, we want to show that
dH(g(x|a), g(y|b))− dH(f(x), f(y)) ≥ dH(a, b) (2)
for all a, b ∈ Z3 since this implies
dH(g(x|a), g(y|b)) ≥ dH(f(x), f(y)) + dH(a, b)
> dH(x,y) + dH(a, b)
= dH((x|a), (y|b)).
The condition (2) is equivalent to the following.
m+k+1∑
(∆g,i −∆f,i) ≥ dH(a, b), (3)
where
∆g,i = dH(g(x|a)i, g(y|b)i)
∆f,i = dH(f(x)i, f(y)i),
and where, for technical reasons, we define
∆f,n+k+1 = 0.
The point is at most three of the terms ∆g,i − ∆f,i are non-zero. We look
at one combination of a and b in detail as an illustration, namely a = 1 and
b = 2. Then g(x|a)i = f(x)i and g(y|b)i = f(y)i and so ∆g,i = ∆f,i for all
i ≤ m+ k + 1, except in the following three cases
i f(x)i f(y)i g(x|a)i g(y|b)i)
r m+ k − 4 γr m+ k + 1 γr
m+ k ϕm+k γm+k ϕm+k m+ k + 1
m+ k + 1 − − m+ k − 4 γm+k
i ∆f,i ∆g,i ∆g,i −∆f,i
r 0 or 1 1 0 or 1
m+ k 0 or 1 1 0 or 1
m+ k + 1 0 1 1
Note that we have used the fact that γm+k 6= m + k − 4. We see that∑
(∆g,i −∆f,i) ≥ 1 = dH(a, b).
The other combinations of a and b are similar. This proves that fm+1 =
g ∈ Im+1,k.
Now, let h = H(g) = fm+2. A similar analysis will show that h ∈ Im+2,k.
We first give a table of the last three symbols in h(x|a1a2) as these three
symbols are the most important in the proof. Let ϕs = m + k − 3. By
assumption, s < m+ k.
a1a2 h(x|a1a2)m+k h(x|a1a2)m+k+1 h(x|a1a2)m+k+2
00 ϕm+k m+ k + 1 m+ k + 2
10 ϕm+k m+ k − 4 m+ k + 2
20 m+ k + 1 ϕm+k m+ k + 2
01 ϕm+k m+ k + 1 m+ k − 3
11 ϕm+k m+ k − 4 m+ k − 3
21 m+ k + 1 ϕm+k m+ k − 3
02 ϕm+k m+ k + 2 m+ k + 1
12 ϕm+k m+ k + 2 m+ k − 4
22 m+ k + 2 ϕm+k m+ k + 1
In addition,
h(x|1a2)r = m+ k + 1 and h(x|a11)s = m+ k + 2.
Note that we have used the fact that ϕm+k 6= m + k − 3 here, since if we
had ϕm+k = m+ k − 3, then we would for example have had h(x|01)m+k =
m+ k + 2. From the table we first see that
dH(h(x|a1a2), h(x|b1b2)) > dH(a1a2, b1b2)
if a1a2 6= b1b2. For example h(x|10) and h(x|21) differ in positions r, s, m+k,
m+ k+ 1 and m+ k+ 2. As another example, h(x|02) and h(x|22) differ in
positions m+ k and m+ k + 1.
Next, consider dH(h(x|a1a2), h(y|b1b2)) for x 6= y. We see that
dH(h(x|a1a2)i, h(y|b1b2)i) ≥ dH(f(x)i, f(y)i)
for i < m+ k: from the table above, we can see that
dH(h(x|a1a2)m+kh(x|a1a2)m+k+1h(x|a1a2)m+k+2,
h(y|b1b2)m+kh(y|b1b2)m+k+1h(y|b1b2)m+k+2)
≥ dH(ϕm+k, γm+k) + dH(a1a2, b1b2).
As an example, let a1a2 = 10 and b1b2 = 02. Then
h(x|10)m+k, h(x|10)m+k+1, h(x|10)m+k+2
= ϕm+k, m+ k − 4, m+ k + 2
h(y|02)m+k, h(y|02)m+k+1, h(y|02)m+k+2
= γm+k, m+ k + 2, m+ k + 1.
The distance between the two is 2 (if ϕm+k = γm+k) or 3 (otherwise). The
other combinations of a1a2 and b1b2 are similar. From this we can conclude
that h ∈ Im+2,k in a similar way we showed that g ∈ Im+1,k above.
Further, we note that
h(x|a1a2)m+k+2 6∈ {(m+ 2) + k − 4, (m+ 2) + k − 3}.
Therefore, we can repeat the argument and, by induction, obtain fn ∈ In,k
for all n ≥ m.
A function F is given by an explicit listing in the appendix. It belongs
to I3,2 and satisfy F (x)5 6∈ {1, 2}. This, combined with Theorem 4, proves
Theorem 1 a).
4 Proof of Theorem 1, second part
To prove Theorem 1 b), using Theorem 3, we need some f ∈ P9,1 such that
f(x)10 6∈ {6, 7} for all x ∈ Z
. (4)
An extensive computer search has been unsuccessful in coming up with such a
mapping. However, an indirect approach has been successful. The approach
is to construct f from two simpler mappings found by computer search.
For a vector ρ = (ρ1, ρ2, . . . , ρn) and a set X ⊂ {1, 2, . . . , n}, let ρ\X
denote the vector obtained from ρ by removing the elements with subscript
in X . For example,
(ρ1, ρ2, ρ3, ρ4, ρ5, ρ6)\{1,5} = (ρ2, ρ3, ρ4, ρ6).
By computer search we have found mappings G ∈ F5,2 and H ∈ F4,2 that
satisfy the following conditions
a) for every x ∈ Z5
, 6 ∈ {G(x)1, G(x)2, G(x)3},
b) for every x ∈ Z5
, 7 ∈ {G(x)4, G(x)5, G(x)6},
c) for every distinct x,y ∈ Z5
dH(G(x)\{7}, G(y)\{7}) ≥ dH(x,y),
d) for every u ∈ Z4
, 1 ∈ {H(u)1, H(u)2, H(u)3},
e) for every distinct u,v ∈ Z4
dH(H(u)\{5,6}, H(v)\{5,6}) ≥ dH(u,v).
The mappings G and H are listed explicitly in the appendix. We will now
show how these mappings can be combined to produce a mapping f ∈ P9,1
satisfying (4).
Let x ∈ Z9
. Then x = (xL,xR), where xL ∈ Z
and xR ∈ Z
. Let
(ϕ1, ϕ2, ϕ3, ϕ4, ϕ5, ϕ6, ϕ7) = G(xL),
(γ1, γ2, γ3, γ4, γ5, γ6) = H(xR) + (4, 4, 4, 4, 4, 4).
We note that Condition d) implies that γ5 ≥ 6 and γ6 ≥ 6. Similarly,
Conditions a) and b) imply that ϕ7 ≤ 5.
Define ρ = (ρ1, ρ2, . . . , ρ10) as follows.
ρi = γ5 if 1 ≤ i ≤ 3 and ϕi = 6,
ρi = γ6 if 4 ≤ i ≤ 6 and ϕi = 7,
ρi = ϕi if 1 ≤ i ≤ 6 and ϕi ≤ 5,
ρi = ϕ7 if 7 ≤ i ≤ 9 and γi−6 = 5,
ρi = γi−6 if 7 ≤ i ≤ 10 and γi−6 ≥ 6.
In ρ, swap 1 and 6 and also swap 2 and 7, and let the resulting array be
denoted by π. More formally,
πi = 1 if ρi = 6,
πi = 2 if ρi = 7,
πi = 6 if ρi = 1,
πi = 7 if ρi = 2,
πi = ρi otherwise.
Then define
f(x) = π.
We will show that f has the stated properties. We first show that π ∈ S10.
We have ϕ ∈ S7 and γ is a permutation of (5, 6, 7, 8, 9, 10). In particular, 5,6,
and 7 appear both in ϕ and γ. The effect of the first line in the definition of ρ
is to move another elements (γ5) into the position where ϕ has a 6. Similarly,
the second line overwrites the 7 in ρ, and the fourth line overwrites the 5 in
γ. The definition of ρ is then the concatenation of the six first (overwritten)
elements of ϕ and the five first (overwritten) elements of γ. Therefore, ρ
contains no duplicate elements, that is, ρ ∈ S10.
The element 1 in ρ must be either in one of the first six positions, coming
from ϕ, or in one of the positions 7− 9 (if ϕ7 = 1). Similarly, the element 2
must be in one of the first nine positions of ρ. Therefore, both 6 and 7 must
be among the first nine elements of π, that is π10 6∈ {6, 7}.
Finally, we must show that f is distance preserving. Let x 6= x′, and let
the arrays corresponding to x′ be denoted by ϕ′, γ′, ρ′ and π′. By assumption,
dH(x,x
′) = dH(xL,x
L) + dH(xR,x
≤ dH(ϕ\{7}, ϕ
\{7}) + dH(γ\{5,6}, γ
\{5,6}). (5)
For 1 ≤ i ≤ 6 we have
dH(ϕi, ϕ
i) ≤ dH(ρi, ρ
i). (6)
If ϕi = ϕ
i this is obvious. Otherwise, we may assume without loss of gener-
ality that ϕ′i < ϕi and we must show that ρi 6= ρ
i. If ϕi ≤ 5, then
ρ′i = ϕ
i < ϕi = ρi.
If ϕi = 6, then
ρ′i = ϕ
i ≤ 5 and ρi = γ5 ≥ 6.
If ϕi = 7, then 4 ≤ i ≤ 6 and so ϕ
i 6= 6. Hence
ρ′i = ϕ
i ≤ 5 and ρi = γ6 ≥ 6.
This completes that proof of (6). A similar arguments show that for 7 ≤ i ≤
10 we have
dH(γi−6, γ
i−6) ≤ dH(ρi, ρ
i), (7)
and that for 1 ≤ i ≤ 10 we have
dH(ρi, ρ
i) ≤ dH(πi, π
i). (8)
Combining (5)–(8), we get
dH(x,x
′) ≤ dH(ϕ\{7}, ϕ
\{7}) + dH(γ\{5,6}, γ
\{5,6})
≤ dH(ρ, ρ
′) ≤ dH(π, π
Hence, f is distance preserving.
5 Proof of Theorem 1, last part
The construction of a mapping f ∈ P13,0 which proves Theorem 1 c) is similar
to the construction in the previous section. However, the construction is more
involved and contains several steps. We will describe the constructions and
properties of the intermediate mappings. The details of proofs are similar to
the proof in the previous section and we omit these details.
We start with three mappings R, S ∈ F3,2 and T ∈ F4,2. These were
found by computer search and are listed explicitly in the appendix. They
have the following properties:
• for every x ∈ Z3
, 1 ∈ {R(x)1, R(x)2, R(x)3},
• for every x ∈ Z3
, R(x)5 6= 5,
• for every distinct x,y ∈ Z3
dH(R(x)\{4,5}, R(y)\{4,5}) ≥ dH(x,y),
• for every x ∈ Z3
, 2 ∈ {S(x)1, S(x)2, S(x)3},
• for every x ∈ Z3
, S(x)5 6= 1,
• for every distinct x,y ∈ Z3
dH(S(x)\{4,5}, S(y)\{4,5}) ≥ dH(x,y),
• for every x ∈ Z4
, 2 ∈ {T (x)1, T (x)2, T (x)3},
• for every x ∈ Z4
, T (x)6 6= 1,
• for every distinct x,y ∈ Z4
dH(T (x)\{5,6}, T (y)\{5,6}) ≥ dH(x,y).
These mappings are used as building blocks similarly to what was done in
the previous section.
Construction of U ∈ F6,2
Let x ∈ Z6
and let
(ϕ1, ϕ2, ϕ3, ϕ4, ϕ5) = R(x1, x2, x3),
(γ1, γ2, γ3, γ4, γ5) = S(x4, x5, x6) + (3, 3, 3, 3, 3).
Define ρ = (ρ1, ρ2, . . . , ρ8) as follows.
ρi = γ5 if 1 ≤ i ≤ 4 and ϕi = 5,
ρi = ϕi if 1 ≤ i ≤ 4 and ϕi 6= 5,
ρi = ϕ5 if 5 ≤ i ≤ 8 and γi−4 = 4,
ρi = γi−4 if 5 ≤ i ≤ 8 and γi−4 6= 4.
In ρ, swap 1 and 7 and also swap 5 and 8, and let the resulting array be
U(x). It has the following properties:
• for every x ∈ Z6
, 7 ∈ {U(x)1, U(x)2, U(x)3},
• for every x ∈ Z6
, 8 ∈ {U(x)5, U(x)6, U(x)7},
• for every distinct x,y ∈ Z6
dH(U(x)\{4,8}, U(y)\{4,8}) ≥ dH(x,y).
Construction of V ∈ F7,2
Let x ∈ Z7
and let
(ϕ1, ϕ2, ϕ3, ϕ4, ϕ5) = R(x1, x2, x3),
(γ1, γ2, γ3, γ4, γ5, γ6) = T (x4, x5, x6, x7) + (3, 3, . . . , 3).
Define ρ = (ρ1, ρ2, . . . , ρ8, ρ9) as follows.
ρi = γ6 if 1 ≤ i ≤ 4 and ϕi = 5,
ρi = ϕi if 1 ≤ i ≤ 4 and ϕi 6= 5,
ρi = ϕ5 if 5 ≤ i ≤ 9 and γi−4 = 4,
ρi = γi−4 if 5 ≤ i ≤ 9 and γi−4 6= 4.
In ρ, swap 2 and 5, and let the resulting array be V (x). It has the
following properties:
• for every x ∈ Z7
, 1 ∈ {V (x)1, V (x)2, V (x)3},
• for every x ∈ Z7
, 2 ∈ {V (x)5, V (x)6, V (x)7},
• for every distinct x,y ∈ Z7
dH(V (x)\{4,9}, V (y)\{4,9}) ≥ dH(x,y).
Construction of f ∈ P13,0
Let x ∈ Z13
and let
(ϕ1, ϕ2, . . . , ϕ8) = U(x1, x2, . . . , x6),
(γ1, γ2, . . . , γ9) = V (x7, x8, . . . , x13) + (4, 4, . . . , 4).
Define ρ = (ρ1, ρ2, . . . , ρ13) as follows.
ρi = γ4 if 1 ≤ i ≤ 3 and ϕi = 7,
ρi = ϕi if 1 ≤ i ≤ 3 and ϕi 6= 7,
ρi = γ9 if 4 ≤ i ≤ 6 and ϕi+1 = 8,
ρi = ϕi+1 if 4 ≤ i ≤ 6 and ϕi+1 6= 8,
ρi = ϕ4 if 7 ≤ i ≤ 9 and γi−6 = 5,
ρi = γi−6 if 7 ≤ i ≤ 9 and γi−6 6= 5,
ρi = ϕ8 if 10 ≤ i ≤ 13 and γi−5 = 6,
ρi = γi−5 if 10 ≤ i ≤ 13 and γi−5 6= 6.
In ρ, swap 1 and 9 and also swap 2 and 10, and let the resulting array be
f(x). Then
f ∈ P13,0 and f(x)13 6∈ {9, 10}.
References
[1] A.E. Brouwer, Heikki O. Hämäläinen, Patric R.J. Österg̊ard, N.J.A.
Sloane, “Bounds on mixed binary/ternary codes”, IEEE Trans. on In-
form. Theory, vol. 44, no. 1, pp. 140–161, Jan. 1998.
[2] J.-C. Chang, “Distance-increasing mappings from binary vectors to per-
mutations”, IEEE Trans. on Inform. Theory, vol. 51, no. 1, pp. 359–363,
Jan. 2005.
[3] J.-C. Chang, “New algorithms of distance-increasing mappings from bi-
nary vectors to permutations by swaps”, Designs, Codes and Cryptog-
raphy, vol. 39, pp. 335–345, Jan. 2006.
[4] J.-C. Chang, “Distance-increasing mappings from binary vectors to per-
mutations that increase Hamming distances by at least two”, IEEE
Trans. on Inform. Theory, vol. 52, no. 4, pp. 1683–1689, April 2006.
[5] J.-C. Chang, R.-J. Chen, T. Kløve, and S.-C. Tsai, “Distance-preserving
mappings from binary vectors to permutations”, IEEE Trans. on In-
form. Theory, vol. 49, pp. 1054–1059, Apr. 2003.
[6] C. J. Colbourn, T. Kløve, and A. C. H. Ling, “Permutation arrays for
powerline communication and mutually orthogonal latin squares”, IEEE
Trans. on Inform. Theory, vol. 50, no. 6, pp. 1289–1291, June 2004.
[7] C. Ding, F.-W. Fu, T. Kløve, and V. K. Wei, “Constructions of permu-
tation arrays”, IEEE Trans. on Inform. Theory, vol. 48, pp. 977–980,
Apr. 2002.
[8] H. C. Ferreira and A. J. H. Vinck, “Inference cancellation with per-
mutation trellis arrays”, Proc. IEEE Vehicular Technology Conf., pp.
2401–2407, 2000.
[9] H. C. Ferreira, A. J. H. Vinck, T. G. Swart, and A. L. Nel, “Permutation
trellis codes”, Proc. IEEE Trans. on Communications, vol. 53, no. 11,
pp. 1782–1789, Nov. 2005.
[10] H. C. Ferreira, D Wright, and A. L. Nel, “Hamming distance preserv-
ing mappings and trellis codes with constrained binary symbols”, IEEE
Trans. on Inform. Theory, vol. 35, no. 5, pp. 1098–1103, Sept. 1989.
[11] F.-W. Fu and T. Kløve, “Two constructions of permutation arrays”,
IEEE Trans. on Inform. Theory, vol. 50, pp. 881–883, May. 2004.
[12] Y.-Y. Huang, S.-C. Tsai, H.-L. Wu, “On the construction of permutation
arrays via mappings from binary vectors to permutations”, Designs,
Codes and Cryptography, vol. 40, pp. 139–155, 2006.
[13] T. Kløve, “Classification of permutation codes of length 6 and minimum
distance 5”, Proc. Int. Symp. Information Theory and Its Applications,
2000, pp. 465–468.
[14] K. Lee, “New distance-preserving maps of odd length”, IEEE Trans. on
Inform. Theory, vol. 50, no. 10, pp. 2539–2543, Oct. 2004.
[15] K. Lee, “Cyclic constructions of distance-preserving maps”, IEEE
Trans. on Inform. Theory, vol. 51, no. 12, pp. 4292–4396, Dec. 2005.
[16] K. Lee, “Distance-increasing maps of all length by simple mapping al-
gorithms”, arXiv:cs.IT/0509073, 23 Sept. 2005.
[17] J.-S. Lin, J.-C. Chang, and R.-J. Chen, “New simple constructions of
distance-increasing mappings from binary vectors to permutations”, In-
formation Processing Letters, vol. 100, no. 2, pp. 83–89, Oct. 2006.
[18] V. S. Pless and W. C. Huffman, Eds., Handbook of Coding Theory.
Amsterdam, The Netherlands: Elsevier, 1998.
[19] T. G Swart, I. de Beer, H. C. Ferreira, “On the distance optimality of
permutation mappings”, Proc. IEEE Int. Symp. Information Theory,
Adelaide, Australia, September 2005, pp. 1068–1072.
[20] T. G Swart and H. C. Ferreira, “A multilevel construction for map-
pings from binary sequences to permutation sequences”, Proc. IEEE Int.
Symp. Information Theory, Seattle, USA, July 2006, pp. 1895–1899.
[21] A. J. H. Vinck, “Coding and modulation for powerline communications”,
A.E.Ü . Int. J. Electron. Commun., vol. 54, no. 1, pp. 45–49, Oct. 2000.
[22] A. J. H. Vinck and J. Häring, “Coding and modulation for power-line
communications”, Proc. Int. Symp. Power Line Communication, Lim-
erick, Ireland, Apr. 57, 2000.
[23] A. J. H. Vinck, J. Häring, and T. Wadayama, “Coded M-FSK for power-
line communications”, Proc. IEEE Int. Symp. Information Theory, Sor-
rento, Italy, June 2000, p. 137.
[24] T. Wadayama and A. J. H. Vinck, “A multilevel construction of permu-
tation codes”, IEICE Trans. Fundamentals Electron., Commun. Comp.
Sci., vol. 84, pp. 2518–2522, 2001.
Appendix
Listing of the elements x ∈ Z3
and the corresponding values of F (x) ∈ S5.
(0,0,0)(1,2,3,4,5), (0,0,1)(1,2,5,4,3), (0,0,2)(1,2,3,5,4),
(0,1,0)(4,2,3,1,5), (0,1,1)(4,2,5,1,3), (0,1,2)(5,2,3,1,4),
(0,2,0)(1,4,3,2,5), (0,2,1)(1,4,5,2,3), (0,2,2)(1,5,3,2,4),
(1,0,0)(2,3,1,4,5), (1,0,1)(2,5,1,4,3), (1,0,2)(2,3,1,5,4),
(1,1,0)(2,3,4,1,5), (1,1,1)(2,5,4,1,3), (1,1,2)(2,3,5,1,4),
(1,2,0)(4,3,1,2,5), (1,2,1)(4,5,1,2,3), (1,2,2)(5,3,1,2,4),
(2,0,0)(3,1,2,4,5), (2,0,1)(5,1,2,4,3), (2,0,2)(3,1,2,5,4),
(2,1,0)(3,4,2,1,5), (2,1,1)(5,4,2,1,3), (2,1,2)(3,5,2,1,4),
(2,2,0)(3,1,4,2,5), (2,2,1)(5,1,4,2,3), (2,2,2)(3,1,5,2,4)
Listing of the elements x ∈ Z5
and the corresponding values of G(x) ∈ S7.
(0,0,0,0,0)(6,1,2,7,3,4,5), (0,0,0,0,1)(6,3,2,7,1,5,4),
(0,0,0,0,2)(6,3,2,7,4,5,1), (0,0,0,1,0)(6,2,1,7,5,3,4),
(0,0,0,1,1)(6,1,2,7,5,3,4), (0,0,0,1,2)(6,3,2,7,5,4,1),
(0,0,0,2,0)(6,1,2,7,3,5,4), (0,0,0,2,1)(6,3,1,7,2,5,4),
(0,0,0,2,2)(6,3,1,7,4,5,2), (0,0,1,0,0)(6,2,5,7,1,4,3),
(0,0,1,0,1)(6,2,5,7,3,4,1), (0,0,1,0,2)(6,3,5,7,4,1,2),
(0,0,1,1,0)(6,2,5,7,1,3,4), (0,0,1,1,1)(6,5,1,7,2,3,4),
(0,0,1,1,2)(6,2,5,7,4,3,1), (0,0,1,2,0)(6,4,5,7,1,3,2),
(0,0,1,2,1)(6,2,4,7,1,5,3), (0,0,1,2,2)(6,1,5,7,4,2,3),
(0,0,2,0,0)(6,4,2,7,3,1,5), (0,0,2,0,1)(6,3,4,7,2,1,5),
(0,0,2,0,2)(6,3,2,7,4,1,5), (0,0,2,1,0)(6,4,1,7,5,3,2),
(0,0,2,1,1)(6,5,4,7,2,3,1), (0,0,2,1,2)(6,5,2,7,4,3,1),
(0,0,2,2,0)(6,4,1,7,5,2,3), (0,0,2,2,1)(6,5,4,7,3,2,1),
(0,0,2,2,2)(6,5,3,7,4,2,1), (0,1,0,0,0)(6,1,3,2,7,5,4),
(0,1,0,0,1)(6,3,2,4,7,5,1), (0,1,0,0,2)(6,3,2,5,7,4,1),
(0,1,0,1,0)(6,4,2,5,7,3,1), (0,1,0,1,1)(6,2,1,5,7,3,4),
(0,1,0,1,2)(6,5,2,1,7,4,3), (0,1,0,2,0)(6,2,1,3,7,5,4),
(0,1,0,2,1)(6,3,1,4,7,5,2), (0,1,0,2,2)(6,5,2,3,7,4,1),
(0,1,1,0,0)(6,3,5,2,7,1,4), (0,1,1,0,1)(6,2,3,5,7,4,1),
(0,1,1,0,2)(6,3,5,2,7,4,1), (0,1,1,1,0)(6,2,5,4,7,3,1),
(0,1,1,1,1)(6,2,5,1,7,3,4), (0,1,1,1,2)(6,3,5,1,7,4,2),
(0,1,1,2,0)(6,2,5,3,7,1,4), (0,1,1,2,1)(6,5,1,3,7,2,4),
(0,1,1,2,2)(6,4,5,3,7,2,1), (0,1,2,0,0)(6,5,4,2,7,1,3),
(0,1,2,0,1)(6,4,3,2,7,1,5), (0,1,2,0,2)(6,5,3,2,7,4,1),
(0,1,2,1,0)(6,4,2,1,7,3,5), (0,1,2,1,1)(6,5,4,1,7,3,2),
(0,1,2,1,2)(6,3,4,5,7,2,1), (0,1,2,2,0)(6,5,4,3,7,1,2),
(0,1,2,2,1)(6,5,4,3,7,2,1), (0,1,2,2,2)(6,4,3,1,7,2,5),
(0,2,0,0,0)(6,4,1,5,3,7,2), (0,2,0,0,1)(6,3,2,4,1,7,5),
(0,2,0,0,2)(6,3,2,5,4,7,1), (0,2,0,1,0)(6,1,4,2,5,7,3),
(0,2,0,1,1)(6,2,4,1,5,7,3), (0,2,0,1,2)(6,3,2,1,5,7,4),
(0,2,0,2,0)(6,4,2,3,5,7,1), (0,2,0,2,1)(6,1,2,3,5,7,4),
(0,2,0,2,2)(6,3,1,5,4,7,2), (0,2,1,0,0)(6,3,5,2,1,7,4),
(0,2,1,0,1)(6,5,1,4,2,7,3), (0,2,1,0,2)(6,3,5,2,4,7,1),
(0,2,1,1,0)(6,1,5,4,2,7,3), (0,2,1,1,1)(6,2,5,1,3,7,4),
(0,2,1,1,2)(6,4,5,1,2,7,3), (0,2,1,2,0)(6,2,5,3,1,7,4),
(0,2,1,2,1)(6,5,1,3,2,7,4), (0,2,1,2,2)(6,3,5,1,4,7,2),
(0,2,2,0,0)(6,5,3,4,1,7,2), (0,2,2,0,1)(6,5,1,4,3,7,2),
(0,2,2,0,2)(6,5,3,2,4,7,1), (0,2,2,1,0)(6,4,2,1,3,7,5),
(0,2,2,1,1)(6,5,4,1,3,7,2), (0,2,2,1,2)(6,5,3,1,4,7,2),
(0,2,2,2,0)(6,5,4,3,1,7,2), (0,2,2,2,1)(6,5,4,3,2,7,1),
(0,2,2,2,2)(6,5,2,3,4,7,1), (1,0,0,0,0)(2,6,1,7,3,5,4),
(1,0,0,0,1)(1,6,3,7,2,5,4), (1,0,0,0,2)(3,6,2,7,1,4,5),
(1,0,0,1,0)(4,6,1,7,5,3,2), (1,0,0,1,1)(4,6,2,7,5,3,1),
(1,0,0,1,2)(1,6,2,7,5,3,4), (1,0,0,2,0)(4,6,1,7,5,2,3),
(1,0,0,2,1)(4,6,1,7,3,2,5), (1,0,0,2,2)(3,6,4,7,1,2,5),
(1,0,1,0,0)(2,6,5,7,4,1,3), (1,0,1,0,1)(2,6,3,7,1,4,5),
(1,0,1,0,2)(1,6,3,7,5,4,2), (1,0,1,1,0)(2,6,5,7,1,3,4),
(1,0,1,1,1)(4,6,5,7,2,3,1), (1,0,1,1,2)(1,6,2,7,4,3,5),
(1,0,1,2,0)(4,6,5,7,1,2,3), (1,0,1,2,1)(4,6,5,7,3,2,1),
(1,0,1,2,2)(1,6,5,7,4,3,2), (1,0,2,0,0)(2,6,4,7,3,1,5),
(1,0,2,0,1)(5,6,3,7,2,1,4), (1,0,2,0,2)(5,6,3,7,4,1,2),
(1,0,2,1,0)(2,6,4,7,5,1,3), (1,0,2,1,1)(2,6,4,7,5,3,1),
(1,0,2,1,2)(5,6,3,7,4,2,1), (1,0,2,2,0)(3,6,1,7,5,2,4),
(1,0,2,2,1)(1,6,5,7,3,2,4), (1,0,2,2,2)(5,6,1,7,4,2,3),
(1,1,0,0,0)(3,6,5,4,7,1,2), (1,1,0,0,1)(3,6,2,5,7,4,1),
(1,1,0,0,2)(3,6,5,2,7,4,1), (1,1,0,1,0)(4,6,1,2,7,3,5),
(1,1,0,1,1)(3,6,2,4,7,5,1), (1,1,0,1,2)(4,6,3,1,7,5,2),
(1,1,0,2,0)(4,6,1,2,7,5,3), (1,1,0,2,1)(4,6,1,3,7,5,2),
(1,1,0,2,2)(4,6,2,3,7,5,1), (1,1,1,0,0)(4,6,5,2,7,1,3),
(1,1,1,0,1)(5,6,2,4,7,1,3), (1,1,1,0,2)(4,6,3,5,7,1,2),
(1,1,1,1,0)(5,6,2,1,7,3,4), (1,1,1,1,1)(4,6,5,1,7,3,2),
(1,1,1,1,2)(3,6,4,1,7,5,2), (1,1,1,2,0)(4,6,5,3,7,1,2),
(1,1,1,2,1)(4,6,5,3,7,2,1), (1,1,1,2,2)(5,6,1,3,7,4,2),
(1,1,2,0,0)(5,6,3,2,7,1,4), (1,1,2,0,1)(5,6,3,4,7,1,2),
(1,1,2,0,2)(5,6,3,2,7,4,1), (1,1,2,1,0)(5,6,4,1,7,3,2),
(1,1,2,1,1)(5,6,3,4,7,2,1), (1,1,2,1,2)(5,6,4,1,7,2,3),
(1,1,2,2,0)(5,6,4,2,7,3,1), (1,1,2,2,1)(5,6,4,3,7,1,2),
(1,1,2,2,2)(5,6,4,3,7,2,1), (1,2,0,0,0)(3,6,5,4,1,7,2),
(1,2,0,0,1)(4,6,1,5,3,7,2), (1,2,0,0,2)(3,6,5,2,4,7,1),
(1,2,0,1,0)(4,6,1,2,5,7,3), (1,2,0,1,1)(4,6,2,1,5,7,3),
(1,2,0,1,2)(4,6,3,1,5,7,2), (1,2,0,2,0)(4,6,1,3,5,7,2),
(1,2,0,2,1)(4,6,2,3,5,7,1), (1,2,0,2,2)(5,6,1,3,4,7,2),
(1,2,1,0,0)(4,6,5,2,1,7,3), (1,2,1,0,1)(5,6,2,4,1,7,3),
(1,2,1,0,2)(4,6,3,5,1,7,2), (1,2,1,1,0)(5,6,2,1,3,7,4),
(1,2,1,1,1)(4,6,5,1,3,7,2), (1,2,1,1,2)(5,6,2,1,4,7,3),
(1,2,1,2,0)(4,6,5,3,1,7,2), (1,2,1,2,1)(4,6,5,3,2,7,1),
(1,2,1,2,2)(5,6,2,3,4,7,1), (1,2,2,0,0)(5,6,3,2,1,7,4),
(1,2,2,0,1)(5,6,3,4,1,7,2), (1,2,2,0,2)(5,6,3,2,4,7,1),
(1,2,2,1,0)(5,6,4,1,3,7,2), (1,2,2,1,1)(5,6,3,4,2,7,1),
(1,2,2,1,2)(5,6,4,1,2,7,3), (1,2,2,2,0)(5,6,4,2,3,7,1),
(1,2,2,2,1)(5,6,4,3,1,7,2), (1,2,2,2,2)(5,6,4,3,2,7,1),
(2,0,0,0,0)(2,1,6,7,3,5,4), (2,0,0,0,1)(1,5,6,7,3,4,2),
(2,0,0,0,2)(2,3,6,7,4,5,1), (2,0,0,1,0)(2,4,6,7,3,5,1),
(2,0,0,1,1)(4,2,6,7,5,3,1), (2,0,0,1,2)(3,1,6,7,2,4,5),
(2,0,0,2,0)(4,1,6,7,5,2,3), (2,0,0,2,1)(4,1,6,7,3,2,5),
(2,0,0,2,2)(3,1,6,7,5,4,2), (2,0,1,0,0)(3,2,6,7,4,1,5),
(2,0,1,0,1)(4,2,6,7,3,1,5), (2,0,1,0,2)(3,2,6,7,1,4,5),
(2,0,1,1,0)(2,5,6,7,1,3,4), (2,0,1,1,1)(4,5,6,7,2,3,1),
(2,0,1,1,2)(2,3,6,7,5,4,1), (2,0,1,2,0)(4,5,6,7,1,2,3),
(2,0,1,2,1)(4,5,6,7,3,2,1), (2,0,1,2,2)(3,1,6,7,4,2,5),
(2,0,2,0,0)(2,5,6,7,4,1,3), (2,0,2,0,1)(5,3,6,7,2,1,4),
(2,0,2,0,2)(5,3,6,7,4,1,2), (2,0,2,1,0)(3,4,6,7,2,1,5),
(2,0,2,1,1)(3,4,6,7,2,5,1), (2,0,2,1,2)(5,3,6,7,4,2,1),
(2,0,2,2,0)(3,4,6,7,5,1,2), (2,0,2,2,1)(3,4,6,7,5,2,1),
(2,0,2,2,2)(5,1,6,7,4,2,3), (2,1,0,0,0)(3,5,6,4,7,1,2),
(2,1,0,0,1)(4,1,6,5,7,3,2), (2,1,0,0,2)(3,5,6,2,7,4,1),
(2,1,0,1,0)(4,1,6,2,7,5,3), (2,1,0,1,1)(4,2,6,1,7,5,3),
(2,1,0,1,2)(4,3,6,1,7,5,2), (2,1,0,2,0)(4,1,6,3,7,5,2),
(2,1,0,2,1)(4,2,6,3,7,5,1), (2,1,0,2,2)(5,1,6,3,7,4,2),
(2,1,1,0,0)(4,5,6,2,7,1,3), (2,1,1,0,1)(5,2,6,4,7,1,3),
(2,1,1,0,2)(4,3,6,5,7,1,2), (2,1,1,1,0)(5,2,6,1,7,3,4),
(2,1,1,1,1)(4,5,6,1,7,3,2), (2,1,1,1,2)(5,2,6,1,7,4,3),
(2,1,1,2,0)(4,5,6,3,7,1,2), (2,1,1,2,1)(4,5,6,3,7,2,1),
(2,1,1,2,2)(5,2,6,3,7,4,1), (2,1,2,0,0)(5,3,6,2,7,1,4),
(2,1,2,0,1)(5,3,6,4,7,1,2), (2,1,2,0,2)(5,3,6,2,7,4,1),
(2,1,2,1,0)(5,4,6,1,7,3,2), (2,1,2,1,1)(5,3,6,4,7,2,1),
(2,1,2,1,2)(5,4,6,1,7,2,3), (2,1,2,2,0)(5,4,6,2,7,3,1),
(2,1,2,2,1)(5,4,6,3,7,1,2), (2,1,2,2,2)(5,4,6,3,7,2,1),
(2,2,0,0,0)(3,5,6,4,1,7,2), (2,2,0,0,1)(4,1,6,5,3,7,2),
(2,2,0,0,2)(3,5,6,2,4,7,1), (2,2,0,1,0)(4,1,6,2,5,7,3),
(2,2,0,1,1)(4,2,6,1,5,7,3), (2,2,0,1,2)(4,3,6,1,5,7,2),
(2,2,0,2,0)(4,1,6,3,5,7,2), (2,2,0,2,1)(4,2,6,3,5,7,1),
(2,2,0,2,2)(5,1,6,3,4,7,2), (2,2,1,0,0)(4,5,6,2,1,7,3),
(2,2,1,0,1)(5,2,6,4,1,7,3), (2,2,1,0,2)(4,3,6,5,1,7,2),
(2,2,1,1,0)(5,2,6,1,3,7,4), (2,2,1,1,1)(4,5,6,1,3,7,2),
(2,2,1,1,2)(5,2,6,1,4,7,3), (2,2,1,2,0)(4,5,6,3,1,7,2),
(2,2,1,2,1)(4,5,6,3,2,7,1), (2,2,1,2,2)(5,2,6,3,4,7,1),
(2,2,2,0,0)(5,3,6,2,1,7,4), (2,2,2,0,1)(5,3,6,4,1,7,2),
(2,2,2,0,2)(5,3,6,2,4,7,1), (2,2,2,1,0)(5,4,6,1,3,7,2),
(2,2,2,1,1)(5,3,6,4,2,7,1), (2,2,2,1,2)(5,4,6,1,2,7,3),
(2,2,2,2,0)(5,4,6,2,3,7,1), (2,2,2,2,1)(5,4,6,3,1,7,2),
(2,2,2,2,2)(5,4,6,3,2,7,1)
Listing of the elements x ∈ Z4
and the corresponding values ofH(x) ∈ S6.
(0,0,0,0)(1,2,3,4,5,6), (0,0,0,1)(1,2,3,6,4,5),
(0,0,0,2)(1,2,3,5,4,6), (0,0,1,0)(1,4,2,6,5,3),
(0,0,1,1)(1,4,2,3,6,5), (0,0,1,2)(1,4,2,5,6,3),
(0,0,2,0)(1,3,4,6,5,2), (0,0,2,1)(1,3,4,5,6,2),
(0,0,2,2)(1,3,4,2,6,5), (0,1,0,0)(1,5,3,4,6,2),
(0,1,0,1)(1,2,5,3,4,6), (0,1,0,2)(1,5,3,2,4,6),
(0,1,1,0)(1,5,2,4,6,3), (0,1,1,1)(1,5,2,3,4,6),
(0,1,1,2)(1,4,5,2,6,3), (0,1,2,0)(1,3,5,4,6,2),
(0,1,2,1)(1,5,4,3,6,2), (0,1,2,2)(1,5,4,2,6,3),
(0,2,0,0)(1,6,3,4,5,2), (0,2,0,1)(1,2,6,3,4,5),
(0,2,0,2)(1,6,3,2,4,5), (0,2,1,0)(1,6,2,4,5,3),
(0,2,1,1)(1,6,2,3,4,5), (0,2,1,2)(1,4,6,2,5,3),
(0,2,2,0)(1,3,6,4,5,2), (0,2,2,1)(1,6,4,3,5,2),
(0,2,2,2)(1,6,4,2,5,3), (1,0,0,0)(4,1,3,5,6,2),
(1,0,0,1)(4,1,3,6,5,2), (1,0,0,2)(4,1,3,2,6,5),
(1,0,1,0)(3,1,2,4,6,5), (1,0,1,1)(3,1,2,6,4,5),
(1,0,1,2)(3,1,2,5,4,6), (1,0,2,0)(2,1,4,5,6,3),
(1,0,2,1)(2,1,4,3,6,5), (1,0,2,2)(2,1,4,6,5,3),
(1,1,0,0)(6,1,3,4,5,2), (1,1,0,1)(4,1,5,3,6,2),
(1,1,0,2)(6,1,3,2,4,5), (1,1,1,0)(3,1,5,4,6,2),
(1,1,1,1)(6,1,5,3,4,2), (1,1,1,2)(6,1,5,2,4,3),
(1,1,2,0)(2,1,5,4,6,3), (1,1,2,1)(6,1,4,3,5,2),
(1,1,2,2)(6,1,4,2,5,3), (1,2,0,0)(5,1,3,4,6,2),
(1,2,0,1)(4,1,6,3,5,2), (1,2,0,2)(5,1,3,2,4,6),
(1,2,1,0)(5,1,2,4,6,3), (1,2,1,1)(5,1,6,3,4,2),
(1,2,1,2)(5,1,6,2,4,3), (1,2,2,0)(2,1,6,4,5,3),
(1,2,2,1)(5,1,4,3,6,2), (1,2,2,2)(5,1,4,2,6,3),
(2,0,0,0)(4,2,1,5,6,3), (2,0,0,1)(4,2,1,3,6,5),
(2,0,0,2)(4,2,1,6,5,3), (2,0,1,0)(3,4,1,5,6,2),
(2,0,1,1)(3,4,1,6,5,2), (2,0,1,2)(3,4,1,2,6,5),
(2,0,2,0)(2,3,1,4,6,5), (2,0,2,1)(2,3,1,6,4,5),
(2,0,2,2)(2,3,1,5,4,6), (2,1,0,0)(6,2,1,4,5,3),
(2,1,0,1)(6,2,1,3,4,5), (2,1,0,2)(4,5,1,2,6,3),
(2,1,1,0)(3,5,1,4,6,2), (2,1,1,1)(6,4,1,3,5,2),
(2,1,1,2)(6,5,1,2,4,3), (2,1,2,0)(6,3,1,4,5,2),
(2,1,2,1)(2,5,1,3,4,6), (2,1,2,2)(6,3,1,2,4,5),
(2,2,0,0)(5,2,1,4,6,3), (2,2,0,1)(5,2,1,3,4,6),
(2,2,0,2)(4,6,1,2,5,3), (2,2,1,0)(3,6,1,4,5,2),
(2,2,1,1)(5,4,1,3,6,2), (2,2,1,2)(5,6,1,2,4,3),
(2,2,2,0)(5,3,1,4,6,2), (2,2,2,1)(2,6,1,3,4,5),
(2,2,2,2)(5,3,1,2,4,6)
Listing of the elements x ∈ Z3
and the corresponding values of R(x) ∈ S5.
(0,0,0)(1,2,3,5,4), (0,0,1)(1,4,3,5,2), (0,0,2)(1,5,3,4,2),
(0,1,0)(1,2,4,5,3), (0,1,1)(1,4,2,5,3), (0,1,2)(1,5,4,3,2),
(0,2,0)(1,2,5,4,3), (0,2,1)(1,4,5,3,2), (0,2,2)(1,3,5,4,2),
(1,0,0)(4,1,3,5,2), (1,0,1)(5,1,3,4,2), (1,0,2)(2,1,3,5,4),
(1,1,0)(3,1,4,5,2), (1,1,1)(5,1,4,3,2), (1,1,2)(2,1,4,5,3),
(1,2,0)(4,1,5,3,2), (1,2,1)(5,1,2,4,3), (1,2,2)(2,1,5,4,3),
(2,0,0)(4,2,1,5,3), (2,0,1)(5,4,1,3,2), (2,0,2)(2,5,1,4,3),
(2,1,0)(3,2,1,5,4), (2,1,1)(3,4,1,5,2), (2,1,2)(3,5,1,4,2),
(2,2,0)(4,3,1,5,2), (2,2,1)(5,3,1,4,2), (2,2,2)(2,3,1,5,4)
Listing of the elements x ∈ Z3
and the corresponding values of S(x) ∈ S5.
(0,0,0)(2,1,3,4,5), (0,0,1)(2,4,3,1,5), (0,0,2)(2,5,3,1,4),
(0,1,0)(2,1,4,5,3), (0,1,1)(2,4,1,5,3), (0,1,2)(2,5,4,1,3),
(0,2,0)(2,1,5,4,3), (0,2,1)(2,4,5,1,3), (0,2,2)(2,3,5,1,4),
(1,0,0)(4,2,3,1,5), (1,0,1)(5,2,3,1,4), (1,0,2)(1,2,3,5,4),
(1,1,0)(3,2,4,1,5), (1,1,1)(5,2,4,1,3), (1,1,2)(1,2,4,5,3),
(1,2,0)(4,2,5,1,3), (1,2,1)(5,2,1,4,3), (1,2,2)(1,2,5,4,3),
(2,0,0)(4,1,2,5,3), (2,0,1)(5,4,2,1,3), (2,0,2)(1,5,2,4,3),
(2,1,0)(3,1,2,5,4), (2,1,1)(3,4,2,1,5), (2,1,2)(3,5,2,1,4),
(2,2,0)(4,3,2,1,5), (2,2,1)(5,3,2,1,4), (2,2,2)(1,3,2,5,4)
Listing of the elements x ∈ Z4
and the corresponding values of T (x) ∈ S6.
(0,0,0,0)(2,4,3,1,5,6), (0,0,0,1)(2,4,3,6,1,5),
(0,0,0,2)(2,4,3,5,1,6), (0,0,1,0)(2,1,4,6,5,3),
(0,0,1,1)(2,1,4,3,6,5), (0,0,1,2)(2,1,4,5,6,3),
(0,0,2,0)(2,3,1,6,5,4), (0,0,2,1)(2,3,1,5,6,4),
(0,0,2,2)(2,3,1,4,6,5), (0,1,0,0)(2,5,3,1,6,4),
(0,1,0,1)(2,4,5,3,1,6), (0,1,0,2)(2,5,3,4,1,6),
(0,1,1,0)(2,5,4,1,6,3), (0,1,1,1)(2,5,4,3,1,6),
(0,1,1,2)(2,1,5,4,6,3), (0,1,2,0)(2,3,5,1,6,4),
(0,1,2,1)(2,5,1,3,6,4), (0,1,2,2)(2,5,1,4,6,3),
(0,2,0,0)(2,6,3,1,5,4), (0,2,0,1)(2,4,6,3,1,5),
(0,2,0,2)(2,6,3,4,1,5), (0,2,1,0)(2,6,4,1,5,3),
(0,2,1,1)(2,6,4,3,1,5), (0,2,1,2)(2,1,6,4,5,3),
(0,2,2,0)(2,3,6,1,5,4), (0,2,2,1)(2,6,1,3,5,4),
(0,2,2,2)(2,6,1,4,5,3), (1,0,0,0)(1,2,3,5,6,4),
(1,0,0,1)(1,2,3,6,5,4), (1,0,0,2)(1,2,3,4,6,5),
(1,0,1,0)(3,2,4,1,6,5), (1,0,1,1)(3,2,4,6,1,5),
(1,0,1,2)(3,2,4,5,1,6), (1,0,2,0)(4,2,1,5,6,3),
(1,0,2,1)(4,2,1,3,6,5), (1,0,2,2)(4,2,1,6,5,3),
(1,1,0,0)(6,2,3,1,5,4), (1,1,0,1)(1,2,5,3,6,4),
(1,1,0,2)(6,2,3,4,1,5), (1,1,1,0)(3,2,5,1,6,4),
(1,1,1,1)(6,2,5,3,1,4), (1,1,1,2)(6,2,5,4,1,3),
(1,1,2,0)(4,2,5,1,6,3), (1,1,2,1)(6,2,1,3,5,4),
(1,1,2,2)(6,2,1,4,5,3), (1,2,0,0)(5,2,3,1,6,4),
(1,2,0,1)(1,2,6,3,5,4), (1,2,0,2)(5,2,3,4,1,6),
(1,2,1,0)(5,2,4,1,6,3), (1,2,1,1)(5,2,6,3,1,4),
(1,2,1,2)(5,2,6,4,1,3), (1,2,2,0)(4,2,6,1,5,3),
(1,2,2,1)(5,2,1,3,6,4), (1,2,2,2)(5,2,1,4,6,3),
(2,0,0,0)(1,4,2,5,6,3), (2,0,0,1)(1,4,2,3,6,5),
(2,0,0,2)(1,4,2,6,5,3), (2,0,1,0)(3,1,2,5,6,4),
(2,0,1,1)(3,1,2,6,5,4), (2,0,1,2)(3,1,2,4,6,5),
(2,0,2,0)(4,3,2,1,6,5), (2,0,2,1)(4,3,2,6,1,5),
(2,0,2,2)(4,3,2,5,1,6), (2,1,0,0)(6,4,2,1,5,3),
(2,1,0,1)(6,4,2,3,1,5), (2,1,0,2)(1,5,2,4,6,3),
(2,1,1,0)(3,5,2,1,6,4), (2,1,1,1)(6,1,2,3,5,4),
(2,1,1,2)(6,5,2,4,1,3), (2,1,2,0)(6,3,2,1,5,4),
(2,1,2,1)(4,5,2,3,1,6), (2,1,2,2)(6,3,2,4,1,5),
(2,2,0,0)(5,4,2,1,6,3), (2,2,0,1)(5,4,2,3,1,6),
(2,2,0,2)(1,6,2,4,5,3), (2,2,1,0)(3,6,2,1,5,4),
(2,2,1,1)(5,1,2,3,6,4), (2,2,1,2)(5,6,2,4,1,3),
(2,2,2,0)(5,3,2,1,6,4), (2,2,2,1)(4,6,2,3,1,5),
(2,2,2,2)(5,3,2,4,1,6)
	Introduction
	Notations and main results
	The general recursive construction.
	Proof of Theorem ??, second part
	Proof of Theorem ??, last part
