The `ε`-compression barrier.
ProvedScanSchemeDecoding.ScanScheme.mean_decodeCost_ge_inv_two_mulaether-catalogalgebra
The ε-compression barrier. If the index is compressed to m ≤ ε · N buckets
then the mean decoding cost is at least 1 / (2ε): buying a factor ε of space costs a
factor 1/ε of time, with the exact constant 1/2.
theorem ScanSchemeDecoding.ScanScheme.mean_decodeCost_ge_inv_two_mul(eps : ℝ) (heps : 0 < eps)
(hα : 0 < Fintype.card α) (hβ : 0 < Fintype.card β)
(hcomp : (Fintype.card β : ℝ) ≤ eps * (Fintype.card α : ℝ)) :
1 / (2 * eps) ≤ (∑ x, S.decodeCost x : ℝ) / (Fintype.card α : ℝ) := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Algebra/ScanSchemeDecoding/Epsilon.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Algebra/ScanSchemeDecoding/Epsilon.lean
import Mathlib
import Definitions.Def_Algebra_ScanSchemeDecoding_Core
/-!
# The `ε`-compression barrier for scan indices
The exact pigeonhole optimum of `Algebra.ScanSchemeDecoding.Triangle` is stated with the
*floor* `⌊N/m⌋`. Here we sharpen it to a statement with genuine (real) division, which
is the form in which a space/time trade-off is usually quoted:
`N * (N + m) ≤ 2 * m * triangleOpt N m` (`triangleOpt_mul_ge`, an exact `ℕ` statement),
and deduce the analytic corollaries
* `mean_decodeCost_ge` — the mean decoding cost of any scan scheme is at least
`(N/m + 1)/2`;
* `mean_decodeCost_ge_inv_two_mul` — the **`ε`-compression barrier**: a scheme whose
index uses only `m ≤ ε · N` buckets has mean decoding cost at least `1/(2ε)`.
Both are sharp: for `m ∣ N` the residue scheme of `Algebra.ScanSchemeDecoding.Optimum`
meets the first bound with equality (`mean_decodeCost_modScheme_eq` for `m ∣ N`).
-/
open ScanSchemeDecoding
open Finset
open ScanScheme
variable {α β : Type*} [Fintype α] [LinearOrder α] [Fintype β] [DecidableEq β]
variable (S : ScanScheme α β)Formal statement
theorem ScanSchemeDecoding.ScanScheme.mean_decodeCost_ge_inv_two_mul(eps : ℝ) (heps : 0 < eps)
(hα : 0 < Fintype.card α) (hβ : 0 < Fintype.card β)
(hcomp : (Fintype.card β : ℝ) ≤ eps * (Fintype.card α : ℝ)) :
1 / (2 * eps) ≤ (∑ x, S.decodeCost x : ℝ) / (Fintype.card α : ℝ) := by sorrySource