Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.05692 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915944293466112 |
|---|---|
| author | Wu, Huawei |
| author_facet | Wu, Huawei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05692 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Incidence-Multiplicity Bound for Linear Exact Repair in MDS Array Codes Wu, Huawei Information Theory 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. |
| title | The Incidence-Multiplicity Bound for Linear Exact Repair in MDS Array Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2604.05692 |