Shortest Embeddings of Linear Codes with Arbitrary Hull Dimension

Jiabin Wang; Jinquan Luo

arxiv: 2604.08843 · v1 · submitted 2026-04-10 · 💻 cs.IT · math.IT

Shortest Embeddings of Linear Codes with Arbitrary Hull Dimension

Jiabin Wang , Jinquan Luo This is my paper

Pith reviewed 2026-05-10 18:03 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords linear codeshull dimensionself-orthogonal embeddingsGram matricesquadratic formsfinite fieldsEuclidean inner productHermitian inner product

0 comments

The pith

The minimal length for embedding any linear code into one with prescribed hull dimension t is exactly determined over arbitrary finite fields.

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

The paper determines the shortest lengths at which any given linear code can be embedded into a larger code whose hull has exact dimension t, in both the Euclidean and Hermitian settings. It extends earlier results limited to LCD codes and fully self-orthogonal codes by classifying every linear code according to the congruence class of its Gram matrix and then applying quadratic-form and group-theoretic counting arguments. Constructive algorithms are given for each class and each t, and the self-orthogonal case is settled completely. A reader would care because hull dimension controls many code properties used in cryptography and quantum error correction, so knowing the shortest possible n for any target t lets designers reach desired hull sizes without unnecessary length.

Core claim

By partitioning linear codes into types via congruence equivalence classes of their Gram matrices, the authors obtain closed-form expressions for the shortest embedding length n that realizes any prescribed hull dimension t; these expressions are derived from the theory of quadratic forms over finite fields together with classical group-order calculations, and they improve earlier partial results by completely determining the self-orthogonal case (t equal to the code dimension).

What carries the argument

Congruence equivalence classes of Gram matrices, which partition linear codes into finitely many types and allow the minimal embedding length for each type and each hull dimension t to be read off from quadratic-form invariants.

If this is right

For every linear code and every t there exists a finite algorithm that constructs a shortest t-hull embedding.
The minimal length of self-orthogonal embeddings is now known exactly for all linear codes, closing the gap left by An et al.
The same classification yields optimal codes inequivalent to existing database entries in multiple parameter regimes.
The results hold uniformly for Euclidean and Hermitian inner products over any finite field.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The Gram-matrix typing could be used to enumerate all minimal-length hull-t codes for small q and small t, producing new tables of best-known codes.
Similar quadratic-form techniques might extend the exact-length results to other weight distributions or to trace-inner-product variants.
The constructive algorithms can be turned into software that, given any seed code and target t, outputs a shortest embedding for immediate use in applications.

Load-bearing premise

Every linear code over an arbitrary finite field belongs to one of the congruence classes of Gram matrices, and those classes alone determine the exact minimal embedding length for every hull dimension t.

What would settle it

Exhibiting any linear code over GF(q) together with a t-hull embedding whose length is strictly smaller than the length predicted by the Gram-matrix class formula for that code would falsify the claimed exactness.

read the original abstract

In this paper, we study the shortest $t$-dimensional hull embeddings of linear codes in both Euclidean and Hermitian cases, extending the existing research on the shortest LCD and self-orthogonal embeddings to arbitrary hull dimensions and arbitrary finite fields. We obtain the exact length of such embeddings by adopting tools from quadratic form theory over finite fields and classical group theory. Based on the congruence equivalence class of Gram matrices of linear codes, we classify linear codes into distinct ``types'' and present corresponding constructive algorithms. In particular, we improve the results of An et al. and fully determine the length of the shortest self-orthogonal embeddings for linear codes. Finally, applying these algorithms, we provide examples for various settings and obtain several optimal codes inequivalent to those in the BKLC database.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper classifies linear codes by Gram matrix congruence types to derive exact shortest t-hull embedding lengths over arbitrary finite fields and gives constructive algorithms.

read the letter

