2
$\begingroup$

Consider a Boolean function $f: GF(2)^n \rightarrow \{0, 1 \}$. I would like to show that if $f$ is sparse, i.e. $\sum f(i) \leq t$, then $f$ must have a large Fourier coefficient. (A Fourier coefficient is defined in the sense of the Walsh-Hadamard transform, $\hat{f} (\gamma) = \sum_i (-1)^{i \cdot \gamma} f(i)$ ).

That is, I want to find some function $F(n,t)$ such that if $\sum f(i) \leq t$, then there is some $\gamma$ with $|f(\gamma)| \geq F(n,t)$.

For example, if $t \leq n$, then there must exist $\gamma$ with $\hat f(\gamma) = n$; for if $x_1, \dots, x_t$ are the non-zero entries of $f$, then simply choose some $\gamma$ which is orthogonal to all of them. Thus, $F(n,t) = n$ for $t < n$.

EDIT: I am aware of the Parseval's identity, but this gives estimates which do not take into account the fact that $f$ is integer-valued. I am primarily interested in the case in which $t$ is quite small, on the order of $n$.

$\endgroup$
7
  • $\begingroup$ So $\gamma$ is again in $GF(2)^n$ and $.$ is the standard scalar product? $\endgroup$ May 2, 2015 at 15:19
  • $\begingroup$ Yes, $\gamma \in GF(2)^n$, and this is the standard dot-product. $\endgroup$ May 2, 2015 at 15:47
  • $\begingroup$ Then I don't quite understand - is not always $|\hat f(\gamma)|\le\sum f(i)$? I mean, $\hat f(\gamma)$ is placed between numbers obtained when either each $(-1)^{i\cdot\gamma}$ is $1$, or each of them is $-1$, i. e. between $\pm\sum f(i)$ $\endgroup$ May 2, 2015 at 17:22
  • 2
    $\begingroup$ I think Tom Sanders considered this question and may have had an argument to show that F(n,cn) > c' 2^n, where c' depends only on c, but I don't remember exactly. I'll ask him. I think this is closely related to the issue of getting a bound on the Sidon constant s(X \cup Y) in terms of s(X) and s(Y) (known, due to work of Rider in the 1970s), together with the fact that a dissociated subset of GF(2)^n is Sidon, where Sidon is in the harmonic analysis sense webpages.uidaho.edu/lnguyen/SidonSet_RieszProduct.pdf. $\endgroup$
    – Ben Green
    May 2, 2015 at 17:49
  • 2
    $\begingroup$ @Ben, Can you please expand on this, and either provide a citation or make it an answer? Thanks a lot $\endgroup$ May 2, 2015 at 20:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.