AFTD Auto-Formalizing Theoretical Domains

booleanAffineRestriction

def

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

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)
See it in the graphDiscuss this resultChallenge it