PaperlayerView exact revision on arXiv

Source-linked AI summary

Covering 1024 syndromes with 50 columns

Stephen Wu

arXiv:2608.27494v1cs.ITmath.COmath.IT

TL;DR

Whether f(2) = 1 remains open. The paper constructs a 10×50 parity-check matrix and establishes a ten-block (2, 0)-partition for its columns. 50 distinct nonzero columns cover all 1024 syndromes, and exactly 973 syndromes require two columns, establishing covering radius exactly 2.

  • Problem

    Whether f(2) = 1 remains open.

    Source: §1.2 · p. 2

  • Method

    The paper constructs a 10×50 parity-check matrix and establishes a ten-block (2, 0)-partition for its columns.

    Source: §2.1 · p. 2, §2.3 · p. 3

  • Results

    50 distinct nonzero columns cover all 1024 syndromes, and exactly 973 syndromes require two columns, establishing covering radius exactly 2.

    Source: §2.1 · p. 2

  • Takeaways & Limitations

    The ten-block partition supplies the small-block seed structure required as input to Construction QM2^2.

    Source: §2.3 · p. 3, §2.5 · p. 4

    Only the m = 4 and m = 5 outputs are exhaustively verified; later family rows inherit a partition bound, and a covering 49-set may exist.

    Source: §5 · p. 6

Abstract

from arXiv · show

We exhibit a binary linear $[50,40]_2$ code of covering radius $2$, so $\ell_2(10,2)\le 50$, one column below the Kaikkonen--Rosendahl length $51$ that has stood since 2003 and that still seeds the $R=2$ family of Davydov--Marcugini--Pambianco (arXiv:2511.02542). The new matrix admits a $(2,0)$-partition into ten blocks, so Construction $\mathrm{QM}_2^2$ propagates it to exhaustively verified codes of lengths $815$ and $1631$ at $r=18$ and $r=20$, and to the family $n=51\cdot 2^{r/2-5}-1$ of asymptotic density $2601/2048$. The matrices, verifiers, and source are at https://github.com/wustep/maths, pin problems/covering/share/2026-08-24/ at commit 736a38f.

1 Definitions and background

The section defines radius-2 covering through sums of parity-check columns and frames Green’s Problem 40 as an open asymptotic density question. It then motivates replacing the length-51 seed with a length-50 code that can also seed an infinite family.

1.1 Covering radius

  • A code has covering radius 2 when every syndrome is a sum of at most two parity-check columns; ℓ_2(r, 2) is the least length at codimension r.For radius 2, the covering condition is S + S = F_2^r.Source: §1.1 · p. 1

1.2 Green’s Problem 40

  • Whether the asymptotic lower-bound quantity f(2) equals 1 remains open, while Davydov, Marcugini, and Pambianco [1] lowered its bound to 2704/2048.Their QM2 construction produces an infinite family from a short radius-2 code whose partition has few enough blocks.Source: §1.2 · p. 2

1.3 The seed at r = 10

  • The prior r = 10 seed was the length-51 Kaikkonen–Rosendahl code, and its 11-block partition supported the family construction of [1].A length-50 matrix with a small (2, 0)-partition therefore improves the seed entry and re-seeds the family.Source: §1.3 · p. 2

2 Results

A 10×50 parity-check matrix establishes a radius-2 [50,40]_2 code and a ten-block partition. That seed yields exhaustively checked propagated codes and a family whose density tends to 2601/2048.

2.1 The code

  • The rank-10 10×50 matrix gives a [50,40]_2 code of radius 2, covering all 1,024 syndromes at density 319/256, one column shorter than KR’s 51.Its 50 columns are distinct and nonzero.Source: §2.1 · pp. 2–3

2.2 Minimality

  • Deleting any column leaves at least 9 syndromes uncovered, so this 50-column set is minimal; whether a covering 49-set exists remains open.The minimum of 9 uncovered syndromes occurs for exactly columns 381, 479, and 927.Source: §2.2 · p. 3

2.3 A (2, 0)-partition into ten blocks

  • The columns admit a (2, 0)-partition into 10 blocks, versus 11 for the length-51 KR code; the 10-block partition’s minimality remains open.Each of the 973 syndromes requiring a pair has a pair from distinct blocks.Source: §2.3 · p. 3

2.4 Dependent triples

  • Of H’s 10 dependent triples, exactly one meets three distinct blocks, the extra condition used by QM2^5 at r=28.That triple is (491, 734, 821).Source: §2.4 · p. 3

2.5 Propagation

  • With n0=50 and p(H0)=10, the construction permits exactly m=4 and m=5; exhaustive enumeration of every syndrome yields codes of lengths 815 and 1,631, respectively.Source: §2.5 · p. 4

2.6 The family

  • Iteration reaches accessible even r through 64; QM2^3 and QM2^5 fill r=22, 24, 26, and 28, while the n0=50 family’s density tends to 2601/2048.The family’s length and density have closed forms on the reachable r values.Source: §2.6 · p. 4

