fourier_cross_level_eq_zero_of_card_lt
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
- fourier_cross_levelThe $k$-th cross Fourier level $W_k[f,g]$ of two real-valued functions $f, g : \{0,1\}^n \to \mathbb{R}$ is the sum…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- Used by 1
- discrete_level_one_to_three_sharp_constant_of_lt_threeThe sharp level 1 to 3 inequality holds for all n < 3 (i.e. n = 1, 2) because W_3[f,g] = 0 and the left-hand side is nonpositive by…
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.
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.
unfold fourier_cross_levelThe 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.
uses
Finset.card_fin,Finset.powersetCard_eq_emptyhave 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
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.
uses
Finset.sum_emptyrw [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
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 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]