Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · CompactFourier · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Distributions_CompactFourier

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

ca-fd889115-k1

Private dependency for the Distribution Theory mission. Module ComputableDistributions/CompactFourier.lean from the frozen computable-analysis foundation with kernel-checked rational decision proofs.

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FourierQuadratureRationalProof
import Definitions.Def_liuyao_ca_fd889115_k1_Distributions_CubeAverage
import Definitions.Def_liuyao_ca_fd889115_k1_Distributions_BoxQuadrature

set_option autoImplicit true

/-! Fourier integration for compact smooth tests at rational frequencies. -/

open ComputableAnalysis
open ComputableAnalysis.ComputableCoefficient
open ComputableAnalysis.RealApproximationOrder

namespace ComputableDistributions
namespace CompactFourier

set_option maxRecDepth 4096

open ComputableAnalysis.FourierQuadrature

export ComputableAnalysis.FourierQuadrature (boxPoint boxPoint_on_unitCube)

private def component {d : Nat} (φ : TestFunction d) (ξ : QPoint d) (cosine : Bool) : Value :=
  FourierQuadrature.component φ.support φ.toJointLipschitzSampler ξ cosine

/-- Fourier transform at a rational frequency with phase
`exp(-2π i x⋅ξ)`. The real and imaginary parts use iterated integration
over the test's rational support box. -/
def transform {d : Nat} (φ : TestFunction d) (ξ : QPoint d) : ComplexActionValue :=
  let values := FourierQuadrature.transform φ.support φ.toJointLipschitzSampler ξ
  ⟨values.1.real.preferred, values.2.real.preferred, values.1.real.valid, values.2.real.valid⟩

/-- The ordinary integral of a real test, evaluated one coordinate at a time. -/
def testIntegral {d : Nat} (φ : TestFunction d) : RealCompute :=
  (FourierQuadrature.integral φ.support φ.toJointLipschitzSampler).real.preferred

theorem transform_at_zero {d : Nat} (φ : TestFunction d) :
    ((transform φ (origin d)).re).Equiv (testIntegral φ) ∧
      ((transform φ (origin d)).im).Equiv (RealCompute.ofRat 0) :=
  FourierQuadrature.component_at_zero φ.support φ.toJointLipschitzSampler

/-- Equivalent test evaluations give the same transform on a common box. -/
theorem transform_congr {d : Nat} {φ ψ : TestFunction d} (ξ : QPoint d)
    (hbox : φ.support = ψ.support) (he : ∀ x, (φ.value x).Equiv (ψ.value x)) :
    (transform φ ξ).Equiv (transform ψ ξ) := by
  have h (cosine : Bool) : Same (component φ ξ cosine) (component ψ ξ cosine) := by
    unfold component
    rw [← hbox]
    exact FourierQuadrature.component_congr φ.support ξ cosine
      φ.toJointLipschitzSampler ψ.toJointLipschitzSampler (fun x _ => he x)
  exact ⟨h true, h false⟩

/-- Transform a complex test by complex linear extension of the real test transform. -/
def transformComplex {d : Nat} (φ : ComplexTestFunction d) (ξ : QPoint d) : ComplexActionValue :=
  let a := transform φ.re ξ
  let b := transform φ.im ξ
  ⟨RealCompute.sub a.re b.im, RealCompute.add a.im b.re,
    RealCompute.sub_valid a.re_valid b.im_valid, RealCompute.add_valid a.im_valid b.re_valid⟩

theorem transformComplex_congr {d : Nat} {φ ψ : ComplexTestFunction d} (ξ : QPoint d)
    (hboxRe : φ.re.support = ψ.re.support) (hboxIm : φ.im.support = ψ.im.support)
    (heRe : ∀ x, (φ.re.value x).Equiv (ψ.re.value x))
    (heIm : ∀ x, (φ.im.value x).Equiv (ψ.im.value x)) :
    (transformComplex φ ξ).Equiv (transformComplex ψ ξ) := by
  have hr := transform_congr ξ hboxRe heRe
  have hi := transform_congr ξ hboxIm heIm
  exact ⟨RealCompute.sub_equiv (transform φ.re ξ).re_valid (transform ψ.re ξ).re_valid
    (transform φ.im ξ).im_valid (transform ψ.im ξ).im_valid hr.1 hi.2,
    RealCompute.add_equiv (transform φ.re ξ).im_valid (transform ψ.re ξ).im_valid
    (transform φ.im ξ).re_valid (transform ψ.im ξ).re_valid hr.2 hi.1⟩

