Source-linked AI summary
Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes
Maosheng Xiong, Chi Hoi Yip, Ferdinando Zullo
TL;DR
The paper studies higher generalized covering radii of binary primitive BCH codes. It uses a geometric argument involving a smooth rational point, Jacobian criteria, Frobenius, Bézout’s inequality, and Lang–Weil estimates to establish an exact value for the second generalized covering radius.
Problem
The paper focuses on higher generalized covering radii, beyond the classical case r = 1.
Method
The proof bypasses monodromy and linear-disjointness machinery by using a smooth rational point at infinity, Jacobian criteria, Frobenius, Bézout’s inequality, and an explicit Lang–Weil estimate.
Results
ρ_2(BCH(e, m)) = 3e −1 for every fixed e once m is sufficiently large.
Takeaways & Limitations
The resulting upper bound is sharp for the second generalized covering radius for all sufficiently large m.
Takeaways & Limitations
For r ≥3, the paper does not claim that the upper bound is optimal, and the exact value remains open in general.
Abstract
from arXiv · showhide
Fix integers $e\ge2$ and $r\ge1$. In this paper we study the $r$-th generalized covering radius $ρ_r\left(BCH(e,m)\right)$ of the binary primitive $e$-error-correcting BCH code $BCH(e,m)$. By using an algebraic-geometric reformulation of the covering problem together with an explicit Lang-Weil estimate, we prove that \[ρ_r\bigl(\BCH(e,m)\bigr)\le(r+1)e-1\] for all sufficiently large $m$. For $e\ge7$, this improves a recent result of Belinsky--Zabokritskiy. Our proof gives a substantially simpler geometric approach to this upper bound. In particular it implies that \[ρ_2\bigl(BCH(e,m)\bigr)=3e-1\] for all sufficiently large $m$. Previously it was only known that \[ρ_2\bigl(\BCH(e,m)\bigr) \in \left\{3e-1,3e\right\}\] for all sufficiently large $m$.
1 Introduction
The paper studies generalized covering radii of binary primitive BCH codes and proves asymptotic upper bounds through a simpler algebraic-geometric argument. It also settles the second generalized covering radius for fixed e, while leaving optimality open for r ≥3.
- The r-th generalized covering radius measures the number of coordinate positions needed to cover r target vectors simultaneously with a common position set.
- The proof uses a common-core system of power-sum equations and a smooth F-rational point at infinity to select a Frobenius-defined irreducible component.Bézout’s inequality and an explicit Lang–Weil estimate then produce the required affine rational point.
- The argument bypasses the monodromy and linear-disjointness machinery used in closely related completion-cover work.The alternative method can be simpler asymptotically, whereas the prior approach gives sharper finite-m information and better field-size thresholds as r grows.
- For r ≥3, the paper does not claim the upper bound is optimal, so the exact asymptotic value remains open in general.
2 Lower bounds
The section establishes lower bounds for generalized covering radii using generalized Hamming weights and a counting argument. These bounds provide the baseline against which the geometric upper bound is compared.
- Generalized Hamming-weight bound: The BCH bound and the binary Griesmer bound yield a lower bound on the r-th generalized Hamming weight of C_{e−1}.The argument punctures an arbitrary r-dimensional subcode outside its support and applies the Griesmer bound to the resulting code of minimum distance at least 2e−1.
- Generalized Hamming-weight bound: For r = 1, the lower bound gives 2e −1; for r = 2, it gives the corresponding specialized value.
- Counting bound: L = re −1 is the threshold used in the second lower-bound argument.The proposition assumes q ≥ L and q > 2^rL.
- Counting bound: If every ordered r-tuple of syndromes were covered by at most L columns, a union bound would contradict the total number of ordered syndrome tuples for sufficiently large q.Each L-element locator set spans at most 2^L syndromes, so it covers at most 2^{rL} ordered r-tuples, while the syndrome space contains q^e syndromes and hence q^{er} ordered tuples.
3 The geometric construction
The construction reformulates simultaneous syndrome coverage as a power-sum variety with e−1 common locators and e additional locators per target. A smooth rational point at infinity identifies an F-defined absolutely irreducible component, and Lang–Weil supplies an affine F-rational point yielding the covering bound.
- Geometric setup: The simultaneous system uses e−1 common locators and e additional locators for each of r syndromes, giving re + e −1 variables and expected dimension e −1.
- Affine points: The explicit Lang–Weil estimate applied to the affine component produces an F-rational point for sufficiently large m, and the resulting locators cover every prescribed syndrome tuple with at most (r+1)e−1 columns.The theorem assumes the BCH full-rank conditions, q = 2^m ≥ e, and an explicit field-size threshold.
- Component construction: A smooth F-rational point at infinity has full Jacobian rank re, so it lies on a unique irreducible component of dimension e −1.The Jacobian contains a block-diagonal Vandermonde minor, and the affine chart has dimension re + e −1.
- Component construction: Frobenius fixes the component through the rational point, proving that it is defined over F and absolutely irreducible.
- Affine points: A second Jacobian computation shows that this component is not contained in the hyperplane at infinity, so it meets the affine chart.
- Consequences and scope: For r = 2, the parametrization uses exactly the three nonzero coefficient vectors in F_2^2, making the upper bound sharp for sufficiently large m.
- Consequences and scope: For r ≥ 3, coincident locators can create additional coefficient vectors not represented separately, so the construction need not be optimal.Allowing those vectors from the outset could lead to smaller common supports; the argument therefore does not determine optimality for general e and r ≥ 3.
4 Explicit thresholds and consequences
The paper makes its upper and lower bounds effective by translating geometric and rank conditions into explicit extension-degree thresholds. These thresholds yield exact values for the first two generalized covering radii and grow linearly with r.
- Upper thresholds: 2m > 2D4r e is the field-size condition used to obtain the effective upper bound under the BCH full-rank condition.The conclusion follows directly from Theorem 1.1 and its proof.
- Explicit m-bounds: mLW(e, r) = ⌊1 + 4r log2 De⌋ + 1 translates the Lang–Weil condition into an explicit bound on m.This is one of the thresholds used in the effective argument.
- Explicit m-bounds: The extension degree supplied by the general argument grows linearly with r.This follows from the explicit threshold formula involving 4r log2 De.
- Upper thresholds: mup(e, r) = 4r log2 De + Oe(1) gives an explicit upper threshold for the geometric argument.The proof already supplies this threshold once m is sufficiently large.
- Consequences: For the first two generalized covering radii, the Griesmer lower bound matches the upper bound, so the effective threshold gives exact values.The general counting lower bound is not needed in these two cases.
- Consequences: The displayed second-radius thresholds are sufficient rather than minimal, with mup(3, 3) = 48, mup(4, 3) = 82, mup(5, 3) = 120, and mup(6, 3) = 162.These values are the thresholds furnished by the general argument.