Perfect codes in weakly metric association schemes

Minjia Shi, Jing Wang, Patrick Solé · 2026

Read Perfect codes in weakly metric association schemes by Minjia Shi, Jing Wang, Patrick Solé (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12818.txt.

Introduction

Minjia Shi, Jing Wang, and Patrick Sole prove nonexistence results for perfect codes in several metrics. Perfect codes are rare gems of coding theory, packing spheres with no waste. The team combine the Lloyd theorem of Sole from 1989 with the Schwartz Zippel lemma from computer science. Their proofs rest on asymptotic enumeration of integer partitions.

The results cover the Lee metric, the NRT metric, and the mixed Hamming metric. The sum rank distance is covered as well. Ruling out perfect codes saves searches for objects that cannot exist. It also steers code design toward near perfect families that can exist. Cross field proofs like this show how algebra and combinatorics reinforce each other.

Catalog record

CREATORMinjia Shi, Jing Wang, Patrick Solé
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-12818

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Perfect codes in weakly metric association schemes Minjia Shi, Jing Wang, Patrick Solé Abstract . The Lloyd Theorem of (Solé, 1989) is combined with the Schwartz-Zippel Lemma of theoretical computer science to derive non-existence results for perfect codes in the Lee metric, NRT metric, mixed Hamming metric, and for the sum-rank distance. The proofs are based on asymptotic enumeration of integer partitions. The framework is the new concept of polynomial weakly metric association schemes. A connection between this notion and the recent theory of multivariate P-polynomial schemes of ( Bannai et al. 2025) and of m m -distance regular graphs ( Bernard et al 2025) is pointed out. Keywords: Perfect codes, Association schemes, Lloyd Theorem, Schwartz-Zippel Lemma, Integer partitions, multivariate P-polynomial schemes, m -distance regular graphs MSC (2020): 05 E30, 05 E10, 94B12, 94B60 1. Introduction If a finite metric space can be partitioned into balls of the same radius e, we say that the set of centers of these spheres form an e -perfect code, or a perfect code of covering radius e. For a general survey of this concept with applications to Coding Theory we refer to the recent book [ 13 ] . Classifying the parameters of the space when this is possible is then a fundamental problem. To that end, non existence results and necessary existence conditions are essential. The Lloyd theorem for the Hamming metric is a nontrivial necessary existence condition for perfect codes. It was first proved for prime powers alphabets by Lloyd in 1957 [ 18 ] . This theorem states that if perfect code of covering radius e and length n exists, then a certain Krawtchouk polynomial of degree e (usually called the Lloyd polynomial) has all its roots at integers in the range [1,n]. It has been the main tool behind the classification of perfect codes by the parameters [ 27 ] for prime powers alphabets, and for arbitrary alphabet size [ 3 ] . Its generalization by Delsarte in the context of metric association schemes appeared in his thesis in 1973 [ 12 ] (for background on association schemes we refer the non-expert reader to [ 8 , 4 , 12 ] ). However, not all association schemes are metric. In 1974 Bassalygo gave a mutivariate generalization of Lloyd theorem to codes for the Lee metric. In 1975, Heden gave a similar multivariate theorem for codes over mixed alphabets for the Hamming metric [ 16 ] . In 1989 the third author introduced the notion of weakly metric association schemes (shortly WMAS) to handle association schemes that are not metric, and derived a general Lloyd theorem in that context [ 24 ] . Indeed, both Bassalygo’s and Heden’s results follow as special cases of this theorem. However, this general theorem was not used to give any non-existence result in the last 36 years. This theorem shows that if an e-perfect code exists then a certain quantity (called the Lloyd polynomial below) vanishes \Pi(e)-1 times where \Pi() is the so-called dispersion function which counts the number of classes yielding elements at distance at most e. For a metric scheme, we have \Pi(e)=e+1. Intuitively speaking, this function measures how far away from a metric scheme the WMAS is. In the present paper, we use an upper bound due to Schwartz and Zippel on the number of zeros of multivariate polynomials in a finite domain to obtain a contradiction when that upper bound is <\Pi(e)-1. This requires the new notion of r -polynomial association schemes which is related to, but distinct from, the recent notion of multivariate P -polynomial schemes [ 5 ] . Our result is very general (Theorem 2), and has application to four important situations in Coding Theory: two are time honored (Lee codes, mixed alphabets), and two are of more current interest (NRT metric, sum rank metric). Firstly, we apply this technique to codes in the Lee metric with two different asymptotic regimes depending wether the alphabet size is fixed or not. It was conjectured 50 years ago that perfect e codes of length n do not exist for e>1 and n>2 [ 14 ] . This conjecture is still open today [ 15 ] . We will not solve it in this paper, but present asymptotic results in that direction. Another metric where our method applies is the sum-rank metric used in network coding [ 2 ] . Perfect codes in that metric were studied in [ 21 ] . We revisit mixed alphabet codes, reproving Heden’s result on our way, and give some non-existence results. Eventually, we consider codes for the (Niederreiter, Rosenbloom-Tsfasman) NRT metric, introduced by Niederreiter to handle discrepancy problems in quasi-random numbers generation [ 20 ] . Perfect codes were considered in [ 22 ] . In order to bound the dispersion from below, some classical results on the enumeration of partitions of integers are needed [ 1 , 31 ] . The material is arranged as follows. The next section collects the notions and notations needed in the rest of the paper. Specifically we have subsections on the Schwartz-Zippel Lemma, weakly metric association schemes, polynomial schemes, partition of integers. The following section recalls background material on the various schemes studied. Section 4 contains the main results. Section 5 collects some numerical tables, illustrating the bounds of Section 4. Section 5 concludes the article. An appendix describes the connection between polynomial WMAS and multivariate P-polynomial schemes of [ 5 ] . 2. Preliminaries 2.1. Schwartz-Zippel Lemma The Schwartz-Zippel lemma is a fundamental tool for polynomial identity testing. It provides an upper bound on the probability that a nonzero multivariate polynomial evaluates to zero at randomly chosen points from a finite set, ensuring that if the polynomial is nonzero, it is likely to be detected by random evaluation. To be self-contained, we give a proof, inspired by [ 29 ] , that avoids probabilistic language. Lemma 1 . Let P\in R[x_{1},x_{2},\ldots,x_{n}] be a non-zero polynomial of total degree e\geq 0 over an integral domain R . Let S be a finite subset of R. For any finite subset S of R , if Z(P) is the zero set of P , then |Z(P)\cap S^{n}|\leq e\cdot|S|^{n-1}. Proof. We proceed by induction on n . For n=1 , the result follows immediately since a univariate polynomial of degree e has at most e roots. For n>1 , express P as a polynomial in x_{1} : P(x_{1},\ldots,x_{n})=\sum_{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\ldots,x_{n}), where d\leq e is the degree of P in x_{1} , and P_{d} is not identically zero. Let A be the set of roots of P in S^{n} , and partition A into two sets: A_{1} , the roots where P_{d}(r_{2},\ldots,r_{n})=0 , and A_{2} , the roots where P_{d}(r_{2},\ldots,r_{n})\neq 0 . For A_{1} : Since \deg P_{d}\leq e-d , by the induction hypothesis, the number of (r_{2},\ldots,r_{n})\in S^{n-1} with P_{d}(r_{2},\ldots,r_{n})=0 is at most (e-d)\cdot|S|^{n-2} . For each such tuple, there are at most |S| choices for r_{1} , giving |A_{1}|\leq(e-d)\cdot|S|^{n-1}. For A_{2} : For fixed (r_{2},\ldots,r_{n}) with P_{d}(r_{2},\ldots,r_{n})\neq 0 , the polynomial P(x_{1},r_{2},\ldots,r_{n}) is a non-zero univariate polynomial of degree at most d , so it has at most d roots in S . Since there are at most |S|^{n-1} such

Read the complete text