Linear Codes from Algebraic Defining Sets

22 concepts10 papers1 proposal

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_defining_set_construction_2c5a8615,
  title = {defining set construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/defining-set-construction/rdr_2c5a8615759f448abfaa4dec512846a5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_defining_set_construction_2c5a8615_v1,
  title = {defining set construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/defining-set-construction/rdr_2c5a8615759f448abfaa4dec512846a5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake