Extending permutation arrays: improving MOLS bounds

Abstract

A permutation array (PA) A is a set of permutations on $Z_n=\{0,1,\dots ,n-1\}$, for some n. A PA A has pairwise Hamming distance at least d, if for every pair of permutations $\sigma$ and $\tau$ in A, there are at least d integers i in $Z_n$ such that $\sigma (i)\ne \tau (i)$. Let M(n, d) denote the maximum number of permutations in any PA with pairwise Hamming distance at least d. Recently considerable effort has been devoted to improving known lower bounds for M(n, d) for all $n>d>3$. We give a partition and extension operation that enables the production of a new PA $A'$ for $M(n+1,d)$ from an existing PA A for $M(n,d-1)$. In particular, this operation allows for improvements for PA’s for $M(q+1,q)$ for powers of prime numbers q, as well as for many other choices of n and d, where n is not a power of a prime. Finally, for prime numbers p, the partition and extension technique provides an asymptotically better lower bound for $M(p+1,p)$ than that given by current knowledge about mutually orthogonal Latin squares. We prove a new asymptotic lower bound for the set of primes p, namely, $M(p+1,p)\ge p^{1.5}/2-O(p)$.

1 Introduction

A permutation array (PA) A is a set of permutations on $Z_n=\{0,1,\dots ,n-1\}$, for some n. Permutations $\sigma$ and $\tau$ on $Z_n$ have Hamming distance d, denoted by $hd(\sigma ,\tau )$, if there are exactly d integers i in $Z_n$ such that $\sigma (i)\ne \tau (i)$. When $\sigma (i)=\tau (i)$, we say that $\sigma$ and $\tau$ agree at position i. The number of agreements between $\sigma$ and $\tau$ is $n-hd(\sigma ,\tau )$. The Hamming distance between two PA’s A and B on $Z_n$, denoted by hd(A, B), is the smallest Hamming distance between permutations $\sigma \in A$ and $\tau \in B$. The Hamming distance of a PA A on $Z_n$, denoted by hd(A), is the smallest Hamming distance between two permutations $\sigma \ne \tau$ in A. If $hd(A)=d$, then A is an (n, d)-PA. Let M(n, d) denote the maximum number of permutations on $Z_n$ in any (n, d)-PA. Recently considerable effort has been devoted to improving known lower bounds for M(n, d), for all $n>d>3$ [4, 6, 7, 9, 10, 12–14, 20]. Large permutation arrays are valuable in creating better error correcting permutation codes, which have application in the transmission of information over very noisy channels, such as power lines [11, 17]. It is known that, if q is either prime or a power of a prime, then $M(q,q-1)=q(q-1)$ and $M(q+1,q-1)=(q+1)q(q-1)$ [8, 18]. More generally, if there is a sharply k-transitive group of order n consisting of N permutations, then $M(n,n-k+1)\ge N$ [8, 16]. It is also known that, for any positive integer n, if there are k mutually orthogonal Latin squares of side n, then $M(n,n-1)\ge kn$ [6]. There are known combinatorial lower bounds and upper bounds for M(n, d) [8, 9]. Several papers give both computational and combinatorial techniques for improved lower bounds on M(n, d) [4, 6, 13, 20]. It is known [4], for any permutations $\sigma ,\tau$ and $\rho$, that $hd(\sigma ,\tau )=hd(\rho \sigma ,\rho \tau )$, where multiplication denotes the composition of functions. So, for any group G of permutations on n symbols, $hd(G)=hd(\rho G)$, where $\rho$ is any permutation on n symbols and $\rho G$ is the so-called left coset of G, which is obtained by function composition of the permutation $\rho$ with every permutation in G.

We present a partition and extension operation that produces a new $(n+1,d)$-PA from an existing $(n,d-1)$-PA. In Sect. 2 we give a detailed description of the operation. In Sect. 3 we apply the partition and extension operation and create several PAs improving known lower bounds for $M(n+1,d)$. In Sect. 4, we prove a new asymptotic lower bound for the set of primes p, namely, $M(p+1,p)\ge p^{1.5}/2-O(p)$.

2 The partition and extension technique

A rudimentary form of extension was described in [15]. Basically, the operation was specified for a group G of permutations on $Z_n$, for some n, and a left coset $\rho G$, where $\rho$ is a permutation not in G. For some integer d, let $hd(G)=d$ and $hd(G,\rho G)=d-1$. One constructs by extension a set of permutations $G'=\{ \sigma '~|~ \sigma \in G\} \cup \{ \tau ''~|~ \tau \in \rho G \}$ on the symbols of $Z_{n+1}=\{0,1\dots ,n\}$, where:

• (1) $\sigma '(i)=\sigma (i)$, for all $i<n$, and $\sigma '(n)=n$, and

• (2) $\tau ''(i)=\tau (i)$, for all i ($0<i<n$), $\tau ''(0)=n$, and $\tau ''(n)=\tau (0)$.

It was shown in [15] that $G'$ is a PA on $n+1$ symbols with Hamming distance d. That is, from the PA $G\cup \rho G$ for $M(n,d-1)$, one extends to a PA $G'$ for $M(n+1,d)$ which has 2|G| permutations.

We describe a new richer form of extension, which we call partition and extension, that enables the construction of PA’s for $M(n+1,d)$ with considerably more than 2|G| permutations from PA’s for $M(n,d-1)$. The necessary property to achieve the stated Hamming distance via partition and extension is to have sets of permutations, say $M_1,M_2,\dots ,M_k$, for some k, such that each set has (intra) Hamming distance say d, at least one greater than the (inter) Hamming distance between pairs of sets. When this is true, one can modify the sets by replacing different symbols in different positions in each permutation of $M_1,M_2,\dots ,M_k$ with the symbol n and moving the replaced symbol, in each case, to the end of the permutation. In addition, for one of the sets, one can simply put the symbol n at the end of each permutation. Because the common new symbol may be positioned in the same location in each set, there will be one more position with identical symbols within them. Since the number of symbols also increases by one, the (intra) Hamming distance remains the same. On the other hand, since the positions of the replaced symbols and the replaced symbols themselves are different in different sets, the (inter) Hamming distance increases by one. So, the intra-distance of d remains d and the inter-distance of $d-1$ increases to d. In the case of rudimentary extension there are two sets, in one set the replacement always happens in the first position, but can involve any one of the original symbols, and in the second set the new symbol is placed at the end of each permutation. Clearly one can generalize, as we do now.

Let s be a positive integer, $M_1, M_2, \dots , M_s$ be an ordered list of s pairwise disjoint sets of permutations on $Z_n$, and let $\mathcal{P}=(P_1, P_2, \dots , P_s )$ and $\mathcal{Q}=(Q_1, Q_2, \dots , Q_s )$ be two ordered lists of subsets of $Z_n$ such that the sets in $\mathcal{P}$ and $\mathcal{Q}$ are partitions of $Z_n$. Each set $P_i$ is the set of locations for replacing symbols in the set $M_i$ and each set $Q_i$ is the set of symbols to be replaced. For each i, let $covered(M_i)=\{\sigma \in M_i ~|~ \exists p\in P_i (\sigma (p)\in Q_i) \}$. In order for a permutation to be included in the extended set of permutation on $n+1$ symbols it must be covered. In other words, it must have one of the named symbols in one of the named positions. In general, for integers i, when $\sigma \in covered(M_i)$, there may be more than one position $p\in P_i$ such that $\sigma (p)\in Q_i$. If so, arbitrarily designate one of these positions, denoted by $p_*$, to cover $\sigma$. If, on the other hand, there is exactly one position $p\in P_i$ such that $\sigma (p)\in Q_i$, then let the designated position $p_*$ be p. In this case we say that ${\sigma }$ is uniquely covered. If, for an integer i, there is a bijection mapping $P_i \times Q_i$ to $covered(M_i)$, so $|P_i \times Q_i|=|covered(M_i)|$, then we say $M_i$ is well covered by $(P_i, Q_i )$. Otherwise, we say that $M_i$ is covered.

