Binary-time initial base and dyadic source-width selection
ProvedInfoLossLAR.WorstCase.NativeDyadicSchedule.native_initial_programThere is a single total polynomial-time multi-stack Turing program which, on binary-coded integer rows, a rational requested width and a natural dimension , computes the fixed-family initializer base, the dyadic crossing index and its selected rational width.
For , , assume
The output base satisfies , and . Its associated width is positive. The output index is at most the sum of the binary lengths of the numerator of and denominator of , every preceding width and the selected width exceed , and
The list of rows need not encode a square or nonsingular matrix for these arithmetic properties. The program uses rational square comparison and binary representations; it does not expand as a unary list. It does not construct the lattice Gaussian pool, BDD oracle or quantum iteration.
Formalization Note. The program is polynomial time in Automatic.enc for row lists, rationals, naturals and outputs. Its link to the platform encMat/encQ input and the actual initializer's TM2/quantum sampler remains a separate proof obligation.
import Definitions.Def_RegevInitialSelection set_option autoImplicit false open InfoLossLAR.WorstCase.NativeDyadicSchedule open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic
namespace InfoLossLAR.WorstCase.NativeDyadicSchedule
theorem native_initial_program :
Nonempty (Turing.TM2ComputableInPolyTime Automatic.enc Automatic.enc initialSelection) ∧
∀ (x : InitialInput) (q eta : ℝ),
0 < x.2 → 0 < x.1.2 → 0 < q → 0 < eta →
(16*q*Real.sqrt x.2/((x.2 : ℝ)+2))*eta ≤ (x.1.2 : ℝ) →
2 ≤ initialBase x.1.2 x.2 ∧ x.2 ≤ initialBase x.1.2 x.2 ∧
(x.1.2 : ℝ)*((x.2 : ℝ)+2) ≤ initialBase x.1.2 x.2 ∧
0 < (initialRequest x).1.1 ∧
crossingIndex (initialRequest x) ≤
Nat.size ((initialRequest x).1.1).num.natAbs + Nat.size x.1.2.den ∧
(∀ j < crossingIndex (initialRequest x),
Real.sqrt 2*q*eta < (width (initialRequest x,j) : ℝ)) ∧
Real.sqrt 2*q*eta < (selectedWidth (initialRequest x) : ℝ) ∧
Real.sqrt x.2/(Real.sqrt 2*(x.1.2 : ℝ)) ≤
((x.2 : ℝ)+2)/(2*(selectedWidth (initialRequest x) : ℝ)) := by sorry
end InfoLossLAR.WorstCase.NativeDyadicSchedule