🔢 mathematics

Weight distributions of two classes of linear codes with few weights derived from Weil sums

This paper constructs two distinct classes of $p$ -ary linear codes with few nonzero weights by selecting specific defining sets, determines their complete weight distributions through detailed Weil sum calculations, and identifies an infinite family of two-weight optimal codes along with several minimal codes.

Original authors: Mrinal Kanti Bose, Abhay Kumar Singh

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mrinal Kanti Bose, Abhay Kumar Singh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a massive, ultra-secure vault system. To protect the contents, you need a set of unique keys (called linear codes). Some keys are very simple, while others are complex. In the world of cryptography, "simple" keys are often better because they are easier to manage and verify. Specifically, mathematicians love keys that have a very specific, predictable pattern of "weights" (a measure of how complex or "heavy" the key is).

This paper is like a blueprint for two new, highly specialized vault designs. The authors, Mrinal Kanti Bose and Abhay Kumar Singh, have created two new families of these "keys" and proved exactly how they behave.

Here is a breakdown of their work using everyday analogies:

1. The Goal: Finding the Perfect "Light" Keys

In the world of error-correcting codes (which help computers fix corrupted data), having a code with "few weights" is like having a set of keys that all look almost identical.

The Problem: Most keys are messy and have many different shapes (weights). This makes them hard to use in secret sharing schemes (where a secret is split among many people) or in creating secure authentication systems.
The Solution: The authors wanted to build keys that only come in a few specific "sizes" (2, 4, 6, 8, or 9 different sizes). This makes them predictable and efficient.

2. The Construction: Building with Special Bricks

To build these codes, the authors used a method called the Defining Set Approach.

The Analogy: Imagine you have a giant grid of tiles (a finite field). You need to pick out specific tiles to build your code. The rule for picking the tiles is the "defining set."
The Innovation: The authors didn't just pick tiles randomly. They used two very specific, mathematical recipes (equations) to select their tiles:
1. Recipe A: A rule involving a sum of two numbers where one is raised to a special power.
2. Recipe B: A rule involving a "weakly regular bent function." Think of this as a special, wavy pattern that ensures the tiles are distributed in a perfectly balanced, non-repeating way.

3. The Math Magic: The "Weil Sum" Telescope

How did they know exactly how many different "sizes" (weights) their keys would have? They used a mathematical tool called Weil sums.

The Analogy: Imagine you are looking at a distant landscape through a telescope. The landscape is full of confusing, swirling clouds (complex numbers). The Weil sum is a special lens that focuses that chaos into a clear, countable number.
The Result: By looking through this "lens," the authors could calculate exactly how many keys would have a weight of 100, how many would have a weight of 105, and so on. They didn't have to guess; they could count them perfectly.

4. The Discoveries: What They Found

After doing the heavy lifting with their "telescope," they found two main classes of codes with surprising properties:

Class 1 (The "Simple" Set): Depending on the settings they chose, they found codes that only had 2, 4, 6, 8, or 9 different weights.
- The Highlight: They found an infinite family of codes that only have two weights. These are the "Goldilocks" codes—not too many weights, not too few.
- The "Optimal" Badge: One of these two-weight families is optimal. This means it hits the theoretical limit of efficiency (the Griesmer bound). It's like building a bridge that uses the absolute minimum amount of steel possible while still holding the weight. You can't build it any better.
Class 2 (The "Bent" Set): Using the wavy "bent function" recipe, they found codes with 6, 8, or 9 weights.
- The "Minimal" Badge: They also discovered that under certain conditions, these codes are minimal.
- What does "Minimal" mean? Imagine a key that is so unique that it cannot be "covered" or hidden by any other key in the set. It stands alone. This is a crucial property for secret sharing schemes, ensuring that no single person can accidentally or maliciously reconstruct the secret without the full group.

5. Why Does This Matter? (According to the Paper)

The paper explicitly states that these "few-weight" codes are useful for:

Secret Sharing: Splitting a secret (like a bank password) among a group so that only a specific number of people can unlock it.
Authentication Codes: Verifying that a message is truly from the sender and hasn't been tampered with.
Graph Theory: Creating specific types of networks (strongly regular graphs) used in computer science.

Summary

In short, Bose and Singh have designed two new, mathematically rigorous blueprints for digital keys. They proved that these keys are incredibly efficient (optimal) and have a very clean, predictable structure (few weights). They used advanced mathematical "telescopes" (Weil sums) to count every single variation of these keys, ensuring that engineers and cryptographers can use them with absolute confidence in building secure systems.

Technical Summary: Weight Distributions of Two Classes of Linear Codes Derived from Weil Sums

