CS Paper Radar

A proof of Ward's conjecture on Griesmer codes

Haihua Deng, Weiye Zhang

cs.IT math.CO ·submitted 2026-10-21 06:26 UTC · v1
theoryhot direction

Abstract

Let $C$ be an $[n,k,d]_q$ Griesmer code, where $q=p^f$ with $p$ prime, and write $e=ν_p(d)$. Ward conjectured that $C$ is $p^{\max\{0,e-f+1\}}$-divisible. In this paper, we prove this conjecture.

Comment
10 pages, comments are welcome

Closest papers

Nearest neighbours by meaning across the whole index.

A Hyperplane Bound and Ward's Divisibility Conjecture

cs.IT ·2026-10-19 ·Guanghui Zhang
theoryhot direction similarity 0.72
Abstract · 31 pages

Let $q=p^f$, where $p$ is prime. We prove that every $q$-ary linear code meeting the Griesmer bound, with positive dimension and minimum distance $d\ge1$, is $p^{\max\{0,ν_p(d)-f+1\}}$-divisible, as asserted in Ward's conjecture. Arbitrary projective column multiplicities are allowed. The geometric ingredient is a bound independent of dimension: a nonzero scalar-invariant function $F:\mathbb{F}_q^k\to\mathbb{F}_p$, with $F(0)=0$ and prime-field algebraic degree at most $(f+s)(p-1)$, vanishes identically on at most $p^s(q-1)$ linear hyperplanes when $0\le s<f$. A truncated digit-sum inequality forces selected coefficient polynomials to be homogeneous of ordinary degree less than $q$. Weighted moments on a projective line then bound their linear factors, while a second-moment argument handles the complementary support configuration. An elementary finite-difference calculation supplies the degree bound for divided weight residues. Endpoint shortenings prove the basic divisibility layers; endpoint lifting, a surjective linear functional, and residual-code induction extend the argument to every valuation. We include the proofs of the classical ingredients, identify their sources, and distinguish the present argument from an earlier reported unpublished proof.

0.52

A density theorem for non-standard irreducible cyclic codes

cs.IT math.CO ·2026-10-31 ·Tao Feng, Henk D. L. Hollmann, Weicong Li, Qing Xiang
theory similarity 0.63
Abstract · 13 pages

We prove a fixed-characteristic density form of the Berger-Charpin conjecture for non-degenerate irreducible cyclic codes: for each prime $p$, the lengths admitting such a non-standard code over some finite field of characteristic $p$ have natural density zero. Thus, for almost every length coprime to $p$, every such code over every finite field of characteristic $p$ has only the permutation automorphisms generated by the cyclic shift and the Frobenius map. The proof uses the Feng--Hollmann--Li--Xiang classification for non-standard irreducible cyclic codes, a normal form for the deriving constructions in that paper, and a theorem by Wiertelak on multiplicative orders, in the form recalled by Moree.

0.21

A Uniform Upper Bound on the Length of MDS Codes from Genus-Two Curves

cs.IT math.AGmath.NT ·2026-10-29 ·Haojie Chen
theory similarity 0.62
Abstract

We study the maximal length of MDS algebraic geometry codes from genus-two curves over finite fields. Let $C_\mathcal{ L}(D,G)$ be such a code over $\mathbb F_q$, with length $n$ and dimension $k$. Assume that $3\leq k\leq n-3$. We prove that $n<(2q+10\sqrt q+16)/3$. This bound holds for every prime power $q$ and for both parities of $k$. It gives a uniform upper bound of $2q/3+O(\sqrt q)$ for the maximal length. The explicit bound is strictly smaller than $q+1$ when $q\geq125$.

0.17

Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound

cs.IT ·2026-10-25 ·Yuhan Li
theoryhot direction similarity 0.61
Abstract · 21 pages

We study the minimum extension degree required for a Reed--Solomon code to admit exact $\mathbb{F}_q$-linear repair at the cut-set bound from every prescribed set of $d$ helpers. Let $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. For every prime power $q$ and all $3\le k<d<n\le2d-2$, we prove that the minimum degree over $\mathbb{F}_q$ is exactly $sQ_s(n)$. When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with $n>2d-2$, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an $\mathbb{F}_p$-linear repair scheme on the same code, where $p$ is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.

0.51

On the maximum length of cyclic MDS codes

cs.IT ·2026-10-21 ·Gaojun Luo, Xiwang Cao, Shitao Li, Yang Li
theoryhot direction similarity 0.61
Abstract

We study the maximum length of nontrivial simple-root cyclic maximum distance separable (MDS) codes over ${\mathbb F}_q$. We prove $n\le q+1$ if $\gcd(n,q^2-1)>2$, or if the dimension is even and $\gcd(n,q^2-1)>1$. The bound also holds for all lengths whose prime factors lie in $\{2,3,5,7\}$. We obtain further cases involving primes $\ell\ge11$ with $(\ell-1)/2$ prime, under conditions on the exponents and the characteristic. The proofs combine Fourier supports, locality bounds and field descent with arithmetic restrictions on multiplicative orders and prime-adic valuations.