/-- Contributor target: the transform is unchanged by replacing the
support box or any other certificates, as long as the test values agree. -/
def SupportIndependenceTarget : Prop :=
  ∀ d (φ ψ : TestFunction d) (ξ : QPoint d),
    (∀ x, (φ.value x).Equiv (ψ.value x)) →
    (transform φ ξ).Equiv (transform ψ ξ)

/-- Contributor target: the iterated computation agrees with tagged
quadrature directly on the test's support box. -/
def TaggedQuadratureAgreementTarget : Prop :=
  ∀ d (φ : TestFunction d) (ξ : QPoint d) (cosine : Bool),
    HasBoxIntegral φ.support
      (fun x => RealCompute.mul (φ.value x) (GeometricTrig.sample cosine (phase ξ x)))
      (component φ ξ cosine).real.preferred

/-- Contributor target: spatial differentiation acts by multiplication by
the frequency symbol, with this file's Fourier phase convention. -/
def DifferentiationTarget : Prop :=
  ∀ d (φ : TestFunction d) (ξ : QPoint d) (i : Fin d),
    let F := transform φ ξ
    let DF := transform (φ.coordinatePartial i) ξ
    DF.re.Equiv (RealCompute.scaleRat (-2 * ξ i) (RealCompute.mul GeometricTrig.pi F.im)) ∧
    DF.im.Equiv (RealCompute.scaleRat (2 * ξ i) (RealCompute.mul GeometricTrig.pi F.re))


namespace Line

open FTCRealCalculus LipschitzQuadrature

/-- Samples of the (j)-th ordinary derivative on the rational line. -/
def derivativeSampler (φ : TestFunction 1) (j : Nat) : JointLipschitzSampler 1 where
  value x := parameter (φ.derivative (fun _ => j) x) (φ.derivative_valid (fun _ => j) x)
  bound := φ.derivativeLipschitz (fun _ => j)
  nonnegative := φ.derivativeLipschitz_nonneg _
  control := φ.derivative_control _

/-- The represented derivative value at a rational input. -/
abbrev sample (φ : TestFunction 1) (j : Nat) (t : Rat) : Value :=
  (derivativeSampler φ j).value (fun _ => t)

/-- The first three derivatives have uniform secant convergence on bounded
windows. The Lipschitz estimate for the third derivative is already part of
the test data. The older bracket law at individual rational points provides
pointwise information. -/
def HasUniformDerivatives (φ : TestFunction 1) : Prop :=
  ∀ j : Nat, j < 3 → ∀ n : Nat,
    UniformFirstOrder (sample φ j) (sample φ (j+1))
      (-((n+1 : Nat) : Rat)) ((n+1 : Nat) : Rat)

/-- A symmetric window radius with a positive margin outside the support. -/
def supportRadius (φ : TestFunction 1) : Rat :=
  1 + qabs (φ.support.lower 0) + qabs (φ.support.upper 0)

private theorem supportRadius_ge_one (φ : TestFunction 1) : 1 ≤ supportRadius φ := by
  have hl := qabs_nonneg (φ.support.lower 0)
  have hu := qabs_nonneg (φ.support.upper 0)
  unfold supportRadius
  grind only

