🔢 mathematics

A Generic Construction of $q$ -ary Near-MDS Codes Supporting 2-Designs with Lengths Beyond $q+1$

This paper presents the first generic construction of an infinite family of $q$ -ary near-MDS codes supporting 2-designs with lengths exceeding $q+1$ , achieved by establishing new connections between elliptic curve codes, finite abelian groups, subset sums, and combinatorial designs.

Original authors: Hengfeng Liu, Chunming Tang, Zhengchun Zhou, Dongchun Han, Hao Chen

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hengfeng Liu, Chunming Tang, Zhengchun Zhou, Dongchun Han, Hao Chen

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 trying to build the most efficient, unbreakable vaults (codes) to store secret messages. In the world of mathematics, these vaults are called Linear Codes.

For decades, architects had a golden rule: "To make a vault perfectly secure and efficient, you can't make it too long." Specifically, if you are working with a specific type of building material (a finite field with $q$ elements), the longest perfect vault you could build was limited to a length of $q + 1$ . This was like a law of physics in their world.

However, some architects discovered "Near-MDS" codes. These are vaults that are almost perfect—just a tiny bit less efficient than the gold standard, but still incredibly strong. The big mystery was: Can we build these "near-perfect" vaults that are longer than the $q + 1$ limit, while still keeping a special, hidden pattern inside them?

This paper says: Yes, we can. And here is how they did it, explained simply.

1. The Problem: The "Length Limit" Wall

Think of the $q + 1$ limit as a wall. For a long time, everyone thought you couldn't build a secure, patterned vault beyond this wall.

MDS Codes: The "Perfect Vaults." They hit the wall but can't go past it.
NMDS Codes: The "Near-Perfect Vaults." They are slightly more flexible. Theoretically, they could go past the wall, but nobody knew how to build them with the special patterns required for advanced applications (like cryptography or data storage).

The only examples found so far were like "one-off" miracles—rare, weird, and impossible to replicate. The authors wanted to build a factory (a generic construction) to mass-produce these long, patterned vaults.

2. The Solution: The "Elliptic Curve" Playground

To break the wall, the authors used a tool from a different part of math: Elliptic Curves.

Imagine an elliptic curve not as a line, but as a magical, curved playground.

The Points: On this playground, there are specific spots where you can stand (called "rational points").
The Group: These points have a special rule: if you stand on two points and "add" them together according to the playground's geometry, you land on a third point. It's like a dance where every move is predictable.

The authors realized that if they treated these points like numbers in a giant, curved group, they could build their codes.

3. The Secret Ingredient: "Subset Sums"

Here is the magic trick. The authors looked at the problem of Subset Sums.

Imagine you have a bag of marbles (the points on the curve).
You want to pick a specific number of marbles (say, $k$ marbles) so that when you "add" them up using the playground's rules, they cancel each other out to zero (or a specific target).

The paper proves a beautiful connection:

If you can find these special groups of marbles that sum to zero, you can build a Near-Perfect Vault (NMDS Code).
Even better, the way these marbles are arranged forms a 2-Design.

4. What is a "2-Design"? (The Hidden Pattern)

Think of a 2-Design as a perfectly balanced team roster.

Imagine you have a huge pool of players (the points).
You need to form teams (blocks).
A 2-Design ensures that any two players you pick from the pool will appear together in exactly the same number of teams.

This balance is crucial for cryptography and error correction. It means the system is fair, robust, and has no weak spots.

5. The Breakthrough: Breaking the Wall

The authors combined these ideas:

They picked specific elliptic curves where the points form a very specific, symmetrical group (like a grid of points).
They used the "Subset Sum" rules to prove that these groups naturally create the balanced "2-Design" pattern.
They built the code based on these points.

The Result: They created an infinite family of codes that are:

Near-Perfect (NMDS): Strong and efficient.
Long: They stretch beyond the $q + 1$ wall (some are as long as $q + 2\sqrt{q}$ ).
Patterned: They hold the precious 2-Design structure.

6. Why Does This Matter?

Before this paper, if you wanted a long, secure code with a perfect pattern, you were stuck. You either had to accept a short code or a code without the pattern.

Now, the authors have handed the world a blueprint.

For Cryptographers: You can now build longer, more secure encryption keys that are harder to crack.
For Data Centers: You can store data more efficiently with better error correction (fixing corrupted data) over longer distances.
For Mathematicians: They solved a 70-year-old puzzle about whether these specific types of codes could even exist in large numbers.

The Analogy Summary

Imagine you are trying to arrange tiles on a floor.

Old Rule: You can only make a perfect, balanced pattern if the floor is small (size $q+1$ ).
The New Discovery: The authors found a way to use a "curved mirror" (the elliptic curve) to reflect the tiles. By looking at the reflection, they realized they could arrange the tiles on a much larger floor (length $> q+1$ ) and still keep the perfect balance (the 2-Design).

They didn't just find one big floor; they found a recipe to build infinite floors of any size you want, all with that perfect, hidden balance.

1. Problem Statement

The paper addresses a significant gap in coding theory and combinatorial design theory regarding Near-Maximum Distance Separable (NMDS) codes.

