CS Paper Radar

Euclidean and Hermitian Self-Orthogonal Codes from Divisible Codes

Ziling Heng, Chenkun Xie

cs.IT ·submitted 2026-11-10 12:01 UTC · v2
theory

Abstract

Self-orthogonality and divisibility are two fundamental properties of linear codes, and the relationship between them has long been of interest. Huffman and Pless (2003) showed that every binary \(4\)-divisible code is Euclidean self-orthogonal, that a ternary code is Euclidean self-orthogonal if and only if it is \(3\)-divisible, and that a quaternary code is Hermitian self-orthogonal if and only if it is \(2\)-divisible. The general case remained open for a long time. In 2024, Li and Heng settled the odd-characteristic case, proving that every \(p\)-divisible code over \(\F_{p^m}\), with \(p\) odd, that contains the all-one vector is Euclidean self-orthogonal. In this paper we treat the even-characteristic case: we prove that every \(4\)-divisible code over \(\F_{2^m}\) containing the all-one vector is Euclidean self-orthogonal. We also prove that, for every prime \(p\), every \(p\)-divisible linear code over \(\F_{q^2}\), where \(q=p^m\), that contains the all-one vector is Hermitian self-orthogonal. In addition, we generalize the Hermitian criterion to the Galois self-orthogonal case, proving that any $p$-divisible linear code over $\gf_{q^r}$ that contains the all-one vector is $\ell$-Galois self-orthogonal for \(\ell\in\{1,\dots,r-1\}\). These criteria make the construction of self-orthogonal codes from divisible codes simple and efficient. As applications, we recover the known Euclidean and Hermitian self-orthogonality of generalized Reed--Muller codes and obtain several infinite families of new Euclidean and Hermitian self-orthogonal codes, which give rise to infinite families of quantum codes with excellent parameters.

Comment
26 pages

Closest papers

Nearest neighbours by meaning across the whole index.

An integer determinant approach to the length of Type II codes and the weights of shadows

cs.IT ·2026-10-22 ·Jae-Hyun Baek, Jon-Lark Kim
theory similarity 0.74
Abstract · 10 pages

It is well known that the length $n$ of a binary Type II code is divisible by $8$. The classical proof relies on Gleason's theorem on weight enumerators. Motivated by a question of Vera Pless, we give elementary proofs of this fact that avoid invariant theory. Our main tool is a congruence modulo $8$ for the determinant of the integer Gram matrix $AA^{\mathsf T}$ of a binary orthogonal matrix $A$, obtained directly from the Leibniz expansion. It gives a short proof of a theorem of Janusz: the number of rows of weight congruent to $3 \pmod 4$ in a binary orthogonal matrix is divisible by $4$. From this single statement we derive both the length restriction for Type II codes and the theorem of Conway and Sloane that every vector in the shadow of a binary self-dual code of length $n$ has weight congruent to $n/2 \pmod 4$. We also give two short character-theoretic proofs of the length restriction and explain how all of these arguments detect the Arf invariant of a quadratic form.

0.30

Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic

cs.IT ·2026-10-06 ·Martin R. Albrecht, Benjamin Benčina, Russell W. F. Lai
position similarity 0.73
Abstract

