coConsider 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) = 2^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) = 2^n$ for $t \leq n$.