How many Boolean functions $ f:\{-1,1\}^n \rightarrow \{-1,1\}$ have exactly one nonzero Fourier coefficient?

Question

How many Boolean functions $ f\colon\{-1,1\}^n \to \{-1,1\}$ have exactly one nonzero Fourier coefficient?

I know that there are $2^{n+1}$ Boolean functions $ f\colon\{-1,1\}^n \to \{-1,1\}$ but I'm not sure how that helps. What's a good way to filter out only those in the $2^{n+1}$ Boolean functions that have exactly one nonzero Fourier coefficient?

Answer 1

First:

"I know that there are $2^{n+1}$ boolean functions $ f\colon\{-1,1\}^n \to \{-1,1\}$"

No. You have $2^{2^n}$ Boolean functions over $n$ variables.

---

How many Boolean functions $f\colon\{-1,1\}^n \to \{-1,1\}$ with only one non-zero Fourier coefficient are there? (I.e., with Fourier sparsity $1$)

You have ${2^{n+1}}$ of those.

Indeed, since any Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}^n$ satisfies, by Parseval,

$$ \sum_{S\subseteq [n]} \hat{f}(S)^2 = \hat{\lVert} f\hat{\rVert}_2^2 = \lVert f \rVert_2^2 = \mathbb{E}_{x\sim \{-1,1\}^n}[ f(x)^2] = \mathbb{E}_{x\sim \{-1,1\}^n}[1] =1 $$ you have that every Boolean function with only one non-zero Fourier coefficient has exactly one non-zero Fourier coefficient equal to either $1$ or $-1$:

$$ \exists S\subseteq [n],\quad f= \hat{f}(S)\chi_S \text{ with } \hat{f}(S)^2=1\,. $$

So any such function is either one of the parity functions $\chi_S$ (where $S\subseteq [n]$) or its negation. You have $2^n$ parity functions, so you have $2\cdot 2^n$ Boolean functions with Fourier sparsity $1$.