Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Characterization and classification of optimal LCD codes

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A simplex-code identity classifies all optimal binary and ternary LCD codes

desk verdict Solid small-table completion with a real structural reduction; the only serious caveat is that the arbitrary-n claims lean on unshipped exhaustive searches. read the letter →

arxiv 1908.03294 v3 pith:VYYBQAN7 submitted 2019-08-09 math.CO cs.ITmath.IT

Makoto Araya , Masaaki Harada , Ken Saito This is my paper · ORCID
classification math.COcs.ITmath.IT MSC 94B0594B65
keywords LCDcodeslinearcomplementarydualminimumweightoptimalsimplexdistanceGriesmerboundcodeclassification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a structural correspondence for linear complementary dual (LCD) codes over the binary and ternary fields with large minimum weight: every such code is built from a self-orthogonal simplex block plus a shorter LCD tail, and this decomposition is unique up to equivalence. Carried by the simplex code's columns, the correspondence maps an LCD [n,k,d] code with dual distance at least 2 to an LCD [q*r, k, (q-1)r] code, where r = $q^{{k-1}}$n - [k]_q d. Because the map is a bijection on equivalence classes, nonexistence and classifications proved for small lengths propagate to every length in the same residue family. The paper uses this to determine, for arbitrary n, the largest minimum weights d_2(n,4), d_3(n,2), d_3(n,3) and to classify all optimal LCD codes for (q,k) equal to (2,3), (2,4), (3,2), and (3,3).

What carries the argument

The carrying object is the simplex code S_{q,k}: a generator matrix whose columns are the nonzero projective vectors, arranged so the code is self-orthogonal and constant-weight, with length [k]_q = (q^k - 1)/(q - 1) and minimum weight $q^{{k-1}}$. Any LCD code with dual distance at least 2 is equivalent to a code C_{q,k}(m) built by repeating these columns according to multiplicities m_i. Lemma 3.6 bounds each multiplicity using the symmetric 2-design formed by the simplex supports, giving qd - (q-1)n <= m_i and an upper bound in terms of d. Lemma 3.5 shows that adjoining s copies of the simplex block raises the length by [k]_q s and the minimum weight by $q^{{k-1}}$s while preserving the LCD property. Together these produce the bijection of Theorem 4.5, so that classifying base codes of length q*r automatically classifies all codes of length [k]_q s + t in the family.

What would settle it

Run an independent exhaustive search for a binary LCD [16,4,8] code with dual distance at least 2: the paper's claimed value d_2(16,4)=7 says no such code exists, so finding one would break the nonexistence propagation chain for the n=15s+1 family. Equivalently, enumerate all multiplicity vectors m satisfying the bounds (9) for (q,k,n,d)=(2,4,16,8) and check the LCD condition; any survivor is a direct counterexample.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 4.5: under the conditions qd - (q-1)n >= 1, k >= k0 with (q,k0) in {(2,3), (3,2)}, and q*r >= k, where r = $q^{{k-1}}$n - [k]_q d, there is a one-to-one correspondence between equivalence classes of LCD [n,k,d] codes over F_q with dual distance at least 2 and equivalence classes of LCD [q*r, k, (q-1)r] codes with dual distance at least 2. In the modified form of Theorem 4.7, writing n = [k]_q s + t and d = $q^{{k-1}}$s + $\alpha$(t), the classification of optimal codes for all lengths in that residue class is exactly the classification of the finite base code with parameters [q*r, k, (q-1)r], and nonexistence at the base length rules out the whole infinite family. The paper applies this to prove explicit formulas for d_2(n,4), d_3(n,2), and d_3(n,3), and to give a complete classification of optimal LCD codes for the four listed parameter families, with counts of inequivalent codes that are eventually periodic in the length n.

Load-bearing premise

The load-bearing premise is that the exhaustive computer searches at the small base lengths found every relevant code and counted equivalence classes correctly; a single missed code at a base length would invalidate the conclusions for infinite families, and the search programs are not shipped.

Editorial extensions

