CS Paper Radar

Optimal and minimal $p$-ary linear codes from generalized order ideals of hierarchical posets

Rumi Melih Pelen

cs.IT math.CO ·submitted 2026-09-27 02:51 UTC · v1

Abstract

Hyun, Kim, Wu and Yue constructed optimal and minimal binary linear codes from order ideals of hierarchical posets with two levels. Two different generalizations of the underlying antichain (simplicial complex) setting to odd characteristic are known: down-sets of $\mathbb{F}_p^n$ under the componentwise order, and support-closed subsets of $\mathbb{F}_q^m$. No generalization of the poset setting itself has appeared. We introduce generalized order ideals of a poset of order $p-1$, obtained by attaching multiplicities in ${0,\dots,p-1}$ to the elements of a poset, and study the two natural notions of order ideal that arise for hierarchical posets with two levels. Whenever the ideal meets the upper level, the resulting defining sets are neither down-sets nor support-closed. We determine the weight distributions of the associated complement codes, exhibit a family of Griesmer codes in which the upper element carries an arbitrary multiplicity, and, via the characteristic function of a generalized order ideal, obtain an infinite family of minimal $p$-ary codes of length $p^n-1$ and dimension $n+1$ violating the Ashikhmin--Barg condition.

Comment
13 pages, no figures. Ancillary files contain a Python script verifying the formulas and computational examples

Closest papers

Nearest neighbours by meaning across the whole index.

Infinite families of 3-designs from linear and nonlinear codes

cs.IT ·2026-09-14 ·Shiyan Xiong, Xiaoqiang Wang, Dabin Zheng, Qinqin Ji
similarity 0.63
Abstract

The connection between coding theory and combinatorial $t$-designs is an important research topic at the intersection of coding theory and combinatorics. Let $q=p^m$, where $p$ is an odd prime and $m\geq 2$. In this paper, we investigate a class of linear codes $\mathcal{C}$ over $\mathbb{F}_{q^2}$ and their connection with combinatorial $3$-designs. By analyzing the relevant structural properties of $\mathcal{C}$ and $\mathcal{C}^{\perp}$, we show that the supports of the codewords of every nonzero weight in $\mathcal{C}$ and {the supports of the codewords of weight $4$ in $\mathcal{C}^{\perp}$} form $3$-designs. We further investigate a class of nonlinear codes $\mathcal{C}_2$ associated with $\mathcal{C}$, and prove that the supports of the codewords of every nonzero Hamming weight in $\mathcal{C}_2$ also form $3$-designs. These results identify further classes of linear and nonlinear codes whose codewords support combinatorial $3$-designs. In particular, the nonlinear case provides additional examples of codes supporting $3$-designs, a topic for which relatively few results are currently available. As applications, we construct from $\mathcal{C}^{\perp}$ an entanglement-assisted quantum error-correcting code with parameters $[[q+1,q-3,4;4]]_q$. We also prove that $\mathcal{C}$ is an all-symbol locally repairable code with locality $3$. Furthermore, we show that the code $\mathcal{C}$ {meets the Singleton-type bound for locally repairable codes} and hence is optimal in some cases.

0.22

A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes

cs.IT math.CO ·2026-11-04 ·Xinghao Wu, Junling Zhou
theory similarity 0.61
Abstract · 6 pages

Let $\mathcal{C}_k$ be the doubly-extended Reed--Solomon code with parameters $[q+1, k, q-k+2]_q$. We give a complete characterization of when its codewords of a fixed weight form $q$-ary 2-designs. The main ingredient is an exact criterion showing that the number of $r$-subsets of $\mathbb{F}_q^*$ with a prescribed product is independent of that product if and only if $\gcd(r, q-1)=1$. Applying this criterion to the minimum-weight codewords of $\mathcal{C}_k$, we prove that they form a $q$-ary 2-design if and only if $\gcd(k-1, q-1)=1$. We further establish a propagation result for MDS codes showing that the $q$-ary 2-design property at minimum weight implies the same property at every nonzero weight. Consequently, $\mathcal{C}_k$ holds $q$-ary 2-designs at all nonzero weights if and only if $\gcd(k-1, q-1)=1$.

