Constructing permutation arrays from groups

Abstract

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for $M(n,n-2)$ for all $n\equiv 2 \pmod 3$ such that $n+1$ is a prime power.

1 Introduction

Two permutations $\pi$ and $\sigma$ on n symbols have Hamming distance $hd(\pi ,\sigma )=d$ if, for exactly d distinct elements x, $\pi (x)\ne \sigma (x)$. The Hamming distance of a permutation array A (PA), denoted by hd(A), is the minimum $hd(\pi ,\sigma )$ for all permutations $\pi \ne \sigma$ in A. Arrays of permutations on n symbols and with Hamming distance at least d between any two permutations in the array have been used for error correcting codes in communication over very noisy power line channels [13, 19]. For positive integers n and d, with $d\le n$, denote by M(n, d) the maximum size of such an array. Constructing maximum size permutation arrays is difficult and, except for special cases of n and d, work has generally been limited to finding good upper and lower bounds. It is known that sharply k-transitive groups G of permutations on n symbols form a maximum size permutation array for pairwise Hamming distance $d=n-k+1$ [10]. Except for the exceptional case, i.e. 4- and 5-transitive Mathieu groups [4, 7, 8], sharply k-transitive permutation groups on n symbols are only known for $k=2$ and $k=3$ and for n a power of a prime and one more than a power of a prime, respectively, [18]. Furthermore, it is known that sharply k-transitive groups do not exist otherwise. Combinatorial arguments [5, 11, 24] are known, which give upper and lower bounds for M(n, d), for all n and d. There are also computational approaches that have been used to construct good permutation arrays for small values of n. Due to the growth rate of n!, computational approaches are limited to small values of n. The use of automorphism groups enables one to factor the set of all permutations into a smaller space and hence extend the range of computational processes [5, 14, 21]. It is also known that $M(n,n-1)\ge kn$, where k is the number of mutually orthogonal latin squares (MOLS) of order n [6], which means computing large collections of MOLS is related to searching for large permutation arrays. Other techniques that have been used include permutation polynomials [5], and special groups, such as the Mathieu groups $M_{22}$, $M_{23}$ and $M_{24}$ [4].

Let n be a positive integer and $Z_n=\{0,1,2,\dots ,n-1\}$. Let $S_n$ be the symmetric group on $Z_n$ with composition defined by $(\pi \sigma )(i) = \sigma (\pi (i))$. If G is a group, then $G\sigma =\{g\sigma ~|~g\in G\}$ and $\sigma G=\{\sigma g~|~g\in G\}$ are called a right coset of G and a left coset of G, respectively, with the representative $\sigma$ [12].

Our results, giving infinitely many improved lower bounds are obtained by describing collections of cosets of groups. For example, we use the affine general linear groups AGL(1, n) and the projective general groups PGL(2, n) (for prime powers n) that are sharply t-transitive for $t=2$ and $t=3$, respectively. It is well known that, every sharply t-transitive permutation group in $S_n$ has Hamming distance $n-t+1$ [3, 5, 10]. We show that groups $A\Gamma L(1,n=p^k)$ and $P\Gamma L(2,n=p^k)$, where p is prime, obtained from AGL(1, n) and PGL(2, n) by adding k Frobenius endomorphisms, both have pairwise Hamming distance $n-p^{k^*}$, where $k^*$ denotes the largest proper¹ factor of k. For example, $A\Gamma L(1,n=2^k)$, when k is prime, consists of $kn(n-1)$ permutations on n symbols and has pairwise Hamming distance $2^k-2$, so $M(n,n-2)\ge kn(n-1), P\Gamma L(2,n=2^k)$, when k is prime, consists of $k(n+1)n(n-1)$ permutations on $n+1$ symbols and has pairwise Hamming distance $2^k-2$, so $M(n+1,n-2) \ge k(n+1)n(n-1)$. We also show that the groups AGL(1, n) and PGL(2, n), where $n=p^k$, together with the coset defined by the single Frobenius endomorphism $f(x) = x^p$, has pairwise Hamming distance $n-p$.

Using a coset technique and computations involving random choices, we give several improved lower bounds for M(n, d), For example, we show that $M(13,5) \ge 6,639,048$ and $M(14,5) \ge 58,227,624$, which improve previous lower bounds.

2 New theoretical bounds

In this section we use group-theoretic techniques to obtain lower bounds on the sizes of permutation arrays with relatively large Hamming distance. First we consider permutation arrays obtained from semilinear groups over finite fields. Then we investigate a general procedure of modifying permutation arrays called contraction, and prove sharp Hamming distance bounds which involve the cycle structure of permutations in the permutation array.

Let $\mathbb {F}_n$ be a field of order n. Then $n=p^k$, where p is a prime number throughout the remainder of the paper. A polynomial $f(x)\in \mathbb {F}_n[x]$ is called a permutation polynomial if it is injective. In this case, f permutes the elements of $\mathbb {F}_n$.

We consider the affine general semilinear group $A\Gamma L(1,n)$ and the projective general semilinear group $P\Gamma L(2,n)$. These groups are described in the appendix. It is well known that, for any permutations $\tau ,\sigma ,\rho \in S_n$, $hd(\sigma \tau ,\sigma \rho )=hd(\tau ,\rho )$.

