boolAnfCoefficient_univ
For any Boolean function f : (Fin n → Bool) → Bool on n variables, boolAnfCoefficient f Finset.univ equals decide (Odd (acceptingCount f)).
Statement
theorem boolAnfCoefficient_univ {n : ℕ} (f : (Fin n → Bool) → Bool) : boolAnfCoefficient f Finset.univ = decide (Odd (acceptingCount f))
- Source
- arXiv:2610.19174, Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- boolAnfCoefficientFor a Boolean function f : (Fin n → Bool) → Bool on n variables and a subset S : Finset (Fin n), the algebraic normal form coefficient…
- acceptingCountThe number of accepting inputs |f⁻¹(1)| of a Boolean function f.
Read back from the Lean
For every natural number $n$ and every Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, the ANF coefficient of $f$ at the universal subset $\text{Finset.univ}$ (boolAnfCoefficient f Finset.univ) is equal to the boolean decision of whether the accepting count of $f$ (acceptingCount f) is odd.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We unfold the definitions of `boolAnfCoefficient` and `acceptingCount`, reducing the claim to showing that the set of satisfying inputs subject to $\forall j \notin \operatorname{univ},\, x(j) = \text{false}$ has the same cardinality as the unconstrained set of satisfying inputs. Since every variable index belongs to `Finset.univ`, this additional restriction is vacuously true for all inputs. Constructing an explicit bijection between the two sets shows their cardinalities are equal, which immediately yields the theorem by substitution.
The goal reduces to showing that $\operatorname{decide}(\operatorname{Odd} |\{ x : \operatorname{Fin} n \to \operatorname{Bool} \mid f(x) = \text{true} \land \forall j \notin \operatorname{univ},\, x(j) = \text{false} \}|) = \operatorname{decide}(\operatorname{Odd} |\{ x : \operatorname{Fin} n \to \operatorname{Bool} \mid f(x) = \text{true} \}|)$.
Unfolding the definitions of `boolAnfCoefficient` (evaluated at the full set of variables `Finset.univ`) and `acceptingCount` expresses both sides in terms of the parity of the cardinality of their respective subtypes of satisfying assignments.
unfold boolAnfCoefficient acceptingCount$|\{ x : \operatorname{Fin} n \to \operatorname{Bool} \mid f(x) = \text{true} \land \forall j \notin \operatorname{univ},\, x(j) = \text{false} \}| = |\{ x : \operatorname{Fin} n \to \operatorname{Bool} \mid f(x) = \text{true} \}|$.
By `Fintype.card_congr`, it suffices to exhibit a bijection between the two subtypes. The forward map sends an assignment to itself while dropping the second condition. The reverse map sends an assignment to itself, where the condition $\forall j \notin \operatorname{univ},\, x(j) = \text{false}$ is vacuously satisfied: by `Finset.mem_univ`, any index $j$ belongs to `Finset.univ`, contradicting $j \notin \operatorname{univ}$. Finally, both directions compose to the identity because the underlying assignments are identical, as confirmed by `Subtype.ext`.
uses
Fintype.card_congr,Finset.mem_univ,Subtype.exthave h : Fintype.card { x : Fin n → Bool // f x = true ∧ ∀ j ∉ (Finset.univ : Finset (Fin n)), x j = false } = Fintype.card { x : Fin n → Bool // f x = true } := by apply Fintype.card_congr refine { toFun := fun x => ⟨x.1, x.2.1⟩ invFun := fun x => ⟨x.1, x.2, ?_⟩ left_inv := ?_ right_inv := ?_ } · intro j hj; exact absurd (Finset.mem_univ j) hj · intro x; exact Subtype.ext rfl · intro x; exact Subtype.ext rfl
$\operatorname{boolAnfCoefficient}\; f\;\operatorname{Finset.univ} = \operatorname{decide}(\operatorname{Odd}(\operatorname{acceptingCount}\; f))$.
Rewriting with the cardinality equality $h$ established in the previous step makes both sides of the unfolded equation identical, closing the goal.
rw [h]
Fintype.card_congr- An equivalence (bijection) between two finite types implies that they have the same cardinality.
Finset.mem_univ- Every element of a finite type is a member of the universal finset `Finset.univ`.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
- In type theory, elements of a subtype package a value together with a proof of its property. Establishing that the forward and backward maps between the two subtypes are mutual inverses requires `Subtype.ext` to reduce equality of these packages to equality of their underlying functions.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- The top ANF coefficient equals the parity of the accepting count. -/theorem boolAnfCoefficient_univ {n : ℕ} (f : (Fin n → Bool) → Bool) : boolAnfCoefficient f Finset.univ = decide (Odd (acceptingCount f)) := by unfold boolAnfCoefficient acceptingCount have h : Fintype.card { x : Fin n → Bool // f x = true ∧ ∀ j ∉ (Finset.univ : Finset (Fin n)), x j = false } = Fintype.card { x : Fin n → Bool // f x = true } := by apply Fintype.card_congr refine { toFun := fun x => ⟨x.1, x.2.1⟩ invFun := fun x => ⟨x.1, x.2, ?_⟩ left_inv := ?_ right_inv := ?_ } · intro j hj; exact absurd (Finset.mem_univ j) hj · intro x; exact Subtype.ext rfl · intro x; exact Subtype.ext rfl rw [h]