Samplinglib
Lean gate not recorded for this source state main · 9bb7a7394ab0

A positive tilt matches the Poisson denominator

Huanjian Zhou and Taiji Suzuki, On Complexity of Gaussian Sampling. Literal selected-parameter step in the proof of Proposition B.7. Omitted scalar algebra is supplied here; the Poisson integral and Eq24 remain separate.

arXiv:2610.20492v1 · Proposition B.7 proof A2.SS2.SSS2.p5, Eq22–23; standing n>=3,kappa>=4 · faithful paraphrase

Complete source statement and conditions

Let natural \(n\ge3\) and real \(\kappa\ge4\), including \(\kappa=4\). Put \(s=\sqrt\kappa\), \(r=(1-1/n)(s-1)/(s+1)\), and \(\ell=(4ns+(s-1)^2)/(8n(n-1))\). Then \(0<r<1\), \(\ell>0\), and \(\ell=(\kappa-1)(1+r^2)/(8r)-(\kappa+1)/4\). Moreover \((\kappa-1)/(2r)=n(s+1)^2/(2(n-1))\). For every real \(u\), \(\kappa+1+4\ell-(\kappa-1)u=((\kappa-1)/(2r))(1+r^2-2ru)=(n(s+1)^2/(2(n-1)))(1+r^2-2ru)\). These are scalar identities; the source applies them to its actual \(U=O_{11}\).

  • Natural \(n\ge3\) and real \(\kappa\ge4\), including \(\kappa=4\).
  • Every subtraction and division involving \(n\) is real arithmetic after coercion. The matching variable \(u\) is any real number. No domain estimate is supplied as a premise.

Selected parameters and matching

\[D_\ell(u)=\frac{n(s+1)^2}{2(n-1)}(1+r^2-2ru),\qquad 0<r<1,\quad\ell>0.\]

Read the formalized proofs

Each statement and proof below has its own closed Lean disclosure. Samplinglib parents, Mathlib calls and external mathematical sources are distinguished in each proof.

Samplinglib mathematical lesson

A positive tilt matches the Poisson denominator

Read this first

Mathematical statement

The selected positive tilt puts the Gaussian denominator into the source Poisson-kernel form.

\[D_\ell(u)=\frac{n(s+1)^2}{2(n-1)}(1+r^2-2ru),\qquad 0<r<1,\quad\ell>0.\]
Lean statement · selected_tilt

Only the standing n and kappa assumptions; all positivity and matching are conclusions.

Braces mark parameters Lean can infer; square brackets request structures such as a measurable space or probability measure. Named hypotheses are mathematical premises, not facts established by this declaration. Section parameters are described in the mathematical hypotheses above; the module link retains their exact source context.

theorem selected_tilt {n : ℕ} (hn : 3 ≤ n) {κ : ℝ} (hκ : 4 ≤ κ) :
    let r : ℝ := (1 - 1 / (n : ℝ)) * ((Real.sqrt κ - 1) / (Real.sqrt κ + 1))
    let ℓ : ℝ := (4 * (n : ℝ) * Real.sqrt κ + (Real.sqrt κ - 1) ^ 2) /
      (8 * (n : ℝ) * ((n : ℝ) - 1))
    0 < r ∧ r < 1 ∧ 0 < ℓ ∧
      ℓ = (κ - 1) / (8 * r) * (1 + r ^ 2) - (κ + 1) / 4 ∧
      (κ - 1) / (2 * r) = (n : ℝ) * (Real.sqrt κ + 1) ^ 2 /
        (2 * ((n : ℝ) - 1)) ∧
      (∀ u : ℝ,
        κ + 1 + 4 * ℓ - (κ - 1) * u =
          (κ - 1) / (2 * r) * (1 + r ^ 2 - 2 * r * u) ∧
        (κ - 1) / (2 * r) * (1 + r ^ 2 - 2 * r * u) =
          ((n : ℝ) * (Real.sqrt κ + 1) ^ 2 / (2 * ((n : ℝ) - 1))) *
            (1 + r ^ 2 - 2 * r * u))

Exact module and namespace context

This supplies the positive tilt and scalar matching for Eq23; the actual sphere/Poisson integral remains open.

Full assumptions and notation