3 The search

The search found a 50-column matrix covering all 1024 syndromes, then a ten-block (2, 0)-partition that supports propagation to longer codes. The resulting length-815 and length-1631 codes were exhaustively checked.

3.1 The matrix

  • The search tracked representations of each syndrome by up to two columns and targeted uncovered syndromes with candidate columns g or g + s.A one-column swap updates only that column’s singleton and 49 pair-sums, rather than recounting all 1276 sums.Source: §3.1 · pp. 4–5
  • The anneal began from the best single deletion of the length-51 Kaikkonen–Rosendahl seed and reached a covering 50-set after 3,600,281 proposals.Moves that raised the uncovered-syndrome count were accepted with probability e^−∆/T; the search stopped at the first covering set.Source: §3.1 · p. 5
  • A 10×50 matrix of rank 10 with distinct nonzero columns covers all 1024 syndromes, with at least one requiring two columns.The finite check improves the length-51 entry of Table 5.1 of [1] by one column.Source: §3.1 · p. 5

3.2 The partition

  • The partition search enforced 821 unique-pair constraints as graph edges, then required each remaining syndrome to have at least one pair split across blocks.The constraint graph has 50 columns and maximum degree 42; candidate partitions were checked over all 1276 sums.Source: §3.2 · p. 5
  • A verified partition uses 10 blocks, fewer than the 11 found for the Kaikkonen–Rosendahl seed, and satisfies the propagation condition for m = 4 and m = 5.The covering 50-set alone gives ℓ2(10, 2) ≤ 50; the partition is needed for the QM2^2 family.Source: §3.2 · p. 5

3.3 The check

  • The m = 4 and m = 5 outputs cover their full syndrome spaces: length 815 at r = 18 and length 1631 at r = 20, versus published lengths 831 and 1663.The length-815 code covers 262144/262144 syndromes and has density µ = 1.26847; both outputs were exhaustively enumerated and checked.Source: §3.3 · pp. 5–6

4 Verification

The pinned verification pipeline is deterministic and independently checks the matrix and partition. Two verifiers use opposite algorithms, with encoding conventions explicitly handled for the Kaikkonen–Rosendahl baseline.

4.1 Replay

  • The pinned pipeline runs offline with Python 3 and Rust, executes 74 assertions, and produces byte-identical output in about two seconds.The replay exits with status 0 using deterministic inputs.Source: §4.1 · p. 6

4.2 Two verifiers with opposite algorithms

  • The pair-driven and syndrome-driven verifiers differ in traversal, parsing, and rank-pivot choice, and a third outside program confirmed their results.The committed replay compares their fact dumps line by line and reports only when the two verdicts agree.Source: §4.2 · p. 6

4.3 Encoding

  • The repository stores columns LSB-first, so reconstructing the MSB-first Kaikkonen–Rosendahl listing requires reversing each column’s ten bits.A verifier missing this reversal fails on the Kaikkonen–Rosendahl baseline, making the encoding mistake visible.Source: §4.3 · p. 6

5 Scope •

The paper establishes a 50-column construction, but neither optimality nor broad coverage of nearby parameters is settled. Exhaustive verification covers only two propagated outputs, and the asymptotic result remains an upper bound.

Optimality

  • The sphere-covering bound gives ℓ2(10, 2) ≥ 45, leaving lengths 45 through 49 unresolved by that bound.At n = 44, the bound’s count is 991, below 1024.Source: §5 · p. 6
  • For n = 44, the threshold ≥1024 fails with 991; minimality is established only for this 50-set, and a covering 49-set may still exist.Source: §5 · p. 6

Exhaustive checks

  • Only the m = 4 and m = 5 outputs were exhaustively verified; later family rows inherit p(HC) ≤ 2m+1 + 1 from equation (4.4) of [1].Source: §5 · p. 6

Scope and asymptotics

  • The scope excludes r ∈ {12, 14, 16, 22, 24, 26, 28, 42, 44}; asymptotically, the result is f(2) ≤ 2601/2048, while whether f(2) = 1 remains open.Source: §5 · p. 7

6 Files

The public repository places the files under `problems/covering/share/2026-08-24/`, with discovery programs in `compute/` and verification artifacts in `result/`.

6 Files

  • The public repository location is `problems/covering/share/2026-08-24/`.The files are available at `https://github.com/wustep/maths`.Source: §6 · p. 7
  • The discovery programs are in `compute/` and include scripts for checking the matrix and partition, reconstructing Kaikkonen–Rosendahl, searching for a partition, and propagating QM2.Source: §6 · p. 7
  • The `result/` directory contains the verification pipeline, replay script, matrix, and 10-block partition; the scripts include an independent matrix check and QM2 propagation programs.Source: §6 · p. 7

A The matrix as bits

The bit representation specifies the matrix’s row and column order and how each integer column encodes its rows.

A The matrix as bits

Loading 2608.27494v1…