arxiv: 2605.08644 · v1 · submitted 2026-05-09 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

On Codes with Support-Constrained Parity Checks

Barron Han , Hikmet Yildiz , Babak Hassibi

Authors on Pith no claims yet

Pith reviewed 2026-05-12 01:14 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords linear codesparity-check matrixsupport constraintsminimum distancegeneralized Reed-Solomon codesGM-MDS theoremerror-correcting codesLDPC codes

0 comments

The pith

Support constraints on a code's parity-check matrix determine a precise optimal minimum distance that is always achievable over large enough fields.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors find the highest minimum distance a linear code can have when its parity-check matrix is forced to have zeros in certain positions according to a given pattern. Such patterns appear when designing codes for limited hardware resources or sparse measurements. They prove this highest distance is reachable by some code as long as the alphabet size is big enough. They also show that unlike generator-matrix constraints, these parity-check constraints sometimes cannot be satisfied by any subcode of a generalized Reed-Solomon code, with an example based on the edges of a complete bipartite graph with six vertices on each side.

Core claim

The optimal minimum distance possible given support constraints on the parity-check matrix is derived and shown to be achievable over sufficiently large fields. When this distance equals the Singleton bound, dual GM-MDS constructions produce generalized Reed-Solomon codes that obey the mask. In the parity-check setting, however, the optimal distance cannot always be realized by subcodes of generalized Reed-Solomon codes, as shown by the vertex-edge incidence matrix of K_{6,6}.

What carries the argument

The support mask on the parity-check matrix, which is a 0-1 pattern indicating allowed nonzero locations, and the combinatorial rule that computes the maximum distance from this mask.

If this is right

When the derived distance matches the Singleton bound, generalized Reed-Solomon codes satisfying the mask exist.
Structured families of masks, including regular, balanced, and cyclic ones, can be analyzed numerically to guide practical constructions.
The GM-MDS theorem does not extend directly to the parity-check matrix setting for achieving optimal distance.
Explicit constructions for the optimal codes exist over sufficiently large fields.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This implies that in systems with strict connectivity limits, such as quantum hardware, designers may need to look beyond Reed-Solomon based codes for the best error correction.
The K_{6,6} counterexample reveals an asymmetry between constraints on generator matrices and on parity-check matrices.
Similar support-constrained problems in other code families could be studied using the same distance derivation approach.

Load-bearing premise

The derived expression for the optimal distance is indeed the largest possible value attainable by any linear code with the given support constraints on its parity-check matrix.

What would settle it

Discovery of a linear code over some field that has a parity-check matrix obeying the support mask yet possesses a larger minimum distance than the derived value, or identification of a generalized Reed-Solomon subcode that achieves the optimal distance for the K_{6,6} mask.

Figures

Figures reproduced from arXiv: 2605.08644 by Babak Hassibi, Barron Han, Hikmet Yildiz.

