An Elementary Approach to MacWilliams Extension Property and Constant Weight Code with Respect to Weighted Hamming Metric

Basic Information

• Paper ID: 2511.00809
• Title: An Elementary Approach to MacWilliams Extension Property and Constant Weight Code with Respect to Weighted Hamming Metric
• Authors: Yang Xu (Fudan University), Haibin Kan (Fudan University), Guangyue Han (The University of Hong Kong)
• Classification: cs.IT (Computer Science - Information Theory), math.IT (Mathematics - Information Theory)
• Publication Date: November 4, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.00809

Abstract

This paper characterizes the MacWilliams Extension Property (MEP) and constant weight codes with respect to $\omega$-weight on finite fields $\mathbb{F}^{\Omega}$ through elementary methods, where $\mathbb{F}$ is a finite field, $\Omega$ is a finite set, and $\omega:\Omega\rightarrow\mathbb{R}^+$ is a weight function. The approach relies solely on elementary linear algebra and two key identities concerning $\omega$-weights of subspaces derived through double counting arguments. When $\omega$ is the constant unit mapping, the results degenerate to two classical results for Hamming metric codes: (1) Hamming weight-preserving mappings between linear codes can be extended to Hamming weight isometries of the entire ambient space; (2) any constant weight Hamming metric code is a repetition of the dual of a Hamming code.

Research Background and Motivation

Problem Background

1. Core Problem: This paper investigates the characterization of MacWilliams Extension Property and constant weight codes under weighted Hamming metric. MacWilliams proved in 1962 a classical result: any mapping preserving Hamming weight between linear codes can be extended to a Hamming weight isometry of the entire ambient space.
2. Problem Significance:
   • Weighted Hamming metric is a natural generalization of classical Hamming metric, with practical significance for modeling channels with non-uniform error distributions
   • In certain channels, error probability depends on codeword position, requiring correction of error sets with different configurations and weights
   • MEP is a fundamental property in coding theory, relating to code equivalence and classification problems
3. Limitations of Existing Methods:
   • Existing proofs largely depend on character theory of finite abelian groups
   • Ward and Wood (1996), Ward (1992) and others use group character methods
   • Liu and Chen (2010) use value function methods
   • These methods are technically involved and lack intuitive appeal
4. Research Motivation:
   • Provide a proof based entirely on elementary linear algebra, avoiding advanced tools like group characters
   • Generalize classical Hamming metric results to weighted Hamming metric
   • Establish a more direct and comprehensible theoretical framework

Core Contributions

The main contributions of this paper include:

1. Establishment of Two Fundamental Identities (Proposition 2.1):
   • Derive two key identities concerning $\omega$-weights of subspaces through double counting and q-binomial coefficients
   • These identities form the foundation for all subsequent results
2. Characterization of Local Equivalence (Theorem 2.1):
   • Provide necessary and sufficient conditions for local $\omega$-equivalence of two linear mappings
   • Offer characterization based on column mappings of generating matrices
3. Bridge from Local to Global (Theorem 2.2):
   • Prove that under appropriate Unique Decomposition Property (UDP) conditions, local equivalence implies global equivalence
   • This is the key step for deriving global properties from local ones
4. Complete Characterization of MEP (Theorem 2.3):
   • Prove that MEP is equivalent to transitivity, which is also equivalent to UDP condition
   • Unify MEP theory under weighted Hamming metric
5. Characterization of Constant Weight Codes (Proposition 2.2 and Theorem 2.4):
   • Provide necessary and sufficient conditions for constant weight codes
   • Characterize constant weight codes using column mappings of generating matrices
   • Generalize Bonisoli's classical result on Hamming metric constant weight codes
6. Methodological Innovation:
   • Completely avoid using group character theory
   • Rely solely on elementary linear algebra and combinatorial counting
   • Provide more concise and direct proofs

Detailed Methodology

Task Definition

Basic Setup:

• $\mathbb{F}$: finite field with $|\mathbb{F}|=q$
• $\Omega$: non-empty finite set (coordinate set)
• $H=\mathbb{F}^{\Omega}$: ambient space
• $\omega:\Omega\rightarrow\mathbb{R}^+$: weight function

Core Concepts:

