PaperlayerView exact revision on arXiv

Source-linked AI summary

The rank of $\mathbb{Z}_{2^s}$-linear Hadamard codes

Xuan Wang, Minjia Shi

arXiv:2610.34730v1cs.ITmath.IT

TL;DR

Closed rank formulas for canonical Z2s-linear Hadamard codes had been known only through s=3, with larger exponents covered by small-length computations. The paper gives a support-decomposition method and finite algorithm for the rank coefficients. It computes them through s=5, yielding explicit formulas through Z32 while leaving a compact general-s description open.

  • Problem

    For s≥4, rank was computed only for individual types and small lengths, and no method produced it for every s.

    Source: §1 · p. 3

  • Method

    A support decomposition expresses rank as a finite binomial polynomial in type parameters, with coefficients computed by an exact algorithm.

    Source: §1 · p. 3, §5 · p. 14

  • Results

    For s≤5, complete coefficient tables yield explicit rank formulas over Z4, Z8, Z16, and Z32, with the Z16 values reproducing every entry of [7, Table 3].

    Source: §1 · p. 3, §5 · p. 14

  • Takeaways & Limitations

    Rank and kernel dimension are invariants that can distinguish nonequivalent nonlinear Hadamard codes, but together they do not always complete classification.

    Source: §1 · p. 2

    For general s, the paper provides no simple closed formula; intermediate-weight coefficients reduce to the rank of an explicit matrix but are not uniformly evaluated.

    Source: §4.5 · p. 14, §5 · p. 15

Abstract

from arXiv · show

The canonical $\mathbb{Z}_{2^s}$-linear Hadamard codes are the Gray images of the $\mathbb{Z}_{2^s}$-additive codes. Their rank, the dimension of the binary linear span, was known in closed form only for $s\le 3$, and for $s \ge 4$ only through computer computations for small lengths. We give a method that computes the rank for every $s$. We show that the rank is a binomial polynomial in the type parameters, with coefficients $\rho_s(\boldsymbol{k})$ independent of the length. We compute all the coefficients for $s\le 5$, which yields explicit rank formulas over $\mathbb{Z}_4$ and $\mathbb{Z}_8$ (recovering the known ones), and over $\mathbb{Z}_{16}$ and $\mathbb{Z}_{32}$.

1 Introduction

The paper addresses the remaining rank invariant for canonical Z2s-linear Hadamard codes: closed forms were known only through s=3, and larger exponents had been handled by small-length computations. It gives a length-independent coefficient representation and computes the coefficients through s=5.

1 Introduction

  • Hadamard codes can be represented as Gray images of additive codes over Z2s or mixed alphabets, providing an algebraic setting for studying their equivalence.The linear Hadamard codes are first-order Reed–Muller codes, while most Hadamard codes are nonlinear.Source: §1 · p. 1
  • Rank and kernel dimension are invariants that can distinguish nonequivalent nonlinear Hadamard codes, but their pair does not always complete classification.For linear Hadamard codes, the rank is t+1 and the kernel is the whole code.Source: §1 · p. 2
  • For s≥4, prior rank results came from computations for individual types and small lengths, leaving no method that handled every s.The closed forms for s≤3 were already known.Source: §1 · pp. 2–3
  • For every s and type, the rank is represented by a finite binomial polynomial whose coefficients depend on s and a multiplicity vector, not on the type or length.A support decomposition and finite exact algorithm compute the coefficients; tables through s=5 yield explicit formulas over Z16 and Z32 as well as the known Z4 and Z8 formulas.Source: §1 · p. 3
  • The paper computes all coefficients through s=5, recovering the Z4 and Z8 formulas and giving explicit rank polynomials over Z16 and Z32.The Z16 values reproduce every entry of [7, Table 3].Source: §1 · p. 3

2 Concepts and notations

The section sets out Carlet’s Gray map and the canonical additive-code family whose Gray images are the Hadamard codes studied here. It also establishes the notation and rank representation used in the paper.

2.1 Carlet’s Gray map

  • Carlet’s map sends each Z2s symbol to a binary vector of length 2^(s−1), using columns that enumerate F2^(s−1); for s=1 it is the identity and for s=2 the classical Gray map.The map is additive modulo 2^s.Source: §2.1 · pp. 3–4

2.2 Z2s-Hadamard codes

  • Each canonical code is generated by a matrix whose columns enumerate specified tuples, and its Gray image has binary coordinates indexed by an additive coordinate and a Gray-digit vector.A message’s additive entry is expanded into binary digits; the coordinate value combines the top digit with the lower digits selected by the Gray-digit vector.Source: §2.2 · pp. 4–5

Index of notation

  • The notation table records the alphabet exponent, type and level parameters, code and Gray-map symbols, message coordinates, and rank as the dimension of the code’s binary span.The paper represents rank as a binomial polynomial in the type parameters, with coefficients computed by a finite exact algorithm.Source: Index of notation · p. 5, §2.2 · p. 5

3 The rank formula

The rank is computed as the dimension of a space of Boolean functions on the messages, decomposed by supports of nonconstant factors. Each support contributes a dimension determined only by its level multiplicities, yielding a binomial-polynomial rank formula.

