🔢 mathematics

Function-Based Minimal Linear Codes over Galois Rings $\mathrm{GR}(p^{n}, \ell)$ : Minimality Criteria and Infinite Constructions

This paper extends minimality criteria and length bounds for linear codes from finite fields to Galois rings by overcoming algebraic challenges posed by zero divisors, and utilizes these refined conditions to construct infinite families of minimal linear codes over $\mathrm{GR}(p^{n}, \ell)$ .

Original authors: Biplab Chatterjee, Sihem Mesnager, Ratnesh Kumar Mishra, Makhan Maji, Kalyan Hansda

Published 2026-03-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Biplab Chatterjee, Sihem Mesnager, Ratnesh Kumar Mishra, Makhan Maji, Kalyan Hansda

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 a master architect designing a secret vault system. In this system, you have a large group of people (the "codewords"), and each person holds a unique key to a specific set of doors.

The goal of this paper is to design a system where every single key is "minimal."

What does "Minimal" mean?

Think of a key as a list of doors it can open.

Key A opens doors {1, 2, 3}.
Key B opens doors {1, 2}.

If Key A opens everything Key B opens (and more), then Key A is "redundant" or "covering" Key B. In a Minimal Linear Code, this is forbidden. Every key must open a unique combination of doors that no other key can fully replicate. If two keys open the same set of doors, they must be essentially the same key (just a different color or size).

Why do we care? Because in Secret Sharing (like splitting a nuclear launch code among 5 generals), you want to know exactly who is needed to open the vault. If you have redundant keys, the rules get messy. Minimal codes ensure the rules are crystal clear.

The Big Shift: From "Fields" to "Rings"

For a long time, mathematicians built these vaults using Finite Fields.

The Analogy: Think of a Field like a perfectly smooth, frictionless ice rink. If you push a puck (a number), it slides perfectly. You can always divide by any non-zero number. It's simple and predictable.

But the authors of this paper decided to build vaults using Galois Rings.

The Analogy: Think of a Ring like a bumpy, muddy construction site.
- Here, you have Zero Divisors. Imagine a "sticky mud" (zero divisors) that can stop a moving object even if it wasn't zero to begin with. If you multiply a number by this mud, it might turn into zero.
- This makes the math much harder. You can't just divide freely. The structure is "chain-like," meaning things get stuck in layers of mud (ideals) before they disappear completely.

The Problem the Authors Solved

The paper asks: "How do we design a perfect, minimal vault system on this bumpy, muddy construction site?"

Previous researchers (like Wu et al.) had figured out how to do this on the smooth ice rink (Fields). They used a clever trick: they defined the keys using a Function (a recipe).

Recipe: "Take a number, plug it into this formula, and that tells you which doors to open."

The authors of this paper asked: "Can we use this same recipe trick on the muddy construction site?"

The Solution: The "Root Word" Filter

The authors discovered a brilliant way to simplify the mess. They realized that even though the construction site is muddy, the most important keys are the ones that are "clean" (not stuck in the mud).

They called these Root Words.

The Metaphor: Imagine the muddy site has a "clean zone" at the top. If a key is in the clean zone, it behaves like a normal key on the ice rink. If it's stuck in the mud, it's a "zero divisor."
The Discovery: The authors proved that if you make sure all the clean keys (Root Words) are minimal, then the whole system is minimal. You don't need to worry about the muddy, stuck keys creating problems, as long as the clean ones are perfect.

How They Built the Codes

They used a Function-Based Construction.

The Function: They created a mathematical recipe (a function) that takes a location on the map and spits out a number.
The Rules: They set strict rules for this recipe:
- If you give it a "small" input (few doors), it must output a "clean" number.
- If you give it a "big" input (all doors), it must output zero or a specific "muddy" number depending on the situation.
The Result: By following these rules, they generated infinite families of these perfect vault systems. No matter how big the vault gets, the system remains minimal and secure.

Why This Matters

Better Security: These codes are essential for Secret Sharing and Secure Voting. If you are voting in a blockchain or a secure election, you want to ensure that no group of voters can accidentally cover the rights of a smaller group. Minimal codes prevent this confusion.
Post-Quantum Future: As we move toward quantum computers, traditional encryption might break. These "Ring-based" codes are part of the new generation of cryptography that is harder for quantum computers to crack.
Generalizing the World: They took a rule that worked in a simple world (Fields) and proved it works in a complex, messy world (Rings). This is like taking a rule for driving on a highway and proving it works for driving in a chaotic, rainy city with potholes.

Summary

The authors took a complex mathematical problem about "minimal codes" (perfectly unique keys for secret vaults) and solved it for a difficult type of number system called Galois Rings.

They did this by:

Realizing that if the "clean" keys work, the whole system works.
Creating a new set of rules for the "recipe" (function) used to generate these keys.
Proving that this works for an infinite number of vault sizes.

This opens the door to building more secure, efficient, and robust communication systems for the future, especially in the era of quantum computing.

1. Problem Statement

The paper addresses the construction and characterization of minimal linear codes over Galois rings $GR(p^n, \ell)$ .

Context: Minimal linear codes are crucial for secret sharing schemes, multiparty computation (MPC), and secure information distribution because minimal codewords correspond to minimal qualified subsets in access structures.
Gap: While minimal codes over finite fields are well-studied (notably via function-based constructions by Wu et al.), the extension to finite rings is significantly more complex due to the presence of zero divisors, non-trivial ideals, and a richer module structure.
Objective: The authors aim to:
1. Establish necessary and sufficient conditions for a linear code over $GR(p^n, \ell)$ to be minimal.
2. Generalize the function-based construction framework (from finite fields) to Galois rings.
3. Derive explicit bounds on the length of minimal codes and construct infinite families of such codes.

