The Weight Hierarchies of Linear Codes from Simplicial Complexes

Chao Liu, Dabin Zheng, Wei Lu, Xiaoqiang Wang

This academic paper, recently published by Liu et al., explores the intersection of combinatorial topology and coding theory. Specifically, it provides a complete mathematical characterization of the "weight hierarchies" for a specific class of linear codes built using simplicial complexes.

TL;DR

The researchers have successfully calculated the complete weight hierarchies for linear codes constructed from simplicial complexes and their complements. By transforming a coding theory problem into a geometric intersection problem between subspaces and complexes, they provide explicit formulas that determine the performance of these codes in cryptographic and data-transmission applications.

What Problem Does This Paper Address?

In coding theory, a linear code is essentially a way to package data so that errors can be detected and corrected. While the "minimum distance" of a code tells us its basic error-correction capability, researchers often need a more detailed map of the code's structure: the Generalized Hamming Weight (GHW).

The GHW is a sequence of values (the weight hierarchy) that describes the minimum support of $r$-dimensional subspaces of the code. This hierarchy is crucial for understanding a code's performance in advanced scenarios, such as the "wire-tap channel" (where you want to keep information secret from an eavesdropper) or $t$-resilient functions in cryptography.

The challenge is that determining the complete weight hierarchy is mathematically grueling. For most types of codes, researchers can only find bounds or the first few values. This paper tackles the problem for codes generated by simplicial complexes—mathematical structures made of points, lines, triangles, and their higher-dimensional counterparts.

Methods

The authors use a "defining set" construction method. They build a linear code $\mathcal{C}$ over a finite field $\mathbb{F}_q$ by selecting a set of vectors $D$ (the defining set) and performing dot products.

The novelty lies in their choice of $D$:

  1. Simplicial Complexes ($\Delta$): A collection of subsets where, if a set is in the collection, all its subsets are also included. In this paper, these are viewed as unions of subspaces in $\mathbb{F}_q^m$.
  2. Complements ($\Delta^c$): The set of all vectors not in the simplicial complex.

To find the weight hierarchy, the authors apply a known formula that relates the $r$-th GHW to the maximum (or minimum) intersection between the simplicial complex and all possible $r$-dimensional dual subspaces. They utilize the Principle of Inclusion-Exclusion to manage the overlapping parts of the complex, effectively turning a coding problem into a high-dimensional geometry problem.

Datasets

As a theoretical mathematics paper, it does not use external "big data" sets. Instead, the authors use the Magma computational algebra system to generate specific numerical examples. These examples (such as a $[23, 6, 4]$ binary code) serve as "benchmarks" to verify that their general theoretical formulas produce the correct results for specific, computable cases.

Key Insights and Ideas

  • Geometric Translation: The "aha moment" is the realization that the weight hierarchy of these codes is entirely determined by how "thickly" or "thinly" the simplicial complex intersects with various subspaces of the surrounding vector space.
  • Structural Simplification: The authors show that if a simplicial complex is generated by a small number of "maximal elements" (the largest "shapes" in the complex), the inclusion-exclusion formulas become solvable.
  • The Complement Challenge: Calculating the hierarchy for the complement of a complex is significantly harder. While the complex itself is a union of subspaces (making maximum intersections easier to find), the complement requires finding minimum intersections, which involves more subtle geometric arguments.
  • Disjoint vs. Overlapping: The paper provides separate, elegant solutions for cases where the components of the complex are disjoint versus when they overlap.

Key Results

The paper provides several landmark theorems that give explicit formulas for the weight hierarchy $\{d_1, d_2, \dots, d_k\}$:

  • Theorems 1-3: Provide the complete hierarchy for complexes generated by one, two, or three maximal elements.
  • Theorems 4 & 7: Establish general formulas for complexes (and their complements) generated by any number of disjoint maximal elements.
  • Theorems 5-6: Solve the hierarchy for codes derived from the complements of complexes.

For example, in a complex with one maximal element $S$, the hierarchy is simply $d_r = q^m - q^{m-r}$. As the complexity of the defining set increases, the formulas incorporate terms that account for the intersections of the underlying subspaces.

Limitations and Future Work

The primary limitation is combinatorial explosion. As the number of maximal elements in the simplicial complex grows beyond three, the inclusion-exclusion logic becomes exponentially more difficult to track.

The authors acknowledge that they have solved "special cases" where the generators have specific properties. They conclude by inviting the research community to tackle the "general case"—finding a universal weight hierarchy formula for any arbitrary simplicial complex, a task that remains one of the "boss levels" of algebraic coding theory.

Summary updated

Abstract

The study of the generalized Hamming weight of linear codes is a significant research topic in coding theory as it conveys the structural information of the codes and determines their performance in various applications. However, determining the generalized Hamming weights of linear codes, especially the weight hierarchy, is generally challenging. In this paper, we investigate the generalized Hamming weights of a class of linear code $\C$ over $\bF_q$, which is constructed from defining sets. These defining sets are either special simplicial complexes or their complements in $\bF_q^m$. We determine the complete weight hierarchies of these codes by analyzing the maximum or minimum intersection of certain simplicial complexes and all $r$-dimensional subspaces of $\bF_q^m$, where $1\leq r\leq {\rm dim}_{\bF_q}(\C)$.
BibTeX
@misc{liu2023weight,
  author = {Chao Liu and Dabin Zheng and Wei Lu and Xiaoqiang Wang},
  title = {{The Weight Hierarchies of Linear Codes from Simplicial Complexes}},
  year = {2023},
  eprint = {2310.11873},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.11873},
}

Loading related content...

Figure