Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Cryptography_FactoringBarriers_Capstone

Definition
Cryptography_FactoringBarriers_Capstone

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

aether-catalogcryptography

Definition bundle for the Aether Catalog module Cryptography.FactoringBarriers.Capstone, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from Cryptography/FactoringBarriers/Capstone.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Cryptography_FactoringBarriers_AsymptoticLadder
import Definitions.Def_Cryptography_FactoringBarriers_CongruenceOfSquares
import Definitions.Def_Cryptography_FactoringBarriers_DFTSampleBound
import Definitions.Def_Cryptography_FactoringBarriers_ResourceClassification

/-!
# Capstone: A Conditional-Impossibility Schema for Classical Factoring

This file assembles the framework and — crucially — keeps its three logical
levels apart.

**Level 1 (unconditional theorems).**
* `barrierCost_superpoly` (imported): each of the four classified barriers is
  superpolynomial in `log N`.
* `congruence_of_squares` (imported): the structural core reduction is
  unconditional.
* `dft_sample_count_ge_period` (imported): the Fourier sample bound `K ≥ r` is
  information-theoretic and unconditional.
* `tradeoff_lower_bound` and `arithmetic_trajectory_blind` (in
  `TradeoffBarrier.lean` and `RandomnessBarrier.lean`): the sieve exponent `1/k`
  is forced by AM–GM, and collision-based methods are provably blind for
  `min p q` steps in the worst case.

**Level 2 (conditional impossibility — proved here).**
`conditional_impossibility`: *if* a classical algorithm factors in
`poly(log N)`, *then* its cost is not bounded below by any classified barrier;
equivalently, the resource it exploits is outside the classified set
`{randomness, smoothness, iteration, analog}`.  This is a logical consequence of
the classification, **not** an unconditional lower bound on factoring.

**Level 3 (scope — a definition, not a theorem).**
`ClassifiedResourceHypothesis`: the assertion that every classical algorithm is
limited by one of the four classified barriers.  We *do not* prove it — it is a
statement about the unknown.  What we do prove is `no_poly_under_CRH`: it
implies no polynomial-time classical factoring algorithm exists, and
`CRH_falsified_by_poly`: any polynomial-time algorithm falsifies it.  The
framework is therefore a genuine classification of the known plus an honest
conditional, never a proof that the unknown is empty.
-/

namespace FactoringBarriers

open Filter Real
open scoped Topology

/-! ## Abstract classical algorithms -/

/-- A classical factoring algorithm, abstracted to its running-time profile
`cost x` as a function of the bit-size parameter `x = log N`. -/
structure ClassicalAlgorithm where
  /-- Running time as a function of `x = log N`. -/
  cost : ℝ → ℝ
  /-- Any algorithm performs at least one step. -/
  one_le_cost : ∀ᶠ x in atTop, 1 ≤ cost x

/-- `A` runs in polynomial time in the bit-size. -/
def PolyTime (A : ClassicalAlgorithm) : Prop := PolyBounded A.cost

/-- `A` is *limited by* the classified resource `rho`: its cost is eventually at
least the barrier documented for `rho`. -/
def LimitedBy (A : ClassicalAlgorithm) (rho : ClassicalResource) : Prop :=
  ∀ᶠ x in atTop, barrierCost rho x ≤ A.cost x

/-- The algorithm's resource lies inside the classified set. -/
def UsesClassifiedResource (A : ClassicalAlgorithm) : Prop :=
  ∃ rho : ClassicalResource, LimitedBy A rho

/-! ## Positivity of the barriers -/


/-! ## Level 2: the conditional-impossibility chain -/






/-! ## Level 3: the scope of the framework, stated honestly -/

/-- The **Classified Resource Hypothesis**: every classical factoring algorithm
is limited by one of the four classified barriers.  This is a hypothesis about
the *unknown*; the framework does not prove it, and the capstone theorems below
are explicitly conditional on it. -/
def ClassifiedResourceHypothesis : Prop :=
  ∀ A : ClassicalAlgorithm, UsesClassifiedResource A



/-! ## The schema is not vacuous

Both sides of the conditional are inhabited, so neither `PolyTime` nor
`UsesClassifiedResource` is an empty predicate and the implication has content. -/

/-- The abstract algorithm whose cost profile *is* the barrier for `rho`. -/
noncomputable def barrierAlgorithm (rho : ClassicalResource) : ClassicalAlgorithm where
  cost := barrierCost rho
  one_le_cost := by
    filter_upwards [(barrierCost_superpoly rho 0).eventually (eventually_ge_atTop (1:ℝ)),
      eventually_gt_atTop (0:ℝ)] with x hx hx0
    simpa [Real.rpow_zero] using hx

/-- A polynomial cost profile, e.g. `x ↦ x²`. -/
noncomputable def quadraticAlgorithm : ClassicalAlgorithm where
  cost := fun x => x ^ (2 : ℝ)
  one_le_cost := by
    filter_upwards [eventually_ge_atTop (1:ℝ)] with x hx
    exact Real.one_le_rpow hx (by norm_num)





/-! ## The capstone statement -/


/-! ## Where the quantum resource sits

The framework does not classify quantum resources, and indeed the two
unconditional facts we proved about the quantum route point in the opposite
direction: the structural reduction `order_finding_yields_factor` is free, and
the only information-theoretic obstruction we could establish for Fourier
sampling, `dft_sample_count_ge_period`, is a bound on the number of *samples*
(`K ≥ r`), which superposition supplies in one shot.  We record the combination
as a single statement to make the boundary of the framework explicit. -/


end FactoringBarriers

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