Binary-time dyadic source-width selection for fixed-family DGS
ProvedInfoLossLAR.WorstCase.NativeDyadicSchedule.native_dyadic_programFor the scan result on a positive rational initial width , positive rational target width and positive integer dimension , there is a single total polynomial-time multi-stack Turing program in the platform's binary encoding that returns the scan's index and rational width .
Let , put , and suppose
The returned is at most the sum of the binary length of the absolute numerator of and the binary length of the denominator of . Every preceding dyadic width and the returned width strictly exceed . In addition,
The program compares rational squares and does not compute a square root or expand , or in unary. The theorem establishes a width-selection interface only; it does not construct the initial lattice sampler, BDD oracle or quantum iteration.
Formalization Note. Polynomial time uses the native Automatic.enc for rational pairs, naturals and outputs. A separate encoding bridge is needed to compose this program with the platform's encMat, encQ and quantum circuit interfaces.
import Definitions.Def_RegevDyadicSchedule set_option autoImplicit false open InfoLossLAR.WorstCase.NativeDyadicSchedule open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic
namespace InfoLossLAR.WorstCase.NativeDyadicSchedule
theorem native_dyadic_program :
Nonempty (Turing.TM2ComputableInPolyTime Automatic.enc Automatic.enc result) ∧
∀ (x : Input) (q eta : ℝ),
0 < x.2 → 0 < x.1.1 → 0 < x.1.2 → 0 < q → 0 < eta →
(16*q*Real.sqrt x.2/((x.2 : ℝ)+2))*eta ≤ (x.1.2 : ℝ) →
(x.1.2 : ℝ)*((x.2 : ℝ)+2)/(Real.sqrt 2*Real.sqrt x.2) ≤ (x.1.1 : ℝ) →
crossingIndex x ≤ (ticks x).length ∧
(∀ j < crossingIndex x, Real.sqrt 2*q*eta < (width (x,j) : ℝ)) ∧
Real.sqrt 2*q*eta < (selectedWidth x : ℝ) ∧
Real.sqrt x.2/(Real.sqrt 2*(x.1.2 : ℝ)) ≤
((x.2 : ℝ)+2)/(2*(selectedWidth x : ℝ)) ∧
1/(Real.sqrt 2*(1/(Real.sqrt 2*(x.1.2 : ℝ)))) = (x.1.2 : ℝ) := by sorry
end InfoLossLAR.WorstCase.NativeDyadicSchedule