Linear Exact Repair in MDS Array Codes: A General Lower Bound and Its Attainability

Hai Liu; Huawei Wu

arxiv: 2604.04519 · v2 · submitted 2026-04-06 · 💻 cs.IT · cs.DM· math.IT

Linear Exact Repair in MDS Array Codes: A General Lower Bound and Its Attainability

Hai Liu , Huawei Wu This is my paper

Pith reviewed 2026-05-10 19:40 UTC · model grok-4.3

classification 💻 cs.IT cs.DMmath.IT

keywords MDS array codesexact repairrepair bandwidthrepair I/Ofinite geometryDesarguesian spreadslinear codessub-packetization

0 comments

The pith

A projective counting argument establishes a general lower bound on linear exact repair bandwidth and I/O for MDS array codes that is attained only when redundancy equals two.

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

The paper develops a geometric approach to linear exact repair in MDS array codes by reformulating the problem in terms of subspace intersections and projective point configurations induced by parity-check matrices. This viewpoint produces a lower bound on average and maximum repair bandwidth and I/O that applies to every such code with redundancy r at least 2. The bound is not attained for r at least 3 and ell at least 2. For r exactly 2 the authors construct MDS array codes from Desarguesian spreads that meet the bound for code lengths up to the MDS maximum q to the ell plus one, and the same codes achieve optimality simultaneously for both bandwidth and I/O metrics.

Core claim

Every linear exact repair scheme for an (n,k,ell) MDS array code over F_q with r=n-k at least 2 must satisfy beta_avg, beta_max, gamma_avg, gamma_max at least ell(n-1) minus (q to the (r-1)ell minus 1) over (q-1), derived by counting points in the projective geometry of the repair subspaces. This obstruction cannot be avoided when r is at least 3 and ell at least 2. When r equals 2 the bound is achieved by explicit MDS array codes built from Desarguesian spreads, up to length n equals q to the ell plus 1, for both repair bandwidth and repair I/O.

What carries the argument

The reformulation of linear exact repair as subspace intersections and the associated projective point configurations in a vector space over F_q, which enables a direct counting argument for the lower bound.

Load-bearing premise

The modeling step that equates linear exact repair to intersections of subspaces and projective point configurations is valid for every MDS array code over F_q.

What would settle it

An explicit (n,k,ell) MDS array code over F_q with r at least 2 whose linear exact repair uses strictly smaller average or maximum bandwidth or I/O than the stated formula would falsify the lower bound.

read the original abstract

For an $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$, how small can the repair bandwidth and repair I/O be under linear exact repair? We study this question in the regime where the field size $q$, the redundancy $r=n-k$, and the sub-packetization level $\ell$ are fixed, while the code length $n$ varies, and we develop a geometric approach to this setting. Our starting point is an intrinsic reformulation of linear exact repair for MDS array codes in terms of subspace intersections and, for repair I/O, the projective point configurations induced by a parity-check realization. This viewpoint yields a simple projective counting argument establishing the general lower bound $$\beta_{\mathrm{avg}},\beta_{\max},\gamma_{\mathrm{avg}},\gamma_{\max}\;\ge\;\ell(n-1)-\frac{q^{(r-1)\ell}-1}{q-1}$$ for linear exact repair of every $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$ with redundancy $r=n-k\ge 2$. To our knowledge, this is the first lower bound of this form that applies to arbitrary redundancy $r\ge 2$ and sub-packetization level $\ell$. At first glance, the projective counting bound appears rather coarse and therefore unlikely to be attained. We prove that this intuition is correct whenever $r\ge 3$ and $\ell\ge 2$. For $r=2$, the picture changes completely. Using Desarguesian spreads from finite geometry, we construct MDS array codes that attain the bound over a broad interval of code lengths, up to the maximum possible length $q^{\ell}+1$, and do so simultaneously for both repair bandwidth and repair I/O. In the smallest nontrivial case $(r,\ell)=(2,2)$, we also prove a converse within the regular-spread model. Together, these results identify a uniform obstruction governing linear exact repair and show that, in the two-parity case, this obstruction is tight.

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

This paper gives a general lower bound on repair bandwidth and I/O for linear exact repair in MDS array codes and shows it is tight for r=2 with explicit Desarguesian spread constructions.

read the letter

