🔢 mathematics

New upper bounds on covering codes K_q(n,R) for alphabets of size six and seven

This paper presents improved upper bounds for nine entries in the standard tables of covering codes $K_q(n,R)$ for alphabet sizes $q \in \{6,7\}$ , achieved through focused local search and verified by multiple independent methods.

Original authors: Mark Marosi

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mark Marosi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, multi-dimensional grid where every point represents a unique combination of symbols, like a lock with many dials, each dial having several possible settings. In mathematics, this grid is called a Hamming space, and the points are words made from a specific set of characters. A "code" is simply a carefully selected collection of these points. The goal of covering codes is to place as few points as possible into this grid while ensuring that every single point in the entire space is close to at least one of the chosen points. "Close" is defined by a specific distance limit; if you are within that distance, you are considered covered. This problem is not just an abstract puzzle; it underpins how data is stored and transmitted reliably, ensuring that even if a few symbols get corrupted during transmission, the original message can still be recovered. For decades, mathematicians have been trying to find the absolute minimum number of points needed to cover these grids for various sizes and distances, creating tables of best-known answers that serve as a map for the field.

For more than a decade, this map had stopped updating for certain complex scenarios involving larger sets of symbols. The last major revision of these tables occurred in 2011, and since then, the entries for grids using six or seven different symbols had remained static. The existing answers for these difficult cases were not the result of a deep, targeted search for a better solution. Instead, they were derived from general mathematical rules that combine smaller, simpler solutions into larger ones. These rules provided a safe upper limit—a guarantee that a solution exists within a certain size—but they did not necessarily find the smallest possible solution. It was as if the mapmakers had drawn a large circle around a treasure based on a rough estimate, rather than digging in the ground to find the exact spot.

A new study has finally broken this long-standing freeze, finding significantly smaller collections of points for nine specific scenarios where the alphabet size is six or seven. The researchers, working with an artificial intelligence system, did not rely on the old, broad mathematical rules. Instead, they took the existing, larger solutions and used a focused search method to improve them. This process is akin to starting with a large, slightly inefficient arrangement and then making tiny, precise adjustments to see if the arrangement can be tightened. The system would pick a point in the grid that was not yet covered, look for the best way to move one of the existing points to cover it, and then repeat this process thousands of times. This method of local search allowed the system to escape the limitations of the old general rules and find more efficient arrangements that had been hiding in plain sight.

The results are concrete and specific. For a grid with a length of seven using six symbols, the researchers found a code with 232 points, improving upon the previous upper bound of 246. In another case, for a grid of length eight with six symbols, they reduced the required number of points from the previous upper bound of 1,080 down to 1,045. The most dramatic improvement occurred in a scenario involving a length of eight with six symbols, where the new code requires only 167 points, a reduction of 49 points from the previous upper bound of 216. In total, nine new, smaller codes were discovered. These are not theoretical guesses; the researchers provided the exact list of points for each of these nine codes, allowing anyone to verify the results. To ensure absolute certainty, they checked every single code using four different, independent computer programs. These programs worked in distinct ways: some marked off every covered point on a digital map, while others calculated the distance from every possible point in the grid to the nearest code point. The fact that all methods agreed confirmed that the new codes are valid and that the covering radius is exactly as claimed.

What makes this discovery particularly notable is the method used to find it. The study highlights that the previous limits were not hard walls but rather loose estimates born from a lack of dedicated searching. The researchers found that when they applied a focused, iterative search to these specific problems, they could consistently beat the old bounds. However, this approach did not work everywhere. The study notes that for problems where mathematicians had already performed deep, dedicated searches or used complex algebraic constructions, the new method failed to find improvements. This suggests that the old tables contained a mix of truly optimal solutions and merely convenient estimates, and the new work has successfully peeled back the layer of estimates to reveal the tighter, more efficient solutions underneath.

The work was conducted using a powerful computer processor, but the most unusual aspect of the project is the role of the artificial intelligence. The AI system designed the search strategy, wrote the verification software, and executed the entire process autonomously. The human researchers provided the initial concept and the computing resources, but the AI acted as the primary discoverer, navigating the vast space of possibilities to find these new records. The researchers have made all their findings, including the code lists and the verification tools, publicly available. They intend to merge these new results with the existing tables, creating a modernized, machine-readable version of the map that reflects the current state of knowledge. This update does not just add a few numbers; it demonstrates that even in a field that has been quiet for over a decade, there is still room for discovery when one looks closely enough at the gaps left by general rules.

Technical Summary: New Upper Bounds on Covering Codes $K_q(n, R)$ for Alphabets of Size Six and Seven

Problem Statement
The paper addresses the problem of determining upper bounds for $K_q(n, R)$ , defined as the minimum cardinality of a $q$ -ary code of length $n$ with covering radius $R$ . A code $C \subseteq \mathbb{Z}_q^n$ has covering radius $R$ if every word in the Hamming space $\mathbb{Z}_q^n$ is within distance $R$ of at least one codeword. The study focuses specifically on alphabets of size $q \in \{6, 7\}$ and lengths $n \le 10$ . The author notes that the standard reference tables for these bounds, maintained by Kéri (last updated in 2011), had seen no improvements for $q \ge 5$ since that date. The entries targeted in this work were previously derived solely from general algebraic constructions (such as direct sums and product rules) rather than explicit search, leaving a "relative slack" between the known upper bounds and the theoretical sphere-covering lower bounds.

