Quantitative form.
ProvedFactoringBarriers.barrier_over_cost_atTopaether-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 sorrySource