PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Twisted Gabidulin Codes

Guglielmo Lunardon, Rocco Trombetti, Yue Zhou

arXiv:1507.07855v3math.COcs.ITmath.IT

TL;DR

The equivalence problem for generalized twisted Gabidulin codes had remained open across arbitrary parameters. This paper proves a generalized family is MRD and determines equivalence, showing that the earlier Gabidulin and twisted families are proper subsets up to equivalence.

  • Problem

    Equivalence between generalized twisted Gabidulin codes with arbitrary parameters remained open, leaving their relation to existing families unresolved.

    Source: §1 · p. 3, §4 · p. 6

  • Method

    The paper gives an alternative proof of the MRD property and develops necessary-and-sufficient equivalence criteria for members of the generalized family.

    Source: §3 · p. 4, §4 · p. 6

  • Results

    The generalized twisted codes are MRD, and generalized Gabidulin and twisted Gabidulin codes are proper subsets of the family up to equivalence.

    Source: §1 · p. 3, §3 · p. 4

  • Takeaways & Limitations

    The classification establishes equivalence classes in the generalized family beyond those represented by the two earlier families.

    Source: §1 · p. 3

    Theorem 4.4 covers 2 ≤ k ≤ n−2; the k = 1 case is solved elsewhere, while k = n−1 can be reduced to equivalence of Delsarte duals.

    Source: §4 · p. 6

Abstract

from arXiv · show

Let $\mathcal{C}$ be a set of $m$ by $n$ matrices over $\mathbb{F}_q$ such that the rank of $A-B$ is at least $d$ for all distinct $A,B\in \mathcal{C}$. Suppose that $m\leqslant n$. If $\#\mathcal{C}= q^{n(m-d+1)}$, then $\mathcal{C}$ is a maximum rank distance (MRD for short) code. Until 2016, there were only two known constructions of MRD codes for arbitrary $1<d<m-1$. One was found by Delsarte (1978) and Gabidulin (1985) independently, and it was later generalized by Kshevetskiy and Gabidulin (2005). We often call them (generalized) Gabidulin codes. Another family was recently obtained by Sheekey (2016), and its elements are called twisted Gabidulin codes. In the same paper, Sheekey also proposed a generalization of the twisted Gabidulin codes. However the equivalence problem for it is not considered, whence it is not clear whether there exist new MRD codes in this generalization. We call the members of this putative larger family generalized twisted Gabidulin codes. In this paper, we first compute the Delsarte duals and adjoint codes of them, then we completely determine the equivalence between different generalized twisted Gabidulin codes. In particular, it can be proven that, up to equivalence, generalized Gabidulin codes and twisted Gabidulin codes are both proper subsets of this family.

1. Introduction

The introduction situates generalized twisted Gabidulin codes among rank-metric MRD constructions and states that the paper determines their equivalences. It also establishes that, up to equivalence, the generalized Gabidulin and twisted Gabidulin families are proper subsets of this larger family.

1. Introduction

  • The Singleton-like bound defines the maximum size for a rank-metric code, and equality makes the code MRD.MRD codes have applications in communications and cryptography.Source: §1 · pp. 1–2
  • Delsarte and Gabidulin independently constructed Fq-linear MRD codes of size q^nk, later generalized by Kshevetskiy and Gabidulin.The introduction identifies these as generalized Gabidulin codes.Source: §1 · p. 2
  • For generalized Gabidulin codes, bounds on polynomial roots determine the minimum distance through the ranks of associated matrices.Every polynomial in Gk,s has at most q^(k−1) roots, and one can vanish on a (k−1)-dimensional subspace spanned by the αi.Source: §1 · p. 2
  • Sheekey introduced a distinct linear MRD construction using linearized polynomials, called twisted Gabidulin codes [22].The construction has size q^nk under the stated norm condition.Source: §1 · p. 2
  • Up to equivalence, generalized Gabidulin codes and twisted Gabidulin codes are proper subsets of the generalized twisted Gabidulin family.The paper also outlines work on Delsarte duals, adjoint codes, an MRD proof, and equivalence classification.Source: §1 · p. 3
  • The paper investigates a generalization of twisted Gabidulin codes, called generalized twisted Gabidulin codes, and shows that generalized Gabidulin and twisted Gabidulin codes are both quite small proper subsets of this new MRD-code family.Source: §1 · p. 3

2. Dual and adjoint codes of MRD codes

This section sets out Delsarte duality for matrix codes and its polynomial counterpart. It also relates polynomial adjoints to matrix transposes.

2. Dual and adjoint codes of MRD codes

  • The Delsarte dual of a code is defined using a symmetric bilinear form on matrices.The section introduces the form and then uses it to define the dual code.Source: §2 · p. 3
  • The Delsarte dual of a linear MRD code remains MRD.Source: §2 · p. 3
  • For n×n codes represented by q-polynomials, the section defines polynomial duality and the adjoint operation.The adjoint of a linearized polynomial is equivalent to the transpose of its associated matrix [14].Source: §2 · pp. 3–4