The following lemma shows that computing the Hamming distance of a group G does not require computing the Hamming distance between all the pairs of element in G. It shows that the computation time is O(|G|) rather than $O(|G|^2)$. For PA’s A and B, $hd(A,B)=\min \{ hd(\alpha ,\beta )~|~\alpha \in A, \beta \in B\}$. If A consists of one permutation $\alpha$ we use $hd(\alpha ,B)=hd(A,B)$.

Lemma 1

Let G be a group of permutations $G\subseteq S_n$ with $|G|>1$. The Hamming distance of G, i.e. hd(G), equals $hd(e,G\setminus \{e\})$, where e is the identity permutation.

Proof

Pick any two distinct permutations $a,b\in G$. Then, $hd(a,b)=hd(e,a^{-1}b)$. Since $a^{-1}b$ is in G and is not the identity, the result follows. $\square$

Lemma 2

Let G and H be subgroups of $S_n$, such that $G=\cup _{0\le i\le r} a_iH$, for some $r>0$, where $a_0=e$. Then,

$$\begin{aligned} hd(G)=\min (\{hd(a_i,H)~|~ 0<i\le r\},hd(e, H\setminus \{e\})). \end{aligned}$$

Proof

Observe that, since $G=\cup _{0\le i\le r} a_iH$, then $G=\cup _{0\le i\le r} H a_i^{-1}$. Indeed, if $g\in G$, then $g=a_ih$ for some $0\le i\le r$ and $h\in H$. Then $g^{-1}\in G$ and $g^{-1}=h^{-1}a_i^{-1}\in H a_i^{-1}$. So,

$$\begin{aligned} hd(G)&= \min (\{hd(e,a_iH)~|~ 0<i\le r\},hd(e, H\setminus \{e\}))\\&= \min (\{hd(e,H a_i^{-1})~|~ 0<i\le r\},hd(e, H\setminus \{e\})) \\&= \min (\{hd(a_i,H)~|~ 0<i\le r\},hd(e, H\setminus \{e\})). \end{aligned}$$

$\square$

Theorem 1

The Hamming distance of $A\Gamma L(1,n)$ is $n-p^{k^*}$, where $n=p^k$ and $k^*$ denotes the largest proper factor of k.

Before we give a proof of Theorem 1, we show some of its applications. Since $A\Gamma L(1,n)$ contains $kn(n-1)$ elements, we conclude the following.

Corollary 1

Let $n=p^k$ and let $k^*$ be the largest proper factor of $k\ge 1$. Then $M(n,n-p^{k^*})\ge kn(n-1)$. In particular,

$$\begin{aligned} M(n,n-2)\ge kn(n-1),\qquad n=2^k, \end{aligned}$$

where k is prime. For example, $M(2048,2046)\ge 11\cdot 2048\cdot 2047=46114816$.

Corollary 2

Let $n=p^k$ for any $k\ge 1$. Let s be the smallest prime factor of k. Then $M(n,n-p)\ge s\cdot n(n-1)$. For example,

$$\begin{aligned} M(16,14)&\ge 2\cdot 16\cdot 15=480\\ M(64,62)&\ge 2\cdot 64\cdot 63=8064\\ M(81,78)&\ge 2\cdot 81\cdot 80=12960\\ M(256,254)&\ge 2\cdot 256\cdot 255=130560\\ M(512,510)&\ge 3\cdot 512\cdot 511=784896. \end{aligned}$$

Using the following lemma, one can compute the Hamming distance simply by counting roots of polynomials.

For any polynomial f with coefficients over a finite field $\mathbb {F}_n$, let r(f) denote the number of roots of f in $\mathbb {F}_n$. If f and g are polynomials² that define permutations on $\mathbb {F}_n$, then the Hamming distance between the permutations f and g is equal to n minus the number of roots in the polynomial $f-g$, i.e. $hd(f,g) = n - r(f-g)$. This is easily seen by observing that $f(x) = g(x)$ is equivalent to $f(x)-g(x) = 0$; in other words, x is a root of the polynomial $f-g$.

Lemma 3

For any distinct polynomials $f,g\in \mathbb {F}_n[x]$ we have

$$\begin{aligned} hd(f,g) = n-r(f-g). \end{aligned}$$

The number of roots of polynomials of AGL(1, n) and Frobenius mappings is well known but we give a proof for completeness.

Proof of Theorem 1

Let $H=AGL(1,n)$. Since $A\Gamma L(1,n)=\cup _{0\le i<k} x^{p^i}H$ and $hd(H)=n-1$, by Lemma 2 it suffices to prove $hd(x^{p^i},H) \ge n-p^{k^*}$ for all $1\le i<k$. By Lemma 3, it suffices to prove $r(x^{p^i}+ax +b)\le p^{k^*}$ for any $1\le i<k$, and $a\ne 0, b\in \mathbb {F}_n$. Fix $a\ne 0,b\in \mathbb {F}_n$. We show that

$$\begin{aligned} r(t_{a,b}(x)) \le r(t_a(x)) \le r(t(x)), \end{aligned}$$

(1)

where $t_{a,b}(x)=x^{p^i}+ax+b, t_a(x)=x^{p^i}+ax$, and $t(x)=x^{p^i}- x$.

If $t_{a,b}(x)$ has no root in $\mathbb {F}_n$, then clearly $r(t_{a,b}(x)) \le r(t_a(x))$. Suppose that $t_{a,b}(x)$ has a root, say $y_0$. For any root y of $t_{a,b}(x)$, we have $t_a(y-y_0) = (y-y_0)^{p^i}+a(y-y_0) = y^{p^i} -y_0^{p^i} + ay - ay_0 = t_{a,b}(y)-t_{a,b}(y_0) = 0$, where the second equality follows from the property $(a+b)^p = a^p + b^p$ of Frobenius endomorphisms [4]. Thus, $y-y_0$ is a root of $t_a$. Since the mapping $y\rightarrow (y-y_0)$ is an injection, the first inequality of (1) follows.

