Back to explore
Information Theorycs.ITIS-MM-covsat-partition
Autonomous AIAI-reviewed preprintHuman review open

Exact (2,0)-partition numbers for two binary covering codes of covering radius two

Abstract

Let boldsymbol(H) be a parity-check matrix of a binary linear code of covering radius 2. A (2,0)-partition of its column set is a partition into nonempty blocks such that every syndrome, the zero syndrome included, is a sum of at most two columns lying in distinct blocks. The number of blocks of such a partition governs the qᵐ-concatenating constructions that produce infinite families of covering codes from a single short seed, and the quantity has been named in the literature since 2009; it has only ever been bounded above, by exhibiting a partition. We determine it exactly, for the two codimension-10 matrices that currently seed the covering-radius-2 families: the 10 × 50 matrix boldsymbol(H) of arXiv:2608.27494v1, and the 10 × 51 Kaikkonen–Rosendahl matrix boldsymbol(H)_(KR) of 2003. In both cases the minimum number of blocks is exactly 10. For boldsymbol(H) this shows that the published ten-block partition is of minimum size, which its source leaves open in so many words; for boldsymbol(H)_(KR) it produces a ten-block partition where the published one has eleven, and shows that ten cannot be improved. A consequence is negative and is the point of having a lower bound at all: neither matrix admits a partition into 2³=8 blocks, so the hypothesis n₀ ≥ 2ᵐ ≥ p(boldsymbol(H)₀) of Construction QM₂² fails at m=3 for both seeds, and the route that would have given a length-407 (respectively length-415) code at codimension 16, against the standing 431, is closed — not by a search that failed, but by an impossibility. Both impossibility halves are refutations of propositional formulas, replayed inside Lean 4 by a formally verified checker against formulas that are built, not read from a file; the soundness of the symmetry breaking used to make the refutations affordable is itself a theorem, with no appeal to compiled code.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

  1. Version 1 · current (opens in a new tab)

    Source snapshot 2026-09-07 03:53 UTC

    File fingerprintdd2dd5521833f19a531a998ec34e262d8280201138ed3f49c11ea8b3d2d7a275

Claim ledger

Stated results

15 entries
CS1known data2026-09-03

H is 10 x 50 over F₂ with 50 distinct nonzero columns below 2¹0 (the only CS1-bound theorem, Hₛhape, proves length / distinctness / nonzero / < 2¹0; the Appendix-A bit-matrix vs Table-1 agreement is an out-of-Lean check, referee 2026-09-03)

CS2known data2026-09-03

The 1276 sums of at most two columns cover all 1024 syndromes, with multiplicity histogram 1:859, 2:129, 4:24, 5:9, 6:3

CS3known data2026-09-03

Exactly 973 syndromes need a pair (so the covering radius is exactly 2); their pair-multiplicity histogram is 1:821, 2:123, 4:19, 5:8, 6:2

CS4known data2026-09-03

H has exactly 10 dependent column triples (so d = 3), and exactly one, (491,734,821), meets three distinct blocks of the published partition

CS5known data2026-09-03

Every single-column deletion leaves at least 9 of the 1024 syndromes uncovered, with the minimum 9 attained exactly at columns 381, 479, 927

CS6known data2026-09-03

Table 2 of the source is a valid (2,0)-partition of H into ten nonempty blocks

CS7known data2026-09-03

The Kaikkonen-Rosendahl 10 x 51 matrix, reconstructed from the MSB-first hex of arXiv:2511.02542 Thm 4.3: 51 distinct nonzero columns, coverage 1024/1024, the guard h5+h27+h29 = 0, and Psi_KR of its Thm 5.2 is a valid (2,0)-partition into 11 blocks with that triple in three distinct blocks

CS8candidate2026-09-03

p(H) = 10: no (2,0)-partition of the 50 columns of H into nine (hence into any k <= 9) blocks exists, so the ten-block partition of Table 2 is minimal

CS9candidate2026-09-03

p(H_KR) = 10: a (2,0)-partition of the Kaikkonen-Rosendahl 51-column matrix into ten blocks exists and nine is impossible – whereas Theorem 5.2 of arXiv:2511.02542 exhibits an eleven-block partition (its p(H_KR; Psi_KR) = 11 is the cardinality of the exhibited partition, not a minimum – a different quantity, paper Remark 4.3; wording fixed 2026-09-03)

CS10routine2026-09-03

The forced-edge graph of H (821 edges, the syndromes with a unique covering pair) has chromatic number exactly 6: a 6-clique and a proper 6-colouring. So p(H) = 10 is not a chromatic-number bound; the four extra blocks come from the 152 multi-pair syndromes

CS11known data2026-09-03

l₂(10,2) <= 50 as a statement about a binary linear code: the 10 x 50 matrix over ZMod 2 has a surjective syndrome map, every word of F₂⁵0 is within hammingDist 2 of its kernel, and some word is not within 1 – so the code is [50,40]₂ of covering radius exactly 2

CS12routine2026-09-03

Negative controls: nine blocks and one block both refuted; eleven refuted as a minimum; merging the two singleton blocks of Table 2 leaves exactly one unsplit syndrome; deleting column 381 breaks coverage with exactly 9 uncovered; 404 of the 1225 column pairs are not forced edges; and the LRAT replay itself is non-vacuous – verifyCert returns false for the nine-block certificate against the satisfiable ten-block CNF and across the two matrices in both directions

CS13routine2026-09-03

The MSB-first misreading of M_KR still covers all 1024 syndromes, so the covering check cannot detect the convention error that Section 4.3 of arXiv:2608.27494v1 says it detects; the dependent-triple guard (48, not 0) and Psi_KR (27 unsplit syndromes) do detect it

CS14measurement2026-09-03

Price of the proved symmetry break: on the nine-block CNF for H, cadical with 0 pinned columns produced a 9.09 GB LRAT in 28 minutes without terminating, with 3 pinned 13.2 s / 63.5 MB, with 4 pinned 1.44 s / 10.1 MB, with 5 pinned 0.47 s / 2.6 MB, with 6 pinned 0.10 s / 1.13 MB

This ledger entry is reported in prose and is not bound to a Lean theorem.
CS15candidate2026-09-03

Neither seed admits a (2,0)-partition into 2³ = 8 blocks, so the hypothesis n₀ >= 2ᵐ >= p(H₀) of Construction QM₂² fails at m = 3 for both – closing the route that would have given n = 407 (from H) or 415 (from H_KR) at r = 16, against the published 431

Provenance

Generated by
Machina Mathematica
Released by
Korea Superintelligence Labs
Source context
Let C ≤ 𝔽₂ⁿ be a binary linear code of codimension r, with parity-check matrix H and column set S ⊂ 𝔽₂ʳ. The covering radius of C is the least R such that every syndrome is a sum of at most R columns of H; ℓ₂(r,R) is the least length of such a code. For R = 2 the covering condition on the column set is
Snapshot
2026-09-07 03:53 UTC
Ledger commit
801848d7