3. Generalized twisted Gabidulin codes

The section gives an alternative proof that generalized twisted Gabidulin codes are MRD. It then identifies their relation to earlier families and supplies a criterion for when members are equivalent.

3. Generalized twisted Gabidulin codes

  • The authors offer an alternative proof of the earlier generalization and use the intersection criterion to establish the new construction.Source: §3 · pp. 4–5
  • The intersection f_M is MRD exactly when its size is q^nk, for the specified Fqs-linear MRD code M.The proof uses a bound on the kernel dimension of nonzero polynomials in the intersection.Source: §3 · p. 4
  • Under the stated gcd and norm conditions, Hk,s(η, h) is an Fq-linear MRD code of size q^nk.The theorem assumes k < n and gcd(n, s) = 1.Source: §3 · p. 4
  • The codes are called generalized twisted Gabidulin codes; setting s = 1 gives twisted Gabidulin codes, while η = 0 gives generalized Gabidulin codes.The family appeared earlier in [22, Remark 8] under different notation.Source: §3 · p. 5

4. Equivalences of generalized twisted Gabidulin codes

This section gives equivalent forms for the Delsarte duals and adjoints of generalized twisted Gabidulin codes and classifies their equivalences under specified parameter conditions. It establishes the necessary constraint s ≡ ±t (mod n), then examines the associated parameter conditions and automorphisms.

4. Equivalences of generalized twisted Gabidulin codes

  • The Delsarte dual of H_k,s(η, h) is equivalent to H_n−k,s(−η, n − h).Source: §4 · p. 5
  • The adjoint of H_k,s(η, h) is equivalent to H_k,s(1/η, sk − h).Source: §4 · p. 5
  • Theorem 4.4 gives an if-and-only-if equivalence classification for H_k,s(η, g) and H_k,t(θ, h), with alternatives requiring either s ≡ t and g ≡ h or s ≡ −t and g ≡ −h modulo n.The theorem assumes gcd(n, s) = gcd(n, t) = 1, 2 ≤ k ≤ n − 2, and the stated norm conditions; each alternative also requires c, d ∈ F* satisfying further conditions.Source: §4 · p. 6
  • Theorem 4.8 concludes that H_{k,s}(η,g) and H_{k,t}(θ,h) are not equivalent when s is not congruent to ±t modulo n.Its hypotheses include n, k, s, t, g, h ∈ Z+, gcd(n,s) = gcd(n,t) = 1, η, θ ∈ F_{q^n}, and N_{q^{sn}/q^s}(η), N_{q^{tn}/q^t}(θ) ≠ (−1)^{nk}.Source: §4 · pp. 8, 11
  • For k = 2 or n − 2, codes with s ≠ ±t are inequivalent when at most one parameter is nonzero or when n ≠ 5 and both are nonzero.The n = 5 case with both parameters nonzero is addressed separately by Theorem 4.10.Source: §4 · pp. 11, 13
  • For k,s,t,g,h ∈ Z+, with gcd(5,s)=gcd(5,t)=1 and k=2 or 3, if η,θ ∈ F*_{q^5} satisfy the stated norm inequalities and s ≢ ±t (mod 5), then H_{k,s}(η,g) and H_{k,t}(θ,h) are not equivalent.Source: §4 · p. 13
  • When s ≡ t (mod n), the argument concludes support A = {0}; it excludes −s by absence of a corresponding term and excludes s using η ≠ 0.Source: §4 · pp. 16–17

Appendix

The appendix proves that in the exceptional case n = 4, k = 2, and s ≡ t ≡ 1 (mod 4), every equivalence map sends monomials to monomials; this is the twisted Gabidulin equivalence case not covered by Theorem 7 in [22].

Appendix

  • For n = 4, k = 2, and s ≡ t ≡ 1 (mod 4), the appendix establishes that every equivalence map between the specified codes sends monomials to monomials.It proves the universal support A equals {0}, a result used in the proof of Theorem 4.4.Source: Appendix · p. 18
  • The proof partitions possible coefficient supports into cases and rules them out by showing they force a zero equivalence map or contradict the norm assumption on η.The cases distinguish which coefficient c_j0 or its nearby terms are nonzero.Source: Appendix · pp. 19–20
  • The relations derived in this case yield a contradiction to the stated assumption that the norm Nq4/q(η) is not equal to 1.Source: Appendix · p. 20
  • When h ≡ 0 (mod 4), equation (21) implies d_{3−j0}=d_{−j0}=d_{2−j0}=0, hence L2(x)=0, contradicting the definition of equivalence map τ.Source: Appendix · p. 20

Related papers

Loading 1507.07855v3…