Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Local activation families and the information retained by adaptive atoms

Definition
NarrowDNF_Adaptive

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

combinatoricsnarrow-dnf-authors-importprobabilitystoc-2027

For a coordinate index type III, write Cube⁡(I)={0,1}I\operatorname{Cube}(I)=\{0,1\}^ICube(I)={0,1}I. An activation family assigns a predicate JS(x)J_S(x)JS​(x) to every finite S⊆IS\subseteq IS⊆I, together with locality: if xxx and yyy agree on SSS, then JS(x)↔JS(y)J_S(x)\leftrightarrow J_S(y)JS​(x)↔JS​(y). Thus the global-input representation of JSJ_SJS​ gives the test no access to coordinates outside SSS.

The family is increasing when every predicate JSJ_SJS​ is monotone in the coordinatewise order. Its active union at xxx is

AJ(x)=⋃S:JS(x)S.A_J(x)=\bigcup_{S:J_S(x)}S.AJ​(x)=S:JS​(x)⋃​S.

Two inputs belong to the same adaptive atom precisely when their active unions coincide and their original labels agree on that common union. A Boolean readout is measurable for this adaptive information when it is constant on each such atom. Finally, zeroOutside⁡(J,x)\operatorname{zeroOutside}(J,x)zeroOutside(J,x) agrees with xxx on AJ(x)A_J(x)AJ​(x) and is zero elsewhere. These objects record input-dependent coordinate information; they do not impose a fixed-coordinate junta restriction.

Definition code
import Mathlib.Data.Bool.Basic
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Data.Fintype.Pi
import Mathlib.Order.Monotone.Basic

namespace NarrowDNF
end NarrowDNF

namespace NarrowDNF.Activation
end NarrowDNF.Activation


/-! Local activation families and their adaptive atoms. The global-input encoding
of a local activation carries an explicit locality proof, so it does not grant
an activation access to coordinates outside its indexing set. -/
namespace NarrowDNF

abbrev Cube (ι : Type*) := ι → Bool

structure Activation (ι : Type*) where
  fires : Finset ι → Cube ι → Prop
  locality : ∀ S x y, (∀ i ∈ S, x i = y i) → (fires S x ↔ fires S y)

namespace Activation
variable {ι : Type*} [DecidableEq ι]

def Increasing (J : Activation ι) : Prop := ∀ S, Monotone (J.fires S)

def active (J : Activation ι) (x : Cube ι) : Set ι :=
  {i | ∃ S, i ∈ S ∧ J.fires S x}

def SameAtom (J : Activation ι) (x y : Cube ι) : Prop :=
  J.active x = J.active y ∧ ∀ i ∈ J.active x, x i = y i

def Measurable (J : Activation ι) (u : Cube ι → Bool) : Prop :=
  ∀ x y, J.SameAtom x y → u x = u y





noncomputable def zeroOutside (J : Activation ι) (x : Cube ι) : Cube ι :=
  by classical exact fun i => if i ∈ J.active x then x i else false







end Activation
end NarrowDNF
Source
https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L41-L42 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L11-L11 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L13-L15 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L20-L20 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L22-L23 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L25-L26 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Adaptive.lean#L28-L29

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