A proof confirms a key inequality in error-correcting codes
A proof of the generalized packing-covering conjecture
Information Theory
Summary
There was a mathematical conjecture about certain properties of error-correcting codes, which are ways to protect information during transmission. The conjecture suggested a relationship between two measures related to how well these codes can detect and cover errors. The authors proved this conjecture for every possible code and order using a combination of mathematical tools and extensive computer checks. This settles a longstanding question in coding theory, ensuring the stated inequality always holds.
What this means in practice
- •For coding system designers: Design codes with guaranteed bounds on weight and coverage properties, improving error detection and correction reliability.
- •For data storage engineers: Use proven bounds to optimize redundancy schemes ensuring efficient use of storage while maintaining error protection.
A theory result. No direct application yet.
Authors
Gianira N. Alfarano, Giuseppe Marino, Alessandro Neri, Rocco Trombetti
Abstract
The generalized packing--covering conjecture of Elimelech, Firer and Schwartz asserts that, for every linear code $\mathcal{C}$ and every admissible order $t$, the $t$-th generalized Hamming weight $d_t(\mathcal{C})$ and the $t$-th generalized covering radius $R_t(\mathcal{C})$ satisfy $d_t(\mathcal{C})\le 2R_t(\mathcal{C})+2$. We give a computer-assisted proof of the conjecture for every linear code over every finite field and every admissible order. Combining a parity-check reformulation of the conjecture, bounds on the length of putative counterexamples, and successive puncturing arguments, we settle all orders $t\ge 32$ and reduce the remaining orders to finitely many parameter tuples, which we exclude by an exact computer verification.