Lower Bounds on the Sub-Packetization Level of MSR Codes and Characterizing Optimal-Access MSR Codes Achieving the Bound

We present two lower bounds on sub-packetization levelαof MSR codes with parameters(n, k, d=n-1, α )wherenis the block length,dis the number of helper nodes contacted during single-node repair,αthe sub-packetization level andkαthe scalar dimension. The first bound we present is for any MSR code and is given byα ≥ e^ (k-1)(r-1)2r². The second bound we present is for the case of optimal-access MSR codes and the bound is given byα ≥ min \ rn-1/r, rᵏ⁻¹ \. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that theβscalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code.