AFTD Auto-Formalizing Theoretical Domains

explicitApproximant_perm

theoremverifiedformalization

For any Boolean function f : (Fin n → Bool) → Bool on n variables, any permutation e : Equiv.Perm (Fin n), if f (x ∘ e) = f x for all x then explicitApproximant f (x ∘ e) = explicitApproximant f x for all x.

Statement

theorem explicitApproximant_perm {n : ℕ} (f : (Fin n → Bool) → Bool)
    (e : Equiv.Perm (Fin n)) (hf : ∀ x, f (x ∘ e) = f x) (x : Fin n → Bool) :
    explicitApproximant f (x ∘ e) = explicitApproximant f x
Formalizes
arXiv:2610.19174, Listing A.15
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • explicitApproximantFor a Boolean function f : (Fin n → Bool) → Bool and input x : Fin n → Bool, explicitApproximant f x is (if f x then 1 else 0)/2 -…
  • bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
  • topCoefficientFor an implicit natural number n and a Boolean-valued function f : (Fin n → Bool) → Bool, topCoefficient f is the integer defined by the…
  • fullMonomialThe full monomial x_[n] = ∏_{i=1}^n x_i evaluated at a point in {0,1}^n.
  • parityCharacterFor an implicit natural number n and a Boolean assignment x : Fin n → Bool, parityCharacter x is the real number defined by the product…

Read back from the Lean

For any natural number $n$, any Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, any permutation $e : \text{Equiv.Perm}(\text{Fin } n)$, and any input $x : \text{Fin } n \to \text{Bool}$, if $f$ is invariant under the coordinate permutation $e$ (that is, $f(y \circ e) = f(y)$ for all $y : \text{Fin } n \to \text{Bool}$), then the explicit approximant of $f$ evaluated at $x \circ e$ is equal to the explicit approximant of $f$ evaluated at $x$.

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

The explicit approximant P_f(x) is an affine combination of f(x), fullMonomial x, and parityCharacter x, where all coefficients depend only on f and n (via topCoefficient f) and are independent of x. The coordinate permutation e preserves f(x) by hypothesis, and it preserves both fullMonomial x and parityCharacter x because reindexing a finite product over a permutation leaves the product unchanged (`Equiv.prod_comp`). Unfolding explicitApproximant and substituting these three invariances directly proves that P_f(x ∘ e) = P_f(x).

  1. The full monomial is invariant under coordinate permutations: fullMonomial (x ∘ e) = fullMonomial x

    Unfolding the definition of `fullMonomial`, the value at x ∘ e is the product ∏ i, bit (x (e i)). Because e is a permutation of the finite index type Fin n and multiplication in ℝ is commutative, reindexing the product by e via `Equiv.prod_comp` leaves the product unchanged, equal to fullMonomial x.

    lines 7–9

    uses Equiv.prod_comp

      have hmul : fullMonomial (x ∘ e) = fullMonomial x := by
        simp only [fullMonomial]
        exact Equiv.prod_comp e (fun i => bit (x i))
  2. The parity character is invariant under coordinate permutations: parityCharacter (x ∘ e) = parityCharacter x

    Unfolding `parityCharacter`, the value at x ∘ e is ∏ i, (if x (e i) = true then 1 else -1). By the same reindexing lemma `Equiv.prod_comp`, permuting the factors of this finite product by e preserves its value, yielding parityCharacter x.

    lines 10–12

    uses Equiv.prod_comp

      have hpar : parityCharacter (x ∘ e) = parityCharacter x := by
        simp only [parityCharacter]
        exact Equiv.prod_comp e (fun i => if x i = true then (1 : ℝ) else -1)
  3. The explicit approximant is invariant under coordinate permutations: explicitApproximant f (x ∘ e) = explicitApproximant f x

    By definition, `explicitApproximant f y` depends on y only through f y, fullMonomial y, and parityCharacter y; the other factors depend on topCoefficient f, which is independent of y. Simplifying the expression at x ∘ e by substituting the hypothesis hf (that f (x ∘ e) = f x) and the invariance of the full monomial and parity character established above shows that explicitApproximant f (x ∘ e) = explicitApproximant f x.

    line 13

      simp only [explicitApproximant, hf x, hmul, hpar]
Equiv.prod_comp
Reindexing a finite product by an equivalence (or permutation) preserves its value: ∏ i, g (e i) = ∏ i, g i in any commutative monoid.

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

/-- Symmetry of f under coordinate permutations implies symmetry of P_f. -/theorem explicitApproximant_perm {n : ℕ} (f : (Fin n → Bool) → Bool)    (e : Equiv.Perm (Fin n)) (hf : ∀ x, f (x ∘ e) = f x) (x : Fin n → Bool) :    explicitApproximant f (x ∘ e) = explicitApproximant f x := by  -- `topCoefficient f` does not depend on the input `x`, so the only inputs that  -- move are `f`, `fullMonomial` and `parityCharacter`.  have hmul : fullMonomial (x ∘ e) = fullMonomial x := by    simp only [fullMonomial]    exact Equiv.prod_comp e (fun i => bit (x i))  have hpar : parityCharacter (x ∘ e) = parityCharacter x := by    simp only [parityCharacter]    exact Equiv.prod_comp e (fun i => if x i = true then (1 : ℝ) else -1)  simp only [explicitApproximant, hf x, hmul, hpar]
See it in the graphDiscuss this resultChallenge it