Content deleted Content added
Line 14:
== Upper Bound ==
A main problem in permutation codes is to determine the value of M(n,d). There has been little progress made for 4 \leq d \leq n-1, except for small lengths. We can define D(n,k) with k=0,1,…,n to denote the set of all permutations in S_n which are exactly k distance away from the identity.
D(n,k)= { \sigma \in S_n : d_H (\sigma, id)=k} with |D(n,k)|={n choose k)D_k. where D_k is the number of derangements of order k.
The Gilbert-Varshamov bound is a very well known upper bound, and so far outperform other bounds for small values of d.
Theorem 1: frac{n!}{(\sum _{k=0} ^{d-1} |D(n,k)|} \leq M(n,d) \leq \frac{n!}{\sum _{k=0} ^{[\frac{d-1}{2}] |D(n,k)|}
This theorem works for small values of d, and there has been improvements on it for the case where d=4, as shown in the next theorem.
Theorem 2: If k^2 \leq n \leq k^2+k-2 for some integer k \geq 2, then
\frac{n!}{M(n,4)} \geq 1 + \frac{(n+1)n(n-1)}{n(n-1)-(n-k^2)((k+1)^2-n)((k+2)(k-1)-n)}.
For small values of n and d, researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed automorphisms. These methods usually provide the best known lower bounds on M(n,d).
==Lower Bound==
| |||