CS Paper Radar

A proof of the Braun-Etzion-Vardy bound for binary subspace codes

Srikanth B. Pai

cs.IT math.CO ·submitted 2026-09-27 16:22 UTC · v1

Abstract

The notion of a linear subspace code in a projective space was introduced by Braun, Etzion and Vardy (2013), who conjectured that a linear subspace code in the projective space has at most 2^n codewords. We resolve this conjecture. A novel character-theoretic argument is used to prove the conjecture and the proof is self-contained.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

On the Length of Maximum Sum-Rank Distance Codes

cs.IT math.CO ·2026-10-16 ·Valentina Astore, Ferdinando Zullo
similarity 0.74
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

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

Efficient construction of subspace design codes over constant alphabet

cs.IT ·2026-10-14 ·Shu Liu
similarity 0.69
Abstract

Subspace-design codes form a central unifying framework in coding theory, connecting probabilistic existence results and explicit algebraically structured constructions. The two core families are folded Reed-Solomon codes and univariate multiplicity codes, both possessing the subspace-design property. These codes reach list-decoding capacity with polynomial-size lists, but their alphabet size grows with code length and hurts practical efficiency. Goyal, Guruswami, and Hsieh achieved a major breakthrough: they constructed the first explicit subspace-design codes over constant-size alphabets via the Alon-Edmonds-Luby expander framework, settling an open problem and showing subspace-design properties can hold without large alphabets. Despite recent progress, constructing subspace-design codes with low-complexity efficient encoding remains a critical open challenge. This work gives an explicit construction of r-dimensional subspace-design codes over a constant alphabet whose size grows exponentially with r. By comparison, Goyal et al. (FOCS 2026) built r-dimensional subspace-design codes with alphabet size doubly exponential in r squared. Our construction is computationally efficient: encoding scales quadratically with block length and linearly with dimension r in field operations. We use modified algebraic geometry codes, replacing rational evaluation points with higher-degree places to obtain a valid additive code. To confirm parameter bounds, we use Moore matrices to analyze determinants with many zero entries. We also generalize univariate multiplicity codes, originally built from Reed-Solomon codes, to algebraic geometry codes, and prove these AG-multiplicity codes achieve optimal parameters.

0.16

Sunflowers of Reed--Solomon Codes

cs.IT math.CO ·2026-09-27 ·Roni Con, Anina Gruica, Maria Montanucci, Ferdinando Zullo
similarity 0.69
Abstract

We introduce and study Reed--Solomon sunflowers, namely families of Reed--Solomon codes whose pairwise intersections are all equal to the same fixed subspace. This notion lies at the intersection of extremal subspace combinatorics and coding theory: it can be viewed as a structured version of the sunflower problem in the Grassmannian, and it naturally produces constant-dimension subspace codes with prescribed minimum distance. We focus mainly on the case in which the center is the one-dimensional space generated by the all-one vector. We give an algebraic criterion, expressed in terms of generalized $V$-matrices, ensuring that a family of Reed--Solomon codes forms such a sunflower. We then study the size of these families through counting and constructions. In dimension two, we show that all distinct Reed--Solomon codes form a sunflower and determine its size by counting Reed--Solomon codes up to affine equivalence of their evaluation vectors. For fixed dimension $k\geq3$ and length $\ell\geq2k-1$, we give an explicit recursive construction with $Ω_{k,\ell}(q^{\lfloor\ell/(2k-1)\rfloor})$ petals and a greedy existence argument with $Ω_{k,\ell}(q^{\ell-2k+2})$ petals as $q\to\infty$. We also apply the greedy argument to obtain families of $[\ell,k]_q$ MDS codes of size $Ω_{k,\ell}(q^{2(\ell-2k+2)})$, whose pairwise intersections have dimension at most one but need not be equal.

0.17

Common zeros of homogeneous polynomials and the weight hierarchy of projective Reed-Muller codes

cs.IT math.ACmath.AG ·2026-11-05 ·Rodrigo San-José
theory similarity 0.68
Abstract

We determine the maximum number of common zeros in projective space of any set of linearly independent homogeneous polynomials of the same degree, when the degree is smaller than the cardinality of the finite field. This proves the conjecture of Beelen, Datta, and Ghorpade, resolving a longstanding problem on common zeros and determining the complete weight hierarchy of the corresponding projective Reed-Muller codes. The proof uses Green's hyperplane restriction bound, combined with a footprint argument that reduces the problem to the affine case solved by Heijnen and Pellikaan. Wei duality then determines the hierarchy in sufficiently large degrees, recovering the complete hierarchy in every degree for the projective plane. Finally, we prove an upper bound valid in every degree, and conjecture that it is always sharp.

0.13

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

cs.IT ·2026-10-29 ·Xiang Fan
theory similarity 0.66
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

Rank-metric intersecting codes

cs.IT math.CO ·2026-11-03 ·Martino Borello, Martin Scotti, Lune Vila
similarity 0.66
Abstract · 18 pages

Intersecting codes are codes in which any two nonzero codewords share a common nonzero coordinate, and they have been extensively studied due to their applications in communication theory, cryptography, and combinatorics. Recently, geometric interpretations have provided new insights into intersecting codes, both in the Hamming metric and, more recently, in the rank metric for linear codes. In this paper, we introduce and study matrix rank-metric intersecting codes. By defining the support of a matrix as its row space, we extend the notion of intersecting codes to the matrix rank-metric setting. Using the slice space associated with the generator tensor of a rank-metric code, we derive a geometric characterization that is equivalent to the intersecting property. This characterization generalizes the known results for linear rank-metric intersecting codes and highlights both analogies and differences with the linear case. In particular, it yields bounds on the parameters of intersecting codes, one of which is sharp and differs from the one in the linear case, together with first constructions. We then consider codes that are closed under multiplication, i.e. matrix algebras. In this setting, the intersecting property can be read off from the algebraic structure, namely the Jacobson radical and the socle. This provides a simple and flexible way to construct many intersecting codes, including codes that do not satisfy the classical sufficient condition on the minimum distance.

0.08

Subspace coverings and generalized covering radii of generalized Zetterberg codes

cs.IT math.CO ·2026-09-20 ·Shitao Li, Yang Li, Gaojun Luo, Zhonghua Sun
theory similarity 0.66
Abstract

Generalized covering radii measure how many columns of a parity-check matrix are needed to generate several syndromes simultaneously. Their finite-geometric counterparts are $(ρ,t)$-saturating sets, for which every $t$-dimensional subspace is contained in a subspace generated by at most $ρ$ prescribed vectors. We investigate this covering problem for the norm-one configurations associated with generalized Zetterberg codes. We establish the upper bound $2t+1$ over every nonbinary finite field and in an explicit binary range, together with complementary lower bounds obtained by counting subspaces and constructing subfield obstructions. For an explicit range of large $t$, these configurations are $t$-strong blocking sets, and the $t^{\rm th}$ generalized covering radius attains its minimum possible value $t$. For binary Zetterberg codes, we determine the second generalized covering radius in every extension degree and prove that the third radius is seven for an infinite subfamily.

0.36