New Lower Bounds for Permutation Arrays Using Contraction

A permutation array $A$ is a set of permutations on a finite set $\mathrm{\Omega }$, say of size $n$. Given distinct permutations $\pi ,\sigma \in \mathrm{\Omega }$, we let $hd(\pi ,\sigma )=\mathrm{\mid }\{x\in \mathrm{\Omega }:\pi (x)\mathrm{\ne }\sigma (x)\}\mathrm{\mid }$, called the Hamming distance between $\pi$ and $\sigma$. Now let $hd(A)=$ min${ hd(\pi, \sigma): \pi, \sigma \in A }$\mathrm{.}Forpositiveintegers$n$and$d$with$d\le n$,welet$M(n,d)$bethemaximumnumberofpermutationsinanyarray$A$satisfying$hd(A) \geq d$\mathrm{.}Thereisanextensiveliteratureonthefunction$M(n,d)$, motivated in part by suggested applications to error correcting codes for message transmission over power lines. A basic fact is that if a permutation group $G$ is sharply $k$-transitive on a set of size $n\ge k$, then $M(n,n-k+1)=\mathrm{\mid }G\mathrm{\mid }$. Motivated by this we consider the permutation groups $AGL(1,q)$ and $PGL(2,q)$ acting sharply $2$-transitively on $GF(q)$ and sharply $3$-transitively on $GF(q)\cup {\infty}$ respectively. Applying a contraction operation to these groups, we obtain the following new lower bounds for prime powers $q$ satisfying $q\equiv 1$(mod$3$).

1. $M(q-1,q-3)\ge (q^2-1)\mathrm{/}2$ for $q$ odd, $q\ge 7$,
2. $M(q-1,q-3)\ge (q-1)(q+2)\mathrm{/}3$ for $q$ even, $q\ge 8$,
3. $M(q,q-3)\ge K{q}^2\log q$ for some constant $K$ if $q$ is odd, $q\geq 13$. These results resolve a case left open in a previous paper \cite{BLS}, where it was shown that $M(q-1,q-3)\ge q^2-q$ and $M(q,q-3)\ge q^3-q$ for all prime powers $q$ such that $q\equiv ̸1$ (mod $3$). We also obtain lower bounds for $M(n,d)$ for a finite number of exceptional pairs $n,d$, by applying this contraction operation to the sharply $4$ and $5$-transitive Mathieu groups.