The main thing to know is that this paper derives a general lower bound on the repair bandwidth and I/O costs for linear exact repair in MDS array codes and proves it is tight when there are exactly two parities. What is new is the lower bound that applies to arbitrary redundancy r at least 2 and any sub-packetization level ℓ. It comes from a geometric view that turns the repair problem into questions about subspace intersections and projective point counts. The bound is ℓ(n-1) minus (q to the (r-1)ℓ minus 1) over (q-1). They also give constructions based on Desarguesian spreads that achieve this bound for r=2 across a wide range of code lengths, up to the maximum q^ℓ +1, and they achieve it for both average and maximum costs at the same time. For r at least 3 they show the bound cannot be reached when ℓ is at least 2. The counting argument is straightforward and applies uniformly, which is a strength. The constructions are concrete and use standard objects from finite geometry, so they should be verifiable. The paper is honest about where the bound is not tight. One soft spot is that the result is specific to the linear exact repair model and the fixed-q-r-ℓ setting. If someone needs bounds for nonlinear repair or other regimes, this won't directly help. But within its scope the argument holds up. This work is for coding theorists interested in distributed storage and regenerating codes. A reader who follows papers on exact repair will get a clear new bound and some explicit codes out of it. It is worth sending to a serious referee. I recommend putting it through peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript develops a geometric approach to linear exact repair for (n,k,ℓ) MDS array codes over F_q. It reformulates linear exact repair via subspace intersections and projective point configurations induced by parity-check matrices, derives a general lower bound β_avg, β_max, γ_avg, γ_max ≥ ℓ(n−1) − (q^{(r−1)ℓ}−1)/(q−1) for r = n−k ≥ 2 via a projective counting argument, proves non-attainability of the bound when r ≥ 3 and ℓ ≥ 2, and constructs explicit MDS array codes attaining the bound for r = 2 (up to length q^ℓ + 1) using Desarguesian spreads, simultaneously for both repair bandwidth and I/O. A converse is also shown for the (r,ℓ) = (2,2) case within the regular-spread model.

Significance. If the results hold, the work supplies the first general lower bound on linear exact repair metrics that applies uniformly for arbitrary redundancy r ≥ 2 and sub-packetization ℓ, identifies a uniform obstruction, and demonstrates tightness in the two-parity case through explicit geometric constructions. The projective counting argument and the use of Desarguesian spreads for simultaneous attainment of both β and γ bounds are notable strengths that advance both the theoretical understanding and the constructive design of repair-efficient MDS array codes.

minor comments (3)

[§2] §2 (reformulation): the equivalence between linear exact repair and the stated subspace-intersection condition is invoked as intrinsic; a brief self-contained verification for the parity-check realization would aid readers unfamiliar with the modeling step.
[§3] The notation β_avg, β_max, γ_avg, γ_max is introduced in the abstract and used throughout; an explicit definition table or paragraph early in §3 would improve readability.
[Theorem 4 / §5] Theorem statements for the non-attainability result (r ≥ 3, ℓ ≥ 2) and the r = 2 constructions would benefit from a short remark on the precise range of n for which the constructions are valid.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the detailed summary of our contributions, and the recommendation to accept. We are pleased that the projective counting argument, the general lower bound, the non-attainability result for r ≥ 3, and the explicit constructions via Desarguesian spreads for r = 2 were viewed as advancing the understanding of linear exact repair in MDS array codes.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper's lower bound follows from an intrinsic reformulation of linear exact repair as subspace intersections and projective point configurations, followed by a direct dimension and point-counting argument over F_q that enumerates intersections without any fitted parameters or self-referential definitions. The counting step is a standard projective geometry enumeration that applies uniformly to any (n,k,ℓ) MDS array code and does not presuppose the bound. For r=2 the attainability constructions are built explicitly from Desarguesian spreads, which are independent finite-geometric objects shown to preserve the MDS property while meeting the numerical bound for both β and γ; these constructions do not reduce to the lower-bound inputs. No self-citations are load-bearing, no ansatz is smuggled, and no known result is merely renamed. The entire chain is self-contained against external vector-space and finite-geometry benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard linear algebra and finite projective geometry; no data-fitted parameters or new postulated entities are introduced.

axioms (2)

