SGL polynomial-bound closure lemmas
Definitionsgl_polynomial_closurescomplexity-theorypolynomial-timesipser-gacs-lautemann
This auxiliary module packages elementary closure properties of the mission predicate PolynomiallyBounded. It proves that constant functions, the identity function, sums, products, multiplication by a constant, successors, and fixed powers of polynomially bounded functions are again polynomially bounded.
These lemmas are reusable bookkeeping for polynomial-time simulations in the Sipser--Gacs--Lautemann mission, where machine runtimes are assembled from scan, reset, and delegated-verifier phases.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Tactic
namespace SipserGacsLautemann
theorem PolynomiallyBounded.const (constant : Nat) :
PolynomiallyBounded (fun _ : Nat => constant) := by
refine ⟨constant, 0, ?_⟩
intro n
simp
theorem PolynomiallyBounded.id :
PolynomiallyBounded (fun n : Nat => n) := by
refine ⟨1, 1, ?_⟩
intro n
simp
theorem PolynomiallyBounded.add {f g : Nat → Nat}
(hf : PolynomiallyBounded f) (hg : PolynomiallyBounded g) :
PolynomiallyBounded (fun n => f n + g n) := by
rcases hf with ⟨cf, df, hfbound⟩
rcases hg with ⟨cg, dg, hgbound⟩
refine ⟨cf + cg, df + dg, ?_⟩
intro n
let base := n + 1
have hbase : 1 ≤ base := Nat.succ_pos n
have hdf :
base ^ df ≤ base ^ (df + dg) :=
Nat.pow_le_pow_right hbase (Nat.le_add_right df dg)
have hdg :
base ^ dg ≤ base ^ (df + dg) :=
Nat.pow_le_pow_right hbase (Nat.le_add_left dg df)
calc
f n + g n ≤ cf * base ^ df + cg * base ^ dg :=
Nat.add_le_add (hfbound n) (hgbound n)
_ ≤ cf * base ^ (df + dg) +
cg * base ^ (df + dg) := by
exact
Nat.add_le_add
(Nat.mul_le_mul_left cf hdf)
(Nat.mul_le_mul_left cg hdg)
_ = (cf + cg) * base ^ (df + dg) := by
rw [Nat.add_mul]
theorem PolynomiallyBounded.mul {f g : Nat → Nat}
(hf : PolynomiallyBounded f) (hg : PolynomiallyBounded g) :
PolynomiallyBounded (fun n => f n * g n) := by
rcases hf with ⟨cf, df, hfbound⟩
rcases hg with ⟨cg, dg, hgbound⟩
refine ⟨cf * cg, df + dg, ?_⟩
intro n
let base := n + 1
calc
f n * g n ≤
(cf * base ^ df) * (cg * base ^ dg) :=
Nat.mul_le_mul (hfbound n) (hgbound n)
_ = (cf * cg) * base ^ (df + dg) := by
rw [Nat.pow_add]
ac_rfl
theorem PolynomiallyBounded.const_mul {f : Nat → Nat}
(constant : Nat) (hf : PolynomiallyBounded f) :
PolynomiallyBounded (fun n => constant * f n) := by
exact (PolynomiallyBounded.const constant).mul hf
theorem PolynomiallyBounded.mul_const {f : Nat → Nat}
(hf : PolynomiallyBounded f) (constant : Nat) :
PolynomiallyBounded (fun n => f n * constant) := by
simpa [Nat.mul_comm] using hf.mul (PolynomiallyBounded.const constant)
theorem PolynomiallyBounded.pow_const {f : Nat → Nat}
(hf : PolynomiallyBounded f) :
∀ exponent : Nat,
PolynomiallyBounded (fun n => (f n) ^ exponent)
| 0 => by
simpa using PolynomiallyBounded.const 1
| exponent + 1 => by
simpa [Nat.pow_succ] using
(PolynomiallyBounded.pow_const hf exponent).mul hf
theorem PolynomiallyBounded.succ {f : Nat → Nat}
(hf : PolynomiallyBounded f) :
PolynomiallyBounded (fun n => f n + 1) := by
simpa using hf.add (PolynomiallyBounded.const 1)
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.