1. $\omega$-weight:
   • $\omega$-weight of vector $\beta\in H$: $\text{wt}(\beta)=\sum_{i\in\text{supp}(\beta)}\omega(i)$
   • $\omega$-weight of subspace $A\subseteq H$: $\text{Wt}(A)=\sum_{i\in\chi(A)}\omega(i)$
   • Where $\text{supp}(\beta)=\{i\in\Omega|\beta_i\neq 0\}$, $\chi(A)=\{i\in\Omega|\exists\beta\in A,\beta_i\neq 0\}$
2. Weighted Hamming Metric: $d_{\omega}^H(\alpha,\beta)=\text{wt}(\beta-\alpha)$
3. MEP (MacWilliams Extension Property): For any linear code $C\leq_{\mathbb{F}}H$ and $\mathbb{F}$-homomorphism $f\in\text{Hom}_{\mathbb{F}}(C,H)$ preserving $\omega$-weight, there exists $\omega$-weight isometry $\phi\in\text{End}_{\mathbb{F}}(H)$ such that $\phi|_C=f$
4. Constant Weight Code: A linear code $C$ is called constant weight if $\text{wt}(\alpha)=\text{wt}(\beta)$ for all $\alpha,\beta\in C-\{0\}$
5. Unique Decomposition Property (UDP): $(H,K,\omega)$ satisfies UDP if for any $I\subseteq H$, $J\subseteq K$ satisfying $\sum_{i\in I}\omega(i)=\sum_{j\in J}\omega(j)$, we have $|\{i\in I|\omega(i)=b\}|=|\{j\in J|\omega(j)=b\}|$ for all $b\in\mathbb{R}$

Core Method Architecture

The proof strategy follows the following logical chain:

Double Counting → Two Fundamental Identities (Prop 2.1)
    ↓
Characterization of Local Equivalence (Thm 2.1)
    ↓
UDP Condition + Local Equivalence → Global Equivalence (Thm 2.2)
    ↓
Complete Characterization of MEP (Thm 2.3)
    ↓
Characterization of Constant Weight Codes (Prop 2.2, Thm 2.4)

Key Technical Components

1. Fundamental Identities (Proposition 2.1)

Identity 1: For $B\leq_{\mathbb{F}}X$, $\dim_{\mathbb{F}}(B)=m$, $\sum_{\theta\in B}\text{wt}(f(\theta))=(q^m-q^{m-1})\text{Wt}(f[B])$

Proof Strategy:

• Let $D=f[B]$, $\dim_{\mathbb{F}}(D)=r$
• For each $\beta\in f[B]$, the number of preimages is $q^{m-r}$
• Rearrange the summation order, converting sum over $\theta$ to sum over support set
• Use $|\{\beta\in D|\beta_i\neq 0\}|=q^r-q^{r-1}$

Identity 2: Let $A\leq_{\mathbb{F}}X$, $\dim_{\mathbb{F}}(A)=a$, $m\in\{a+1,\ldots,k\}$, then $\sum_{(B\leq_{\mathbb{F}}X,\dim(B)=m,A\subseteq B)}\text{Wt}(f[B])=q^{k-m}\binom{k-a-1}{m-a-1}_q\text{Wt}(f[X])+\binom{k-a-1}{m-a}_q\text{Wt}(f[A])$

Proof Strategy:

• Apply Identity 1 to all $m$-dimensional subspaces containing $A$
• Use q-binomial coefficients to count subspaces containing given elements
• Key distinction between cases $\theta\in A$ and $\theta\in X-A$

2. Characterization of Local Equivalence (Theorem 2.1)

Part One: Local equivalence $\Rightarrow$ Equal weights for all subspaces

Direct application of Identity 1.

Part Two: Existence of dimension $m$ such that all $m$-dimensional subspaces have equal weight $\Rightarrow$ Local equivalence

Proof Strategy:

• First use Identity 2 (with $a=0$) to prove $\text{Wt}(f[X])=\text{Wt}(g[X])$
• Then for any 1-dimensional subspace $A$, use Identity 2 to prove $\text{Wt}(f[A])=\text{Wt}(g[A])$
• Finally apply Identity 1 again to obtain local equivalence