For our construction, we include an additional set of permutations $M_{s+1}$, for which there is no corresponding set of positions or symbols. None of the permutations in $M_{s+1}$ are in any of the sets $M_{i}$. The partition and extension operation adds the new symbol n to the end of each permutation of $M_{s+1}$, as was done with the second set in the rudimentary form of extension. Every permutation in $M_{s+1}$ is used in the construction of our new PA. By definition we say that $M_{s+1}$ is well covered. Thus, we create the vector $\mathcal{M}=(M_1, M_2, \dots , M_{s+1})$, which includes this extra set. We define $\mathcal{M}$ to be well covered if every $M_i$, $0\le i\le s+1$ is well covered.

We define a distance-d partition system for $Z_n$ to be a triple $\Pi =(\mathcal{M,P,Q})$ that satisfies the following properties:

• (1) for all $M_i\in \mathcal{M}, hd(M_i)\ge d$, and

• (2) for all $i,j (1\le i<j\le s+1), hd(M_i,M_j)\ge d-1$.

Observe that the set consisting of the union of the sets of $\mathcal M$ does not have Hamming distance d, because the distance between permutations in different sets may only be $d-1$.

In practice, the collection of pairwise disjoint sets of permutations $\mathcal{M}=(M_1, M_2, \dots ,$ $M_{s+1})$ will often consist of a group and some collection of its cosets. In such a case all sets have the same cardinality. The list $\mathcal{M}$, in general, will not correspond to all available cosets; in fact, we often choose the cosets and their order in a careful manner for optimality. As stated, the particular sets and partitions, and the order of the sets in the partitions $\mathcal{P}$ and $\mathcal{Q}$, will be chosen with some thought. Example 1 is a distance-7 partition system illustrating explicitly the covered permutations in each set $M_i$.

Example 1

Let $n=7$ and $\mathcal{M}=(M_1, M_2,M_3, M_4)$ be an ordered list of permutation arrays on $Z_7$, where:

• (1) $M_1=\{0123456,1234560,2345601,3456012,4560123,5601234,6012345\}$,

• (2) $M_2=\{0246135,2461350,4613502,6135024,1350246,3502461,5024613\}$,

• (3) $M_3=\{0531642,5316420,3164205,1642053,6420531,4205316,2053164\}$, and

• (4) $M_4=\{0362514,3625140,6251403,2514036,5140362,1403625,4036251\}$.

Let $\mathcal{P} = (\{0,3\},\{1,4,6\},\{2,5\})$ and $\mathcal{Q} = (\{0,1,2\},\{3,5\},\{4,6\})$. The triple $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ is a distance-7 partition system.

All but one of the permutations in $M_1$ and $M_2$ are covered, and all but three of the permutations of $M_3$ are covered, as shown in Table 1. In this example $M_{s+1}=M_4$. All permutations in $M_{s+1}$ are included in the construction. Each $M_i$ is well covered so $\mathcal{M}$ is well covered. $\square$

Table 1 Covered permutations of $\mathcal{M}$

Let $\sigma$ be a permutation on $Z_n$ and let $k\in Z_n$. The extension of $\sigma$ by position k, denoted by $ext_k(\sigma )=\sigma '$, is a permutation on $Z_{n+1}$ defined by: $\sigma '(k)=n,\sigma '(n)=\sigma (k)$, and $\sigma '(j)=\sigma (j)$, for all j $(0\le j<n,j\ne k)$. We will always extend $\sigma$ at the designated position $p_*$ and refer to this new permutation as $ext(\sigma )$ and $\sigma '$ interchangeably.

Partition and extension uses sets $P_i$ and $Q_i$ in the two partitions $\mathcal{P}$ and $\mathcal{Q}$ to modify the covered permutations in $M_i$, for $1\le i\le s$, for the purpose of creating a new PA on $Z_{n+1}$ with Hamming distance d. Let $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ be a distance-d partition system, where $\mathcal{M}=(M_1, M_2, \dots , M_{s+1})$, for some s. We now show how the partition and extension operation creates a new permutation array $ext(\Pi )$ on $Z_{n+1}$. For all i $(1\le i\le s)$, let $ext(M_i)$ be the set of permutations defined by

$$\begin{aligned} ext(M_i)=\{ext(\sigma )~|~\sigma \in covered (M_i)\}. \end{aligned}$$

For $M_{s+1}$, let $ext(M_{s+1})$ be the set of permutations on $Z_{n+1}$ defined by:

