A geometric approach to generalized covering radii of linear codes
2026-06-15 • Information Theory
Information Theory
AI summaryⓘ
The authors explore a connection between certain coding theory problems and finite geometry by looking at special sets of points called $(ρ,t)$-saturating sets. They show these sets exactly match codes with a specific measure called the $t$-th generalized covering radius. Their work connects known concepts like saturating sets and strong blocking sets, providing new ways to understand and construct these sets using geometric and graph-based methods. This geometric perspective helps clarify the structure and limits of these coding-related parameters.
covering radiuslinear codesparity-check matrixfinite geometrysaturating setsstrong blocking setsGrassmannianprojective configurationsaffine geometry
Authors
Gianira N. Alfarano, Giuseppe Marino, Alessandro Neri, Rocco Trombetti
Abstract
Covering problems in coding theory are closely related to finite geometry through the interpretation of the columns of parity-check matrices as point sets in finite vector spaces. Motivated by the recent notion of generalized covering radii of linear codes introduced by Elimelech, Firer and Schwartz, we develop a geometric framework for these parameters. We introduce $(ρ,t)$-saturating sets and show that they are precisely the finite-geometric counterparts of linear codes whose $t$-th generalized covering radius is at most $ρ$. We study the structure of these sets and show that the extremal case $ρ=t$ coincides with the notion of $t$-strong blocking sets. Thus, $(ρ,t)$-saturating sets interpolate between classical saturating sets and strong blocking sets. We provide several equivalent formulations, including affine and dual Grassmannian criteria, derive lower bounds on their size, and give constructions from strong blocking sets, graphs and projective configurations.