13
$\begingroup$

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.

$\endgroup$

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.