This paper gives exact minimal lengths for embeddings of linear codes with any hull dimension t, both Euclidean and Hermitian, over arbitrary finite fields. They do it by sorting the codes into types based on the congruence equivalence class of the Gram matrix, then using quadratic form theory and classical group theory to find the shortest length for each type, along with algorithms to construct them. What stands out is the extension from the LCD case (t=0) and self-orthogonal embeddings to general t. They improve on An et al. by fully determining the shortest self-orthogonal embeddings and provide examples that yield some optimal codes not listed in the BKLC database. The classification approach organizes the problem in a way that makes the constructions systematic. The potential weak point is whether the congruence classes of Gram matrices really partition all linear codes exhaustively for every field and every t. The central claims rest on that being true and on the minimal length within each class being the global minimum. If the paper verifies this completely, the results are solid; otherwise some cases might be missed. The abstract indicates they base it on external results from quadratic forms and group theory, which is fine as long as the application is correct. This is for people in coding theory who care about hull dimensions, like in quantum error correction or self-orthogonal code constructions. A reader looking for explicit algorithms and length formulas will find it useful. It deserves serious refereeing because it claims to close the problem for self-orthogonal embeddings and generalizes the area. I would send it out for peer review to check the completeness of the classification and the derivations.

Referee Report

3 major / 3 minor

Summary. The paper studies shortest t-dimensional hull embeddings of linear codes over arbitrary finite fields in both Euclidean and Hermitian settings. It classifies codes into types via congruence equivalence classes of Gram matrices, applies quadratic form theory and classical group theory to derive exact minimal embedding lengths for each type, provides constructive algorithms, improves prior results on self-orthogonal embeddings, and gives examples of optimal codes.

Significance. If the classification is exhaustive and derivations correct, the work supplies a complete algebraic determination of minimal lengths for arbitrary hull dimension t, extending LCD and self-orthogonal cases to a general framework. The explicit algorithms and examples of new optimal codes represent a concrete advance in constructive coding theory.

major comments (3)

[§3.1–3.2] §3.1–3.2: The central claim that congruence equivalence classes of Gram matrices provide an exhaustive partition of all linear codes over arbitrary finite fields (including all characteristics and extension degrees) is asserted without an explicit proof or reference to a covering theorem; this partition is load-bearing for the exact-length formulas in Theorems 4.1 and 5.2.
[§4.3] §4.3, Theorem 4.5: The improvement over An et al. for self-orthogonal (t=0) embeddings states that lengths are fully determined, yet the group-action arguments are verified only for the listed types; no check is given that the attained minimum is global when the underlying field has characteristic 2 or when the code dimension exceeds the listed bounds.
[§5.1] §5.1, Algorithm 2: The constructive procedure for Hermitian embeddings assumes that every Gram matrix is equivalent to one of the enumerated forms, but the algorithm does not include a verification step or complexity bound; if the enumeration misses a class, the claimed exact length fails for those codes.

minor comments (3)

[Abstract] The abstract claims 'exact lengths are obtained' but the introduction does not state the precise range of t and q for which the results hold; a clarifying sentence would help.
[Table 2] Table 2 reports minimal lengths but omits the corresponding code parameters (n,k,d) for the constructed embeddings; adding these would make the optimality claims easier to verify.
[§2] Notation for the Gram matrix congruence is introduced in §2 but reused with slight variations in §4; a single consistent definition would improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, providing clarifications based on the underlying theory and indicating revisions where they strengthen the presentation without altering the core results.

read point-by-point responses

Referee: [§3.1–3.2] The central claim that congruence equivalence classes of Gram matrices provide an exhaustive partition of all linear codes over arbitrary finite fields (including all characteristics and extension degrees) is asserted without an explicit proof or reference to a covering theorem; this partition is load-bearing for the exact-length formulas in Theorems 4.1 and 5.2.

Authors: The classification of linear codes by congruence classes of their Gram matrices follows directly from the standard theory of symmetric bilinear forms over finite fields, which is exhaustive: every such form is congruent to a unique canonical representative determined by its rank, discriminant, and (in even characteristic) additional invariants. This is a classical result in quadratic form theory (e.g., as summarized in standard references on finite geometries and coding theory). The types enumerated in §3.1–3.2 correspond precisely to these invariants and therefore cover all possible codes over any finite field. To make this explicit, we will add a short paragraph with a reference to the relevant theorem in §3.1. revision: partial
Referee: [§4.3] §4.3, Theorem 4.5: The improvement over An et al. for self-orthogonal (t=0) embeddings states that lengths are fully determined, yet the group-action arguments are verified only for the listed types; no check is given that the attained minimum is global when the underlying field has characteristic 2 or when the code dimension exceeds the listed bounds.

