BoolBLR.linear_bool_iff_character_aux_h_fx
theoremverifiedimported Lean
Value of a linear Boolean function from its action on basis vectors. Let $f : \{0,1\}^n \to \{0,1\}$ be a linear Boolean function, meaning $f(x \oplus y) = f(x) \oplus f(y)$ for all $x, y \in \{0,1\}^n$, where $\oplus$ is componentwise XOR. For each coordinate $i$, let $e_i \in \{0,1\}^n$ denote the standard basis vector that is $1$ in coordinate $i$ and $0$ elsewhere. Then for every $x \in \{0,1\}^n$, the value $f(x)$ is $1$ if the number of coordinates $i$ with $x_i = 1$ and $f(e_i) = 1$ is odd, and $0$ if that number is even; equivalently, $f(x)$ is the parity of $\lvert\{\, i : x_i = 1 \text{ and } f(e_i) = 1 \,\}\rvert$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.linear_bool_iff_character_aux_h_fx {n : ℕ} (f : hypercube n → Bool) (hf : is_linear_bool f) (x : BooleanAnalysis.BoolCube n) : f x = if (∑ i with x i = true, if (f fun j => if j = i then true else false) = true then 1 else 0) % 2 = 0 then false else true
- Source
- TCSlib, `BoolBLR.linear_bool_iff_character_aux_h_fx`
- Lean proof
- By Prastik Mohanraj, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Prastik Mohanraj. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.BoolBLR.linear_bool_iff_character_aux_h_fx← BoolBLR.linear_bool_iff_character_aux_h_fx (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:112): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- BoolBLR.is_linear_boolA function $f : \{0,1\}^n \to \{0,1\}$ is linear if for all $x, y \in \{0,1\}^n$ we have \[ f(x \oplus y) = f(x) \oplus f(y), \]…
- BoolBLR.linear_bool_iff_character_aux_h_fx_2Value of a linear Boolean function from its values on basis vectors. Let $f : \{0,1\}^n \to \{0,1\}$ be a linear Boolean function, meaning…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- Used by 1
- BoolBLR.linear_bool_iff_characterLinear Boolean functions are exactly the Walsh characters. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean function. Then $f$ is linear —…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.linear_bool_iff_character_aux_h_fx {n : ℕ} (f : hypercube n → Bool) (hf : is_linear_bool f) (x : BooleanAnalysis.BoolCube n) : f x = if (∑ i with x i = true, if (f fun j => if j = i then true else false) = true then 1 else 0) % 2 = 0 then false else true := (linear_bool_iff_character_aux_h_fx_2 f hf x)