CS Paper Radar

The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths

Weiguo Gao, Zhi Shan

cs.IT ·submitted 2026-09-16 07:12 UTC · v2
theory

Abstract

We prove the \(3/4\) conjecture for \(q\)-ary fix-free codes with at most three distinct codeword lengths, for every integer \(q\geq2\). Every prescribed length distribution with Kraft sum at most \(3/4\) is realized by a deterministic construction. We introduce a matrix approach based on an exact identity for the overlap between forbidden prefix extensions and suffix residuals. Natural numerical order fixes the shortest layer, and the remaining selection problem is expressed through row and column counts. A fixed-cardinality interpolation theorem supplies feasible sets of every intermediate cardinality between nested endpoints, provided their differences satisfy one-sided uniqueness and either acyclicity or integral slack. Reverse-order selection handles the uniform cases directly; in the remaining cases, layer completion and aligned groups provide endpoints for interpolation. Together, these methods extend the binary three-length result to arbitrary finite alphabets and give a deterministic procedure for constructing the code.

Comment
33 pages, 4 figures, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

The Support-Distribution Conditions for MSRD Codes Reduce to a Single Inequality

cs.IT ·2026-10-29 ·Xiang Fan
theory similarity 0.69
Abstract · 18 pages

Byrne, Gluesing-Luerssen, and Ravagnani determined the number of codewords with a prescribed nonzero support in a linear maximum sum-rank distance code whose blocks have a common number of columns. Their formula depends only on the code parameters and the support dimensions. Evaluating it for arbitrary parameters gives a family of necessary nonnegativity conditions for existence. We prove their conjecture that this family is equivalent to the condition at the vector of total dimension $d+1$ obtained by filling the longest blocks first, where $d$ is the distance parameter. The resulting explicit criterion applies over every finite field $\mathbb F_q$, for all row numbers $n_i\leqslant m$ and $1\leqslant d<N$, where $m$ is the common number of columns and $N$ is the total number of rows. It also covers the boundary cases in which this vector fills each of its nonzero blocks completely, not explicitly included in the conjecture's displayed parameter range. The proof uses a generating function and an exchange identity to reduce the problem to vectors obtained by filling the longest blocks first. We then estimate alternating sums of elementary symmetric polynomials, with a separate argument for $q=2$. The dual conditions admit the same reduction. For codes that exist, the joint condition follows from sphere-packing bounds for the code and its dual. An infinite family of parameters satisfies the joint condition but admits no such linear code.

0.22

Subcodes with Prescribed Hull Dimensions in Linear Codes:Enumeration, Containment, and Asymptotic Distributions

cs.IT ·2026-10-26 ·Linhan Xiong, Hongwei Liu, Liren Lin
similarity 0.67
Abstract · 39 pages

Mass formulas for prescribed hull dimensions have mainly been studied for linear codes viewed as subspaces of the whole space. We study internal enumeration for an arbitrary fixed parent code. Let $C$ be an $[n,k]_q$ linear code with an $\ell$-dimensional hull, and let $s$ be the subcode dimension. We determine the number of subcodes with prescribed dimension, hull dimension, and type over finite fields of both even and odd characteristic. We decompose the parent code into an LCD complement and its hull, and use projection to reduce enumeration to the corresponding problem inside the LCD complement. This yields explicit formulas refined by complete type and shows that the counts depend only on the relevant parameters, not on the particular parent code or its length. The known whole-space mass formulas and the enumeration of LCD subcodes of LCD codes arise as special cases. Motivated by code extension, we also study the dual containment problem: for a fixed code, we enumerate larger codes containing it with prescribed hull dimension and type. By duality, this problem is converted into the subcode enumeration problem already solved above, leading to corresponding conditional mass formulas. Finally, we investigate the asymptotic distributions arising from the exact enumeration formulas. When both the subcode dimension $s$ and $k-\ell-s$ tend to infinity, the hull distribution is governed by the LCD complement, and the limiting proportions are explicit constants determined by the field, the prescribed hull dimension, and the relevant type. When $s$ approaches or exceeds the dimension $k-\ell$ of the LCD complement, we determine the asymptotic proportion of subcodes attaining the minimum possible hull dimension and establish the associated concentration behavior. Analogous asymptotic results are obtained for the containment problem.

0.23

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

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.66
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

On the Length of Maximum Sum-Rank Distance Codes

cs.IT math.CO ·2026-10-16 ·Valentina Astore, Ferdinando Zullo
similarity 0.65
Abstract

The classical theory of arcs in finite projective spaces provides a powerful geometric framework for studying maximum distance separable (MDS) codes and their possible lengths. In this paper, we investigate how this perspective extends to maximum sum-rank distance (MSRD) codes, whose geometric description involves systems of linear sets rather than individual projective points. Our main goal is to understand how the block structure of an MSRD code constrains its length. In dimension three, we determine the possible intersection patterns of lines with the associated linear sets and obtain explicit formulas for their characters and the weight distribution of the corresponding codes. These results lead to new length bounds and show that the block structure comes at a cost: the presence of a block of rank at least two reduces the maximum possible total length by at least $q-1$, and sufficiently long MSRD codes must be classical, that is, MDS codes over $\mathbb F_{q^m}$. We also prove that three-dimensional one-weight MSRD codes do not exist. In arbitrary dimension, we interpret shortening geometrically as projection and establish a general projection bound that extends classical counting arguments for arcs. This yields restrictions depending explicitly on the block profile and, for full-length blocks, identifies parameter ranges in which linearized Reed--Solomon codes attain the maximum possible number of blocks. Finally, we construct an exceptional three-dimensional MSRD code over $\mathbb F_9$ with three blocks of length two and propose a sum-rank analogue of the MDS conjecture.

0.41

