The Neighbor Graph of Linear Complementary Dual (LCD) Codes

1 Introduction

• LCD codes intersect their dual trivially and are discussed in connection with error correction, cryptographic robustness, and entanglement-assisted quantum error correction.The introduction also cites their use in classical and quantum coding applications.Source: §1 · pp. 1–2
• The paper studies a graph joining LCD codes whose intersection has codimension one, a relation used to examine code structure and potential applications.The introduction mentions identifying codes with good parameters, classification, and adaptive decoding as potential uses of neighbor analysis.Source: §1 · p. 2
• Theorem 3.5 gives the number of LCD neighbors of an LCD code over Fq, supporting analysis of the neighbor graph's regularity.The introduction identifies this as a main result.Source: §1 · p. 2
• The paper reports regularity properties for the main structural subgraphs in the binary and odd-q cases.These results are identified with Theorem 4.17 and Corollary 5.11.Source: §1 · p. 2

2.1 Coding and graph theory basics

• Minimum distance determines a code's error-detection and correction capabilities; although this paper does not compute distances, neighbor graphs motivate searching for good-distance codes.The motivation is especially noted for small field sizes.Source: §2.1 · p. 3
• The preliminaries define induced and bipartite subgraphs and equitable partitions, whose graph-automorphism orbits are equitable.An equitable partition makes within-part subgraphs regular and between-part subgraphs biregular.Source: §2.1 · p. 3

2.2 Neighbors of linear codes

• Two [n,k]q codes are neighbors when their intersection has dimension k−1, and all such codes form the Grassmann graph Jq(n,k).The paper also notes that code neighbors correspond to neighbors of their duals.Source: §2.2 · pp. 4–5
• The paper focuses on LCD-code orbits under the orthogonal group, which has at most three orbits for q=2 and two for odd q.The text says this bounded orbit count permits general study across code parameters.Source: §2.2 · p. 6

2.3 Linear complementary dual (LCD) codes

• The paper excludes proper binary extension fields because any LCD code over a field of even characteristic has an equivalent LCD code over F2, and distinguishes even-like from odd-like binary codes.Even-like codes have coordinate sum zero for every codeword; odd-like codes do not satisfy that condition.Source: §2.3 · p. 6
• The orthogonal-group action preserves LCD-code types, partitioning codes into orbits according to binary parity-like type or, for odd q, determinant sign.The exact orbit cardinalities depend on the parities of q, n, and k.Source: §2.3 · pp. 7–8

3 Number of neighbors among LCD codes

• For fixed parameters, every LCD code has the same number of LCD neighbors, so the corresponding neighbor graph is regular.Theorem 3.5 gives the count; the supplied passages do not provide its complete formula.Source: §3 · pp. 9, 13
• The counting argument treats self-orthogonal vectors as a hyperplane in even characteristic and as a quadratic variety in odd characteristic.Source: §3 · p. 10
• Neighbor counting enumerates (k −1)-dimensional subspaces as possible intersections, then considers their extensions in the quotient space.Each such subspace has distinct k-dimensional extensions, one of which returns the original code.Source: §3 · p. 14
• When the intersection subspace is LCD, self-orthogonal projective points yield non-LCD neighbors, while non-self-orthogonal points yield LCD neighbors.Source: §3 · p. 14
• For q = 2, exactly half of every LCD code’s neighbors are LCD, and as q grows the fraction of LCD neighbors approaches 1.Source: §3 · p. 17

4 Structure of binary LCD neighbor graphs

• The binary LCD neighbor graph G2(n, k) is connected.The proof uses its regularity as an induced subgraph of J2(n, k).Source: §4 · p. 17
• Membership is determined by whether the all-ones vector w lies in C and C⊥; the even-even LCD class is empty.The odd-odd class excludes w from both spaces, odd-even includes w only in C, and even-odd includes it only in C⊥.Source: §4 · p. 18
• Odd-odd codes have neighbors in odd-even codes when n-k is even and in even-odd codes when k is even, while odd-even and even-odd codes are never neighbors.Source: §4 · p. 18
• Cross-orbit degrees are biregular: odd-odd to even-odd is 2^(n-k-1) if k is even and zero otherwise; odd-odd to odd-even is 2^(k-1) if n-k is even and zero otherwise.The reverse degrees are 2^(n-1) - 2^(k-1) from odd-even to odd-odd, and 2^(n-1) - 2^(n-k-1) from even-odd to odd-odd.Source: §4 · pp. 21, 23
• Extending a binary LCD code by v preserves LCD exactly when the component of v in C⊥ has nonzero self-inner-product; for nonzero d in C⊥, exactly one of C′ + ⟨d⟩ and C′ + ⟨d + v⟩ is LCD.Source: §4 · p. 23
• Each binary [n, k] LCD code has exactly (2^(n-k) - 1)(2^k - 1) LCD neighbors.Thus the binary LCD neighbor graph is regular with this degree.Source: §4 · pp. 17, 25

• Goo(n, k) is regular with degree (2^(n-k) - 1)(2^k - 1) - 2^(n-k-1) - 2^(k-1) when n and k are even.Source: §4 · p. 25
• Goe(n, k) is regular with degree (2^(n-k) - 1)(2^k - 1) - 2^(n-1) + 2^(n-k-1) when k is even, and degree 0 when k is odd.Source: §4 · p. 25
• Geo(n, k) is regular with degree (2^(n-k) - 1)(2^k - 1) - 2^(n-1) + 2^(k-1) when n-k is even, and degree 0 when n-k is odd.Source: §4 · p. 25

5 Structure of LCD neighbor graphs for odd q

• For odd q, the LCD neighbor graph is regular and connected.The regularity degree is given by Corollary 5.1.Source: §5 · p. 25
• Every code in the C+ orthogonal-group orbit has a neighbor in the C− orbit.For orbit representatives C+ and C−, the paper also gives a correspondence C+M to C−M that preserves the neighbor relation.Source: §5 · p. 26
• The degree calculation counts codimension-one subcodes by sign, then augments them; for a subcode with one-dimensional intersection with its dual, LCD augmentation requires ⟨u, v⟩ ≠ 0.In that case, the resulting code's sign is independent of the choice of augmenting vector.Source: §5 · p. 28
• Theorem 5.10 counts same-sign neighbors as N_r,r + E_r and opposite-sign neighbors as N_r,−r.Its degree cases are organized by the parities of n and k.Source: §5 · pp. 29–30
• The sign classes LCD+[n, k]q and LCD−[n, k]q induce regular subgraphs, while edges between them form a biregular bipartite graph.The within-class degrees are N+,+ + E+ and N−,− + E−; the cross-class degrees are N+,− and N−,+.Source: §5 · p. 31

6 Conclusion

• LCD neighbor graphs are regular, with degree given by Theorem 3.5, and connected.The paper reports these properties for the graphs induced by LCD codes.Source: §6 · p. 31
• Subgraphs induced by orthogonal-group orbits are regular, and the bipartite graphs between orbits are biregular.The paper explicitly calculates the regularity and biregularity degrees.Source: §6 · p. 31
• The orbit analysis provides explicit degrees for both within-orbit and between-orbit neighbor relations.Source: §6 · p. 31