2. Methodology and Theoretical Framework

The authors employ a combination of module theory, Frobenius duality, and valuation analysis to navigate the algebraic complexities of Galois rings.

A. Algebraic Structure of $GR(p^n, \ell)$

Chain Ring Properties: $GR(p^n, \ell)$ is a finite local chain ring with maximal ideal $\langle p \rangle$ and residue field $\mathbb{F}_q$ (where $q=p^\ell$ ).
Zero Divisors vs. Units: Elements are classified as units (non-zero mod $p$ ) or zero divisors (multiples of $p$ ). This dichotomy drives the complexity of the minimality criteria.
Root Words: A vector $v \in GR(p^n, \ell)^m$ is defined as a root word if at least one of its components is a unit (equivalently, $v \not\in p GR(p^n, \ell)^m$ ). Root words behave similarly to non-zero vectors in vector spaces, whereas non-root words exhibit torsion.

B. Minimality Criteria via Orthogonal Modules

The core theoretical tool is the relationship between a codeword's support and its orthogonal module $v^\perp$ .

Duality: Since $GR(p^n, \ell)$ is a Frobenius ring, the double-orthogonality property $(C^\perp)^\perp = C$ holds.
Characterization: A linear code $C$ is minimal if and only if for every non-zero codeword $c$ , the submodule generated by the annihilators of $c$ within the defining set equals the full orthogonal module of the corresponding vector.
Key Theorem (Theorem 17): For dimension $m \ge 2$ , a code is minimal if and only if all its root words are minimal. This reduces the global minimality problem to analyzing specific "root" vectors, effectively bypassing the need to check all torsion elements individually.

C. Function-Based Construction

The paper constructs codes $C_f$ using a generator matrix derived from a function $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$ .

Generator Matrix: The rows correspond to the evaluation of the function and the identity map.
Synchronization Conditions: To ensure minimality, the function $f$ $f$ must satisfy specific "synchronization" conditions with linear forms $w \cdot x$ $w \cdot x$ .
- Unit Case: $f(\beta_i) = w \cdot \beta_i$ .
- Zero-Divisor Case: $p^r f(\beta_i) = w \cdot \beta_i$ (reflecting the valuation of the zero divisor).

3. Key Contributions

1. Complete Minimality Characterization

The authors provide a rigorous necessary and sufficient condition for minimality over $GR(p^n, \ell)$ . They prove that for $m \ge 2$ , the minimality of the entire code is determined solely by the behavior of root words. This generalizes previous results from $\mathbb{Z}_{p^n}$ to the broader class of Galois rings.

2. Classification of Root Words

The analysis identifies five distinct types of root words in the constructed codes, each requiring specific conditions on the function $f$ :

$c(u, 0)$ : Unit scalar, zero vector.
$c(u, v)$ : Unit scalar, root word vector.
$c(u, v)$ : Unit scalar, non-root word vector.
$c(0, v)$ : Zero scalar, root word vector.
$c(d, v)$ : Zero-divisor scalar, root word vector.

3. New Lower Bounds on Code Length

The paper derives explicit lower bounds for the length $k$ of an $m$ -dimensional minimal linear code over $GR(p^n, \ell)$ :

For $m \ge 3$ : $k > (m-1)q^n + q^{n-m}$ .
For $m = 2$ : Specific bounds depending on $n$ (e.g., $k > q^n + q^{n-2} + 1$ for $n \ge 3$ ).
These bounds are shown to be tight in specific cases, matching known results for finite fields when $n=1$ .

4. Infinite Families of Minimal Codes

Using the derived criteria, the authors construct several infinite families of minimal codes:

General Function Construction: They define functions satisfying specific weight and unit-component conditions (Theorem 40 and Theorem 43) to guarantee minimality.
Polynomial Construction: A concrete family is constructed using multivariate polynomials with disjoint monomial supports (Theorem 45). This provides an easily verifiable method for generating minimal codes.

4. Key Results

Theorem 17: Establishes that for $m \ge 2$ , checking the minimality of root words is sufficient for the whole code.
Proposition 24: Proves that for $m=2$ , the minimal length is exactly $k(2; GR(p^n, \ell)) = q^n + q^{n-1}$ , generalizing the result for $\mathbb{Z}_{p^n}$ .
Theorem 40 & 43: Provide sufficient conditions on a function $f$ (involving unit invariance and specific values on vectors of specific Hamming weights) such that the resulting code $C_f$ is minimal.
Theorem 45: Demonstrates that polynomials of the form $f(x) = \sum a_i g_i(x)$ with disjoint supports and specific exponent constraints yield minimal codes.

5. Significance and Impact

Unification: The work unifies minimality theory across finite fields and Galois rings, showing that the "root word" concept is the fundamental invariant governing minimality in chain rings.
Algebraic Insight: It clarifies how zero divisors and valuation filtration affect code structure. Specifically, it shows that while zero divisors introduce torsion, they do not create new minimality obstructions beyond those captured by the root word analysis (for $m \ge 2$ ).
Cryptographic Applications: By providing explicit infinite families of minimal codes over rings, the paper opens new avenues for:
- Secret Sharing Schemes: More flexible access structures over ring-based alphabets.
- Post-Quantum Cryptography: Ring-based constructions are relevant for lattice-based schemes.
- Decentralized Systems: Applications in blockchain and secure voting where ring structures are natural.
Future Directions: The paper outlines open problems regarding weight distributions, few-weight codes, and extensions to general Frobenius rings, setting a roadmap for future research in coding theory over rings.

In summary, this paper successfully bridges the gap between field-based coding theory and ring-based algebra, providing a robust theoretical framework and practical construction methods for minimal linear codes over Galois rings.