Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two-sided derandomization.

Proved
AlmostLossless.exists_doubly_good_key

by raver1975 · Sep 10, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogbridges

Two-sided derandomization. There is a single key that is simultaneously good on the complement of the codebook (the only region where a silent error can occur) and on the whole space: the two bad-key sets each have size < K/2, so together they cannot exhaust the key space.

theorem AlmostLossless.exists_doubly_good_key(μ : FinProbDist α) {H : Fin K → α → Fin M}
    (hU : Universal2 H) (hK : 0 < K) (S : Finset α) :
    ∃ k : Fin K,
      (M : ℝ) * setMass μ ((Sᶜ).filter (fun x => Collides H k S x))
          ≤ 2 * (S.card : ℝ) * setMass μ Sᶜ
      ∧ (M : ℝ) * setMass μ (Finset.univ.filter (fun x => Collides H k S x))
          ≤ 2 * (S.card : ℝ) := by sorry

Formalization Note Transplanted verbatim from the Aether Catalog source Bridges/AlmostLosslessSharpSilent.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.

Preamble
-- Thm stub generated from Bridges/AlmostLosslessSharpSilent.lean
import Mathlib
import Definitions.Def_Bridges_AlmostLosslessCompression
import Definitions.Def_Bridges_AlmostLosslessRandomCoding
import Definitions.Def_Bridges_AlmostLosslessSharpSilent
import Definitions.Def_Bridges_MinEntropy
/-
Copyright (c) 2025 Non-Archimedean Information Theory Project. All rights reserved.

# Almost-Lossless Compression VII: Silent Corruption is Rarer than Failure

## Bridge: Universal hashing (algebra) ↔ two-sided Markov counting (probability)

`exists_almost_lossless_scheme` produces a key whose *failure* probability is at
most `δ + |S|/M` and whose *silent corruption* probability is at most `|S|/M`.
That silent bound is wasteful: a silent error requires a symbol to be **outside**
the codebook (inside the codebook the decoder provably abstains rather than
lying) *and* to collide with the codebook.  The first event has probability at
most `δ`, so the first moment of the silent-error mass carries an extra factor
`δ`.

This file proves that the two guarantees can be obtained **simultaneously for a
single key**:

* `card_badMass_lt` — a Markov/counting bound: fewer than half of the keys are
  twice as bad as the average, for any region `A`;
* `exists_doubly_good_key` — a key that is good for the region `Sᶜ` *and* for
  the whole space at once (both bad sets have size `< K/2`, so they cannot
  cover the key space);
* `exists_sharp_almost_lossless_scheme` — **the deliverable**: a single explicit
  key with failure probability `≤ δ + 2|S|/M`, silent-corruption probability
  `≤ 2δ|S|/M` (a factor `δ` better), and decoding cost still exactly `|S|`.

This settles Conjecture 2 of the previous cycle's `FUTURE_DIRECTIONS.md`.

## Impact: sharp_silent_error_bound, two_sided_derandomization
-/


open Finset BigOperators NonArchInfoTheory

open AlmostLossless


variable {α : Type*} [Fintype α] [DecidableEq α] {K M : ℕ}
Formal statement
theorem AlmostLossless.exists_doubly_good_key(μ : FinProbDist α) {H : Fin K → α → Fin M}
    (hU : Universal2 H) (hK : 0 < K) (S : Finset α) :
    ∃ k : Fin K,
      (M : ℝ) * setMass μ ((Sᶜ).filter (fun x => Collides H k S x))
          ≤ 2 * (S.card : ℝ) * setMass μ Sᶜ
      ∧ (M : ℝ) * setMass μ (Finset.univ.filter (fun x => Collides H k S x))
          ≤ 2 * (S.card : ℝ) := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Bridges/AlmostLosslessSharpSilent.lean#L104

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me