Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall $τ$-Metric
The Nguyen










Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall τ-Metric
      
The Nguyen


Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL 61801, United States

Email:   thevn2@illinois.edu 

    April 29, 2024
=======================================================================================================================================================


plain
plain


The Cayley distance between two permutations , ∈_n is the minimum number of transpositions required to obtain the permutation  from . When we only allow adjacent transpositions, the minimum number of such transpositions to obtain  from  is referred to the Kendall τ-distance. A set C of permutation words of length n is called a t-Cayley permutation code if every pair of distinct permutations in C has Cayley distance greater than t. A t-Kendall permutation code is defined similarly. Let C(n,t) and K(n,t) be the maximum size of a t-Cayley and a t-Kendall permutation code of length n, respectively.  In this paper,  we improve the Gilbert–Varshamov bound asymptotically by a factor log(n), namely

    C(n,t) ≥Ω_t(n!log n/n^2t)  and  K(n,t) ≥Ω_t(n! log n/n^t).

Our proof is based on graph theory techniques. 








§ INTRODUCTION


A permutation code is a non-empty subset of the symmetry group _n equipped with a distance metric. Permutation codes, originally introduced by Slepian <cit.> in 1965 for transmitting data in the presence of additive Gaussian noises, have been extensively studied for their effectiveness in powerline transmission systems against impulsive noise <cit.>, as well as in the development of block ciphers <cit.>. Especially in recent years, permutation codes under Kendall’s τ-metric, Ulam metric, and Cayley metric have been extensively studied in clouding storage systems, genome resequencing, and the rank modulation scheme of flash memories <cit.>. Under these metrics, codes are designed to correct transposition errors
or translocation errors.

In this paper, we investigate the problem of determining the maximum size of permutation codes in the Cayley metric and Kendall τ-metric. The Cayley distance between two permutations , ∈_n is the minimum number of transpositions required to obtain the permutation  from , where transposition is an exchange of two distinct elements. When we only allow adjacent transpositions, i.e. exchange of two distinct adjacent elements, the minimum number of such transpositions to obtain  from  is referred to the Kendall τ-distance. Let C(n,t) and K(n,t) be the maximum sizes of a permutation code of length n with minimum Cayley distance and Kendall τ-distance at least t+1, respectively. Generally, the problem of estimating the maximum size of a code in any metric for given parameters is very difficult. It is known that C(n,0) = K(n,0) = n! and K(n,1) = n!/2. Additionally, it is also known that K(n, d) = 2 if 2/3n2≤  d ≤n2 
(see <cit.>). Several other bounds are presented in <cit.>. We refer interested readers to see <cit.> and references therein for recent results on the size of permutation codes in the Cayley metric and Kendall τ-metric for small distances.    

In general, the Gilbert–Varshamov (GV) and sphere-packing bounds for permutation codes are well-known and generally outperform other bounds for small values of d. The main goal of this paper is to provide an asymptotic improvement of the Gilbert-Varshamov bound on the size of permutation codes in the Cayley distance and Kendall τ-metric. Note that there are several works that improved the GV bound for permutation codes of length n in the Hamming distance d <cit.> and block permutation distance <cit.>. To the best of our knowledge, this paper is the first work to improve the GV bound of permutation code in the Cayley metric and Kendall τ-metric. In the upcoming paper with Wang, Chee, and Vu <cit.>, an improvement of GV bound is also achieved for permutation codes in the Ulam distance (also known as deletion distance), which is recently considered for q-ary codes by Alon et al. <cit.>. 

The rest of this paper is organized as follows. In Section 
 <ref>, we review some basic facts about the Cayley metric and Kendall τ-metric together with the statement of our results. In Section <ref>, we introduce some relevant terminologies and results from graph theory and then establish some properties that allow us to compute the distance between two permutations in the Cayley metric. The proofs of main results are presented in Section <ref>. 




§ BASIC NOTATION AND STATEMENT OF RESULTS

Denote the set {1,2,…,m} as [m]. Let n be a positive integer and _n be the set of all permutations on the set [n]. Denote =(π_1,π_2,…,π_n)∈_n as a permutation with length n. The symbol ∘ denotes the composition of permutations. Specifically, for two permutations  and  , their composition, denoted by ∘, is the permutation with ∘ (i) = ((i)) for all i ∈ [n]. All the permutations under this operation form the noncommutative group _n known as the symmetric group on [n] of size |_n| = n!.