All objects and hypotheses

  • Natural \(n\ge3\) and real \(\kappa\ge4\), including \(\kappa=4\).
  • Every subtraction and division involving \(n\) is real arithmetic after coercion. The matching variable \(u\) is any real number. No domain estimate is supplied as a premise.

Notation and interpretation

\(s,r,\ell\)

Literal source parameter choices; s is shorthand for the real square root.

\[s=\sqrt\kappa,\quad r=\left(1-\frac1n\right)\frac{s-1}{s+1},\quad\ell=\frac{4ns+(s-1)^2}{8n(n-1)}.\]
\(D_\ell(u)\)

Affine denominator from the already formalized Gaussian transform.

\[D_\ell(u)=\kappa+1+4\ell-(\kappa-1)u.\]

Mathematical proof

Open a step to read its argument and formula.

1. Establish the parameter domains

The standing source assumptions keep every denominator away from zero. These are conclusions derived internally, not extra caller premises.

\[s=\sqrt\kappa\ge2,\quad s^2=\kappa,\quad n\ge3,\quad n>0,\quad n-1>0,\quad s-1>0.\]
Corresponding Lean step

hs, hs2, hn3, hn0 and hn1 use the canonical Real.le_sqrt_of_sq_le and Real.sq_sqrt declarations and real arithmetic.

2. Shrink the spectral ratio

Both factors defining r lie strictly between zero and one. Rewrite r into a single rational expression for later normalization.

\[0<1-1/n<1,\quad0<\frac{s-1}{s+1}<1,\qquad r=\frac{(n-1)(s-1)}{n(s+1)}\in(0,1).\]
Corresponding Lean step

hfactor, hfactor1, hratio and hratio1 use positive division; hr, hr1 and hreq establish the exact source radius and its domain.

3. Choose a strictly positive tilt

The closed-form numerator is positive and its denominator is positive. Clearing these established nonzero denominators recovers the other presentation of the same source tilt.

\[\ell=\frac{4ns+(s-1)^2}{8n(n-1)}>0,\qquad\ell=\frac{\kappa-1}{8r}(1+r^2)-\frac{\kappa+1}{4}.\]
Corresponding Lean step

hℓ proves positivity from the literal formula. hell rewrites kappa=s² and the exact hreq radius; field arithmetic checks the equality.

4. Normalize the positive coefficient

Factor the spectral difference and cancel only factors already proved nonzero. This makes explicit the scalar coefficient equality underlying the second source line of Eq23.

\[\kappa-1=(s-1)(s+1),\qquad\frac{\kappa-1}{2r}=\frac{n(s+1)^2}{2(n-1)}.\]
Corresponding Lean step

hcoeff uses hs2 and hreq followed by canonical field normalization. This is supplied scalar bookkeeping, not an additional displayed source theorem or a sphere-law assertion.

5. Match the entire affine denominator

Substitute the recovered tilt formula, collect the affine terms, and replace the coefficient. The calculation is valid for any real u. Positivity for arbitrary real u is not claimed; the source later uses its bounded actual coordinate U.

\[D_\ell(u)=\kappa+1+4\ell-(\kappa-1)u=\frac{\kappa-1}{2r}(1+r^2-2ru)=\frac{n(s+1)^2}{2(n-1)}(1+r^2-2ru).\]
Corresponding Lean step

The final forall-u block expands hell and then rewrites hcoeff. The separate actual_gaussian_transform consumer can use the proved ell>0; Poisson evaluation and Eq24 are not inferred.

Lean verification

Lean proof · selected_tilt

Positive rational factors and canonical square-root/field arithmetic.

Braces mark parameters Lean can infer; square brackets request structures such as a measurable space or probability measure. Named hypotheses are mathematical premises, not facts established by this declaration. Section parameters are described in the mathematical hypotheses above; the module link retains their exact source context.