Authors: The listed types exhaust all congruence classes of Gram matrices, including those arising in characteristic 2 (where the associated quadratic forms are handled via the standard Arf invariant or alternating bilinear forms). The group-action arguments determining the minimal orbit sizes apply uniformly to each type via the structure of the orthogonal group over the given field; the minimum length is therefore global by construction. We will add an explicit remark after Theorem 4.5 confirming that the arguments hold for characteristic 2 and for code dimensions beyond the illustrative bounds, supported by the general classification. revision: partial
Referee: [§5.1] §5.1, Algorithm 2: The constructive procedure for Hermitian embeddings assumes that every Gram matrix is equivalent to one of the enumerated forms, but the algorithm does not include a verification step or complexity bound; if the enumeration misses a class, the claimed exact length fails for those codes.

Authors: The enumerated forms in Algorithm 2 are derived from the complete classification of Hermitian Gram matrices (again via quadratic form theory over finite fields of square order), so no classes are missed. Nevertheless, we agree that including an explicit verification step (matching the input matrix invariants to the canonical form) and a complexity analysis (O(n^3) field operations for dimension n) would improve robustness and clarity. We will revise Algorithm 2 and the surrounding text in §5.1 accordingly. revision: yes

Circularity Check

0 steps flagged

No circularity: external algebraic tools determine exact lengths

full rationale

The derivation classifies linear codes by congruence equivalence classes of Gram matrices and applies quadratic form theory over finite fields plus classical group theory to compute minimal embedding lengths for each type. These are standard external mathematical results, not quantities defined from or fitted to the target lengths. Constructive algorithms and improvements on An et al. are presented without any step that renames a fitted parameter as a prediction or reduces the claimed exact lengths to a self-referential input. The approach remains self-contained against independent algebraic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard results from quadratic form theory over finite fields and classical group theory; no new free parameters, ad-hoc axioms, or invented entities are indicated in the abstract.

axioms (2)

standard math Standard theorems of quadratic form theory over finite fields
Invoked to classify Gram matrices and obtain exact embedding lengths
standard math Results from classical group theory
Used together with quadratic forms to determine minimal lengths

pith-pipeline@v0.9.0 · 5418 in / 1269 out tokens · 47862 ms · 2026-05-10T18:03:25.835135+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Based on the congruence equivalence class of Gram matrices of linear codes, we classify linear codes into distinct 'types' and present corresponding constructive algorithms... we fully determine the length of the shortest self-orthogonal embeddings for linear codes.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

we obtain the exact length of such embeddings by adopting tools from quadratic form theory over finite fields and classical group theory.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

J. An, N. Kaplan, J.-L. Kim, J. Luo and G. Wang, Shortest self-orthogonal embeddings of binary linear codes, arXiv:2511.05440, 2025

work page arXiv 2025
[2]

An, J.-H

J. An, J.-H. Hong, J.-L. Kim and H. Lim, Shortest LCD embeddings of binary, ternary and quaternary linear codes, arXiv:2601.20600, 2026

work page arXiv 2026
[3]

E. F. Assmus Jr. and J.D. Key, Affine and projective planes,Discrete Math., vol. 83, pp. 161-187, 1990

work page 1990
[4]

A. R. Calderbank, E. M. Rains, P. Shor, N. J. Sloane, Quantum error correction via codes over GF(4),IEEE Trans. Inf. Theory, vol. 44, no. 4, pp. 1369-1387, Apr. 1998

work page 1998
[5]

Cannon and C

J. Cannon and C. Playoust,An Introduction to Magma.University of Sydney, Sydney, Australia, 1994

work page 1994
[6]

Carlet and S

C. Carlet and S. Guilley, Complementary dual codes for countermeasures to side-channel attacks,Adv. Math. Commun., vol. 10, no. 1, pp. 131-150, 2016

work page 2016
[7]

Chen, On the hull-variation problem of equivalent linear codes,IEEE Trans

H. Chen, On the hull-variation problem of equivalent linear codes,IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 2911-2922, May 2023

work page 2023
[8]

Dastbasteh and P

R. Dastbasteh and P. Lison ˇek, New quantum codes from self-dual codes overF 4,Des. Codes Cryptogr., vol. 92, pp. 787-801, 2024

work page 2024
[9]

L. E. Dickson,Linear Groups with an Exposition of the Galois Field Theory, B.G. Teubner, 1901

work page 1901
[10]

W. Fang, F. -W. Fu, L. Li and S. Zhu, Euclidean and Hermitian hulls of MDS codes and their applications to EAQECCs, IEEE Trans. Inf. Theory, vol. 66, no. 6, pp. 3527-3537, June 2020

work page 2020
[11]