If this is right

  • For every length n, the largest minimum weights d_2(n,4), d_3(n,2), and d_3(n,3) are determined by explicit formulas depending only on n modulo 15, 4, and 13 respectively, e.g., d_2(n,4) = floor(8n/15) for n congruent to 5, 9, or 13 mod 15, and floor(8n/15) - 2 for n divisible by 15.
  • The complete classification of optimal LCD codes for (q,k) in {(2,3), (2,4), (3,2), (3,3)} is finite in each residue class: for each residue of n modulo [k]_q, the number of inequivalent optimal codes with dual distance at least 2 becomes constant for all large enough n, with the paper giving the exact counts.
  • Because the correspondence is a bijection on equivalence classes, any future independent classification of the short base lengths [q*r, k, (q-1)r] automatically upgrades to a full classification for all lengths in the corresponding residue family without any new search.
  • The nonexistence part of the theorem rules out Griesmer-bound-attaining LCD codes for infinite families, such as binary LCD [15s, 4, 8s] codes and ternary LCD [13s, 3, 9s] codes for every positive integer s.
  • The classification data from small lengths is enough to certify optimality for arbitrarily large n: the paper's results settle d_q(n,k) and the number of optimal codes for every n in the covered families, not just up to some finite cutoff.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same 'self-orthogonal constant-weight block plus LCD tail' decomposition could be adapted to other code classes that contain a self-orthogonal constant-weight subcode, potentially yielding analogous propagation of classification results for near-MDS codes or codes with prescribed dual distances.
  • Editorial inference: the periodic structure implies that the asymptotic number of inequivalent optimal LCD codes for fixed q and k is governed by finitely many constants, so the classification problem does not grow harder with n once the base lengths are resolved.
  • Editorial inference: providing machine-checkable certificates, or publishing the exhaustive-search programs, for the base-length nonexistence statements would convert the computational part of the proof into independently verifiable evidence; the present paper states the search results but does not ship the code.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper studies LCD codes over F2 and F3. The main theoretical result, Theorem 4.5, establishes a one-to-one correspondence between equivalence classes of LCD [n,k,d] codes with dual distance at least 2 and equivalence classes of LCD [q r, k, (q-1) r] codes with dual distance at least 2, where r = q^{k-1} n - [k]_q d, under the assumptions (q,k0) in {(2,3),(3,2)}, k >= k0, qd-(q-1)n >= 1, and q r >= k. This reduces classification and nonexistence for infinite families of lengths to finite base cases. Using Theorem 4.7 (a reformulation adapted to the residue-class structure of the lengths) and exhaustive computer searches over the m-vectors satisfying (9), the paper determines the largest minimum weights d_q(n,k) for (q,k) in {(2,4),(3,2),(3,3)} and gives classifications of optimal LCD codes for (q,k) in {(2,3),(2,4),(3,2),(3,3)} for all n.

Significance. If the computational base cases are correct, the paper settles the optimal-LCD classification problem for the four small-dimension families over F2 and F3, a genuinely useful contribution given the recent interest in LCD codes. The theoretical reduction in Theorem 4.5 is elegant and parameter-free: it derives the correspondence from the structure of simplex codes and symmetric designs (Lemma 3.6) and avoids relying on previously conjectured bounds. The proof of the correspondence is checkable and the algebra leading to r and (q-1)r is clean. The classification tables and the explicit lists of optimal codes are valuable data. The main risk is that the arbitrary-n results rest on an exhaustive-search foundation that is not independently verifiable from the manuscript; this is a correctness risk rather than a mere reproducibility inconvenience, because Theorem 4.7 propagates every base-case count or nonexistence to all lengths in the residue class.

major comments (2)
  1. [Section 5, Theorem 4.7] The exhaustive enumeration over all m-vectors satisfying (9) is the load-bearing computational premise for the arbitrary-n results. The text reports that all such vectors were considered and that NTL determinant checks and nauty equivalence tests were used, and that Magma verified that the reported codes are LCD and inequivalent; but no search program, search log, or certificate of completeness is provided. Magma verification of the codes that were found does not certify that no other m-vector was missed, and a single missed vector at a base length (for example, one that would yield a binary [16,4,8] or [30,4,15] code, or a ternary [3r,3,2r] code for r in {4,6,7,8,9}) would change a classification count or a nonexistence statement that Theorem 4.7 then propagates to every length in the corresponding residue class. Please make the search programs available or supply a machine-checkable certificate (or an independent full computation) that the enumerations in Propositions 6.1, 6.4, 6.6, 7.4, 7.7, and 7.9 are complete.
  2. [Propositions 6.2, 6.7, 7.5, 7.10 (classification statements)] The paper claims a complete classification of optimal LCD codes, but the stated counts and the tables N_q(n,k) refer only to codes with dual distance at least 2. Since d_q(n,k)=d_q(n-1,k) for several residue classes (for example, d2(7s+1,3)=d2(7s,3) and d2(15s,4)=d2(15s-1,4)), zero-padding every optimal code of length n-1 yields additional optimal codes of length n with dual distance 1, and these are not included in the listed numbers. Lemma 3.1 is invoked, but the paper should state explicitly how these padded classes are part of the classification and, if the classification is meant to enumerate all equivalence classes, provide the total counts or an explicit recursive description of the full set of optimal codes for each length.