Given a permutation = (π_1, π_2, …, π_n) ∈_n, the inverse permutation is denoted as ^-1 = (π^-1_1, π^-1_2, …, π^-1_n). Here, π^-1_i indicates the position of the element i in the permutation . For an integer x ∈ [n], π^-1(x) indicates the position of x in permutation . We also use cycle decomposition to represent a permutation in this paper; however, whenever we use this, there is no comma in the representation to distinguish it from the above notation. For example, = (1, 3, 2, 5, 6, 4) has the cycle representation as (1)(2 3)(4 5 6), or (2  3)(4  5  6) for short by deleting all the cycle of length 1 in the representation. 


    For distinct i,j∈[n], a transposition φ(i,j) leads to a new permutation obtained by swapping π_i and π_j in , i.e,
    
    φ(i,j)=(π_1,…,π_i-1,π_j,π_i+1,…,π_j-1,π_i,π_j+1,…,π_n).

    If |i-j|=1, φ(i,j) is called the adjacent transposition.

Note that each transposition can be viewed as a 2-cycle permutation. In this paper, we sometime identify φ(i,j) with _i, j = (i   j), the 2-cycle permutation on [n] defined as _i,j(i) = j, _i,j(j) = i, and _i,j(k) = k for all k ≠ i, j.  In this way, we have φ(i, j) =  ∘_i,j as a composition of two permutations. 


    The Cayley distance between two permutations , ∈_n, denoted by d_C(,), is defined as the minimum number of transpositions which are needed to change  to , i.e,
    
    d_C(,)=min{m:φ_1φ_2…φ_m=},

    where φ_1,…,φ_m are transpositions and φ_1φ_2…φ_m = (…((φ_1)φ_2)…φ_m). 



    The Kendall τ-distance between two permutations , ∈_n, denoted by d_K(,), is defined as the minimum number of adjacent transpositions which are needed to change  to , i.e,
    
    d_K(,)=min{m:φ_1φ_2…φ_m=},

    where φ_1,…,φ_m are adjacent transpositions.


A t-Cayley permutation code of length n is a subset  of _n such that the Cayley distance of any pair of distinct element in  is at least t+1. Let C(n, t) be the maximum size of a t-Cayley permutation code of length n. Define 

    _t() = { : d_C(, ) ≤ t },

and let V(n,t) be size of |_t()| for ∈_n. Note that by symmetry, V(n,t) is well-defined, namely it does not depend on . The following proposition provides us the classical bounds for C(n,t).

    Let n>t be positive integers. C(n, t) is bounded as follows

    n!/V(n,t)≤ C(n,t) ≤n!/V(n,t/2).


For t fixed, we know that V(n,t) = Θ_t(n^2t), so 

    Ω_t(n!/n^2t) ≤ C(n,t) ≤ O_t(n!/n^t).


The lower bound is known as the Gilbert-Varshamov (GV) bound and the upper bound follows from the fact that all _t/2() are disjoint for all  in a t-Cayley permutation code. Our first main result is to improve the GV bound by a log factor when the distance t is constant. In particular, we have the following theorem.

 For n≥ t≥ 1 be positive integers, then 
 
    C(n,t) ≥Ω_t(n! log n/n^2t).



Similarly, let K(n,t) be the maximum size of a t-Kendall permutation code that is a subset  of _n such that the Kendall τ-distance of any pair of distinct elements in  is at least t+1. An analog of Proposition <ref> gives 

    Ω_t(n!/n^t) ≤ K(n,t) ≤ O_t(n!/n^t/2).

We have the following theorem, which gives us an improvement of a log factor, compared with GV bound, for permutation codes in the Kendall τ-metric. 

For n ≥ t ≥ 1,  then 

    K(n,t) ≥Ω_t(n! log n/n^t).





§ GRAPH THEORY PERSPECTIVE




 §.§ Independence number of a graph with few triangles

An independent set of a graph G is a subset of vertices such that no two vertices in the subset represent an edge of G. For a graph G, let α(G) be the independence number of G, i.e. the size of a largest independent set in G. We recall the following folklore result in graph theory. 

Let G be a graph on n vertices with maximum degree Δ. Then G contains an independent set of size n/(Δ  + 1), in other words α(G) ≥ n/(Δ +1).  


When the graph is locally sparse. i.e only few triangles, Ajtai, Komlós and Szemerédi <cit.> showed that Proposition <ref> can be improved by a log factor. More precisely, they showed that for any ε > 0 and any graph G on N ≥ 1 vertices with average degree d and T < N d^2 - ε triangles, then α(G) > Ω_ε((N/d)log d). This line of work has led to several important developments in extremal graph theory and Ramsey theory. We mention that we can easily replace average degree d by maximum degree Δ in the Ajtai, Komlós, and Szemerédi result. In this paper, we will use the following form, which can be found in <cit.>. 

