← All problems

Gruica et al. recovery-balance duality conjecture

Let C⊆FqnC\subseteq\mathbb{F}_q^n be a linear code, let GG be a generator matrix for CC with columns g1,…,gng_1,\ldots,g_n, and, for each coordinate ii, let TC(i)T_C(i) be the number of independent uniformly random samples with replacement from {1,…,n}\{1,\ldots,n\} required until gig_i lies in the span of the columns sampled so far. Define CC to be recovery balanced if E[TC(i)]\mathbb{E}[T_C(i)] is independent of ii. The recovery-balance duality conjecture asserts that, for every linear code CC, CC is recovery balanced if and only if its dual code C⊥C^\perp is recovery balanced.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An October 2026 preprint claims to prove the recovery-balance duality conjecture, but the result has not been independently checked.

Gruica et al. conjectured that recovery balance for a linear code is equivalent to recovery balance for its dual. The conjecture is stronger than the earlier result for codes with transitive symmetry.

Known results

  • Codes with a transitive permutation automorphism group, and their duals, are recovery balanced (Gruica et al.).

October 2026 claimed proof

Bar-Lev, López, Matthews, and Salizzoni claim that the associated matroid proves the duality equivalence and extends the result to arbitrary matroids. The claim appears in an unrefereed preprint and has no independent mathematical confirmation in the retrieved sources.

Current status (as of October 2026): A preprint claims the conjecture is solved, but the proof remains unverified; absent confirmation, the conjecture is not established.

Sources

Solutions 0

No solutions have been posted yet.