The generalized covering radii of Melas codes at t ≥ 3: exact values at six cells, and two data points for 2t+1

Abstract

For an [n,k]_q linear code C with parity-check columns h₁,…,hₙ ∈ 𝔽_qⁿ⁻ᵏ, the t-th generalized covering radius ρₜ(C) of Elimelech, Firer and Schwartz is the least r such that any t syndromes lie together in the span of at most r of the columns. Li and Xiong have recently determined ρ₁ and ρ₂ for every Melas code M(m,q) and have bracketed ρₜ for t ≥ 3: in their asymptotic regime m ≥ t(2t-1) one has ρₜ(M(m,q)) ∈ {2t,2t+1} for q ∈ {2,3} and =2t for q ≥ 4, and below that regime a wider interval. For q ∈ {2,3} no value of ρₜ with t ≥ 3 is determined anywhere in their paper, at any cell; the only cells they pin down have q ≥ 4 and m ≥ t(2t-1), which at t=3 means m ≥ 15. We determine ρₜ(M(m,q)) exactly at six cells: ρₜ(M(3,2))=6 and ρₜ(M(3,3))=6 for all t ≥ 3, ρₜ(M(2,3))=4 for all t ≥ 1, ρ₃(M(4,2))=7, ρₜ(M(4,2))=8 for all t ≥ 4, and ρ₃(M(5,2)) ≥ 7 — with equality by an exhaustive computation carried out outside the formal development. The point of interest is that at both cells whose value we determine and where the trivial bound ρₜ ≤ n-k does not already give it, namely (m,q,t)=(4,2,3) and (5,2,3), that value is 2t+1=7: the upper of the two values Li and Xiong leave open for q ∈ {2,3}. Two further findings are negative rather than new: M(3,2) is the repetition code Rep₂(7), so its whole t ≥ 3 column already follows from a published formula, at a cell the interval statement leaves open; and the value "the covering radius of M(m,2) is 3 if m ≥ 2" printed by Shi, Helleseth, Özbudak and Solé is false at m=2, an error Li and Xiong found first and which we refute in a machine-checked form. Apart from four items labelled where they occur as computations outside the formal development, every assertion below is verified in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   be643f9f337491491e375f50044c63ad3694922176fb3ac2d3349a7c5111a192