Multilevel constructions of constant dimension codes based on one-factorization of complete graphs

2025

Read Multilevel constructions of constant dimension codes based on one-factorization of complete graphs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27071.txt.

Introduction

Dengming Xu and Mengmeng Li construct constant dimension codes, a class of error-control codes used in random network coding. In these codes every codeword is a subspace of fixed dimension, and good constructions are prized because they raise how much data a network can carry reliably. The multilevel construction is among the most effective routes to such codes.

The authors first pick a skeleton code from binary vectors tied to one-factorization of complete graphs, meaning a splitting of all pairings into perfect rounds. They then build the full codes with quasi-pending blocks and compute dimensions using known optimal Ferrers diagram rank-metric codes. As a payoff, they improve known lower bounds for a key code size across several lengths. The gains give network coding designers stronger options.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-27071

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multilevel constructions of constant dimension codes based on one-factorization of complete graphs Abstract Constant dimension codes (CDCs) have become an important object in coding theory due to their application in random network coding. The multilevel construction is one of the most effective ways to construct constant dimension codes. The paper is devoted to constructing CDCs by the multilevel construction. Precisely, we first choose an appropriate skeleton code based on the transformations of binary vectors related to the one-factorization of complete graphs; then we construct CDCs by using the chosen skeleton code, where quasi-pending blocks are used; finally, we calculate the dimensions by use of known constructions of optimal Ferrers diagram rank metric codes. As applications, we improve the lower bounds of A ¯ q ​ ( n , 8 , 6 ) \overline{A}_{q}(n,8,6) for 16 ≤ n ≤ 19 . 16\leq n\leq 19. Dengming Xu 1 Mengmeng Li 2 Keywords : Constant dimension codes; Multilevel construction; Quasi-pending blocks; Complete graphs. † † 1 Corresponding author, Sino-European Institute of Aviation Engineering, Civil Aviation University of China, 300300 Tianjin, PR China. E-mail: [email protected]. † † 2 College of Science, Civil Aviation University of China, 300300 Tianjin, PR China. E-mail: [email protected] 1 Introduction Let \mathbb{F}_{q} be the finite field of order q and \mathbb{F}_{q}^{n} be the n dimensional vector space over \mathbb{F}_{q} . Let \mathcal{P}_{q}(n) be the set of all subspaces of \mathbb{F}_{q}^{n} . Given a nonnegative integer k\leq n , denote by \mathcal{G}_{q}(n,k) the set of all k -dimensional subspaces of \mathbb{F}_{q}^{n} . It is well-known that \left|\mathcal{G}_{q}(n,k)\right|=\left[\begin{smallmatrix}n\\ k\end{smallmatrix}\right]_{q}:=\prod_{i=1}^{k}\frac{q^{n-k+i}-1}{q^{i}-1} where \left[\begin{smallmatrix}n\\ k\end{smallmatrix}\right]_{q} is the Gaussian coefficient. For any two subspaces U,V\in\mathcal{P}_{q}(n) , the subspace distance between U and V is defined by d_{S}(U,V)=\dim(U)+\dim(V)-2\dim(U\cap V). A subset \mathscr{C} of \mathcal{G}_{q}(n,k) is called an \left(n,M,d,k\right)_{q} constant dimension code (CDC) if it has cardinality M and d=\min\{d_{S}(U,V)\mid(U,V)\in\mathscr{C}^{2},U\neq V\}. Denote by A_{q}(n,d,k) the maximum size of an (n,M,d,k)_{q} code. Then an (n,M,d,k)_{q} -CDC is said to be optimal if M=A_{q}(n,d,k) . Constant dimension codes have received significant attention since Koetter and Kschischang presented an application of subspaces codes for error correction in random network coding [ 1 ] . One main problem on CDCs is to improve the lower bound of A_{q}(n,d,k) for given parameters n,d,k. In [ 2 ] , it was proved that a simple construction based on lifting of maximum rank distance (MRD) codes can produce asymptotically optimal CDCs. However, there are still big gaps between the sizes of lifted MRD codes and known upper bounds for CDCs. Since 2008, various methods have been used to construct CDCs for improving the lower bound of A_{q}(n,d,k) , such as multilevel construction [ 3 , 4 , 5 , 6 ] , linkage construction [ 7 , 8 , 9 ] , coset construction [ 10 ] , and so on. Multilevel construction was first introduced by Etzion and Silberstein in [ 3 ] , which is a generalization of the construction of the lifted MRD codes. In [ 5 ] , Trautmann and Rosenthal indicated that the pending dots of an Ferrers diagram can increase the subspace distance. In [ 11 ] , Etzion and Silberstein improved the multilevel construction by using pending dots and complete graphs. In [ 6 ] , Silberstein and Trautmann further generalized multilevel construction by using quasi-pending blocks. Multilevel construction has become an effective way and was widely used to construct CDCs, see also [ 12 , 13 ] . In the paper, we focus on constructing (nt,4t,3t)_{q} CDCs by the multilevel construction. Precisely, we first choose an appropriate skeleton code by the extensions and permutations of binary vectors related to one-factorization of complete graphs, this provides a new idea to choose the skeleton codes in the multilevel construction; then, inspired by the work in [ 11 , 6 ] , we construct CDCs by using the chosen skeleton code, where quasi-pending blocks are used; finally, we calculate the dimensions by use of the known constructions of optimal Ferrers diagram rank metric codes. As applications, we improve the lower bounds of \overline{A}_{q}(n,8,6) for 16\leq n\leq 19. The paper is organized as follows. In Section 2, we introduce some definitions and known results which will be used in the paper. In Section 3, we give the constructions of (nt,4t,3t)_{q} CDCs and calculate the dimensions, as applications of the main result, new lower bounds of \overline{A}_{q}(n,8,6) for 16\leq n\leq 19 are provided . In Section 4, we give the conclusions of the paper. 2 Preliminaries In this section, we introduce some definitions and known results which will be needed in the paper. 2.1 Ferrers diagram rank metric codes Let \mathbb{F}^{m\times n}_{q} be the set of all m\times n matrices over \mathbb{F}_{q} . Let A and B in \mathbb{F}^{m\times n}_{q} , the rank metric d_{R}\left(A,B\right) of A and B is defined by {\rm rank}\left(A-B\right) . An \left(m\times n,M,\delta\right)_{q} rank metric code \mathcal{C} is a subset of \mathbb{F}^{m\times n}_{q} with cardinality M and d_{R}(A,B)\geq\delta for all A,B\in\mathcal{C} with A\neq B. For an \left(m\times n,M,\delta\right)_{q} rank-metric code \mathcal{C} , the Singleton-like upper bound ( [ 14 , 15 ] ) implies that \textstyle{M\leq q^{\max\left\{m,n\right\}\left(\min\left\{m,n\right\}-\delta+1\right)}}. If the equation holds, then \mathcal{C} is called a maximum rank metric (MRD) code. Furthermore, if \mathcal{C} is a k -dimensional \mathbb{F}_{q} -linear subspace of \mathbb{F}^{m\times n}_{q} , then it is said to be linear, and is denoted by \left[m\times n,k,\delta\right]_{q} . Linear MRD codes were constructed for all possible parameters ( [ 14 , 15 ] ). Theorem 2.1 . [ 2 , Definition 3] Let n\geq 2k and \mathcal{D} be a \left[k\times\left(n-k\right),\delta\right]_{q} -MRD code. Then the lifted MRD code \mathscr{C}=\left\{rowspace(I_{k}\mid A):A\in\mathcal{D}\right\} is an (n,q^{(n-k)(k-\delta+1)},2\delta,k)_{q} -CDC, where I_{k} is the k\times k identity matrix. In the following, we denote by \overline{A}_{q}(n,2\delta,k) the maximum size of an (n,2\delta,k)_{q} CDC which contains a lifted MRD code as a subset. Ferrers diagrams are used to represent partitions by arrays of dots and empty entries. They are defined as follows. Definition 2.2 . [ 3 ] Given positive integers m and n , an m\times n Ferrers diagram \mathcal{F} is an m\times n array of dots and empty entries satisfying the following conditions : • the number of dots in each row is at most the number of dots in the previous row; • all dots are shifted to the right; • the first row has n dots and the rightmost column has m dots. Let \mathcal{F} be an m\times n Ferrers diagram. For 1\leq i\leq n , let \gamma_{i} be the number of dots in the i th column of \mathcal{F} . Then \mathcal{F} can be written as \mathcal{F}=\left[\gamma_{1},\gamma_{2},\dots\dots\dots,\gamma_{n}\right] . The transposed Ferrers diagram of \mathcal{F} is defined by \mathcal{F}^{t}=\left[\rho_{m},\rho_{m-1},\dots\dots\dots,\rho_{1}\right] , where \rho_{i} is the number of dots in the i th row of \mathcal{F} for each 1\leq i\leq m . An m\times n Ferrers diagram is said to be full if it has mn dots. Example 2.1 . Let \mathcal{F}=\left[1,2,4\right] . Then \begin{matrix}\mathcal{F}=\bullet&\bullet&\bullet\\ &\bullet&\bullet&\\ &&\bullet&\\ &&\bullet&\\ \end{matrix} \begin{matrix}\mathcal{F}^{t}=\bullet&\bullet&\bullet&\bullet\\ &&\bullet&\bullet&\\ &&&\bullet&\\ \end{matrix} Definition 2.3 . [ 3 ] An [m\times n,k,\delta]_{q} rank metric code \mathcal{C} is called an \left[\mathcal{F},k,\delta\right]_{q} Ferrers diagram rank metric code (FDRMC) if for each U\in\mathcal{C} , all the entries of U not in \mathcal{F} are zeros. The FDRMC

Read the complete text