Neighbor connections reveal patterns in special error correcting codes
The Neighbor Graph of Linear Complementary Dual (LCD) Codes
Information Theory
Summary
Some codes, called linear complementary dual (LCD) codes, are useful for making sure messages get through safely in computing and cryptography. This paper looks at how these codes relate to each other when they share almost all of their parts but differ slightly. The authors discovered patterns in how these codes are connected in a network-like graph. They found that this network is very regular and predictable, which helps us understand the structure of LCD codes better. This approach uses ideas from graph theory to study codes in a new way.
linear complementary dual (LCD) codesfinite fieldslinear codeserror correctiongraph theoryneighbor relationcodimensionregular graphcryptographyquantum coding
Authors
Javier de la Cruz, Anna-Lena Horlemann, Marc Newman, Carlos Vela Cabello, Wolfgang Willems
Abstract
Linear complementary dual (LCD) codes form an important class of linear codes with applications in cryptography, classical error correction, and quantum coding theory. In this paper, we study the neighbor relation on LCD codes over finite fields and the graph induced by this relation, where two codes are adjacent whenever they intersect in codimension one. We determine the number of neighbors of an LCD code that are also LCD, and we use this result to analyze the structure of the corresponding neighbor graph. In particular, we prove its regularity over arbitrary finite fields and establish further regularity properties for its main structural subgraphs in the binary and odd-characteristic cases. These results provide a graph-theoretic framework for the study of LCD codes and reveal a strong combinatorial regularity in their neighborhood structure.