CS Paper Radar

A Mirror Vanishing Band for Weight Distributions of Binary Linear Codes

Xianmang He

cs.IT ·submitted 2026-09-17 13:11 UTC · v1

Abstract

Chen and Xie recently proved, using the Ashikhmin--Barg lemma on minimal vectors, that every binary linear $[n,k,d]$ code with $k=n-2d+2+v$ ($v\ge 0$) has no codewords of weight in the interval $[2d-v,\,2d-1]$. Their argument uses two of the five basic properties of minimal vectors established by Ashikhmin and Barg (1998). In this note we utilize the third property, the disjoint-support decomposition of non-minimal codewords in binary codes, to generate a \emph{mirror} vanishing band on the other side of $2d$: if $A_{d+1}=\cdots=A_{d+t}=0$ for some $t\ge 1$ and $k\ge n-2d+1$, then $A_w=0$ for all $w\in[2d+1,\,2d+t]$. Combining the two bands, the number of nonzero weights of such a code is at most $n-d-v-2t+1$, improving the Chen--Xie bound $n-d+1-v$ by $2t$.

Closest papers

Nearest neighbours by meaning across the whole index.

The Support-Distribution Conditions for MSRD Codes Reduce to a Single Inequality

cs.IT ·2026-10-29 ·Xiang Fan
theory similarity 0.70
Abstract · 18 pages

Byrne, Gluesing-Luerssen, and Ravagnani determined the number of codewords with a prescribed nonzero support in a linear maximum sum-rank distance code whose blocks have a common number of columns. Their formula depends only on the code parameters and the support dimensions. Evaluating it for arbitrary parameters gives a family of necessary nonnegativity conditions for existence. We prove their conjecture that this family is equivalent to the condition at the vector of total dimension $d+1$ obtained by filling the longest blocks first, where $d$ is the distance parameter. The resulting explicit criterion applies over every finite field $\mathbb F_q$, for all row numbers $n_i\leqslant m$ and $1\leqslant d<N$, where $m$ is the common number of columns and $N$ is the total number of rows. It also covers the boundary cases in which this vector fills each of its nonzero blocks completely, not explicitly included in the conjecture's displayed parameter range. The proof uses a generating function and an exchange identity to reduce the problem to vectors obtained by filling the longest blocks first. We then estimate alternating sums of elementary symmetric polynomials, with a separate argument for $q=2$. The dual conditions admit the same reduction. For codes that exist, the joint condition follows from sphere-packing bounds for the code and its dual. An infinite family of parameters satisfies the joint condition but admits no such linear code.

0.22

Minimality of Binary Codes From Weight Layers and Graph Cut Spaces

cs.IT ·2026-10-26 ·Xianhong Xie, Mengni Wang, Tingting Wu
similarity 0.66
Abstract

Minimal binary linear codes play an important role in secret-sharing schemes and in the structural study of linear codes. We study the minimality of three classes of known constructions: codes from a single complete Hamming-weight layer, codes from arbitrary unions of such layers and graph cut-space codes. For the previously studied single-layer codes C, we give a complete minimality classification: C is minimal if and only if t is even. For t = 4, we determine the minimum and maximum weights, and show that the family strictly violates the binary Ashikhmin Barg sufficient condition for every k. We also calculate the minimum distance of the dual code. For arbitrary unions of complete Hamming-weight layers, we obtain an if-and-only-if classification of minimality and uniform criteria for evenness, self-orthogonality, the doubly even property and hull dimension. We further analyze the family for odd k. Finally, using the classical bond characterization of cuts, we translate minimality of graph cut space codes into a graph-theoretic condition: a nonempty simple graph has a minimal cut code precisely when it has one edge-containing component and that component is complete. We also give a graph-function realization of the known binary tetrahedron code and explicitly identify the resulting code equivalence.

0.24

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

cs.IT ·2026-11-12 ·Yota Maeda, Ruho Kondo
theory similarity 0.66
Abstract · 25 pages

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

0.19

Six Families of Binary Codes Arising from Ding's Conjectures

cs.IT ·2026-09-29 ·Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng +1 more
theory similarity 0.66
Abstract

Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

0.04

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

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

Auxiliary Codes and the Generalized Packing-Covering Conjecture

cs.IT ·2026-09-16 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
theory similarity 0.65
Abstract · 10 pages, 2 tables. Revised exposition and references; clarified the auxiliary-code method and improved presentation

The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established range of redundancies at most seven. We also prove the bound on generalized Hamming weights $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$. Both results use an auxiliary-code criterion that converts a covering property in the syndrome space into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.

0.37

Generalized Hamming Weights and Subcode Support Weight Distributions of Twisted Reed-Solomon Codes

cs.IT ·2026-10-12 ·Chao Liu, Hao Chen, Dabin Zheng, Yaqi Chen
similarity 0.65
Abstract · 38 pages

In this paper, we determine the generalized Hamming weight hierarchies of two classes of twisted Reed--Solomon (TRS) codes. For TRS codes with one twist, we first determine all possible values of the generalized Hamming weights. We then give a complete characterization of the weight hierarchy in terms of the minimum distance of the dual code. Explicit conditions are derived for the minimum distances of the code and its dual, which make the whole weight hierarchy explicitly computable. As special cases, the obtained results recover several known characterizations for TRS codes to be MDS, NMDS codes, and $s$-gap AMDS codes. For TRS codes with two twists, we similarly determine the complete generalized Hamming weight hierarchy. In this case, the higher generalized Hamming weights are determined by the first two generalized Hamming weights of the dual code, for which explicit rank conditions are also obtained. In addition, we further determine the subcode support weight distributions of this class of single-twist TRS codes. More precisely, for each $1 \le r \le k$, we derive an explicit formula for the number of $r$-dimensional subcodes with a prescribed support size, thereby giving a complete description of the support distribution of subcodes.

0.22