minor comments (4)
  1. [Proposition 7.9] The statement says 'ternary LCD [3r,2,2r] codes' but the dimension should be 3, as is clear from the context and from the table of parameters in the same subsection.
  2. [Lemma 4.1 / Theorem 4.5] The proof that the constructed short code C0 has dual distance at least 2 is omitted. This holds because the columns of G0 are a subset of the columns of G and C has no zero columns, but the argument should be stated explicitly given that Theorem 4.5(i) includes the condition d^⊥ >= 2 on both sides of the correspondence.
  3. [Section 5] The canonical condition m1,m2,m4 >= 1 (and the analogous conditions for the other cases) should be justified in one sentence: these indices correspond to the unit coordinate columns in the recursive ordering of the simplex matrix S_{q,k}, so any code with dual distance at least 2 can be brought to this form.
  4. [Equation (16)] The definition of s' via the fraction (qr - t)/[k]_q + 1 is less transparent than the equivalent identity qr = [k]_q(s' - 1) + t used in the proof of Theorem 4.7; introducing the latter earlier would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 4.5 is proved from simplex-code design bounds and elementary linear-algebra lemmas; infinite-family results are propagated from finite base classifications, not assumed.

full rationale

The derivation chain is not circular. Theorem 4.5's one-to-one correspondence is proved in Lemmas 4.1, 4.3, and 4.4 from Lemma 3.6, whose bound (9) follows from the standard Assmus-Mattson 2-design of the simplex code and the design inequality (8), and from elementary generator-matrix arguments. The parameter r = q^{k-1}n - [k]_q d is algebraically derived, not fitted: Lemma 4.1 shows that after removing (qd-(q-1)n) copies of each simplex column, the residual code has length q.r and minimum weight (q-1)r, so the reduction is not a renaming or a fitted input called a prediction. The later sections apply Theorem 4.7 to finite base classifications and nonexistences (Tables 2, 5, 9, 15), obtained either by the paper's own exhaustive search 'by considering all possible vectors m satisfying the above condition and (9)' or cited from earlier computational papers [1], [2], [12]. These citations overlap with the authors, but they are parameter-free, externally falsifiable finite checks and do not assume the present theorem's target conclusions. The main genuine limitation is stated in the text: 'All computer calculations in this paper were done by programs in the language C' and no exhaustive-search certificate is shipped, so completeness of the Section 5 enumeration is not independently auditable. That is a correctness, reproducibility, and verification risk, not circularity. No equation in the paper reduces to its own input, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no fitted constants and no new entities. Its theoretical reduction uses standard facts about simplex codes, symmetric designs, and coding bounds. The central results additionally depend on the correctness of prior classifications from the same group and on the exhaustiveness of new computer searches, both of which are treated as domain assumptions rather than as theorems proved in this paper.

assumptions (7)
  • standard math The generator matrix criterion G G^T nonsingular characterizes LCD codes (Proposition 2.1, due to Massey).
    Used throughout the paper to test whether a code with a given generator matrix is LCD.
  • standard math The simplex code columns realize a symmetric 2-([k]_q, q^(k-1), (q-1)q^(k-2)) design for k >= k0 via the Assmus-Mattson theorem.
    This is the foundation of the bounds in Lemma 3.6.
  • standard math Every equidistant linear code is equivalent to repetitions of the simplex code (Bonisoli's theorem).
    Used in Lemma 3.4 and in the canonical form C_{q,k}(m) for codes with dual distance at least 2.
  • standard math The symmetric-design inequality (8) from [3, Lemma 3.1] bounds each block entry when every point is covered at least d times.
    Applied verbatim in Lemma 3.6 to obtain the lower and upper bounds on m_i.
  • standard math The Griesmer bound and sphere-packing bound give standard upper bounds on minimum weight and on length when minimum weight is at least 3.
    Used to set g_q(n,k), to justify optimality, and to compute dual distances in the remarks.
  • domain assumption Prior classifications and bounds from [1], [2], [12], and [13] are correct.
    Base-case counts and lower/upper bounds for d_2(n,3), d_2(n,4), d_3(n,2), and d_3(n,3) are taken from these papers, several by the same authors.
  • domain assumption The finite computer searches in Section 5 are exhaustive and correctly identify inequivalent codes.
    The arbitrary-n results propagate from these searches via Theorem 4.7; the search programs are not included.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Characterization and classification of optimal LCD codes." pith.science (2026). https://pith.science/paper/VYYBQAN7

@misc{pith2026190803294,
  author       = {Pith},
  title        = {Pith review of: Characterization and classification of optimal LCD codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VYYBQAN7}},
  note         = {Machine review of arXiv:1908.03294}
}
abstract

