Permutation code: Difference between revisions

Revision as of 20:30, 7 February 2023

Revision as of 00:07, 27 March 2023

Line 29:

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 [[automorphism]]s <ref>{{Cite journal |last1=Smith |first1=Derek H. |last2=Montemanni |first2=Roberto |date=2011-08-19 |title=A new table of permutation codes |url=http://dx.doi.org/10.1007/s10623-011-9551-8 |journal=Designs, Codes and Cryptography |volume=63 |issue=2 |pages=241–253 |doi=10.1007/s10623-011-9551-8 |s2cid=207115236 |issn=0925-1022}}</ref>

== Other Bounds ==

There are numerous bounds on permutation codes, we list two here

=== Gilbert-Varshamov Bound Improvement ===

An Improvement is done to the Gilbert-Varshamov bound already discussed above. Using the connection between permutation codes and independent sets in certain graphs one can improve the Gilbert–Varshamov bound [[Asymptote|asymptotically]] by a factor <math>\log(n)</math>, when the code length goes to infinity. <ref>F. Gao, Y. Yang and G. Ge, "An Improvement on the Gilbert–Varshamov Bound for Permutation Codes," in IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 3059-3063, May 2013, doi: 10.1109/TIT.2013.2237945.</ref>

Let <math>G(n, d)</math> denote the subgraph induced by the neighbourhood of identity in <math>\Gamma (n, d)</math>, the [[Cayley graph]] <math>\Gamma (n, d) := \Gamma (S_n, S(n, d - 1))</math> and <math>S(n, k):= \bigcup_{i = 1}^k D(n, i)</math>.

Let <math>m(n, d)</math> denotes the maximum degree in <math>G(n, d)</math>

'''Theorem 3''': Let <math>m'(n, d) = m(n, d) + 1</math> and

<math>M_{IS}(n, d) := n!.\int_0^1 \frac{(1 - t)^{\frac{1}{m'(n, d)}}}{m'(n, d) + [\Delta(n, d) - m'(n, d)]t}dt</math>

Then, <math>M(n, d) \ge M_{IS}(n, d)</math>

where <math>\Delta(n, d) = \sum_{k = 0}^{d - 1}\binom{n}{k}D_k</math>.

The Gilbert-Varshamov bound is, <math>M(n, d) \ge M_{GV}(n, d) := \frac{n!}{1 + \Delta(n, d)}</math>

'''Theorem 4''': when <math>d</math> is fixed and <math>n</math> does to infinity, we have

<math>\frac{M_{IS}(n, d)}{M_{GV}(n, d)} = \Omega(\log(n))</math>

=== Lower bounds using linear codes ===

Using a <math>[n, k, d]_q</math> linear block code, one can prove that there exists a permutation code in the symmetric group of degree <math>n</math>, having minimum distance at least <math>d</math> and large cardinality<ref name=":1">G. Micheli and A. Neri, "New Lower Bounds for Permutation Codes Using Linear Block Codes," in IEEE Transactions on Information Theory, vol. 66, no. 7, pp. 4019-4025, July 2020, doi: 10.1109/TIT.2019.2957354.</ref>. A lower bound for permutation codes that provides asymptotic improvements in certain regimes of length and distance of the permutation code<ref name=":1" /> is discussed below. For a given subset <math>\Kappa</math> of the symmetric group <math>S_n</math>, we denote by <math>M(\Kappa, d)</math> the maximum cardinality of a permutation code of minimum distance at least <math>d</math> entirely contained in <math>\Kappa</math>, i.e.

<math>M(\Kappa, d) = max\{|\Gamma| : \Gamma \subset \Kappa , d(\Gamma) \ge d\}</math>.

'''Theorem 5:''' Let <math>d, k, n</math> be integers such that <math>0 < k < n</math> and <math>1 < d \le n</math>. Moreover let <math>q</math> be a prime power and <math>s, r</math> be positive integers such that <math>n = qs + r</math> and <math>0 \le r < q</math>. If there exists an <math>[n, k, d]_q</math> code <math>C</math> such that <math>C^\perp</math> has a codeword of Hamming weight <math>n</math>, then

<math>M(n, d) \ge \frac{n!M(\Kappa, d)}{(s + 1)!^r s!^{q-r}q^{n - k -1}},</math>

where <math>\Kappa = (S_{s + 1})^r \times (S_s)^{q-r}</math>

'''Corollary 1''': for every prime power <math>q \ge n</math>, for every <math>2 < d \le n</math>,

<math>M(n, d) \ge \frac{n!}{q^{d - 2}}</math>.

'''Corollary 2''': for every prime power <math>q </math>, for every <math>3 < d < q</math>,

<math>M(q + 1, d) \ge \frac{(q + 1)!}{2q^{d - 2}}</math>.

==References==