Context: An $[n, k, d]$ linear code is MDS if $d = n-k+1$ and NMDS if both the code and its dual are Almost MDS (AMDS), meaning $d = n-k$ and $d^\perp = k$ .
The Challenge: While MDS codes are known to support trivial designs, NMDS codes are of high interest because they can support non-trivial $t$ -designs. Prior to this work, known constructions of NMDS codes supporting 2-designs were limited to lengths $n \leq q + 1$ .
The Gap: Although NMDS codes with lengths $n > q + 1$ exist (up to $2q+k$ ), finding infinite families of such codes that simultaneously support 2-designs has been an open problem. Existing examples were sporadic (limited to specific binary or ternary cases) and lacked a general construction method.

2. Methodology

The authors propose a generic construction that bridges three distinct mathematical fields: Elliptic Curve Codes, Finite Abelian Groups, and Subset Sums.

Elliptic Curve Codes (AG Codes): The construction utilizes algebraic geometry codes defined over elliptic curves $E$ over a finite field $\mathbb{F}_q$ . The code is generated by evaluating functions from a Riemann-Roch space $L(D)$ at a set of rational points $P \subset E(\mathbb{F}_q)$ .
Connecting Code Properties to Subset Sums:
- The authors establish a criterion (Proposition 4) linking the NMDS property of the code to the subset sum problem in the group of rational points $E(\mathbb{F}_q)$ .
- Specifically, the code is NMDS if and only if there exists a subset of $k$ points in $P$ whose sum (under the elliptic curve group operation $\oplus$ ) equals a specific divisor point $Q_D$ .
Leveraging Group Structure:
- The construction focuses on elliptic curves where the group of rational points is isomorphic to $\mathbb{Z}_p \oplus \mathbb{Z}_p$ (an elementary abelian $p$ -group).
- They utilize known results on subset sums in finite abelian groups (specifically Theorem 10 and 11) to determine when these sums form $t$ -designs.
Design Derivation:
- By ensuring the subset sums form a 2-design in the group $E(\mathbb{F}_q)$ , the supports of the minimum-weight codewords in the resulting linear code automatically form a 2-design.
- The authors use the Generalized Assmus-Mattson Theorem (Theorem 3) to prove that all codewords of fixed weight in these codes support 2-designs, even though they fail the conditions of the classical Assmus-Mattson Theorem.

3. Key Contributions

First Generic Construction for $n > q+1$ : The paper presents the first infinite family of $q$ -ary NMDS codes with length $n = p^2$ (where $p^2 > q+1$ ) that support 2-designs. This breaks the previous barrier where such codes were only known for $n \leq q+1$ .
Novel Connection: It establishes a rigorous link between the support designs of elliptic curve codes and subset sums in the group $E(\mathbb{F}_q) \cong \mathbb{Z}_p \oplus \mathbb{Z}_p$ .
Explicit Parameters and Weight Distributions:
- The authors provide explicit conditions on $q$ and $p$ (e.g., $p$ is an odd prime, $p | q-1$ , and specific bounds on $p^2 - q - 1$ ) to guarantee the existence of the required elliptic curves.
- They derive the exact weight distribution of the constructed codes and their duals using formulas for subset sums in abelian groups.
New Combinatorial Designs: The construction yields new families of 2-designs (specifically 2- $(p^2, p^2-2k, \lambda)$ designs) that were previously unknown or only available sporadically.

4. Key Results

Theorem 14: For a prime power $q \geq 7$ $q \geq 7$ and an odd prime $p$ $p$ satisfying specific number-theoretic conditions (related to the Hasse-Weil bound and group structure), there exists an NMDS code with parameters $[p^2, 2k, p^2-2k]$ $[p^{2}, 2 k, p^{2} - 2 k]$ .
- The minimum-weight codewords support a 2-design with block size $p^2-2k$ .
- The dual code $[p^2, p^2-2k, 2k]$ also supports a 2-design.
- Crucially, the length $n = p^2$ exceeds $q+1$ (since $p^2 \approx q + 2\sqrt{q}$ ).
Weight Distribution: The paper provides closed-form formulas for the number of codewords of any weight $w$ ( $A_w$ ) and for the dual code ( $A^\perp_w$ ).
Numerical Examples:
- Example 1: For $q=7, p=3$ , the construction yields a $[9, 6, 3]$ NMDS code. The minimum weight codewords form a Steiner Triple System $S(2, 3, 9)$ .
- Table IV: Lists 38 specific parameter sets $(q, p)$ found via computer search (with $p < 2000$ ) that satisfy the construction criteria, generating codes with lengths up to $3948169$.
Theoretical Limitation: The constructed codes satisfy the Generalized Assmus-Mattson theorem but fail the classical Assmus-Mattson theorem, highlighting the necessity of the generalized approach for these long codes.

5. Significance

Breaking the $q+1$ Barrier: This work fundamentally expands the known landscape of NMDS codes supporting designs. It proves that long NMDS codes (lengths significantly exceeding $q+1$ ) can possess strong combinatorial structures, challenging the intuition that long codes are "random" or lack design properties.
Unification of Fields: The paper successfully unifies algebraic geometry (elliptic curves), additive combinatorics (subset sums), and design theory. This methodology offers a new toolkit for constructing codes with specific combinatorial properties.
Future Research: The authors conjecture that infinitely many such parameters exist, suggesting an infinite family of these codes. The work opens avenues for exploring $t$ -designs with $t > 2$ using different elliptic curve group structures and investigating the weight distributions of other extremal NMDS codes.

In summary, this paper solves a long-standing open problem by providing a systematic, generic method to construct long NMDS codes that support 2-designs, utilizing the rich structure of elliptic curve rational points and subset sums.