private theorem sample_vanishes (φ : TestFunction 1) (j : Nat) (t : Rat)
    (ht : supportRadius φ ≤ qabs t) : Same (sample φ j t) (Value.rational 0) := by
  apply φ.derivative_vanishes_off_support
  intro h
  obtain ⟨hl, hu⟩ := h (0 : Fin 1)
  change φ.support.lower 0 ≤ t at hl
  change t ≤ φ.support.upper 0 at hu
  have h₁ := neg_qabs_le_self (φ.support.lower 0)
  have h₂ := self_le_qabs (φ.support.upper 0)
  have hn₁ := qabs_nonneg (φ.support.lower 0)
  have hn₂ := qabs_nonneg (φ.support.upper 0)
  let B := qabs (φ.support.lower 0) + qabs (φ.support.upper 0)
  have hb : qabs t ≤ B := qabs_le_of_neg_le_le (by dsimp only [B]; grind only)
    (by dsimp only [B]; grind only)
  unfold supportRadius at ht
  dsimp only [B] at hb
  grind only

private theorem derivative_bound (φ : TestFunction 1) (j : Nat) (t : Rat) :
    Small (sample φ j t) ((derivativeSampler φ j).bound * (2*supportRadius φ+1)) := by
  let R := supportRadius φ
  let f := derivativeSampler φ j
  have hR := supportRadius_ge_one φ
  have bound0 : 0 ≤ f.bound*(2*R+1) := Rat.mul_nonneg f.nonnegative (by grind only)
  by_cases h : R ≤ qabs t
  · have hz : Small (Value.rational 0) 0 := by
      simpa only [show qabs (0 : Rat) = 0 by decide +kernel] using rational_small 0
    exact (hz.congr (sample_vanishes φ j t h).symm).mono bound0
  have href : R ≤ qabs (R+1) := by have := self_le_qabs (R+1); grind only
  have ht₁ := neg_qabs_le_self t
  have ht₂ := self_le_qabs t
  have H := f.control (fun _ => t) (fun _ => R+1) (2*R+1)
    (by grind only) (fun _ => ⟨by grind only, by grind only⟩)
  refine H.congr (((Same.refl (sample φ j t)).sub (sample_vanishes φ j (R+1) href)).trans ?_)
  apply arithmetic_identity
  intro s
  simp only [sub, Value.rational, Rat.sub_eq_add_neg, Rat.neg_zero, Rat.add_zero]

/-- Each derivative has a whole-line decay certificate from its support and
Lipschitz bound. -/
def derivativeDecay (φ : TestFunction 1) (j : Nat) : LineDecay (derivativeSampler φ j) :=
  LineDecay.of_support _ (supportRadius φ)
    (Rat.mul_nonneg (derivativeSampler φ j).nonnegative (by
      have := supportRadius_ge_one φ; grind only))
    (supportRadius_ge_one φ) (derivative_bound φ j)
    (fun t ht => sample_vanishes φ j t (Rat.le_of_lt ht))

private def windowDerivativeData (φ : TestFunction 1) (j n : Nat) :
    Data (sample φ j) (-((n+1 : Nat) : Rat)) ((n+1 : Nat) : Rat) where
  ordered := by have := Rat.natCast_nonneg (a := n+1); grind only
  constant := (derivativeSampler φ j).bound
  nonnegative := (derivativeSampler φ j).nonnegative
  lipschitz u v _ huv _ :=
    (derivativeSampler φ j).control (fun _ => v) (fun _ => u) (v-u) (by grind only)
      (fun _ => ⟨by grind only, by grind only⟩)

/-- The derivative bounds for Melrose's proof follow from the FTC on the
fixed dyadic windows. -/
def derivatives (φ : TestFunction 1) (h : HasUniformDerivatives φ) :
    LineDerivatives (derivativeSampler φ 0) where
  first := derivativeSampler φ 1
  second := derivativeSampler φ 2
  third := derivativeSampler φ 3
  firstDecay := derivativeDecay φ 1
  secondDecay := derivativeDecay φ 2
  thirdDecay := derivativeDecay φ 3
  firstStep n := (windowDerivativeData φ 1 n).stepOfUniformFirstOrder (h 0 (by decide) n)
  secondStep n := (windowDerivativeData φ 2 n).stepOfUniformFirstOrder (h 1 (by decide) n)
  thirdStep n := (windowDerivativeData φ 3 n).stepOfUniformFirstOrder (h 2 (by decide) n)

