AFTD Auto-Formalizing Theoretical Domains

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