Source-linked AI summary
Linear Programming Bounds for Locally Recovery Codes II
Ming-Hsuan Kang, Maosheng Xiong
TL;DR
Locally recoverable code bounds can lose how local and global differences align when they retain only a single distance marginal. This paper builds a polynomial-size three-block LP for arbitrary q-ary all-symbol locally recoverable codes; certified comparisons show strict improvement over the outside-distance marginal in thirteen of fifteen cases and establish several exact maxima.
Problem
Collapsing local and global distances into separate marginals loses which values occur together for a codeword pair and recovery view.
Source: §I · p. 1Method
The paper retains helper-set, recovered-coordinate, and outside-view weights and combines their averaged identities with locality constraints and product-Krawtchouk positivity in a polynomial-size LP.
Source: §VI · p. 12Results
The three-block bound is strictly smaller than the outside-distance marginal in thirteen rows and equal in the remaining two; verified constructions determine seven exact maximum code sizes and twelve exact maximum linear dimensions.
Source: §I · p. 2, §V · p. 10Takeaways & Limitations
Preserving three-block coupling can strictly improve finite-length bounds over binary, ternary, and quaternary alphabets.
Source: §VI · p. 12
Abstract
from arXiv · showhide
We give a polynomial-size linear programming bound for $q$-ary all-symbol locally recoverable codes with locality parameters $(r,\delta)$, without assuming linearity. The key idea is to keep, for every ordered pair of codewords and every selected recovery view, the joint Hamming weight on the helper set, the recovered coordinate, and the rest of the code -- rather than collapsing this triple into a single distance, as earlier formulations do. Averaging this three-block distribution over recovery views of the same length yields exact identities linking it to the global distance distribution, together with nonnegative product-Krawtchouk constraints that encode locality and spectral positivity simultaneously. The resulting LP has polynomially many variables, its optimum dominates the ordinary Delsarte bound, and an earlier outside-distance formulation, the convex-hull bound of Li--Wei--Xiong, and the dual-based bound of Gruica--Jany--Ravagnani all arise from it as coarser marginals. Exact rational certificates over $q=2,3,4$ show the bound is strictly stronger than the best of these prior LPs in thirteen of fifteen tested cases, pinning down seven exact maximum code sizes and twelve exact maximum linear dimensions.
I. INTRODUCTION
The paper develops a three-block LP for arbitrary q-ary all-symbol locally recoverable codes, preserving how each codeword pair’s helper, recovered-coordinate, and outside-view differences occur together. Its certified bounds improve on the outside-distance marginal in thirteen cases and determine seven exact maximum code sizes and twelve exact maximum linear dimensions.
I. INTRODUCTION
- The LP retains the helper-set, recovered-coordinate, and outside-view weights for each ordered codeword pair and recovery view, preserving their coupling after aggregation.The paper notes that this is the finest block-weight description considered short of tracking individual difference vectors.Source: §I · p. 1
- Averaging recovery views of the same length gives exact centered identities, locality constraints, and product-Krawtchouk positivity in a polynomial-size LP.The framework does not assume linearity or disjoint recovery views.Source: §I · p. 1
- The global Delsarte transform and its two coordinate-centered sectors decompose into nonnegative three-block components.The three-block distribution also projects to the outside-distance marginal and the LWX and GJR statistics.Source: §I · p. 2
- The three-block LP is strictly stronger than the outside-distance marginal in thirteen cases, and verified constructions determine seven exact maximum code sizes and twelve exact maximum linear dimensions.The LP also yields exact rational bounds for fifteen parameter sets over q = 2, 3, 4.Source: §I · p. 2
II. LOCALITY AND COORDINATE-PARTITION POSITIVITY
The section formalizes all-symbol locality through a selected recovery view for each coordinate and develops coordinate-partition positivity for the resulting blocks. Keeping the recovered coordinate distinct from its helper set preserves a distinction used by the locality constraints.
II. LOCALITY AND COORDINATE-PARTITION POSITIVITY
- All-symbol (r, δ)-locality assigns each coordinate a selected recovery view; δ is its local minimum distance, while r bounds view size, up to r + δ − 1.When δ = 2, this is the classical locality notion with r helper symbols.Source: §II · p. 2
- Separating the recovered coordinate from the helper set preserves whether that coordinate differs, a distinction needed by the later locality constraints.This separation adds no information beyond the complete difference vector on the recovery view.Source: §II · p. 3
- Coordinate-partition positivity follows from a sum of squared absolute values and applies to nonlinear as well as linear codes.For linear codes, the corresponding right-hand side is the code size times the partitioned dual weight distribution.Source: §II · pp. 3–4
III. THE THREE-BLOCK DISTANCE DISTRIBUTION AND LP
The three-block distance distribution records, by recovery-view length, the helper-set weight, outside-view weight, and whether the recovered coordinate differs for each ordered codeword pair. Its identities link these counts to global distance layers, while locality and partition positivity provide additional LP constraints.
III. THE THREE-BLOCK DISTANCE DISTRIBUTION AND LP
- The three-block distribution counts ordered pairs by recovery-view length and by helper weight a, outside-view weight c, and recovered-coordinate difference b.The ranges are δ ≤ t ≤ R0, 0 ≤ a < t, 0 ≤ c ≤ n − t, and b ∈ {0, 1}.Source: §III · p. 4
- Summing over views and ordered pairs gives exact identities relating each global distance layer to the three-block distribution.For a pair at distance ℓ, the distinguished coordinate agrees in n − ℓ choices and differs in ℓ choices.Source: §III · p. 4
- Locality forces the distance within each recovery view to be at least δ, and projection collisions impose an additional inequality.The section also derives product-Krawtchouk positivity by applying coordinate-partition positivity to each view and averaging over coordinates of the same length.Source: §III · p. 5
A. Complete LP formulation
The complete LP is specified by five parameters and uses three-block variables indexed by view length and the three block weights. Its constraints make the optimum a valid upper bound for all-symbol locally recoverable codes without requiring linearity.
A. Complete LP formulation
- The five parameters q, n, d, r, and δ determine every variable, index range, and constraint, so no code or explicit recovery-view choice is needed to state or solve the LP.The primary variables are the three-block counts indexed by t, a, c, and b.Source: A. Complete LP formulation · p. 5
- Every q-ary code with minimum distance at least d and all-symbol (r, δ)-locality has size at most the three-block LP optimum, with no linearity assumption.For linear codes, the LP also admits a dual-weight interpretation.Source: A. Complete LP formulation · p. 6
- The constraints include centered identities, local-distance zeros, projection-collision inequalities, and three-block Fourier inequalities.These constraints yield a feasible point from any code meeting the stated distance and locality conditions.Source: A. Complete LP formulation · p. 6
IV. SPECTRAL DECOMPOSITION AND SELECTED PROJECTIONS
The three-block variables admit exact spectral identities and decompositions, so their constraints recover ordinary Delsarte positivity while supporting coarser projections.
IV. SPECTRAL DECOMPOSITION AND SELECTED PROJECTIONS
- The LP permits projections that retain selected indices or linear moments, including global-distance, outside-distance, LWX, and GJR statistics.These projections reduce the three-block variables to coarser descriptions.Source: §IV · p. 7
- Every feasible three-block LP point satisfies the global spectral decomposition, which implies the ordinary Delsarte inequalities.The decomposition expresses global spectral positivity through nonnegative three-block components.Source: §IV · p. 7
- For each function, adding the two centered identities yields an identity used to establish the global spectral decomposition.The proof substitutes the Krawtchouk function into this relation.Source: §IV · p. 7
- The distinguished-coordinate sector identities express Krawtchouk terms through weights on the shortened length n − 1.The displayed recurrences relate K_w at length n to K_{w−1} or K_w at length n − 1.Source: §IV · p. 7
A. Global-distance and outside-distance projections
Aggregating three-block variables by total weight recovers the global distance distribution, while projecting to outside distance can discard spectral information.
A. Global-distance and outside-distance projections
- Retaining only the total weight ℓ = a + c + b recovers the ordinary global distance distribution.Its Delsarte positivity is an exact sum of three-block inequalities.Source: A. Global-distance and… · p. 8
- The outside-distance marginal retains helper distance and the recovered-coordinate indicator, but sums out outside distance.This marginal is the basis of the earlier outside-distance formulation.Source: A. Global-distance and… · p. 8
- Discarding the three-block variables recovers the ordinary Delsarte LP.The outside-distance formulation retains additional projected constraints alongside Delsarte constraints.Source: A. Global-distance and… · p. 8
- The outside-distance projection can be strictly weaker because it discards every spectral component with s > 0.The hierarchy also includes constraints obtained by discarding nonnegative terms at higher weights.Source: A. Global-distance and… · p. 8
B. Moment summaries: LWX and GJR
The three-block distribution supports moment and dual-statistic projections that connect the LP to LWX and GJR formulations.
B. Moment summaries: LWX and GJR
- The LWX formulation retains factorial moments of the nonzero-at-i sector, with a length-resolved identity giving its three-block projection.This corresponds to the nonlinear factorial-moment identity of Li–Wei–Xiong [10, Theorem 3].Source: B. Moment summaries: LWX and GJR · p. 8
- In this normalization, nonnegative Z_t variables encode a common mixture of admissible local lengths in an extended LWX convex-hull LP.The LP also includes global Delsarte constraints and nonnegative v_w variables.Source: B. Moment summaries: LWX and GJR · p. 9
- Table V.1 presents certified LP bounds and verified constructions, with bold entries marking improved induced linear-dimension caps.Nonintegral entries include decimal approximations.Source: Table V.1 · p. 10
- For linear codes, a coordinate-pointed dual marginal records total dual weight and whether a dual word is nonzero at coordinate i, but not its support split across S_i and O_i.This is the refined-weight statistic used by Gruica, Jany, and Ravagnani; their LP is applied directly for the comparison.Source: B. Moment summaries: LWX and GJR · p. 10
- The balanced base LP matches the symmetrized GJR dimension bound for nondegenerate linear codes, but this does not extend to the full higher-moment LWX strengthening.The stated equality concerns the LP with v_1 = 0 and positive-order moment constraints omitted.Source: B. Moment summaries: LWX and GJR · p. 10
- The outside-distance marginal, LWX moments, and GJR statistic are selected projections, not an exhaustive hierarchy.Other aggregations may reduce computation while discarding nonnegative spectral information.Source: B. Moment summaries: LWX and GJR · p. 10
V. CERTIFIED FINITE-LENGTH BOUNDS
Certified comparisons show the three-block bound improves on the outside-distance marginal in most tested cases, while verified constructions establish exact maximum sizes and linear dimensions for subsets of the tested parameters.
V. CERTIFIED FINITE-LENGTH BOUNDS
- Verified constructions establish seven exact maximum code sizes and twelve exact maximum linear dimensions across the tested parameter sets.When the three-block LP value equals the size of a verified construction, the maximum size is determined without assuming linearity.Source: §V · pp. 10–11
- Every displayed LP value has a rational primal–dual certificate independently checked of the numerical optimizer.The table also gives the size of a verified linear code for each parameter set.Source: §V · p. 10
- The three-block bound is strictly smaller than the outside-distance marginal in 13 of 15 rows and equal in the other two; the outside-distance marginal improves on LWX in four rows.The section also notes two strict improvements that cross a power of the alphabet.Source: §V · p. 10
- Mmax(4, 5, 2, 2, 2) = 64 is one of the stated exact maximum code sizes.The section states that the exact sizes are established by matching upper bounds and verified constructions.Source: §V · pp. 10–11
- The q = 3, 4 length-five constructions combine a [3, 2, 2] single-parity-check code with a length-two repetition code, using the component supports as views.A ternary (3, 8, 3, 2, 3) construction is the direct sum of two MDS codes; for (3, 8, 5, 2, 3), every coordinate of a ternary MDS code is repeated twice.Source: §V · p. 11
- Three parameter rows still have a gap between the three-block dimension cap and the dimension of the verified construction.The exact maximum linear dimension is determined for twelve of the fifteen displayed parameter sets.Source: §V · p. 11
VI. CONCLUSION
The conclusion presents a polynomial-size LP for arbitrary q-ary locally recoverable codes, using three-block recovery-view weights and spectral constraints. Certified computations show finite-length improvements, while the relaxation does not retain detailed recovery-view geometry.
VI. CONCLUSION
- The LP retains the three weights for a selected recovery view and combines exact centered identities, recovery constraints, and product-Krawtchouk positivity.It has polynomially many variables in n and r + δ and applies to possibly nonlinear codes.Source: §VI · p. 12
- Certified computations show that preserving the three-block coupling can strictly improve finite-length bounds over q = 2, 3, and 4.Source: §VI · p. 12
- Averaging views of the same length leaves an outer relaxation that omits recovered-coordinate identities, exact supports, and intersections among views.The conclusion names prescribed recovery-set geometry and multiple views for one coordinate as directions for finer models.Source: §VI · p. 12
DATA AND CODE AVAILABILITY
The manuscript's rational certificates, checkers, and construction verifiers are available in a separate reproducibility repository.
DATA AND CODE AVAILABILITY
- Exact rational certificates, optimizer-independent checkers, and construction verifiers for Table V.1 accompany the manuscript in a separate reproducibility repository.Source: DATA AND CODE AVAILABILITY · p. 12