booleanAffineRestriction
The restriction of a Boolean function p to an affine subspace a + U is the function on Fin (dim U) → ZMod 2 obtained by evaluating p at a plus the linear combination of the canonical basis vectors of U.
Statement
open scoped Pointwise in noncomputable def booleanAffineRestriction {n : ℕ} (p : (Fin n → ZMod 2) → ZMod 2) (a : Fin n → ZMod 2) (U : Submodule (ZMod 2) (Fin n → ZMod 2)) : (Fin (Module.finrank (ZMod 2) U) → ZMod 2) → ZMod 2
- Defined in
- arXiv:2611.03452, Lemma 2.2 and Section 2.4
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 1
- not_boolean_subspace_degree_reduction_criterionThe statement
boolean_subspace_degree_reduction_criterionis false: The statement is false for d = 0. When d = 0: Let n = 1, p : (Fin 1…
- not_boolean_subspace_degree_reduction_criterionThe statement
Read back from the Lean
Given a natural number $n$, a function $p : (\mathbb{Z}/2\mathbb{Z})^n \to \mathbb{Z}/2\mathbb{Z}$, a vector $a \in (\mathbb{Z}/2\mathbb{Z})^n$, and a submodule (subspace) $U \le (\mathbb{Z}/2\mathbb{Z})^n$, booleanAffineRestriction p a U is defined to be the function $(\mathbb{Z}/2\mathbb{Z})^{\dim(U)} \to \mathbb{Z}/2\mathbb{Z}$ that maps a coordinate vector $y \in \operatorname{Fin}(\operatorname{finrank}_{\mathbb{Z}/2\mathbb{Z}} U) \to \mathbb{Z}/2\mathbb{Z}$ to $p(a + \iota(y))$, where $\iota(y) \in U \subseteq (\mathbb{Z}/2\mathbb{Z})^n$ is the element corresponding to coordinate vector $y$ under the inverse of the coordinate isomorphism (Module.finBasis (ZMod 2) U).equivFun associated with the basis Module.finBasis (ZMod 2) U.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
open scoped Pointwise in /-- Restriction of a Boolean function p to the affine subspace a + U, represented as a function on Fin (dim U) -> ZMod 2 via the canonical basis of U. -/ noncomputable def booleanAffineRestriction {n : ℕ} (p : (Fin n → ZMod 2) → ZMod 2) (a : Fin n → ZMod 2) (U : Submodule (ZMod 2) (Fin n → ZMod 2)) : (Fin (Module.finrank (ZMod 2) U) → ZMod 2) → ZMod 2 := fun y => p (a + (Module.finBasis (ZMod 2) U).equivFun.symm y)