Uniform polynomial-time conversion to exact round fixed-point lengths
ProvedStudentTeacher976.Adaptivity.uniform_input_size_conversionLet be polynomial-time computable on unary lengths and nondecreasing. Suppose that, for some real ,
There are an integer and unary polynomial-time functions such that, for every ,
and, for every positive ,
Thus the raw construction length is exactly the number of blocks times their length, and its round count is exactly the number of blocks. Both functions are uniform; the result is not merely a length-by-length existence statement. No upper restriction on or unboundedness assumption on is needed. The zero-length output is handled by a total default, without asserting a fixed-point equation there.
This strengthens the size-conversion existence argument in Appendix A by providing an explicit polynomial search bound, a uniform compiled exhaustive search, and all positive input lengths.
import Definitions.Def_StudentTeacher976_Adaptivity_InputConversion set_option autoImplicit false open StudentTeacher976.Adaptivity
theorem StudentTeacher976.Adaptivity.uniform_input_size_conversion (g : ℕ → ℕ) (hpoly : PolyTimeLength g) (hg : Monotone g)
(ε : ℝ) (hε : 0 < ε)
(hbound : ∀ m : ℕ,0 < m → 1 ≤ g m ∧ (g m : ℝ) ≤ (m : ℝ)^(1-ε)) :
∃ (d : ℕ) (p m : ℕ → ℕ),PolyTimeLength p ∧ PolyTimeLength m ∧
(∀ n,1 ≤ p n ∧ p n ≤ (n+1)^d ∧ m n=n*p n) ∧
∀ n,0 < n → p n=g (m n) := by sorry