Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Binary-time initial base and dyadic source-width selection

Proved
InfoLossLAR.WorstCase.NativeDyadicSchedule.native_initial_program

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

lar-regev-bridgelatticeslearning-with-errorsquantum-computing

There is a single total polynomial-time multi-stack Turing program which, on binary-coded integer rows, a rational requested width rrr and a natural dimension nnn, computes the fixed-family initializer base, the dyadic crossing index and its selected rational width.

For n≥1n\ge1n≥1, r,q,η>0r,q,\eta>0r,q,η>0, assume

r≥16qnn+2 η.r\ge\frac{16q\sqrt n}{n+2}\,\eta.r≥n+216qn​​η.

The output base bbb satisfies b≥2b\ge2b≥2, b≥nb\ge nb≥n and b≥r(n+2)b\ge r(n+2)b≥r(n+2). Its associated width W=b(1+∑i,j∣Bij∣)W=b(1+\sum_{i,j}|B_{ij}|)W=b(1+∑i,j​∣Bij​∣) is positive. The output index kkk is at most the sum of the binary lengths of the numerator of WWW and denominator of rrr, every preceding width W/2jW/2^jW/2j and the selected width uuu exceed 2qη\sqrt2q\eta2​qη, and

n2r≤n+22u.\frac{\sqrt n}{\sqrt2r}\le\frac{n+2}{2u}.2​rn​​≤2un+2​.

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 bbb 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.

Preamble
import Definitions.Def_RegevInitialSelection
set_option autoImplicit false
open InfoLossLAR.WorstCase.NativeDyadicSchedule
open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic
Formal statement
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
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 and 3.14. This is a binary fixed-family initialization and dyadic-width interface derived for the formalization, not a verbatim algorithm in that source.

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