Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Binary-time dyadic source-width selection for fixed-family DGS

Proved
InfoLossLAR.WorstCase.NativeDyadicSchedule.native_dyadic_program

by BoomShaKaLaaaKa · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

lar-regev-bridgelatticeslearning-with-errorsquantum-computing

For the scan result on a positive rational initial width WWW, positive rational target width rrr and positive integer dimension nnn, there is a single total polynomial-time multi-stack Turing program in the platform's binary encoding that returns the scan's index kkk and rational width uuu.

Let q,η>0q,\eta>0q,η>0, put σ=n+2\sigma=n+2σ=n+2, and suppose

r≥16qnση,W≥rσ2n.r\ge \frac{16q\sqrt n}{\sigma}\eta,\qquad W\ge\frac{r\sigma}{\sqrt2\sqrt n}.r≥σ16qn​​η,W≥2​n​rσ​.

The returned kkk is at most the sum of the binary length of the absolute numerator of WWW and the binary length of the denominator of rrr. Every preceding dyadic width W/2jW/2^jW/2j and the returned width uuu strictly exceed 2qη\sqrt2q\eta2​qη. In addition,

n2r≤σ2u,12(1/(2r))=r.\frac{\sqrt n}{\sqrt2r}\le\frac{\sigma}{2u}, \qquad \frac1{\sqrt2(1/(\sqrt2r))}=r.2​rn​​≤2uσ​,2​(1/(2​r))1​=r.

The program compares rational squares and does not compute a square root or expand WWW, rrr or nnn 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.

Preamble
import Definitions.Def_RegevDyadicSchedule
set_option autoImplicit false
open InfoLossLAR.WorstCase.NativeDyadicSchedule
open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic
Formal statement
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
Source
Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, https://cims.nyu.edu/~regev/papers/qcrypto.pdf, Theorem 3.1 and Lemmas 3.2, 3.3, 3.14, pp. 18–19 and 26–27. This is a separately proved binary-time fixed-family width-selection and terminal-step statement; the source does not specify this implementation.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me