CS Paper Radar

The Neighbor Graph of Linear Complementary Dual (LCD) Codes

Javier de la Cruz, Anna-Lena Horlemann, Marc Newman, Carlos Vela Cabello, Wolfgang Willems

cs.IT math.CO ·submitted 2026-09-07 14:55 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Graph-Based Linear Codes Associated with the Finite Ring $\mathbb{F}_p[x]/\langle x^4 \rangle$

cs.IT ·2026-10-06 ·Apurba Sarkar, Kalyan Hansda, Makhan Maji
similarity 0.68
Abstract

We investigate the linear codes derived from the zero-divisor graph $Γ(R)$ of the finite local ring $R = \mathbb{F}_p[x]/\langle x^4 \rangle$ for an odd prime $p$. Using an equitable partition of $Z^*(R)$, we determine the parameters of the binary incidence code of $Γ(R)$ and construct induced bipartite subgraph codes achieving dual minimum distance $4$. Over $\mathbb{F}_p$, we parameterize the adjacency and Laplacian codes, derive the closed-form weight distribution of the Laplacian code via the MacWilliams identity, and establish its LCD property. Additionally, we determine the automorphism groups of the graph and its matrix codes. Finally, from extremal subgraphs of $Γ(R)$, we construct two families of Griesmer-optimal linear codes over $\mathbb{F}_p$, comprising a constant-weight minimal code and an optimal two-weight code.

0.11

New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids

cs.DM quant-ph ·2026-10-03 ·Anderson S. Barbosa, Franklin de L. Marquezino, Giuliano G. La Guardia
similarity 0.67
Abstract · 19 pages, 4 figures

In this paper, we present a method for constructing linear codes derived from book graphs. Applying such a method, we construct binary codes that have the greatest possible minimum distance for their length and dimension by means of the $2$-sum of two equal book graphs. We then utilize matroid and graph theory together to investigate some properties of the resulting linear codes. Furthermore, we show that, from the incidence matrix of any graph, we can obtain a linear code over any finite field maintaining the same parameters. Furthermore, we show how the condition for two linear codes to generate a Calderbank-Shor-Steane (CSS) code translates into matroid theory and, utilizing cycle graphs, we exhibit a way to generate codes that meet this condition.

0.18

Perfect Combinatorial Structures in Coding Theory and Cryptography

cs.IT math.HOmath.CO ·2026-09-07 ·Vladimir N. Potapov
similarity 0.65
Abstract · 238 pages

This book develops algebraic and combinatorial methods for studying discrete structures. It brings together graph theory, Boolean functions, Fourier analysis on finite groups, coding theory, perfect colorings and perfect codes, association schemes, Latin squares, and related topics. A central theme is the interaction between different representations of the same object: combinatorial, algebraic, spectral, and coding-theoretic. The main mathematical object studied in this book is a perfect coloring of a graph, or, equivalently, an equitable partition of a graph. The book is intended for advanced undergraduate and graduate students in mathematics and computer science, as well as for researchers in discrete mathematics, combinatorics, coding theory, and related fields.

0.21

Classification of binary, ternary and quaternary Hermitian LCD codes

cs.IT ·2026-10-22 ·Keita Ishizuka
similarity 0.65
Abstract

We extend the complete classifications of linear complementary dual (LCD) codes from length 15 to length 19 in the binary case, from length 10 to length 15 in the ternary case and from length 12 to length 13 in the quaternary Hermitian case. The classification rests on a reduction of the monomial equivalence of LCD codes to graph isomorphism on the coordinates, combined with canonical augmentation.

0.13

On $\ell$-rank additive intersection pairs (RAIP) of codes

cs.IT ·2026-08-11 ·Sanjit Bhowmick, Kuntal Deka, Sihem Mesnager
publishedtheory similarity 0.64
Abstract

This paper introduces and studies \(\ell\)-rank additive intersection pairs (RAIP) of codes over finite fields for a given positive integer \(\ell\). The notion of \(\ell\)-RAIP provides a common framework that generalizes additive complementary dual (ACD) codes, additive complementary pairs (ACP) of codes, and the hull of an additive code. We establish necessary and sufficient conditions characterizing when a pair of additive codes forms an \(\ell\)-RAIP. Furthermore, for (q>2), we prove that any pair of additive codes is monomially equivalent to an ACP of codes. As a consequence, for (q>3), every additive code is monomially equivalent to an ACD code. { A key contribution of the paper is a general construction method for \(\ell\)-RAIP of codes derived from self-orthogonal additive codes, which yields families of \((\ell+1)\)-RAIP of codes under suitable conditions.} In addition, several explicit constructions of \(\ell\)-RAIP of codes are presented.

