PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotically unit-rate storage codes from binary BCH codes

Aryeh Lev Zabokritskiy

arXiv:2610.01733v1cs.ITmath.COmath.IT

TL;DR

Triangle-free graphs exclude the complete-graph single-parity-check construction that supports rates tending to one, motivating the search for high-rate storage codes on these graphs. A polynomial-map convolution-rank bound uses low Boolean coordinate degree to force coefficient cancellation, then applies a polynomial rank bound. The estimate gives storage rate tending to one when s ≥ 2 and s(log(s + 1))² = o(m); for the double-error-correcting family, the storage deficiency’s exponential order is determined.

  • Problem

    Triangle-free graphs exclude the complete-graph single-parity-check construction that supports rates tending to one, motivating the search for high-rate storage codes on these graphs.

    Source: §1 · p. 1

  • Method

    A polynomial-map convolution-rank bound uses low Boolean coordinate degree to force coefficient cancellation, then applies a polynomial rank bound.

    Source: §1 · p. 2

  • Results

    The estimate gives storage rate tending to one when s ≥ 2 and s(log(s + 1))² = o(m); for the double-error-correcting family, the storage deficiency’s exponential order is determined.

    Source: §1 · p. 1, §7 · p. 10

  • Takeaways & Limitations

    The BCH rank bound applies to other parametrized connection sets when their Boolean coordinate degree and syndrome-space dimension are controlled.

    Source: §7 · p. 10

    The largest BCH error-budget growth range yielding asymptotically unit rate remains open, and quadratic Reed–Muller evaluation requires a stronger rank argument.

    Source: §7 · p. 10

Abstract

from arXiv · show

A storage code on a graph assigns a symbol to each vertex so that the symbol can be recovered from its neighbors. We prove that the binary full-parity storage codes on triangle-free coset graphs of primitive BCH codes have rate tending to one for every fixed error-correction capability of at least two. The conclusion also holds for an increasing error budget under an explicit growth condition. The proof bounds the binary rank of convolution matrices associated with polynomial maps. Low coordinate degree forces cancellation in the polynomial representing the image, and a polynomial rank bound converts this cancellation into a quantitative estimate for the storage rate. For the double-error-correcting family over $\mathbb{F}_{2^m}$, we prove that the storage deficiency is $\Theta(((1+\sqrt{5})/4)^m)$. This refinement follows from an exact Fibonacci formula for a polynomial coefficient rank and a matching exponential lower bound after finite-field evaluation.

1. Introduction

Triangle-free graphs rule out the complete-graph single-parity-check route to rates tending to one, motivating the study of BCH coset graphs. The paper proves asymptotically unit rate for fixed BCH error-correction capability and extends the conclusion to a specified growing-error regime.

1. Introduction

  • Triangle-free coset graphs pose a different rate question because the complete-graph single-parity-check construction yielding rates tending to one is unavailable.The graph determines recovery sets, and the rate is the optimization objective.Source: §1 · p. 1
  • Earlier work established asymptotically unit-rate binary storage codes on triangle-free graphs, including the double-error-correcting BCH family; BCH codes were identified as a source of further examples.Relevant works include Golovnev and Haviv, Barg, Schwartz, and Yohananov, Huang and Xiang, and Deng, Huang, Weng, and Xiang.Source: §1 · p. 1
  • The coset graph defined using a BCH code supports a full-parity storage code with rate tending to one for every fixed s ≥ 2.The same estimate proves convergence to one whenever s = s(m) ≥ 2 and s(log(s + 1))² = o(m); s is the error-correction capability of the BCH code used to define the graph.Source: §1 · p. 1
  • The proof bounds convolution-matrix rank using Boolean coordinate degree: low degree forces high-degree coefficients in the fibre-parity polynomial to vanish, then a polynomial rank bound completes the estimate.The rank argument is due to Croot, Lev, and Pach. For fixed s, the syndrome dimension is at most sm, versus target dimension m(m + 1)/2 for the nonconstant quadratic evaluation map.Source: §1 · p. 2
  • For the double-error-correcting family, the storage deficiency has exponential order determined by an exact Fibonacci formula for coefficient rank and matching bounds after finite-field evaluation.This sharpens the earlier rank estimate in.Source: §1 · p. 2
  • The quadratic Reed–Muller rates left open by Barg and Zémor [2] are not resolved; the paper instead relates their unit-rate question to symmetric-matrix rank and cut–cycle-space intersections.The paper presents these reformulations as routes for transferring rank and dimension estimates to storage-rate bounds.Source: §1 · p. 2

