Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Applying a coordinate-shift order using a Boolean choice assignment

Definition
NarrowDNF_ShiftProbability

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

combinatoricsnarrow-dnf-authors-importprobabilitystoc-2027

Let v:{0,1}ι→{0,1}v:\{0,1\}^{\iota}\to\{0,1\}v:{0,1}ι→{0,1}, let O\mathcal OO be an ordered list of coordinates, and let d∈{0,1}ιd\in\{0,1\}^{\iota}d∈{0,1}ι specify the shift choice at each coordinate. Define the shifted function by applying, in list order, the upper shift at an occurrence of iii when di=0d_i=0di​=0 and the lower shift when di=1d_i=1di​=1. The upper shift has slices (v0,v0∨v1)(v_0,v_0\lor v_1)(v0​,v0​∨v1​); the lower shift has slices (v0∧v1,v1)(v_0\land v_1,v_1)(v0​∧v1​,v1​).

The order is retained explicitly. Repeated coordinates are allowed by the construction, and every occurrence of the same coordinate uses the same bit did_idi​. For a list without repetitions and a Bernoulli-ppp choice assignment, the coordinate choices are independent, with lower-shift probability ppp and upper-shift probability 1−p1-p1−p. This definition is the deterministic function of the choice cube used in the subsequent randomized error analysis. It does not itself assert an error inequality or any commutation property of shifts.

Definition code
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Data.Bool.Basic
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.Linarith
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_Adaptive
import Definitions.Def_NarrowDNF_CoordinateShift

namespace NarrowDNF.ProductMeasure
end NarrowDNF.ProductMeasure

namespace NarrowDNF.ShiftProbability
end NarrowDNF.ShiftProbability


/-!
# Randomized coordinate shifting under the biased product measure

This file proves the full error inequality of Lemma 3.1 and the iterated
expectation inequality following Lemma 3.1 in the 2026-11-06 STOC revision. Random choices form an
explicit Bernoulli product cube; the independence needed by iteration is
derived from the finite-sum Fubini formula.
-/

noncomputable section

namespace NarrowDNF.ShiftProbability

open ProductMeasure

variable {ι : Type*} [DecidableEq ι]







variable [Fintype ι]









/-- Apply a fixed coordinate order, using the corresponding bits of `d`
as the lower/upper choices. -/
def shiftByChoices (order : List ι) (d : Cube ι) (v : Cube ι → Bool) : Cube ι → Bool :=
  applyShifts (order.map fun i => (i, d i)) v



















end NarrowDNF.ShiftProbability
Source
https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/ShiftProbability.lean#L96-L99

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