CS Paper Radar

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

Martin R. Albrecht, Benjamin Benčina, Russell W. F. Lai

cs.IT ·submitted 2026-10-06 16:47 UTC · v1
position

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Euclidean and Hermitian Self-Orthogonal Codes from Divisible Codes

cs.IT ·2026-11-10 ·Ziling Heng, Chenkun Xie
theory similarity 0.73
Abstract · 26 pages

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.

0.11

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

cs.IT ·2026-10-26 ·Tingting Wu, Xianhong Xie
similarity 0.71
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

Uniform Sampling of Linear Codes with Prescribed Hull Dimension

cs.IT math.CO ·2026-11-02 ·Keita Ishizuka
similarity 0.70
Abstract

We give exactly uniform samplers for linear codes with prescribed hull dimension, for the Euclidean, Hermitian, and symplectic inner products and over finite fields of every characteristic. Except for the Euclidean form over fields of odd characteristic, these are the first uniform samplers for arbitrary prescribed hull dimension. Each sample costs an expected $O(k^2 N + k \log q)$ field operations for codes of dimension $k$ in a space of dimension $N$ over $\mathbb{F}_q$ or $\mathbb{F}_{q^2}$.

0.10

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

cs.IT ·2026-08-28 ·Junmin An, Jon-Lark Kim
similarity 0.66
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

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.64
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

Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

cs.IT cs.DSmath.CO ·2026-09-04 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.63
Abstract

We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.

0.35

On the structure of polynomial ideal codes and additive Reed--Solomon codes

cs.IT ·2026-10-15 ·Umberto Martínez-Peñas, Rubén Rodríguez-Ballesteros
similarity 0.63
Abstract

We study structural properties of polynomial ideal (PI) codes and additive Reed--Solomon (aRS) codes in the folded Hamming metric (equivalently, the Hamming metric over a larger alphabet). We first determine the maximum possible length of PI codes, prove that the dual of every PI code is a generalized PI code, and deduce that PI codes are dually QMDS together with an explicit formula for their weight distribution. We then show that PI codes defined by irreducible polynomials correspond to aRS codes with pairwise nonconjugate evaluation points. For these aRS codes, the previous results on PI codes apply (duality, QMDS property and weight distribution). We show that, asymptotically, aRS codes with nonconjugate evaluation points achieve the same length as PI codes. We also compute the permutation group of such aRS codes. We also extend the family of PI codes to consider arbitrary polynomial modules (not necessarily pairwise coprime), and study when these and general aRS codes satisfy the QMDS and dually QMDS properties.

0.15

Optimal self-orthogonal binary linear codes

cs.DM math.COcs.IT ·2026-10-29 ·Sascha Kurz
theory similarity 0.62
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