**Figure 2.** Figure 2: Full-rank cyclic mask distance for n = 9. Comparing with [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Full-rank balanced-cyclic mask distance for [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

read the original abstract

We study linear codes that maximize minimum distance subject to arbitrary support constraints on the parity-check matrix. Such constraints arise naturally in the design of LDPC codes, locally repairable codes, and hardware-constrained systems where each parity check must involve only a limited number of code symbols. They are also essential in quantum error correction, where sparse stabilizers reduce measurement noise and respect the connectivity constraints of physical qubit architectures. We derive the optimal minimum distance possible given support constraints on the parity-check matrix and show it is achievable over sufficiently large fields. When this maximum distance coincides with the Singleton bound for unconstrained parity check matrices, the dual GM-MDS construction yields generalized Reed--Solomon codes obeying the mask. In the generator-matrix setting, the GM-MDS theorem guarantees that the optimal distance can always be achieved by a subcode of a generalized Reed--Solomon code while satisfying arbitrary support constraints. We show that this is not true for the parity-check setting. We exhibit a set of support constraints, derived from the vertex-edge incidence of $K_{6,6}$, for which the optimal minimum distance cannot be realized by any subcode of a generalized Reed--Solomon code over any field. We also analyze structured constraint families -- regular, balanced, and cyclic masks -- through numerical optimization, providing design guidance for practical code constructions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down the exact optimal distance under arbitrary parity-check support constraints, shows achievability over large fields, and gives a clean K_{6,6} counterexample proving GRS subcodes do not always work here unlike in the generator-matrix setting.

read the letter

The main thing to know is that this work derives the optimal minimum distance for linear codes whose parity-check matrix obeys a given support mask and proves the bound is achievable over sufficiently large fields. It also cleanly separates this parity-check case from the generator-matrix setting, where the GM-MDS theorem always lets a GRS subcode hit the bound; here the authors exhibit a vertex-edge incidence mask from K_{6,6} where no GRS subcode over any field reaches the optimum. That distinction and the explicit combinatorial counterexample are the genuinely new pieces. The paper does a solid job framing the problem for LDPC codes, locally repairable codes, hardware-limited systems, and quantum stabilizers, then walks through regular, balanced, and cyclic masks with numerical optimization to give practical design pointers. The claims rest on standard linear-algebra facts with no obvious circularity, and the abstract plus stress-test show internal consistency with no hidden restrictions on the mask visible. One minor soft spot is that full proof details for the general achievability construction would need checking to confirm it holds without edge-case restrictions, but the counterexample itself is independent and combinatorial so it stands on its own. This is aimed at coding theorists and engineers who need precise distance limits imposed by parity-check constraints rather than unconstrained MDS codes. Readers working on mask-constrained designs or looking for alternatives to GRS constructions will find the exact bound and the negative result directly useful. It deserves a serious referee because the separation result and counterexample are new, the bound is exact, and the overall framing is clear enough to repay the time.

Referee Report

0 major / 2 minor

Summary. The paper studies linear codes maximizing minimum distance subject to arbitrary support constraints on the parity-check matrix. It derives the optimal minimum distance for given constraints and proves achievability over sufficiently large fields. When this distance meets the Singleton bound, the dual of the GM-MDS construction yields generalized Reed-Solomon codes satisfying the mask. The authors contrast this with the generator-matrix setting by exhibiting a counterexample based on the vertex-edge incidence matrix of K_{6,6}, showing that the optimal distance cannot always be realized by any GRS subcode over any field. Numerical optimization results are provided for regular, balanced, and cyclic masks to guide practical constructions.

Significance. If the derivation and counterexample hold, the work provides a valuable theoretical benchmark for code design under support constraints, with direct relevance to LDPC codes, locally repairable codes, hardware-constrained systems, and quantum error correction. The explicit combinatorial counterexample is a strength, as it cleanly separates the parity-check setting from the generator-matrix GM-MDS theorem. The numerical analysis for structured families offers practical design insights. The results rest on standard linear-algebra and coding-theory tools plus an explicit graph-theoretic object, with no free parameters or fitted quantities.

minor comments (2)

Abstract: the phrase 'the dual GM-MDS construction' is used without a one-sentence reminder of the original GM-MDS statement or a citation; a brief parenthetical would aid readers.
The notation for the support mask (e.g., how the incidence matrix of K_{6,6} is formally encoded as a constraint set) should be introduced with an explicit definition or small example before the counterexample section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, for highlighting its relevance to LDPC codes and related areas, and for recommending acceptance. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation of the optimal minimum distance under support constraints on the parity-check matrix follows from standard linear-algebraic characterizations of minimum distance (smallest linearly dependent set of columns) adapted to the given mask, with achievability shown constructively over large fields. The K_{6,6} incidence-matrix counterexample is an explicit combinatorial object independent of the bound derivation. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear; the GM-MDS references are to external results and the central claims remain self-contained against standard coding-theory benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard facts from linear coding theory and graph theory; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math Linear codes over finite fields obey the Singleton bound when there are no support constraints
Invoked when comparing the constrained optimum to the unconstrained case.
domain assumption Support constraints are arbitrary 0-1 masks on the parity-check matrix entries
Defines the problem setting and is used throughout the derivation.

pith-pipeline@v0.9.0 · 5529 in / 1510 out tokens · 48601 ms · 2026-05-12T01:14:33.945553+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We derive the optimal minimum distance possible given support constraints on the parity-check matrix and show it is achievable over sufficiently large fields... exhibit a set of support constraints, derived from the vertex-edge incidence of K_{6,6}
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

d⋆_min(M) := τ(M) + 1 ... kr(H) ≤ τ(M)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

On simple multiple access networks,

S. H. Dau, W. Song, and C. Yuen, “On simple multiple access networks,”IEEE J.Sel. A. Commun., vol. 33, p. 236–249, Feb. 2015

work page 2015
[2]

Distributed Reed–Solomon codes for simple multiple access networks,

W. Halbawi, T. Ho, H. Yao, and I. Duursma, “Distributed Reed–Solomon codes for simple multiple access networks,” in2014 IEEE International Symposium on Information Theory, pp. 651–655, June 2014

work page 2014
[3]

On the existence of MDS codes over small fields with con- strained generator matrices,

S. H. Dau, W. Song, and C. Yuen, “On the existence of MDS codes over small fields with con- strained generator matrices,” in2014 IEEE International Symposium on Information Theory, pp. 1787–1791, June 2014

work page 2014
[4]

Optimum linear codes with support-constrained generator matrices over small fields,

H. Yildiz and B. Hassibi, “Optimum linear codes with support-constrained generator matrices over small fields,”IEEE Transactions on Information Theory, vol. 65, pp. 7868–7875, Dec. 2019

work page 2019
[5]

MDS matrices over small fields: A proof of the GM-MDS conjecture,

S. Lovett, “MDS matrices over small fields: A proof of the GM-MDS conjecture,” in2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 194–199, Oct. 2018. 19

work page 2018
[6]

Low-density parity-check codes,

R. Gallager, “Low-density parity-check codes,”IRE Transactions on Information Theory, vol. 8, pp. 21–28, Jan. 1962

work page 1962
[7]

Design of capacity-approaching irregular low- density parity-check codes,

T. Richardson, M. Shokrollahi, and R. Urbanke, “Design of capacity-approaching irregular low- density parity-check codes,”IEEE Transactions on Information Theory, vol. 47, pp. 619–637, Feb. 2001

work page 2001
[8]

NR;multiplexing andchannel coding (3GPPTS 38.212),

3rdGeneration PartnershipProject, “NR;multiplexing andchannel coding (3GPPTS 38.212),”

work page
[9]

Expander codes,

M. Sipser and D. Spielman, “Expander codes,” inProceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 261–271, May 1996

work page 1996
[10]

A family of optimal locally recoverable codes,

I. Tamo and A. Barg, “A family of optimal locally recoverable codes,”IEEE Transactions on Information Theory, vol. 60, pp. 4661–4676, Aug. 2014

work page 2014
[11]

Partial-MDS codes and their application to RAID type of architectures,

M. Blaum, J. L. Hafner, and S. Hetzler, “Partial-MDS codes and their application to RAID type of architectures,”IEEE Transactions on Information Theory, vol. 59, pp. 4510–4519, July 2013

work page 2013
[12]

Good quantum error-correcting codes exist,

A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”Physical Review A, vol. 54, p. 1098–1105, Aug. 1996

work page 1996
[13]

Multiple particle interference and quantum error correction,

A. Steane, “Multiple particle interference and quantum error correction,”Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 452, Nov. 1996

work page 1996
[14]

LDPC-cat codes for low- overhead quantum computing in 2d,

D. Ruiz, J. Guillaud, A. Leverrier, M. Mirrahimi, and C. Vuillot, “LDPC-cat codes for low- overhead quantum computing in 2d,”Nature Communications, vol. 16, Jan. 2025

work page 2025
[15]

Weight-reduced stabilizer codes with lower overhead,

E. Sabo, L. G. Gunderman, B. Ide, M. Vasmer, and G. Dauphinais, “Weight-reduced stabilizer codes with lower overhead,”PRX Quantum, vol. 5, Oct. 2024

work page 2024
[16]

Fault-tolerant quantum computation with constant overhead,

D. Gottesman, “Fault-tolerant quantum computation with constant overhead,”Quantum Info. Comput., vol. 14, p. 1338–1372, Nov. 2014

work page 2014
[17]

Grassl, W

M. Grassl, W. Geiselmann, and T. Beth,Quantum Reed–Solomon Codes, p. 231–244. Springer Berlin Heidelberg, 1999

work page 1999
[18]

Quantum locally recoverable codes,

L. Golowich and V. Guruswami, “Quantum locally recoverable codes,” inProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (Philadelphia, PA), pp. 5512–5522, Society for Industrial and Applied Mathematics (SIAM), Jan. 2025

work page 2025
[19]

Quantum locally recoverable codes via good poly- nomials,

S. Sharma, V. Ramkumar, and I. Tamo, “Quantum locally recoverable codes via good poly- nomials,”IEEE Journal on Selected Areas in Information Theory, vol. 6, pp. 100–110, May 2025

work page 2025
[20]

Quantum codes on a lattice with boundary,

S. B. Bravyi and A. Y. Kitaev, “Quantum codes on a lattice with boundary,” 1998

work page 1998
[21]

Surface codes: Towards practical large-scale quantum computation,

A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,”Physical Review A, vol. 86, Sept. 2012

work page 2012
[22]

On representatives of subsets,

P. Hall, “On representatives of subsets,”Journal of the London Mathematical Society, vol. s1-10, pp. 26–30, Jan. 1935. 20

work page 1935
[23]

Sparse and balanced Reed– Solomon and Tamo–Barg Codes,

W. Halbawi, Z. Liu, I. M. Duursma, H. Dau, and B. Hassibi, “Sparse and balanced Reed– Solomon and Tamo–Barg Codes,”IEEE Transactions on Information Theory, vol. 65, pp. 118– 130, Jan. 2019. 21

work page 2019