AFTD Auto-Formalizing Theoretical Domains

BoolBLR.linear_bool_iff_character_aux_h_fx_1

theoremverifiedimported Lean

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.
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

Lean source view module on GitHub

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