Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Restricted adaptive partitions and conditional Fourier approximants

Definition
NarrowDNF_HatamiResidual

by chenghua.liu · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsnarrow-dnf-authors-importprobabilitystoc-2027

Let JJJ be a local activation family on {0,1}ι\{0,1\}^{\iota}{0,1}ι. For S⊆ιS\subseteq\iotaS⊆ι, define its restriction by

(J∣S)T(x)  ⟺  T⊆S and JT(x).(J|_S)_T(x)\iff T\subseteq S\ \text{and}\ J_T(x).(J∣S​)T​(x)⟺T⊆S and JT​(x).

An adaptive atom records both the active union and the actual input labels on that union. The operator Ep[F∣J]\mathbb E_p[F\mid J]Ep​[F∣J] is the finite weighted conditional expectation on this actual partition. For the ppp-biased Fourier component FSF_SFS​ of a real-valued fff, set

F~S=Ep[FS∣J∣S].\widetilde F_S=\mathbb E_p[F_S\mid J|_S].FS​=Ep​[FS​∣J∣S​].

Thus each component is conditioned on its own restricted activation family.

For a retained family AAA, the bundle defines both ∑S∈AFS\sum_{S\in A}F_S∑S∈A​FS​ and ∑S∈AF~S\sum_{S\in A}\widetilde F_S∑S∈A​FS​. It also defines the simpler revealed-component competitor 1{JS(x)}FS(x)\mathbf1_{\{J_S(x)\}}F_S(x)1{JS​(x)}​FS​(x) and the literal coordinate restriction x↦xTx\mapsto x_Tx↦xT​. These constructions are the concrete functions compared in the diagonal and cross-term residual analysis. No residual bound or projection optimality conclusion is assumed by introducing them.

Definition code
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.GroupWithZero.Finset
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Sqrt
import Mathlib.Data.Bool.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Finset.Image
import Mathlib.Data.Finset.Insert
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Logic.Equiv.Prod
import Mathlib.Order.Monotone.Basic
import Mathlib.Tactic
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.GCongr
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_Adaptive
import Definitions.Def_NarrowDNF_ConditionalExpectation
import Definitions.Def_NarrowDNF_Fourier
import Definitions.Def_NarrowDNF_ProductMeasure

namespace NarrowDNF.HatamiResidual
end NarrowDNF.HatamiResidual

namespace NarrowDNF.ProductMeasure
end NarrowDNF.ProductMeasure


/-!
# Hatami's actual restricted-activation conditional components

This file formalizes the Step III/IV construction using actual adaptive atom
labels. `approxComponent` is conditional expectation onto the family retaining
only activations whose index is contained in the component's support. Generic
projection and diagonal estimates are proved here. Construction-specific
cross-term bounds are stated only when proved; no analytic estimate is an axiom.
-/

noncomputable section
open scoped BigOperators

namespace NarrowDNF.HatamiResidual

open ProductMeasure
attribute [local instance] Classical.propDecidable

variable {ι : Type*} [Fintype ι] [DecidableEq ι]

/-- Hatami's family `J_S`: retain exactly the original activations indexed inside `S`. -/
def restrict (J : Activation ι) (S : Finset ι) : Activation ι where
  fires T x := T ⊆ S ∧ J.fires T x
  locality T x y hxy := and_congr_right fun _ => J.locality T x y hxy











/-- Real-valued conditional expectation on the actual full adaptive partition. -/
def adaptiveConditional (p : ℝ) (J : Activation ι) (F : Cube ι → ℝ) : Cube ι → ℝ :=
  ConditionalExpectation.conditional (ConditionalExpectation.adaptiveCode J) (weight p) F

/-- Hatami's `F̃_S = E[F_S | F_(J_S)]`, with actual labels and the exact restricted family. -/
def approxComponent (p : ℝ) (J : Activation ι) (f : Cube ι → ℝ)
    (S : Finset ι) : Cube ι → ℝ :=
  adaptiveConditional p (restrict J S) (Fourier.component p f S)

/-- The retained Fourier polynomial. -/
def truncated (p : ℝ) (f : Cube ι → ℝ) (retained : Finset (Finset ι)) (x : Cube ι) : ℝ :=
  ∑ S ∈ retained, Fourier.component p f S x

/-- The measurable competitor used in Hatami's Step III. -/
def approxTruncated (p : ℝ) (J : Activation ι) (f : Cube ι → ℝ)
    (retained : Finset (Finset ι)) (x : Cube ι) : ℝ :=
  ∑ S ∈ retained, approxComponent p J f S x









section Generic
variable {α β : Type*} [Fintype α] [Fintype β] [DecidableEq β]





end Generic



/-- The competitor that keeps the component only when its complete support is revealed. -/
def revealedComponent (p : ℝ) (J : Activation ι) (f : Cube ι → ℝ)
    (S : Finset ι) (x : Cube ι) : ℝ :=
  if J.fires S x then Fourier.component p f S x else 0














section GenericBound
variable {α β : Type*} [Fintype α] [Fintype β] [DecidableEq β]



end GenericBound





















section GenericMeanBound
variable {α β : Type*} [Fintype α] [Fintype β] [DecidableEq β]







end GenericMeanBound



/-- Fixed-coordinate restriction of a cube point. -/
def restriction (T : Finset ι) (x : Cube ι) : T → Bool := fun i => x i







end NarrowDNF.HatamiResidual



Source
https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L534-L535 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L76-L78 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L80-L83 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L85-L87 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L89-L92 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L26-L29 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/HatamiResidual.lean#L177-L180

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