A linear code over a finite field with elements is a linear subspace . The vectors in this subspace are called codewords. A linear error-correcting code uses a large minimum Hamming distance between distinct codewords to permit recovery from errors by choosing a nearest codeword.

The dual code consists of the vectors orthogonal to every codeword of . In a random-access model, encoded coordinates are read independently and uniformly with replacement. A coordinate is recoverable once its value is determined by the observed coordinates for every codeword consistent with those observations. Let be the expectation value of the number of reads needed to recover coordinate . A coordinate that is identically zero is known without any reads, so its recovery time is zero. The linear code is called recovery balanced when is independent of (Gruica et al. 2025).

MathIsEvenEasier (2026) reported the identity

where is the length of the linear code. It implies that is recovery balanced iff its dual code is recovery balanced, answering Conjecture 1 of Gruica et al. (2025). For a self-dual linear code, every would equal . Nonuniform sampling is outside the identity; requiring at least one read even for an identically zero coordinate changes its right-hand side. GPT-6 Astra developed the proof and Lean formalization under human direction. As of Oct. 7, 2026, a public continuous-integration run had compiled all 13 positive modules, rejected two false controls, and reported only standard Lean axioms for the final theorem, but independent specialist review had not been reported (VibeMathed 2026).

A locally correctable code allows a randomized algorithm to recover a requested coordinate of a corrupted codeword from a bounded number of queries (Dvir 2016).

See also

Code, Coding Theory, Dual Code, Error-Correcting Code, Gray Code, Huffman Coding, ISBN, Maximum Distance Separable Code, MDS Conjecture, Singleton Bound, UPC

Explore with Wolfram|Alpha

References

Dvir, Z. "Locally Correctable Codes." Lecture 8 in Linear Locally Decodable Codes. 2016. https://www.cs.princeton.edu/~zdvir/LDCnotes/LDC8.pdf.Gruica, A.; Bar-Lev, D.; Ravagnani, A.; and Yaakobi, E. "A Combinatorial Perspective on Random Access Efficiency for DNA Storage." IEEE Trans. Inform. Th. 71, 9395-9412, 2025. https://doi.org/10.1109/TIT.2025.3623202.MathIsEvenEasier. "Coordinatewise Duality for Random-Access Recovery Times." Oct. 4, 2026. https://github.com/MathIsEvenEasier/dna-recovery-duality/blob/main/recovery-duality.tex.VibeMathed. "Recovery Balance Is Preserved by Duality." Oct. 4, 2026. https://vibemathed.com/problem/recovery-balance-is-preserved-by-duality.

Referenced on Wolfram|Alpha

Linear Code

Cite this as:

Weisstein, Eric W. "Linear Code." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LinearCode.html

Subject classifications