pith. sign in

arxiv: 2604.15080 · v1 · submitted 2026-04-16 · 💻 cs.IT · math.IT

Codes with Large Minimum Distance in Product Codes: Explicit Constructions and Bounds

Amit Berman , Yaron Shany , Itzhak Tamo This is my paper

Pith reviewed 2026-05-10 09:54 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords product codesReed-Solomon codessubcodesminimum distanceexplicit constructionsMDS codesbounds
0
0 comments X

The pith

Explicit subcodes of Reed-Solomon product codes reach the largest possible minimum distance for dimensions r squared minus one, minus two, and all values up to 2r minus one.

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

The paper constructs subcodes inside product codes formed from two Reed-Solomon codes that improve minimum distance without losing too many information bits. For a component code of dimension r the new subcodes hit the theoretical maximum distance exactly when their dimension equals r squared minus one, r squared minus two, or any value at most 2r minus one. The construction uses a field whose size grows only linearly with the total length of the product code. A separate upper bound shows that no subcode of two identical component codes can exceed a certain distance for other dimensions. These results matter because product codes already appear in distributed storage and data-availability sampling, where higher minimum distance directly improves resilience to errors.

Core claim

For Reed-Solomon component codes of dimension r the authors give explicit subcodes of the product code whose minimum distance equals the largest value permitted by the Singleton bound for every dimension at most 2r-1 and also for the two dimensions r squared minus one and r squared minus two; the same constructions require only a field linear in the product-code length. They further prove a new upper bound on the minimum distance attainable by any subcode of the product of two codes that have identical length and dimension.

What carries the argument

Explicit algebraic subcodes of the Reed-Solomon product code obtained by restricting the information symbols in a way that forces many low-weight codewords out of the code while preserving the MDS property of the components.

If this is right

  • The minimum distance of the product code is strictly increased for all listed dimensions while the field size stays linear.
  • The dimension-distance pairs (r squared minus one, optimum distance) and (r squared minus two, optimum distance) become achievable by a concrete construction.
  • Any subcode of a product code built from two identical codes cannot exceed the new upper bound on minimum distance.
  • The constructions give an optimal or near-optimal tradeoff between dimension and distance inside the product code.

Where Pith is reading between the lines

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

  • The linear field-size requirement makes the codes easier to implement than constructions that demand exponentially large fields.
  • The same selection technique might extend to other families of MDS codes beyond Reed-Solomon.
  • Higher minimum distance in these subcodes would reduce the number of erasures that must be recovered in data-availability sampling applications.

Load-bearing premise

The component codes must remain maximum-distance-separable over a field whose size is at least linear in the product-code length.

What would settle it

Exhibit any subcode of dimension r squared minus one whose minimum distance is strictly smaller than the claimed optimum, or prove that the stated upper bound is violated by some explicit subcode of two identical component codes.

Figures

Figures reproduced from arXiv: 2604.15080 by Amit Berman, Itzhak Tamo, Yaron Shany.

Figure 1
Figure 1. Figure 1: The erasure pattern for the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A comparison of the lower bound (12), the upper bound (9) (minimum over a, b), and the upper bound (23) of Appendix B for (n, r) = (32, 8). 7 Examples In this section we include some concrete examples for comparing the upper bounds with the lower bound for the codes Ck. In all examples, we take q to be a power of 2. Example 22. In this example, we examine codes of very low rate. Take n = 32 and r = 8. Henc… view at source ↗
Figure 3
Figure 3. Figure 3: A comparison of the lower bound (12), the upper bound (9) (minimum over a, b), and the upper bound (23) of Appendix B for (a) (n, r) = (32, 16), (b) (n, r) = (128, 64). addition, the exact values at k = r 2 − 1 and k = r 2 − 2 coincide with the upper bound. Also, even for lower k values, the lower bound is not too far from the upper bound. We are not aware of previous explicit constructions in the specific… view at source ↗
Figure 4
Figure 4. Figure 4: A comparison of the lower bound (12), the upper bound (9) (minimum over a, b), and the upper bound (23) of Appendix B for (n, r) = (32, 25). distance for dimensions r 2 − 1, r 2 − 2, and all dimensions at most 2r − 1. Moreover, when r/n ≤ 1/2, the minimum distance of our construction is provably close to optimal over a broad range of dimensions; for example, it attains at least 90% of the maximum possible … view at source ↗
Figure 5
Figure 5. Figure 5: The erasure pattern for the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
read the original abstract

