Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Quantitative form.

Proved
FactoringBarriers.barrier_over_cost_atTop

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

aether-catalogcryptography

Quantitative form. For a polynomial-time algorithm the gap to every classified barrier is not merely positive but unbounded: the barrier exceeds the cost by an arbitrarily large factor.

theorem FactoringBarriers.barrier_over_cost_atTop{A : ClassicalAlgorithm} (h : PolyTime A)
    (rho : ClassicalResource) :
    Tendsto (fun x => barrierCost rho x / A.cost x) atTop atTop := by sorry

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

Preamble
-- Thm stub generated from Cryptography/FactoringBarriers/Capstone.lean
import Mathlib
import Definitions.Def_Cryptography_FactoringBarriers_Capstone
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.
-/

open FactoringBarriers

open Filter Real
open scoped Topology

/-! ## Abstract classical algorithms -/





/-! ## Positivity of the barriers -/


/-! ## Level 2: the conditional-impossibility chain -/
Formal statement
theorem FactoringBarriers.barrier_over_cost_atTop{A : ClassicalAlgorithm} (h : PolyTime A)
    (rho : ClassicalResource) :
    Tendsto (fun x => barrierCost rho x / A.cost x) atTop atTop := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Cryptography/FactoringBarriers/Capstone.lean#L113

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