PaperlayerView exact revision on arXiv

Source-linked AI summary

Classification of binary, ternary and quaternary Hermitian LCD codes

Keita Ishizuka

arXiv:2610.30561v1cs.ITmath.IT

TL;DR

The paper addresses complete classification of LCD codes across binary, ternary, and quaternary Hermitian settings. It reduces equivalence to graph isomorphism and generates only LCD codes, extending classifications to lengths 19, 15, and 13, respectively.

  • Problem

    The paper addresses complete classification of LCD codes across binary, ternary, and quaternary Hermitian settings.

    Source: §1 · p. 1

  • Method

    The classification reduces code equivalence to graph isomorphism on the coordinates and generates only LCD codes, using canonical augmentation to produce each equivalence class exactly once.

    Source: §3.4 · p. 9, §6 · p. 16

  • Results

    Complete classifications cover binary LCD codes through length 19, ternary LCD codes through length 15, and quaternary Hermitian LCD codes through length 13, for all dimensions.

    Source: §1 · p. 3, §6 · p. 16

  • Takeaways & Limitations

    At these lengths, the limit of complete classification is data storage and distribution rather than the equivalence test.

    Source: §6 · p. 16

    The next lengths would require several terabytes of generator matrices, impractical to store and distribute with present means.

    Source: §4 · p. 15, §6 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

LCD codes are relevant to side-channel countermeasures, equivalence algorithms, and quaternary quantum error correction, but classification is meaningful only where the LCD property is invariant under equivalence. The paper extends complete classifications using graph isomorphism and LCD-only generation, reaching binary length 19, ternary length 15, and quaternary Hermitian length 13.

1 Introduction

  • LCD status is invariant under equivalence exactly for binary and ternary codes with the Euclidean inner product and quaternary codes with the Hermitian inner product.Source: §1 · p. 1
  • Earlier equivalence tests require computing codewords, which can be at least as hard as finding minimum distance or require enumerating all q^k codewords.The paper describes its graph-isomorphism approach as removing this equivalence test as the bottleneck.Source: §1 · p. 2
  • For ternary and quaternary Hermitian codes, closure and a reduction decide monomial equivalence by graph isomorphism on (q − 1)n vertices.Generation stays within LCD codes, and canonical augmentation using the projector digraph produces each equivalence class exactly once.Source: §1 · p. 2
  • Binary, ternary, and quaternary Hermitian LCD classifications reach lengths 19, 15, and 13, respectively, for all dimensions.The paper also obtains inequivalent-code counts by minimum weight and the largest minimum weights d_LCD(n, k).Source: Table 1 · p. 2, §1 · p. 3

2 Preliminaries

The preliminaries define the code and inner-product conventions, LCD property, and equivalence relation used in the paper. They also introduce mass formulas for counting LCD codes and explain how orbit sizes support completeness checks.

2.1 Codes

  • A linear [n, k] code is a k-dimensional subspace of F_q^n; a generator matrix has rows forming a basis, and minimum weight is the least weight of a nonzero codeword.Puncturing deletes a coordinate; shortening restricts to codewords zero there before deleting it.Source: §2.1 · p. 3
  • The Euclidean and Hermitian inner products define dual codes, and the hull is C ∩ C^⊥; C is LCD exactly when this hull is {0}.For a generator matrix G, the LCD condition is equivalent to nonsingularity of the Gram matrix, and puncturing and shortening are dual operations.Source: §2.1 · pp. 3–4
  • For q ∈ {2, 3, 4}, monomial equivalence preserves the inner product and LCD property; otherwise the paper uses coordinate permutations as its equivalence group.Duality bijects equivalence classes of LCD [n, k] and LCD [n, n − k] codes.Source: §2.1 · p. 4

2.2 Mass formula

  • L_q[n, k] counts all LCD [n, k] codes, not just inequivalent ones; mass formulas give these totals for the stated settings.The preliminaries cite closed-form Euclidean counts and a formula for quaternary Hermitian LCD codes.Source: §2.2 · pp. 4–5
  • A set of pairwise inequivalent codes represents every equivalence class exactly when the sum of their orbit sizes attains the stated mass-formula total.Each orbit size is |Mon(n, q)|/|Aut(C)|.Source: §2.2 · p. 5

3 Method

The method reduces LCD-code equivalence to graph isomorphism, generates codes through LCD-preserving deletions and canonical augmentation, and verifies the classifications against independent counts.

3.1 Equivalence of LCD codes and graph isomorphism

  • Projector digraphs encode projector entries as vertex and arc colours; for ternary and quaternary codes, closure reduces monomial equivalence to permutation equivalence while preserving the LCD property.The closure has (q−1)n coordinates, and its projector digraph is a complete invariant of monomial equivalence for q ∈ {3, 4}.Source: §3.1 · p. 6

3.2 Computational cost

  • About 40×, 1,400×, and 1,800× faster than the codeword digraph, the projector digraph is also 4 × 10^4 to 5 × 10^5 times faster than SageMath.The reported complete classifications required about 240, 540, and 200 CPU hours for binary length 19, ternary length 15, and quaternary Hermitian length 13, respectively.Source: §3.2 · p. 8, Table 2 · p. 8

