BoolBLR.linear_bool_iff_character_aux_h_fx_1
Value of a linear Boolean function on an indicator vector. 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 a subset $s \subseteq \{0, \dots, n-1\}$, let $\mathbf{1}_s \in \{0,1\}^n$ be its indicator vector, whose $i$-th coordinate is $1$ when $i \in s$ and $0$ otherwise, and for each index $i$ let $e_i \in \{0,1\}^n$ be the standard basis vector, whose $i$-th coordinate is $1$ and all others $0$. Then for every $s$ the value $f(\mathbf{1}_s)$ is $0$ when \[ \sum_{i \in s} \mathbf{1}[\,f(e_i) = 1\,] \equiv 0 \pmod 2, \] and $1$ otherwise; that is, $f(\mathbf{1}_s)$ equals the parity of the number of $i \in s$ with $f(e_i) = 1$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.linear_bool_iff_character_aux_h_fx_1 {n : ℕ} (f : BoolFourier.hypercube n → Bool) (hf : is_linear_bool f) : ∀ (s : Finset (Fin n)), (f fun i => if i ∈ s then true else false) = if (∑ i ∈ s, 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_1`
- 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_1← BoolBLR.linear_bool_iff_character_aux_h_fx_1 (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:71): adapted
What was changed in
BoolBLR.linear_bool_iff_character_aux_h_fx_1--- TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:71 (BoolBLR.linear_bool_iff_character_aux_h_fx_1) +++ as compiled here @@ -1,2 +1,5 @@ -private lemma linear_bool_iff_character_aux_h_fx_1 {n : ℕ} (f : BoolFourier.hypercube n → Bool) (hf : is_linear_bool f) : +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open Finset BoolFourier in +lemma BoolBLR.linear_bool_iff_character_aux_h_fx_1 {n : ℕ} (f : BoolFourier.hypercube n → Bool) (hf : is_linear_bool f) : ∀ (s : Finset (Fin n)), @@ -9,2 +12,3 @@ convert (hf ( fun _ => false ) ( fun _ => false )) using 1; + · rfl simp +decide; - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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), \]…
- BoolFourier.xor_vecFor $x, y \in \{0,1\}^n$, the vector $\mathrm{xor\_vec}(x,y)_i = x_i \oplus y_i$ is the componentwise XOR, giving the group operation on…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$.
- Used by 1
- 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…
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_1 {n : ℕ} (f : BoolFourier.hypercube n → Bool) (hf : is_linear_bool f) : ∀ (s : Finset (Fin n)), (f fun i => if i ∈ s then true else false) = if (∑ i ∈ s, if (f fun j => if j = i then true else false) = true then 1 else 0) % 2 = 0 then false else true := by intro s; induction s using Finset.induction <;> simp_all +decide ; · -- Base case s = ∅: f(0,…,0) = false, computed using linearity at (0,0). convert (hf ( fun _ => false ) ( fun _ => false )) using 1; · rfl simp +decide; · -- Inductive step: peel off one element using the linearity hypothesis hf. rename_i i s hi hs; specialize hf ( fun j => decide ( j = i ) ) ( fun j => decide ( j ∈ s ) ) ; simp_all +decide [ Finset.filter_insert ] ; convert hf using 1; · congr! 2; by_cases hi : ‹Fin n› = i <;> by_cases hs : ‹Fin n› ∈ s <;> simp +decide [ hi, hs, xor_vec ]; · assumption; · assumption; · grind +splitImp;