AFTD Auto-Formalizing Theoretical Domains

fourier_cross_level_eq_zero_of_card_lt

theoremverified

For any two functions $f, g : \{0,1\}^n \to \mathbb{R}$ and any integer $k > n$, the $k$-th cross Fourier level $W_k[f,g]$ equals zero.

Statement

theorem fourier_cross_level_eq_zero_of_card_lt {n k : ℕ} (h : n < k) (f g : BooleanAnalysis.BooleanFunc n) :
    fourier_cross_level k f g = 0
Source
arXiv:2611.08289 Section 2.1
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

For all natural numbers $n$ and $k$, if $n < k$, then for any two Boolean functions $f, g : \text{BooleanAnalysis.BooleanFunc } n$, the level-$k$ Fourier cross-term $\operatorname{fourier\_cross\_level}(k, f, g)$ is equal to $0$.

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 k-th cross Fourier level W_k[f,g] is defined as the sum of products of Fourier coefficients f̂(S) * ĝ(S) over all subsets S ⊆ {0, …, n - 1} of cardinality k. Because the domain has size n and k > n, no subset of size k exists, so the sum is taken over the empty set. Consequently, the sum evaluates to zero.

  1. The cross Fourier level W_k[f,g] is written out as a sum of products of Fourier coefficients over all size-k subsets of {0, …, n - 1}.

    Unfolding the definition of fourier_cross_level expresses W_k[f,g] as the sum of f̂(S) * ĝ(S) over all subsets S ⊆ Fin n with |S| = k.

    line 4

      unfold fourier_cross_level
  2. The collection of size-k subsets of {0, …, n - 1} is empty.

    The universal set Finset.univ on Fin n has cardinality n by Finset.card_fin. A finite set has no subsets of size k if and only if its cardinality is strictly less than k, by Finset.powersetCard_eq_empty. Because n < k by assumption h, the collection of such subsets is empty.

    lines 5–8

    uses Finset.card_fin, Finset.powersetCard_eq_empty

      have h_card : Finset.card (Finset.univ : Finset (Fin n)) = n := Finset.card_fin n
      have h_empty : Finset.powersetCard k (Finset.univ : Finset (Fin n)) = ∅ := by
        rw [Finset.powersetCard_eq_empty, h_card]
        exact h
  3. The sum vanishes, so W_k[f,g] = 0.

    Substituting the empty set for the collection of size-k subsets reduces the summation to an empty sum. By Finset.sum_empty, any sum over the empty set equals zero.

    line 9

    uses Finset.sum_empty

      rw [h_empty, Finset.sum_empty]
Finset.card_fin
The cardinality of the universal finset of type Fin n is n.
Finset.powersetCard_eq_empty
The collection of subsets of a finite set s having cardinality n is empty if and only if the cardinality of s is strictly less than n.
Finset.sum_empty
The sum of any function over the empty finset is zero.

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 cross Fourier level W_k[f,g] vanishes when k > n. -/theorem fourier_cross_level_eq_zero_of_card_lt {n k : ℕ} (h : n < k) (f g : BooleanAnalysis.BooleanFunc n) :    fourier_cross_level k f g = 0 := by  unfold fourier_cross_level  have h_card : Finset.card (Finset.univ : Finset (Fin n)) = n := Finset.card_fin n  have h_empty : Finset.powersetCard k (Finset.univ : Finset (Fin n)) = ∅ := by    rw [Finset.powersetCard_eq_empty, h_card]    exact h  rw [h_empty, Finset.sum_empty]
See it in the graphDiscuss this resultChallenge it