Download module (.lean)
theorem selected_tilt {n : ℕ} (hn : 3 ≤ n) {κ : ℝ} (hκ : 4 ≤ κ) :
    let r : ℝ := (1 - 1 / (n : ℝ)) * ((Real.sqrt κ - 1) / (Real.sqrt κ + 1))
    let ℓ : ℝ := (4 * (n : ℝ) * Real.sqrt κ + (Real.sqrt κ - 1) ^ 2) /
      (8 * (n : ℝ) * ((n : ℝ) - 1))
    0 < r ∧ r < 1 ∧ 0 < ℓ ∧
      ℓ = (κ - 1) / (8 * r) * (1 + r ^ 2) - (κ + 1) / 4 ∧
      (κ - 1) / (2 * r) = (n : ℝ) * (Real.sqrt κ + 1) ^ 2 /
        (2 * ((n : ℝ) - 1)) ∧
      (∀ u : ℝ,
        κ + 1 + 4 * ℓ - (κ - 1) * u =
          (κ - 1) / (2 * r) * (1 + r ^ 2 - 2 * r * u) ∧
        (κ - 1) / (2 * r) * (1 + r ^ 2 - 2 * r * u) =
          ((n : ℝ) * (Real.sqrt κ + 1) ^ 2 / (2 * ((n : ℝ) - 1))) *
            (1 + r ^ 2 - 2 * r * u)) := by
  let s := Real.sqrt κ
  have hs : (2 : ℝ) ≤ s := Real.le_sqrt_of_sq_le (by nlinarith)
  have hs0 : 0 < s := by linarith
  have hm : 0 < s - 1 := by linarith
  have hp : 0 < s + 1 := by linarith
  have hs2 : s ^ 2 = κ := Real.sq_sqrt (by linarith)
  have hn3 : (3 : ℝ) ≤ n := by exact_mod_cast hn
  have hn0 : (0 : ℝ) < n := by linarith
  have hn1 : (0 : ℝ) < (n : ℝ) - 1 := by linarith
  let r : ℝ := (1 - 1 / (n : ℝ)) * ((s - 1) / (s + 1))
  let ℓ : ℝ := (4 * (n : ℝ) * s + (s - 1) ^ 2) /
    (8 * (n : ℝ) * ((n : ℝ) - 1))
  change 0 < r ∧ r < 1 ∧ 0 < ℓ ∧ _
  have hfactor : 0 < (1 : ℝ) - 1 / (n : ℝ) := by
    have hdiv : (1 : ℝ) / n < 1 := (div_lt_one hn0).2 (by linarith)
    linarith
  have hfactor1 : (1 : ℝ) - 1 / (n : ℝ) < 1 := by
    have : (0 : ℝ) < 1 / (n : ℝ) := one_div_pos.mpr hn0
    linarith
  have hratio : 0 < (s - 1) / (s + 1) := div_pos hm hp
  have hratio1 : (s - 1) / (s + 1) < 1 := (div_lt_one hp).2 (by linarith)
  have hr : 0 < r := mul_pos hfactor hratio
  have hr1 : r < 1 := by
    dsimp [r]
    nlinarith
  have hℓ : 0 < ℓ := by dsimp [ℓ]; positivity
  have hreq : r = ((n : ℝ) - 1) * (s - 1) / ((n : ℝ) * (s + 1)) := by
    dsimp [r]
    field_simp
  have hcoeff : (κ - 1) / (2 * r) =
      (n : ℝ) * (s + 1) ^ 2 / (2 * ((n : ℝ) - 1)) := by
    rw [← hs2, hreq]
    field_simp
    ring
  have hell : ℓ = (κ - 1) / (8 * r) * (1 + r ^ 2) - (κ + 1) / 4 := by
    rw [← hs2, hreq]
    dsimp [ℓ]
    field_simp
    ring
  refine ⟨hr, hr1, hℓ, hell, hcoeff, ?_⟩
  intro u
  change κ + 1 + 4 * ℓ - (κ - 1) * u =
      (κ - 1) / (2 * r) * (1 + r ^ 2 - 2 * r * u) ∧
    (κ - 1) / (2 * r) * (1 + r ^ 2 - 2 * r * u) =
      ((n : ℝ) * (s + 1) ^ 2 / (2 * ((n : ℝ) - 1))) *
        (1 + r ^ 2 - 2 * r * u)
  constructor
  · rw [hell]
    field_simp
    ring
  · rw [hcoeff]

end AutoSamplingTheory.ExampleCases.GaussianComplexity.SelectedTilt

Exact module and namespace context

Source correspondence and review