standard math Vector space and subspace intersection properties over finite fields F_q
Invoked to reformulate linear exact repair as subspace conditions.
standard math Counting formulas for points in projective spaces PG(m,q)
Used directly in the lower-bound derivation.

pith-pipeline@v0.9.0 · 5682 in / 1318 out tokens · 59402 ms · 2026-05-10T19:40:18.975470+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/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

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

projective counting argument establishing the general lower bound β_avg, β_max, γ_avg, γ_max ≥ ℓ(n−1)−(q^{(r−1)ℓ}−1)/(q−1)
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

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

Using Desarguesian spreads from finite geometry, we construct MDS array codes that attain the bound

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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The Incidence-Multiplicity Bound for Linear Exact Repair in MDS Array Codes
cs.IT 2026-04 unverdicted novelty 8.0

Derives the incidence-multiplicity lower bound ℓ(n-1) - (r-1)(q^ℓ-1)/(q-1) on repair bandwidth and I/O for MDS array codes with r≥2 and shows it is attained by field reductions of normal rational curves for specified ...

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 1 Pith paper

[1]

[BBBM95] Mario Blaum, Jim Brady, Jehoshua Bruck, and Jai Menon

doi:10.1145/ 3313276.3316387. [BBBM95] Mario Blaum, Jim Brady, Jehoshua Bruck, and Jai Menon. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures.IEEE Transactions on Computers, 44(2):192–202, 1995.doi:10.1109/12.364531. [BK18] S. B. Balaji and P. Vijay Kumar. A tight lower bound on the sub-packetization level of optimal...

work page doi:10.1109/12.364531 1995
[2]

[BR98] Albrecht Beutelspacher and Ute Rosenbaum.Projective geometry: from foundations to applications

doi:10.1109/ISIT.2018.8437486. [BR98] Albrecht Beutelspacher and Ute Rosenbaum.Projective geometry: from foundations to applications. Cambridge University Press,

work page doi:10.1109/isit.2018.8437486 2018
[3]

Pierobon, I

doi:10.1109/TIT. 2022.3180034. [DGW+10] Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan Ramchandran. Network coding for distributed storage systems.IEEE Transactions on Information Theory, 56(9):4539–4551,

work page doi:10.1109/tit 2022
[4]

doi:10.1109/TIT.2010. 2054295. [DM17] Hoang Dau and Olgica Milenkovic. Optimal repair schemes for some families of full- length Reed-Solomon codes. In2017 IEEE International Symposium on Information Theory (ISIT), pages 346–350, 2017.doi:10.1109/ISIT.2017.8006547. [DV18] Hoang Dau and Emanuele Viterbo. Repair schemes with optimal I/O costs for full-length...

work page doi:10.1109/tit.2010 2010
[5]

org/conference/fast25/presentation/gan

URL: https://www.usenix. org/conference/fast25/presentation/gan. [GW16] Venkatesan Guruswami and Mary Wootters. Repairing Reed–Solomon codes. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 216–226, 2016.doi:10.1145/2897518.2897525. [HT16] J. W. P. Hirschfeld and J. A. Thas.General Galois Geometries. Springer M...

work page doi:10.1145/2897518.2897525 2016
[6]

URL: https: //www.intel.cn/content/dam/develop/external/us/en/documents/ case-study-of-tencent-ultra-cold-storage-system-optimization-720747. pdf. 23 [KG18] Katina Kralevska and Danilo Gligoroski. An explicit construction of systematic MDS codes with small sub-packetization for all-node repair. In2018 IEEE 16th Intl Conf on Dependable, Autonomic and Secur...

work page doi:10.1109/dasc/picom/datacom/cyberscitec.2018.00066 2018
[7]

2019.8849700

doi:10.1109/ISIT. 2019.8849700. [LT25] Jie Li and Xiaohu Tang. Efficient repair of ( k + 2, k) degraded read friendly MDS array codes with sub-packetization 2.arXiv preprint arXiv:2510.23316,

work page doi:10.1109/isit 2019
[8]

[LXZ26] Zhongyan Liu, Jingke Xu, and Zhifang Zhang

doi: 10.48550/arXiv.2510.23316. [LXZ26] Zhongyan Liu, Jingke Xu, and Zhifang Zhang. Calculating the I/O cost of linear repair schemes for RS codes evaluated on subspaces via exponential sums.IEEE Transactions on Information Theory, 72(2):994–1010, 2026.doi:10.1109/TIT.2025.3645309. [LZ25] Zhongyan Liu and Zhifang Zhang. A formula for the I/O cost of linea...

