MacWilliams identity for Hamming weight enumerators
ProvedCodingTheory.macWilliamsIdentityLet be a finite field of cardinality , let be a finite coordinate type, and let be a linear code. If denotes the homogeneous Hamming weight enumerator and is the dual under the standard coordinatewise bilinear form, then
as an identity in the integer polynomial ring .
This is the denominator-free polynomial form of the MacWilliams identity for Hamming weight enumerators. It determines the complete Hamming-weight distribution of the dual code from that of the original code.
Formalization Note. Coordinates are indexed by an arbitrary finite type. The statement includes the zero code, the full code, and the empty coordinate type.
import Definitions.Def_CodingTheory
namespace CodingTheory
/-- The homogeneous MacWilliams identity for a linear code over a finite field. -/
theorem macWilliamsIdentity
(F ι : Type*) [Field F] [Fintype F] [DecidableEq F]
[Fintype ι] [DecidableEq ι]
(C : LinearCode F ι) :
MvPolynomial.C (Nat.card C : ℤ) *
hammingWeightEnumeratorPolynomial F ι (dualCode F ι C) =
MvPolynomial.bind₁ ![
MvPolynomial.X 0 +
MvPolynomial.C ((Fintype.card F - 1 : ℕ) : ℤ) * MvPolynomial.X 1,
MvPolynomial.X 0 - MvPolynomial.X 1]
(hammingWeightEnumeratorPolynomial F ι C) := by sorry
end CodingTheory
Read-back
What the Lean code literally says, in plain math · gpt-5.6-sol
For every type equipped with a field structure, a finite enumeration, and decidable equality; every type equipped with a finite enumeration and decidable equality; and every -linear subspace , let , , , and define the integer-coefficient polynomial in the two variables by . Define , where the sum and products are in . The assertion is the following equality in :
More literally, on the left is first computed as the natural-number cardinality of the subtype , cast to , embedded as a constant polynomial, and then multiplied by ; on the right, is first natural-number subtraction , then cast to and embedded as a constant polynomial, and the displayed replacement of and is the coefficient-preserving polynomial-algebra homomorphism sending to and to . The exponent is likewise natural-number subtraction, which would return if , although here because it counts a subset of ; similarly, a field is nonempty (indeed has at least two elements), so the natural subtraction does not underflow. No assumption requires to be nonempty or to be nonzero, proper, or of positive dimension: the statement includes the zero and full codes and the case , in which , the word space and every code or dual code have one element, every weight is , and both enumerator polynomials are the constant polynomial .
Confirmed by the mission captain (proposal self-audit).