Lower bound on sum of Fourier coefficients

Question

Let $f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$ be a Boolean function. Let the Fourier coefficients of this function be given by

$$ f^{\sim}(y) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x.y}$$

for each $y \in \{0, 1\}^{n}$. Let the spectral norm of $f$ be

$$||f||_{S} = \sum_{y \in \{0, 1\}^{n}} |f^{\sim}(y)|. $$

I am trying to prove

$$||f||_{S} \geq \frac{1}{2^{n/2}}.$$

I can get an upper bound of $\sqrt{2^{n}}$ on $||f||_{S}$ very easily, using Cauchy Schwarz and Parceval's theorem but I am struggling with the lower bound.

Answer 1

The bound you desire is much weaker than what is actually true. Since $|f^{\sim}(y)|\leq 1$, we have that $|f^{\sim}(y)|^2\leq |f^{\sim}(y)|$ and so

$$||f||_S=\sum_{y\in\{0,1\}^n}|f^{\sim}(y)|\geq\sum_{y\in\{0,1\}^n}|f^{\sim}(y)|^2=1$$

and thus $||f||_S\geq \frac{1}{2^{n/2}}$, but only since $\frac{1}{2^{n/2}}<1$.