CS Paper Radar

Quaternary Preparata codes are quasi-perfect covering codes in the Hamming metric

Tamal Maharaj

cs.IT ·submitted 2026-09-27 07:03 UTC · v1
theory

Abstract

The quaternary Preparata codes of Hammons, Kumar, Calderbank, Sloane and Solé are $\mathbb{Z}_4$-linear codes of length $2^m$ with $4^{2^m-m-1}$ codewords. They are usually studied through their binary Gray images, that is, in the Lee metric. We consider them instead as codes over a 4-letter alphabet with the Hamming metric. We show that for odd $m$ they have covering radius 2 and minimum distance 4, so they are quasi-perfect. For even $m$ the same construction has covering radius 3. The proof is a short computation with Teichmüller representatives in the Galois ring $\mathrm{GR}(4,m)$, and it also gives the coset weight distribution. The covering density of these codes tends to $9/8$. The best previously known infinite families of quaternary codes with covering radius 2 have covering density about 1.5. Consequently $K_4(n,2)\le 4^{n-m-1}$ for all $n\ge 2^m$ and odd $m$, which improves the best available bounds for a range of lengths above each $2^m$. For $m=3$ the code is the octacode, and it gives $K_4(8,2)\le 256$; the previous bound was 352, from 2005, and the best lower bound is 251. We also give a quaternary code showing $K_4(6,2)\le 48$, where the previous bound was 52, together with consequences for larger alphabets.

Closest papers

Nearest neighbours by meaning across the whole index.

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.78
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

On Nearly-Perfect Covering Codes Beyond Radius One

cs.IT math.CO ·2026-08-12 ·Gabriel Sac Himelfarb, Moshe Schwartz
theory similarity 0.72
Abstract · 26 pages

We study (binary) nearly-perfect covering codes, which are codes that attain the Van Wee bound with equality. They act as the covering counterparts to nearly-perfect error-correcting codes, which attain the Johnson bound with equality. These codes have been completely classified for covering radius $R=1$. We prove that no code with $R\geq 2$ can attain the original Van Wee bound with equality, since it omits the dependence on the minimum distance of the code. We refine the bound to account for the minimum distance and show some nearly-perfect covering codes. By proving some structural properties of such codes, we prove all nearly-perfect covering codes with $R=2,3$ must be equivalent to the codes we showed. We also prove that for any $R\geq 3$, there are at most a finite number of nearly-perfect covering codes.

0.38

Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes

cs.IT math.CO ·2026-08-31 ·Maosheng Xiong, Chi Hoi Yip, Ferdinando Zullo
theoryhighly cited similarity 0.71
Abstract

Fix integers $e\ge2$ and $r\ge1$. In this paper we study the $r$-th generalized covering radius $ρ_r\left(BCH(e,m)\right)$ of the binary primitive $e$-error-correcting BCH code $BCH(e,m)$. By using an algebraic-geometric reformulation of the covering problem together with an explicit Lang-Weil estimate, we prove that \[ρ_r\bigl(\BCH(e,m)\bigr)\le(r+1)e-1\] for all sufficiently large $m$. For $e\ge7$, this improves a recent result of Belinsky--Zabokritskiy. Our proof gives a substantially simpler geometric approach to this upper bound. In particular it implies that \[ρ_2\bigl(BCH(e,m)\bigr)=3e-1\] for all sufficiently large $m$. Previously it was only known that \[ρ_2\bigl(\BCH(e,m)\bigr) \in \left\{3e-1,3e\right\}\] for all sufficiently large $m$.

0.44

Auxiliary Codes and the Generalized Packing-Covering Conjecture

cs.IT ·2026-09-16 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
theory similarity 0.71
Abstract · 10 pages, 2 tables. Revised exposition and references; clarified the auxiliary-code method and improved presentation

The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established range of redundancies at most seven. We also prove the bound on generalized Hamming weights $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$. Both results use an auxiliary-code criterion that converts a covering property in the syndrome space into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.

0.37

The generalized covering radii of Melas codes

