Designs, Self-Dual Codes, and Invariant Theory

The weight enumerator of a self-dual code is invariant under the MacWilliams transform, so it lies in a ring of invariants of a finite group. Gleason's theorem identifies generators of that ring, and bounding the coefficients of the invariants that can be weight enumerators of an actual code gives upper bounds on the minimum distance of a self-dual code. That is the thread connecting the three groups of functions below.

The designs functions come from the Assmus-Mattson theorem: under a condition on the weight distributions of a code and its dual, the supports of the minimum-weight codewords form a combinatorial design. design_strength reports the resulting strength and minimum_weight_blocks returns the blocks.

CodingTheory.design_strength — Method
design_strength(C::AbstractLinearCode; verbose) -> Any

Return the maximum strength t for which the Assmus–Mattson theorem guarantees that the code forms a t-design.

source
CodingTheory.is_design_holder — Method
is_design_holder(
    C::AbstractLinearCode,
    t::Int64;
    verbose
) -> Any

Evaluates the Assmus-Mattson theorem to determine if the codewords of C form a t-design.

source
CodingTheory.minimum_weight_blocks — Method
minimum_weight_blocks(C::ReedMullerCode) -> BigInt

Return the exact number of minimum weight codewords in RM(r, m).

Notes

  • Geometrically, this is the number of (m-r)-dimensional affine subspaces in AG(m, 2).
  • These codewords form the blocks of a 3-design.
source

Gleason bounds

CodingTheory.Gleason_bound — Method
Gleason_bound(C::AbstractLinearCode) -> Any

Return the theoretical maximum minimum distance for a self-dual code under Gleason's Theorems. Returns missing if the code does not fit a standard extremal classification.

source
CodingTheory.is_extremal — Method
is_extremal(C::AbstractLinearCode; verbose) -> Any

Return true if a self-dual code attains the maximum minimum distance allowed by Gleason's theorems; otherwise, return false.

source

Invariant theory

CodingTheory.Bachoc_Gaborit_bound — Method
Bachoc_Gaborit_bound(n::Int64) -> Int64

Return the Bachoc-Gaborit upper bound on the joint geometric distance 2d + s for a Type I code and its shadow.

source
CodingTheory.Mallows_Sloane_bound — Method
Mallows_Sloane_bound(n::Int64; type) -> Int64

Return the Mallows-Sloane upper bound on the minimum distance of a binary self-dual code.

Notes

  • type = :TypeII (Doubly-even): d ≤ 4 * ⌊n / 24⌋ + 4
  • type = :TypeI (Singly-even): d ≤ 2 * ⌊n / 8⌋ + 2
  • Codes meeting this bound exactly are called "Extremal".
source
CodingTheory.extremal_weight_enumerator — Method
extremal_weight_enumerator(n::Int64; type) -> Any

Return the theoretical weight enumerator of an extremal self-dual code of length n.

Notes

  • Mathematically forces the low-weight coefficients to 0 to maximize minimum distance.
  • If the resulting polynomial contains negative coefficients, no extremal code exists at this length!
source
CodingTheory.gleason_generators — Method
gleason_generators(

) -> Tuple{Nemo.QQMPolyRingElem, Nemo.QQMPolyRingElem, Nemo.QQMPolyRingElem}

Return the fundamental Gleason polynomial generators for binary self-dual codes. Return the tuple (ϕ_2, ϕ_8, ϕ_24) as polynomials in R = QQ[x, y].

source
CodingTheory.is_valid_self_dual_enumerator — Method
is_valid_self_dual_enumerator(
    W::AbstractAlgebra.MPolyRingElem,
    n::Int64;
    type
) -> Union{Tuple{Bool, Vector{Any}}, Tuple{Bool, Vector{Nemo.QQFieldElem}}}

Verify if a weight enumerator W is a mathematically valid Type I or Type II self-dual code.

Notes

  • Checks if W is in the Gleason invariant ring.
  • Returns (true, gleason_coeffs) if valid, or (false, []) if it is a "Ghost Code".
source
CodingTheory.shadow_transform — Method
shadow_transform(
    W::AbstractAlgebra.MPolyRingElem,
    n::Int64
) -> Any

Return the shadow weight enumerator of a Type I binary self-dual code.

Notes

  • Transforms the primal weight enumerator W(x, y) via the MacWilliams-like shadow transformation: W_S(x, y) = 1/2^(n/2) * W(x+y, i*(x-y)).
  • If the returned polynomial contains negative or fractional coefficients, the primal code is mathematically impossible (a "Ghost Code").
source