0.22

Stabiliser codes over prime fields as weighted graphs and as quantum sets of lines

cs.IT math.COquant-ph ·2026-11-03 ·Simeon Ball, Gülizar Günay, Robin Simoens, Ricard Vilar
theory similarity 0.64
Abstract

We further develop the theory of quantum stabiliser codes and its links with graph theory and finite geometry. We prove that an [[n,k,d]]_p stabiliser code over a finite field with p elements, p prime, gives rise to a graph on n-k vertices together with two disjoint independent sets of size k. Its edges are weighted with elements of a finite field of size p. If k=0, such codes are known as graph states. Second, we view stabiliser codes as so-called quantum sets of lines in projective space, allowing us to determined their minimum distance geometrically. We describe two geometrical operations to obtain new quantum sets of lines from given quantum sets of lines. As an application, we list the number of stabiliser codes up to equivalence, for given small parameters.

0.20

Double circulant LCD codes over $\mathbb{F}_2+u\mathbb{F}_2$ and their related binary LCD codes

cs.IT math.RA ·2026-10-12 ·Xingxing Xu, Bo Wu, Jon-Lark Kim
theory similarity 0.63
Abstract

Linear complementary dual (LCD) codes are linear codes that intersect their dual trivially. We study double circulant (Euclidean) LCD codes over the finite chain ring $R=\mathbb F_2+u\mathbb F_2$, where $u^2=0$. Using the Chinese Remainder Theorem and the factorization of $x^n-1$, we derive an explicit enumeration formula, with a separate treatment of the constituent corresponding to $x-1$, which is not obtained by a formal specialization of the previously known counting formula over $\mathbb F_q[u]/(u^k)$. Assuming Artin's primitive root conjecture for $2$, we show that the binary Gray images contain an asymptotically good family of rate $1/2$ which attains the asymptotic Gilbert--Varshamov bound, i.e., whose relative distance can approach $H_2^{-1}(1/2)$ from below. More importantly from the constructive viewpoint, by combining Gray images with a known extension construction, we obtain a binary LCD code with previously unknown parameters $[29,15,7]$ and construct two explicit permutation-inequivalent binary LCD codes with parameters $[45,23,9]$ and nine binary LCD codes with the best known parameters.

0.25

Subcodes with Prescribed Hull Dimensions in Linear Codes:Enumeration, Containment, and Asymptotic Distributions

cs.IT ·2026-10-26 ·Linhan Xiong, Hongwei Liu, Liren Lin
similarity 0.63
Abstract · 39 pages

Mass formulas for prescribed hull dimensions have mainly been studied for linear codes viewed as subspaces of the whole space. We study internal enumeration for an arbitrary fixed parent code. Let $C$ be an $[n,k]_q$ linear code with an $\ell$-dimensional hull, and let $s$ be the subcode dimension. We determine the number of subcodes with prescribed dimension, hull dimension, and type over finite fields of both even and odd characteristic. We decompose the parent code into an LCD complement and its hull, and use projection to reduce enumeration to the corresponding problem inside the LCD complement. This yields explicit formulas refined by complete type and shows that the counts depend only on the relevant parameters, not on the particular parent code or its length. The known whole-space mass formulas and the enumeration of LCD subcodes of LCD codes arise as special cases. Motivated by code extension, we also study the dual containment problem: for a fixed code, we enumerate larger codes containing it with prescribed hull dimension and type. By duality, this problem is converted into the subcode enumeration problem already solved above, leading to corresponding conditional mass formulas. Finally, we investigate the asymptotic distributions arising from the exact enumeration formulas. When both the subcode dimension $s$ and $k-\ell-s$ tend to infinity, the hull distribution is governed by the LCD complement, and the limiting proportions are explicit constants determined by the field, the prescribed hull dimension, and the relevant type. When $s$ approaches or exceeds the dimension $k-\ell$ of the LCD complement, we determine the asymptotic proportion of subcodes attaining the minimum possible hull dimension and establish the associated concentration behavior. Analogous asymptotic results are obtained for the containment problem.

0.23