Products of MDS codes are of major practical importance; for a recent example, they are used in Data Availability Sampling (DAS) in blockchain networks such as Celestia and as part of the Ethereum roadmap. This motivates us to consider subcodes of such codes with the goal of obtaining a larger minimum distance. In this paper, we present explicit constructions of subcodes of Reed--Solomon product codes, along with bounds on their minimum distance. In particular, they achieve an optimal or near-optimal dimension--distance tradeoff. For component codes of dimension $r$, our construction requires a field whose size is bounded linearly by the overall product code length, and attains the maximum possible minimum distance for subcode dimensions $r^2-1$, $r^2-2$, and all dimensions at most $2r-1$. Furthermore, we establish a new upper bound on the minimum distance of subcodes of the product of two codes with identical parameters.

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.

Referee Report

0 major / 3 minor

Summary. The paper presents explicit constructions of subcodes of Reed-Solomon product codes along with bounds on their minimum distance, claiming optimal or near-optimal dimension-distance tradeoffs. For component codes of dimension r, the constructions use a field size linear in the product code length and attain the maximum possible minimum distance for subcode dimensions r²-1, r²-2, and all dimensions at most 2r-1. A new upper bound is also established on the minimum distance of subcodes of the product of two codes with identical parameters. The work is motivated by applications such as Data Availability Sampling in blockchain networks.

Significance. If the constructions and bounds are correct, the results would be significant for practical coding applications in blockchain DAS systems, offering improved minimum distances for subcodes of product codes. The explicit constructions (as opposed to non-constructive existence results) and the matching of the new upper bound for the listed dimensions are notable strengths that could inform code design in high-reliability settings.

minor comments (3)
  1. In the abstract, the claim of a field size 'bounded linearly by the overall product code length' should be compared explicitly to the standard Reed-Solomon requirement (field size at least the component length) to clarify any overhead introduced by the subcode construction.
  2. The abstract uses 'optimal or near-optimal' for the dimension-distance tradeoff; specify in the main text which dimensions achieve exact optimality versus near-optimality and provide the corresponding distance expressions.
  3. Add a brief comparison in the introduction or related-work section to prior results on subcodes or punctured product codes to better highlight the novelty of the new upper bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. We appreciate the recognition of the practical relevance of our explicit constructions and new upper bound to applications such as Data Availability Sampling in blockchain networks.

Circularity Check

0 steps flagged

No significant circularity; explicit constructions and bound are self-contained

full rationale

The paper presents explicit constructions of subcodes of Reed-Solomon product codes that attain optimal or near-optimal dimension-distance tradeoffs for specified dimensions, along with a new upper bound on minimum distance for subcodes of product codes. These rely on the standard existence of MDS Reed-Solomon codes over sufficiently large fields, which is an independent, well-established result not derived within the paper. No equations, fitted parameters, self-citations, or ansatzes are shown that reduce any claimed prediction or bound to the inputs by construction. The central claims are presented as direct constructions and a matching upper bound without load-bearing reductions to prior self-referential results.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are mentioned in the abstract; the work relies on standard properties of Reed-Solomon and MDS codes.

pith-pipeline@v0.9.0 · 5462 in / 1046 out tokens · 14292 ms · 2026-05-10T09:54:44.640817+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

  1. [1]

    David Forney, Jr

    1 [For66] G. David Forney, Jr. Generalized minimum distance decoding.IEEE Trans- actions on Information Theory, 12(2):125–131, 1966. 20 [GHK+17] Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, and Sergey Yekhanin. Maximally recoverable codes for grid-like topolo- gies. In Philip N. Klein, editor,Proceedings of the Twenty-Eigh...

    work page 1966

  2. [2]

    Repair locality from a combinatorial perspec- tive

    2 [WZ14a] Anyu Wang and Zhifang Zhang. Repair locality from a combinatorial perspec- tive. In2014 IEEE International Symposium on Information Theory, pages 1972–1976, 2014. 3, 20 [WZ14b] Anyu Wang and Zhifang Zhang. Repair locality with multiple erasure tol- erance.IEEE Transactions on Information Theory, 60(11):6979–6987, 2014. 3 26

    work page 1972