Polynomial bounds are closed under affine input scaling
Definitionsgl_polynomial_linear_compcomplexity-theorypolynomial-timeutility
This module proves a standard closure property for the mission predicate PolynomiallyBounded: if a time bound is polynomially bounded, then so is for fixed natural constants and . It also records the special cases of adding a constant to the input length and multiplying the input length by a constant.
This is scheduler bookkeeping for the Sipser--Gács--Lautemann machine construction: verifier-query lengths and encoded-simulation input lengths are bounded by affine functions of the controlling input lengths, so existing polynomial verifier time bounds can be transported through those size changes.
Definition code
import Definitions.Def_sgl_polynomial_closures
import Mathlib.Tactic
namespace SipserGacsLautemann
theorem linear_argument_le_scaled_succ
(a b n : Nat) :
a * n + b + 1 ≤ (a + b + 1) * (n + 1) := by
have ha : a * n ≤ a * (n + 1) :=
Nat.mul_le_mul_left a (Nat.le_succ n)
have hb : b + 1 ≤ (b + 1) * (n + 1) := by
have hone : 1 ≤ n + 1 := Nat.succ_pos n
simpa using Nat.mul_le_mul_left (b + 1) hone
calc
a * n + b + 1 = a * n + (b + 1) := by omega
_ ≤ a * (n + 1) + (b + 1) * (n + 1) :=
Nat.add_le_add ha hb
_ = (a + b + 1) * (n + 1) := by
ring
theorem PolynomiallyBounded.comp_linear
{f : Nat → Nat}
(hf : PolynomiallyBounded f)
(a b : Nat) :
PolynomiallyBounded (fun n => f (a * n + b)) := by
rcases hf with ⟨coefficient, degree, hbound⟩
refine
⟨coefficient * (a + b + 1) ^ degree,
degree, ?_⟩
intro n
have hlinear :
a * n + b + 1 ≤
(a + b + 1) * (n + 1) :=
linear_argument_le_scaled_succ a b n
have hpow :
(a * n + b + 1) ^ degree ≤
((a + b + 1) * (n + 1)) ^ degree :=
Nat.pow_le_pow_left hlinear degree
calc
f (a * n + b) ≤
coefficient * (a * n + b + 1) ^ degree :=
hbound (a * n + b)
_ ≤ coefficient *
((a + b + 1) * (n + 1)) ^ degree :=
Nat.mul_le_mul_left coefficient hpow
_ = (coefficient * (a + b + 1) ^ degree) *
(n + 1) ^ degree := by
rw [Nat.mul_pow]
ac_rfl
theorem PolynomiallyBounded.comp_add_const
{f : Nat → Nat}
(hf : PolynomiallyBounded f)
(b : Nat) :
PolynomiallyBounded (fun n => f (n + b)) := by
simpa [Nat.one_mul] using hf.comp_linear 1 b
theorem PolynomiallyBounded.comp_mul_const
{f : Nat → Nat}
(hf : PolynomiallyBounded f)
(a : Nat) :
PolynomiallyBounded (fun n => f (a * n)) := by
simpa using hf.comp_linear a 0
end SipserGacsLautemann
Source
Standard closure of polynomially bounded functions under affine input scaling; used in the Prove2me Sipser--Gács--Lautemann scheduler formalization.