$$\begin{aligned} ext(M_{s+1})=\{\tau '~|~\tau \in M_{s+1}\text { and }\tau '(j)=\tau (j),\forall j~ (0\le j<n),\text { and }\tau '(n)=n\}. \end{aligned}$$

Let $ext(\Pi )$ be defined by $ext(\Pi )\!=\!\cup _{i=1}^{s+1} ext(M_i)$. Note that $|ext(\Pi )|=\sum _{i=1}^{s+1} |ext(M_i)|$. A permutation $\sigma \in M_i$ is extended only by a position in its designated position set, $P_i$, which contains a symbol in its designated symbol set, $Q_i$. This will ensure that the permutations in $ext(\Pi )$ have Hamming distance d, as we shall prove in Theorem 1 below. Before we prove the theorem, we illustrate the creation of $ext(\Pi )$.

Example 2

Let us use the partition and extension operation to compute $ext(\Pi )$ for $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, the distance-7 partition system described in Example 1. Table 2 illustrates $ext(M_i)$ for all $M_i$ in $\mathcal{M}$. $\square$

Table 2 Permutations in $ext(\Pi )$

Of course, our goal is to use $ext(\Pi )$ to obtain improvements on $M(n+1,d)$. For this we need to compute $hd(ext(\Pi ))$ and $|ext(\Pi )|$. Theorem 1 and Corollary 1 below show us how to compute these quantities.

Theorem 1

Let d be a positive integer. Let $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ be a distance-d partition system for $Z_n$, with $\mathcal{M}=(M_1,M_2,\dots ,M_{s+1})$ for some positive integer s. Let $ext(\Pi )$ be the PA on $Z_{n+1}$ created by partition and extension. Then, $hd(ext(\Pi ))\ge d$.

Proof

First, suppose that both $\sigma ',\tau '$ are in $ext(M_{s+1})$. Then $hd(\sigma ',\tau ')\ge d$, because $\sigma$ and $\tau$ are in $M_{s+1}$, $hd(M_{s+1})=d$, and by definition of $ext(M_{s+1})$, $\sigma '(j)=\sigma (j)$ and $\tau '(j)=\tau (j)$, for all j $(0\le j<n)$. That is, $hd(ext(M_{s+1}))\ge d$.

Next suppose $\tau '$ is in $ext(M_{s+1})$, and suppose that $\sigma '$ is in $ext(M_{i})$ for some i. This means that $\sigma '=ext_x(\sigma )$ for some covered permutation ${\sigma }$ in $M_i$, where $0\le x<n$. Hence $\tau '(n)=n\ne {\sigma }'(n), \tau '(x)\ne n={\sigma }'(x)$. In other words, the two positions that the partition and extension operation have altered in ${\sigma }$ and $\tau$, namely positions x and n, contain different symbols. That is, no additional agreement has been created. Furthermore since $hd(M_i,M_{s+1})\ge d-1$, there are at most $n-(d-1)=n-d+1$ positions k such that ${\sigma }(k)=\tau (k)$, so, there are at least $(n+1)-(n-d+1)=d$ positions where ${\sigma }'$ and $\tau '$ do not agree. Hence $hd({\sigma }',\tau ')\ge d$, and $hd(ext(M_{s+1}),ext(M_i))\ge d$, for all i.

What remains is to show that $hd(ext(M_i),ext(M_j))\ge d$, for all i, j ($1\le i,j\le s$). The rest of the proof is divided into two cases. The cases are based on whether two covered permutations, ${\sigma }$ and $\tau$, are in the same set $M_i$, for some i ($1\le i\le s$), or are in two different sets.

Case (1). For some i, ${\sigma }$ and $\tau$ are covered permutations in the same set $M_i$.

Since $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ is a distance-d partition system, for all $M_i\in \mathcal{M}$, $hd(M_i)\ge d$. Thus, since ${\sigma },\tau \in M_i$, $hd({\sigma },\tau )\ge d$. We show that $hd({\sigma }',\tau ')\ge d$, hence $hd(ext(M_i))\ge d$, for all i.

Part (a): Let ${\sigma },\tau$ both be covered by position r in $P_i$. Then ${\sigma }'(n)={\sigma }(r)$ and $\tau '(n)=\tau (r)$. If ${\sigma }(r)=\tau (r)$, then since $hd({\sigma },\tau )\ge d$, there are at least d other positions m, such that ${\sigma }'(m)={\sigma }(m)\ne \tau (m)=\tau '(m)$. So, $hd({\sigma }',\tau ')\ge d$. On the other hand, if ${\sigma }(r)\ne \tau (r)$, since $hd({\sigma },\tau )\ge d$, there are at least $d-1$ positions m, such that ${\sigma }'(m)={\sigma }(m)\ne \tau (m)=\tau '(m)$. Hence, including position n, where ${\sigma }'(n)={\sigma }(r)\ne \tau (r)=\tau '(n)$, there are at least d positions where ${\sigma }'$ and $\tau '$ disagree, so $hd({\sigma }',\tau ')\ge d$.

Part (b): For some r, t ($0\le r,t<n, r\ne t$), let ${\sigma }$ be covered by position r in $P_i$ and let $\tau$ be covered by position t in $P_i$. So ${\sigma }'(r)=n\ne \tau '(r)$ and $\tau '(t)=n\ne {\sigma }'(t)$. Moreover, since $hd({\sigma },\tau )\ge d$, there are at least $d-2$ other positions m, ($0\le m<n, m\notin \{r,t\}$) such that ${\sigma }'(m)={\sigma }(m)\ne \tau (m)=\tau '(m)$. So, $hd({\sigma }',\tau ')\ge d$. Note that it is not necessary in this argument to separate cases when ${\sigma }(r)=\tau (r)$ or ${\sigma }(t)=\tau (t)$, because regardless, as shown above by counting, there must be at least d positions in ${\sigma }'$ and $\tau '$ with different values. Hence $hd({\sigma }',\tau ')\ge d$. Thus, for all i, ($1\le i\le s$), $hd(ext(M_i))\ge d$.

Case (2). For some i, j ($1\le i<j\le s$), ${\sigma },\tau$ are covered permutations in $M_i$ and $M_j$, respectively.

Since $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ is a distance-d partition system, for all $M_i,M_j\in \mathcal{M}$, $hd(M_i,M_j)\ge d-1$. Thus, $hd({\sigma },\tau )\ge d-1$. We show that $hd({\sigma }',\tau ')\ge d$.

Let ${\sigma }$ be covered at position r by the pair $(P_i,Q_i)$, and let $\tau$ be covered at position t by the pair $(P_j,Q_j)$. As $P_i$ and $P_j$ are disjoint, it follows that $r\ne t$. It follows that ${\sigma }'(r)=n\ne \tau '(r)$ and $\tau '(t)=n\ne {\sigma }'(t)$. Also, since $hd({\sigma },\tau )\ge d-1$ there are at least $d-3$ other positions m, ($0\le m<n,m\notin \{r,t\}$) such that ${\sigma }'(m)={\sigma }(m)\ne \tau (m)=\tau '(m)$. Note that, since $Q_i$ and $Q_j$ are disjoint, ${\sigma }(r)\ne \tau (t)$. Hence ${\sigma }'(n)\ne \tau '(n)$. Hence, there are at least d positions where ${\sigma }'$ and $\tau '$ disagree, so $hd({\sigma }',\tau ')\ge d$. Thus, for all i, j, $(1\le i<j\le s)$, $hd(ext(M_i),ext(M_j))\ge d$.

We have shown that for all i, j, ($1\le i,j\le s+1$), $hd(ext(M_i),ext(M_j))\ge d$. That is, $hd(ext(\Pi ))\ge d$. $\square$

Corollary 1

Let $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ be a distance-d partition system for $Z_n$, where $\mathcal{M}=(M_1,M_2,\dots ,M_{s+1})$, and where $|M_{s+1}|=m$.

• (1) If $\mathcal{M}$ is covered (but not well covered), then $|ext(\Pi )|=\sum _{i=1}^{s+1} |ext(M_i)|$.

• (2) If $\mathcal{M}$ is well covered by $\mathcal{P}=(P_1,P_2,\dots ,P_s)$ and $\mathcal{Q}=(Q_1,Q_2,\dots ,Q_s)$, then $|ext(\Pi )|=m+\sum _{i=1}^s|P_i|\cdot |Q_i|$. Hence,

  $$\begin{aligned} M(n+1,d)\ge m+\sum _{i=1}^s|P_i|\cdot |Q_i|. \end{aligned}$$

Proof

For (1), for all $M_i, |ext(M_i)|=|covered(M_i)|$, by definition of $ext(M_i)$, and $|ext(M_{s+1})|=|M_{s+1}|$. Hence $|ext(\Pi )|=\sum _{i=1}^{s+1} |ext(M_i)|$.

For (2), clearly, $|ext(M_{s+1})|=|M_{s+1}|=m$. Because $\mathcal{M}$ is well covered, for any i, $(1\le i\le s)$, $|ext(M_i)|=|covered(M_i)|=|P_i\times Q_i|=|P_i|\cdot |Q_i|$. Hence, $|ext(\Pi )|=|M_{s+1}|+\sum _{i=1}^s|M_i|=m+\sum _{i=1}^s|P_i|\cdot |Q_i|$. Since $ext(\Pi )$ consists of permutations of length $n+1$, $M(n+1,d)\ge m+\sum _{i=1}^s|P_i|\cdot |Q_i|$. $\square$

3 New PAs obtained by partition and extension

Distance-d partition systems $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, as described, are useful for obtaining better lower bounds for $M(n+1,d)$ for many cases of n and d. There are generally three situations:

• 1. improving the lower bound for $M(q+1,q)$, where q is a power of a prime,

• 2. improving the lower bound for $M(n+1,n)$, where n is not a power of a prime, and the current bound for $M(n,n-1)$ is given by mutually orthogonal Latin squares (MOLS), and

• 3. improving the lower bound for $M(n+1,d)$, given a group $G=M_1$ of permutations over $Z_n$ with $hd(G)=d$ and cosets $M_2,M_3,\dots ,M_k$ such that $hd(M_i,M_j)\ge d-1$, $1\le i,j\le k, i\ne j$.

We now illustrate the use of the partition and extension operation on certain distance-d partition systems $\Pi$ to obtain new results.

Results 1 and 2 below illustrate the use of the partition and extension technique to obtain better lower bounds for M(q, d) where q is a power of a prime. We create PAs from subsets of AGL(1, q). AGL(1, q) is the affine general linear group of permutations on $Z_q$, where $AGL(1,q)=\{ax+b~|~a,b,x\in GF(q),a\ne 0\}$ [19]. Note that, for any choice of $a,b\in GF(q),a\ne 0$, the function $f(x)=ax+b$ is a permutation, so AGL(1, q) is a set of $q(q-1)$ permutations. GF(q) denotes the Galois field on the elements of $Z_q$. If $q=p^1$, where p is a prime, then the operations are addition and multiplication mod p [19]. When $q=p^\alpha , \alpha \ne 1$, (i.e. q is a power of a prime), elements of GF(q) can be viewed as polynomials of degree at most $\alpha -1$ with coefficients in $Z_p$. Addition of two polynomials is done with mod p arithmetic of the coefficients. Multiplication in GF(q) depends on a primitive polynomial r(x) of degree $\alpha$. That is, the elements of GF(q) can be viewed as $1,x,x^2,\dots ,x^{q-1}$, where if $t>\alpha -1$, then $x^t$ is replaced by its remainder when divided by r(x) [19].

AGL(1, q) can be viewed as a collection of permutations given by a group $B_1=\{x+b~|~b,x\in GF(q)\}$ together with $q-2$ cosets of permutations denoted by $B_a=\{ax+b~|~a,b,x\in GF(q), a>1\}$. For example, the coset $B_2$ is given by $\{2x+b~|~b,x\in GF(q)\}$; the coset $B_3$ is given by $\{3x+b~|~b,x\in GF(q)\}$, and so on. Note that, for any $a\in Z_q$, where $a>1$, $B_a$ is the left coset of $B_1$, given by $B_a=\pi _aB_1$, where $\pi _a$ is the permutation by $\pi _a(x)=ax$ and the group operation is composition of permutations. When $q=p^1$ where p is prime, then $B_1=C_p$, the cyclic group of permutations on $Z_p$, consisting of the identity permutation and its cyclic shifts.

It is known that AGL(1, q) is sharply 2-transitive, hence, $hd(AGL(1,q))=q-2+1=q-1$. Consequently, for any subset X of AGL(1, q), $hd(X)=q-1$ as well.

Result 1: $M(26,25)\ge 130$.

We begin with an example of type (1) for $q=25$, a power of the prime $p=5$, with $\alpha =2$. We show that $M(26,25)\ge 130$. The best previous lower bound, $M(26,25)\ge 104$, was obtained by exhibiting 4 MOLS of side 26 [5].

Consider the Galois field $GF(5^2)$. We use the primitive polynomial $r(x)=x^2+2x+3$ to obtain the cyclic group containing of the 24 non-zero elements: $\widehat{1}=x^0$, $\widehat{2}=x^1$, $\widehat{3}=x^2, \dots , \widehat{24}=x^{23}$, of $GF(5^2)$, where we refer to the ith non-zero element $x^{i-1}$ temporarily as $\widehat{i}$. We reduce each of these terms to polynomials of degree $\alpha -1=1$ by computing the remainder when divided by the primitive polynomial (mod 5). Thus we have $\widehat{1}=x^0=1, \widehat{2}=x^1=x, \widehat{3}=x^2=3x+2, \widehat{4}=x^3=3x^2+2x=x+1, \widehat{5}=x^4=x^2+x=4x+2$, and so on. The element $\widehat{0}$ is simply 0. Eliminating the hats on top of the names of the elements, we get the first two rows of the addition table of $GF(5^2)$, which are:

Here, the second row gives $1+x$, for each x in $GF(5^2)$. For example, $\widehat{1}+\widehat{2} = \widehat{4}$, since $\widehat{4}=1+x$, as shown above. The remaining rows of the addition table for $GF(5^2)$ can be obtained using distributive laws of multiplication over addition. Specifically, if $x^i+x^j = x^k$, then $x^{i+1}+x^{j+1}= x(x^i+x^j)=x(x^k)= x^{k+1}$. So, if the entry in the ith row ($i\ge 2$) and jth column is $x^k$, then the entry in the $(i+1)$st row and $(j+1)$st column is $x^{k+1(\text {mod }24)}$. Similarly, if the entry in the ith row ($i\ge 2$) and jth column is 0, then the entry in the $(i+1)$st row and $(j+1)$st column is also 0. Also, if $j=24$, then the $(j+1)$st column is column 1. This can be seen in Table 3, where the addition table of $GF(5^2)$, after a partition and extension operation, is shown in the first twenty four rows.

Create the distance-25 partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, where:

• 1. $\mathcal{M}=(M_1, M_2, M_3, M_4, M_5, M_6)$, where $M_1$ is the group $B_1$, $M_2$ is its coset $B_2$, $M_3=B_3, M_4=B_4, M_5=B_5$ and the extra set is $M_6=B_6$,

• 2. $\mathcal{P}=\{P_1,P_2,P_3,P_4,P_5\}$, where $P_1=\{0,5,11,17,23\}$, $P_2=\{1,7,16,21,24\}$, $P_3=\{2,6,9,13,19\}$, $P_4=\{3,10,12,15,18\}$, $P_5=\{4,8,14,20,22\},$ and

• 3. $\mathcal{Q}=\{Q_1,Q_2,Q_3,Q_4,Q_5\}$, where $Q_1=\{0,1,2,3,10\}$, $Q_2=\{4,6,8,12,23\}$, $Q_3=\{9,14,15,17,24\}$, $Q_4=\{11,13,16,18,19\}$, $Q_5=\{5,7,20,21,22\}$.

Table 3 show the covered permutations from $B_1, B_2, B_3, B_4, B_5$, and $B_6$, after the partition and extension operation has replaced designated symbols in each covered permutation with the symbol 25 and put the original symbols at the end. The group $B_1$ is well covered by $(P_1,Q_1)$, as can be seen in Table 3. That is, there are 5 positions in $P_1$ and 5 symbols in $Q_1$, and all $25 =5\cdot 5$ permutations in $B_1$ are covered. The cosets $B_2, B_3, B_4$, and $B_5$ are covered (but not well covered) by $(P_2,Q_2), (P_3,Q_3), (P_4,Q_4), (P_5,Q_5)$, respectively, as can be seen also in Table 3. In fact, $(P_2,Q_2)$ covers 21 permutations of $B_2$, $(P_3,Q_3)$ covers 21 permutations of $B_3$, $(P_4,Q_4)$ covers 19 permutations of $B_4$, and $(P_5,Q_5)$ covers 19 permutations of $B_5$. The extra coset, $B_6$, is completely covered by putting the symbol 25 in the last position of each of its permutations. It follows from Theorem 1 that $hd(ext(\Pi ))\ge 25$. Furthermore, by Corollary 1, $|ext(\Pi ) |= 25+21+21+19+19+25=130$. Hence $M(26,25) \ge 130$. $\square$

Table 3 Permutations in $ext(\Pi )$ of Result 1

Result 2: $M(30,29)\ge 170$.

Another example of type (1) is for the prime number $p=29$. We show that $M(30,29)\ge 170$. The best previous lower bound, $M(30,29)\ge 120$, was obtained by exhibiting four mutually orthogonal Latin squares of side 30 [5]. Let $p=29$ and consider the group $G=AGL(1,29)$ of permutations on $Z_{29}$, where $hd(G)=28$. G consists of the cyclic group $C_{29}$ together with 27 cosets $B_a$ defined by non-zero values a in GF(29), $1<a\le 28$.

Create the distance-29 partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, where:

• 1. $\mathcal{M}=(M_1, M_2, M_3, M_4, M_5, M_6, M_7)$, where $M_1=C_{29}$, and $M_2,\dots M_7$ are its cosets: $M_2=B_{28}, M_3=B_2, M_4=B_{27}, M_5=B_4, M_6=B_7, M_7=B_3$,

• 2. $\mathcal{P}=(P_1, P_2, P_3, P_4, P_5, P_6)$, where $P_1=\{0,9,14,19,24\}, P_2 =\{1,6,11,16,21\}, P_3 =\{2,7,12,17,22\}, P_4 = \{3,8,13,18,23\}, P_5 = \{5,10,15,20,25\}, P_6 = \{4,26,27,28\}$, and

• 3. $\mathcal{Q}=(Q_1, Q_2, Q_3, Q_4, Q_5, Q_6)$, where $Q_1 = \{0,1,2,3,4\}, Q_2 \!=\! \{5,6,7,8,9\}, Q_3 = \{10,14,18,22,26\}, Q_4 = \{11,15,19,23,27\}, Q_5 = \{12,16,20,24,28\},Q_6 = \{13,17,$ $21,25\}$.

Since $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ is a distance-29 partition system, it follows from Theorem 1 that $hd(ext(\Pi ))\ge 29$. Furthermore, $\mathcal{M}$ is well covered, so it follows from Corollary 1 that $|ext(\Pi )|=|M_7|+5\cdot 25+4\cdot 4=170$. Hence, $M(30,29)\ge 170$. $\square$

Results 1 and 2 give new values $M(q+1,q)$ for q a power of a prime. We now give two results of type (3). Results 3 and 4 below illustrate the partition and extension technique to obtain better lower bounds for $M(q+2,d)$ where $q=p^\alpha , \alpha \ne 1$, is a power of a prime. We use the group PGL(2, q), the projective general linear group of permutations on $Z_{q+1}$. Denote the symbols of $Z_{q+1}$ by $0,1,2,\dots ,q-1,\infty$. The permutations of PGL(2, q) are defined for all $a,b,c,d\in GF(q)$ such that $ad\ne bc$:

• if $x\in GF(q)$, but $x\ne -d/c$, then $g(x)=\frac{ax+b}{cx+d}$,

• if $x=-d/c$, then $g(-d/c)=\infty$,

• if $c\ne 0$, then $g(\infty )=a/c$,

• if $c=0$, then $g(\infty )=\infty$.

Then $|PGL(2,q)|=(q+1)q(q+1)$. It is known that PGL(2, q) is sharply 3-transitive [16, 19], hence

$$\begin{aligned} hd(PGL(2,q))=(q+1)-3+1=q-1. \end{aligned}$$

(1)

Result 3: $M(10,7)\ge 1504$.

This is an example of type (3). We use the partition and extension technique to show that $M(10,7)\ge 1504$, which improves on the previous lower bound of $M(10,7)\ge 1484$ [13]. Consider $G=PGL(2,8)$ on $Z_9$, which is sharply 3-transitive, has $504=9\cdot 8\cdot 7$ elements and shows that $M(9,7)=504$. We consider two cosets of G, say $f_1 G$ and $f_2 G$, where $f_1$ and $f_2$ are the permutations defined by the Frobenius mappings $f_1(x)=x^2$ and $f_2(x)=x^4$ [19] and $hd(f_1 G,G)=hd(f_2 G,G)=hd(f_1 G,f_2 G)=6$.

Create the distance-7 partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, where:

• 1. $\mathcal{M}=(M_1, M_2, M_3)$, where $M_1=G, M_2=f_1 G$ and the extra set $M_3$ is $f_2 G$,

• 2. $\mathcal{P}=(P_1, P_2)$, where $P_1=\{0,1,2,3\}, P_2 =\{4,5,6,7,8\}$, and

• 3. $\mathcal{Q}=(Q_1, Q_2)$, where $Q_1=\{0,1,2,3,4\}, Q_2 =\{5,6,7,8\}$.

It can be seen that $(P_1,Q_1)$ covers all but four of the permutations in $M_1 = G$. This is because all but 4 of the permutations have one of the integers 0, 1, 2, 3 or 4 (i.e., one of the symbols in $Q_1$) in one of the first four positions (i.e., a position in $P_1$). Similarly, $(P_2,Q_2)$ covers all but four of the 504 permutations in $M_2$. Lastly, the 504 permutations in $M_3$ are all included. Hence, by Theorem 1, $ext(\Pi )$ is a PA of $1504=504\cdot 3{-}8$ permutations of length 10 with Hamming distance 7. So, by Corollary 1, $M(10,7) \ge 1504$. $\square$

The PA of 1504 permutations for M(10, 7) is provided in [2].

Result 4: $M(18,14)\ge 12240$.

Another example of type (3) shows that $M(18,14)\ge 12240$, which improves the previous lower bound of $M(18,14)\ge 4896$ [20]. Consider the projective linear group $G=PGL(2,16)$, which is sharply 3-transitive, has $4080=17\cdot 16\cdot 15$ elements, and shows that $M(17,15)=4080$. We use two left cosets of G, namely those with the representatives: $\sigma =(3,5,12,11,14$, 10, 9, 8, 4, 7, 6, 0, 2, 1, 16, 13, 15), and $\tau =(1,7,3,16,5,15,0,10,9,2,6,8,4,11,13,14,12)$. It can be seen that $hd(\sigma G,G)\ge 13, hd(\tau G,G)\ge 13$, and $hd(\sigma G,\tau G)\ge 13$.

Create the distance-14 partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, where:

• 1. $\mathcal{M}=(M_1, M_2, M_3)$, where $M_1=G, M_2=\sigma G$ and the extra set $M_3$ is $\tau G$,

• 2. $\mathcal{P}=(P_1, P_2)$, where $P_1=\{0,1,2,3,8,9,10,11\}, P_2 =\{4,5,6,7,12,13,14,15,16\}$, and

• 3. $\mathcal{Q}=(Q_1, Q_2)$, where $Q_1=\{0,1,2,3,4,5,6,7\}, Q_2 =\{8,9,10,11,12,13,14,15,16\}$.

It can be seen that $(P_1,Q_1)$ covers all of the permutations in $M_1 = G$, $(P_2,Q_2)$, covers all of the permutations in $M_2$. Hence, all of the permutations in $\mathcal{M}$ are covered, and by Corollary 1, $ext(\Pi )$ is a PA of $4080\cdot 3=12240$ permutations of length 18 with Hamming distance 14. So, $M(18,14)\ge 12240$. $\square$

The PA of 12240 permutations for M(18, 14) is provided at [2].

Result 5: $M(33,32)\ge 183$.

An example of type (1) shows that $M(33,32)\ge 183$, whereas the previous lower bound, obtained by demonstrating five MOLS of side 33, was $M(33,32)\ge 165$ [21]. Define the group $AGL(1,32)=\{ax+b~|~a,b,x\in GF(32),a\ne 0\}$, which has 992 permutations.

Create the distance-32 partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$, where:

• 1. $\mathcal{M}=(M_1,M_2,M_3,M_4,M_5,M_6,M_7)$, where $M_1=B_1$, and $M_2$ through $M_7$ are the cosets $B_2$ through $B_7$, respectively.

  Specifically, for the primitive polynomial $r(x)=x^5+x^2+1$, the element named $\widehat{1}$ is $x^0$, the element named $\widehat{2}$ is $x^1$, the element named $\widehat{3}$ is $x^2$, the element named $\widehat{4}$ is $x^3$, the element named $\widehat{5}$ is $x^4$, the element named $\widehat{6}$ is $x^5$, which is equivalent to $x^2+1$ by dividing by the primitive polynomial, and so on. As the non-zero elements form a cyclic group under multiplication, they can be denoted by $x^0, x^1, x^2, \dots , x^{30}$, and renamed as the remainders of division by the primitive polynomial given above. For example, the addition of $\widehat{1}$ and $\widehat{6}$ is $\widehat{3}$, because $1+(x^2+1)$ is $x^2$. Note that $1 + 1 = 0$, as the coefficients of the polynomials are added via GF(2). Also, as can be verified, $\widehat{19}$ is $x+1$, so $\widehat{1}+\widehat{2} = \widehat{19}$. Using this process we see that $M_1$ consists of the 32 permutations given by rows of an addition table for GF(32), where rows 0, 1 and 2 (with hats on top of the names removed) are:

  

  where, when viewed as a matrix with entries $m_{i,j}$.

  (a) for $i=0$ and all j $(0\le j\le 31),m_{0,j}=j$. (This generates the 0th row of $M_1$ shown above, which consists of the integers 0 through 31 in increasing order).

  (b) for $j=0$ and all i $(1\le i\le 31),m_{i,0}=m_{0,i}$. (This generates the 0th column of $M_1$, which is the transpose of the 0th row).

  When viewed as a matrix, the diagonal elements of $M_1$ are zero, and 0th row and 0th column consist of the integers 0 through 31 in increasing order. The sub-matrix starting at row 1 column 1 through row 31 column 31 (except for the main diagonal) is generated row by row, where row $i+1$ is a right cyclic shift of row i, followed by adding 1 to each element, with the rule that $31+1=1$.

  Furthermore, for all k ($1<k\le 7$), $M_k$ is defined as the table with 32 permutations on $Z_{32}$, in which the 0th column is $0,1,2,3,\dots ,31$, and each row, excluding the element in the 0th column, is the left cyclic shift of the corresponding row of $M_{k-1}$ (excluding the element in the 0th column).

  Note that addition and multiplication are abelian, so the jth row and the jth column of $M_i$ are identical for all $M_i\in \mathcal{M}$.

• 2. $\mathcal{P}=(P_1,P_2,P_3,P_4,P_5,P_6)$, where $P_1=\{1,5,8,18,24,27\}, P_2=\{2,9,13,21,30\}$, $P_3=\{0,4,14,15,20,23\}, P_4=\{3,7,11,16\}, P_5=\{10,12,19,25,28,29,31\}, P_6=\{6,17,22,$ $26\}$, and

• 3. $\mathcal{Q}=(Q_1,Q_2,Q_3,Q_4,Q_5,Q_6)$, where $Q_1=\{6,10,11,12,13,21\}, Q_2=\{3,8,15,16,20,$ $24,29\}$, $Q_3=\{5,9,17,26,30\}$, $Q_4=\{0,1,2,7,19,27,28\}$, $Q_5=\{18,23,25,31\}$, and $Q_6=\{4,14,22\}$.

$(P_1, Q_1)$ covers 28 permutations in $M_1$. $(P_2, Q_2)$ covers 29 permutations in $M_2$. $(P_3, Q_3)$ covers 28 permutations in $M_3$. $(P_4, Q_4)$ covers 24 permutations in $M_4$. $(P_5, Q_5)$ covers 27 permutations in $M_5$ and $(P_6, Q_6)$ covers 12 permutations in $M_6$. So, by Theorem 1 $hd(ext(\Pi ))\ge 32$, and by Corollary 1, $|ext(\Pi )|= 28+29+26+28+28+12+32 = 183$. Thus, $M(33,32)\ge 183$. $\square$

Result 6: $M(118,117)\ge 936$.

We give an example of type (2) for $n=118$. The previous bound is $M(118,117)\ge 708$, by demonstrating 6 MOLS of side 118 [5, 21]. There are 8 MOLS of side 117 [5, 21], hence $M(117,116)\ge 8\cdot 117=936$. It is known [5] that a set of k MOLS of side n, for integers k and n, can be transformed into a PA, A, of permutations on $Z_n$ with kn elements such that $hd(A)=n-1$. The transformation is such that the resulting PA A consists of k disjoint sets of permutations, say $M_1, M_2,\dots ,M_k$ such that $hd(M_i)=n$ and $hd(M_i,M_j)=n-1$, for all i, j $(1\le i<j\le k)$. By the partition and extension technique we cover all 936 permutations in the PA A. Therefore, $M(118,117)\ge 936$. The PA of 936 permutations for M(118, 117) is provided in [2].

A natural question arises. Is it possible to use the partition and extension operation iteratively to obtain PA’s on $Z_{n+k}$, for $k>1$? The answer is a qualified “yes”, but improved lower bounds may result only for large n. To see this consider the following: Given a distance-n partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ for $Z_n$, where $\mathcal{M}=(M_1, M_2,\dots , M_s, M_{s+1})$, $\mathcal{P}=(P_1, P_2,\dots , P_s)$, and $\mathcal{Q}= (Q_1, Q_2, \dots , Q_s)$, we can obtain an extended set of permutations, namely $ext(\Pi )$, which consists of permutations of $Z_{n+1}$ with Hamming distance n. For all i, $ext(M_i)$ does not have Hamming distance $n+1$, because the new symbol n in $Z_{n+1}$ (but not in $Z_n$) is often inserted in the same position by the extension operation. So, the ordered list of sets $M'=(ext(M_1), ext(M_2), \dots , ext(M_s), ext(M_{s+1}))$, is not appropriate for a distance-$(n+1)$ partition system. Subsets of these PA’s can be used for another extension. For each set $ext(M_i)$ we create a collection of subsets with Hamming distance $n+1$. For a pair of integers u, v, with u in $\mathcal{P}_i$ and v in $Q_i$, let perm(u, v) be a permutation $\sigma$ in $M_i$ such that $\sigma (u)=v$. Note that there is at most one permutation in $M_i$ with this property, because $hd(M_i)=n$. It follows that $ext_u(\sigma )$ has the symbol n in position u and the symbol v in position n. Let $r\ne u$ be a position, let $t\ne v$ be a symbol, and let $\tau =perm(r,t)$. Then the Hamming distance between ${\sigma }$ and $\tau$ is $n+1$. That is, the new symbol n in $Z_{n+1}$ in $ext_u({\sigma })$ is in position u and in $ext_r(\tau )$ is in position r, with $u\ne r$, and the symbols in position n in $ext_u({\sigma })$ and $ext_v(\tau )$, respectively, are v and t with $v\ne t$. It follows that, for any set of pairs $A=\{(u_1,v_1),(u_2,v_2),\dots ,(u_m,v_m)\}$ such that no two pairs agree in either coordinate, the subset $M_i(A)=\{ perm(u_i,v_j)~|(u_i,v_j)\in A, \forall j, (1\le j\le m)\}$ has Hamming distance $n+1$. That is, the sets $ext(M_i)$ can be partitioned into subsets, each with Hamming distance $n+1$. This allows, for suitable partitions $P'$ and $Q'$, a distance-$(n+1)$ partition system $\Pi '=(\mathcal{M}',\mathcal{P}',\mathcal{Q}')$ for $Z_{n+1}$. It should be noted that the sets in $\mathcal{M}'$ are much smaller than the sets in $\mathcal{M}$ and, hence, the size of the PA produced by the partition and extension operation is also smaller.

For suitably large n, which is, say, 2 more than a power of a prime, iteration of the partition and extension operation could produce better bounds for $M(n,n-1)$ than can be achieved with MOLS. This is an area of continuing research.

Table 4 Lower bounds for $M(n,n-1)$, for $n\in \{10,11,\dots , 309\}$

Many other examples of improved values for $M(n,n-1)$ exist. For many small integers we did the partition and extension by hand. We also developed a simple program for computing partitions and extensions of PA’s and used it on primes p, $61\le p\le 309$ to construct PAs for $n=p+1$. For each such prime, the program uses partitions of $m=\lfloor \sqrt{p}\rfloor$ consecutive integers, that is, for all i, ($1\le i\le \lfloor p/m\rfloor$), it uses the set $P_i=Q_i=\{(i-1)m,(i-1)m+1,\dots ,(i-1)m+(m-1)\}$ and determines the number of permutations covered by $(P_i,Q_i)$ in whichever coset (among those remaining) maximizes the number. Because of the arithmetic, since $\lfloor p/m\rfloor \cdot m$ is less than p, there are $t=p-\lfloor p/m\rfloor \cdot m$ of positions and symbols not used so far. The program chooses another coset and uses a partition consisting of these t symbols and positions to cover additional permutations in this coset. Finally, the program includes an additional coset ($M_{s+1}$ in the definition of distance-d partition systems) from the remaining cosets. Recall that for $M_{s+1}$, no symbols are swapped, but the permutations are extended by putting the integer p in position p (at the end) of each permutation. This gives us a distance-p partition system $\Pi$. The size of the resulting $ext(\Pi )$ is our lower bound for $M(p+1,p)$. Our new results are summarized in Table 4 along with other known bounds $M(n,n-1)$ for $10\le n\le 309$. PAs that exhibit some of our improved results are provided in [2]. In Table 4, improved lower bounds by our techniques, if known, are given in bold at the top of a cell. The second entry gives the previous lower bound. If the second entry comes from MOLS, the number of MOLS is given in the bottom entry of the cell.

4 A new lower bound for $M(p+1,p)$, for primes p

Previous lower bounds for $M(n,n-1)$ have been obtained by exhibiting sets of mutually orthogonal Latin squares (MOLS). Optimum results are known for powers of primes. When n is a power of a prime $M(n,n-1)=n(n-1)$; otherwise, finding a large set of MOLS is a combinatorial problem of considerable difficulty and ongoing interest [5, 18]. Work has also been done on establishing an asymptotic lower bound on the number of MOLS. Let N(n) denote the number of MOLS of side n. It is known that $N(n)\ge n^{1/14.8}$ for sufficiently large n [3]. As previously mentioned, for any positive integer n, if there are k mutually orthogonal Latin squares of side n, then $M(n,n-1)\ge kn$ [6]. From this we obtain $M(n,n-1)\ge n^{1+1/14.8}$ for sufficiently large n.

Using the partition and extension technique, we now show that for primes p, $M(p+1,p)\ge p^{1.5}/2-O(p)$. So, for an infinite set of integers, the partition and extension technique provides an asymptotically better lower bound than that given by current knowledge about MOLS.

The proof considers, for each prime $p\ge 17$, partitions $\mathcal{P}$ and $\mathcal{Q}$, where $\mathcal{P}=\{P_1,P_2,P_3,\dots$ $,P_{t(p)}\}$, $\mathcal{Q}=\{Q_1,Q_2,Q_3,\dots ,Q_{t(p)}\}$, $P_i=Q_i=\{(i-1)s(p),(i-1)s(p)+1,(i-1)s(p)+2,\dots ,is(p)-1\}$, and where $s(p)=\lfloor \sqrt{p} /2\rfloor$ and $t(p)\le \lfloor p/(s(p))\rfloor$ will be selected later. Note that the number of positions included in $\mathcal{P}$ is s(p)t(p), which is less than or equal to p. The same is true for the number of symbols in $\mathcal{Q}$. In order to ensure that $\mathcal{P}$ and $\mathcal{Q}$ are partitions, we can add the missing elements to an arbitrary set $P_k$ (resp. $Q_k$). This addition has no effect on the proof of Lemma 1. The important property is that the sets comprising $\mathcal{P}$ are pairwise disjoint (and likewise for $\mathcal{Q}$).

Lemma 1

For any prime $p\ge 17$, and for any j, $s(p)\le j\le 3s(p)$ or $-3s(p)\le j\le -s(p)$, the permutations in the coset $B_j=\{jx+b~|~b\in GF(p)\}$ are uniquely covered by $(P_i ,Q_i )$, where $P_i=Q_i=\{(i-1)s(p),(i-1)s(p)+1,(i-1)s(p)+2,\dots ,is(p)-1\}$, for all i $(1\le i\le t(p))$.

Proof

First, let $b=0$. We show that, for any choice of j, with $s(p)\le j\le 3s(p)$, and for any position x in $P_1=\{0,1,\dots ,s(p)-1\}$, the permutation $\pi _0(x)=jx$ (mod p) cannot have two values in $Q_1=\{0,1,\dots ,s(p)-1\}$. In particular, the values in these specific positions are: $\pi _0 (0)=0,\pi _0(1)=j, \pi _0 (2)=2j,\dots ,\pi _0(s(p)-1)=(s(p)-1)j$. Since $j\ge s(p)$, all of the values except $\pi _0 (0)=0$ are larger than the elements in $Q_1$, at least when we do not compute remainders modulo p. Since $j\le 3s(p)$, the largest such value, say L, when $j=3s(p)$, namely $L=\pi _0 (s(p)-1)=(s(p)-1)j$, is at most $(s(p)-1)3s(p)=(\lfloor \sqrt{p} /2\rfloor -1)3(\lfloor \sqrt{p} /2\rfloor )<3p/4<p$. For all values $v\ne 0$ in $V=\{0,j,2j,\dots ,L=s(p)j\}$, $s(p)\le v<p$ and the remainder of v divided by p is equal to v. Thus, only one value in V, namely, $\pi _0 (0)=0$, occurs in $Q_1$. Hence, $\pi _0$ is uniquely covered by $(P_1,Q_1)$.

Observe that other permutations in the coset $B_j$, namely $\pi _b (x)=jx+b$ (mod p) for $0<b<p$, which represent all cyclic shifts of $\pi _0$, have the same property. That is, if $\pi _b (0)=j\cdot 0+b$ (mod $p)=b$ is in $Q_1$, then $\pi _b (1)= j+b, \pi _b (2) =2j+b, \dots , \pi _b (s(p)-1)=(s(p)-1)j+b$ are all larger than the elements of $Q_1$, at least when we don’t compute remainders modulo p. Again since $j\le 3s(p)$, the largest such value, say L, when $j=3s(p)$, namely $L=\pi _b (s(p)-1)=(s(p)-1)j+b$, is at most $(s(p)-1)3s(p)+b=(\lfloor \sqrt{p} /2\rfloor -1)3\lfloor \sqrt{p} /2\rfloor +\lfloor \sqrt{p} /2\rfloor -1< 3p/4-\lfloor \sqrt{p} /2\rfloor -1<4p/4\le p$. (Note that $b\le \lfloor \sqrt{p} /2\rfloor -1$, since b is in $Q_1$.) So, in fact, for each value v in $V=\{b,j+b,2j+b,\dots ,L=(s(p)-1)j+b\}$, the remainder of v divided by p is equal to v. Thus, only one value in V, namely, $\pi _b (0)=b$, occurs in $Q_1$. Hence, $\pi _b$ is uniquely covered by $(P_1,Q_1)$. That is, every covered permutation in the coset $B_j$ is uniquely covered by $(P_1,Q_1)$.

By a symmetric argument we can show that cosets $B_j$, with $-3s(p)\le j\le -s(p)$, are also uniquely covered by $(P_1,Q_1)$. That is, in this case, one subtracts j instead of adding, but otherwise the argument is the same.

We may also generalize to the sets $(P_i,Q_i)$, for $0<i\le t(p)$. In the first paragraph of this proof it was shown that for each j, with $s(p)\le j\le 3s(p)$, the permutation $\pi (j)=jx$ (mod p) cannot have two values in $Q_i=\{(i-1)s(p),(i-1)s(p)+1,\dots ,i\cdot s(p)-1\}$. Furthermore, as shown in the first paragraph of the proof, the maximum element in the sequence $j,2j,3j,\dots ,(s(p)-1)j$ is less than p, so even when considering remainders modulo p it is not possible for two values to be in $Q_i$. Together with the generalization in the second paragraph to permutations of the form $\pi (j)=jx+b$ (mod p), we have shown that every covered permutation in the coset $B_j=\{jx+b~|~b\in GF(p)\}$ is uniquely covered by $(P_i,Q_i), P_i=Q_i=\{(i-1)s(p),(i-1)s(p)+1,(i-1)s(p)+2,\dots ,is(p)-1\}$, for all i ($1\le i\le t(p)$). $\square$

Theorem 2

For primes p, $M(p+1,p)\ge p^{1.5}/2-O(p)$.

Proof

Create the distance-p partition system $\Pi =(\mathcal{M},\mathcal{P},\mathcal{Q})$ on $Z_p$, where:

• 1. $\mathcal{M}=(M_1,M_2,\dots ,M_{t(p)+1})$, where $M_j=B_j$ as described above, and $M_{t(p)+1}$ is an additional coset that is not part of the partition process,

• 2. $\mathcal{P}=(P_1,P_2,\dots ,P_{t(p)})$,

• 3. $\mathcal{Q}=(Q_1,Q_2,\dots ,Q_{t(p)})$.

By Theorem 1, $hd(ext(\Pi ))\ge p$. By Lemma 1, for any prime $p\ge 17$, the covered permutations in the cosets $B_j$, for all j ($s(p)\le j\le 3s(p)$ or $-3s(p)\le j\le -s(p)$), are uniquely covered by ($P_i,Q_i$). All of these cosets are candidates for sets $M_i$. Recall that we can select at most $\lfloor p/\lfloor \sqrt{p} /2\rfloor \rfloor$ cosets. Hence the number of cosets to be partitioned and extended is

$$\begin{aligned} t(p)=\min \{4\lfloor \sqrt{p} /2\rfloor +2,\lfloor p/\lfloor \sqrt{p} /2\rfloor \rfloor \}. \end{aligned}$$

We show that

$$\begin{aligned} \min \{4\lfloor \sqrt{p} /2\rfloor +2,\lfloor p/\lfloor \sqrt{p} /2\rfloor \rfloor \}\ge 2\sqrt{p}-2, \end{aligned}$$

by noting that

• (i) $4\lfloor \sqrt{p} /2\rfloor +2\ge 2\sqrt{p}-2$ or, equivalently, $\lfloor \sqrt{p} /2\rfloor \ge \sqrt{p}/2-1$, and

• (ii) $p/\lfloor \sqrt{p} /2\rfloor \ge 2\sqrt{p}$ or, equivalently, $\lfloor \sqrt{p} /2\rfloor \le \sqrt{p} /2$.

When we have sets $M_i$ of permutations on $Z_p$ such that $hd(M_i)=p$, if the permutations are uniquely covered, then $M_i$ is well covered. That is, when $M_i$ is viewed as a matrix with rows corresponding to permutations, each symbol $v_k$ in $Q_i$ appears once in each column $u_j$. So, for each column $u_j$ there are $|Q_i|$ covered permutations. Since the permutations are uniquely covered, none of the permutations covered in column $u_j$ are covered by another column $u_r$ ($r\ne j$). So, altogether $|covered(M_i)|=|P_i|\cdot |Q_i|$ for all i. Hence $\mathcal{M}$ is well covered by $\mathcal{P}=(P_1,P_2,\dots ,P_{t(p)})$ and $\mathcal{Q}=(Q_1,Q_2,\dots ,Q_{t(p)})$. So, by Corollary 1, $|ext(\Pi ) |=|M_{t(p)+1}|+\sum _{i=1}^{t(p)} |P_i |\cdot |Q_i |= p+\sum _{i=1}^{t(p)} |P_i |\cdot |Q_i |$. There are $|P_i |\cdot |Q_i | =\lfloor \sqrt{p} /2\rfloor ^2\ge (\sqrt{p}/2-1)^2=p/4-\sqrt{p}+1$ covered permutations in each covered coset. Hence, the total number of covered permutations is at least

$$\begin{aligned} p+(2\sqrt{p}-2)\cdot (p/4-\sqrt{p}+1)=p^{1.5}/2-3p/2+4\sqrt{p}-2. \end{aligned}$$

(2)

The theorem follows. $\square$

As an example, consider the prime $p = 10007$. By Eq. (2), $M(10008,10007) \ge 10007^{1.5}/2 -3\cdot 10007/2 + 4 \cdot 10007^{0.5} -2\ge 485,912$. With more care in the choice of a partition system, we conjecture that one can show M(10008, 10007) is at least one million.

5 Conclusions

Using a new partition and extension operation, we have given an algorithm for creating permutation arrays with a larger number of permutations than those generated by previous techniques. Hence, we improve results for M(n, d) for various values of n and d. The size of the permutation arrays obtained by our techniques is related to the quality of the partitions, and it is quite likely that the results can be further improved by additional effort. Finding better values for M(n, d) is an ongoing area of research.

The partition and extension operation has also allowed us to improve previous lower bounds on $M(n,n-1)$ which were obtained from MOLS. Our results are constructive. We use the partition and extension technique to build permutation arrays for primes p that exhibit $M(p+1,p)\ge p^{1.5}/2-O(p)$. Explicitly, for any prime $p\ge 17$ the technique yields a permutation array of $p^{1.5}/2-1.5p+4\sqrt{p}-2$ permutations at Hamming distance p. Results for M(n, d) can be obtained from our website [1]. Permutation arrays exhibiting some of our results can be found in [2].