Permutation code: Difference between revisions

Revision as of 18:12, 27 October 2022

Revision as of 12:39, 2 November 2022

Line 14:

== Gilbert-Varshamov Bound ==

A main problem in permutation codes is to determine the value of <math>M(n,d)</math>. There has been little progress made for <math>4 \leq d \leq n-1</math>, except for small lengths. We can define <math>D(n,k)</math> with <math>k \in \{0, 1,… ..., n\}</math> to denote the set of all permutations in <math>S_n</math> which have exactly <math>k</math> distance from the identity.

<math>D(n,k)= \{ \sigma \in S_n : d_H (\sigma, id)=k\}</math> with <math>|D(n,k)|={n choose k}D_k</math>. where <math>D_k</math> is the number of [[Derangement|derangements]] of order <math>k</math>.

The [[Gilbert–Varshamov bound|Gilbert-Varshamov bound]] is a very well known upper bound, and so far outperforms other bounds for small values of <math>d</math>.

'''Theorem 1''': <math>\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)|}

</math>

This theorem works for small values of <math>d</math>, and there has been improvements on it for the case where <math>d = 4</math> as the next theorem shows.

'''Theorem 2''': If <math>k^2 \leq n \leq k^2+k-2</math> for some integer <math>k \geq 2</math>, then

<math>\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)}</math>.

For small values of <math>n</math> and <math>d</math>, 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 <math>M(n,d)</math>.

==Lower Bound==