Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Question

Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free monomials. (These $2^n$ monomials form a basis to the space of real functions on $\{-1,1\}^n$. The sum of the squares of the coefficients is simply $1$ so $f$ leads to a probability distribution on square free monomials. Let's call this distribution the F-distribution.

If f can be described by a bounded depth circuit of polynomial size then we know by a theorem of Linial, Mansour and Nisan that the F distribution is concentrated on monomials of $\text{polylog } n$ size up to almost-exponentially-small weight. This is derived from Hastad switching lemma. (A direct proof would be most desirable.)

What happens when we add mod 2 gates? One example to consider is the function $IP_{2n}$ on $2n$ variables which is described as the mod 2 inner product of the first n variables and the last n variables. Here the F-distribution is uniform.

Question: Is the F-distribution of a Boolean function described by bounded depth polynomial size AND, OR, MOD$_2$ circuit concentrated (up to superpolynomially small error) on $o(n)$ "levels"?

Remarks:

1. One possible path to a counterexample would be to "glue somehow" various IP$_2k$ on disjoint sets of variables but I don't see how to do it. Perhaps one should weaken the question and allow assigning some weights to the variables, but I don't see a clear way for doing it either. (So referring to these two matters is also part of what I am asking about.)

2. I would speculate that a positive answer to the question, (or to a successful variation) will apply also when you allow mod$_k$ gates. (So asking the question was motivated by Ryan Williams' recent impressive ACC result.)

3. For MAJORITY the F-distribution is large (1/poly) for every "level".

As shown by Luca, the answer to the question I asked is "no". The question that is left is to propose ways to find properties of the F distributions of Boolean functions that can be described by AND OR and mod 2 gates not shared by MAJORITY.

An attempt to save the question by talking about MONOTONE functions:

Question: Is the F-distribution of a MONOTONE Boolean function described by bounded depth polynomial size AND, OR, MOD$_2$ circuit concentrated (up to superpolynomially small error) on $o(n)$ "levels"?

We may speculate that we can even replace $o(n)$ by $\text{polylog} (n)$ so a counterexample for this strong version can be interesting.

Answer 1

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \oplus \cdots \oplus x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \oplus \cdots \oplus x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).