work page doi:10.48550/arxiv.2510.23316 2026
[9]

[RRT25] Vinayak Ramkumar, Netanel Raviv, and Itzhak Tamo

doi:10.1561/0100000115. [RRT25] Vinayak Ramkumar, Netanel Raviv, and Itzhak Tamo. ε-MSR codes for any set of helper nodes.IEEE Transactions on Information Theory, 71(9):6657–6667,

work page doi:10.1561/0100000115
[10]

[RSR17] K

doi:10.1109/TIT.2025.3582186. [RSR17] K. V. Rashmi, Nihar B. Shah, and Kannan Ramchandran. A piggybacking design framework for read-and download-efficient distributed storage codes.IEEE Transactions on Information Theory, 63(9):5802–5820, 2017.doi:10.1109/TIT.2017.2715043. [RTGE17] Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, and Klim Efremenko. ...

work page doi:10.1109/tit.2025.3582186 2025
[11]

[SCC+25] Zhirong Shen, Yuhui Cai, Keyun Cheng, Patrick P

doi:10.1109/ISIT.2017.8006888. [SCC+25] Zhirong Shen, Yuhui Cai, Keyun Cheng, Patrick P. C. Lee, Xiaolu Li, Yuchong Hu, and Jiwu Shu. A survey of the past, present, and future of erasure coding for storage systems.ACM Transactions on Storage, 21(1), 2025.doi:10.1145/3708994. [Tie73] Aimo Tiet¨ av¨ ainen. On the nonexistence of perfect codes over finite fi...

work page doi:10.1109/isit.2017.8006888 2017
[12]

Amichai Painsky