private def clip (R t : Rat) : Rat := max (-R) (min R t)

private theorem clip_bounds {R : Rat} (hR : 0 ≤ R) (t : Rat) : -R ≤ clip R t ∧ clip R t ≤ R := by
  unfold clip
  rw [Rat.max_def, Rat.min_def]
  split <;> split <;> grind only

private theorem clip_eq {R t : Rat} (ht : qabs t ≤ R) : clip R t = t := by
  have h₁ := neg_qabs_le_self t
  have h₂ := self_le_qabs t
  unfold clip
  rw [Rat.max_def, Rat.min_def]
  split <;> split <;> grind only

private theorem clip_control {R u v δ : Rat}
    (h : u ≤ v+δ ∧ v ≤ u+δ) : qabs (clip R u-clip R v) ≤ δ := by
  apply qabs_le_of_neg_le_le
  all_goals
    unfold clip
    rw [Rat.max_def, Rat.min_def, Rat.max_def, Rat.min_def]
    split <;> split <;> split <;> (try split) <;> grind only

/-- The moment sampler clips the coordinate before multiplying. The support
identity makes its value exactly (tphi(t)) on the entire rational line. -/
def momentSampler (φ : TestFunction 1) : JointLipschitzSampler 1 where
  value x := scale (clip (supportRadius φ) (x 0)) ((derivativeSampler φ 0).value x)
  bound := supportRadius φ * (derivativeSampler φ 0).bound + (derivativeDecay φ 0).bound
  nonnegative := Rat.add_nonneg
    (Rat.mul_nonneg (by have := supportRadius_ge_one φ; grind only)
      (derivativeSampler φ 0).nonnegative) (derivativeDecay φ 0).nonnegative
  control := by
    intro u v δ hδ h
    let R := supportRadius φ
    let f := derivativeSampler φ 0
    let D := derivativeDecay φ 0
    let p := clip R (u 0)
    let q := clip R (v 0)
    have hR : 0 ≤ R := by have := supportRadius_ge_one φ; grind only
    have hp := clip_bounds hR (u 0)
    have hF := f.control u v δ hδ h
    have hV : Small (f.value v) D.bound := by
      have e : (fun _ : Fin 1 => v 0) = v := by
        funext i
        have hi : i = 0 := Subsingleton.elim _ _
        rw [hi]
      simpa only [e] using D.bounded (v 0)
    have hL := (scale_small hF p).mono (Rat.mul_le_mul_of_nonneg_right
      (qabs_le_of_neg_le_le hp.1 hp.2) (Rat.mul_nonneg f.nonnegative hδ))
    have hM := (scale_small hV (p-q)).mono
      (Rat.mul_le_mul_of_nonneg_right (clip_control (h 0)) D.nonnegative)
    have H := hL.add hM
    have e : R*(f.bound*δ)+δ*D.bound = (R*f.bound+D.bound)*δ := by grind only
    rw [e] at H
    apply H.congr
    apply arithmetic_identity
    intro s
    change p*((f.value u).sample s-(f.value v).sample s)+(p-q)*(f.value v).sample s =
      p*(f.value u).sample s-q*(f.value v).sample s
    grind only

theorem moment_identity (φ : TestFunction 1) (t : Rat) :
    Same ((momentSampler φ).value (fun _ => t)) (scale t (sample φ 0 t)) := by
  change Same (scale (clip (supportRadius φ) t) (sample φ 0 t)) _
  by_cases ht : qabs t ≤ supportRadius φ
  · rw [clip_eq ht]
    exact Same.refl _
  · have hz := sample_vanishes φ 0 t (by grind only)
    refine (hz.scale _).trans (Same.trans ?_ (hz.scale t).symm)
    apply arithmetic_identity
    intro s
    simp only [scale, Value.rational, Rat.mul_zero]

