Bit-length bounded dyadic initialization and terminal DGS width
ProvedInfoLossLAR.WorstCase.RegevSketch.dyadic_initial_scheduleLet , , and let the initial width and requested width be positive rationals. Put and suppose
Let be the sum of the binary lengths of the numerator of and the denominator of . There is an integer such that every source width for is strictly above , and the final source width permits terminal amplitude width inside the decoding radius:
The square of the threshold scale is and is rational. This gives a finite, bit-length bounded mathematical width plan from a sufficiently broad rational initial width to the exact requested terminal width, including the strict smoothing margin. It neither constructs the initial sampler and BDD oracle nor proves that the least crossing index or its comparison is implementable in the platform machine model.
import Mathlib set_option autoImplicit false
namespace InfoLossLAR.WorstCase.RegevSketch
theorem dyadic_initial_schedule (n : ℕ) (q eta : ℝ) (start target : ℚ)
(hn : 0 < n) (hq : 0 < q) (heta : 0 < eta)
(hstart : 0 < start) (htarget : 0 < target)
(hthreshold : (16*q*Real.sqrt n/((n : ℝ)+2))*eta ≤ (target : ℝ))
(hinit : (target : ℝ)*((n : ℝ)+2)/(Real.sqrt 2*Real.sqrt n) ≤ (start : ℝ)) :
let K := Nat.size start.num.natAbs + Nat.size target.den
∃ k : ℕ, k ≤ K ∧
(∀ j < k, Real.sqrt 2*q*eta < (start : ℝ)/(2 : ℝ)^j) ∧
Real.sqrt 2*q*eta < (start : ℝ)/(2 : ℝ)^k ∧
Real.sqrt n/(Real.sqrt 2*(target : ℝ)) ≤ ((n : ℝ)+2)/(2*((start : ℝ)/(2 : ℝ)^k)) ∧
1/(Real.sqrt 2*(1/(Real.sqrt 2*(target : ℝ)))) = (target : ℝ) ∧
((target : ℝ)*((n : ℝ)+2)/(Real.sqrt 2*Real.sqrt n))^2 =
(target : ℝ)^2*((n : ℝ)+2)^2/(2*(n : ℝ)) := by sorry
end InfoLossLAR.WorstCase.RegevSketch