Let G be a graph with maximum degree Δ (Δ≥ 1) and suppose that G has T triangles. Then 

    α(G) ≥|V(G)|/10Δ(logΔ - 1/2log(T/|V(G)|)).






 §.§ Cayley graph on _n


In this section, we discuss about the structure of Cayley graph on _n generated by sets of 2-cycles or transpostions. Given a subset D of a group (G, ·), we write Γ_G(D) to denote the Cayley graph of G with respect to the generator set D; that is, the graph on the vertex set G that contains an directed edge (x, y) if and only if x · y^-1∈ D.  

For n ∈ consider the Cayley graph Γ__n(D) where D is the set of all transposition permutations, i.e 2-cycle permutations 

    D  = {_i,j |  1 ≤ i, j ≤ n}.

Then the Cayley distance is the distance on _n which is the graph distance of the Cayley graph Γ__n(D). 

Note that Γ__n(D) is undirected graph since if ∘σ^-1 = _i,j then ∘^-1 = _i,j. Clearly, the Definition <ref> is equivalent to the Definition <ref>. This perspective allows us to apply the extensive research on Cayley graph to analyze Cayley permutation codes. The following proposition provides a formula to compute the Cayley distance between two permutations, which can be found in <cit.>. We include  the proof here for sake of convenience and completeness.


    The Cayley distance distance d_C(,) between  and  equals  n minus the number of permutation cycles in ∘^-1, i.e 
    
    d_C(, ) = n - |Cycles(∘^-1)|.

     where Cycles() is the set of permutation cycles in , including 1-cycles. 


Firstly, it follows from the definition that the Cayley metric is a left/right invariant metric, i.e.

    d_C(∘, ∘) = d_C(, ) = d_C(∘ , ∘)

 for all , , ∈_n. Therefore, it suffices to prove the Proposition <ref> for the case that = 𝕀, the identity permutation of _n. We now show that for any permutation , the Cayley distance d_C(, 𝕀) equals n minus the number of cycles of . 
 
 Indeed, we observe that a cycle permutation of k elements (a k-cycle) is a composite of k-1 transpositions. For example, the k-cycle permutation (1   2  3  …  k) can be written as _1, 2∘_2, 3∘…∘_k-1, k. We also have  k-1 is the minimum number of transpositions such that their composition is a k-cycle. This can be easily seen by induction on k. Additionally, any permutation  can be expressed as the product of disjoint cycles. All together implies that 
    d_C(, 𝕀) =  n - |Cycles()|.







§ PROOF OF THEOREM <REF> AND THEOREM <REF>
 


The proof idea of Theorem <ref> and Theorem <ref> relies on techniques from graph theory by constructing auxiliary graphs on the set of permutations such that each permutation code is an independent set of these graphs. Therefore, studying the size of codes is equivalent to analyzing the independence number of the auxiliary graph. Hence, the Gilbert-Varshamov bound is simply the application of Proposition <ref> on this graph. By this terminology, if we can show that the auxiliary graph has few triangles, we have an improvement by a log factor compared with the classical GV bound. This idea was initially used by Jiang and Vardy <cit.> to improve GV bound for binary codes with Hamming distance, followed by subsequent papers in other settings, see <cit.> for example. 



 §.§ Proof of Theorem <ref>


We define the graph _n, t with vertex set _n, and two permutations are connected by an edge if their Cayley distance is most t. Therefore, a t-Cayley permutation code is an independent set of _n, t. Note that |V(_n,t)| = n! and Δ = O_t(n^2t). Thus, in order to prove Theorem <ref>, by using Lemma <ref>, it suffices to show that the number of triangles in _n, t is O_t(n! n^4t - ε) for some ε > 0. We will prove this holds for ε = 1. 


 The number of triples (, , ) ∈ (_n)^3 such that d_C(,  ) ≤ t, d_C(, ) ≤ t, and d_C(, ) ≤ t is at most O_t(n! n^4t-1). 