We give an algorithm that samples uniformly random linear codes of any hull dimension and type over finite fields of odd characteristic, implying the first algorithm for sampling uniformly random self-orthogonal codes of any rate, including self-dual codes. Our algorithm is a re-visitation of the algorithm given by Albrecht, Benčina and Lai (EC'25), using the mass formulae proven by Li, Shi and Ling (IEEE Trans. Inf. Theory 71(1)). This allows us to instantiate code-based cryptographic schemes that rely on the hardness of Permutation Code Equivalence (PCE) on `random' self-dual codes for security and that were previously unable to sample them. Building on the observation by Bardet, Otmani and Saeed-Taha (ISIT'19) that Euclidean orthogonality is insufficient when considering PCE over finite extension fields due to non-trivial Galois automorphisms, we study the behaviour of what we call total orthogonality, that is orthogonality with respect to all induced Galois geometries simultaneously. We characterise total orthogonality of vectors and codes, and give an algorithm that samples linear codes with a total hull of a prescribed dimension; a subcode that acts as the hull in all Galois geometries of the ambient space. The algorithm incurs a rate decrease by a factor equal to the extension degree, however, we argue why this may be necessary in the context of PCE and explore how it limits the practicality of our algorithm. We consider the notion of Galois type of a linear code when Galois hulls are symmetric and show that all linear codes have constant Hermitian type.

0.43

Optimal self-orthogonal binary linear codes

cs.DM math.COcs.IT ·2026-10-29 ·Sascha Kurz
theory similarity 0.71
Abstract · 39 pages; comments more than welcome

We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.

0.24

Self-Orthogonal MDS Principal-Ideal Codes

cs.IT ·2026-11-19 ·Yangcheng Li, Pingzhi Yuan
theory similarity 0.71
Abstract · 15 pages

We investigate Euclidean self-orthogonality and the generalized Reed--Solomon (GRS) property for coefficient-vector codes generated by a monic polynomial $g$ and its shifts $xg,\ldots,x^{k-1}g$, of length $n=r+k$ and dimension $k$, where $°g=r$ and $3\le k\le r$. We give a complete classification, over any algebraically closed field, of the generators for which these codes are both self-orthogonal and GRS. Such generators have either distinct roots in a geometric progression satisfying explicit order and scalar conditions, or a single repeated root in certain positive characteristics. In particular, only finitely many generators occur for fixed $r$, $k$, and characteristic. We determine their maximal self-orthogonal lengths, show that the corresponding maximal-length codes are cyclic or negacyclic, and obtain exact generator counts over finite fields, together with the least fields of definition. In contrast, when $3\le k<r$, we prove that every algebraically closed field supports infinitely many pairwise monomially inequivalent self-orthogonal non-GRS maximum distance separable (MDS) codes in this family. Consequently, arbitrarily many such codes can be realized over a common finite extension of any prescribed finite field, while remaining inequivalent and non-GRS over its algebraic closure.

0.16

Further Study of p-Ary Self-Orthogonal Codes From Square Functions

cs.IT ·2026-10-26 ·Tingting Wu, Xianhong Xie
similarity 0.70
Abstract

In this paper, we investigate a family of trace codes over finite fields of odd characteristic defined by two quadratic trace conditions. By analyzing the quadratic forms associated with these trace conditions and evaluating the corresponding character sums, we obtain the parameters and complete weight distributions of the codes. We further exploit the natural multiplicative orbit structure of the defining sets to obtain punctured codes and determine their parameters, weight distributions and dual distances. Moreover, we establish self?orthogonality criteria and investigate divisibility and projectivity of the constructed codes. These results give a unified treatment for arbitrary odd prime fields and for extension degrees of both parities.

0.25

Non-additive symmetric rank-metric codes

cs.IT math.CO ·2026-10-13 ·Marta Messia, Ferdinando Zullo
theory similarity 0.68
Abstract

We study non-additive rank-metric codes contained in the space of symmetric matrices over a finite field. Our main focus is on symmetric $2$-codes. For odd $q$, we introduce a quotient construction for $\mathrm{Sym}_3(q)$ in which rank-one differences are described by isotropic vectors of a nondegenerate quadratic form on $\mathbb F_q^4$. This leads to a correspondence with partial ovoids of the elliptic quadric $Q^-(5,q)$. Using a construction of Cossidente and Pavese, we obtain a non-additive symmetric $2$-code in $\mathrm{Sym}_3(q)$ of cardinality $q^4+2q^3$, improving the previously known general lower bound. We also give an explicit matrix description of this family. Lastly, we present a block-based construction for symmetric $2$-codes that extends the three-dimensional improvement to all odd dimensions. In particular, for every odd $n\geq3$ and every prime power $q>2$, we obtain \begin{equation*} A_q^{\rm sym}(n,2) \ge q^{(n^2-1)/2}+q^{(n^2-3)/2}+q^{(n^2-9)/2}, \end{equation*} which is strictly larger than the maximum cardinality of an additive symmetric $2$-code with the same parameters. This yields the first infinite family (as the matrix dimension $n$ varies) of non-additive symmetric $2$-codes whose size is larger than the largest achievable size of an additive code with the same parameters; before this, such a gap had only been established for $n=3$.

0.43

Shortest self-orthogonal and LCD embeddings of linear codes over Fq+uFq

cs.IT ·2026-08-28 ·Junmin An, Jon-Lark Kim
similarity 0.68
Abstract

This paper determines the exact lengths of shortest self-orthogonal and LCD embeddings of linear codes over $\mathbb{F}_q+u\mathbb{F}_q$. By decomposing Gram matrices over $\mathbb{F}_q+u\mathbb{F}_q$ into pairs of symmetric matrices over the finite field $\mathbb{F}_q$, the embedding problems are reduced to the congruence classification of symmetric and alternate matrices over finite fields. Complete formulas for the shortest self-orthogonal embedding length are obtained, with two distinct cases arising in both even and odd characteristic. We also show that every self-orthogonal code over $\mathbb{F}_q+u\mathbb{F}_q$ with nonzero free rank can be viewed as a shortest self-orthogonal embedding of another code. We use Witt theory to construct all shortest self-orthogonal embeddings. A complete characterization of shortest LCD embeddings is also established in terms of invertible and arbitrary matrices of prescribed sizes appended to a generator matrix. Examples of self-orthogonal and LCD embeddings with the largest minimum distance for the code considered are also presented, some of whose Gray images are optimal codes over $\mathbb{F}_q$.

0.39

Cyclic triorthogonal codes in prime dimension

cs.IT quant-ph ·2026-10-06 ·Shiroman Prakash
theorycode/data similarity 0.68
Abstract · 24 pages, 2 tables. Code and data: https://github.com/spdei/cyclic-triorthogonal-codes

We study cyclic triorthogonal codes in prime dimension $p$, on which a transversal third-level diagonal gate acts as a logical non-Clifford gate. For odd $p$, we use a definition of triorthogonality that does not require self-orthogonality. For cyclic codes of length coprime to $p$, triorthogonality reduces to a sumset condition on the spectral support, which makes exhaustive search feasible: for two natural constructions, we enumerate all maximal codes of this kind for $p=3$ up to length $121$ and $p=5,7$ up to length $96$. For qubits, we prove that a cyclic code of odd length is triply even if and only if it is classically triorthogonal, giving a complete description of triply-even cyclic codes, and we determine all such codes up to length $763$. For qudits, we find codes such as $[[19,1,3]]_3$ and $[[7,1,3]]_7$, which improve on the shortest Reed-Muller and Reed-Solomon codes in both overhead exponent and distillation threshold. The latter is the first member of an infinite family of $[[p,1,2\lfloor p/6\rfloor+1]]_p$ codes.

0.50