Fourier sparsity
Number of nonzero Fourier coefficients.
also written:
\|\hat f\|_0, number of nonzero Fourier coefficients
Definition
$\mathrm{spar}(f)=|\{S : \hat f(S)\ne 0\}|$.
Basic facts
- $\mathrm{D}^{\oplus}(f)=O(\sqrt{\mathrm{spar}(f)}\log \mathrm{spar}(f))$; whether $\mathrm{poly}\log \mathrm{spar}$ suffices is the query analogue of the log-rank conjecture.
- $\deg_2(f)\le\log_2(\mathrm{spar}(f)+1)$. The real degree is not bounded by sparsity: $\oplus_n$ has $\deg = n$ and $\mathrm{spar} = 1$.
- $\mathrm{spar}(f)\le 4^{\mathrm{D}^{\oplus}(f)}$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{spar}(f)\). “\(\mathrm{spar}(f)\) in terms of it” is the pair with \(\mathrm{spar}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(2^n\) | In the $\pm1$ encoding $(-1)^{\mathrm{OR}(x)} = -1 + 2^{1-n}\prod_i(1+\chi_i)$, so every one of the $2^n$ characters has a nonzero coefficient. |
| AND total | \(2^n\) | $(-1)^{\mathrm{AND}(x)} = 1 - 2^{1-n}\prod_i(1-\chi_i)$: every character appears. |
| PARITY total | \(1\) | |
| MAJORITY total | \(2^{n-1}\) | MAJ is odd, so only odd-size sets can appear, and the standard formula for $\widehat{\mathrm{MAJ}}(S)$ is nonzero for every one of them. ODonnell14 |
| EXACT-HALF total | \(2^{n-1}\) putative | Exactly. Using $\binom ns K_k(s) = \binom nk K_s(k)$ and $K_s(n/2) = [z^s](1-z)^{n/2}(1+z)^{n/2} = [z^s](1-z^2)^{n/2}$, the Fourier coefficient at a set of size $s$ is $\widehat{\mathrm{EH}}(S) = 2^{-n}\binom{n}{n/2}(-1)^{s/2}\binom{n/2}{s/2}\big/\binom ns$ for even $s$, and $0$ for odd $s$. So every even-size set carries a nonzero coefficient and no odd one does -- consistent with the recorded $\mathrm{Fdim} = n-1$. |
| ODD-MAX-BIT total | \(\Theta(2^n)\) putative | At least $2^{n-1}$, since every one of the $2^{n-1}$ sets containing coordinate $1$ carries the nonzero coefficient $\pm2^{-(n-1)}$ (see the \(\mathrm{D}^{\oplus}(f)\) line); at most $2^n$ trivially. |
| ADDRESS / multiplexer total | \(4^k\) putative | In the $\pm 1$ basis each of the $2^k$ terms $\mathbb{1}[\mathrm{addr}=a]\,y_a$ expands into $2^k$ monomials of coefficient $\pm 2^{-k}$, and the $y_a$ factor keeps the supports of different $a$ disjoint. Consistent with the recorded $\mathrm{L}_1 = 4^k \cdot 2^{-k} = 2^k$. |
| Binary tree navigation total | \(4^{k-1}\) putative | From the recursion $\mathrm{Nav}_k = \tfrac{L+R}{2} + x_0\tfrac{L-R}{2}$ in the $\pm1$ encoding, where $L$ and $R$ are $\mathrm{Nav}_{k-1}$ on disjoint variable sets and each is balanced (no constant term). The four groups of monomials have pairwise disjoint supports, so $\mathrm{spar}(k) = 4\,\mathrm{spar}(k-1)$ with $\mathrm{spar}(1) = 1$. |
| TRIBES total | \(\Theta(2^n)\) putative | Full support, or one short of it. Write $\mathrm{Tribes} = 1 - \prod_{j=1}^{s}(1-A_j)$ with $A_j = \prod_{i \in T_j}x_i = 2^{-w}\prod_{i \in T_j}(1-\chi_i)$. The tribes are on disjoint variables, so the Fourier coefficient of $\chi_S$ in the product factorises over $j$, the factor being $1-2^{-w}$ when $S \cap T_j = \emptyset$ and $-(-1)^{|S \cap T_j|}2^{-w}$ otherwise -- never zero. So every nonempty $S$ carries a nonzero coefficient. The empty set is the only possible exception: in the $\pm1$ encoding $\hat g(\emptyset) = 2(1-2^{-w})^{s}-1$, which vanishes exactly when the function is perfectly balanced. Maximal sparsity, in contrast with the $2^{n-1}$ of \(\mathrm{MAJ}_n\) and \(\mathrm{EH}_n\), which are forced down by a symmetry. |
| AND-OR tree (depth 2) total | \(2^N = 2^{n^2}\) putative | Full Fourier support: the closed form in the \(\hat{L}_1(f)\) note is nonzero for every $T$ (including $\hat f(\emptyset) = 1 - 2(1-2^{-n})^n$, which vanishes only at the degenerate $n=1$). Sparsity is therefore no better than the trivial bound even though $\mathrm{C} = \sqrt N$. |
| NAND tree (balanced AND-OR formula) total | \(2^{N}\) putative | Full Fourier support. Every coefficient is a product of the factors in the \(\hat{L}_1(f)\) recursion, none of which vanishes because $\Pr[f_j = 1] \notin \{0,1\}$ at every level; brute force confirms $2^N$ nonzero coefficients for $d \le 4$. |
| Recursive MAJORITY-of-3 total | \(2^{\Theta(N)}\) putative | The same factorisation as for \(\hat{L}_1(f)\), now counting terms instead of adding them: $\mathrm{spar}(f\circ g^n) = \sum_{A \in \mathrm{supp}\widehat f} \mathrm{spar}(g)^{|A|}$, since every Fourier coefficient of the composition is a single product and nothing cancels. Here $\mathrm{spar}(d) = 3\,\mathrm{spar}(d-1) + \mathrm{spar}(d-1)^3$ from $\mathrm{spar}(0)=1$: $4, 76, 439204, \dots$, so $\log_2\mathrm{spar} = \Theta(3^{\,d}) = \Theta(N)$. (Checked exhaustively at $d = 2$.) |
| Kushilevitz's function (iterated) total | \(2^{\Theta(N^{0.6131})}\) putative | The same factorisation as for \(\hat{L}_1(f)\), counting terms instead of adding them: $\mathrm{spar}(f\circ g^n) = \sum_{A\in\mathrm{supp}\widehat f}\mathrm{spar}(g)^{|A|}$. With the ten triples and six singletons of $\widehat K$ this is $\mathrm{spar}(k) = 6\,\mathrm{spar}(k-1) + 10\,\mathrm{spar}(k-1)^3$ from $\mathrm{spar}(0)=1$: $16, 41056, 6.9\cdot10^{14},\dots$, so $\log_2 \mathrm{spar} = \Theta(3^k) = \Theta(N^{\log_6 3})$. Sparsity is therefore governed by the degree, not by $N$: $K^{\circ k}$ has only $2^{N^{0.62}}$ of the $2^N$ possible coefficients, matching $\widehat L_1$. |
| Rubinstein's function total | \(\Theta(2^N)\) putative | Near-maximal. Sparsity multiplies over the disjoint blocks, and the gadget misses only the $S$ that split exactly half of the $n/2$ pairs: $\hat g(S) = 2^{-n}\sum_j(-1)^{|S\cap\{2j-1,2j\}|}$ vanishes iff exactly $n/4$ pairs are split, so $\mathrm{spar}(g) = 2^n - \binom{n/2}{n/4}2^{n/2}$ for $n/2$ even and $2^n$ otherwise. Hence $\mathrm{spar}(f) = \mathrm{spar}(g)^n = (1-o(1))2^N$. |
| AND composed with NOT-EXACT-HALF total | \(2^{N-\sqrt N}\) putative | Sparsity is multiplicative over disjoint blocks, and the gadget has exactly $2^{n-1}$ nonzero coefficients: $\hat g(S)$ is $2^{-n}$ times a Krawtchouk value $K_{n/2}(|S|)$, which vanishes for every odd $|S|$ (complementation fixes the middle slice) and is nonzero for every even $|S|$ (checked for $n \le 18$). So $\mathrm{spar}(f) = (2^{n-1})^n = 2^{N-\sqrt N}$, near-maximal. |
| Surjectivity total | \(2^{\Theta(n)}\) putative | Sparsity never increases under restriction, since the Fourier support of a restriction is a projection of the original support. On the restriction of the \(\deg_2(f)\) entry, $\pm1$-valued $f=1-2\prod_i(1-\mathrm{AND}_{\log_2 R})$: the blocks are disjoint, every one of the $2^{\log_2 R}$ coefficients of $1-\mathrm{AND}$ is nonzero, and coefficients multiply, so the product has $2^{(R+1)\log_2 R}=2^{\Theta(n)}$ nonzero coefficients. The ceiling is $2^n$. |
| Triangle finding total | \(2^{\Theta(m^2)}\) putative | Sparsity does not increase under restriction, and the restriction of \(\deg_2(f)\) is $\mathrm{OR}_t$ with $t=\binom{m-1}2$, whose $\pm1$ form $1-2\prod_i(1-x_i)$ has all $2^t$ Fourier coefficients nonzero. The ceiling is $2^{\binom m2}$. |
| Inner product mod 2 total | \(2^n\) | Bent: no Fourier coefficient vanishes. This is the maximum possible, and with \(\oplus_n\) (where $\mathrm{spar} = 1$) it brackets the range. |
| Minsky-Papert one-in-a-box total | \(2^{N} = 2^{m^3}\) putative | Full: no Fourier coefficient vanishes. The boxes are disjoint, so $\hat f(S) = \prod_j \hat g_j(S_j)$ where $g_j$ is the box $\mathrm{OR}_{m^2}$, and every coefficient of $\mathrm{OR}_k$ is nonzero ($1-2^{-k}$ on the empty set, $-2^{-k}$ elsewhere). Together with $\mathrm{L}_1 = \Theta(2^{m})$ this puts MP at the opposite corner from \(\mathrm{SINK}_m\): maximal sparsity, tiny spectral norm. |
| Sink of a tournament total | \(m2^{m-1} - m^2 + 1 = \Theta(m2^{m})\) putative | A set $S$ has $\hat F(S) \ne 0$ iff $|S| \ge 2$ and $S$ lies inside some star (each star has $2^{m-1}-m$ such subsets, and no two stars share one), plus the empty set. Singletons cancel exactly: the edge $uv$ appears in the star at $v$ with the opposite sign to the star at $u$. Verified exhaustively for $m = 3,4,5$ (the empty coefficient also vanishes at $m = 4$, where $\mathrm{SINK}_4$ happens to be balanced, so the count is one lower there). Note $\log_2\mathrm{spar} = \Theta(m) = \Theta(\mathrm{D})$ while $\mathrm{L}_1 = O(m)$ -- sparse and of small spectral norm. |