Source assumptions versus formal assumptions

SourceActual LeanDifference kindWhy it matters
B7 natural n>=3 and real kappa>=4.Exactly hn and hkappa, including kappa4. All positivity/nonzero factors proved internally.sameNo selected-radius, tilt-positivity or coefficient-matching conclusion is accepted as an input.
Eq23 is applied to the actual Haar matrix coordinate U=O_11.The matching equalities hold for every real scalar u; no probability distribution or all-real-u positivity is asserted.generalizationAffine scalar identities have no coordinate-domain hypothesis. Their actual-coordinate use and the sphere pushforward/Poisson integration remain separate.
Eq23 gives equality of the two positive multiples without a standalone coefficient lemma.The coefficient equality is included as an internally proved conclusion.source-implicitMakes the omitted scalar cancellation bridge explicit; no extra mathematical premise or replacement object.

Selected numerical tilt and all Eq22–23 scalar matching only. No sphere law/Poisson integral, Eq24 H evaluation, actual TV first ratio, amplification, transcript/query/cost, hidden-eigenbasis or main lower bound. Source zero-tilt remark is context, not an extra conclusion.

Encoder–denoiser: accepted · equivalent-after-elaboration

Detected semantic differences

  • objects: The tilt is renamed from lambda to ell, and its two explicitly equal source presentations are reversed in definition/proof order. — Pinned A2.E22Xa gives the reciprocal-r presentation equal to the literal rational closed form. SelectedTilt.lean uses the closed form as its let and proves the reciprocal-r expression as hell; the current packet and blind reconstruction retain both exact expressions.
  • assumptions: The formal proof supplies domain and nonzero-factor derivations that are omitted in the original scalar presentation; no caller assumption is added. — Pinned B.7 assumes n>=3,kappa>=4 and p5 asserts 0<r<1,lambda>0. Whole-module inspection finds exactly hn,hkappa as premises; hs,hs0,hm,hp,hs2,hn3,hn0,hn1,hfactor,hfactor1,hratio,hratio1,hr,hr1,hℓ derive the needed bounds and nonzero factors internally.
  • conclusion: The public conjunction separately exposes the scalar coefficient equality implicit in the original two-line denominator matching. — Pinned Eq23 displays two equal multiples of (1+r^2-2rU), while hcoeff explicitly proves (kappa-1)/(2r)=n*(sqrt(kappa)+1)^2/(2*(n-1)) from hs2 and hreq. Lesson step four and the current publication identify this as supplied scalar bookkeeping, not an additional original displayed theorem.
  • quantifiers: The affine matching equalities are valid for every real scalar u, extending the original displayed use at the actual matrix coordinate U. — Pinned A2.SS2.p2 defines U:=O_11 and Eq23 uses U. The complete theorem has forall u:Real for the two identities and its final proof block uses only hell, field normalization, ring and hcoeff; no u-domain or sphere-law premise, nor arbitrary-u positivity conclusion, occurs. Current exposition explicitly states this scope.

A generalization is not a source correction. Proposed missing conditions require separate independent repair review. No proposed repair silently changes the original theorem.

Scope and omitted-condition boundaries
  • Selected numerical tilt and all Eq22–23 scalar matching only. No sphere law/Poisson integral, Eq24 H evaluation, actual TV first ratio, amplification, transcript/query/cost, hidden-eigenbasis or main lower bound. Source zero-tilt remark is context, not an extra conclusion.
Sources, dependencies, and reuse

Source and reuse

Samplinglib parents called

    Mathlib API called (external library)

    • Real.le_sqrt_of_sq_le
    • Real.sq_sqrt
    • div_lt_one
    • one_div_pos
    • div_pos
    • mul_pos

    Mathematical sources

    • Zhou-Suzuki, Eq. (22)-(23) — Only literal r/ell positivity and Eq22–23 denominator matching, including the coefficient equality; scalar identities hold for every real u, with no claim of positivity for every real u.

    Samplinglib prose is not a quotation or a source-equivalence certificate. Definitions and aliases are explained as constructions, not counted as new mathematical proofs.

    Which proof obligations and prerequisites are covered?

    • TODO — not closed by these contributions Literal Eq22 radius/tilt domains and Eq23 scalar denominator matching