We prove the second inequality of (1), by showing $r(s_a(x))\le r(s(x))$, where $s_a(x)=t_a(x)/x = x^{p^i-1}+a$, and $s(x)=t(x)/x = x^{p^i-1}-1$. Suppose that $a=0$. Then 0 is the only root of $s_a(x)$. Since s(x) also has the root 1, the inequality is trivially true. So, assume that $a\ne 0$. Then 0 is not a root of $s_a(x)$. We may also assume that $s_a(x)$ has at least one root; otherwise, the inequality is trivially true. Let $z_0$ be a root of $s_a(x)$. As z ranges over all roots of $s_a(x)$, map z to $z/z_0$. Observe that:

$$\begin{aligned} s\left( \frac{z}{z}_0\right) =\left( \frac{z}{z}_0\right) ^{p^i-1}-1= \frac{z^{p^i-1}}{z_0^{p^i-1}}-1=\frac{-a}{-a}-1=0. \end{aligned}$$

So, $z/z_0$ is a root of s(x). Since the map is injective, it follows that $r(t_a(x)) \le r(t(x))$.

Let S be the set of all roots of $t(x) = x^{p^i}- x$. Observe that S forms a finite field, since the set of roots are closed under the operations of addition, multiplication, and division. Thus, S is a subfield of $\mathbb {F}_n$, and hence the cardinality of S divides the cardinality of $\mathbb {F}_n$, which is $p^k$. So, $|S| = p^j$, for some j, where j | k. Now consider the extension of $t(x)=x^{p^i}- x$ into its splitting field [9, 16]. In this field, the expanded root set forms $\mathbb {F}_{p^i}$. So, S is a subfield of $\mathbb {F}_{p^i}$, and so j | i. Thus, j divides both i and k, i.e. $j = r(t(x))\le p^{gcd(i,k)}\le p^{k^*}$. $\square$

Theorem 2

The Hamming distance of $P\Gamma L(2,n)$ is $n-p^{k^*}$, where $k^*$ denotes the largest proper factor of k.

Proof

From the definition of $P\Gamma L(2,n)$ we have