Part Three: Characterization based on generating matrices

For generating matrices $L$ and $M$ with column mappings $\tau$ and $\eta$, $f$ and $g$ are locally $\omega$-equivalent if and only if for all 1-dimensional subspaces $I\leq_{\mathbb{F}}\mathbb{F}^{[k]}$, $\sum_{(i\in\chi(f[X]),\tau(i)\in I)}\omega(i)=\sum_{(i\in\chi(g[X]),\eta(i)\in I)}\omega(i)$

Key Observation:

• $\chi(f[B])=\{i\in\Omega|\tau(i)\notin U^{\perp}\}$, where $U$ corresponds to $B$
• Transform subspace weight problem into column mapping distribution problem

3. From Local to Global (Theorem 2.2)

Theorem Statement: If $f$ and $g$ are locally $\omega$-equivalent and $(\chi(f[X]),\chi(g[X]),\omega)$ satisfies UDP, then $f$ and $g$ are globally $\omega$-equivalent.

Proof Strategy:

1. By Theorem 2.1, for all 1-dimensional subspaces $I$, the two column mappings have identical weight distributions on $I$
2. UDP condition ensures not only equal weight sums but also identical occurrence counts for each weight value
3. Construct bijection $\lambda:\Omega\rightarrow\Omega$ and nonzero scalars $(c_i)$ such that $\eta(\lambda(i))=\tau(i)\cdot c_i$
4. Define matrix $Q$ and mapping $\phi$, verify that $\phi$ is $\omega$-weight isometry with $g=\phi\circ f$

Key Lemma (Lemma 3.1): $\phi$ is $\omega$-weight isometry if and only if there exists bijection $\lambda$ such that $\omega(i)=\omega(\lambda(i))$ and $\text{supp}(\phi(\alpha))=\lambda[\text{supp}(\alpha)]$

4. Complete Characterization of MEP (Theorem 2.3)

Theorem Statement: The following three conditions are equivalent:

1. $H$ satisfies MEP
2. $H$ is transitive with respect to $\omega$-weight
3. $(\Omega,\omega)$ satisfies UDP

Proof Chain:

• $(1)\Rightarrow(2)$: Direct from MEP definition
• $(2)\Rightarrow(3)$: Use transitivity and Lemma 3.1 to construct bijection
• $(3)\Rightarrow(1)$: Direct application of Theorem 2.2

Technical Innovation Points

1. Clever Use of Double Counting:
   • Transform vector weight sums into subspace weights by rearranging summation order
   • Precisely count containment relations using q-binomial coefficients
2. Avoidance of Group Character Theory:
   • Traditional methods rely on Fourier analysis of finite abelian groups
   • This paper uses only linear algebra and combinatorial counting, more elementary
3. Hierarchical Proof Structure:
   • Start from fundamental identities
   • Progressively establish local properties, global properties, and equivalence conditions
   • Each step is clear and natural
4. Introduction of UDP Condition:
   • UDP provides bridge from "equal weight sums" to "identical weight distributions"
   • Key for local-to-global transformation
5. Unified Framework:
   • Handle MEP and constant weight code problems in same framework
   • Characterization of constant weight codes directly uses MEP results (Proposition 2.2 uses Theorem 2.1)

Experimental Setup

Note: This is a pure theory paper with no experimental section. All results are mathematical theorems and their proofs.

Theoretical Verification

The paper verifies theoretical correctness through:

1. Special Case Verification: When $\omega(i)=1$ (constant weight), all results degenerate to known classical results:
   • Theorem 2.3 recovers MacWilliams (1962) MEP
   • Theorem 2.4 recovers Bonisoli (1984) result on constant weight codes
2. Logical Completeness:
   • All theorems provide necessary and sufficient conditions
   • Complete proof chain with rigorous mathematical derivations at each step
3. Comparison with Existing Results:
   • Theorem 2.3 is special case of 12, Theorem VI.1
   • When $q=2$, is special case of 6, Theorem 8
   • But proofs in this paper are simpler and more direct

Experimental Results

Main Theoretical Results

Result 1: Subspace Weight Identities (Proposition 2.1)

