🔢 mathematics

Perfect codes in weakly metric association schemes

This paper introduces the concept of polynomial weakly metric association schemes and combines the Lloyd Theorem with the Schwartz-Zippel Lemma to derive non-existence results for perfect codes in various metrics, including Lee, NRT, mixed Hamming, and sum-rank distances.

Original authors: Minjia Shi, Jing Wang, Patrick Solé

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Minjia Shi, Jing Wang, Patrick Solé

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 trying to pack a giant, multi-dimensional warehouse with identical, perfectly round boxes. Your goal is to arrange these boxes so that every single square inch of the warehouse floor is covered by exactly one box, with no gaps and no overlaps. In the world of mathematics and coding theory, this is called finding a "perfect code."

This paper by Shi, Wang, and Solé is essentially a detective story. The authors are trying to figure out: "In which specific types of warehouses is it mathematically impossible to pack these boxes perfectly?"

Here is how they solve the mystery, broken down into simple concepts:

1. The Warehouse and the Rules (The Setting)

In coding theory, data is sent as a list of numbers (like a long string of 0s and 1s, or numbers in a different language).

The Space: Think of the "warehouse" as a giant grid where every point represents a possible message.
The Distance: Usually, we measure distance by counting how many letters are different (like spelling "cat" vs. "bat" is a distance of 1). But in this paper, they look at more complex ways to measure distance, like the Lee metric (where numbers wrap around like a clock) or the NRT metric (where the position of a number matters more than the number itself).
The Perfect Code: A perfect code is a set of "center points" (messages) such that if you draw a circle (or sphere) of a certain size around each center, those circles cover the entire warehouse perfectly without overlapping.

2. The Old Clue: The Lloyd Theorem

For decades, mathematicians have had a tool called the Lloyd Theorem. Think of this as a "magic checklist."

If a perfect code could exist, this theorem says a specific mathematical recipe (a polynomial equation) must have a certain number of "roots" (solutions) that are whole numbers.
If the recipe doesn't have enough whole-number solutions, then a perfect code cannot exist.

However, the old checklist was limited. It worked well for simple, standard warehouses (like the Hamming metric), but it broke down or gave vague answers for the more complex, "weird" warehouses mentioned above (like the Lee or NRT metrics).

3. The New Tool: The Schwartz-Zippel Lemma

The authors decided to combine the old checklist with a new, powerful tool from computer science called the Schwartz-Zippel Lemma.

The Analogy: Imagine you have a giant, multi-colored cake (a multi-variable polynomial). You want to know if there are any spots on the cake that are "zero" (empty).
The Schwartz-Zippel Lemma is like a rule that says: "If you have a cake with a certain number of ingredients (variables) and a certain complexity (degree), there is a strict limit on how many empty spots you can possibly have."
The Twist: The authors realized that for these complex warehouses, the "magic checklist" (Lloyd Theorem) demands more empty spots than the Schwartz-Zippel rule says is physically possible.

4. The "Dispersion" Problem

To make this work, they introduced a new concept called the Dispersion Function.

Think of this as a "crowd meter." It counts how many different types of "neighborhoods" exist within a certain distance from the center.
In a simple warehouse, the crowd grows slowly (linearly). In these complex warehouses, the crowd grows explosively fast (exponentially).
The authors proved that because the crowd grows so fast in these specific metrics, the "magic checklist" demands a number of solutions that simply cannot fit within the limits set by the Schwartz-Zippel rule.

5. The Verdict: "No Perfect Codes Here"

By combining these two ideas, the authors derived a "Master Theorem." They applied it to four specific types of complex warehouses:

Lee Metric: Used for things like digital clocks or modular arithmetic.
NRT Metric: Used for generating random numbers and handling data blocks.
Sum-Rank Metric: Used in network coding (sending data across the internet).
Mixed Alphabet Codes: Where different parts of the message use different "languages" (e.g., some parts are binary, others are base-3).

The Result: For these four scenarios, under certain conditions (usually when the warehouse is very large or the boxes are a specific size), the math proves that perfect packing is impossible. The "crowd" is too big, and the "rules" don't allow for a perfect fit.

6. What They Didn't Do

It is important to note what this paper doesn't do:

They did not invent a new way to pack the boxes.
They did not say these codes are useless; they just proved that the perfect version of them doesn't exist in these specific settings.
They didn't solve a 50-year-old conjecture about all Lee codes (that remains open), but they provided strong evidence that perfect codes likely don't exist for large sizes.

Summary

The authors built a new mathematical "trap." They showed that for several important types of data transmission systems, the geometry of the space is so twisted that you can never arrange your error-correcting codes perfectly. If you try to force a perfect arrangement, the math says, "Nope, the numbers don't add up." This helps engineers know that they should stop looking for a "perfect" solution in these specific areas and instead focus on finding "good enough" solutions.

Technical Summary: Perfect Codes in Weakly Metric Association Schemes

