Source-linked AI summary
Harmonic higher weight distributions, Simonis' approach of MacWilliams identity and moments
Himadri Shekhar Chakraborty, Mehedi Hasan Tanver
TL;DR
The paper addresses how Simonis’ MacWilliams identity extends to harmonic higher weight distributions and how these enumerators behave statistically for random linear codes. It adapts Simonis’ combinatorial counting method using a reflection identity, and defines the enumerators through generator-matrix rank functions. The expectation is zero for non-trivial harmonic functions, while the covariance is strictly non-zero and explicitly characterized.
Problem
The paper studies harmonic higher weight distributions and the statistical moments of their enumerators for random linear codes.
Method
The paper adapts Simonis’ combinatorial counting method with a harmonic reflection identity and formulates enumerators through generator-matrix rank functions.
Results
The expectation is zero for all non-trivial harmonic functions, while the covariance is strictly non-zero.
Takeaways & Limitations
The covariance provides a non-trivial statistical invariant that can be used to verify the MacWilliams identity probabilistically.
Takeaways & Limitations
The random-code formulation assumes a generator matrix with independent uniformly distributed entries over F_q, and the examples include fixed parameters q = 2, n = 2, k = 1, r = 1, d = 1.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends Simonis’ combinatorial MacWilliams approach to harmonic higher weight distributions and studies their moments for random linear codes. The expectation vanishes for non-trivial harmonic functions, while the covariance remains non-zero.
- Introduction: The paper adapts Simonis’ elementary counting method to prove a MacWilliams identity for harmonic higher weight distributions.The adaptation resolves the factorization of harmonic sums using a reflection identity.
- Introduction: It investigates statistical moments of harmonic higher weight enumerators for random linear codes, extending earlier work on higher weight distributions.The study targets both expectation and covariance.
- Introduction: The first moment is zero for all non-trivial harmonic functions because random matrices exhibit the relevant symmetry.The paper interprets this symmetry as mirroring the properties of the trivial code.
- Introduction: The covariance is strictly non-zero, yielding a non-trivial statistical invariant for probabilistic verification of the MacWilliams identity.The paper also presents an explicit covariance formula in its stated contribution.
2 Preliminaries
The preliminaries introduce linear-code operations, higher weight distributions, and discrete harmonic functions. They also establish the spaces, operators, and reflection identity used later.
- 2.1 Linear codes: Linear-code preliminaries define supports, weights, dual codes, puncturing, shortening, and their dimension relationships.These notions support the later complement-based counting arguments.
- 2.1 Linear codes: The r-th higher weight distribution records subcodes of dimension r according to their support-related weights.Simonis’ MacWilliams-type identity for these distributions is recalled as prior groundwork.
- 2.2 Discrete Harmonic Functions: Discrete harmonic functions are developed through set-function spaces, extensions, differentiation operators, and the kernel defining harmonicity.The extension vanishes outside the relevant degree range.
- 2.2 Discrete Harmonic Functions: The reflection identity is identified as the key useful identity for discrete harmonic functions.It is later used in the harmonic MacWilliams proof.
- 2.2 Discrete Harmonic Functions: An example applies the differential operator to derive linear constraints among the values of a degree-two function.For the example, a3 = a4 = −(a1 + a2), a5 = a2, and a6 = a1.
3 Harmonic analogue of Simonis’ MacWilliams identity
The paper proves a harmonic analogue of Simonis’ MacWilliams identity by combining complement-based combinatorial counting with the reflection identity. The resulting theorem relates dual harmonic higher weight distributions through an invertible linear transformation.
- Harmonic analogue of Simonis’ MacWilliams identity: The proof adapts Simonis’ counting method to harmonic higher weight distributions, with the reflection identity supplying the central harmonic ingredient.The argument counts suitable subset–subcode configurations in two ways.
- Harmonic analogue of Simonis’ MacWilliams identity: The harmonic r-th higher weight enumerator is defined from the harmonic higher weight distribution and is divisible by z^d.The divisibility follows from the vanishing properties of extended harmonic functions.
- Harmonic analogue of Simonis’ MacWilliams identity: The complement map bijects subsets satisfying dual-code dimension conditions with subsets satisfying corresponding primal-code conditions.The dimension correspondence follows from puncturing and shortening formulas.
- Harmonic analogue of Simonis’ MacWilliams identity: Theorem 3.9 states the MacWilliams identity for harmonic r-th higher weight distributions for d ≤ j ≤ n−d.It applies to an [n, k] code and f ∈ Harm_d(n).
- Harmonic analogue of Simonis’ MacWilliams identity: The transformation matrix is invertible because it is equivalent to a lower-triangular matrix with ones on the diagonal.Its determinant is 1, so the dual harmonic distributions can be solved explicitly.
- Harmonic analogue of Simonis’ MacWilliams identity: Taking r = 1 and d ≠ 0 reduces the theorem to Bachoc’s MacWilliams identity for harmonic weight distributions.A concrete binary-code example verifies the identity.
4 Moments of the harmonic higher weight enumerator
The paper reformulates harmonic higher weight enumerators through generator-matrix rank functions and studies their moments for random linear codes. The expectation vanishes for non-trivial harmonic functions, while covariance is computed through rank-covariance formulas grouped by set intersections.
- 4.1 Random linear codes and the rank-function formulation: Random [n,k] codes are modeled by k × n generator matrices with independent uniform entries over F_q.The code is generated by the rows of the random matrix, and r_I is the rank of the column submatrix indexed by I.
- 4.1 Random linear codes and the rank-function formulation: The harmonic rank function weights rank-based subcode counts by the harmonic evaluation e_f(I), packaging these statistics into a polynomial.For d = 0, this formulation coincides with the ordinary rank-function approach.
- 4.2 The Expectation (First Moment): For non-trivial harmonic functions, the expected harmonic rank function is zero because e_f(E) = 0 when d ≠ 0.The calculation uses linearity of expectation and the fact that the expected rank coefficient depends only on |I|.
- 4.3 The Covariance (Second Moment): The covariance is derived by applying a rank-covariance formula and grouping pairs of d-subsets according to their intersection size s.The resulting factors depend on α = q^-r_x, β = q^-r_y, and c_m = q^(r-m), with contributions organized by the four regions determined by Z and W.
- 4.3 The Covariance (Second Moment): The covariance calculation combines independent elementwise contributions across the regions Z ∩ W, Z \ W, W \ Z, and E \ (Z ∪ W).Each region contributes a factor determined by whether its elements are included in the relevant subsets I and J.
5 Examples for Moments of Random Codes
The examples verify the moment formulas in small random-code settings and construct a degree-3 harmonic function whose mean is zero but whose covariance is strictly non-zero. The computations illustrate both the symmetry behind the first moment and the non-triviality of the second.
- Example 5.1: Four 1 × 2 generator matrices over F_2 are equiprobable, and their evaluated harmonic rank values are 0, 1, 1, and 0.The corresponding expectation is therefore zero.
- Example 5.2: For q = 2, n = 32, k = 1, r = 1, and d = 3, the example defines a harmonic function supported on four disjoint blocks.Each block has size 8 and is partitioned into two subsets of size 4.
- Step 1: Verifying that f is harmonic: The constructed function is harmonic because the contributions from the two subsets within each block cancel for every relevant 2-subset.Subsets intersecting multiple blocks give zero directly, while within-block cases cancel by construction.
- Step 2: Derivation of the expectation (first moment): The degree-3 example has zero expectation because summing the harmonic function over all possible 3-subsets gives zero.This explicitly instantiates the structural first-moment result.
- Step 3: The covariance is non-zero: For d = 3, the covariance is strictly non-zero whenever a, b, c, and d are not all zero.The example obtains the covariance by reducing the general formula to the m = 0 term and summing independent block contributions.
6 Conclusion
The paper establishes a combinatorial MacWilliams identity for harmonic higher weight distributions and analyzes the first two statistical moments of harmonic enumerators for random linear codes. It concludes by identifying higher moments, asymptotic covariance, and larger numerical experiments as natural continuations.
- 6 Conclusion: The paper adapts Simonis’ method through a reflection identity and studies higher moments, covariance asymptotics, and larger parameter regimes.The stated continuations extend beyond the first two moments and small examples.