0.33

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

Subcodes with Prescribed Hull Dimensions in Linear Codes:Enumeration, Containment, and Asymptotic Distributions

cs.IT ·2026-10-26 ·Linhan Xiong, Hongwei Liu, Liren Lin
similarity 0.59
Abstract · 39 pages

Mass formulas for prescribed hull dimensions have mainly been studied for linear codes viewed as subspaces of the whole space. We study internal enumeration for an arbitrary fixed parent code. Let $C$ be an $[n,k]_q$ linear code with an $\ell$-dimensional hull, and let $s$ be the subcode dimension. We determine the number of subcodes with prescribed dimension, hull dimension, and type over finite fields of both even and odd characteristic. We decompose the parent code into an LCD complement and its hull, and use projection to reduce enumeration to the corresponding problem inside the LCD complement. This yields explicit formulas refined by complete type and shows that the counts depend only on the relevant parameters, not on the particular parent code or its length. The known whole-space mass formulas and the enumeration of LCD subcodes of LCD codes arise as special cases. Motivated by code extension, we also study the dual containment problem: for a fixed code, we enumerate larger codes containing it with prescribed hull dimension and type. By duality, this problem is converted into the subcode enumeration problem already solved above, leading to corresponding conditional mass formulas. Finally, we investigate the asymptotic distributions arising from the exact enumeration formulas. When both the subcode dimension $s$ and $k-\ell-s$ tend to infinity, the hull distribution is governed by the LCD complement, and the limiting proportions are explicit constants determined by the field, the prescribed hull dimension, and the relevant type. When $s$ approaches or exceeds the dimension $k-\ell$ of the LCD complement, we determine the asymptotic proportion of subcodes attaining the minimum possible hull dimension and establish the associated concentration behavior. Analogous asymptotic results are obtained for the containment problem.

0.23

Hermitian Duality and Syndrome Structure of CSS-Type Codes over the ring $\mathbb{Z}_q[i]$

cs.IT ·2026-09-13 ·Akanksha Tiwari, Ritumoni Sarma
similarity 0.58
Abstract

We study the algebraic structure of principal ideal codes and CSS-type stabilizer constructions over the ring $ R_q=\mathbb Z_q[i],$ where every prime divisor of $q$ is congruent to $1$ modulo $4$. Although such ring-based constructions have recently been considered in the context of classical and quantum error correction, the precise relationship among principal ideal cardinalities, Hermitian duality, algebraic cosets, and stabilizer syndromes requires further structural analysis. We obtain cardinality formulas for principal ideals and their annihilators. For a length-one principal ideal code $C=\langleα\rangle$, we show that its Hermitian dual is $ C^{\perp_H}=\operatorname{Ann}(σ(α)). $ For nested codes satisfying $ C_2^{\perp_H}\subseteq C_1\subseteq C_2, $ we determine the corresponding CSS-type stabilizer and prove that the kernel of the physical $X$-error syndrome map is $ \ker(\operatorname{Syn}_X)=C_2. $ Consequently, $C_2/C_1$ parametrizes logical $X$-operator classes and $R_q^n/C_2$ parametrizes physical $X$-error syndrome classes. Using this syndrome quotient, we construct a transversal of $C_2$ in $R_q^n$ whose elements have pairwise distinct physical $X$-error syndromes. The corresponding $X$-type error family is correctable by stabilizer syndrome measurement, yielding a syndrome-based recovery procedure that is consistent with the stabilizer structure. Explicit examples illustrate the resulting duality, cardinality, and syndrome structure.

0.26

A Simple Explicit Construction of Smaller Strong Blocking Sets

cs.IT math.CO ·2026-10-09 ·Hao Chen
similarity 0.58
Abstract · 12 pages

