Let G_q be an alphabet of size q≥ 2, let t≥ 1 be fixed, and let C⊆ G_q^n. For X,Y∈ G_q^t× n, define the column Hamming distance by d_H(X,Y)=|j∈1,…,n:X_,j≠ Y_,j|, and define the t-th covering radius of C by R_t(C)=max_X∈ G_q^t× nmin_Y∈ C^td_H(X,Y). Let kappa_t(rho,q) be the infimum of liminf_n→∞n^-1log_q|C_n| over sequences C_n⊆ G_q^n satisfying R_t(C_n)≤ rho n. Determine whether kappa_t(rho,q)= 1-H_q^t(rho),&0≤ rho<1-q^-t,0,&1-q^-t≤ rho≤ 1, where H_Q(rho)=rholog_Q(Q-1)-rholog_Q rho-(1-rho)log_Q(1-rho). When q is a prime power, determine whether the same formula holds when every C_n is required to be a linear code over F_q.

Generalized covering-code rate problem

Let $G_q$ be an alphabet of size $q\ge 2$ , let $t\ge 1$ be fixed, and let $C\subseteq G_q^n$ . For $X,Y\in G_q^{t\times n}$ , define the column Hamming distance by $d_H(X,Y)=|\{j\in\{1,\ldots,n\}:X_{*,j}\ne Y_{*,j}\}|$ , and define the $t$ -th covering radius of $C$ by $R_t(C)=\max_{X\in G_q^{t\times n}}\min_{Y\in C^t}d_H(X,Y)$ . Let $\kappa_t(\rho,q)$ be the infimum of $\liminf_{n\to\infty}n^{-1}\log_q|C_n|$ over sequences $C_n\subseteq G_q^n$ satisfying $R_t(C_n)\le \rho n$ . Determine whether $\kappa_t(\rho,q)=\begin{cases}1-H_{q^t}(\rho),&0\le \rho<1-q^{-t},\\0,&1-q^{-t}\le \rho\le 1,\end{cases}$ where $H_Q(\rho)=\rho\log_Q(Q-1)-\rho\log_Q\rho-(1-\rho)\log_Q(1-\rho)$ . When $q$ is a prime power, determine whether the same formula holds when every $C_n$ is required to be a linear code over $\mathbb F_q$ .

References

Primary source

arXiv

Additional references

The Optimal Asymptotic Rate of Generalized Covering Codes — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new preprint claims to settle the generalized covering-code rate problem in every dimension and alphabet, but the result has not yet been independently verified.

The problem seeks the exact asymptotic rate $\kappa_t(\rho,q)$ for generalized covering codes, extending the cases $t=1$ and $t=2$ . It concerns open questions posed by Elimelech and Schwartz.

Known results

$t=1$ : $\kappa_1(\rho,q)=1-H_q(\rho)$ for $0\le\rho\le1-q^{-1}$ , and $0$ above the threshold (Elimelech, Firer, and Schwartz, 2021).
General $t$ : the ball-covering bound gives $\kappa_t(\rho,q)\ge1-H_{q^t}(\rho)$ .
Binary $t=2$ : a probabilistic upper bound was obtained, with $\kappa_2(\rho,2)=0$ above $\rho=3/4$ (Elimelech, Firer, and Schwartz, 2021).

August 25, 2026 claimed resolution

The preprint The Optimal Asymptotic Rate of Generalized Covering Codes claims $\kappa_t(\rho,q)=1-H_{q^t}(\rho)$ below $1-q^{-t}$ and $0$ above it, including linear codes over prime-power alphabets. If correct, this resolves both open problems; the claim is supported only by the new preprint.

arxiv.org · scholarship.claremont.edu · books.google.com · eprint.iacr.org · terpconnect.umd.edu · e-crt.org · www-cdn.anthropic.com · community.openai.com · arxiv.org · arxiv.org · arxiv.org · arxiv.org · www-cdn.anthropic.com · community.openai.com · community.openai.com · www-cdn.anthropic.com

Current status (as of August 2026): The $t=1$ case and partial $t=2$ results are established, while the all- $t$ , all- $q$ formula is claimed by a new preprint but remains unverified.

Sources

No solutions have been posted yet.