Theorem 4.3.5 — Guarantees for an error correcting code (corrected: )
ProvedHighDimProb.RandomMatrices.error_correcting_code_guarantee_v2This is Theorem 4.3.5 of Vershynin's High-Dimensional Probability: the coding-theoretic application of the packing/covering machinery of §4.2, in which covering numbers of the Hamming cube control a concrete combinatorial guarantee.
Assume positive integers with satisfy
Then there exists an error correcting code that encodes -bit strings into -bit strings and can correct errors: maps and such that for every word and every string that differs from in at most bits (Definition 4.3.3, IsErrorCorrectingCode, with the Hamming distance hammingDist).
Formalization Note. The retired version transcribed the printed hypothesis verbatim, which admits — e.g. , where makes the inequality hold — although no code with two codewords can correct errors, so it was disproved. The new statement adds the hypothesis and is otherwise unchanged. This is a correction to the printed source: the book's proof applies Exercise 4.2.16 (covering numbers of the Hamming cube, stated only "for every integer ") and the binomial-sum bound of Exercise 0.0.5 with , so is exactly the range in which the printed proof is valid, and with it the proof goes through verbatim: , then Lemma 4.3.4. (At the hypothesis is unsatisfiable for since , so no degenerate instance remains.) is Real.exp 1, is Real.logb 2, and as in the book's "positive integers".
import Mathlib import Definitions.Def_HighDimProb_RandomMatrices_hammingDist import Definitions.Def_HighDimProb_RandomMatrices_IsErrorCorrectingCode
namespace HighDimProb.RandomMatrices
/-- **Theorem 4.3.5** (Guarantees for an error correcting code), Vershynin, *High-Dimensional
Probability* (2018), p. 88 — **corrected statement**.
Assume that positive integers `k, n, r` with `2r ≤ n` are such that `n ≥ k + 2r log₂(en/(2r))`.
Then there exists an error correcting code that encodes `k`-bit strings into `n`-bit strings and
can correct `r` errors (Definition 4.3.3, `IsErrorCorrectingCode`).
Correction to the printed source: the book states the theorem without the restriction
`2r ≤ n`, but its proof applies Exercise 4.2.16 (and the binomial bound of Exercise 0.0.5)
with `m = 2r`, which are stated only "for every integer `m ∈ [0, n]`". Without `2r ≤ n` the
printed statement is false: for `(k, n, r) = (1, 1, 2)` the hypothesis holds (since
`log₂(e/4) < 0`) but no code with two codewords can correct `r ≥ n/2` errors (the accepted
disproof of the retired version). With `2r ≤ n` the printed proof goes through verbatim:
`P({0,1}ⁿ, d_H, 2r) ≥ N({0,1}ⁿ, d_H, 2r) ≥ 2ⁿ (2r/(en))^{2r} ≥ 2ᵏ`, then Lemma 4.3.4. -/
theorem error_correcting_code_guarantee_v2 (k n r : ℕ) (hk : 0 < k) (hn : 0 < n) (hr : 0 < r)
(hrn : 2 * r ≤ n)
(h : (n : ℝ) ≥ (k : ℝ) + 2 * (r : ℝ) * Real.logb 2 (Real.exp 1 * (n : ℝ) / (2 * (r : ℝ)))) :
∃ E : (Fin k → Bool) → (Fin n → Bool), ∃ D : (Fin n → Bool) → (Fin k → Bool),
IsErrorCorrectingCode (r := r) E D := by sorry
end HighDimProb.RandomMatrices