In coding theory, we often want to design linear codes where the codewords have a highly predictable, restricted distribution of weights (the number of non-zero coordinates). Codes with only two, three, or a few distinct weights are incredibly valuable: their structured nature makes them ideal for cryptographic secret sharing schemes, distributed storage systems, and optimal error-correction protocols.
However, if you try to construct a code by randomly writing down a generator matrix, the weights of the resulting codewords will be highly unpredictable. To guarantee a specific, small set of weights, researchers use a powerful framework known as defining set construction. Instead of designing the generator matrix directly, this method builds codes from the ground up by selecting a structured subset of a finite field and evaluating algebraic functions over it.
The Core Mechanism: From Sets to Codewords
To understand why this approach works, let's look at how a linear code is generated from a defining set.
Let $\mathbb{F}_{q}$ be a finite field, and let $D = \{d_1, d_2, \dots, d_n\}$ be a carefully chosen subset of elements from an extension field $\mathbb{F}_{p^m}$ (or a vector space over the field). This subset $D$ is called the defining set.
We construct a linear code $\mathcal{C}_D$ by mapping every element $\alpha$ in our field to a codeword $c_\alpha$. Each coordinate of the codeword is computed by evaluating a trace function—which maps elements from a larger field down to a smaller base field—on the product of $\alpha$ and an element from our defining set:
$$c_\alpha = \left( \text{Tr}(\alpha d_1), \text{Tr}(\alpha d_2), \dots, \text{Tr}(\alpha d_n) \right)$$
As noted by Wei Lü et al. in The weight hierarchies of three classes of linear codes, this mechanism directly couples the geometric and algebraic distribution of the elements within $D$ to the weight properties of the resulting code. The Hamming weight of the codeword $c_\alpha$ is simply the number of coordinates where $\text{Tr}(\alpha d_i) \neq 0$. Therefore, controlling the weights of the code reduces to a single geometric problem: choosing a set $D$ such that any linear hyperplane intersects $D$ in only a few possible sizes.
Constructing Defining Sets via Special Functions
How do we choose a set $D$ that satisfies this strict geometric property? The standard strategy is to define $D$ as the "level set" or root system of specific algebraic functions that possess highly regular structures.
For example, Shudi Yang et al. in Complete weight enumerators of a class of two-weight linear codes isolate specific algebraic conditions using trace functions to construct defining sets. Because the underlying equations have highly symmetric solution sets, the resulting linear codes are guaranteed to possess at most three distinct weights.
Instead of a single function, we can also use pairs of functions to define coordinates in a multi-dimensional space. Shudi Yang et al. in Linear Codes from Two Weakly Regular Plateaued Balanced Functions demonstrate a general framework where the defining set is constructed from two separate functions, $f$ and $g$, via the relation:
$$D_{f,g} = \{(x,y) : f(x) + g(y) = c\}$$
By choosing $f$ and $g$ from specific classes of functions (like weakly regular plateaued functions), the authors ensure that the joint distribution of their outputs is highly constrained, limiting the resulting code to at most five nonzero weights. Similarly, Dabin Zheng et al. in Binary linear codes with few weights from Boolean functions apply pairs of Boolean functions to construct defining sets that restrict binary linear codes to just three or four distinct Hamming weights.
Why It Works: The Role of Spectral Analysis
The reason these function-based defining sets work so reliably comes down to character sums and spectral analysis.
When calculating the weight of a codeword, we are essentially counting how often $\text{Tr}(\alpha d_i) = 0$ for $d_i \in D$. Mathematically, this counting problem can be translated into evaluating exponential sums over the finite field.
When the defining set is built from classical algebraic varieties, these sums manifest as Gauss sums or Weil sums. As shown by Gaopeng Jian et al. in Two-weight and three-weight linear codes based on Weil sums, the deep arithmetic properties of Weil sums naturally restrict the possible values that these character sums can take, yielding exact formulas for the weight distributions and proving that the codes are optimal or near-optimal relative to theoretical limits like the Griesmer bound.
When dealing with Boolean or $p$-ary functions, the primary tool for analyzing these sums is the Walsh transform. The Walsh transform measures how close a given function is to an affine linear function. If a function has a restricted "Walsh spectrum"—meaning its Walsh transform yields only a few distinct values—it implies that the function behaves with a high degree of predictable regularity when intersected by linear hyperplanes.
Dabin Zheng et al. demonstrate that identifying specific spectral conditions (such as the product condition $f(w)f(w+1)=0$) allows designers to precisely dictate the weight distribution of the final code. To exploit this, Ziling Heng et al. in Two families of linear codes with desirable properties from some functions over finite fields utilize monomial and weakly regular bent functions—functions known for having perfectly flat or highly symmetric Walsh spectra. By evaluating trace functions over defining sets derived from these bent functions, the authors systematically construct highly efficient codes tailored for distributed storage and hardware security.
Generalizations and Structural Bridges
The connection between a function's Walsh spectrum and the weight distribution of a code is not an isolated coincidence; it is a reflection of underlying algebraic structures called association schemes.
Yansheng Wu et al. in Characterization of p-ary functions in terms of association schemes and its applications established a direct, explicit criterion showing that a $p$-ary function's Walsh spectrum determines whether it can generate an association scheme. These combinatorial schemes act as an intermediate bridge: a well-behaved spectrum creates a structured association scheme, which in turn provides the exact defining sets needed to generate novel two-weight linear codes.
[p-ary / Boolean Function]
│
▼ (Restricted Walsh Spectrum)
[Association Scheme / Poset / Simplicial Complex]
│
▼ (Defines Geometric Constraints)
[Algebraic Defining Set D]
│
▼ (Trace Evaluation)
[Few-Weight Linear Code]
This structural perspective allows the defining set methodology to be generalized beyond standard finite fields into other mathematical objects:
- Simplicial Complexes and Posets: Rather than using raw functions, Yansheng Wu et al. in Quaternary Codes and Their Binary Images use simplicial complexes to construct quaternary (four-valued) codes with a limited number of Lee weights. Similarly, Xiaomeng Zhu 0002 et al. in New Quaternary Codes Derived from Posets of the Disjoint Union of Two Chains leverage partially ordered sets (posets) to build quaternary families that map down to optimal binary linear codes.
- Algebraic-Geometric Codes: Moving to higher-dimensional curves, Ma Liang et al. in Vectorial resilient PC(l) of order k Boolean functions from AG-codes use algebraic-geometric (AG) codes as a generalized framework to construct highly resilient vectorial Boolean functions, offering fine-grained control over cryptographic parameters.
Ultimately, the defining set method succeeds because it transforms a difficult combinatorial search for error-correcting codes into a manageable problem of algebraic design. By selecting functions with clean spectral properties, coding theorists can pre-program the geometric intersections of their sets, ensuring the resulting codes have the exact, constrained weight distributions required for modern communication and security.
Key Foundational Work
Complete weight enumerators of a class of two-weight linear codes (2019) — contributed 1 concept elements to this direction.
Two-weight and three-weight linear codes based on Weil sums (2019) — contributed 1 concept elements to this direction.
Vectorial resilient PC(l) of order k Boolean functions from AG-codes (2010) — contributed 1 concept elements to this direction.