Frederic Ezerman, M

M. Frederic Ezerman, M. Grassl, S. Ling, F. ¨Ozbudak, and B. ¨Ozkaya, Characterization of nearly self-orthogonal quasi-twisted codes and related quantum codes,IEEE Trans. Inf. Theory, vol. 71, no. 1, pp. 499-517, Jan. 2025

work page 2025
[12]

Gluesing-Luerssen and A

H. Gluesing-Luerssen and A. Ravagnani,ℓ-Complementary subspaces and codes in finite bilinear spaces,IEEE Trans. Inf. Theory, vol. 70, no. 4, pp. 2443-2455, Apr. 2024

work page 2024
[13]

L. C. Grove,Classical Groups and Geometric Algebra, Providence, RI: American Mathematical Society, 2002

work page 2002
[14]

M. A. Hossain and R. Bandi, LCD codes as a counter-measure for relevant security threats: a survey,2021 19th OITS International Conference on Information Technology (OCIT), Bhubaneswar, India, pp. 302-307, 2021

work page 2021
[15]

W. C. Huffman and V . Pless,Fundamentals of Error-Correcting Codes. Cambridge, U.K.: Cambridge Univ. Press, 2003

work page 2003
[16]

J. -L. Kim, Y . -H. Kim and N. Lee, Embedding linear codes into self-orthogonal codes and their optimal minimum distances, IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 3701-3707, June 2021

work page 2021
[17]

Li and P

C. Li and P. Zeng, Construction of linear codes with one-dimensional hull,IEEE Trans. Inf. Theory, vol. 65, no. 3, pp. 1668-1676, March 2019

work page 2019
[18]

R. Li, Z. Xu and X. Zhao, On the classification of binary optimal self-orthogonal codes,IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3778-3782, Aug. 2008

work page 2008
[19]

S. Li, M. Shi, and S. Ling, A mass formula for linear codes with prescribed hull dimension and related classification,IEEE Trans. Inf. Theory,vol. 71, no. 1, pp. 273-286, Jan. 2025

work page 2025
[20]

S. Li, M. Shi, Y . Li, and S. Ling, A further study on the mass formula for linear codes with prescribed hull dimension, arXiv:2410.13578, 2024

work page arXiv 2024
[21]

J. L. Massey, Linear codes with complementary duals,Discrete Math., vol. 106-107, pp. 337-342, 1992

work page 1992
[22]

Sok, On linear codes with one-dimensional Euclidean hull and their applications to EAQECCs,IEEE Trans

L. Sok, On linear codes with one-dimensional Euclidean hull and their applications to EAQECCs,IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4329-4343, July 2022

work page 2022
[23]

Wang and Z

X. Wang and Z. Heng, Several families of self-orthogonal codes and their applications in optimal quantum codes and LCD codes,IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4769-4791, July 2024

work page 2024
[24]

Wan.Introduction to Algebra(in Chinese)

Z. Wan.Introduction to Algebra(in Chinese). Science Press, Beijing, 2004

work page 2004
[25]

C. Xie, H. Chen, H. Zhou, Y . Li and H. Lao, Optimal, almost optimal few-weight linear codes and related quantum codes, IEEE Trans. Inf. Theory, vol. 71, no. 6, pp. 4250-4259, June 2025

work page 2025

[1] [1]

J. An, N. Kaplan, J.-L. Kim, J. Luo and G. Wang, Shortest self-orthogonal embeddings of binary linear codes, arXiv:2511.05440, 2025

work page arXiv 2025

[2] [2]

An, J.-H

J. An, J.-H. Hong, J.-L. Kim and H. Lim, Shortest LCD embeddings of binary, ternary and quaternary linear codes, arXiv:2601.20600, 2026

work page arXiv 2026

[3] [3]

E. F. Assmus Jr. and J.D. Key, Affine and projective planes,Discrete Math., vol. 83, pp. 161-187, 1990

work page 1990

[4] [4]

A. R. Calderbank, E. M. Rains, P. Shor, N. J. Sloane, Quantum error correction via codes over GF(4),IEEE Trans. Inf. Theory, vol. 44, no. 4, pp. 1369-1387, Apr. 1998

work page 1998

[5] [5]

Cannon and C

J. Cannon and C. Playoust,An Introduction to Magma.University of Sydney, Sydney, Australia, 1994

work page 1994

[6] [6]

Carlet and S

