pith. sign in

arxiv: 2604.05692 · v2 · submitted 2026-04-07 · 💻 cs.IT · math.IT

The Incidence-Multiplicity Bound for Linear Exact Repair in MDS Array Codes

Huawei Wu This is my paper

Pith reviewed 2026-05-10 18:44 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords MDS array codeslinear exact repairrepair bandwidthrepair I/Oincidence multiplicityprojective geometryfield reduction
0
0 comments X

The pith

MDS array codes with redundancy above two obey a strictly tighter lower bound on linear exact repair bandwidth and I/O than earlier projective counts.

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

The paper refines a projective-geometry counting argument to show that any linear exact repair scheme for an (n,k,ℓ) MDS array code over F_q must use at least ℓ(n-1) minus (r-1) times (q^ℓ-1)/(q-1) symbols of repair bandwidth and the same number of I/O accesses, both on average and in the worst case. The new bound matches the prior one when r equals two and improves it for every larger redundancy. The authors also construct MDS array codes from field reductions of normal rational curves that meet the bound for every n in a wide interval once ℓ is at least two, r at least two, and q satisfies simple divisibility conditions with r.

Core claim

Every linear exact repair scheme for an (n,n-r,ℓ) MDS array code over F_q with r≥2 has average and worst-case repair bandwidth and repair I/O at least ℓ(n-1)-(r-1)(q^ℓ-1)/(q-1). This incidence-multiplicity bound is attained simultaneously for bandwidth and I/O by codes obtained from field reduction of normal rational curves whenever ℓ≥2, r≥2, (r-1) divides (q-1), (q-1)/(r-1)≥2, and n lies between 2(r-1)(q^ℓ-1)/(q-1) and q^ℓ+1.

What carries the argument

The incidence-multiplicity bound obtained by refining the projective counting argument to track how often each point or line is visited across the linear repair equations.

Load-bearing premise

The linear repair constraints are completely captured by the incidence relations among points and subspaces in the projective geometry over F_q, with no extra hidden dependencies coming from the MDS property itself.

What would settle it

For parameters ℓ=2, r=3, q=7 (satisfying the divisibility conditions), construct the claimed MDS array code of length n=32 and check whether any linear exact repair scheme achieves bandwidth or I/O below 2(32-1)-2*(49-1)/6.

read the original abstract

We study linear exact repair for $(n,k,\ell)$ MDS array codes over $\mathbb{F}_q$, with redundancy $r=n-k$, in the regime where $q$, $r$, and $\ell$ are fixed and the code length $n$ varies. A recent projective counting argument gives a general lower bound on repair bandwidth and repair I/O in this setting. While this bound is attained over a broad interval of code lengths in the two-parity case, it is not attained once $r\ge 3$ and $\ell\ge 2$. In this paper, we refine the counting argument behind this bound and establish a sharper lower bound, which we call the incidence-multiplicity bound. We prove that for every $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$ with $r\ge 2$, both the average and worst-case repair bandwidth, as well as the average and worst-case repair I/O, are at least $$\ell(n-1)-(r-1)\frac{q^\ell-1}{q-1}.$$This bound agrees with the earlier projective counting bound when $r=2$, and is strictly stronger for every $r\ge 3$. We also show that the incidence-multiplicity bound is sharp in a broad parameter range. Assume that $\ell\ge 2$, $r\ge 2$, $(r-1)\mid(q-1)$, and $(q-1)/(r-1)\ge 2$. Then for every integer $n$ satisfying $$2(r-1)\frac{q^\ell-1}{q-1}\le n\le q^\ell+1,$$ there exists an $(n,n-r,\ell)$ MDS array code over $\mathbb{F}_q$ that attains the incidence-multiplicity bound simultaneously for both repair bandwidth and repair I/O. These codes arise from field reduction of a normal rational curve. Together, these results reveal incidence multiplicity as the governing geometric principle for linear exact repair in MDS array codes beyond the two-parity case.

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 / 2 minor

Summary. The paper refines a projective counting argument to derive the incidence-multiplicity lower bound on linear exact repair bandwidth and I/O for (n,k,ℓ) MDS array codes over F_q with r=n-k≥2: both average and worst-case quantities are at least ℓ(n-1)-(r-1)(q^ℓ-1)/(q-1). The bound coincides with the prior projective bound when r=2 and is strictly stronger for r≥3. The authors further construct MDS array codes attaining the bound simultaneously for bandwidth and I/O when ℓ≥2, r≥2, (r-1)|(q-1), (q-1)/(r-1)≥2, and n lies in the interval [2(r-1)(q^ℓ-1)/(q-1), q^ℓ+1], using field reduction of normal rational curves.

