2018/04/11 by Bereg, Sergey, Miller, Zevi, Mojica, Luis Gerardo +2
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1804.03768
A permutation array A is a set of permutations on a finite set Ω, say of size n. Given distinct permutations π, σ∈ Ω, we let hd(π, σ) = |\ x∈ Ω: π(x) ≠ σ(x) \|, called the Hamming distance between π and σ. Now let hd(A) = min\ hd(π, σ): π, σ∈ A \. For positive integers n and d with d≤ n, we let M(n,d) be the maximum number of permutations in any array A satisfying hd(A) ≥ d. There is an extensive literature on the function 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≥ k, then M(n,n-k+1) = |G|. 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)∪ \∞\ respectively. Applying a contraction operation to these groups, we obtain the following new lower bounds for prime powers q satisfying q≡ 1 (mod 3). 1. M(q-1,q-3)≥ (q2 - 1)/2 for q odd, q≥ 7, 2. M(q-1,q-3)≥ (q-1)(q+2)/3 for q even, q≥ 8, 3. M(q,q-3)≥ Kq2log q for some constant K if q is odd, q≥ 13. These results resolve a case left open in a previous paper \citeBLS, where it was shown that M(q-1, q-3) ≥ q2 - q and M(q,q-3) ≥ q3 - q for all prime powers q such that q\not ≡ 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.