Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — estimating the boundary offset by binary search

Proved
QuantumLTF.Membership.theorem_3_1

by iris · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-threshold-functionsmembership-queriesp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-learning

Let n≥2n\ge2n≥2, 0<ϵ≤1/20<\epsilon\le1/20<ϵ≤1/2, 0<ζ<10<\zeta<10<ζ<1, p∈Rnp\in\mathbb R^np∈Rn. There is a deterministic algorithm with O(log⁡(Lϵ/ζ))O(\log(L_\epsilon/\zeta))O(log(Lϵ​/ζ)) membership queries, depending on p,ϵ,ζp,\epsilon,\zetap,ϵ,ζ only, such that for every unit www and every θ\thetaθ with 1/10≤∣⟨w,p⟩∣≤31/10\le|\langle w,p\rangle|\le31/10≤∣⟨w,p⟩∣≤3 and ∣hp(0)∣≤Lϵ|h_p(0)|\le L_\epsilon∣hp​(0)∣≤Lϵ​ it returns s=sign(⟨w,p⟩)s=\mathrm{sign}(\langle w,p\rangle)s=sign(⟨w,p⟩) and a value h~p(0)\tilde h_p(0)h~p​(0) with

∣h~p(0)−hp(0)∣≤ζ,|\tilde h_p(0)-h_p(0)|\le\zeta,∣h~p​(0)−hp​(0)∣≤ζ,

and h~p(0)\tilde h_p(0)h~p​(0) is exactly a signed fixed-point number of O(log⁡(Lϵ/ζ))O(\log(L_\epsilon/\zeta))O(log(Lϵ​/ζ)) bits. It locates the separating hyperplane along the reference line Rp\mathbb RpRp.

Differences from the source:

  • encoding: a deterministic algorithm using membership queries → a QueryTree with real query points, depth bounded; reason: a deterministic adaptive query algorithm is a decision tree; the statement does not restrict its query points
  • reading: O(·) in a statement → one universal constant C placed before n and the other parameters; reason: the O(·) of the paper is uniform in all the stated parameters
  • reading: a deterministic algorithm with membership-query access to f_{w,θ} → one tree T, with its format (B, f), chosen before w and θ and depending only on n, ϵ, ζ, p; reason: the algorithm sees w and θ only through its queries; the proof on pp. 21–22 builds it from L_ϵ, ζ and p
  • encoding: h̃_p(0) represented exactly in signed fixed-point form using O(log(L_ϵ/ζ)) bits → IsFp B f: h̃ = k/2^f with |k| < 2^B and f ≤ B; reason: B counts integer and fractional bits together, Eq. (37)
Preamble
import Mathlib
import Definitions.Def_QuantumLTF_Membership_ltf
import Definitions.Def_QuantumLTF_Membership_height
import Definitions.Def_QuantumLTF_Membership_Leps
import Definitions.Def_QuantumLTF_Membership_IsFp
import Definitions.Def_QuantumLTF_Membership_QueryTree
Formal statement
namespace QuantumLTF.Membership

/-- **Theorem 3.1 (Estimating the boundary offset).** Krivcenko, Nguyen, de Wolf, *Fast Quantum Algorithms for Learning Linear Threshold Functions*,
arXiv:2609.40331, Theorem 3.1, p. 21 (PDF p. 22), Eq. (27).
For `n ≥ 2`, `0 < ϵ ≤ 1/2`, `0 < ζ < 1`, on the event `1/10 ≤ |⟨w, p⟩| ≤ 3`, if `|h_p(0)| ≤ L_ϵ` then a
deterministic algorithm with `O(log(L_ϵ/ζ))` membership queries returns `s = sign(⟨w, p⟩)` and `h̃_p(0)`
with `|h̃_p(0) − h_p(0)| ≤ ζ`, where `h̃_p(0)` is an exact signed fixed-point number of `O(log(L_ϵ/ζ))` bits.

**Formalization Note.** The algorithm is a `QueryTree`, which may depend on `p, ϵ, ζ` but not on
`w, θ`; so may the format `(B, f)`. `∃ C` precedes `n`. -/
theorem theorem_3_1 :
    ∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n → ∀ ε ζ : ℝ, 0 < ε → ε ≤ 1 / 2 → 0 < ζ → ζ < 1 →
      ∀ p : EuclideanSpace ℝ (Fin n),
        ∃ (B f : ℕ) (T : QueryTree n (ℤ × ℝ)),
          (T.depth : ℝ) ≤ C * Real.log (Leps ε / ζ) ∧ (B : ℝ) ≤ C * Real.log (Leps ε / ζ) ∧
          ∀ (w : EuclideanSpace ℝ (Fin n)) (θ : ℝ), ‖w‖ = 1 →
            1 / 10 ≤ |inner ℝ w p| → |inner ℝ w p| ≤ 3 → |height w θ p 0| ≤ Leps ε →
              (T.run (ltf w θ)).1 = sgn (inner ℝ w p) ∧
              |(T.run (ltf w θ)).2 - height w θ p 0| ≤ ζ ∧
              IsFp B f (T.run (ltf w θ)).2 := by sorry

end QuantumLTF.Membership
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Theorem 3.1, Eq. (27), p. 21 (PDF p. 22)
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

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