Source-linked AI summary
The generalized covering radii of Melas codes
Shuxing Li, Maosheng Xiong
TL;DR
Generalized covering radii measure the access complexity of answering batches of database linear queries, and this paper studies them for Melas codes. It establishes bounds for general t and completely determines the second generalized covering radius, while separately treating a degenerate function case.
Problem
Generalized covering radii were introduced to study linear codes and have a natural interpretation as the access complexity of answering batches of database queries.
Method
The paper establishes lower and upper bounds on the generalized covering radii of Melas codes and applies them across parameter ranges.
Results
The second generalized covering radius of Melas codes is completely determined, and the paper proves a lower bound ρ_t(M(m,q)) ≥ 2t under stated conditions.
Takeaways & Limitations
For database linear querying, generalized covering radii provide a measure of how many parity-check columns suffice to answer a batch of t queries.
Takeaways & Limitations
The degenerate case f = h^2 + h + c_0 requires separate treatment later.
Abstract
from arXiv · showhide
The generalized covering radii have recently emerged as fundamental parameters of linear codes with applications to database linear querying. In this paper, we study the generalized covering radii $ρ_t(M(m,q))$ of Melas codes $M(m,q)$ over any finite field $\mathbb{F}_q$. We determine $ρ_2(M(m,q))$ for all $q$, and for a general $t \ge 3$, we prove that $ρ_t(M(m,q)) \in \left\{2t,2t+1\right\}$ for $q \in \{2,3\}$ and $ρ_t(M(m,q))=2t$ for $q \ge 4$ whenever $m$ is sufficiently large. These results extend recent work on the covering radius of Melas codes.
1 Introduction
The introduction motivates generalized covering radii through database linear querying and studies these parameters for Melas codes. It establishes exact values for t=2 and bounds or exact results for larger t, depending on q and m.
- Motivation: Generalized covering radii measure how many parity-check columns suffice to span any batch of t query vectors.This gives ρ_t(C) an access-complexity interpretation for database linear querying.
- Problem and contribution: Melas codes M(m,q) have length q^m−1, and their covering radii were previously known for all parameter pairs.The paper extends this study to generalized covering radii.
- Problem and contribution: ρ_2(M(m,q)) is completely determined for every prime power q and every m≥1.The values vary across small binary and ternary cases, while for q≥4 they are 2 when m=1 and 4 when m≥2.
- Bounds for general t: 2t is a general lower bound for ρ_t(M(m,q)) when m is sufficiently large relative to t, excluding three small parameter pairs.In particular, m≥t(2t−1) suffices for the lower bound.
- Proof strategy: The lower bounds use a combinatorial technique, whereas the upper bounds rely on character-sum analysis.Together these bounds produce the stated ranges and exact results.
- Bounds for general t: For t≥3 and m≥t(2t−1), ρ_t(M(m,q)) lies in [2t,2t+1] for q∈{2,3}, while ρ_t(M(m,q))=2t for q≥4.For smaller m, the introduction gives broader parameter-dependent intervals.
2 Preliminaries
The preliminaries introduce quadratic and additive characters, character-sum tools, generalized Hamming weights, and the code families used to analyze Melas codes. They also record bounds for related cyclic codes and initial covering-radius values.
- Finite-field tools: A multiplicative quadratic character distinguishes nonzero squares from nonsquares in finite fields, with η(0)=0 by convention.
- Finite-field tools: Weil-type bounds control quadratic-character sums for polynomials that are not polynomial squares and rational functions satisfying specified pole conditions.
- Finite-field tools: Canonical additive characters are defined through the field trace, supporting the paper’s character-sum arguments.
- Code parameters: The r-th generalized Hamming weight d_r(C) is the minimum support size of an r-dimensional subcode, extending the minimum-distance concept.
- Code parameters: The Generalized Supercode Lemma links generalized covering radii to generalized Hamming weights and relative code parameters of a supercode.
- Melas-code setting: For Melas-code-related cyclic codes, the preliminary results give explicit generalized-Hamming-weight bounds and covering-radius values by field size and extension degree.
3 Lower and upper bounds on the generalized covering radii of Melas codes
This section develops lower and upper bounds for generalized covering radii of Melas codes. Lower bounds come from supercodes and generalized Hamming weights, while upper bounds reduce spanning questions to finite-field solvability.
- Lower bounds: The supercode approach yields lower bounds such as ρ_t(M(m,q)) ≥ t + ⌈log_q(t +1)⌉ for relevant parameters.
- Lower bounds: For q=3, the corresponding bound is ρ_t(M(m,3)) ≥ t + ⌈log_3(2t +3)⌉.
- Lower bounds: If m≥t(2t−1) and the exceptional parameter pairs are excluded, then ρ_t(M(m,q)) ≥2t.
- Lower bounds: For t=2, ρ_2(M(m,q)) ≥4 for every m≥2 except (m,q)=(2,2).
- Upper bounds: For sufficiently large Q, both even- and odd-characteristic arguments establish the upper bound ρ_t(M(m,q)) ≤2t+1.
- Upper bounds: The upper-bound proof represents independent vectors inside spans generated by at most 2t+1 vectors and reduces the construction to solvable finite-field systems.
4 Generalized covering radius of M(m,q) with q ≥4
For q≥4, the paper determines the generalized covering radii in the large-m regime and gives a bounded range for smaller m. It also determines the second generalized covering radius.
- General q≥4 result: For q≥4 and 3≤t≤m, ρ_t(M(m,q)) lies in [t+⌈log_q(t+1)⌉,2t] when 3≤m<t(2t−1).
- General q≥4 result: For q≥4 and m≥t(2t−1), ρ_t(M(m,q))=2t.
- Low-order radii: For q≥4, ρ_1(M(m,q))=2 for all m≥1, while ρ_2(M(1,q))=2 and ρ_2(M(m,q))=4 for m≥2.
5 Generalized covering radius of M(m,3)
For M(m,3), the paper derives bounds for generalized covering radii using quadratic-character sums, elliptic curves, and solvability analyses. It determines ρ_2(M(m,3)) and gives ranges for ρ_t(M(m,3)) when t ≥ 3.
- Methods: The analysis uses quadratic characters and character sums over F_3m, including elliptic-curve point counts, to establish auxiliary propositions and solvability conditions.The elliptic curves E_1 and E_2 are used to evaluate relevant character sums.
- Generalized covering radii: For t ≥ 3, the derived range for ρ_t(M(m,3)) narrows to [2t, 2t + 1] when m ≥ t(2t − 1).For smaller m, the stated ranges depend on logarithmic thresholds and include lower bounds involving t + ⌈log_3(2t + 3)⌉.
- Second generalized covering radius: ρ_2(M(m,3)) = 5 for m ≥ 6, while numerical experiments give values 1, 4, and 5 for m = 1, 2, and 3–5, respectively.The m = 2–5 values are reported as numeric-experiment results.
6 Generalized covering radius of M(m,2)
For M(m,2), the paper establishes ranges for ρ_t with t ≥ 3 and determines ρ_2 for sufficiently large m, supplemented by numerical values for small m.
- Generalized covering radii: ρ_t(M(m,2)) lies in [2t, 2t + 1] when m ≥ t(2t − 1), for t ≥ 3.For smaller m, the lower bounds include t + ⌈log_2(t + 1)⌉ and depend on explicit threshold ranges.
- Second generalized covering radius: Numerical experiments indicate ρ_2(M(2,2)) = 2, ρ_2(M(3,2)) = 5, ρ_2(M(4,2)) = 6, and ρ_2(M(m,2)) = 5 for 5 ≤ m ≤ 7.These values complement the proven cases m = 1 and m ≥ 8.
7 Conclusion
The conclusion states that the paper establishes lower and upper bounds for generalized covering radii of Melas codes and completely determines the second generalized covering radius.
- Main contributions: The paper establishes lower and upper bounds on generalized covering radii for Melas codes M(m,q).These bounds are applied to the generalized radii for 3 ≤ t ≤ m under a sufficient condition on m.
- Main contributions: The second generalized covering radius ρ_2(M(m,q)) is completely determined.
Appendix A
The appendix proves auxiliary propositions used in the main results by constructing rational functions and counting field elements satisfying prescribed conditions. The arguments treat even and odd characteristic separately.
- Even characteristic: For even q, the appendix defines rational functions R_i and their subset sums R_I to support positivity results for an associated count N.The functions are built from parameters a_i and nonzero b_i, with E collecting the relevant exceptional points.
- Even characteristic: The rational-function argument reduces functions of the form R_I to h^2 + h + c when R_I belongs to the specified function class.Evaluating at infinity yields a trace condition on c, while poles of h remain among the exceptional points.
- Auxiliary bounds: A pole-degree bound gives ˜L_I ≤ 4|I|, which contributes to the proof that the relevant count N is positive.The appendix also concludes directly that N > 0 after applying the auxiliary lemmas.
- Odd characteristic: For odd q, the appendix defines polynomial products S_i and S_I, using square and nonsquare character behavior to prove positivity of N.The leading coefficient of each S_i is a nonzero square, and nonsquare products are handled separately.
- Odd characteristic: For odd q, Frobenius invariance shows that a monic factor lies in F_Q[x], allowing the character value η(S_I(x)) to be controlled.This yields N′ > 0 and consequently N > 0 in the nonsquare case.
AI Usage Disclosure
The authors disclose using ChatGPT for literature surveying, theorem verification, and identifying proof issues, while retaining responsibility for the paper’s content.
- ChatGPT was used to survey recent literature on generalized covering radii and locate relevant work.
- ChatGPT helped verify the specialization of a cited theorem to Lemma 2.
- That verification led to correcting an error in the specialization in an earlier manuscript version.
- ChatGPT helped identify and repair a gap in the proof of Theorem 3 in an earlier version.
- The authors state that they checked all definitions, statements, proofs, and computations and take full responsibility for the paper.