3.1 The digit space

  • The code's column space equals V_s, the span of the digit functions of its Z_2^s-valued columns.The binary rank is therefore dim V_s; the digit columns and binary code columns span the same space.Source: §3.1 · p. 6

3.2 Boolean functions

  • Boolean functions on message bits have unique algebraic normal forms, whose monomials can be grouped by the factors appearing in them.Setting coefficient factors to zero retains exactly the monomials whose support is disjoint from those factors.Source: §3.2 · pp. 6–7

3.3 rank

  • The functions D_j,S,ζ_S belong to V_s and have monomials supported exactly on S, enabling the support-wise decomposition.Their support weight bound also identifies when the corresponding space W_s(S) vanishes.Source: §3.3 · pp. 7, 10
  • The spaces W_s(S) form a direct sum, so the rank-space dimension is obtained by adding their dimensions across supports.The support components span V_s, and the empty-support space is spanned by the s bits of b.Source: §3.3 · p. 8
  • A support contributes zero when its weight exceeds 2^s−1, restricting the rank sum to feasible multiplicity vectors.The generating functions have no coefficient of degree 2j for j < s when the support's weight is too large.Source: §3.3 · p. 10
  • For any feasible multiplicity vector k, dim W_s(S) depends only on s and k, not on the ambient type or length.Supports with the same multiplicities have equal dimensions, and the local message box argument establishes independence from the ambient code.Source: §3.3 · p. 10
  • Theorem 8 expresses the rank using binomial multiplicities of supports and coefficients ρ_s(k) that depend only on s and k.The coefficients are defined as the dimensions of the spaces associated with supports having multiplicity vector k.Source: §3.3 · pp. 10–11
  • The computation is not uniformly inexpensive: its complexity grows with s, although it is finite for every fixed s.Source: §3.3 · p. 11

4 Ranks over Z4, Z8, Z16 and Z32

The coefficients ρ_s(k) are computed by Algorithm 1 to give rank polynomials over Z4, Z8, Z16, and Z32. For general s, the paper gives a compact matrix description, but does not evaluate it uniformly for intermediate weights.

4.2 Explicit ranks over Z8

  • For s=3, Table 2 lists the coefficients ρ3 whose sum gives the closed formula in; ranks are also tabulated for lengths 2^t with t ≤17.Source: §4.2 · p. 11, Table 2 · p. 11

4.3 The rank over Z16

4.4 The rank over Z32

4.5 A talk for for general s

  • For general s, ρ_s(k) is the rank of an explicit matrix whose rows are indexed by (j,T) and whose columns are message monomials.Source: §4.5 · pp. 12, 14
  • At maximum weight 2^s−1, the coefficient is 1, but intermediate-weight coefficients lack a uniform evaluation, leaving a closed formula for general s open.Source: §4.5 · p. 14

5 Conclusion

The paper represents the rank of every canonical Z2^s-linear Hadamard code as a binomial polynomial whose coefficients depend on s and a multiplicity vector, not on type or length. It computes coefficients for s ≤ 5 and leaves general closed forms and mixed-type ranks open.

5 Conclusion

  • For every type, the rank is a binomial polynomial in the type parameters, with coefficients ρ_s(k) independent of the type and length.The coefficients are computed by a finite exact algorithm.Source: §5 · pp. 14–15
  • For s = 4 and s = 5, the method yields explicit binomial polynomials with coefficients tabulated for 36 and 202 feasible supports, respectively.For s = 2 and s = 3, the sum collapses to compact closed forms, recovering the known formulas over Z4 and Z8.Source: §5 · p. 14
  • For arbitrary s, the paper proves the representation theorem and provides an exact algorithm for computing ρ_s(k), but no simple uniform closed formula.Closed-form evaluation for intermediate weights and ranks for related mixed-type families remain open.Source: §5 · p. 15

A The algorithm to compute ρs(k)

Algorithm 1 computes ρ_s(k) by constructing truncated polynomial products, extracting coefficient functions, and finding their span dimension over F2. Its output equals the dimension of the local space whenever w(k) ≤ 2^s−1.

A The algorithm to compute ρs(k)

  • Given s and a multiplicity vector k, Algorithm 1 returns zero when w(k) > 2^s−1; otherwise it builds factor polynomials and multiplies them with truncation at degree 2^s.After each multiplication, it may replace the span of partial products by a basis without changing the final span.Source: A The algorithm to compute ρs(k) · p. 15
  • The algorithm extracts coefficients of T^(2j), then uses Gaussian elimination on their monomials to compute the dimension of their span over F2.The coefficient functions generate the local space whose dimension defines ρ_s(k).Source: A The algorithm to compute ρs(k) · pp. 15–16
  • For w(k) ≤ 2^s−1, Algorithm 1 outputs ρ_s(k) = dim W_s(S); the degree truncation is sufficient, and w(k) above the threshold makes the output zero.The product has no term below degree w(k), so if w(k) exceeds the threshold it contributes none of the coefficients used.Source: A The algorithm to compute ρs(k) · p. 15
Loading 2610.34730v1…