Problem Statement
Linear codes with few weights are of significant interest in coding theory due to their applications in secret sharing schemes, authentication codes, association schemes, and strongly regular graphs. A primary challenge in this field is the construction of new families of linear codes with specific weight distributions (i.e., a small number of distinct non-zero weights) and the determination of their parameters (length, dimension, and minimum distance). While previous works have utilized defining sets based on trace functions and specific polynomial forms to construct such codes, there remains a need to explore new defining sets that leverage advanced evaluations of exponential sums, particularly binomial Weil sums, to generate codes with diverse weight structures.

Methodology
The authors construct two distinct classes of $p$ -ary linear codes over a finite field $\mathbb{F}_q$ , where $q = p^e$ , $p$ and $\ell$ are distinct odd primes, and $e = \phi(\ell^k)$ . The construction relies on the defining-set approach, where a linear code $C_D$ is defined as:
$C_D = \{c(\gamma, \delta) = (\text{Tr}_1^e(\gamma x + \delta y))_{(x,y) \in D} : \gamma, \delta \in \mathbb{F}_q\}$
The paper investigates two specific defining sets, $D_u$ and $D'$ , which differ from prior constructions by incorporating a specific binomial Weil sum structure.

Defining Set $D_u$ : Defined as $D_u = \{(x, y) \in \mathbb{F}_q^2 \setminus \{(0,0)\} : \text{Tr}_1^e(x + y^N) = u\}$ , where $N = \frac{q-1}{2\ell^k}$ and $u \in \mathbb{F}_p$ .
Defining Set $D'$ : Defined as $D' = \{(x, y) \in \mathbb{F}_q^2 \setminus \{(0,0)\} : f(x) + \text{Tr}_1^e(y^N) = 0\}$ , where $f$ is a weakly regular bent function from $\mathbb{F}_q$ to $\mathbb{F}_p$ satisfying specific homogeneity conditions on its dual.

The core methodology involves the detailed evaluation of exponential sums, specifically the binomial Weil sum $S_{2\ell^k}(a, b)$ and related sums over cyclotomic fields. The authors utilize:

Properties of canonical additive and quadratic multiplicative characters.
Evaluations of Gauss sums and Weil sums derived from recent works by Cheng, Gao, and Sheng.
The theory of weakly regular bent functions and their duals.
Partitioning of index sets based on the order of elements in the multiplicative group to handle the trace conditions.

By calculating the number of solutions to the defining equations for various pairs $(\gamma, \delta)$ , the authors derive the Hamming weights of the codewords and their corresponding frequencies.

Key Contributions and Results
The paper provides a complete characterization of the parameters and weight distributions for the constructed codes under various conditions on $p$ , $\ell$ , $k$ , and $u$ .

Codes from $D_u$ :
- The authors determine the weight distributions for five distinct cases based on the value of $u$ and the congruence of $\ell$ modulo $p$ .
- The resulting codes exhibit two, four, or six non-zero weights.
- Specifically, when $u \neq 0$ and certain quadratic non-residue conditions are met, the construction yields an infinite family of two-weight linear codes.
- Under specific conditions (where the ratio of minimum to maximum weight exceeds $\frac{p-1}{p}$ ), these codes are proven to be minimal, making them suitable for secret sharing applications.
Codes from $D'$ :
- By incorporating a weakly regular bent function $f$ , the authors construct codes with more complex weight structures.
- Depending on the congruence of $p$ modulo 4 and the relationship between $\ell$ and $p$ , the codes are shown to have six, eight, or nine non-zero weights.
- The weight distributions are explicitly tabulated for all cases, involving terms derived from the sign of the Walsh transform of $f$ and quadratic character evaluations.
Optimality:
- A significant result is the identification of an infinite family of two-weight optimal linear codes derived from the $D_u$ construction. These codes meet the Griesmer bound, a fundamental lower bound on the length of a linear code given its dimension and minimum distance.

Significance
The paper claims significance in the following areas:

Novelty of Defining Sets: The defining sets used in this work introduce a new binomial Weil sum structure ( $S_{2\ell^k}(a, b)$ ) that differs from previous constructions summarized in the literature (e.g., those using simple trace functions or specific power maps).
Diversity of Weight Distributions: The work expands the known landscape of linear codes with few weights, providing explicit constructions for codes with 2, 4, 6, 8, and 9 non-zero weights.
Optimality and Minimality: The construction of an infinite family of optimal two-weight codes meeting the Griesmer bound is a notable contribution to the search for efficient error-correcting codes. Furthermore, the identification of minimal codes under specific conditions reinforces the utility of these constructions in cryptographic applications like secret sharing.
Methodological Rigor: The paper demonstrates a rigorous application of Weil sums and cyclotomic field theory to solve the problem of weight distribution determination, offering a template for analyzing similar code constructions.

The authors conclude that their work successfully generalizes previous methods and provides a rich source of new linear codes with desirable properties for both theoretical study and practical application.