CS Paper Radar

Harmonic higher weight distributions, Simonis' approach of MacWilliams identity and moments

Himadri Shekhar Chakraborty, Mehedi Hasan Tanver

cs.IT math.COmath.NT ·submitted 2026-08-16 17:18 UTC · v2
theory

Abstract

We present a combinatorial proof of Simonis type MacWilliams identity for harmonic higher weight distributions of linear codes. Furthermore, we investigate the statistical moments of the harmonic higher weight enumerators for random linear codes. Defining the enumerators via rank functions of the generator matrices of linear codes, we prove that its expectation vanishes for all non-trivial harmonic functions due to the inherent symmetry of random matrices, and we also derive an explicit, non-trivial formula for the covariance.

Comment
19 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

Weight Distributions of Single Parity-Check Product Codes via Character Sums

cs.IT math.CO ·2026-08-26 ·Makson Miller Alves Ribeiro, Sara D. Cardell
similarity 0.55
Abstract

We investigate structural and enumerative properties of binary single parity-check product codes. For each $n\geq 2$, $\operatorname{SPC}(n)$ denotes the binary single parity-check code of length $n$, consisting of all binary vectors of length $n$ having even Hamming weight. We determine the generalized Hamming weight hierarchy of the product code $\mathcal{C}_{m,n}=\operatorname{SPC}(m)\otimes\operatorname{SPC}(n)$, whose codewords can be represented as $m\times n$ binary matrices in which every row and every column has even Hamming weight. For the square product $\mathcal{C}_n =\operatorname{SPC}(n)\otimes\operatorname{SPC}(n)$, we also determine the maximum codeword weight and prove that its homogeneous weight enumerator is symmetric if and only if $n$ is even. After characterizing the dual code, we apply the MacWilliams identity in its Walsh--Hadamard formulation to derive an exact closed-form expression for the weight enumerator. By grouping the auxiliary binary vectors according to their Hamming weights, we obtain an explicit formula for each coefficient in terms of binomial coefficients and alternating convolutions. Finally, using Krawtchouk polynomials, we present an exact procedure for computing the full weight distribution without exhaustively enumerating all codewords. Numerical examples illustrate the formulas and verify the resulting computations.

0.20

On the $b$-Symbol Weight Distribution of Dual Melas Codes and a Poisson Randomness Postulate

cs.IT ·2026-10-27 ·Gabriel Sac Himelfarb, Moshe Schwartz
theory similarity 0.55
Abstract · 25 pages

We prove a new lower bound on the $b$-symbol weight of codewords in dual Melas codes, which is strictly better than known results. We employ a new strategy that translates a pattern counting problem in linear-feedback shift register sequences to a problem on orbits of binary polynomials under a certain action. We use the same techniques to provide an improved lower bound on the burst-covering radius of Melas codes and a new upper bound on the critical exponent of dual Melas codes. We then define a new randomness postulate on (families of) binary sequences, based on the definition of infinite Poisson generic sequences. We conjecture that codewords in the dual Melas code satisfy this postulate, and we show partial progress in establishing this conjecture. We also show how a relaxed version of the problem can be completely resolved, and relate the conjecture to the first part of the paper, giving a justification of why the improved bounds on the $b$-symbol weight were somewhat to be expected.

0.30

Uniform Sampling of Linear Codes with Prescribed Hull Dimension

cs.IT math.CO ·2026-11-02 ·Keita Ishizuka
similarity 0.54
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

Vanishing Relative Distance of Uniformly Random CSS LDPC Codes Built from Permutation Matrices

cs.IT quant-ph ·2026-11-16 ·Kenta Kasai
theory similarity 0.53
Abstract · 17 pages, 1 figure

Classical random regular low-density parity-check codes can have minimum distance growing linearly with block length. We study CSS check matrices formed as full $J\times L$ arrays of arbitrary $P\times P$ permutation matrices, sampled uniformly subject to commutation. For fixed column weight $J\ge3$ and fixed even row weight $L>2J$, we prove that the relative minimum distance converges to zero in probability as $P\to\infty$, with block length $n=LP$. We analyze the weight enumerators that count all nontrivial logical representatives after excluding stabilizers. A coefficientwise lower bound shows that, at every fixed relative weight $0<α<1$ along even-weight sequences, exponentially many such representatives exist with high probability. Their typical and mean counts have exponent lower bound $h_2(α)/2$, where $h_2$ is the binary entropy function. We compare this bound with the classical LDPC and dense CSS mean weight-distribution exponents. The existence, with high probability, of a logical operator below every fixed target weight $δn$ yields the distance conclusion.

0.13

Linear Hashing Is Poissonesque

cs.DS cs.CCcs.ITmath.PR ·2026-10-26 ·Vinayak M. Kumar
theory similarity 0.53
Abstract · Abstract shortened to fit character limit

The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. $\textbf{Expected loads.}$ We show that the expected value of the $r$th largest bin is governed by the $r$th largest value among $n$ independent Poisson random variables of mean $m/n$. Specializing to the canonical setting of $m=n$ and $r=1$, our bounds show that the expected maximum load when $n$ balls are hashed into $n$ bins by a random $\mathbb{F}_2$-linear map is no more than the corresponding expectation for a fully random map $\textit{plus}$ $\frac{3}2 + o(1)$. Specializing to $m\gg n\log n$, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. $\textbf{Concentration.}$ When $m\gg n\log (1/ρ)$ balls are tossed into $n$ bins randomly, we expect with $0.99$ probability that $\textit{every}$ density-$ρ$ subset of bins will contain a $(1\pm o(1) )ρ$-fraction of the balls. We show that this remains the case if the $m$ balls are tossed using a random linear map, and our bound matches the $o(1)$-factor produced by the fully random case. This gives a stronger version of the Leftover Hash Lemma for linear maps. An implication of this is that all bins have load $m/n \pm O(\sqrt{(m/n)\log n})$ with probability $0.99$. We obtain these results by showing that the average of a log-potential on the bin loads is upper bounded by the cumulant generating function of a Poisson random variable of mean $m/n$.

0.17

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$

cs.IT cs.CCcs.DSmath.CO+1 ·2026-09-15 ·Vinayak M. Kumar, Geoffrey Mon
publishedtheoryhighly cited similarity 0.52
Abstract

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

0.43

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