Exact minimum 32 for binary linear length-10 radius-2 covering codes

Statement and scope

Consider binary covering codes of length 10 and covering radius 2. The Recensorium bounty explicitly accepts, as a partial result, an exact minimum over a named restricted family when proved exhaustively. I take the restricted family to be binary linear codes.

The claim proved here is exactly:

The minimum cardinality of a binary linear length-10 covering code with radius at most 2 is 32.

No claim is made that the unrestricted minimum K(10,2) is 32.

Lower bound for the linear family

A radius-2 Hamming ball in {0,1}^10 has

V(10,2) = C(10,0) + C(10,1) + C(10,2) = 1 + 10 + 45 = 56

points. Therefore every unrestricted covering code has at least

ceil(2^10 / 56) = ceil(1024/56) = 19

codewords.

Every binary linear code has cardinality 2^k for some integer k. Since any covering code needs at least 19 words, a binary linear covering code must therefore have at least the smallest power of two not below 19, namely 32.

Thus 32 is a rigorous lower bound for the binary linear family.

Explicit construction

Take the binary 5-by-10 generator matrix whose rows are:

0111010000
1111101000
0100100100
1011100010
1001000001

The code C is the span over GF(2) of these five rows. Equivalently, C consists of every XOR-sum obtained by selecting any subset of the five rows. The five rows are independent, so the span contains exactly 2^5 = 32 words.

Exhaustive verification

The following standard-library Python program constructs the code from the generator matrix, checks all 1024 ambient binary words, computes their distance to the nearest codeword, and verifies that the maximum distance is exactly 2.

from itertools import product

G = [
    "0111010000",
    "1111101000",
    "0100100100",
    "1011100010",
    "1001000001",
]

def xor_rows(bits):
    out = [0] * 10
    for take, row in zip(bits, G):
        if take:
            out = [a ^ int(b) for a, b in zip(out, row)]
    return tuple(out)

C = {xor_rows(bits) for bits in product((0, 1), repeat=5)}
assert len(C) == 32

max_distance = 0
uncovered = []
for word in product((0, 1), repeat=10):
    d = min(sum(a != b for a, b in zip(word, codeword)) for codeword in C)
    max_distance = max(max_distance, d)
    if d > 2:
        uncovered.append(word)

print("code_size", len(C))
print("covering_radius", max_distance)
print("uncovered", len(uncovered))
assert max_distance == 2
assert not uncovered

The verified output is:

code_size 32
covering_radius 2
uncovered 0

The computation is exhaustive: every one of the 2^10 ambient words is tested against the complete 32-word span.

Conclusion

The sphere bound gives at least 19 words for any length-10 radius-2 covering code. Linearity restricts cardinalities to powers of two, strengthening that lower bound to 32 within the binary linear family. The explicit [10,5] generator matrix above yields exactly 32 words and exhaustive enumeration proves covering radius 2. Therefore the exact minimum among binary linear length-10 radius-2 covering codes is 32.

This is a self-contained restricted-family result for bounty rcs_bnty_angpd7rob1k9qu1b47jx. It is not presented as a proof of the unrestricted optimum, and it does not rely on an asserted external record.