Fourier dimension
Dimension of the F_2-span of the Fourier support.
Definition
The dimension of the linear span over $\mathbb{F}_2$ of $\{S : \hat f(S)\ne 0\}$, viewing sets as vectors. $\mathrm{D}^{\oplus}(f)\le\dim_{\mathbb{F}_2}(f)$ and this is the natural "number of relevant parities".
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\dim_{\mathbb{F}_2}(f)\). “\(\dim_{\mathbb{F}_2}(f)\) in terms of it” is the pair with \(\dim_{\mathbb{F}_2}(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 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | The Fourier support is all of $2^{[n]}$, whose $\mathbb{F}_2$-span is everything. |
| AND total | \(n\) | The Fourier support spans all of $\mathbb{F}_2^n$: it contains every singleton. |
| PARITY total | \(1\) | The Fourier support is the single set $[n]$. |
| MAJORITY total | \(n\) | The support contains every singleton (odd sets of size $1$ have nonzero coefficient), so it spans $\mathbb{F}_2^n$. |
| Threshold total | \(n\) putative | Every singleton is in the Fourier support: $\hat f(\{i\})$ is a nonzero multiple of $\binom{n-1}{k-1}$, which is exactly the statement that $\mathrm{MaxInf}(f) \ne 0$. The $n$ singletons already span $\mathbb{F}_2^n$. |
| EXACT-HALF total | \(n-1\) putative | $\mathrm{EH}_n(\bar x) = \mathrm{EH}_n(x)$, so only even-size sets carry Fourier weight and the support lies in the even-weight subspace of $\mathbb{F}_2^n$, of dimension $n-1$. It spans that subspace: every level-$2$ coefficient is nonzero, since conditioned on the middle slice $\mathbb{E}[X_iX_j] = -1/(n-1) \ne 0$. Note the singletons all vanish -- $\mathrm{EH}$ has no linear part at all. |
| ODD-MAX-BIT total | \(n\) putative | Full. By the computation on the \(\mathrm{D}^{\oplus}(f)\) line, $\hat g(S) = \pm2^{-(n-1)} \ne 0$ for every $S$ containing the coordinate $1$; in particular $\{1\}$ and $\{1,j\}$ are in the support, and their $\mathbb{F}_2$-sum is $\{j\}$. |
| ADDRESS / multiplexer total | \(k + 2^k\) putative | The Fourier support contains every singleton $\{y_a\}$ and every subset of the address bits, so it spans all $n$ coordinates over $\mathbb{F}_2$. |
| Binary tree navigation total | \(2^k - 1\) putative | Full. By the same recursion the support contains both $S$ and $S \cup \{0\}$ for every $S$ in the support of the left subtree, so their sum $\{0\}$ lies in the $\mathbb{F}_2$-span; inductively the span is everything. |
| TRIBES total | \(n\) putative | TRIBES is monotone, so $\hat f(\{i\}) = \mathrm{Inf}_i > 0$ for every $i$: the Fourier support contains all $n$ singletons and therefore spans $\mathbb{F}_2^n$. |
| AND-OR tree (depth 2) total | \(N = n^2\) putative | The Fourier support is everything (see \(\mathrm{spar}(f)\)), so its $\mathbb{F}_2$-span is all of $\mathbb{F}_2^{N}$. In particular the bound $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}$ is vacuous here: parity queries have no structure to exploit on a read-once formula. |
| NAND tree (balanced AND-OR formula) total | \(N\) putative | The Fourier support is everything (see \(\mathrm{spar}(f)\)), so its $\mathbb{F}_2$-span is all of $\mathbb{F}_2^{N}$ and the bound $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}$ is vacuous -- consistent with \(\mathrm{D}^{\oplus}(f)\) $= N$. |
| Recursive MAJORITY-of-3 total | \(N = 3^d\) putative | The Fourier support contains every singleton: $\widehat{\mathrm{MAJ}_3}$ is supported on $\{1\},\{2\},\{3\},\{123\}$, and taking the outer set $A = \{j\}$ at every level embeds each lower-level support set into a block, so by induction $\{\ell\} \in \mathrm{supp}\widehat{f}$ for every leaf $\ell$. Singletons alone span $\mathbb{F}_2^N$, so $\dim_{\mathbb{F}_2} = N$ and the bound $\mathrm{D}^{\oplus}\le\dim_{\mathbb{F}_2}$ is vacuous -- the real bound on \(\mathrm{D}^{\oplus}(f)\) here is the granularity one, which gives $(N+1)/2$. |
| Kushilevitz's function (iterated) total | \(N = 6^k\) putative | The Fourier support of the base contains all six singletons (the $-\tfrac14\sum_i\chi_i$ term of the formal expansion), and taking the outer set $A = \{j\}$ at every level embeds each lower-level support set into a block, so every singleton of $[N]$ is in $\mathrm{supp}\widehat{K^{\circ k}}$. Singletons span $\mathbb{F}_2^N$, so $\dim_{\mathbb{F}_2} = N$ even though $\mathrm{spar} = 2^{\Theta(N^{0.61})}$ is far from full. |
| Rubinstein's function total | \(N\) putative | Sparsity is near-maximal (see \(\mathrm{spar}(f)\)) and in particular the gadget's singleton coefficients $\hat g(\{i\}) = 2^{-n}(n/2-2)$ are nonzero for $n \ge 6$, so every singleton of $[N]$ lies in the Fourier support and its $\mathbb{F}_2$-span is everything. |
| Ambainis-Sun function total | \(\Theta(N)\) putative | Fourier dimension is squeezed by $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}(f) \le N$, and the \(\mathrm{D}^{\oplus}(f)\) entry gives $\mathrm{D}^{\oplus} = \Theta(N)$. |
| AND composed with NOT-EXACT-HALF total | \(n^2-n = N-\sqrt N\) putative | The gadget's Fourier support is exactly the even-size sets (see \(\mathrm{spar}(f)\)), which span the even-weight subspace of $\mathbb{F}_2^{n}$, of dimension $n-1$. Since the support of the composition is the product of the blocks' supports, its $\mathbb{F}_2$-span is the direct sum of the $n$ even-weight subspaces, of dimension $n(n-1)$. So $\mathrm{D}^{\oplus} \le N - \sqrt N$: parity queries save something here, but only a $\sqrt N$ additive term. |
| Ambainis' exact-quantum function total | \(\Theta(3^d)\) putative | Exactly $2\cdot3^{d-1}$. In the $\pm1$ encoding $\mathrm{NE}=\tfrac12(-1+y_1y_2+y_1y_3+y_2y_3)$, so the Fourier support of $\mathrm{NE}^d$ consists of the sets $S_i\triangle S_j$ ($i<j$) with $S_i$ in the support of child $i$; since $\emptyset$ is in each child's support for $d\ge2$, taking $\mathbb{F}_2$-sums of two such sets recovers every $S_i$, so the span is the direct sum of the children's spans and $\dim_d=3\dim_{d-1}$ with $\dim_1=2$. Verified exhaustively for $d\le2$ ($2$ and $6$). So $\mathrm{NE}^d$ depends on $\tfrac23 n$ independent parities -- no parity structure to exploit. |
| Surjectivity total | \(\Theta(n)\) | $\mathrm{D}^{\oplus}(f)\le\dim_{\mathbb{F}_2}(f)\le n$ (\(\dim_{\mathbb{F}_2}(f)\) vs \(\mathrm{D}^{\oplus}(f)\)), and $\mathrm{D}^{\oplus}=\Theta(n)$ here. |
| Triangle finding total | \(\Theta(m^2)\) | $\mathrm{D}^{\oplus}\le\dim_{\mathbb{F}_2}(f)\le\binom m2$ (\(\dim_{\mathbb{F}_2}(f)\) vs \(\mathrm{D}^{\oplus}(f)\)), and $\mathrm{D}^{\oplus}=\Theta(m^2)$. |
| Inner product mod 2 total | \(n\) | The support is all of $\mathbb{F}_2^n$, so its span is everything. |
| Minsky-Papert one-in-a-box total | \(N = m^3\) | Between $\mathrm{D}^{\oplus} = N$ and the arity $N$, since $\mathrm{D}^{\oplus}(f) \le \dim_{\mathbb{F}_2}(f) \le n$. |
| Sink of a tournament total | \(\binom m2 = N\) putative | Full, for $m \ge 4$. The support contains every pair of edges sharing a vertex, and those pairs already span all even-weight sets; it also contains $3$-subsets of a star once $m \ge 4$, so the span is all of $\mathbb{F}_2^{N}$. Verified exhaustively at $m = 4,5$. The Fourier-dimension bound $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}$ is therefore vacuous here, and the real $\mathrm{D}^{\oplus} = \Theta(\sqrt N)$ comes from sparsity instead. |
| Scorpion graphs total | \(\binom{m}{2} = N\) putative | Full. The Fourier support fails to span $\mathbb{F}_2^N$ exactly when $f(x \oplus a) = f(x)$ for some $a \ne 0$, since the shifted function has coefficients $(-1)^{a \cdot S}\hat f(S)$; no nonempty edge set $a$ can be flipped without ever destroying scorpionhood (flip an edge of $a$ at the sting of a scorpion whose triple avoids the rest of $a$). Confirmed by exhaustive computation for $m \le 7$. So a parity decision tree gets no help from a global change of basis, even though $\mathrm{D} = \Theta(\sqrt N)$. |
| Graph connectivity total | \(\binom{m}{2} = N\) putative | Full, so the Fourier support spans everything and no change of basis helps. The support lies in a proper subspace exactly when $f(x \oplus a) = f(x)$ identically for some $a \ne 0$, the shifted function having coefficients $(-1)^{a\cdot S}\hat f(S)$. Given $a \ne 0$, pick a vertex $u$ meeting some pair of $a$ and let $x$ be the graph consisting of the pairs of $a$ at $u$ together with all pairs inside $V \setminus \{u\}$: then $x$ is connected, while $x \oplus a$ deletes every edge at $u$ and adds none, isolating $u$. So no such $a$ exists. |