0.22

On the MDS conjecture in even characteristic

cs.IT math.CO ·2026-10-20 ·Bocong Chen, Jing Huang
theoryhot direction similarity 0.61
Abstract · 34 pages

We prove that every nontrivial linear $[n,k]$ maximum distance separable (MDS) code over a finite field $\F_q$ of characteristic two satisfies $n\le q+1$, except in dimensions $k=3$ and $k=q-1$, where $n\le q+2$. This resolves the linear MDS conjecture in even characteristic.

0.24

The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound

cs.IT ·2026-10-27 ·Weijun Fang, Jing Qiu, Shu-Tao Xia, Fang-Wei Fu
surveytheory similarity 0.61
Abstract · 33 pages

In this paper, we study the minimum subpacketization of $(n,k)$ Reed-Solomon (RS) codes over $\mathbb{F}_{q^\ell}$ admitting cut-set-optimal exact $\mathbb{F}_q$-linear repair of every coordinate from any $d$ helpers. For $3\le k<d\le n-1$, write $s=d+1-k$ and denote this minimum by $\ell_{min}(n,k,d;q)$. Using divisibility and relative-degree constraints on cross-ratio fields of evaluation sets, we establish $\ell_{min}(n,k,d;q)\ge sG_s(d+1)$, where $G_s(m)$ is the minimum product of $m$ pairwise coprime integers, each at least $s$. Let $Δ_s(n,d)$ be the minimum of $lcm(a_1,\ldots,a_n)$ over positive integers $a_1,\ldots,a_n$ satisfying $lcm(a_j:j\in J\cup\{i\})\ge s~lcm(a_j:j\in J)$ for every $d$-subset $J\subseteq[n]$ and every $i\in[n]\setminus J$. We construct RS codes with subpacketization $sΔ_s(n,d)$ and further prove that $\ell_{min}(n,k,d;q)=sΔ_s(n,d)=sG_s(n)$ whenever $d(d+2)\geq 4(n+1)$, for every prime power $q$. In particular, this determines the minimum subpacketization in the full-helper case $d=n-1$, resolving the corresponding exact linear-repair case of Open Problem 20 posed by Ramkumar et al. in their survey on codes for distributed storage. We further give a finite formula for $G_s(n)$ and determine the exact threshold for its closed-form expression in terms of the first $n$ primes. For fixed $k$ and $d$, we prove $\log\ell_{min}(n,k,d;q)= Θ_{k,d}(\log n\log\log n)$ as $n\to\infty$, using divisor-function estimates and cover-free families. An affine-plane construction shows that $Δ_s(n,d)<G_s(n)$ for some parameters, so $sG_s(n)$ is not a universal formula. We conjecture that $\ell_{min}(n,k,d;q)=sΔ_s(n,d)$ for every prime power $q$ and all $3\le k<d\le n-1$.

0.43

New constructions of optimal Ferrers diagram rank-metric codes for quasi-block monotone Ferrers diagrams

cs.IT ·2026-11-14 ·Yong Jin, Yuhao Ning, Dengming Xu, Chengming Duan
theory similarity 0.60
Abstract

Constant dimension subspace codes (CDCs) have become an important object in coding theory due to their applications in random network coding. The paper is devoted to constructing optimal Ferrers diagram rank-metric codes for block Ferrers diagrams, which play a crucial role in the multilevel construction of CDCs. Let \(\mathbb{F}_q\) be the finite field with \(q\) elements of characteristic \(p\), \(P\) be a power of \(p\), and \(e\) be a positive integer. Let \(L=\mathbb F_{q^{eP}}\) and \(σ\) be the Frobenius \(\mathbb F_q\)-automorphism of \(L\), set \(N=σ^e-\mathrm{id}\). Based on the multiplicative property of the kernel filtration of the nilpotent map \(N\), we construct optimal Ferrers diagram rank-metric codes for block monotone diagrams. Specifically, considering \(n \times l\) Ferrers diagrams, we prove that optimal codes always exist for block monotone diagrams when \(n = eP\). Furthermore, by employing puncturing on columns, we prove that optimal codes also always exist for block strictly monotone diagrams, removing the restriction \(n = eP\). Consequently, optimal codes always exist for block upper triangular diagrams, specifically for maximum sum-rank distance (MSRD)-constructible block diagram pairs, which generalizes the corresponding results in \cite{neri2024,calderini2026}, in which the rank distance or the characteristic is restricted. Furthermore, by employing both puncturing and shortening on columns, we prove that optimal codes always exist for quasi-block strictly monotone diagrams, thereby generalizing the corresponding results in \cite{pratihar2023, zhang2019}. The optimal codes constructed in this paper will potentially be beneficial to the further construction of CDCs.

0.04