def momentDecay (φ : TestFunction 1) : LineDecay (momentSampler φ) :=
  LineDecay.of_support (supportRadius φ * (derivativeDecay φ 0).bound) (supportRadius φ)
    (Rat.mul_nonneg (by have := supportRadius_ge_one φ; grind only) (derivativeDecay φ 0).nonnegative)
    (supportRadius_ge_one φ)
    (fun t => by
      let p := clip (supportRadius φ) t
      have hp := clip_bounds (show 0 ≤ supportRadius φ by
        have := supportRadius_ge_one φ; grind only) t
      exact (scale_small ((derivativeDecay φ 0).bounded t) p).mono
        (Rat.mul_le_mul_of_nonneg_right (qabs_le_of_neg_le_le hp.1 hp.2)
          (derivativeDecay φ 0).nonnegative))
    (fun t ht => by
      refine (moment_identity φ t).trans (((sample_vanishes φ 0 t (Rat.le_of_lt ht)).scale t).trans ?_)
      apply arithmetic_identity
      intro s
      simp only [scale, Value.rational, Rat.mul_zero])

/-- Forward transform using the fixed dyadic whole-line quadrature. -/
def dyadicTransformAt (φ : TestFunction 1) (cosine : Bool) (x : RealCompute) (hx : x.Valid) : RealCompute :=
  lineTransformAt (derivativeDecay φ 0) cosine x hx

theorem dyadicTransformAt_valid (φ : TestFunction 1) (cosine : Bool) (x : RealCompute) (hx : x.Valid) :
    (dyadicTransformAt φ cosine x hx).Valid :=
  lineTransformAt_valid (derivativeDecay φ 0) cosine x hx

/-- At a rational frequency the dyadic forward transform is already the
compact integral as soon as a window covers the padded support. -/
theorem dyadicTransformAt_eq_window (φ : TestFunction 1) (cosine : Bool) (q : Rat) (n : Nat)
    (hn : supportRadius φ ≤ ((n+1 : Nat) : Rat)) :
    (dyadicTransformAt φ cosine (RealCompute.ofRat q) (RealCompute.ofRat_valid q)).Equiv
      (lineCompactComponent (derivativeDecay φ 0) (fun _ => q) cosine n).real.preferred := by
  let D := derivativeDecay φ 0
  let F := parameter (dyadicTransformAt φ cosine (RealCompute.ofRat q) (RealCompute.ofRat_valid q))
    (dyadicTransformAt_valid φ cosine _ _)
  have hF : Same F (lineValue D cosine q) := lineTransformAt_rational D cosine q
  have hI : Same (lineValue D cosine q) (expandingComponent (derivativeSampler φ 0) (fun _ => q) cosine n) :=
    lineTransform_of_support D _ cosine (supportRadius φ) n hn (sample_vanishes φ 0)
  exact (hF.trans hI).trans (lineCompactComponent_agrees D _ cosine n)

/-- The reconstruction supplied by Melrose's theorem for the dyadic
transform of a compactly supported smooth line test. -/
def dyadicInverseAt (φ : TestFunction 1) (h : HasUniformDerivatives φ)
    (x : RealCompute) (hx : x.Valid) : RealCompute :=
  (inverseLineAt (derivativeDecay φ 0) (derivatives φ h) (momentDecay φ) (moment_identity φ) x hx).real.preferred

theorem dyadicInverseAt_eq (φ : TestFunction 1) (h : HasUniformDerivatives φ)
    (x : RealCompute) (hx : x.Valid) :
    (dyadicInverseAt φ h x hx).Equiv (lineSamplerAt φ.toJointLipschitzSampler x hx) :=
  inverseLineAt_eq (derivativeDecay φ 0) (derivatives φ h) (momentDecay φ) (moment_identity φ) x hx

theorem dyadicInverseAt_congr (φ : TestFunction 1) (h : HasUniformDerivatives φ)
    {x y : RealCompute} (hx : x.Valid) (hy : y.Valid) (hxy : x.Equiv y) :
    (dyadicInverseAt φ h x hx).Equiv (dyadicInverseAt φ h y hy) :=
  inverseLineAt_congr (derivativeDecay φ 0) (derivatives φ h) (momentDecay φ) (moment_identity φ) hx hy hxy

end Line

end CompactFourier
end ComputableDistributions

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