3.3 Generation of LCD codes

  • A coordinate can be deleted by puncturing to retain dimension k when Π_ii ≠ 1, or shortening to retain dimension k−1 when Π_ii ≠ 0; at least one preserves LCD.For q ∈ {2, 4}, exactly one operation preserves LCD; for q = 3, both can when Π_ii is neither 0 nor 1.Source: §3.3 · p. 9

3.4 Canonical augmentation

  • Canonical augmentation applies LCD-preserving deletion and extension to select exactly one representative of every equivalence class.The canonical parent is obtained by deleting the coordinate selected through the canonical labelling; the algorithm builds classifications inductively from length n−1.Source: §3.4 · pp. 9–12

3.5 Verification

  • The results are checked against the mass formula, previously published complete classifications, and counts derived from.The program reproduces the reported earlier classifications and the available counts for binary length 19 and ternary length 15, including specified dimensions.Source: §3.5 · pp. 12–13

4 Results

The results report inequivalent-code counts for newly classified lengths and use mass-formula lower bounds to quantify why the next lengths are impractical to classify and distribute.

4 Results

  • For k = 1, LCD status is equivalent to odd weight for q = 2 or 4, and to weight not divisible by 3 for q = 3.Source: §4 · p. 13
  • Table 3 reports numbers of inequivalent LCD [n, k] codes for the newly classified lengths, with k ≤ n/2.The table covers binary, ternary, and quaternary Hermitian codes.Source: §4 · p. 14, Table 3 · p. 14
  • At lengths 20, 16, and 14, lower bounds are at least 1.2 × 10^12 binary, 7.7 × 10^12 ternary, and 2.3 × 10^12 quaternary Hermitian classes, respectively.By duality, only classes with k ≤ n/2 need to be stored.Source: §4 · p. 14
  • The largest classifications occupy about 191 GB for binary length 19, 139 GB for ternary length 15, and 18 GB for quaternary Hermitian length 13.Even at three bytes per class, the next-length lower bounds imply more than 3.5 TB, 23 TB, and 7 TB, respectively.Source: §4 · p. 14
  • The next lengths cannot be classified in practice because storing and distributing the resulting data would be impractical.The paper states that present storage and distribution capacity sets the stopping point.Source: §4 · p. 15

5 Minimum weights

The section reports the largest minimum weights of LCD codes relative to the largest minimum weights among all codes, for binary, ternary, and quaternary Hermitian cases. It also compares the reported values with prior classifications.

Method and definitions

  • The minimum weights of each code and its dual were computed by exhaustive enumeration of codewords.The section defines dLCD(n, k) as the largest minimum weight among LCD [n, k] codes and compares it with dall(n, k), the largest minimum weight among all [n, k] codes.Source: §5 · pp. 15–16

Binary codes

  • For q = 2 and n ≤ 19, dLCD(n, k) equals dall(n, k) − 2 when (n, k) ∈ S′2, dall(n, k) − 1 when (n, k) ∈ S2, and dall(n, k) otherwise.For q = 2, the values agree with [15, Table 3] for n ≤ 16 and with [2, Table 15] and [7, Table 3] for n = 17.Source: §5 · pp. 15–16

Ternary codes

  • For q = 3 and n ≤15, dLCD(n, k) is dall(n, k) −1 on S3 and dall(n, k) otherwise.The set S3 for n ≤10 coincides with the set in [1, Remark 9], and values for n = 11–15 agree with [4, Table 7].Source: §5 · pp. 15–16

Quaternary Hermitian codes

  • For q = 4 (Hermitian) and n ≤13, dLCD(n, k) is dall(n, k) −1 on S4 and dall(n, k) otherwise.The reported counts for n ≤12 agree with [3, Tables 2–4].Source: §5 · p. 16

6 Conclusion

The paper completes classifications of binary, ternary, and quaternary Hermitian LCD codes through lengths 19, 15, and 13, respectively. The next lengths are constrained by the amount of data that can currently be stored and distributed.

6 Conclusion

  • The classifications cover all dimensions through lengths 19 for binary, 15 for ternary, and 13 for quaternary Hermitian LCD codes.The work reduces equivalence to graph isomorphism on coordinates and generates only LCD codes.Source: §6 · p. 16
  • Several terabytes of generator matrices are projected for the next lengths, making complete classification impractical with present storage and distribution means.One canonical form takes 5–44 microseconds, so data volume rather than the equivalence test now sets the limit; the method itself could extend if storage and transfer become practical.Source: §6 · p. 16
  • Table 4 marks LCD largest minimum weights equal to dall(n, k) −1 with an asterisk and those equal to dall(n, k) −2 with a double asterisk; other entries equal dall(n, k).Source: Table 4 · p. 17
  • For larger lengths, classifications restricted to small dimensions or additional properties such as optimal minimum weight remain feasible, but are not complete classifications in this paper’s sense.Source: §6 · p. 18

A Minimum weight distributions

The appendix tables report numbers of inequivalent LCD codes by field and code parameters. The supplied passages identify binary, ternary, and quaternary Hermitian table entries, but do not provide their numerical counts.

Binary tables

Ternary tables

Quaternary Hermitian table

Loading 2610.30561v1…