2. Storage codes and polynomial maps

The section defines the binary full-parity storage code and relates its rate to the rank of a matrix indexed by a graph. For Cayley graphs, a map parametrizes the connection set, and the resulting matrix records parity of preimage counts.

2. Storage codes and polynomial maps

  • The storage rate is determined by the binary matrix indexed by the Cayley-graph vertices, allowing rank estimates without computing the original BCH code's dimension.For injective h with h(0)=0, this matrix is I + A(G); for a general map, its entries record parity of the number of preimages of x+y.Source: §2 · pp. 2–3
  • In the full-parity code, each coordinate is recovered by its parity check from neighboring coordinates, and the rate of this code is determined by that construction's matrix rank.The identity matrix supplies the symbol being recovered in the construction of [2, author version, Section 3].Source: §2 · p. 2
  • A Cayley graph on a binary vector space connects distinct x and y when x+y belongs to the connection set; a spanning set makes the graph connected.The syndrome map identifies the graph with the coset graph of ker H, with im H as its vertex space.Source: §2 · pp. 2–3
  • A coordinate-degree bound on h survives binary linear changes of target coordinates, so redundant target dimensions can be replaced by the span of the image without changing normalized rank or storage rate.Keeping the larger ambient space instead yields identical components on the cosets of that span.Source: §2 · p. 3

3. A rank bound for polynomial maps

The section bounds the rank of convolution matrices using Boolean coordinate degree, then applies that bound to storage-rate conclusions. Its proof encodes fibre parity as a low-degree polynomial and separates monomials to control matrix rank.

3. A rank bound for polynomial maps

  • Low coordinate degrees force the polynomial recording fibre parity to have degree at most D − k, and it vanishes when k > D.The proof bounds each coefficient by summing a Boolean polynomial over the input space; terms of degree below m sum to zero.Source: §3 · pp. 3–4
  • Splitting monomials of F(x + y) by their x- or y-monomials expresses the matrix as a sum of rank-one matrices, so rank subadditivity bounds its rank.The split groups monomials using the degree constraint |A| + |B| ≤ D − k.Source: §3 · pp. 3–4
  • The exponential rank estimate follows by bounding a binomial tail with the exponential Markov inequality and log cosh w ≤ w^2/2.The cited derivation takes t = 2k/D.Source: §3 · p. 4
  • Injective maps that send zero to zero yield full-parity storage rates tending to one when the normalized convolution-matrix rank tends to zero.The section also gives an endpoint case: when k = D, the rank is at most one, attained by h(a) = a.Source: §3 · p. 4

4. BCH coset graphs

Primitive binary BCH coset graphs give triangle-free full-parity storage codes whose rate tends to one for fixed error budgets of at least two. The same conclusion holds for a growing error budget under the stated growth condition.

4. BCH coset graphs

  • For fixed s, the syndrome-space dimension grows at most linearly with m, allowing the rank estimate to yield asymptotically unit storage rate.The proof also ensures the BCH parameter constraint for sufficiently large m under the stated growth condition.Source: §4 · pp. 4–5
  • The parity-check matrix with columns h_s(a) for nonzero a has kernel equal to the primitive narrow-sense binary BCH code of designed distance 2s + 1.The odd power checks imply all power checks with exponents 1 through 2s.Source: §4 · p. 5
  • For every fixed s ≥ 2, the triangle-free graph G_m,s supports a full-parity storage code with rate tending to one; this also holds when s(log(s + 1))^2 = o(m).The graph is triangle-free for 2s + 1 ≤ 2^m − 1.Source: §4 · p. 5
  • The BCH power map has binary coordinate degrees at most wt2(e) for a power a^e, enabling the polynomial-map rank estimate to apply in binary coordinates.For the odd power checks, the maximum degree is determined by the largest binary weight among exponents through 2s − 1.Source: §4 · p. 5
  • For s = 3, the power map is (a, a^3, a^5), has coordinate degrees at most two, and the general estimate applies.The s = 2 construction is the BCH family treated in.Source: §4 · p. 6

5. Fibonacci ranks for the double-error-correcting family

