CS Paper Radar

Some Results on the Weight Spectrum of Binary Reed-Muller Codes $RM(m-7,m)$

Zibo Wei, Bo Zhou, Xiao Zhang, Hao Chen

cs.IT ·submitted 2026-10-21 14:33 UTC · v1
theory

Abstract

We study the set of weights occurring in the high-order binary Reed-Muller codes $RM(m-7,m)$. For every $m\geq 14$, we prove that the weight spectrum contains all even weights in $[336,2^m-336]$, together with an explicit finite set of low weights and their complements. The proof first establishes the corresponding base-code inclusion in $RM(7,14)$. This base step uses four-block concatenation, explicit degree-six monomial witnesses, and known spectrum inputs for $RM(5,10)$ and $RM(6,12)$. The base inclusion is then lifted to all $m\geq 14$ by a concatenation-based induction. We also analyze the remaining base-code target weights $322,326,330,334$ in several restricted families, including four-block branches, affine-flat and structured inner corrections in a fixed Carlet-type Maiorana-McFarland outer shell, and sparse sums of degree-7 coordinate monomials. The residual analysis delineates several construction routes that cannot yield the four unresolved base-code weights, thereby sharpening the remaining $c=7$ spectrum problem.

Comment
36 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Weight spectra of some families of GRM codes

cs.IT ·2026-09-12 ·Minjia Shi, Zhaokang Xing, Patrick Sole
similarity 0.77
Abstract

Let $\mathrm{RM}_q(r,m)$ denote the generalized Reed--Muller code of order $r$ and length $q^m$ over the finite field $\mathbb{F}_q$. We completely determine the weight spectra of $\mathrm{RM}_3(2m-i,m)$ for $i=3,4$, $\mathrm{RM}_4(3m-i,m)$ for $i=2,3$, $\mathrm{RM}_5(4m-4,m)$, and $\mathrm{RM}_7(6m-4,m)$, in the ranges of $m$ specified in the corresponding results. The proofs proceed by induction on $m$, using a sumset inclusion for GRM weight spectra together with results on low-weight codewords. The required base cases are established by computations in Magma and, for certain ternary cases, exact constraint solving with Z3.

0.20

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

The Exact Weight Spectrum of $\RM(m-7,m$): A Counterexample to the Carlet-Solé Conjecture

cs.IT ·2026-10-27 ·Yueying Lou, Qichun Wang
similarity 0.70
Abstract

Boolean functions are widely used in cryptography and coding theory. A key challenge lies in finding the weight spectrum for all $n$-variable Boolean functions of degree at most $r$, also known as the Reed--Muller code $\RM(r,n)$. In 2023, Carlet and Solé determined the weight spectra of $\RM(n-c,n)$ for $c=3,4$, and conjectured the weight spectrum of $\RM(n-c, n$) for $n\ge2c$. The weight spectra of $\RM(n-5, n)$ and $\RM(n-6,n)$ were determined by Carlet in 2024 and by Lou and Wang in 2025, respectively, confirming the Carlet-Solé conjecture for the cases $c=5,6$. Very recently, Leuenberger et al. and Wei et al. investigated the weight spectrum of $\RM(7,14)$ independently, and there are eight potential weights which have not been determined. Up until now, the weight spectra of the Reed--Muller codes $RM(r,n)$ are still unknown for $r=3,...,n-7$. In this paper, we determine the exact weight spectrum of $\RM(m-7, m)$ for every $m\ge 14$. By combining affine geometry and Fourier analysis, we exclude the conjectured eight weights for $\RM(7,14)$. We then extend the exclusions to all higher dimensions using a geometric transfer. Consequently, we provide a counterexample to the Carlet-Solé conjecture.

0.13

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

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

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

A Mirror Vanishing Band for Weight Distributions of Binary Linear Codes

cs.IT ·2026-09-17 ·Xianmang He
similarity 0.65
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$.

0.18

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