Significance. If the counting argument and constructions hold, the work supplies a tighter, geometrically grounded bound that governs linear exact repair beyond the two-parity case and demonstrates its sharpness over a wide parameter range. The explicit normal-rational-curve constructions and the identification of incidence multiplicity as the governing principle constitute concrete advances for MDS array codes in distributed storage.

minor comments (2)
  1. [Abstract] The abstract states the bound and the sharpness regime clearly, but the parenthetical condition (q-1)/(r-1)≥2 could be restated once in the introduction for readers who skip the abstract.
  2. [Introduction] In the statement of the main theorem, the lower bound expression uses the same symbol ℓ for both the array size and the number of rows; a brief reminder that ℓ is fixed would prevent any momentary ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript. The referee summary accurately captures our refinement of the projective counting argument to the incidence-multiplicity bound and the constructions attaining it via field reduction of normal rational curves. We appreciate the recognition of the advance beyond the r=2 case.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation proceeds via a direct refinement of the projective incidence counting argument applied to the linear repair constraints of any (n,k,ℓ) MDS array code; the resulting incidence-multiplicity lower bound is obtained by algebraic counting that does not presuppose or fit to the final expression. Sharpness is established by an explicit construction that maps normal rational curves in PG(ℓ,r-1) to MDS array codes via field reduction, a standard finite-geometry technique whose parameters are independent of the bound being proved. No self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear in the central chain. The r=2 case recovers a known bound while the r≥3 strengthening follows from the same counting without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on established finite geometry and coding theory without introducing new free parameters or invented entities.

axioms (2)
  • standard math Finite fields F_q and projective spaces PG(ℓ-1,q) obey standard incidence and counting properties.
    Foundation for the refined projective counting argument.
  • domain assumption Normal rational curves exist in projective spaces and their field reductions produce MDS array codes.
    Invoked to establish existence of codes attaining the bound.

pith-pipeline@v0.9.0 · 5671 in / 1557 out tokens · 59034 ms · 2026-05-10T18:44:49.657084+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

10 extracted references · 10 canonical work pages · 1 internal anchor

  1. [1]

    InACM Symposium on Theory of Computing

    doi:10.1145/ 3313276.3316387. [BK18] S. B. Balaji and P. Vijay Kumar. A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes. In2018 IEEE International Symposium on Information Theory (ISIT), pages 2381–2385,

    work page arXiv

  2. [2]

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

    doi:10.1109/ISIT.2018.8437486. [BVK22] S. B. Balaji, Myna Vajha, and P. Vijay Kumar. Lower bounds on the sub-packetization level of MSR codes and characterizing optimal-access MSR codes achieving the bound. IEEE Transactions on Information Theory, 68(10):6452–6471,

    work page doi:10.1109/isit.2018.8437486 2018

  3. [3]

    Pierobon, I

    doi:10.1109/TIT. 2022.3180034. 19 [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. [DV18] Hoang Dau and Emanuele Viterbo. Repair schemes with optimal I/O costs for full-length Reed-Solomon codes with two parities. In2018 IEEE Information Theory Workshop (ITW), pages 1–5, 2018.doi:10.1109/ITW.2018.8613326. [GHZ+25] Chuang Gan, Yuchong Hu, Leyan Zhao, Xin Zhao, Pengyu Gong, and Dan Feng. Revisiting network c...

    work page doi:10.1109/tit.2010 2010

  5. [5]

    org/conference/fast25/presentation/gan

    URL: https://www.usenix. org/conference/fast25/presentation/gan. [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 Secure Computing, 16th Intl Conf on Pervasive Intelligence and Computing, 4th Intl Conf on...

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

  6. [6]

    2019.8849700

    doi:10.1109/ISIT. 2019.8849700. [LW26] Hai Liu and Huawei Wu. Linear exact repair in MDS array codes: A general lower bound and its attainability.arXiv preprint arXiv:2604.04519,

    work page doi:10.1109/isit 2019

  7. [7]

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

    doi:10.48550/ arXiv.2604.04519. [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 internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tit.2025.3645309 2026

  8. [8]

    [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

  9. [9]

    [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. 20 [RTGE17] Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, and Klim Efremenk...

    work page doi:10.1109/tit.2025.3582186 2025

  10. [10]

    [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. 21

    work page doi:10.1109/isit.2017.8006888 2017