Boolean functions with small approximate spectral norm

Boolean functions with small approximate spectral norm, Discrete Analysis 2024:6, 22 pp.

Let $G$ be a finite Abelian group and let $f:G\to\mathbb C$. A quantity of considerable interest in many contexts is the spectral norm of $f$, that is, the $\ell_1$ norm of the Fourier transform $\hat f$. One way to interpret this is as a measure of “how much randomness” $f$ exhibits, since by the duality of $\ell_1$ and $\ell_\infty$ we can rewrite it as
$$\max\{|\langle f,g\rangle|:\|\hat g\|_\infty\leq 1\}.$$
The quantity $\|\hat g\|_\infty$ is small if and only if every Fourier coefficient of $g$ is small, which can be interpreted as saying that $g$ is “arithmetically random” in a certain sense. Therefore, if there is some small $\delta>0$ such that $|\langle f,g\rangle|\leq\delta\|\hat g\|_\infty$ for every $g$, then we learn that not only is $f$ not random in this sense, but it does not even correlate with any random function.

One expects functions that are “everywhere non-random” in a sense like this to have some kind of interesting structure, and there are some interesting results that show that various precise versions of this intuition are indeed true. Of particular relevance to this paper is results about functions that take values in $\{0,1\}$, and what it says about such a function if its spectral norm is bounded.

If $f$ is the characteristic function of a subgroup $H$ of $G$ and $\chi:G\to\mathbb C$ is a character, then $\hat f(\chi)=0$ unless $\chi$ vanishes identically on $H$, in which case it is $|H|/|G|$. Using the structure theorem for finite Abelian groups, one can show quite easily that the number of characters that do not vanish identically on $H$ is $|G|/|H|$, from which we deduce that $\|\hat f\|_1=1$ for such functions.

From that we can deduce that any 01-valued function that can be expressed as a linear combination $\sum_i\lambda_i\mathbf 1_{H_i}$ has spectral norm at most $\sum_i|\lambda_i|$. Also, since we have the simple inequality $\|\hat f*\hat g\|_1\leq\|\hat f\|_1\|\hat g\|_1$, the convolution law implies that if $f$ and $g$ have bounded spectral norm, then so does their pointwise product $fg$.

A theorem known as Cohen’s idempotent theorem gives the following converse to the above observations. If $G$ is a finite Abelian group (in fact, the theorem is more general and applies to locally compact Abelian groups), and $f:G\to\{0,1\}$ is a function with bounded spectral norm, then $f$ is the characteristic function of a set built out of a bounded number of characteristic functions of cosets of subgroups of $G$ using Boolean operations, where the second bound depends only on the first. This theorem was given a second proof by Green and Sanders, who obtained a reasonable quantitative estimate for the dependence – Cohen’s proof was qualitative. The number of cosets needed is referred to as the coset complexity of $f$.

This paper addresses the following question: what if instead of asking for $f$ to have a small spectral norm, we ask only that it should be approximated (uniformly) by a function with small spectral norm?

It is not immediately obvious that this gives us any new examples, but the authors show in the paper (see Lemma 3) that if $f:\mathbb F_2^k\to\{0,1\}$ is the function that takes the value 1 at $x$ if and only if $x$ has at most one non-zero coordinate, then the spectral norm of $f$ is at least $\sqrt k/2$, but for every $\epsilon\in(0,1/2)$ there is a function $g$ with spectral norm at most $5\log(1/\epsilon)$ such that $\|g-f\|_\infty\leq\epsilon$. Thus, for any fixed $\epsilon$ in this range we can find a sequence of functions $f_k$ such that $f_k$ has unbounded spectral norm but can be uniformly approximated to within $\epsilon$ by a sequence of functions $g_k$ with bounded spectral norm.

In the light of this example, what can one hope to prove about Boolean functions defined on $\mathbb F_2^n$ with small approximate spectral norm? The best one could hope for is to show that the above example is essentially the only obstacle, and that is exactly the type of result that the authors show. More precisely, they define a set $A$ to be $k$-affine connected if there does not exist a $k$-dimensional coset of a subspace that intersects $A$ in a set of $k+1$ affinely independent vectors. It is straightforward to show that if either $A$ or $A^c$ is not $k$-affine connected, then the spectral norm of the characteristic function of $A$ is at least $\sqrt k$. The authors prove a much less obvious converse to this (Theorem 2 in the paper), which implies that if $A$ and $A^c$ are both $k$-affine connected and the characteristic function of $A$ has bounded approximate spectral norm, then $A$ has bounded coset complexity (where the bound depends on $k$, the $\epsilon$ that comes from the approximation, and the size of the $\epsilon$-approximate spectral norm – note that the result becomes stronger as $\epsilon$ approaches 1/2).

Some of the proof follows similar lines to that of Green and Sanders, but at a crucial point a new approach is needed, which takes the form of a sophisticated inductive argument. Thus, among other things this paper provides a new proof of the result of Green and Sanders. Unfortunately, where Green and Sanders obtain exponential bounds, the bounds in this paper are of tower type: it is an interesting open question to determine whether those are necessary.

The concluding section of the paper discusses this and other interesting questions that arise naturally out of the paper, as well as placing the results in a wider complexity-theory context.