Upper and lower coordinate shifts and their ordered iteration
DefinitionNarrowDNF_CoordinateShiftcombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
For , write and for the inputs obtained by fixing coordinate . For any Boolean function , define
Equivalently, the two slices become and , respectively. The formulas are meaningful for arbitrary , without an initial monotonicity assumption.
The predicate of monotonicity in coordinate is for every , with all other coordinates fixed. A Boolean choice selects the lower shift when true and the upper shift when false. A finite list of such choices is applied in list order, retaining repetitions and making no commutativity assumption. These are the concrete operations whose order-preservation and bias-matched error properties are established by separate theorem nodes.
Definition code
import Mathlib.Data.Bool.Basic
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Order.Monotone.Basic
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_Adaptive
namespace NarrowDNF
end NarrowDNF
/-!
# Coordinate shifts on Boolean functions
The unbranched shift formulas are equivalent to the two-slice definitions in
the shift definitions preceding Lemma 3.1 of the 2026-11-06 STOC revision, by Boolean idempotence. This file concerns
monotonicity; the global biased-error bound requires a separate finite-sum
argument.
-/
namespace NarrowDNF
variable {ι : Type*} [DecidableEq ι]
def lowerInput (i : ι) (x : Cube ι) : Cube ι := Function.update x i false
def upperInput (i : ι) (x : Cube ι) : Cube ι := Function.update x i true
def upperShift (i : ι) (v : Cube ι → Bool) (x : Cube ι) : Bool :=
v x || v (lowerInput i x)
def lowerShift (i : ι) (v : Cube ι → Bool) (x : Cube ι) : Bool :=
v x && v (upperInput i x)
/-- Nondecreasing in one coordinate, with the other coordinates held fixed. -/
def CoordinateMonotone (i : ι) (v : Cube ι → Bool) : Prop :=
∀ x, v (lowerInput i x) ≤ v (upperInput i x)
/-- A Boolean records whether the lower shift was chosen. -/
def shiftChoice (i : ι) (useLower : Bool) (v : Cube ι → Bool) : Cube ι → Bool :=
if useLower then lowerShift i v else upperShift i v
/-- Apply shifts in list order; no commutativity of shifts is assumed. -/
def applyShifts : List (ι × Bool) → (Cube ι → Bool) → (Cube ι → Bool)
| [], v => v
| (i, b) :: rest, v => applyShifts rest (shiftChoice i b v)
end NarrowDNF
Source