CS Paper Radar

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

Zhichao Tang, Xiang Fan

cs.IT cs.DMmath.CO ·submitted 2026-11-18 15:05 UTC · v1
theory

Abstract

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.

Comment
10 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

Optimal self-orthogonal binary linear codes

cs.DM math.COcs.IT ·2026-10-29 ·Sascha Kurz
theory similarity 0.65
Abstract · 39 pages; comments more than welcome

We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.

0.24

Some Results on the Weight Spectrum of Binary Reed-Muller Codes $RM(m-7,m)$

cs.IT ·2026-10-21 ·Zibo Wei, Bo Zhou, Xiao Zhang, Hao Chen
theory similarity 0.65
Abstract · 36 pages

We study the set of weights occurring in the high-order binary Reed-Muller codes $RM(m-7,m)$. For every $m\geq 14$, we prove that the weight spectrum contains all even weights in $[336,2^m-336]$, together with an explicit finite set of low weights and their complements. The proof first establishes the corresponding base-code inclusion in $RM(7,14)$. This base step uses four-block concatenation, explicit degree-six monomial witnesses, and known spectrum inputs for $RM(5,10)$ and $RM(6,12)$. The base inclusion is then lifted to all $m\geq 14$ by a concatenation-based induction. We also analyze the remaining base-code target weights $322,326,330,334$ in several restricted families, including four-block branches, affine-flat and structured inner corrections in a fixed Carlet-type Maiorana-McFarland outer shell, and sparse sums of degree-7 coordinate monomials. The residual analysis delineates several construction routes that cannot yield the four unresolved base-code weights, thereby sharpening the remaining $c=7$ spectrum problem.

0.47

An integer determinant approach to the length of Type II codes and the weights of shadows

cs.IT ·2026-10-22 ·Jae-Hyun Baek, Jon-Lark Kim
theory similarity 0.65
Abstract · 10 pages

It is well known that the length $n$ of a binary Type II code is divisible by $8$. The classical proof relies on Gleason's theorem on weight enumerators. Motivated by a question of Vera Pless, we give elementary proofs of this fact that avoid invariant theory. Our main tool is a congruence modulo $8$ for the determinant of the integer Gram matrix $AA^{\mathsf T}$ of a binary orthogonal matrix $A$, obtained directly from the Leibniz expansion. It gives a short proof of a theorem of Janusz: the number of rows of weight congruent to $3 \pmod 4$ in a binary orthogonal matrix is divisible by $4$. From this single statement we derive both the length restriction for Type II codes and the theorem of Conway and Sloane that every vector in the shadow of a binary self-dual code of length $n$ has weight congruent to $n/2 \pmod 4$. We also give two short character-theoretic proofs of the length restriction and explain how all of these arguments detect the Arf invariant of a quadratic form.

0.30

New linear codes over GF(7), GF(8) and GF(9) from quasi-cyclic codes and Construction X

cs.IT ·2026-11-10 ·Sebastian Cochinescu
theory similarity 0.65
Abstract · 12 pages, 1 table. Ancillary files: verification program and generator matrices. v2: three more codes and two more derived codes added. Code…

We present linear codes with parameters [88,8,64]_7, [90,8,65]_7, [98,7,75]_8, [97,8,72]_8, [44,7,31]_9, [97,8,71]_7, [85,6,67]_8 and [78,8,56]_7. Each has a minimum distance one larger than the lower bound listed in Grassl's tables of best known linear codes; codes with parameters [89,8,64]_7, [96,8,71]_8, [95,8,70]_8, [94,8,69]_8, [77,8,55]_7 and [86,6,68]_8 follow. Seven of the eight codes are obtained from a quasi-cyclic code and a vector that is constant on each block, by Construction X with a repetition code. The remaining one, the [90,8,65]_7 code, is obtained from the first by appending two coordinates. The parameters and all weight counts were obtained by exhaustive enumeration, and a short program that repeats these computations is included.

0.12

Revisiting the Weight Spectrum of the Affine Grassmann Code $C^{\mathbb{A}}(2,m)$

cs.IT ·2026-09-09 ·Rohit Yadav
similarity 0.64
Abstract · 9 Pages

Affine Grassmann codes, introduced by Beelen, Ghorpade and Høholdt, are linear codes over $\mathbb{F}_q$ obtained by evaluating linear combinations of minors of a generic matrix. The weight spectrum of the affine Grassmann code $C^{\mathbb{A}}(2,m)$ was determined by Piñero and Singh via a case analysis on the rank of an associated alternating matrix. We give an independent and more streamlined derivation, valid for all $m\ge4$ and every prime power $q$, in which each codeword is written in a compact matrix form and its Hamming weight is expressed through a single closed formula involving two explicit affine subspaces and their intersection.

0.23

A Mirror Vanishing Band for Weight Distributions of Binary Linear Codes

cs.IT ·2026-09-17 ·Xianmang He
similarity 0.64
Abstract

Chen and Xie recently proved, using the Ashikhmin--Barg lemma on minimal vectors, that every binary linear $[n,k,d]$ code with $k=n-2d+2+v$ ($v\ge 0$) has no codewords of weight in the interval $[2d-v,\,2d-1]$. Their argument uses two of the five basic properties of minimal vectors established by Ashikhmin and Barg (1998). In this note we utilize the third property, the disjoint-support decomposition of non-minimal codewords in binary codes, to generate a \emph{mirror} vanishing band on the other side of $2d$: if $A_{d+1}=\cdots=A_{d+t}=0$ for some $t\ge 1$ and $k\ge n-2d+1$, then $A_w=0$ for all $w\in[2d+1,\,2d+t]$. Combining the two bands, the number of nonzero weights of such a code is at most $n-d-v-2t+1$, improving the Chen--Xie bound $n-d+1-v$ by $2t$.

0.18

Four New Single-Error-Correcting Binary Codes

cs.IT math.CO ·2026-10-16 ·Moshe Milshtein
similarity 0.64
Abstract

We construct a $(16, 3072, 3)$-code, a $(17,6144,3)$-code, an $(18,12288,3)$-code and a $(19,24576,3)$-code. Consequently, we get four new lower bounds: $A(16,3) \geq 3072$, $A(17,3) \geq 6144$, $A(18,3) \geq 12288$ and $A(19,3) \geq~24576$. Each of the codes consists of a union of cosets of a linear code. The constructions are the result of a computer search executing a tabu search algorithm.

0.17