CS Paper Radar

Six Families of Binary Codes Arising from Ding's Conjectures

Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng, Jiawei He

cs.IT ·submitted 2026-09-29 09:19 UTC · v1
theory

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)$.

Closest papers

Nearest neighbours by meaning across the whole index.

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.75
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.72
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

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.72
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

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

A Characterization of $q$-Ary $2$-Designs and a $3$-Design Obstruction for Doubly-Extended Reed-Solomon Codes

cs.IT ·2026-11-08 ·Guanghui Zhang, Zhengbang Zha
theory similarity 0.70
Abstract · 18 pages

Let $\mathcal{C}_k$ be the doubly extended Reed--Solomon code with parameters $[q+1,k,q-k+2]_q$, where $q\ge3$ is a prime power and $2\le k\le q$. We prove a conjecture of Wu and Zhou by showing that the minimum-weight codewords of $\mathcal{C}_k$ do not form a $q$-ary $3$-design when $2\le k\le q-1$. Using shortening, we extend this obstruction to every nonempty weight class with $3\le w<q+1$. We also establish that each individual nonempty positive-weight class of $\mathcal{C}_k$ forms a $q$-ary $2$-design if and only if $\gcd(k-1,q-1)=1$. Consequently, every nonempty positive-weight class below full support has exact $q$-ary design strength $2$ when this coprimality condition holds, and $1$ otherwise.The three-design obstruction follows by applying a classical subset-product character identity to a marginal covering count for three prescribed nonzero symbols. The comparison between weights rests on a covering-count formulation of the classical MDS coset-weight relations. For every linear $[n,k,d]_q$ MDS code with $2\le k\le n-1$, this formulation shows that the $q$-ary $2$-design property at any one nonempty positive weight is equivalent to the same property at every nonempty positive weight.More generally, for $2\le t\le\min\{k,d\}$, we prove that the $q$-ary $t$-design property at any $t-1$ distinct nonempty positive weights forces it at all nonempty positive weights.

0.07

Infinite families of 3-designs from linear and nonlinear codes

cs.IT ·2026-09-14 ·Shiyan Xiong, Xiaoqiang Wang, Dabin Zheng, Qinqin Ji
similarity 0.69
Abstract

The connection between coding theory and combinatorial $t$-designs is an important research topic at the intersection of coding theory and combinatorics. Let $q=p^m$, where $p$ is an odd prime and $m\geq 2$. In this paper, we investigate a class of linear codes $\mathcal{C}$ over $\mathbb{F}_{q^2}$ and their connection with combinatorial $3$-designs. By analyzing the relevant structural properties of $\mathcal{C}$ and $\mathcal{C}^{\perp}$, we show that the supports of the codewords of every nonzero weight in $\mathcal{C}$ and {the supports of the codewords of weight $4$ in $\mathcal{C}^{\perp}$} form $3$-designs. We further investigate a class of nonlinear codes $\mathcal{C}_2$ associated with $\mathcal{C}$, and prove that the supports of the codewords of every nonzero Hamming weight in $\mathcal{C}_2$ also form $3$-designs. These results identify further classes of linear and nonlinear codes whose codewords support combinatorial $3$-designs. In particular, the nonlinear case provides additional examples of codes supporting $3$-designs, a topic for which relatively few results are currently available. As applications, we construct from $\mathcal{C}^{\perp}$ an entanglement-assisted quantum error-correcting code with parameters $[[q+1,q-3,4;4]]_q$. We also prove that $\mathcal{C}$ is an all-symbol locally repairable code with locality $3$. Furthermore, we show that the code $\mathcal{C}$ {meets the Singleton-type bound for locally repairable codes} and hence is optimal in some cases.

0.22

On the structure of polynomial ideal codes and additive Reed--Solomon codes

cs.IT ·2026-10-15 ·Umberto Martínez-Peñas, Rubén Rodríguez-Ballesteros
similarity 0.67
Abstract

We study structural properties of polynomial ideal (PI) codes and additive Reed--Solomon (aRS) codes in the folded Hamming metric (equivalently, the Hamming metric over a larger alphabet). We first determine the maximum possible length of PI codes, prove that the dual of every PI code is a generalized PI code, and deduce that PI codes are dually QMDS together with an explicit formula for their weight distribution. We then show that PI codes defined by irreducible polynomials correspond to aRS codes with pairwise nonconjugate evaluation points. For these aRS codes, the previous results on PI codes apply (duality, QMDS property and weight distribution). We show that, asymptotically, aRS codes with nonconjugate evaluation points achieve the same length as PI codes. We also compute the permutation group of such aRS codes. We also extend the family of PI codes to consider arbitrary polynomial modules (not necessarily pairwise coprime), and study when these and general aRS codes satisfy the QMDS and dually QMDS properties.

0.15

There is no binary linear $[65,9,29]$ code

cs.IT cs.DMmath.CO ·2026-11-18 ·Zhichao Tang, Xiang Fan
theory similarity 0.67
Abstract · 10 pages

We prove that no binary linear $[65,9,\geqslant29]$ code exists, equivalently, that no even binary linear $[66,9,\geqslant30]$ code exists. Together with known constructions, this determines $d_2(65,9)=28$, $n_2(9,29)=66$, and $n_2(9,30)=67$. A residual-code bound and a known construction also give $d_2(122,10)=56$. To prove nonexistence, we associate with a hypothetical even code a quadratic function derived from half the codeword weight modulo $2$. Its polar form determines the fourth derivative of a Boolean function of degree at most four. Character sums, weight moments, and the exclusion of weight-$42$ codewords give upper bounds on the support of this function in seven cases. Restrictions to nondegenerate affine subspaces exclude six cases. In the remaining case, equality would force four distinct coordinate functionals to be identically $1$ on an affine seven-space, although at most two can have this property. The argument uses published minimum-length results for binary linear codes of dimensions eight and nine.

0.25