For the double-error-correcting family, the paper computes an exact Fibonacci recurrence for polynomial coefficient rank and bounds the rank after finite-field evaluation. Together these yield the exponential order of the storage deficiency.

5. Fibonacci ranks for the double-error-correcting family

  • For the Gold function a ↦ a^3, the matrix I + A_m is the incidence matrix defining its Γ-rank, so the bounds also determine that invariant’s exponential order.The Γ-rank is the binary incidence rank of points and translates of the function’s graph; small-dimensional values were previously tabulated in [5].Source: §5 · p. 6
  • The graph matrix I + A_m is permutation equivalent to evaluation of 1 + P_m after bijective row and column substitutions.The substitutions are u = b + x^3 and v = c + y^3.Source: §5 · p. 6
  • The coefficient-matrix ranks satisfy r_0 = 1, r_1 = 4, and r_m+1 = 2r_m + 4r_m−1.The recurrence follows from the coefficient-space intersection analysis; its solution gives the Fibonacci formula in (11).Source: §5 · pp. 6–7
  • The recurrence is derived by tracking the intersection of the coefficient image U_m with its translate xU_m.The intersection identity yields the dimension recurrence used to compute the coefficient ranks.Source: §5 · p. 7
  • Finite-field evaluation can identify distinct monomials, so coefficient rank alone does not determine storage-matrix rank; the paper proves a separate evaluation bound.A block decomposition gives a lower bound of twice the preceding coefficient rank, and evaluation preserves rank for the reduced coefficient matrix.Source: §5 · pp. 7–8
  • The storage deficiency is Θ(((1 + √5)/4)^m), with exponential order established by matching bounds on the evaluated storage-matrix rank.In terms of ambient graph order N = q^2, the deficiency is Θ(N^−ε/2), where ε = log2(2/φ) = 0.3057580863….Source: §5 · pp. 8–9

6. Quadratic evaluation and symmetric matrices

The section recasts the open unit-rate question for the quadratic Reed–Muller construction as a binary-rank problem on symmetric binary matrices. It also gives a cut-and-cycle-space formulation and a lower bound on the storage rate.

6. Quadratic evaluation and symmetric matrices

  • Whether the quadratic Reed–Muller storage rate tends to one remains open, and the BCH argument does not establish convergence for this family.Its target dimension is quadratic rather than linear in the input dimension.Source: §6 · pp. 9–10
  • The quadratic evaluation coordinates can be assembled into symmetric matrices, identifying the construction’s Cayley graph with the rank-one graph on those matrices.The evaluation coordinates are the nonconstant squarefree monomials of degree at most two.Source: §6 · p. 9
  • For the quadratic family, this method yields a storage rate of at least 0.5204998778 . . . −o(1), as stated after the central limit theorem gives (20).Source: §6 · p. 10
  • The rank condition concerns dependencies among indicator-matrix rows; counts of symmetric matrices by rank alone do not determine that binary rank.The rank of S+T is taken on m × m matrices, while the indicator matrix is indexed by all symmetric matrices.Source: §6 · p. 10
  • The binary-rank question is equivalently whether the graph’s bicycle space has dimension N−o(N); the stated theorem gives this conclusion for the BCH graphs in its parameter range.The bicycle space is the intersection of the graph’s cut and cycle spaces.Source: §6 · p. 10

7. Conclusions

The conclusions establish asymptotically unit rate for primitive binary BCH full-parity storage codes at every fixed error budget of at least two, and determine the deficiency’s exponential order for the double-error-correcting family. They also identify open questions about the largest growing error budget and the quadratic Reed–Muller family.

7. Conclusions

  • Primitive binary BCH full-parity storage codes have asymptotically unit rate for every fixed error budget of at least two.The same bound permits a growing error budget and applies to other parametrized connection sets when Boolean coordinate degree and syndrome-space dimension are controlled.Source: §7 · p. 10
  • For the double-error-correcting family, an exact Fibonacci rank formula and a finite-field lower bound determine the exponential order of storage deficiency.This refines the qualitative unit-rate conclusion for that family.Source: §7 · p. 10
  • The largest growth range for the BCH error budget remains open, and the quadratic Reed–Muller question needs a stronger rank argument.The Reed–Muller target dimension is quadratic in the input dimension.Source: §7 · p. 10

Declarations

Loading 2610.01733v1…