AFTD Auto-Formalizing Theoretical Domains

boolAnfCoefficient_univ

theoremverified

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.

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

    line 4

      unfold boolAnfCoefficient acceptingCount
  2. $|\{ 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`.

    lines 5–15

    uses Fintype.card_congr, Finset.mem_univ, Subtype.ext

      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
  3. $\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.

    line 16

      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.

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

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