For ∈ S_n, we will count the number of permutations  and  such that (, , ) forms a triangle in _n, t. Note that (, , ) is uniquely determined by  and sequences S_1 = (φ_1,φ_2,…, φ_h), S_2 = (φ'_1,φ'_2, …φ'_ℓ) of transpositions for which = φ_1φ_2…φ_h and = φ'_1φ'_2…φ'_ℓ. For the sake of brevity, we denote ∘ S=φ_1φ_2…φ_m, where the transposition sequence is S=(φ_1,φ_2,…,φ_m).



Since d_C(, ) ≤ t and d_C(, ) ≤ t, we can choose S_1, S_2 such that |S_1|, |S_2| ≤ t. Hence, we can combine S_1 and S_2 to obtain a sequence S of transpositions with size |S_1| + |S_2| ≤ 2t such that = ∘ S. Now, for a such sequence S, there are at most t = O_t(1) possibilities for S_1 and S_2 that produce S. Therefore, for a given , the number of triangles (, , ) is at most O_t(1) times the number of ways to choose a transposition sequence S with |S| ≤ 2t such that = ∘ S and d_C(, ) ≤ t. Hence, it suffices to show that for a given permutation , the number of transposition sequences S with |S| ≤ 2t such that = ∘ S and d_C(, ) ≤ t is at most O_t(n^4t-1). 

By symmetry, we can assume that = id and |S| = 2t, here id stands for identity permutation, i.e id= (1, 2, …, n). Let S =  φ(a_1, b_1) ∘φ(a_2, b_2)  ∘…∘φ(a_2t, b_2t) be a transposition sequence such that d_C(id, id∘  S)  ≤ t. If a_i,b_j are distinct for all 1 ≤ i, j ≤ t, then = id∘ S is determined by (a_i) = b_i and (b_i) = a_i for all 1 ≤ i ≤ t and (x) = x for all other positions, i.e = (a_1   b_1) (a_2   b_2) … (a_2t  b_2t), here we write a permutation as a product of cycles. This is because each transposition does not affect the positions of other elements and a_i, b_j are distinct for all 1≤ i, j ≤ t. It follows that  has n-2t disjoint cycles, so d_C(id, ) = 2t by Proposition <ref>, a contradiction. Therefore, the multiset {a_i, b_j : 1 ≤ i, j ≤ t} has at most 4t-1 distinct values. Hence, the number of choices for S is at most 

    n4t-1 (4t-1)^4t = O_t(n^4t-1).

This completes the proof of Lemma <ref>.






 §.§ Proof of Theorem <ref>

Let _n,t be the graph with V(_n,t) = _n and there is an edge between two permutation  and  if d_K(,  ) ≤ t.  Hence, a t-Kendall permutation code is an independent of _n,t. It is easy to see that |V(_n,t)| = n! and Δ = O_t(n^t). Thus, Theorem <ref> is followed by Lemma <ref> and the following lemma, which is an analog of Lemma <ref> for Kendall τ-distance.  


 The number of triples (, , ) ∈ (_n)^3 such that d_K(,  ) ≤ t, d_K(, ) ≤ t, and d_K(, ) ≤ t is at most O_t(n! n^2t-1). 



The proof is almost identical to Lemma <ref>, in which we consider adjacent transpositions instead of general transpositions. It suffices to prove for a given permutation , the number of sequences S of adjacent transpositions with |S| ≤ 2t such that = ∘ S and d_K(, ) ≤ t is at most O_t(n^2t-1). 

Without loss of generality, we can assume = id and |S| = 2t. Let S = φ(i_1, i_1+1)  ∘φ(i_2, i_2+1) ∘…∘φ(i_2t, i_2t +1) be a sequence of adjacent transpositions such that d_K(id, 𝕀∘ S) ≤ t. If |i_a -  i_b| ≥ 2 for all 1 ≤ a < b ≤ 2t then we have 

    = id∘ S = (i_1   i_1+1) (i_2  i_2+1) … (i_2t  i_2t+1).

However, in this case, we have d_K(id, ) = 2t, a contradiction. Therefore, there exists 1 ≤ a < b ≤ 2t such that |i_a - i_b| ≤ 1. We now define an equivalence relation ∼ on the elements of {i_1, …, i_2t} by setting i ∼ j if |i - j| ≤ 1 and then taking transitive closure. By the above argument, there exists some equivalence class of size at least 2. Thus there are at most 2t - 1 equivalence classes. Now, there are at most n^2k-1 ways to choose the minimal elements of each equivalence class and then 2^2t-x ways to choose the remaining elements. Therefore, the number of ways to choose (i_1, …, i_2t) is at most O_t(n^2t-1). It follows that the number of sequences  S is at most O_t(n^2t-1), which completes the proof of Lemma <ref>.



The exponent 4t-1 and 2t-1 in Lemma <ref> and Lemma <ref> can be improved by a more precise argument. However, we present the above proofs for simplicity since this is enough to obtain our main reults. 





§ ACKNOWLEDGEMENT

The author would like to thank Jozsef Balogh,  Bob Krueger, Quy Dang Ngo, Van Khu Vu, Micheal Wigal, and Ethan White for useful discussions. The author is grateful to Ethan White for a careful reading of the manuscript. The author was partially supported by a David G. Bourgin Mathematics Fellowship. 



abbrv