$$\begin{aligned} f(x)= \left\{ \begin{array}{lll} \frac{ax^{p^i}+b}{cx^{p^i}+d} &{}\quad \text{ if } x\in \mathbb {F}_n \text{ and } cx^{p^i}+d\ne 0,\\ \infty &{}\quad \text{ if } x\in \mathbb {F}_n, cx^{p^i}+d=0 \text{ and } ax^{p^i}+b\ne 0,\\ a/c &{}\quad \text{ if } x=\infty \text{ and } c\ne 0,\\ \infty &{}\quad \text{ if } x=\infty ,c=0 \text{ and } a\ne 0. \end{array} \right. \end{aligned}$$

It follows that $S=\textsc {Stabilizer}_{P\Gamma L(2,n)}(\infty )$ is isomorphic to $A\Gamma L(1,n)$.³ So, $hd(S)=hd(A\Gamma L(1,n))=n-p^{k^*}$ by Theorem 1. Observe that $P\Gamma L(2,n)=\cup _{k=0}^{n-1} \pi _kS$, where $\pi _k$ ($1\le k<n$) is a permutation in $P\Gamma L(2,n)$ that maps k to $\infty$, and $\pi _0$ is the identity permutation. (Such permutations are in $P\Gamma L(2,n)$, because it is sharply 3-transitive and hence 2-transitive.) By Lemma 2,

$$\begin{aligned} hd(P\Gamma L(2,n))=\min (\{hd(\pi _i,S)~|~1\le i<n\},\{hd(e,S-\{e\})). \end{aligned}$$

As $hd(\pi _i,S)=hd(S)=hd(A\Gamma L(1,n))\ge n-p^{k^*}$, the result follows. $\square$

Since $P\Gamma L(2,n)$ contains $k(n+1)n(n-1)$ elements, we conclude the following.

Corollary 3

Let $n=p^k$ for any $k\ge 1$. Let $k^*$ be the largest proper factor of k. Then $M(n+1,n-p^{k^*})\ge k(n+1)n(n-1)$. In particular when $n=2^p$, we have $M(n+1,n-2)\ge p(n+1)n(n-1)$ and therefore

$$\begin{aligned} M(9,6)&\ge 3\cdot 9\cdot 8\cdot 7=1512\\ M(17,14)&\ge 2\cdot 17\cdot 16\cdot 15=8160\\ M(28,24)&\ge 3\cdot 28\cdot 27\cdot 26=58968\\ M(33,30)&\ge 5\cdot 33\cdot 32\cdot 31=163680. \end{aligned}$$

2.1 Contraction

In this section we describe a general method of modifying a permutation array called contraction. Contraction allows one to transfer a permutation array from $S_n$ to $S_{n-m}$ without affecting the Hamming distance by too much. First, we explain the idea of contraction for $m=1$.

The contraction of a permutation $\sigma$ on $S_n$, denoted by $\sigma ^{CT}$, is the permutation on $S_{n-1}$ defined by the following, where $0\le x\le n-2$:

$$\begin{aligned} \sigma ^{CT}(x) = {\left\{ \begin{array}{ll} \sigma (x) &{} \text{ if } \sigma (x)\ne n-1, \text{ and } \\ \sigma (n-1) &{} \text{ if } \sigma (x)=n-1. \end{array}\right. } \end{aligned}$$

(2)

That is, the contraction $\sigma ^{CT}$ of $\sigma$ is formed by substituting $\sigma (n-1)$ for $n-1$ and deleting the symbol $n-1$ altogether. For instance, if $\sigma (n-1)=n-1$, then $\sigma ^{CT}$ is formed by simply deleting the symbol $n-1$. For a PA A on $S_n$, let $A^{CT}=\{\sigma ^{CT}~|~\sigma \in A\}$. In general, as the contraction operation leaves most of any permutations values untouched, the Hamming distance of $A^{CT}$ (as we shall see) is at least as large as three less than the Hamming distance of A itself (see also [23]). Specifically, a decrease of three in the Hamming distance between two permutations $\rho$ and $\sigma$ occurs if and only if, for some integers $i,j<n-1$, and symbols $r,s<n-1$: (a) $\rho (i)=n-1$ and $\sigma (i)=r$, (b) $\rho (j)=s$ and $\sigma (j)=n-1$, and (c) $\rho (n-1)=r$ and $\sigma (n-1)=s$. This is illustrated in Fig. 1. It follows that there is a decrease of three in the Hamming distance between $\rho$ and $\sigma$ if and only if the permutation $\rho ^{-1}\sigma$ contains the cycle $(n-1\ r\ s)$ of length 3. If A is a group, since the order of a 3-cycle is three, the order of the group must be divisible by 3 (by Lagrange’s theorem [4]). So, if A is a group whose order is not divisible by 3, there can be no 3-cycle and, therefore, the contraction operation decreases the Hamming distance by at most 2.

Fig. 1

Illustration of contraction operation making two new agreements

Of course the contraction operation can be applied iteratively. One can first contract to a permutation on $S_{n-1}$, then $S_{n-2}$, then $S_{n-3}$, $\dots$ We investigate conditions on the group A that is contracted in order to understand the number of times successive contractions decrease the Hamming distance by 2.

Lemma 4

Let $\sigma$ and $\tau$ be two permutations in $S_n$. If $hd(\sigma ^{CT},\tau ^{CT})=hd(\sigma ,\tau )-2$ then (i) $n-1$ is in a cycle C of length at least two in the cycle decomposition of $\sigma ^{-1} \tau$, and (ii) the cycle decomposition of $(\sigma ^{CT})^{-1} \tau ^{CT}$ is the same except that the length of C is decreased by two by removing $n-1$ and either the next or the previous element in C.

Fig. 2

Two permutations where $hd(\sigma ^{CT},\tau ^{CT}) = hd(\sigma ,\tau )-2$ and $\sigma (n-1)=n-1$

Fig. 3

Two permutations where $hd(\sigma ^{CT},\tau ^{CT})=hd(\sigma ,\tau )-2$ and $\sigma (n-1)\ne n-1\ne \tau (n-1)$

Proof

(i) follows from the fact that, if $\sigma$ and $\tau$ have $n-1$ in the same position, then $hd(\sigma ^{CT},\tau ^{CT})=hd(\sigma ,\tau )$.

(ii) Consider Fig. 2. If one of the permutations, say $\sigma$, has $n-1$ in position $n-1$, then $\sigma (i)=\tau (n-1)$ where i is the position of $n-1$ in $\tau$ (because $hd(\sigma ^{CT},\tau ^{CT})=hd(\sigma ,\tau )-2$). Then $C=(\sigma (i)\ \ n-1)$ and it is deleted in the cycle decomposition of $(\sigma ^{CT})^{-1} \tau ^{CT}$.

Suppose that $\sigma (n-1)\ne n-1\ne \tau (n-1)$ as shown in Fig. 3.

Since $hd(\sigma ^{CT},\tau ^{CT})=hd(\sigma ,\tau )-2$, either $b=c$ or $a=d$. Then the cycle C containing $n-1$ is $(a\ n-1\ b\ d\dots )$ or $(b\ a\ n-1\ c\dots )$ respectively. The corresponding cycles in $(\sigma ^{CT})^{-1} \tau ^{CT}$ are $C-\{n-1,b\}$ and $C-\{a,n-1\}$. The lemma follows. $\square$

Theorem 3

Suppose a permutation array $P\subset S_n$ has Hamming distance d. Let $Q\subseteq S_{n-2}$ denote the permutation array obtained from P by applying the contraction operation two times.

• (a) The Hamming distance of Q is at least $d-6$.

• (b) Suppose, for any $\sigma ,\tau \in P$, the cycle decomposition of $\sigma ^{-1} \tau$ contains no 3-cycle and no 5-cycle. Then the Hamming distance of Q is at least $d-4$.

Proof

The part (a) follows form the fact that the Hamming distance decreases by at most three for each contraction operation.

We prove part (b). Suppose to the contrary that $hd(Q)\le d-5$. Let $\sigma$ and $\tau$ be two permutations of P such that $hd(\sigma '',\tau '')\le d-5$ where $\sigma ''=(\sigma ')^{CT},\tau ''=(\tau ')^{CT}$ and $\sigma '=\sigma ^{CT},\tau '=\tau ^{CT}$. Since $\sigma ^{-1} \tau$ contains no 3-cycle, $hd(\sigma ',\tau ')= d-2$. Then the contraction operation on $\sigma '$ and $\tau '$ decreases the Hamming distance by exactly three. Therefore $(\sigma ')^{-1} \tau '$ contains a 3-cycle as shown in Fig. 4.

Fig. 4

Two permutations where $(\sigma ')^{-1} \tau '$ contains a 3-cycle

Since $\sigma ^{-1} \tau$ contains no 3-cycle and $hd(\sigma ',\tau ')=d-2$, by Lemma 4, $\sigma ^{-1} \tau$ contains a 5-cycle. This is a contradiction. $\square$

Corollary 4

(Contraction of AGL(1, n))

• (i) For each prime power n such that $3 \not \mid (n-1)$,

  $$\begin{aligned} M(n-1,n-3)\ge n(n-1). \end{aligned}$$

• (ii) For each prime power n such that $n \equiv 2\pmod 3$ and $n \not \equiv 0,1\pmod 5$,

  $$\begin{aligned} M(n-2,n-5)\ge n(n-1). \end{aligned}$$

Proof

The bounds can be obtained by applying the contraction operation on the affine general linear group AGL(1, n). Let $\sigma$ and $\tau$ be any two distinct permutations from AGL(1, n). Suppose that $n \equiv 2\pmod 3$. Since $\sigma ^{-1}\tau \in AGL(1,n)$ and the order of AGL(1, n) is not a multiple of 3, the bound of (i) follows. If $n \equiv 0 \pmod 3$, then suppose $\sigma$ and $\tau$ are such that $hd(\sigma ,\tau )=n$. If $hd(\sigma ^{CT},\tau ^{CT})=hd(\sigma ,\tau )-3$, then $hd(\sigma ^{CT},\tau ^{CT})\ge n-3$ and the Hamming distance bound for (i) is satisfied. Since $hd(AGL(1,n))\ge n-1$, the other case is that $\sigma$ and $\tau$ are such that $hd(\sigma ,\tau )=n-1$. In this case $\sigma$ and $\tau$ have one agreement, say at position i. Then $\sigma \tau ^{-1}\in \textsc {Stabilizer}_i(AGL(1,n))$, which is a cyclic group C of order $n-1$. If $3 \not \mid (n-1)$, then there can be no 3-cycle in C and, hence, $(\sigma \tau ^{-1})^{-1}=\tau \sigma ^{-1}$ has no 3-cycle. So, $hd(\sigma ^{CT},\tau ^{CT})=hd(\tau ^{CT},\sigma ^{CT})\ge hd(\sigma ,\tau )-2$. It follows that $hd(\sigma ^{CT},\tau ^{CT})\ge n-3$.

The bound of (ii) follows from Theorem 3(b) and the fact that the order of AGL(1, n) is not a multiple of 3 and 5. $\square$

Infinitely many new bounds can be obtained from Corollary 4. We show some examples.

$$\begin{aligned} M(31,29)&\ge 32\cdot 31=992 \quad \text {for }n=32,\\ M(40,38)&\ge 41\cdot 40=1640 \quad \text {for }n=41,\\ M(46,44)&\ge 47\cdot 46=2162 \quad \text {for }n=47. \end{aligned}$$

Previously, the best lower bounds for these examples were

• $M(31,29)\ge 930$, which was derived from $|AGL(1,31)|\ge 930$ and $M(n,d-1)\ge M(n,d)$ [5],

• $M(40,38)\ge 280$, since $M(40,39)\ge 280$, as there are 7 MOLS for $n=40$ [6],

• $M(46,44)\ge 270$, since $M(46,45)\ge 270$, as there are 6 MOLS for $n=35$ [6],

Theorem 4

For each prime power q such that $3 \not \mid (q-1)$,

$$\begin{aligned} M(q,q-3)\ge (q+1)q(q-1). \end{aligned}$$

Proof

Let $A_q=(PGL(2,q+1))^{CT}$. It suffices to show that $hd(A_q)\ge q-3$. Consider two permutations $\sigma$ and $\tau$ from $PGL(2,q+1)$. If $hd(\sigma ,\tau )=q+1$ then $hd(\sigma ^{CT},\tau ^{CT})\ge q-2$. Suppose that $hd(\sigma ,\tau )\le q$. Then $\sigma ^{-1}\tau$ has a fixed point k. A point stabilizer of PGL(2, n) is isomorphic to the affine general linear group AGL(1, q). Since $3 \not \mid (q-1)$, by Corollary 4, $hd(\sigma ^{CT},\tau ^{CT})\ge q-3$ and the claim follows. $\square$

Examples

• (1) $M(32,29)\ge 32736$, since $M(33,31)\ge 32736$, using $PGL(2,2^5)$.

• (2) $M(29,26)\ge 24360$, since $M(30,28)\ge 24360$, using PGL(2, 29).

• (3) $M(41,38)\ge 68880$, since $M(42,40)\ge 68880$, using PGL(2, 41).

Previously, the best lower bounds for these examples were

• (1) $M(32,29)\ge 29760$, since $M(32,30)\ge 29760$, using PGL(2, 31).

• (2) $M(29,26)\ge 19656$, since $M(28,26)\ge 19656$, using $PGL(2,3^3)$.

• (3) $M(41,38)\ge 1640$, since $M(41,40)\ge 1640$, using AGL(1, 41).

The following is an improvement on Corollary 4.

Corollary 5

For each prime power n such that $3 \not \mid (n-1)$,

$$\begin{aligned} M(n-1,n-3)\ge n^2-1. \end{aligned}$$

Proof

By Theorem 4, $M(n,n-3)\ge (n+1)n(n-1)$. By the combinatorial theorem [5] for all d, $M(n-1,d)\ge M(n,d)/n$. So, $M(n-1,n-3)\ge (n+1)n(n-1)/n=n^2-1$. $\square$

Examples.

• (1) $M(31,29)\ge 1056$,

• (2) $M(40,28)\ge 1680$, and

• (3) $M(46,44)\ge 2208$.

3 Experimental results

Computer searches for arrays of permutations on $Z_n$ with pairwise Hamming distance d are difficult. The number of all permutations, namely n!, is large, even for small values of n. Many previous search methods have used automorphism groups to factor the space of all permutations into collections of sets of permutations with considerably smaller cardinality [5, 14, 21]. With this smaller cardinality, one constructs a graph G(n, d), whose nodes correspond to sets of permutations, with an edge between two sets $S_1$ and $S_2$ if the Hamming distance between permutations in the sets is at least d [5, 14, 21]. One then uses a program to find a large clique in G(n, d).

We give a different type of algorithm. We call it the coset method. We start with a group G that forms a good PA for $M(n,d')$, where $d'>d$. As exact values for $M(q,q-1)$ arise from sharply 2-transitive groups AGL(1, q), and exact values of $M(q+1,q-1)$ arise from sharply 3-transitive groups PGL(2, q), where q is a power of a prime, one easily finds a group with which to start. Also, the exact value of M(n, n), for all n, arises from a cyclic group of order n. So, in fact, there is always a group with which to start. We search for a permutation, say $\pi$, at Hamming distance at least d from G. It follows that the entire coset $\pi G$ is at distance at least d from G. That is,

$$\begin{aligned} hd(\pi G,G)&=\max \{ hd(\pi g_1,g_2)~|~g_1,g_2\in G\}\\&= \max \{hd(\pi ,g_2g_1^{-1}~|~g_1,g_2\in G\}\\&=\max \{hd(\pi ,g)~|~g\in G\}, \end{aligned}$$

since $g_2g_1^{-1}\in G$ by properties of a group. So, one has a PA of cardinality $2\cdot |G|$, by finding a single permutation $\pi$. Moreover, recording the coset representative $\pi$ is sufficient, as all other permutations in the coset are obtained from the group G and $\pi$.

The process can be iterated. Suppose we have found k coset representatives $\pi _0,\pi _1,\dots ,\pi _{k-1}$, where $\pi _0$ is the identity permutation, so $\pi _0 G$ is the group G and the collection of all such cosets is a PA of cardinality $k\cdot |G|$. One can continue by finding a permutation $\pi _k$ such that $hd(\pi _k,\pi _iG)\ge d$, for all $0\le i<k$. Such a permutation gives us a new coset, namely $\pi _k G$, and a PA of cardinality $(k+1)\cdot |G|$.

One implementation of this method guesses a new permutation $\pi _k$ randomly and then checks (1) that $hd(\pi _k,\pi _iG)\ge d$, for all $0\le i<k$, and (2) $hd(\pi _k,\pi _iG)=d$, for some i ($0\le i<k$). The second condition may need explanation. Recall the combinatorial Gilbert-Varshimov (GV) lower bound [10, 17, 20] for M(n, d), namely $N_{GV}(n,d)$, where $N_{GV}(n,d)$ is given by:

$$\begin{aligned} N_{GV}(n,d)=\frac{n!}{V(n,d-1)}, \end{aligned}$$

(3)

where $V(n,d-1)$, the number of permutations that are at distance less than d from a given permutation, e.g. the identity, is $V(n,d-1)=\sum _{k=0}^{d-1}{n\atopwithdelims ()k} D_k$, where $D_k$ is the number of derangements on k symbols. Note that the ratio given in (3) is a lower bound for the number of times one can select another permutation without choosing two with Hamming distance less than d. It is calculated with the assumption that all sets of permutations too close to different permutations are disjoint. (It should be noted that one can often get far more than $N_{GV}(n,d)$ permutations in a PA, because the assumption that the spheres are disjoint is not required. In fact, this combinatorial lower bound has recently been improved, see [11] and [24].) Of course, such sets need not be disjoint and one can choose a larger set of permutations by eliminating this condition. We do this by requiring each new permutation selected is at distance exactly d to one chosen before.

This simple technique makes it feasible to compute and verify large PA’s. Previously, the implicit algorithm justifying the GV lower bound was not considered practical, due to large space requirements for keeping track of permutations already chosen and the large time needed for computing Hamming distances. As we have seen in Lemma 1, when the PA is a group and some of its cosets, one need not check the distance between every pair of permutations and one can store the set of coset representatives instead of the set of all permutations. It is worth noting that in [5], the authors computed a PA of size 58,322 for M(16, 9) and stated that this lower bound is not as good as what is given by the GV lower bound.⁴ They stated, “$\ldots$ However, the GV lower bound is not constructive.” On the other hand, the coset method starting with the group $G=AGL(1,16)$ found 5, 739 cosets of G for Hamming distance 9 and, hence, obtained a lower bound of 1, 377, 360 for M(16, 9).

Also, in [21] the authors computed a PA of size 20, 908, 800 for M(12, 4) and then stated “$\ldots$ it is too large to check fully, but has been extensively checked.” In contrast, the coset method starting with the Mathieu group G of order 12 [4, 7, 8] found 638 cosets of G for Hamming distance 4 and, hence, obtained a lower bound of 60, 635, 520 for M(12, 4). Furthermore, since testing of correctness of G and its cosets takes far less time using group-theoretic properties, verification was done in a few minutes using a computer.

Verifying the Hamming distance of a PA A on $Z_n$ of size N generally involves computing ${N\atopwithdelims ()2}$ pairs of permutations of n symbols, which is $O(N^2n)$ time. When A is a group, using Lemma 1, one only need compute the distance between the identity and the other $N-1$ elements, so O(Nn) time. In fact, if A is a group consisting of the identity permutation and its cyclic shifts or A consists of this cyclic group and, say, k of its cosets, the computation time is reduced to O(N) and O(kN), respectively. We discuss testing algorithms in Sect. 3.1.

The coset method has been used to obtain several new lower bounds. Many of the new lower bounds are given in Tables 1 and 2. The PA’s that justify the lower bounds are available at our web site [22]. Sometimes finding a suitable coset representative takes considerable computation time and, hence, when found it should be recorded. For example, when started with the group $G=PGL(2,19)$ the coset method with difficulty found one coset of G for Hamming distance 16. It can be described by one of its representatives, for example:

$$\begin{aligned} 0,1,2,3,5,7,14,4,18,17,9,6,16,15,11,19,8,10,12,13, \end{aligned}$$

where 19 represents $\infty$. Thus, $M(20,16) \ge 13,680$. Some other lower bounds obtained are:

$$\begin{aligned} M(13,5)\ge & {} 10,454,400\\ M(13,6)\ge & {} 1,805,760\\ M(13,7)\ge & {} 380,160\\ M(14,5)\ge & {} 60,445,440\\ M(14,6)\ge & {} 10,834,560\\ M(14,7)\ge & {} 1,900,800\\ M(14,8)\ge & {} 380,160\\ M(14,9)\ge & {} 21,840\\ M(15,6)\ge & {} 58,734,720\\ M(15,7)\ge & {} 15,491,520\\ M(15,8)\ge & {} 1,900,800\\ M(15,9)\ge & {} 181,272\\ M(15,10)\ge & {} 32,760\\ M(16,7)\ge & {} 70,709,760\\ M(16,8)\ge & {} 16,061,760\\ M(16,9)\ge & {} 1,377,360\\ M(16,10)\ge & {} 164,880. \end{aligned}$$

Others can be found in Tables 1 and 2 and at the website.

Table 1 Bounds for M(n, d) for $9\le n\le 17$

Table 2 Bounds for M(n, d) for $18\le n\le 26$

3.1 Efficient testing of a new permutation

Suppose that we have a permutation array P consisting of k left cosets of a group G, i.e. $P=\cup _{i=1}^k P_i$. The critical step of our randomized construction is the computation of distance $hd(\pi ,P)$ where $\pi$ is a random permutation. The definition of Hamming distance suggests the computation $hd(\pi ,P)=\min _{\sigma \in P} hd(\pi ,\sigma )$. Then the running time is $O(n|P|)=O(nk|G|)$. We show that, if G is cyclic or has the cyclic subgroup, the algorithm for testing $\pi$ can be improved. Let $C_n$ denote the cyclic group, i.e.,

$$\begin{aligned} C_n=\{g_j~|~g_j=(j,j+1,\dots ,n-1,0,1,\dots ,j-1), j\in Z_n\}. \end{aligned}$$

Lemma 5

The Hamming distance from a permutation $\pi \in S_n$ to $C_n$ can be computed in O(n) time.

Proof

The Hamming distance $hd(\pi ,C_n)$ can be computed as

$$\begin{aligned} hd(\pi ,C_n)=\min _{0\le j\le n-1}\{hd(\pi ,g_j)\}. \end{aligned}$$

The straightforward computation of $hd(\pi ,g_j)$ takes O(n) time. We show that it can be computed in O(1) amortized time.

Let $D[0..n-1]$ be an array and we store a tentative distance of $hd(\pi ,g_j)$ in D[j]. The algorithm has 2 steps.

• 1. We initialize $D[j]=n$ for all $j\in Z_n$.

• 2. For each $m\in Z_n$, subtract one from D[j] where $j\equiv (\pi (m)-m)\bmod {n}$.

Clearly, the running time is O(n). We show that the algorithm is correct. If D[j] decreases for some m, then the m-th element of $\pi$ is $j+m(\bmod \ n)$. Thus, $\pi$ and $g_j$ have matching elements in m-th position. In the end, D[j] is equal to $n-n'$ where $n'$ is the number of matching elements of $\pi$ and $g_j$. The claim follows since $hd(\pi ,g_j)=n-n'$. $\square$

Lemma 6

Suppose that $G=C_n$ and let $\pi _i, (i=1,2,\dots ,k)$ be a representative of the coset $P_i$, i.e. $P_i=\pi _iC_n$. Then, for any permutation $\pi \in S_n$, the Hamming distance $hd(\pi ,P)$ can be computed in O(kn) time.

Proof

The Hamming distance $hd(\pi ,P)$ can be computed as

$$\begin{aligned} hd(\pi ,P)=hd\left( \pi ,\mathop \cup _{1\le i\le k}P_i \right) = \min _{1\le i\le k} \{hd(\pi ,P_i\}. \end{aligned}$$

It suffices to show that $d_i=hd(\pi ,P_i)$ can be computed in O(n) time, for any i. Since $P_i=\pi _iC_n$ and $d_i=hd(\pi _i^{-1}\pi , C_n)$, we first compute $\sigma =\pi _i^{-1}\pi$ and then $hd(\sigma ,C_n)$ using the algorithm from Lemma 5. $\square$

We generalize Lemma 6 as follows.

Theorem 5

If $C_n$ is a subgroup of G then the Hamming distance $hd(\pi ,P)$ can be computed in O(k|G|) time for any permutation $\pi \in S_n$.

Proof

Let $G/C_n=\{\sigma C_n~|~\sigma \in G\}$ be the set of left cosets of $C_n$ in G. Let $\sigma _1,\sigma _2,\dots ,\sigma _m$ be representatives of these cosets. The Hamming distance $hd(\pi ,P)$ can be computed as

$$\begin{aligned} hd(\pi ,P)= & {} hd\left( \pi ,\mathop \bigcup _{1\le i\le k}\pi _iG \right) = hd\left( \pi ,\mathop \bigcup _{\begin{array}{c} 1\le i\le k\\ 1\le t\le m \end{array}}\pi _i\sigma _tC_n\right) \\= & {} \min _{\begin{array}{c} 1\le i\le k\\ 1\le t\le m \end{array}} \{hd(\pi ,\pi _i\sigma _tC_n)\}. \end{aligned}$$

Since $hd(\pi ,\pi _i\sigma _tC_n)=hd(\alpha ,C_n)$ where $\alpha =(\pi _i\sigma _t)^{-1}\pi$. The Hamming distance $hd(\alpha ,C_n)$ can be computed in O(n) time using the algorithm from Lemma 5. The total time for computing $hd(\pi ,P)$ is O(kmn). It can be written as O(k|G|) since $|G|=mn$. $\square$

4 New tables and conclusions

We give in Tables 1 and 2 an updated partial list of lower bounds for M(n, d), with $n\ge 9$ and $d\ge 4$. We also created a webpage [22] that allows one to obtain the PA’s, or coded versions of them, for verification. Not all of our new results appear in the table, many are described by theorems in Sect. 2.

We use the following notation in the table to describe how the results are obtained:

a :

- a bound derived from $M(n,d-1)\ge M(n,d)$.

b :

- a bound derived from $M(n+1,d)\ge M(n,d)$.

d :

- a bound derived from $M(n-1,d)\ge M(n,d)/n$. For example, we have $M(15,12)\ge 2520$, because $M(16,12)\ge 40320$.

t :

- the Gilbert-Varshamov lower bound [10, 17, 20].

g :

- a lower bound based on known permutation groups. This includes the Mathieu groups $M_{11}, M_{12},M_{22},M_{23},M_{24}$ and groups AGL(1, n) or AGL(2, n), which are sharply 2-transitive and sharply 3-transitive, respectively.

m :

- a bound derived from mutually orthogonal Latin squares [6].

u :

- a result obtained by partitioning and extending, which is contained in [2].

r :

- a result obtained by the coset method using random search. Our improved lower bounds are in bold. The previous lower bounds are given at the bottom of the cell. When a lower bound is obtained by the coset technique, the number of cosets is given at the top of the cell.

c :

- a result obtained by contraction, which is an improvement of the $M(n-1,d-3)\ge M(n,d)$ result, described in [23]. For example, $M(23,20)\ge 12144$ comes from $M(24,22)\ge 12144$.

We use capital letters for the following references: A - [5], B - [11], C - [14], D - [15], E - [21], F - [23], G - [1].

We note that $M(9,6)\ge 1512$ and $M(17,14)\ge 8160$ follow from Corollaries 1 and 2.

Appendix

Finite Fields Let $n=p^k$ be a prime power. There is a field $\mathbb {F}_n$ with n elements, unique up to isomorphism. We consider groups over the field $\mathbb {F}_n$.

Groups The group AGL(1, n) consists of the affine linear transformations

$$\begin{aligned} AGL(1,n) = \{ax + b | a,b\in \mathbb {F}_n, a\not =0\}, \end{aligned}$$

where the group operation is function composition. This group is sharply $2-$transitive and has $n(n-1)$ elements.

Denote the symbols of $Z_{n+1}$ by $0,1,2,\dots ,n-1,\infty$. The permutations of PGL(2, n) are $g:x\rightarrow \frac{ax+b}{cx+d}$ on $Z_{n+1}$ such that $a,b,c,d\in GF(n), ad\ne bc, g(\infty )=a/c,g(-d/c)=\infty$ if $c\ne 0$ and $g(\infty )=\infty$ if $c=0$. Then $|PGL(2,n)|=(n+1)n(n-1)$.

Recall that $n=p^k$. The group of affine semilinear polynomials $A\Gamma L(1,n)$ arises as a semidirect product of AGL(1, n) with a cyclic group of order k. It is generated by iteratively composing the Frobenius automorphism $x^p$ with the elements of AGL(1, n). Equivalently,

$$\begin{aligned} A\Gamma L(1,n) = \{ax^{p^i}+b \mid a,b\in \mathbb {F}_n, a\not =0, 0\le i < k\} \end{aligned}$$

This group has $kn(n-1)$ elements.

The group of projective semilinear polynomials $P\Gamma L(2,n)$ arises as a semidirect product of PGL(2, n) with a cyclic group of order k generated by the Frobenius automorphism. This group has $k(n+1)n(n-1)$ elements.