Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Universe–gap domains and two operational reductions

Definition
NearLogSetCover966_Main_Supplement_Tradeoff

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover

The amplification domain records the polynomial lower relation between u0u_0u0​ and ρ\rhoρ, the exact two upper bounds for γ\gammaγ, and the trivial small-universe cases. The tradeoff domain is

1≤γ≤min⁡{log⁡2ulog⁡2log⁡2n,log⁡2uk2log⁡2log⁡2u},u≤n.1\le\gamma\le\min\left\{\frac{\log_2u}{\log_2\log_2n},\frac{\log_2u}{k^2\log_2\log_2u}\right\},\qquad u\le n.1≤γ≤min{log2​log2​nlog2​u​,k2log2​log2​ulog2​u​},u≤n.

The equivalence predicate requires one forward many-one randomized program and one reverse adaptive exact-oracle program. It records all instance, gap, parameter, universe, time, call-count and success clauses of Corollary 4.10. Its constants are uniform over instances. Reverse queries use r=⌊γ⌋r=\lfloor\gamma\rfloorr=⌊γ⌋, parameters at most kkk and universe at most Cu4/γCu^{4/\gamma}Cu4/γ; forward parameters are at most 17k17k17k. It is a predicate to be proved, never a certificate bundled into machine data.

Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Promises

set_option autoImplicit false

namespace NearLogSetCover966.Main.Supplement

noncomputable def amplifyInput (I : SCInstance) (k : ℕ) (γ : ℝ) : Str :=
  coverInput I k ++ thresholdCode (γ * (17*k : ℕ))

/-- The u₀=0,1 branches do not divide by log u₀. The lower polynomial growth
has a single absolute coefficient/exponent, before all inputs. -/
noncomputable def AmplificationDomain (α : ℝ) (a : ℕ) (I : SCInstance)
    (k : ℕ) (ρ γ : ℝ) : Prop :=
  1 ≤ k ∧ 1 ≤ I.sets.length ∧ I.n ≤ I.sets.length ∧
  (I.n : ℝ)^a ≤ ρ ∧ 2 < ρ ∧ ρ ≤ I.sets.length ∧
  1 ≤ γ ∧ (I.n ≤ 1 ∨ γ ≤ α * log2 ρ / log2 I.n) ∧
  γ ≤ α * log2 ρ / ((k : ℝ)^2 * log2 (log2 ρ))

/-- The instance is first, the round count second and the cover budget last.
For k>n the algorithm can stop reading its unary tail after n bits and use min(k,n).
This retains arbitrary positive budgets while keeping polynomial overhead in n. -/
def sampleInput (I : SCInstance) (k r : ℕ) : Str := frame (scEncode I) ++ unary r ++ unary k

noncomputable def TradeoffDomain (n u k : ℕ) (γ : ℝ) : Prop :=
  1 ≤ k ∧ 2 < n ∧ 2 < u ∧ u ≤ n ∧ 1 ≤ γ ∧
    γ ≤ log2 u / log2 (log2 n) ∧
    γ ≤ log2 u / ((k : ℝ)^2 * log2 (log2 u))

noncomputable def forwardInput (I : SCInstance) (k u : ℕ) (γ : ℝ) : Str :=
  coverInput I k ++ unary u ++ thresholdCode (γ * (17*k : ℕ))

/-- Both directions of the universe–gap equivalence, with their allowed constant
rescalings and computable parameter bounds. This is a property, never algorithm data.
The forward reduction is many-one; the reverse is adaptive and uses the exact oracle.
The gap floor at 1 handles bounded γ by an exact identity branch. -/
noncomputable def UniverseGapEquivalence (a C : ℝ) (e : ℕ)
    (P : RandomProgram) (R : OracleProgram) : Prop :=
  0 < a ∧ 0 < C ∧
  (∀ n u k : ℕ, ∀ γ : ℝ, TradeoffDomain n u k γ →
    ∀ I : SCInstance, I.sets.length = n → (I.n : ℝ) ≤ (u : ℝ)^(1/γ) →
      let x := forwardInput I k u γ
      let B := C * (n+1 : ℝ)^e
      P.halts x B ∧
      (∀ ω, ∃ J K, P.output x B ω = coverInput J K ∧ 1 ≤ K ∧ K ≤ 17*k ∧
        J.sets.length ≤ 34*k*n ∧ J.n ≤ u ∧
        (coverSmall I k → coverSmall J K)) ∧
      (coverLarge I k → P.prob x B (fun y => ∃ J K, y = coverInput J K ∧
        coverLarge J (max 1 (a*γ) * K)) ≥ 2/3)) ∧
  (∀ n u k : ℕ, ∀ γ : ℝ, TradeoffDomain n u k γ →
    ∀ I : SCInstance, I.sets.length = n → I.n ≤ u →
      let x := sampleInput I k ⌊γ⌋₊
      let B := C * (n+1 : ℝ)^e
      let Q := C * γ * n
      R.bounded x B Q (queryBound n (C * (u : ℝ)^(4/γ)) k) ∧
      (coverSmall I k → ∀ ω, R.output x B Q ω = [true]) ∧
      (coverLarge I (γ*k) → R.prob x B Q (· = [false]) ≥ 2/3))

end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorems 4.7, 4.9 and Corollary 4.10, printed pp.20–23 (PDF pp.22–25)

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