Alon, Bishnoi, Das and Neri constructed sequences of strong blocking sets in $(k-1)$-dimension projective space $P({\bf F}_q, k-1)$ with sizes at most $Cqk$, where $k$ goes to the infinity and $C$ is a fixed positive constant not depending on $q$, in their paper published in Transactions AMS, vol. 277, pp. 5389-5410, 2024. This is equivalent to a sequence of minimal $[n_i,k_i]_q$ codes with positive rate $\frac{k_i}{n_i} \geq c$, where $k_i$ goes to the infinity and $c$ is a fixed positive constant only depending on $q$. They solved one of the main open problems on minimal codes. The Alon-Bishnoi-Das-Neri construction was based on asymptotically good sequences of algebraic geometric codes and expander graphs. However, the constant $C$ is large for small prime power $q$. In this paper, based on a simple approach using $(q-1)$-power intersecting algebraic geometric codes via concatenation to construct minimal codes, we construct explicit strong blocking sets in $(k-1)$-dimension projective space with sizes around $2(q^2-1)k$, equivalently, explicit minimal $[n,k]_q$ codes with length around $2(q^2-1)k$. This is an essential improvement on the previous result of Alon-Bishnoi-Das-Neri, when $q \leq 11$. For large $q$, strong blocking sets and minimal codes in our construction are worse than the previous construction of Alon-Bishnoi-Das-Neri. However, our approach is much simpler and does not depend on expander graphs.

0.38

Graph-Based Linear Codes Associated with the Finite Ring $\mathbb{F}_p[x]/\langle x^4 \rangle$

cs.IT ·2026-10-06 ·Apurba Sarkar, Kalyan Hansda, Makhan Maji
similarity 0.57
Abstract

We investigate the linear codes derived from the zero-divisor graph $Γ(R)$ of the finite local ring $R = \mathbb{F}_p[x]/\langle x^4 \rangle$ for an odd prime $p$. Using an equitable partition of $Z^*(R)$, we determine the parameters of the binary incidence code of $Γ(R)$ and construct induced bipartite subgraph codes achieving dual minimum distance $4$. Over $\mathbb{F}_p$, we parameterize the adjacency and Laplacian codes, derive the closed-form weight distribution of the Laplacian code via the MacWilliams identity, and establish its LCD property. Additionally, we determine the automorphism groups of the graph and its matrix codes. Finally, from extremal subgraphs of $Γ(R)$, we construct two families of Griesmer-optimal linear codes over $\mathbb{F}_p$, comprising a constant-weight minimal code and an optimal two-weight code.

0.11

New constructions of optimal Ferrers diagram rank-metric codes for quasi-block monotone Ferrers diagrams

cs.IT ·2026-11-14 ·Yong Jin, Yuhao Ning, Dengming Xu, Chengming Duan
theory similarity 0.57
Abstract

Constant dimension subspace codes (CDCs) have become an important object in coding theory due to their applications in random network coding. The paper is devoted to constructing optimal Ferrers diagram rank-metric codes for block Ferrers diagrams, which play a crucial role in the multilevel construction of CDCs. Let \(\mathbb{F}_q\) be the finite field with \(q\) elements of characteristic \(p\), \(P\) be a power of \(p\), and \(e\) be a positive integer. Let \(L=\mathbb F_{q^{eP}}\) and \(σ\) be the Frobenius \(\mathbb F_q\)-automorphism of \(L\), set \(N=σ^e-\mathrm{id}\). Based on the multiplicative property of the kernel filtration of the nilpotent map \(N\), we construct optimal Ferrers diagram rank-metric codes for block monotone diagrams. Specifically, considering \(n \times l\) Ferrers diagrams, we prove that optimal codes always exist for block monotone diagrams when \(n = eP\). Furthermore, by employing puncturing on columns, we prove that optimal codes also always exist for block strictly monotone diagrams, removing the restriction \(n = eP\). Consequently, optimal codes always exist for block upper triangular diagrams, specifically for maximum sum-rank distance (MSRD)-constructible block diagram pairs, which generalizes the corresponding results in \cite{neri2024,calderini2026}, in which the rank distance or the characteristic is restricted. Furthermore, by employing both puncturing and shortening on columns, we prove that optimal codes always exist for quasi-block strictly monotone diagrams, thereby generalizing the corresponding results in \cite{pratihar2023, zhang2019}. The optimal codes constructed in this paper will potentially be beneficial to the further construction of CDCs.

0.04