BoolBLR.linear_bool_iff_character_aux_h_fx_2
theoremverifiedimported Lean
Value 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 $f(x \oplus y) = f(x) \oplus f(y)$ for all $x, y \in \{0,1\}^n$, and for each coordinate $i$ let $e_i \in \{0,1\}^n$ denote the standard basis vector that is $1$ in position $i$ and $0$ elsewhere. Then for every $x \in \{0,1\}^n$, the value $f(x)$ equals the parity of the number of coordinates $i$ with $x_i = 1$ and $f(e_i) = 1$; that is, $f(x) = 1$ if that count is odd and $f(x) = 0$ if it is even.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.linear_bool_iff_character_aux_h_fx_2 {n : ℕ} (f : BoolFourier.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_2`
- 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_2← BoolBLR.linear_bool_iff_character_aux_h_fx_2 (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:90): 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), \]…
- 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…
- BoolBLR.linear_bool_iff_character_aux_h_fx_1Value of a linear Boolean function on an indicator vector. Let $f : \{0,1\}^n \to \{0,1\}$ be a linear Boolean function, meaning…
- Used by 1
- BoolBLR.linear_bool_iff_character_aux_h_fxValue 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…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BoolFourier inlemma BoolBLR.linear_bool_iff_character_aux_h_fx_2 {n : ℕ} (f : BoolFourier.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 := by -- More general claim by induction on the support set s. -- Specialize to s = support of x. convert (linear_bool_iff_character_aux_h_fx_1 f hf) ( Finset.univ.filter fun i => x i = true ) using 2 ; aesop;