C. Carlet and S. Guilley, Complementary dual codes for countermeasures to side-channel attacks,Adv. Math. Commun., vol. 10, no. 1, pp. 131-150, 2016

work page 2016

[7] [7]

Chen, On the hull-variation problem of equivalent linear codes,IEEE Trans

H. Chen, On the hull-variation problem of equivalent linear codes,IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 2911-2922, May 2023

work page 2023

[8] [8]

Dastbasteh and P

R. Dastbasteh and P. Lison ˇek, New quantum codes from self-dual codes overF 4,Des. Codes Cryptogr., vol. 92, pp. 787-801, 2024

work page 2024

[9] [9]

L. E. Dickson,Linear Groups with an Exposition of the Galois Field Theory, B.G. Teubner, 1901

work page 1901

[10] [10]

W. Fang, F. -W. Fu, L. Li and S. Zhu, Euclidean and Hermitian hulls of MDS codes and their applications to EAQECCs, IEEE Trans. Inf. Theory, vol. 66, no. 6, pp. 3527-3537, June 2020

work page 2020

[11] [11]

Frederic Ezerman, M

M. Frederic Ezerman, M. Grassl, S. Ling, F. ¨Ozbudak, and B. ¨Ozkaya, Characterization of nearly self-orthogonal quasi-twisted codes and related quantum codes,IEEE Trans. Inf. Theory, vol. 71, no. 1, pp. 499-517, Jan. 2025

work page 2025

[12] [12]

Gluesing-Luerssen and A

H. Gluesing-Luerssen and A. Ravagnani,ℓ-Complementary subspaces and codes in finite bilinear spaces,IEEE Trans. Inf. Theory, vol. 70, no. 4, pp. 2443-2455, Apr. 2024

work page 2024

[13] [13]

L. C. Grove,Classical Groups and Geometric Algebra, Providence, RI: American Mathematical Society, 2002

work page 2002

[14] [14]

M. A. Hossain and R. Bandi, LCD codes as a counter-measure for relevant security threats: a survey,2021 19th OITS International Conference on Information Technology (OCIT), Bhubaneswar, India, pp. 302-307, 2021

work page 2021

[15] [15]

W. C. Huffman and V . Pless,Fundamentals of Error-Correcting Codes. Cambridge, U.K.: Cambridge Univ. Press, 2003

work page 2003

[16] [16]

J. -L. Kim, Y . -H. Kim and N. Lee, Embedding linear codes into self-orthogonal codes and their optimal minimum distances, IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 3701-3707, June 2021

work page 2021

[17] [17]

Li and P

C. Li and P. Zeng, Construction of linear codes with one-dimensional hull,IEEE Trans. Inf. Theory, vol. 65, no. 3, pp. 1668-1676, March 2019

work page 2019

[18] [18]

R. Li, Z. Xu and X. Zhao, On the classification of binary optimal self-orthogonal codes,IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3778-3782, Aug. 2008

work page 2008

[19] [19]

S. Li, M. Shi, and S. Ling, A mass formula for linear codes with prescribed hull dimension and related classification,IEEE Trans. Inf. Theory,vol. 71, no. 1, pp. 273-286, Jan. 2025

work page 2025

[20] [20]

S. Li, M. Shi, Y . Li, and S. Ling, A further study on the mass formula for linear codes with prescribed hull dimension, arXiv:2410.13578, 2024

work page arXiv 2024

[21] [21]

J. L. Massey, Linear codes with complementary duals,Discrete Math., vol. 106-107, pp. 337-342, 1992

work page 1992

[22] [22]

Sok, On linear codes with one-dimensional Euclidean hull and their applications to EAQECCs,IEEE Trans

L. Sok, On linear codes with one-dimensional Euclidean hull and their applications to EAQECCs,IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4329-4343, July 2022

work page 2022

[23] [23]

Wang and Z

X. Wang and Z. Heng, Several families of self-orthogonal codes and their applications in optimal quantum codes and LCD codes,IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4769-4791, July 2024

work page 2024

[24] [24]

Wan.Introduction to Algebra(in Chinese)

Z. Wan.Introduction to Algebra(in Chinese). Science Press, Beijing, 2004

work page 2004

[25] [25]

C. Xie, H. Chen, H. Zhou, Y . Li and H. Lao, Optimal, almost optimal few-weight linear codes and related quantum codes, IEEE Trans. Inf. Theory, vol. 71, no. 6, pp. 4250-4259, June 2025

work page 2025