2^n ≥ 2n for n ≥ 1: exponential query complexity.
ProvedStoneDualityML.exponential_query_boundaether-catalogbridges
2^n ≥ 2n for n ≥ 1: exponential query complexity. Bridge: Cryptography (query complexity) ↔ Information Theory
theorem StoneDualityML.exponential_query_bound(n : ℕ) (hn : 1 ≤ n) : 2 ^ n ≥ 2 * n := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Bridges/StoneDualityMLCore.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Bridges/StoneDualityMLCore.lean import Mathlib import Definitions.Def_Bridges_StoneDualityMLCore /- # Stone Duality for Machine Learning: Boolean Hypothesis Algebras and Topological Online Learnability Certification Bridge: connects Algebra (Boolean algebras, Stone spaces) to Machine Learning (online learnability, Littlestone dimension, mistake bounds) via Topology (Cantor-Bendixson rank, compact zero-dimensional spaces). -/ open Set Function Finset open StoneDualityML /-! ## Section 1: Hypothesis Classes and Growth Functions Bridge: Machine Learning ↔ Combinatorics -/ /-! ## Section 2: Cantor-Bendixson Derivative Theory Bridge: Topology ↔ Descriptive Set Theory -/ /-! ## Section 3: Binary Trees and Shattering Bridge: ML (online learning) ↔ Combinatorics -/ /-! ## Section 4: Cylinder Sets Bridge: Algebra ↔ Topology ↔ ML -/ /-! ## Section 5: Hamming Metric Bridge: Analysis ↔ ML (certified robustness) -/ /-! ## Section 6: Exponential Bounds Bridge: ML ↔ Cryptography ↔ Information Theory -/
Formal statement
theorem StoneDualityML.exponential_query_bound(n : ℕ) (hn : 1 ≤ n) : 2 ^ n ≥ 2 * n := by sorry
Source