Infinite families of $2$-designs from two classes of linear codes

Xiaoni Du, Rong Wang, Chunming Tang, Qi WangarXiv 2019 · DOI · arXiv

TL;DR

This paper bridges the gap between coding theory and combinatorial design by identifying two specific classes of linear codes that generate infinite families of 2-designs. By calculating the exact weight distributions of these codes using exponential sums, the authors explicitly determine the parameters ($v, k, \lambda$) for these new combinatorial designs.

What Problem Does This Paper Address?

The study of $t$-designs—sets of points and blocks where every $t$-element subset of points is contained in exactly $\lambda$ blocks—is a cornerstone of combinatorial mathematics. While $t$-designs have applications in cryptography, communications, and statistics, finding new "infinite families" of them is notoriously difficult.

Coding theory offers a promising path: if you take a linear code, the "supports" (the set of indices where a codeword has non-zero entries) of all codewords of a specific weight might form the blocks of a $t$-design. However, this only happens for specific types of codes. The challenge addressed here is identifying suitable code classes, proving they possess the necessary symmetry (specifically, being affine-invariant), and then doing the heavy mathematical lifting to calculate their weight distributions so the design parameters can be explicitly known.

Methods

The authors focus on two specific classes of linear codes, denoted as $\overline{C_1}^{\perp}$ and $\overline{C_2}^{\perp}$. These are the extended duals of cyclic codes defined over a finite field $\mathbb{F}_q$ (where $q = p^m$).

Key techniques include:

  • Affine Invariance: The authors prove these codes are invariant under the affine group $GA_1(\mathbb{F}_q)$. A known theorem (Theorem 3 in the paper) states that any affine-invariant code holds a 2-design for every nonzero weight.
  • Exponential Sums: To find the parameters of the designs, one must know how many codewords exist for each weight. The authors calculate these "weight distributions" by evaluating complex exponential sums (specifically Weil sums and Gauss sums) involving trace functions and polynomials of the form $ax^{p^l+1} + bx^2 + cx$.
  • Cyclotomic Fields: They utilize properties of the Galois group of cyclotomic fields to simplify the evaluation of these sums.

Datasets

As a theoretical mathematics paper, no external datasets were used. However, the authors employed the Magma computational algebra system to run numerical examples. These examples (such as for $p=3, m=3$) serve as "unit tests" to verify that their general theoretical formulas match specific, computable instances.

Key Insights and Ideas

  • Symmetry as a Bridge: The core "aha moment" is leveraging the fact that the extended codes are affine-invariant. This symmetry automatically guarantees the existence of 2-designs, shifting the problem from "does a design exist?" to "what are its exact parameters?"
  • Few-Weight Codes: The codes studied are "few-weight" codes (typically having between 4 and 10 distinct non-zero weights). Codes with few weights are highly prized in both coding theory (for their error-correction properties) and combinatorics (for generating clean designs).
  • Explicit Parameterization: Unlike some papers that prove the existence of designs, this work provides the exact formulas for $v, k,$ and $\lambda$ based on the underlying field parameters $p$ and $m$.

Key Results

The paper provides a complete characterization of the weight distributions for both code classes across both odd and even values of $m$.

  • Code $\overline{C_1}^{\perp}$: Proved to be an 8-weight code when $m$ is odd and a 10-weight code when $m$ is even.
  • Code $\overline{C_2}^{\perp}$: Proved to be a 4-weight code when $m$ is odd and a 6-weight code when $m$ is even.
  • Design Parameters: The authors derived explicit, albeit complex, algebraic expressions for the $\lambda$ parameter of the resulting 2-designs. For example, in the case of $(p,m) = (3,3)$, they confirmed the existence of 2-designs with parameters like $(27, 9, 4)$ and $(27, 12, 132)$.

Limitations and Future Work

While the paper successfully derives parameters for most weights, the authors acknowledge a specific limitation: for the code $\overline{C_1}^{\perp}$, determining the parameters for certain specific weights (e.g., $i = p^2(p-1)$ when $m=3$) remains mathematically "hard."

They suggest that future work could involve:

  1. Solving these remaining "hard" weight cases.
  2. Investigating whether these or similar classes of codes could hold 3-designs, which are even rarer and more difficult to construct than 2-designs.
  3. Exploring the applications of these specific designs in experimental design or secret sharing schemes.

Summary updated

Abstract

The interplay between coding theory and $t$-designs has attracted a lot of attention for both directions. It is well known that the supports of all codewords with a fixed weight in a code may hold a $t$-design. In this paper, by determining the weight distributions of two classes of linear codes, we derive infinite families of $2$-designs from the supports of codewords with a fixed weight in these codes, and explicitly obtain their parameters.
BibTeX
@misc{du2019infinite,
  author = {Xiaoni Du and Rong Wang and Chunming Tang and Qi Wang},
  title = {{Infinite families of $2$-designs from two classes of linear codes}},
  year = {2019},
  eprint = {1903.07459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.07459},
}

Loading related content...

Figure