Spectral norm
Sum of absolute values of the Fourier coefficients.
also written:
Fourier L1 norm, \|\hat f\|_1
Definition
$\hat L_1(f)=\sum_S|\hat f(S)|$. Also called the spectral norm or approximate spectral norm (when only approximation is required, $\hat L_{1,\varepsilon}$). Central in the log-rank conjecture and in learning theory (the Kushilevitz-Mansour algorithm runs in $\mathrm{poly}(\hat L_1)$ time).
Parameters
\(\varepsilon\) (eps) default \(0\)
approximate version
Basic facts
- $\hat L_1(f)\le 2^{\mathrm{D}(f)}$ (sum the leaf indicators), and $\hat L_1(f)\ge 1$ always.
- Bounds of the form $\mathrm{D}^{\oplus}(f) = O(\hat L_1(f)^2)$ hold; sharpening them is tied to the log-rank conjecture.
- Relations of the shape $\deg_2(f)\le \log_2(\mathrm{spar}(f)+1)$ connect $\hat L_1$, $\mathrm{spar}$ and degree. Note it is the $\mathbb{F}_2$-degree: the real degree is not bounded by sparsity at all, since $\chi_{[n]}$ has $\deg = n$ and $\mathrm{spar} = 1$.
- For approximate versions, $\widetilde{\deg}(f)$ and $\hat L_{1,\varepsilon}(f)$ are the query analogues of approximate rank / approximate $\gamma_2$ in communication complexity.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\hat{L}_1(f)\). “\(\hat{L}_1(f)\) in terms of it” is the pair with \(\hat{L}_1(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 | \(3 - 2^{2-n}\) | From the same expansion: $|-1+2^{1-n}| + (2^n-1)\,2^{1-n}$. The spectral norm of OR is below $3$ for every $n$ -- a useful reminder that $\hat L_1$ is not a proxy for query complexity. ODonnell14 |
| AND total | \(3 - 2^{2-n}\) | Same computation as for OR. ODonnell14 |
| PARITY total | \(1\) | |
| MAJORITY total | \(\Theta\!\big(2^{n/2}/\sqrt n\big)\) putative | Exponentially large, in sharp contrast with $\hat L_1(\mathrm{OR}_n) < 3$. Upper: Cauchy-Schwarz against $\mathrm{spar} = 2^{n-1}$ gives $\hat L_1 \le 2^{(n-1)/2}$. The exact sum $\sum_{k \text{ odd}}\binom nk \big|\widehat{\mathrm{MAJ}}([k])\big|$, evaluated from the standard closed form for $\widehat{\mathrm{MAJ}}(S)$, is $\tfrac{2}{\sqrt\pi}\,2^{n/2}n^{-1/2}(1+o(1))$ -- so majority is within a $\sqrt n$ factor of the largest spectral norm any $n$-bit function can have. ODonnell14 |
| EXACT-HALF total | \(\Theta(2^{n/2}/\sqrt n)\) putative | Exactly $\binom{n}{n/2}2^{-n/2}$, from the closed form on the \(\mathrm{spar}(f)\) line: the binomials $\binom ns$ cancel and $\hat L_1 = 2^{-n}\binom{n}{n/2}\sum_{t}\binom{n/2}{t} = 2^{-n/2}\binom{n}{n/2}$. Asymptotically $\sqrt{2/\pi}\,2^{n/2}n^{-1/2}$ -- the same order as \(\mathrm{MAJ}_n\), and within $\sqrt n$ of the maximum possible, which is what Cauchy--Schwarz against $\mathrm{spar} = 2^{n-1}$ predicts. |
| ODD-MAX-BIT total | \(\Theta(n)\) putative | Exactly. The $2^{-(n-i+1)}$-weighted subcubes $B_i = \{x_i=1,\ x_j=0\ \forall j>i\}$ for odd $i$ partition $\mathrm{OMB}^{-1}(1)$, and $\mathbb{1}_{B_i} = 2^{-(n-i+1)}(1-\chi_i)\prod_{j>i}(1+\chi_j)$. Summing, a set $S$ with $\min S = t$ gets $\widehat{\mathrm{OMB}}(S) = \sum_{i \text{ odd},\, i \le t} 2^{i-n-1} - 2\cdot[t \text{ odd}]\,2^{t-n-1}$, whose absolute value is $\tfrac23 2^{t-n-1}(1+o(1))$ for either parity of $t$. There are $2^{n-t}$ sets with $\min S = t$, so each $t$ contributes $\tfrac13$ and $\hat L_1 = \tfrac{2n}{3}(1+o(1))$ in the $\pm1$ encoding. Linear, not exponential -- $\mathrm{OMB}$ is a sum of only $n/2$ subcube indicators, so it sits with \(\mathrm{OR}_n\) rather than with \(\mathrm{MAJ}_n\) on the spectral-norm scale, despite having full degree. |
| ADDRESS / multiplexer total | \(2^k\) | Write $\mathrm{ADDR}_k = \sum_a \mathbb{1}[\mathrm{addr}=a]\cdot y_a$: each term has spectral norm $1$ and the $2^k$ terms have disjoint Fourier supports, so the norms add. |
| Binary tree navigation total | \(2^{k-1}\) putative | Same recursion: the halving is exactly cancelled by the doubling of the number of terms, giving $\hat L_1(k) = 2\,\hat L_1(k-1)$ from $\hat L_1(1) = 1$. So $\hat L_1 = 2^{\mathrm{D}-1}$, the maximum a depth-$\mathrm{D}$ tree can have. |
| TRIBES total | \(2^{\Theta(n/\log n)}\) putative | Exactly $2^{s(1\pm o(1))}$ with $s = \Theta(n/\log n)$ tribes. Write $f = 1 - \prod_j (1-A_j)$ with $A_j = \prod_{i \in T_j} x_i$. In the $\pm1$ basis $A_j = 2^{-w}\prod_{i \in T_j}(1-\chi_i)$ has $\hat L_1(A_j) = 1$, so $\hat L_1(1-A_j) = (1-2^{-w}) + (1-2^{-w}) = 2 - 2^{1-w}$; the tribes are variable-disjoint, so the norms multiply and $\hat L_1\big(\prod_j (1-A_j)\big) = (2-2^{1-w})^s$. Subtracting the product from $1$ changes only the constant term. Since $w = \Theta(\log n)$, this is $2^{\Theta(n/\log n)}$ -- exponentially large, but exponentially far below the maximum $2^{\mathrm{D}} = 2^n$. ODonnell14 |
| AND-OR tree (depth 2) total | \(\Theta(2^n) = \Theta(2^{\sqrt N})\) putative | Exactly $\widehat{L}_1(f) = (2-2^{1-n})^{n+1} + |1 - 2(1-2^{-n})^{n}|$. In the $\pm1$ encoding the composed coefficients are $\hat f(T) = \pm 2^{1-n}(2^{1-n})^{|A|}(2-2^{1-n})^{\,n-|A|}$, where $A$ is the set of blocks $T$ touches, and all $T$ with the same $A$ share a sign, so the sum telescopes to a geometric one with no cancellation. Values $3.5,\ 9.71875,\ 23.719\ldots$ for $n = 2,3,4$. |
| NAND tree (balanced AND-OR formula) total | \(2^{\Theta(N)}\) putative | Because the two subtrees are on disjoint variables, $\hat f_d(T)$ is a single product term and the spectral norm obeys the exact recursion $A_d = A_{d-1}|1-\hat f_{d-1}(\emptyset)| + \tfrac12 A_{d-1}^2$ with $\widehat{L}_1 = |\hat f_d(\emptyset)| + A_d$. The quadratic term wins, so $\log_2 \widehat{L}_1(f_d) \to 0.29396\ldots\cdot N$. Exact small values $2,\ 3.5,\ 9.265625,\ 51.6915\ldots$ for $d = 1,2,3,4$ (checked against the full Fourier expansion). |
| Recursive MAJORITY-of-3 total | \(2^{\Theta(N)}\) putative | Balancedness kills the empty coefficient, so Fourier coefficients of the composition factor exactly and $\widehat L_1(f\circ g^n) = \sum_A |\widehat f(A)|\,\widehat L_1(g)^{|A|}$. With $\widehat{\mathrm{MAJ}_3} = \tfrac12(\chi_1+\chi_2+\chi_3-\chi_{123})$ this reads $\widehat L_1(d) = \tfrac32 \widehat L_1(d-1) + \tfrac12 \widehat L_1(d-1)^3$, starting from $2$; the cubic recursion gives $\log_2 \widehat L_1 \sim 0.26\,N$, against the universal ceiling $2^{N/2}$. (Values: $2, 7, 182, 3014557,\dots$) |
| Kushilevitz's function (iterated) total | \(2^{\Theta(3^k)}\) putative | Because $K$ is balanced, $\widehat{K}(\emptyset)=0$ and the Fourier coefficients of a composition factor exactly: $\widehat{f\circ g}(T) = \widehat f(A)\prod_{j\in A}\widehat g(T_j)$ where $A$ is the set of blocks $T$ touches. Hence $\widehat L_1(f\circ g^n) = \sum_A|\widehat f(A)|\,\widehat L_1(g)^{|A|}$ with no cancellation, i.e. $\widehat L_1(K^{\circ k}) = \tfrac32\widehat L_1(K^{\circ k-1}) + \tfrac52\widehat L_1(K^{\circ k-1})^3$ from $\widehat L_1(K)=4$. The cubic recursion gives $\log \widehat L_1 = \Theta(3^k) = \Theta(\deg)$, comfortably under the universal ceiling $2^{N/2}$. |
| Rubinstein's function total | \(2^{\Theta(\sqrt N\log N)}\) putative | Because the blocks are disjoint, $\widehat{L}_1(f) = |2(1-p)^n - 1| + 2\big[(1-p+\tfrac12 L')^n - (1-p)^n\big]$ exactly, where $L' = \sum_{S\ne\emptyset}|\hat g(S)|$ in the $\pm1$ encoding. For the gadget $\hat g(S)$ depends only on the number $t$ of pairs that $S$ splits, giving $L' = 2^{1-n/2}\sum_t \binom{n/2}{t}|n/2-2t| - 2p = \Theta(\sqrt n)$. Hence $\widehat{L}_1 = 2^{\Theta(n\log n)}$. Exact value $17.7578\ldots$ at $n = 4$, matching the full Fourier expansion. |
| AND composed with NOT-EXACT-HALF total | \(2^{\Theta(N)}\) putative | The blocks are disjoint, so $\widehat{L}_1(f) = |1 - 2q^n| + 2\big[\widehat{L}_1^{01}(\overline{\mathrm{EH}}_n)^n - q^n\big]$ with $q = 1-c$. The gadget's $0/1$ spectral norm is $2^{n/2}$ up to polynomial factors: Cauchy--Schwarz against $\sum_S \hat g(S)^2 = c$ gives $\widehat{L}_1^{01} \le \sqrt{\binom{n}{n/2}} \le 2^{n/2}$, and level $n/2$ alone contributes $\binom{n}{n/2}2^{-n}\binom{n/2}{n/4} = \Theta(2^{n/2}/n)$ when $n/2$ is even, because the Krawtchouk value there is $\pm\binom{n/2}{n/4}$. Hence $\widehat{L}_1(f) = 2^{(1/2-o(1))N}$. Exact value $19.1474\ldots$ at $n = 4$. |
| Surjectivity total | \(2^{\Omega(n/\log n)},\ O(2^n)\) | On the restriction of the \(\deg_2(f)\) entry the spectral norm multiplies over the disjoint blocks: $\hat L_1(\prod_i(1-\mathrm{AND}_s))=(2-2^{1-s})^{R+1}$ with $s=\log_2 R$, and $\hat L_1(1-2P)\ge2\hat L_1(P)-1$, so $\hat L_1\ge2^{\Omega(R)}=2^{\Omega(n/\log n)}$. Restriction can only decrease $\hat L_1$. The ceiling is $\hat L_1\le2^{\mathrm{D}}=2^n$ (\(\hat{L}_1(f)\) vs \(\mathrm{D}(f)\)). |
| Triangle finding total | \(2^{\Omega(m)}\) putative | Restrict to $m/3$ vertex-disjoint triangles with all other edges set to $0$: the restriction is $\mathrm{OR}_{m/3}\circ\mathrm{AND}_3$, the blocks are disjoint so $\hat L_1$ multiplies, and $\hat L_1(\prod_i(1-\mathrm{AND}_3))=(2-2^{-2})^{m/3}$; with $\hat L_1(1-2P)\ge2\hat L_1(P)-1$ this gives $2^{\Omega(m)}$. Restriction can only decrease $\hat L_1$, and the ceiling is $2^{\mathrm{D}}=2^{\binom m2}$ (\(\hat{L}_1(f)\) vs \(\mathrm{D}(f)\)). |
| Inner product mod 2 total | \(2^{n/2}\) | $2^n$ coefficients of magnitude $2^{-n/2}$ each. Bent functions maximise $\mathrm{L}_1$ among all Boolean functions, so this is the extreme point of $\mathrm{L}_1 \le 2^{n/2}$. |
| Minsky-Papert one-in-a-box total | \(\Theta(2^m) = 2^{\Theta(N^{1/3})}\) putative | Writing $f$ in the $\pm1$ encoding, $F = 1 - 2^{1-m}\prod_{j}(1 - G_j)$ with $G_j$ the $\pm1$ form of $\mathrm{OR}_{m^2}$; the boxes are disjoint so the norms multiply, giving exactly $\hat L_1(F) = |1 - 2(1-2^{-m^2})^m| + 2(2^m-1)(1-2^{-m^2})^m = (1+o(1))\,2^{m+1}$. Checked exactly at box size $4$ with $2$ boxes ($6.03125$). |
| Sink of a tournament total | \(O(m) = O(\sqrt N)\) | Each of the $m$ disjoint conjunctions has spectral norm $1$ in the $\pm1$ normalisation, and spectral norm is subadditive. This -- a total function whose spectral norm is only $\sqrt N$ -- is what the refutation runs on. CMS19 |
| Scorpion graphs total | \(O(m^3) = O(N^{3/2})\) putative | For $m \ge 5$ the property is a disjoint union of $m(m-1)(m-2)$ subcubes, one per ordered triple, and the indicator of a subcube has spectral norm $1$; spectral norm is subadditive, so the $\pm1$ version has $\hat{\mathrm{L}}_1 \le 1 + 2m(m-1)(m-2)$. Like \(\mathrm{SINK}_m\), the scorpion is a total function whose spectral norm is only polynomial in $N$, against the $2^{\Theta(N)}$ of a generic function. The exhaustive values $16.5,\,40.6,\,99.1$ at $m = 5,6,7$ leave the constant, and indeed the exponent, unsettled. |