Methodology
The author employs a focused local search algorithm, rooted in the WalkSAT lineage and similar to tabu search, to improve upon incumbent codes. The methodology consists of three primary components:

Search State and Updates: The search maintains a multiset of $M$ codewords and tracks the coverage count for every word in $\mathbb{Z}_q^n$ . To ensure efficiency, the algorithm utilizes a specific update mechanism derived from Lemma 1. When a single coordinate of a codeword is changed, the set of words leaving the radius- $R$ ball and the set entering the new ball are disjoint and indexed by words at distance exactly $R$ in the remaining coordinates. This allows the algorithm to update exactly $2S$ coverage counters per move, where $S = \binom{n-1}{R}(q-1)^R$ , avoiding a full re-scan of the space.
Search Strategy: The algorithm selects a random uncovered word $u$ and identifies candidate moves: codewords at distance $R+1$ from $u$ are nudged one coordinate toward $u$ . If no such codeword exists, those at the minimum distance are used. All candidates are evaluated exactly and in parallel. The best candidate is committed, with ties broken randomly. To escape stagnation, a codeword is "teleported" to an uncovered word. Parameter studies indicated that evaluating all candidate moves exactly outperformed sampling strategies, and that move quality was more critical than move count (simulated annealing was less effective).
Seeding and Descent: The search is seeded with codes constructed via the same general methods that produced the previous upper bounds (e.g., direct sums). The improvement process involves a "remove-and-repair" descent: the codeword with the smallest "private coverage" (words covered only by that codeword) is deleted, and the resulting deficit is repaired via local search. If successful, the process repeats with $M-1$ codewords. This "factor attack" on small components proved decisive for seeding, while the descent phase broke the rigid product structure of the initial constructions.

Hardware and Implementation
All computations were performed on a single NVIDIA GH200 node using its 64-core Grace CPU. While a CUDA port was implemented, it was found to be latency-bound and slower than the CPU for these specific instance sizes. Move throughput varied from approximately 1,300 moves/second on larger instances to 400,000 moves/second on smaller ones. The search for each entry was stopped before convergence, suggesting further improvements may be possible with increased computation time.

Key Results
The study reports improved upper bounds for nine specific entries in the range $q \in \{6, 7\}$ and $n \le 10$ . The new bounds are:

$K_6(7, 3) \le 232$ (improved by 14 from the previous bound of 246)
$K_6(8, 3) \le 1045$ (improved by 35)
$K_6(8, 4) \le 167$ (improved by 49)
$K_6(9, 4) \le 703$ (improved by 35)
$K_6(9, 5) \le 123$ (improved by 21)
$K_6(10, 4) \le 2951$ (improved by 1)
$K_6(10, 5) \le 610$ (improved by 5)
$K_7(8, 4) \le 329$ (improved by 14)
$K_7(9, 4) \le 1743$ (improved by 100)

The most significant relative improvement is a 23% reduction for $K_6(8, 4)$ . All nine codes are provided explicitly in ancillary files.

Verification
To ensure the validity of the results, every claimed code was subjected to four independent, exhaustive verification methods:

Ball marking: Marking all words within distance $R$ of each codeword on a bitmap.
Meet-in-the-middle: Bitset covering over a coordinate split.
Min-distance scan: Enumerating all $q^n$ words to compute the distance to the nearest codeword.
Hamming-graph dilation: Computing the $R$ -fold neighborhood dilation of the code's indicator vector without calculating distances.
Additionally, a fifth, independently written dilation verifier confirmed all results. The largest verification (involving $6^{10} \approx 60$ million words) completed in seconds.

Significance and Claims
The paper claims these are the first improvements to any upper bound on $K_q(n, R)$ with $q \ge 5$ since 2011. The author attributes the success to the application of modern, large-scale local search hardware to entries that had previously only been addressed by general algebraic constructions. The results demonstrate that "plain local search," when seeded with construction-based incumbents, can outperform inherited arithmetic bounds in cases where the gap between the upper bound and the sphere-covering lower bound is significant (4×–10×). Conversely, the method failed to improve cells that had already been the subject of dedicated search or algebraic construction (where the slack was $\le 3\times$ ).

The author notes an internal inconsistency in Kéri's tables regarding $K_{17}(7, 2)$ , which they observed but did not resolve with a new construction. They intend to publish a merged, machine-readable table incorporating these new bounds alongside existing lower-bound literature.

Authorship and AI Contribution
The paper explicitly states that the discovery and verification pipeline was designed, implemented, and operated autonomously by the AI system Claude (Anthropic). The human author's contributions are limited to the initiating idea (applying modern hardware to frozen tables), methodological guidance, and the provision of computational resources. The AI system is regarded as the primary contributor to the results.

Technical Summary: New Upper Bounds on Covering Codes Kq(n,R)K_q(n, R)Kq​(n,R) for Alphabets of Size Six and Seven

More like this

Technical Summary: New Upper Bounds on Covering Codes $K_q(n, R)$ for Alphabets of Size Six and Seven