Maximizing Hamming Distance in Contraction of Permutation Arrays. (arXiv:1804.03768v1 [math.CO])

A {\it permutation array} A is set of permutations on a finite set $\Omega$, say of size $n$. Given distinct permutations $\pi, \sigma\in \Omega$, we let $hd(\pi, \sigma) = |\{ x\in \Omega: \pi(x) \ne \sigma(x) \}|$, called the {\t Hamming distance} between $\sigma$ and $\tau$. Now let $hd(A) =$ min$\{ hd(\pi, \sigma): \pi, \sigma \in A \}$. For positive integers $n$ and $d$ with $d\le n$ we let $M(n,d)$ be the maximum number of permutations in any array $A$ satisfying $hd(A) \geq d$. There is an extensive literature on the function $M(n,d)$, motivated in part by applications to error correcting codes for message transmission over power lines.

In this paper we consider the case where $q$ is a prime power with $q\equiv 1$ (mod $3$). For this case, we give lower bounds for $M(q-1,q-3)$ if $q\geq 7$, and when $q$ is odd for $M(q,q-3)$ if $q\geq 13$. These bounds are based on a {\it contraction} operation applied to the permutation groups $AGL(1,q)$ and $PGL(2,q)$. We obtain additional lower bounds on $M(n,d)$ for a finite number of pairs $(n,d)$ by applying the contraction operation to the Mathieu groups.

from cs updates on arXiv.org https://ift.tt/2qppqdA
//