CS Paper Radar

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

Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu

cs.IT math.CO ·submitted 2026-10-22 02:26 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT ·2026-09-27 ·Tamal Maharaj
theory similarity 0.78
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.

0.07

Six Families of Binary Codes Arising from Ding's Conjectures

cs.IT ·2026-09-29 ·Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng +1 more
theory similarity 0.72
Abstract

Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

0.04

Nonlinear fixed-distance codes via real lifts of moment configurations

cs.IT cs.DMmath.CO ·2026-10-14 ·Sergey Yekhanin
theory similarity 0.71
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.42

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.70
Abstract · 52 pages

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}n^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2)^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge2$.

0.12

New lower bounds for constant-weight codes via seeded bit-swap tabu search

cs.IT math.CO ·2026-08-14 ·William Echols
similarity 0.70
Abstract

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $τ_{32}$, $τ_{33}$, $τ_{34}$, and $τ_{37}$.

0.40

Auxiliary Codes and the Generalized Packing-Covering Conjecture

cs.IT ·2026-09-16 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
theory similarity 0.69
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

A proof of the generalized packing-covering conjecture

cs.IT math.CO ·2026-09-28 ·Gianira N. Alfarano, Giuseppe Marino, Alessandro Neri, Rocco Trombetti
similarity 0.68
Abstract

The generalized packing--covering conjecture of Elimelech, Firer and Schwartz asserts that, for every linear code $\mathcal{C}$ and every admissible order $t$, the $t$-th generalized Hamming weight $d_t(\mathcal{C})$ and the $t$-th generalized covering radius $R_t(\mathcal{C})$ satisfy $d_t(\mathcal{C})\le 2R_t(\mathcal{C})+2$. We give a computer-assisted proof of the conjecture for every linear code over every finite field and every admissible order. Combining a parity-check reformulation of the conjecture, bounds on the length of putative counterexamples, and successive puncturing arguments, we settle all orders $t\ge 32$ and reduce the remaining orders to finitely many parameter tuples, which we exclude by an exact computer verification.

0.03

Solutions to Three Conjectures and an Open Problem on Binary BCH Codes

cs.IT ·2026-09-01 ·Xiaoqiang Wang, Jiawei He, Boru Yi, Dabin Zheng
theory similarity 0.67
Abstract

BCH codes are among the most important classes of cyclic codes and have played a central role in coding theory and its applications. One of the fundamental problems in the study of BCH codes is to determine their exact minimum distances, which directly govern their error-correcting capability. Although the BCH bound provides a general lower bound, determining the exact minimum distance is often difficult, and many parameter families remain unresolved. In this paper, we investigate three conjectures and an open problem on binary BCH codes proposed by Chen, Xie, and Ding in \cite{Chen59}. We settle these conjectures on the exact minimum distances of three families of binary BCH codes by constructing codewords attaining the BCH bound. Beyond these conjectures, we further study the more difficult family codes and determine its minimum distance for some cases. We further study Open Problem 8.4: affirmative answers are obtained for the first two length families, while for the third family a sufficient condition is established and a counterexample shows that the unrestricted assertion does not hold in general.

0.20