Quantitative Tiling Stability From Quadratic Discrepancy In Hamming Spaces

cs.IT math.CO ·2026-08-26 ·Valery, Grishin, Aryeh Lev Zabokritskiy
theory similarity 0.65
Abstract · 39 pages; no figures. Revised exposition and reference locators. Exact-arithmetic verification companion: https://doi.org/10.5281/zenodo.221…

Quadratic ball discrepancy measures how uniformly a code meets Hamming balls over all centers and radii. Perfect codes minimize this quantity among codes of the same cardinality. We prove a quantitative refinement: at the parameters of every perfect code other than a one-word code or the full space, the discrepancy excess over the minimum is at least an explicit positive multiple of the discrepancy at the packing radius. The latter equals the tiling defect divided by the square of the code cardinality. This defect is the total squared deviation of the covering multiplicity from one. The comparison applies to all codes of that cardinality. For one-error perfect codes, the coefficient is at least one, and no larger constant holds for all such codes; explicit coefficients depending on the parameters can be much larger. The tiling defect also measures the failure of uniform ball noise to smooth a code distribution. Consequently, the same discrepancy excess gives explicit bounds on holes, overlaps, and divergence from the uniform distribution.

0.52

New upper and lower bounds on covering codes K_q(n,R) for alphabets of size 5 <= q <= 21

cs.IT math.CO ·2026-08-20 ·Mark Marosi
theory similarity 0.65
Abstract · 14 pages, 1 figure. v3: revised exposition; certificate hygiene (only certificates improving the tabulated bound are included); 84 improveme…

Let K_q(n,R) denote the minimum cardinality of a q-ary code of length n with covering radius R. We improve the known bounds on K_q(n,R) in 83 cases (82 distinct cells). On the upper-bound side we give 25 improved bounds for 5<=q<=15 -- twenty-four found by search and one propagated by monotonicity -- using two complementary methods: an engineered focused local search seeded with structural constructions, and a large-neighbourhood search driven by exact full-space coverage transforms that evaluates every candidate codeword position simultaneously. These are, to our knowledge, the first improvements to any upper bound on K_q(n,R) with q >= 5 since the 2011 revision of Keri's tables; several bounds decrease by more than 20%, e.g. K_6(8,4)<=166 (previously 216) and K_8(10,5)<=1883 (previously 2461). On the lower-bound side we give 58 improved bounds for 6<=q<=21, obtained from the semidefinite programming hierarchy of Gijswijt and Polak, whose published results cover q<=5, by combining an exact-arithmetic reimplementation of the reduced program with a multiprecision solution pipeline. Every new lower bound is certified by a rational dual solution validated by a standalone exact-arithmetic checker; no floating-point computation is part of the trusted base. The same pipeline also gives strong numerical evidence of limits: on a dozen further cells the certified value of the relaxation, which the solver reports as optimal to within its working precision, lies below the best known bound, indicating that no improvement is available there at this level of the hierarchy. One cell is improved from both sides: 441<=K_6(10,4)<=2751, previously 417--2952. All codes and certificates are provided in machine-readable form together with standalone verifiers.

0.20

Improved LCL Equivalences and Curve Decoding Alphabet Sizes

cs.IT cs.CR ·2026-10-28 ·Rohan Goyal, Venkatesan Guruswami, Yihang Sun, Mary Wootters
theory similarity 0.63
Abstract · 60 pages

Local Coordinate-wise Linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025), capture coding-theoretic properties such as list decoding and list recovery. They showed that every LCL property has the same rate threshold for random linear codes (RLC) and random Reed--Solomon codes (RRS). Brakensiek, Chen, Dhar, and Zhang (2025) extended this to random additive codes. Thus any property of all subspace design codes holds for RLCs and RRS at the same rate. In this work, we improve the probabilistic guarantees in the RRS local equivalence theorem and extend the equivalence to all known subspace design constructions individually. Each such construction, including folded Reed--Solomon codes, has the same LCL threshold as RLC and RRS codes. We apply these results to alphabet-size bounds for curve decoding. Curve decoding, introduced by Goyal and Guruswami (2025) and Carmon et al. (2026), is a row-span-constrained LCL property implying proximity gaps (PG), correlated agreement (CA), and mutual correlated agreement (MCA), relevant to IOPs and SNARKs. Informally, a rate-$R$ code $C \subset \mathbb{F}^n$ is $(\ell,δ,a,b)$-curve decodable if any degree-$\ell$ curve $u:\mathbb{F}\to\mathbb{F}^n$ that is $δ$-close to $C$ on at least $a$ points has at least $b\leq a$ nearby codewords lying on a degree-$\ell$ curve in $C$. Goyal and Guruswami (2025) and Goyal, Guruswami, Sun, and Wootters (2026) established curve decodability for RLC and RRS codes at radius $δ$ approaching $1-R$, but with large alphabets in $\ell$ and $η:=1-R-δ$. Using our improved LCL equivalence and rank-sensitive counting inspired by Goyal and Guruswami (2026), we exponentially improve alphabet requirements while matching the best known values of $(a,b)$. For $\ell=O(1)$, our alphabet-size bounds match the best known for list decoding, and improves results for PG, CA, and MCA.

0.25

On the lengths of MDS codes with a two-transitive permutation automorphism group

cs.IT math.COmath.GR ·2026-09-04 ·Haihua Deng, Tao Feng, Andrey V. Vasil'ev
similarity 0.63
Abstract · 16 pages, comments are welcome

Let $C$ be an $[n,k]_q$ maximum distance separable (MDS) code with $4\le k\le q-3$, and suppose that it has a $2$-transitive permutation automorphism group. In this paper we show that $n\le q+1$, so the MDS conjecture holds for this class of codes.

0.46