Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise.

For a boolean function $f: \{0,1\}^n \to \{0,1\}$, consider its Fourier coefficients defined, as usual, in the following way: $\hat{f}(\alpha) = \mathbb{E}_x[f(x)\cdot (-1)^{\langle \alpha, x\rangle}]$. Is there a characterization of the sign-pattern of Fourier coefficients of boolean functions?

Note that there are $2^{2^n}$ many boolean functions $f: \{0,1\}^n \to \{0,1\}$ and the same number of sign-pattern sequences of length $2^n$. But not all of the $2^{2^n}$ sequences can be realized. To see this, let $b$ be a bent function where each nonzero Fourier coefficient is $\pm 2^{-n/2}$, and let $b'$ be a boolean function which differs from $b$ at exactly one point. Clearly, each Fourier coefficient of $b'$ differs from that of $b$ by $\pm 2^{-n}$, so that the sign pattern of the Fourier coefficients of $b$ and $b'$ are the same.

I'd like to conjecture that the number of possible sign-patterns for Fourier coefficients of Boolean functions is at most $c\cdot 2^{2^n}$ where $c$ is a constant less than 1. But any information about signs of Fourier coefficients is very welcome.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.