Identity (2.7): $\sum_{\theta\in B}\text{wt}(f(\theta))=(q^m-q^{m-1})\text{Wt}(f[B])$

Significance: Establishes quantitative relationship between vector weight sum and subspace weight, with coefficient $(q^m-q^{m-1})$ exactly equal to size of $B-\{0\}$.

Identity (2.8): For all $m$-dimensional subspaces containing $A$, their weight sum can be expressed as linear combination of $\text{Wt}(f[X])$ and $\text{Wt}(f[A])$, with coefficients given by q-binomial coefficients.

Result 2: Necessary and Sufficient Conditions for Local Equivalence (Theorem 2.1)

Condition 1: $f$ and $g$ are locally $\omega$-equivalent $\Leftrightarrow$ there exists dimension $m\in\{1,\ldots,k-1\}$ such that all $m$-dimensional subspaces have equal weight

Condition 2: Local $\omega$-equivalence $\Leftrightarrow$ column mappings of generating matrices have equal weight sums on each 1-dimensional subspace

Importance:

• Reduce global property (all vectors have equal weight) to local property (subspaces of certain dimension have equal weight)
• Provide computable decision conditions

Result 3: UDP Ensures Local-to-Global (Theorem 2.2)

Statement: Local $\omega$-equivalence + UDP $\Rightarrow$ Global $\omega$-equivalence

Independent Value:

• Only requires "local" UDP condition: $(\chi(f[X]),\chi(g[X]),\omega)$ satisfies UDP
• No need for entire $(\Omega,\omega)$ to satisfy UDP
• Useful for analyzing specific mapping pairs

Result 4: Complete Characterization of MEP (Theorem 2.3)

Equivalence Chain: $\text{MEP}\Leftrightarrow\text{Transitivity}\Leftrightarrow\text{UDP}$

Specific Form: $(\Omega,\omega)$ satisfies UDP means: for any $I,J\subseteq\Omega$, if $\sum_{i\in I}\omega(i)=\sum_{j\in J}\omega(j)$, then for all $b\in\mathbb{R}$, $|\{i\in I|\omega(i)=b\}|=|\{j\in J|\omega(j)=b\}|$

Practical Meaning:

• UDP is verifiable combinatorial condition
• When $\omega$ is injective, UDP automatically holds
• When $\omega$ is constant 1, UDP trivially holds

Result 5: Characterization of Constant Weight Codes (Theorem 2.4)

Necessary and Sufficient Condition 1: $C$ is constant weight code $\Leftrightarrow$ there exists $\sigma\in\mathbb{R}$ such that for all 1-dimensional subspaces $I\leq_{\mathbb{F}}\mathbb{F}^{[k]}$, $\sum_{(i\in\chi(C),\tau(i)\in I)}\omega(i)=\sigma$

In this case, for any $s$-dimensional subspace $D\leq_{\mathbb{F}}C$, its weight is $\text{Wt}(D)=\frac{(q^k-q^{k-s})\sigma}{q-1}$

Necessary and Sufficient Condition 2 (under UDP): $C$ is constant weight code $\Leftrightarrow$ for all 1-dimensional subspaces $I,J$, column mapping has identical weight distributions on $I$ and $J$

Applications:

• Provide matrix conditions for determining constant weight codes
• Give explicit formulas for subspace weights
• When $\omega\equiv 1$, recover classical result "constant weight codes are repetitions of dual Hamming codes"

Theoretical Insights

1. Dimension Reduction Principle: No need to check all vectors; checking all subspaces of certain fixed dimension suffices to determine local equivalence
2. Core Role of UDP: UDP bridges "equal weight sums" to "identical weight distributions," key for local-to-global transformation
3. Geometric Meaning of Column Mapping: Column mapping $\tau:\Omega\rightarrow\mathbb{F}^{[k]}$ maps coordinate positions to dual space; constant weight code condition is equivalent to uniform weight distribution of $\tau$'s image on each 1-dimensional subspace
4. Combinatorial Meaning of q-Binomial Coefficients: Precisely characterizes counting of containment relations among subspaces over finite fields, foundation of double counting arguments

Related Work

Classical MEP Theory

1. MacWilliams (1962) 7:
   • First proved MEP under Hamming metric
   • Used combinatorial and group-theoretic methods
   • This paper generalizes to weighted metric
