One-way functions ⇔ hardness of approximate compression search.
ProvedCompressionOWF.owf_iff_approx_compression_hardaether-catalogspeculative
One-way functions ⇔ hardness of approximate compression search.
theorem CompressionOWF.owf_iff_approx_compression_hard(C : SearchClosedClass) (δ : ℕ → ℕ) :
(∃ f, OneWayIn C f) ↔
(∃ D, D ∈ C.Comp ∧ HonestIn C D ∧ ∀ A ∈ C.Comp, ¬ ApproxShortestFinder D A δ) := 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 -/
/-! ## Section 6: Robustness of the cryptographic equivalence -/Formal statement
theorem CompressionOWF.owf_iff_approx_compression_hard(C : SearchClosedClass) (δ : ℕ → ℕ) :
(∃ f, OneWayIn C f) ↔
(∃ D, D ∈ C.Comp ∧ HonestIn C D ∧ ∀ A ∈ C.Comp, ¬ ApproxShortestFinder D A δ) := by sorrySource