Linear complementary dual (LCD) codes are linear codes that intersect with their dual trivially. We give a characterization of LCD codes over $\mathbb{F}_q$ having large minimum weights for $q \in \{2,3\}$. Using the characterization, we determine the largest minimum weights among LCD $[n,k]$ codes over $\mathbb{F}_q$ for $(q,k) \in \{(2,4), (3,2),(3,3)\}$. Moreover, we give a complete classification of optimal LCD $[n,k]$ codes over $\mathbb{F}_q$ for $(q,k) \in \{(2,3), (2,4), (3,2),(3,3)\}$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the minimum weights of binary LCD codes and ternary LCD codes

    cs.IT 2019-08 conditional novelty 5.0 of 10

    Exact values and bounds for the optimal minimum weight of binary and ternary linear complementary dual codes are established for new infinite families, and several previously published values are corrected.

Reference graph

Works this paper leans on

21 extracted references · 12 canonical work pages · cited by 1 Pith paper

  1. [20]

    B. Pang, S. Zhu and X. Kai, Some new bounds on LCD codes over fi nite fields, Cryptogr. Commun. 12 (2020), 743–755. 33

    work page 2020

  2. [1]

    Araya and M

    M. Araya and M. Harada, On the classification of linear complement ary dual codes, Discrete Math. 342 (2019), 270–278

    2019

  3. [2]

    Araya and M

    M. Araya and M. Harada, On the minimum weights of binary linear complementary dual codes, Cryptogr. Commun. 12 (2020), 285–300

    2020

  4. [3]

    Araya, M

    M. Araya, M. Harada and K. Saito, Quaternary Hermitian linear co m- plementary dual codes, IEEE Trans. Inform. Theory 66 (2020), 2751– 2759

    work page 2020

  5. [4]

    Bonisoli, Every equidistant linear code is a sequence of dual Ham ming codes, Ars Combin

    A. Bonisoli, Every equidistant linear code is a sequence of dual Ham ming codes, Ars Combin. 18 (1984), 181–186

    work page 1984

  6. [5]

    Bosma, J

    W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235–265

    1997

  7. [6]

    Cameron and J.H

    P.J. Cameron and J.H. van Lint, Designs, Graphs, Codes and Their Links, Cambridge University Press, Cambridge, 1991

    work page 1991

  8. [7]

    Carlet and S

    C. Carlet and S. Guilley, Complementary dual codes for counter- measures to side-channel attacks, Adv. Math. Commun. 10 (2016), 131– 150. 32

    work page 2016

Show all 21 references
  1. [8]

    Carlet, S

    C. Carlet, S. Mesnager, C. Tang and Y. Qi, New characterization and parametrization of LCD codes, IEEE Trans. Inform. Theory 65 (2019), 39–49

    2019

  2. [9]

    Carlet, S

    C. Carlet, S. Mesnager, C. Tang, Y. Qi and R. Pellikaan, Linear co des over Fq are equivalent to LCD codes for q > 3, IEEE Trans. Inform. Theory 64 (2018), 3010–3017

    2018

  3. [10]

    Q. Fu, R. Li, F. Fu and Y. Rao, On the construction of binary opt i- mal LCD codes with short length, Internat. J. Found. Comput. Sci. 30 (2019), 1237–1245

    2019

  4. [11]

    Galvez, J.-L

    L. Galvez, J.-L. Kim, N. Lee, Y.G. Roe and B.-S. Won, Some bounds on binary LCD codes, Cryptogr. Commun. 10 (2018), 719–728

    2018

  5. [12]

    Harada and K

    M. Harada and K. Saito, Binary linear complementary dual codes , Cryp- togr. Commun. 11 (2019), 677–696

    2019

  6. [13]

    Harada and K

    M. Harada and K. Saito, Remark on subcodes of linear complemen tary dual codes, Inform. Process. Lett. 159 (2020), 105963 (3 pp.)

    2020

  7. [14]

    Huffman and V

    W.C. Huffman and V. Pless, Fundamentals of Error-Correcting C odes, Cambridge University Press, Cambridge, (2003)

    2003

  8. [15]

    Lina, Jr

    E.R. Lina, Jr. and E.G. Nocon, On the construction of some LCD c odes over finite fields, Manila J. Science 9 (2016), 67–82

    2016

  9. [16]

    L. Lu, R. Li, L. Guo and Q. Fu, Maximal entanglement entangleme nt- assisted quantum codes constructed from linear codes, Quantum Inf. Process. 14 (2015), 165–182

    2015

  10. [17]

    Maruta, On the achievement of the Griesmer bound, Des

    T. Maruta, On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997), 83–87

    1997

  11. [18]

    Massey, Linear codes with complementary duals, Discrete Math

    J.L. Massey, Linear codes with complementary duals, Discrete Math. 106/107 (1992), 337–342

    1992

  12. [19]

    McKay and A

    B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Sym- bolic Comput. 60 (2014), 94–112

    2014

  13. [21]

    Shoup, NTL: A Library for doing Number Theory, Available onlin e at http://www.shoup.net/ntl/

    V. Shoup, NTL: A Library for doing Number Theory, Available onlin e at http://www.shoup.net/ntl/. 34

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.