Neighbor graph reveals regular patterns in special linear codes
The Neighbor Graph of Linear Complementary Dual (LCD) Codes
Information Theory
Summary
Some special types of codes called LCD codes help protect data in various technologies like cryptography and quantum computing. This paper explores how these codes relate to each other when they differ just a little bit, linking them as neighbors in a graph. The authors found that the way these codes connect in this neighbor graph follows very regular and predictable patterns, no matter what kind of finite field is used. These patterns help us understand the structure of LCD codes better through graph theory.
What this means in practice
- •For cryptography engineers: Design more robust error-correcting codes by exploiting predictable neighborhood structures of LCD codes.
- •For quantum hardware developers: Use the graph structure of LCD codes to better organize quantum error correction schemes with known interaction patterns.
A theory result. No direct application yet.
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.