AFTD Auto-Formalizing Theoretical Domains

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

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