2. Bogart, Goldberg, Gordon (1978) 4:
   • Gave elementary combinatorial proof of MEP
   • Used binary matrices induced by 1-dimensional subspaces
   • This paper's method inspired by but more systematic
3. Ward and Wood (1996) 11:
   • Proved MEP via character theory of finite abelian groups
   • Simultaneously proved constant weight code characterization
   • This paper avoids character theory, more elementary

Constant Weight Code Theory

1. Bonisoli (1984) 3:
   • Proved any Hamming constant weight code is repetition of dual Hamming code
   • This paper generalizes to weighted metric
2. Ward (1992) 10:
   • Used group characters for constant weight code results
   • This paper's method more direct
3. Liu and Chen (2010) 5:
   • Extended constant weight code theory using value functions
   • This paper's Theorem 2.4 generalizes 5, Theorem 1

Weighted Metric Theory

1. Bezzateev and Shekhunova (2013) 2:
   • Studied Goppa codes under weighted Hamming metric
   • Provided practical application background for weighted metric
2. Machado and Firer (2020) 6:
   • Studied support-respecting weights and NN-decoding
   • When $q=2$, this paper's Theorem 2.3 is special case of 6, Theorem 8
3. Xu, Kan, Han (2024) 12:
   • Studied MEP under weighted poset metric
   • This paper's Theorem 2.3 is special case of 12, Theorem VI.1
   • But proofs here are simpler

Relative Advantages of This Paper

1. Methodological Advantages:
   • Completely elementary, using only linear algebra
   • Avoids group characters, value functions, and other advanced tools
   • Proofs more intuitive and understandable
2. Result Unification:
   • Handle MEP and constant weight codes in same framework
   • All results based on two fundamental identities
3. Condition Clarity:
   • UDP condition clear and verifiable
   • Provide necessary and sufficient conditions rather than just sufficient

Conclusions and Discussion

Main Conclusions

1. Methodological Contribution:
   • Establish MEP and constant weight code theory based on elementary linear algebra
   • Two identities derived through double counting are core tools
   • Avoid advanced techniques like group characters
2. Theoretical Contribution:
   • Completely characterize MEP under weighted Hamming metric: equivalent to UDP condition
   • Provide necessary and sufficient conditions for constant weight codes and generating matrix characterization
   • Unify treatment of local and global equivalence
3. Generalizability:
   • When $\omega\equiv 1$, recover all classical results
   • Provide foundation for more general metrics (e.g., weighted poset metric)

Limitations

1. Theoretical Limitations:
   • Only handle linear codes, not nonlinear codes
   • Only consider vector spaces over finite fields
   • UDP condition may be too strong in some cases
2. Method Limitations:
   • Double counting relies on finiteness
   • Difficult to directly extend to infinite-dimensional cases
   • More complex metric structures may require new techniques
3. Application Aspects:
   • Pure theory paper, lacks concrete application examples
   • No discussion of algorithmic complexity and computational issues
   • Missing numerical examples and specific code constructions
4. Completeness:
   • No discussion of sufficient conditions for UDP
   • No classification of weight functions $\omega$
   • Lack of alternative theory for cases not satisfying UDP

Future Directions

While paper doesn't explicitly propose future directions, possible extensions include:

1. Algorithmic Aspects:
   • Develop efficient algorithms for verifying UDP conditions
   • Construct weight functions satisfying specific properties
   • Design encoding and decoding algorithms for constant weight codes
2. Theoretical Extensions:
   • Generalize to more general metric spaces
   • Study cases partially satisfying UDP
   • Consider extension properties for nonlinear codes
3. Application Research:
   • Apply weighted metric in practical channel models
   • Design constant weight codes with good properties
   • Study applications in distributed storage

In-Depth Evaluation

Strengths

1. Strong Method Innovation:
   • Completely elementary proof method is important innovation
   • Combination of double counting and q-binomial coefficients is clever
   • Avoiding group character theory makes results more understandable and generalizable
2. Rigorous and Complete Theory:
   • All theorems provide necessary and sufficient conditions
   • Proof logic clear with distinct levels
   • Derivation from fundamental identities to MEP is natural