Problem Statement
The paper addresses the fundamental problem of classifying the parameters of finite metric spaces that admit $e$ -perfect codes (codes where the space is partitioned into disjoint balls of radius $e$ ). While the Lloyd Theorem provides a necessary condition for the existence of such codes in standard metric association schemes (specifically, the vanishing of a Lloyd polynomial at integer points), many coding scenarios of interest—such as the Lee metric, NRT metric, mixed alphabets, and sum-rank distance—do not strictly satisfy the definition of a metric association scheme. Previous generalizations, such as the concept of "weakly metric association schemes" (WMAS) introduced by Solé (1989), established a generalized Lloyd theorem but had not yielded non-existence results for over three decades. The core challenge is to derive effective non-existence criteria for perfect codes in these broader, non-metric contexts.

Methodology
The authors combine two distinct mathematical frameworks to derive new non-existence results:

Generalized Lloyd Theorem in WMAS: They utilize the framework of weakly metric association schemes, where the Lloyd polynomial $\Psi^{(e)}(j)$ must vanish at least $\Pi(e) - 1$ times if an $e$ -perfect code exists. Here, $\Pi(e)$ is the "dispersion function," counting the number of classes yielding elements at distance at most $e$ .
Schwartz-Zippel Lemma: They apply the Schwartz-Zippel Lemma from theoretical computer science, which provides an upper bound on the number of zeros of a non-zero multivariate polynomial over a finite domain. Specifically, a polynomial of total degree $e$ in $r$ variables over a set $S$ can have at most $e \cdot |S|^{r-1}$ zeros.

To bridge these concepts, the authors introduce the notion of $r$ -polynomial association schemes. A WMAS is $r$ -polynomial if its first eigenvalues are polynomials in $r$ variables evaluated at specific points. By treating the Lloyd polynomial as a multivariate polynomial of degree at most $e$ , the authors compare the required number of zeros ( $\Pi(e) - 1$ ) against the maximum possible number of zeros allowed by the Schwartz-Zippel bound ( $e \cdot |S|^{r-1}$ ). If $\Pi(e) - 1 > e \cdot |S|^{r-1}$ , a contradiction arises, proving that no such perfect code can exist.

Key Contributions and Results
The paper establishes a master theorem (Theorem 2) stating that no $e$ -perfect code exists in an $r$ -polynomial WMAS if the dispersion function grows sufficiently fast relative to the size of the index set and the number of variables. This general result is applied to four specific coding scenarios:

Lee Metric:
- Fixed Alphabet ( $q$ ): For large code lengths $n$ and covering radii $e$ proportional to $n$ , the authors prove non-existence.
- Fixed $e$ : For fixed alphabet size $q$ and sufficiently large $n$ , if $e > (s+1) \cdot (s!)^2 / (s-1)$ (where $s = \lfloor q/2 \rfloor$ ), no perfect code exists. This provides asymptotic support for a 50-year-old conjecture that perfect $e$ -codes do not exist for $e > 1$ and $n > 2$ .
Sum-Rank Metric: Used in network coding, the paper derives a condition for non-existence when the number of blocks $t \to \infty$ . If the ratio of covering radius to blocks $e/t \to a$ and the dimension $d$ satisfies $d < (1+a)^{1+a}/a^a - 1$ (approximated as $d < e^a$ ), perfect codes do not exist.
Mixed Alphabet Codes: For direct products of Hamming schemes, the paper proves that if the covering radius $e$ scales as $an$ with $a > 1/k$ (where $k$ is the number of distinct alphabet groups), no perfect code exists.
NRT Metric (Ordered Hamming Space): Similar to the Lee metric case, non-existence is proven for large $n$ when $e$ exceeds a specific threshold dependent on the block length $r$ .

The authors also provide numerical tables illustrating these bounds, showing that the theoretical thresholds derived are sufficient conditions, though the actual critical points for non-existence often occur earlier.

Limitations and Counterexamples
The paper explicitly notes that the method is not universal. It fails for schemes where the dispersion function $\Pi(e)$ grows too slowly or where the number of variables is too large. Specifically:

Homogeneous Metric: The condition $\Pi(e) - 1 > e \cdot |S|^{r-1}$ does not hold for large $n$ , so the theorem cannot prove non-existence here.
$q$ -ary Johnson Scheme: The dispersion function growth is insufficient to satisfy the inequality for any admissible parameters, meaning the theorem does not apply to this scheme.

Significance
The paper's primary significance lies in revitalizing the study of perfect codes in non-metric settings by combining classical algebraic coding theory (Lloyd Theorem) with combinatorial bounds from computer science (Schwartz-Zippel). By introducing the concept of polynomial weakly metric association schemes, the authors create a unified framework that yields asymptotic non-existence results for four major metrics in coding theory. The work connects recent developments in multivariate $P$ -polynomial schemes and $m$ -distance regular graphs to classical coding problems, offering a new tool for analyzing the limits of perfect codes where traditional metric assumptions fail.