doi:10.1007/ 978-3-642-58575-3. [WHL+21] Ting-Yi Wu, Yunghsiang S. Han, Zhengrui Li, Bo Bai, Gong Zhang, Xiaoyang Zhang, and Xiang Wu. Achievable lower bound on the optimal access bandwidth of ( k + 2, k, 2)- MDS array code with degraded read friendly. In2021 IEEE Information Theory Workshop (ITW), pages 1–5, 2021.doi:10.1109/ITW48936.2021.9611476. [ZLH25...

work page doi:10.1109/itw48936.2021.9611476 2021
[13]

MDS array codes.arXiv preprint arXiv:2509.21036, 2025.doi:10.48550/arXiv.2509.21036. 25

work page doi:10.48550/arxiv.2509.21036 2025

[1] [1]

[BBBM95] Mario Blaum, Jim Brady, Jehoshua Bruck, and Jai Menon

doi:10.1145/ 3313276.3316387. [BBBM95] Mario Blaum, Jim Brady, Jehoshua Bruck, and Jai Menon. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures.IEEE Transactions on Computers, 44(2):192–202, 1995.doi:10.1109/12.364531. [BK18] S. B. Balaji and P. Vijay Kumar. A tight lower bound on the sub-packetization level of optimal...

work page doi:10.1109/12.364531 1995

[2] [2]

[BR98] Albrecht Beutelspacher and Ute Rosenbaum.Projective geometry: from foundations to applications

doi:10.1109/ISIT.2018.8437486. [BR98] Albrecht Beutelspacher and Ute Rosenbaum.Projective geometry: from foundations to applications. Cambridge University Press,

work page doi:10.1109/isit.2018.8437486 2018

[3] [3]

Pierobon, I

doi:10.1109/TIT. 2022.3180034. [DGW+10] Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan Ramchandran. Network coding for distributed storage systems.IEEE Transactions on Information Theory, 56(9):4539–4551,

work page doi:10.1109/tit 2022

[4] [4]

doi:10.1109/TIT.2010. 2054295. [DM17] Hoang Dau and Olgica Milenkovic. Optimal repair schemes for some families of full- length Reed-Solomon codes. In2017 IEEE International Symposium on Information Theory (ISIT), pages 346–350, 2017.doi:10.1109/ISIT.2017.8006547. [DV18] Hoang Dau and Emanuele Viterbo. Repair schemes with optimal I/O costs for full-length...

work page doi:10.1109/tit.2010 2010

[5] [5]

org/conference/fast25/presentation/gan

URL: https://www.usenix. org/conference/fast25/presentation/gan. [GW16] Venkatesan Guruswami and Mary Wootters. Repairing Reed–Solomon codes. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 216–226, 2016.doi:10.1145/2897518.2897525. [HT16] J. W. P. Hirschfeld and J. A. Thas.General Galois Geometries. Springer M...

work page doi:10.1145/2897518.2897525 2016

[6] [6]

URL: https: //www.intel.cn/content/dam/develop/external/us/en/documents/ case-study-of-tencent-ultra-cold-storage-system-optimization-720747. pdf. 23 [KG18] Katina Kralevska and Danilo Gligoroski. An explicit construction of systematic MDS codes with small sub-packetization for all-node repair. In2018 IEEE 16th Intl Conf on Dependable, Autonomic and Secur...

work page doi:10.1109/dasc/picom/datacom/cyberscitec.2018.00066 2018

[7] [7]

2019.8849700

doi:10.1109/ISIT. 2019.8849700. [LT25] Jie Li and Xiaohu Tang. Efficient repair of ( k + 2, k) degraded read friendly MDS array codes with sub-packetization 2.arXiv preprint arXiv:2510.23316,

work page doi:10.1109/isit 2019

[8] [8]

[LXZ26] Zhongyan Liu, Jingke Xu, and Zhifang Zhang

doi: 10.48550/arXiv.2510.23316. [LXZ26] Zhongyan Liu, Jingke Xu, and Zhifang Zhang. Calculating the I/O cost of linear repair schemes for RS codes evaluated on subspaces via exponential sums.IEEE Transactions on Information Theory, 72(2):994–1010, 2026.doi:10.1109/TIT.2025.3645309. [LZ25] Zhongyan Liu and Zhifang Zhang. A formula for the I/O cost of linea...

work page doi:10.48550/arxiv.2510.23316 2026

[9] [9]

[RRT25] Vinayak Ramkumar, Netanel Raviv, and Itzhak Tamo

doi:10.1561/0100000115. [RRT25] Vinayak Ramkumar, Netanel Raviv, and Itzhak Tamo. ε-MSR codes for any set of helper nodes.IEEE Transactions on Information Theory, 71(9):6657–6667,

work page doi:10.1561/0100000115

[10] [10]

[RSR17] K

doi:10.1109/TIT.2025.3582186. [RSR17] K. V. Rashmi, Nihar B. Shah, and Kannan Ramchandran. A piggybacking design framework for read-and download-efficient distributed storage codes.IEEE Transactions on Information Theory, 63(9):5802–5820, 2017.doi:10.1109/TIT.2017.2715043. [RTGE17] Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, and Klim Efremenko. ...

work page doi:10.1109/tit.2025.3582186 2025

[11] [11]

[SCC+25] Zhirong Shen, Yuhui Cai, Keyun Cheng, Patrick P

doi:10.1109/ISIT.2017.8006888. [SCC+25] Zhirong Shen, Yuhui Cai, Keyun Cheng, Patrick P. C. Lee, Xiaolu Li, Yuchong Hu, and Jiwu Shu. A survey of the past, present, and future of erasure coding for storage systems.ACM Transactions on Storage, 21(1), 2025.doi:10.1145/3708994. [Tie73] Aimo Tiet¨ av¨ ainen. On the nonexistence of perfect codes over finite fi...

work page doi:10.1109/isit.2017.8006888 2017

[12] [12]

Amichai Painsky

doi:10.1007/ 978-3-642-58575-3. [WHL+21] Ting-Yi Wu, Yunghsiang S. Han, Zhengrui Li, Bo Bai, Gong Zhang, Xiaoyang Zhang, and Xiang Wu. Achievable lower bound on the optimal access bandwidth of ( k + 2, k, 2)- MDS array code with degraded read friendly. In2021 IEEE Information Theory Workshop (ITW), pages 1–5, 2021.doi:10.1109/ITW48936.2021.9611476. [ZLH25...

work page doi:10.1109/itw48936.2021.9611476 2021

[13] [13]

MDS array codes.arXiv preprint arXiv:2509.21036, 2025.doi:10.48550/arXiv.2509.21036. 25

work page doi:10.48550/arxiv.2509.21036 2025