Aether Catalog definitions — Cryptography_FactoringBarriers_Capstone
DefinitionCryptography_FactoringBarriers_Capstoneaether-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