Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Density of incompressibility.

Proved
CompressionOWF.density_incompressible

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

aether-catalogspeculative

Density of incompressibility. For any decompressor at most a 2^{-(c-1)} fraction of the 2^n strings of length n can be compressed to n - c bits.

theorem CompressionOWF.density_incompressible(D : Str → Str) (n c : ℕ) (hc : 1 ≤ c) (hcn : c ≤ n) :
    2 ^ (c - 1) *
        ((bitStrings n).filter (fun y => Describable D y ∧ K D y ≤ n - c)).card
      ≤ (bitStrings n).card := by sorry

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

Preamble
-- Thm stub generated from Speculative/AutoResearch/CompressionUniversality.lean
import Mathlib
import Definitions.Def_Speculative_AutoResearch_CompressionOneWayFunctions
import Definitions.Def_Speculative_AutoResearch_CompressionUniversality
/-
Copyright (c) 2025. All rights reserved.

# Universal Description Systems, Derandomization, and Robustness of the
# Compression ⇋ One-Way-Function Equivalence

## Overview

This file is the second cycle of the Phase-B/M8 investigation begun in
`Shared.CompressionOneWayFunctions`.  There we proved

* the pigeonhole ceiling and its seeded (randomized) refinement, and
* the equivalence "inverting one-way functions ⇔ solving the
  compression-search (shortest-program) problem".

Here we build the missing structural layer and push the calibration further.

### 1. Self-delimiting codes and universality

`unaryTag`/`parseUnary` and `sdPair`/`parseSD` are prefix-free encodings with
verified parsing lemmas.  They yield:

* `K_univSys_le` — the **invariance theorem** in finitary form: a single
  universal decompressor simulates a whole family at an additive cost equal to
  the length of the index;
* `K_pairSys_le` — **subadditivity**: describing `x ++ y` costs at most
  `2·K x + 1 + K y`.

### 2. Derandomization: buying back randomness at the seed price

`derandomization_cost` shows that a seeded family of decompressors is simulated
by *one* deterministic decompressor at additive cost `2k + 1` for `k`-bit seeds.
Combined with `card_le_of_K_le_seeded` (which says randomness can never buy more
than `log₂|R| + 1` bits) this closes the loop: **the value of randomness for
compression is its seed length, and it is always purchasable deterministically
at that same price, up to a factor two.**

### 3. Most strings are incompressible

`density_incompressible`: for every decompressor, at most a `2^{-(c-1)}`
fraction of the strings of length `n` have complexity `≤ n - c`.

### 4. Robustness of the cryptographic equivalence

`inversion_iff_approx_compression`: the equivalence with inversion survives an
*arbitrary additive slack* `δ` in the compression task.  Finding descriptions
that are merely within `δ(n)` bits of optimal is still exactly as hard as
inverting one-way functions.  Consequently `owf_gap_universal` shows that
switching to a universal description system does not close the gap between
*existing* and *findable* descriptions.

No axioms beyond the standard three, and no `sorry`.
-/

open CompressionOWF

/-! ## Section 1: Self-delimiting codes -/









/-! ## Section 2: Universal decompressors and the invariance theorem -/





/-! ## Section 3: Subadditivity of complexity -/



/-! ## Section 4: Derandomization at the seed price -/




/-! ## Section 5: Most strings are incompressible -/

open scoped Classical in
Formal statement
theorem CompressionOWF.density_incompressible(D : Str → Str) (n c : ℕ) (hc : 1 ≤ c) (hcn : c ≤ n) :
    2 ^ (c - 1) *
        ((bitStrings n).filter (fun y => Describable D y ∧ K D y ≤ n - c)).card
      ≤ (bitStrings n).card := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Speculative/AutoResearch/CompressionUniversality.lean#L184

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