cs.IT ·2026-08-30 ·Shuxing Li, Maosheng Xiong
theory similarity 0.70
Abstract · We have updated the references to reflect recent literature on this topic. In addition, we have clarified the relationship between our work …

The generalized covering radii have recently emerged as fundamental parameters of linear codes with applications to database linear querying. In this paper, we study the generalized covering radii $ρ_t(M(m,q))$ of Melas codes $M(m,q)$ over any finite field $\mathbb{F}_q$. We determine $ρ_2(M(m,q))$ for all $q$, and for a general $t \ge 3$, we prove that $ρ_t(M(m,q)) \in \left\{2t,2t+1\right\}$ for $q \in \{2,3\}$ and $ρ_t(M(m,q))=2t$ for $q \ge 4$ whenever $m$ is sufficiently large. These results extend recent work on the covering radius of Melas codes.

0.39

Extremal diagonal-coherent binary codes: shortened Hamming cores, deep holes, and the 64 I-Ching hexagrams

cs.DM math.COcs.IT ·2026-10-24 ·Jon-Lark Kim
similarity 0.70
Abstract · 24 pages

Each of the 64 hexagrams of the I-Ching, or Book of Changes, is a stack of six Yin-Yang lines and is therefore a binary vector of length 6; the eight hexagrams formed by repeating a single trigram span a doubled-trigram subspace $Δ$. We ask which binary $[6,3,3]$ codes are compatible with this trigram structure. We show that a $[6,3,3]$ code meets $Δ$ in at most four codewords, that the four are then forced to be the doubled trigrams Earth, Fire, Wind and Lake, and that exactly two codes attain this bound: the shortened Hamming code $\mathcal C_A$ and its dual. Since $\mathcal C_A$ has covering radius 2, its eight codewords, their radius-one balls, and its eight deep holes together reconstruct all 64 hexagrams. In general, we call a binary code of length $2m$ with $d \ge 3$ diagonal-coherent if it contains the half of the diagonal subspace $\{(u,u)\}$ coming from even-weight vectors $u$ -- the largest part of that subspace a single-error-correcting code can contain -- and extremal if its dimension is as large as possible. For $m\ge2$ and $r=\lceil\log_2(2m+1)\rceil$, we determine the number $N(m)$ of extremal diagonal-coherent codes with parameters $[\,2m,\ 2m-r,\ \ge3\,]$, show that diagonal coherence entails no loss of redundancy, and determine their minimum distances. We also put these codes in a normal form, determine their hulls, and show that each has covering radius $2$ with exactly $2^r-1-2m$ deep-hole cosets. Finally we propose three open problems.

0.25

Nonlinear fixed-distance codes via real lifts of moment configurations

cs.IT cs.DMmath.CO ·2026-10-14 ·Sergey Yekhanin
theory similarity 0.70
Abstract

Let $A_q(n,d)$ denote the largest size of a code of length $n$ and minimum Hamming distance $d$ over an alphabet of $q$ symbols. For fixed $q\ge2$ and $d\ge4$ we construct codes with redundancy $n-\log_q A_q(n,d)\le(d-3)\log_q n+O(\sqrt{\log n})$ for all large $n$. No algebraic structure is imposed on the alphabet, and the codes are not linear. For $d=4$ and $d=5$ the coefficient of $\log_q n$ matches the Hamming bound, so the redundancy is determined up to lower-order terms. At distance four the codes are provably better than every linear code: by the polynomial-method bound for cap sets, $\mathbb{F}_q$-linear codes with $q>2$ require a strictly larger coefficient in front of $\log_q n$. The construction imposes moment checksums over an auxiliary finite field, as BCH codes do, but one fewer than the distance would normally require. The affine-line theorem from prior work describes the dependencies left by these checks. We exclude them by placing the code positions inside a specially structured subset of the field, built from Behrend's sphere construction with the help of algebraic number theory.

0.44

On the Generalized Packing and Covering Radii of Codes

cs.IT math.CO ·2026-09-13 ·Wenjun Yu, Moshe Schwartz
theory similarity 0.70
Abstract

The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.

0.37