In classical coding theory, the goal is often to find codes that maximize the minimum distance for a given rate. However, for specialized applications like secret sharing schemes, authentication protocols, and the construction of strongly regular graphs, the entire weight distribution of the code matters. Specifically, researchers seek "few-weight" codes—linear codes where the codewords take on only a small number of distinct non-zero Hamming weights.
Constructing these codes is difficult because standard algebraic techniques often produce a broad spectrum of weights. A growing body of research addresses this by using combinatorial structures—specifically simplicial complexes and partially ordered sets (posets)—as "defining sets" to precisely engineer the code’s weight properties.
The Defining Set Framework
A linear code can be constructed by choosing a "defining set" $D$ of vectors from a finite field. The codewords are then formed by taking the inner product of a message vector with every vector in $D$. The weight of a codeword depends entirely on how many vectors in $D$ are orthogonal to the message.
As Jian et al. and Zheng and Zhang demonstrate, if $D$ is chosen randomly, the weights will vary wildly. To restrict the code to just two or three weights, $D$ must possess a highly regular internal structure.
Simplicial Complexes as Geometric Blueprints
A simplicial complex is a collection of sets that is closed under the subset operation: if a set is in the complex, all its subsets are too. This combinatorial property provides a natural way to control codeword weights.
Wu et al. show that by using simplicial complexes with a small number of maximal elements, one can systematically generate optimal or near-optimal few-weight codes. The intuition is that the subset-closure property of the complex creates a predictable "overlap" between different codewords, forcing their weights into a narrow range of values. This approach has been extended to:
- Binary LCD and Self-Orthogonal Codes: Wu and Lee utilize the difference between two distinct simplicial complexes to build codes that meet the Griesmer bound, a fundamental limit on code efficiency.
- Quaternary Codes: Wu et al. and Wu et al. apply these structures to codes over larger alphabets (like $GF(4)$), showing that the resulting quaternary codes can be mapped to high-performing binary subfield codes.
Increasing Flexibility via Posets and Set Operations
While simplicial complexes are powerful, their strict subset-closure property can limit the range of achievable code parameters. To overcome this, researchers have introduced more flexible combinatorial operations:
- Posets: Zhu et al. explore posets formed by the disjoint union of chains. This allows for a more nuanced definition of the defining set, leading to new optimal quaternary codes.
- Symmetric Differences: Instead of using a single complex, Fang et al. use the symmetric difference of intersecting sets. This technique allows for the construction of MDS (Maximum Distance Separable) Euclidean self-dual codes, which are highly prized for their error-correction efficiency.
Algebraic Refinement: Trace Functions and Weil Sums
To further refine the weight distribution, combinatorial structures are often combined with algebraic constraints. Jian et al. and Yang et al. use trace functions and Weil sums to filter the defining set. By selecting vectors where the trace of a specific polynomial vanishes, the authors can guarantee that the resulting code has exactly two or three weights.
This algebraic precision is critical for secret sharing schemes. As Yang and Zhang explain, codes derived from "plateaued functions" result in "minimal" codes. In these codes, no codeword's support is a subset of another's, ensuring that every participant in a cryptographic protocol is essential for reconstructing the secret.
Breaking Asymptotic Barriers
Beyond the construction of specific few-weight codes, moving to higher-dimensional structures solves a fundamental problem in coding theory. Traditional "cycle codes" based on 1D graphs are mathematically prevented from being "asymptotically good" (maintaining high rate and distance as they grow).
However, Newman and McCullough prove that by moving to homological codes derived from 2D or higher simplicial complexes (using triangles and tetrahedra instead of just edges), this barrier is broken. This suggests that the topological properties of these complexes are not just useful for weight control, but are essential for the next generation of high-performance error-correcting codes.
Key Foundational Work
Binary LCD Codes and Self-Orthogonal Codes via Simplicial Complexes (2020) — contributed 7 concept elements to this direction.
Optimal Few-Weight Codes From Simplicial Complexes (2020) — contributed 6 concept elements to this direction.
Two-weight and three-weight linear codes based on Weil sums (2019) — contributed 4 concept elements to this direction.