Hamming Ball Covering Growth

Covering Density of Binary Linear Codes

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

The Hamming weight $w(x)$ counts nonzero coordinates and $H_n(r)=\{x\in{\mathbb{F}}_2^n:w(x)\leq r\}$. A subspace $V$ has covering radius at most $r$ when $V+H_n(r)={\mathbb{F}}_2^n$. Its covering density is $|V||H_n(r)|/2^n$. For fixed $r$, $f(r)$ is the least limiting density obtainable along unbounded lengths as in the statement; the subsequent question lets $r$ tend to infinity. [S1] [S2]

Statement recorded in the supplied source.

Let $r$ be fixed and let $H(r)$ be the Hamming ball of radius $r$ in $\mathbb{F}_2^n$. Let $f(r)$ be the smallest constant such that there exist infinitely many $n$ with subspaces $V_n \leq \mathbb{F}_2^n$ satisfying $V_n + H(r) = \mathbb{F}_2^n$ and $|V_n| = (f(r) + o(1)) \frac{2^n}{|H(r)|}$. Does $f(r) \to \infty$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove an unbounded lower bound for the asymptotic density of linear covering codes as the radius grows, or construct bounded-density families refuting divergence. [S1]

Short English statement

As the allowed error radius increases, must binary linear covering codes become increasingly inefficient relative to the elementary sphere-covering bound?

Research attempt

Provenance and scope.

This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.

Formal limits and context.

For a fixed radius $r$, the ambient lengths tend to infinity first. The covering density of a binary linear code $V\leq{\mathbb{F}}_2^n$ is $|V||H_n(r)|/2^n$, and the question then asks whether the least achievable limiting density diverges as $r\to\infty$. The primary problem list concerns linear codes, so constructions of arbitrary nonlinear coverings are not substituted. We compute an explicit family for every fixed radius and examine the syndrome-counting obstruction to improving the elementary lower bound.

The sphere bound in syndrome form.

Let $H$ be a full-rank parity-check matrix with $m$ rows and kernel $V$. The covering condition means that every syndrome in ${\mathbb{F}}_2^m$ is the sum of at most $r$ distinct columns of $H$, because an error vector of weight at most $r$ selects those columns. There are $|H_n(r)|=\sum_{j=0}^r\binom nj$ possible error supports, so necessarily \[ 2^m\leq\sum_{j=0}^r\binom nj. \] Since $|V|=2^{n-m}$, this is exactly covering density at least one. Counting repeated ordered column sums would give the wrong sphere size; distinct supports, including the empty support, are essential.

Radius one is exactly efficient.

For an integer $s\geq1$, take a parity-check matrix whose columns are all nonzero vectors of ${\mathbb{F}}_2^s$, each once. Its length is $L=2^s-1$ and its rank is $s$. Every nonzero syndrome is a column, while zero is represented by no error. Therefore its kernel has covering radius one. There are $L+1=2^s$ possible errors of weight at most one, exactly one for each syndrome, so the density is one. These unbounded lengths show $f(1)=1$, matching the sphere bound.

A product construction for arbitrary fixed radius.

Take the direct product of $r$ copies of the preceding radius-one code, each on a block of length $L$. The resulting binary linear code has length $n=rL$, codimension $rs$, and covering radius at most $r$: correct each block with at most one bit. In fact its covering radius is exactly $r$, because a syndrome nonzero in every block requires at least one error in every block.

Its density relative to the full radius-$r$ ball in $n$ coordinates is \[ D_{r,s}=\frac{1}{(L+1)^r}\sum_{j=0}^r\binom{rL}{j}. \] Now hold $r$ fixed and let $s\to\infty$, hence $L\to\infty$. The degree-$r$ term dominates the fixed polynomial sum, giving \[ D_{r,s}\longrightarrow\frac{r^r}{r!}. \] Thus \[ 1\leq f(r)\leq\frac{r^r}{r!}. \] Stirling's formula makes the upper bound asymptotic to $e^r/\sqrt{2\pi r}$ as the radius subsequently grows. This is an explicit finite upper bound for every radius, not evidence that the optimum itself must grow exponentially or even diverge.

Why the product construction wastes volume.

Its blockwise decoding uses only errors with at most one bit in each block. The ambient Hamming ball also contains errors placing two or more bits in one block while leaving another block untouched. Those extra supports create many repeated syndromes instead of filling additional ones. The density formula measures this discrepancy exactly: the construction provides $(L+1)^r$ blockwise canonical errors, compared with about $(rL)^r/r!$ total low-weight errors. Correlating the blocks could potentially reduce this waste, but the product calculation does not prove such a reduction is impossible.

A nonzero codeword of weight at most $2r$ necessarily creates a collision between two radius-$r$ error syndromes: split its support into two pieces of size at most $r$. Their indicator vectors have the same syndrome and are distinct. Conversely every such collision gives a nonzero codeword of weight at most $2r$. Therefore exact sphere-bound equality requires minimum distance at least $2r+1$. This is a useful structural condition, but near equality permits some collisions. Counting one collision at a time without controlling overlap does not yield a lower density growing with $r$.

Verification and remaining gap.

The parity-check ranks are explicit, all products are linear subspaces, and the order of limits is preserved. For $r=1$, the general formula returns one; for $r=2$ it returns two, consistent with two independent perfect blocks. The collision equivalence uses binary addition, so symmetric difference of supports is the relevant codeword support. The established result is a self-contained all-radius construction and a precise explanation of its inefficiency. The unresolved task is an unbounded universal lower density for linear codes, or a family with uniformly bounded density that defeats divergence.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 170 (GREEN-082), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 A. A. Davydov, Construction of linear covering codes, Problems of Information Transmission 26 $1990$, 317-331 (English translation, 1991). https://www.mathnet.ru/eng/ppi628. Bibliographic information from the supplied record.

• S3 B. Green, 100 Open Problems, Problem 40, version. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.