3. Unified and Elegant Results:
   • UDP condition elegantly characterizes MEP
   • Clear relationship between local and global properties
   • Treat constant weight codes and MEP in same framework
4. Clear Writing:
   • Reasonable structure: Section 2 states results, Section 3 gives proofs
   • Consistent and clear notation
   • Clear relationship with existing work
5. Good Generalizability:
   • Recover all classical results as special cases
   • Lay foundation for further generalization
   • Methods potentially applicable to other metrics

Weaknesses

1. Lack of Concrete Examples:
   • No examples of weight functions satisfying/violating UDP
   • Missing specific code constructions and calculations
   • Practical applications of theoretical results unclear
2. Insufficient Discussion of UDP Condition:
   • No sufficient conditions or decision methods for UDP
   • Cases not satisfying UDP not deeply discussed
   • Geometric or combinatorial meaning of UDP not sufficiently clarified
3. Relationship with Existing Results:
   • While special case of 12, simplification degree not quantified
   • Relationship with 6 only discussed for $q=2$
   • Could more thoroughly compare proof complexity
4. Computational Complexity:
   • No discussion of algorithm complexity for verifying conditions
   • Computational cost of generating matrix characterization not analyzed
   • Lack of practical operability discussion
5. Insufficient Application Orientation:
   • Pure theory paper, lacks application drive
   • No discussion of specific applications in channel coding
   • Weak connection with practical problems

Impact Assessment

1. Contribution to Field:
   • High: Provides new proof techniques for coding theory
   • Elementary methods facilitate teaching and generalization
   • Unified framework helps understand MEP essence
2. Practical Value:
   • Moderate: Theoretical results provide foundation for applications
   • Weighted metric has application potential in non-uniform channels
   • But lacks specific coding schemes and algorithms
3. Reproducibility:
   • High: All proofs are constructive
   • Independent of computational experiments, pure mathematics
   • Methods clear, easy to verify and extend
4. Academic Impact:
   • Likely to become standard reference in field
   • Elementary methods may inspire research on other problems
   • Unified framework facilitates further theoretical development

Applicable Scenarios

1. Theoretical Research:
   • Equivalence and classification problems in coding theory
   • Study of isometry groups of metric spaces
   • Weight problems in combinatorial optimization
2. Teaching:
   • Elementary proof of MEP for textbooks
   • Advanced applications of linear algebra and combinatorics
   • Application examples of q-binomial coefficients
3. Potential Applications:
   • Coding design for non-uniform error channels
   • Distributed storage systems (different node reliability)
   • Network coding with weighted metrics
4. Further Research:
   • Starting point for studying more general metrics
   • Theoretical foundation for developing practical coding algorithms
   • Guidance for weight function design

Overall Evaluation

This is an excellent theoretical paper, with main strengths:

• Method innovation: completely elementary proof avoids advanced tools
• Complete results: necessary and sufficient conditions with unified framework
• Classical generalization: recover known results in more general setting

Main weaknesses:

• Lack of concrete examples and applications
• UDP condition discussion could be deeper
• Computational and algorithmic aspects not covered

Recommendation Index: ★★★★☆ (4/5)

Suitable for coding theory researchers, scholars interested in MEP, and educators seeking elementary proof methods.

Key References

3 A. Bonisoli, "Every equidistant linear code is a sequence of dual Hamming codes," Ars Combinatoriai, vol. 18, 1984. (Classical result on constant weight codes)

4 K. Bogart, D. Goldberg, J. Gordon, "An elementary proof of the MacWilliams theorem on equivalence of codes," Information and Control, vol. 37, 1978. (Elementary proof of MEP)

7 F. J. MacWilliams, "Combinatorial problems of elementary abelian groups," Ph.D. Dissertation, Harvard University, 1962. (Original MEP proof)

11 H. N. Ward, J. A. Wood, "Characters and the equivalence of codes," Journal of Combinatorial Theory, Series A, vol. 73, no. 2, 1996. (Character theory method)

12 Y. Xu, H. Kan, G. Han, "MacWilliams extension property with respect to weighted poset metric," IEEE Transactions on Information Theory, vol. 70, no. 2, 2024. (More general results)