I have the following conjecture about bounded functions on the hypercube. Any help resolving it (proof, counterexample, some ideas) is much appreciated.

Conjecture. Let $f : \{ -1, +1 \}^n \to [-1, +1]$ and $p \in [0,1/2]$. Suppose $\left| \widehat{f}(S) \right| \leq p^{|S|+1}$ for all $S \subseteq [n]$. Then $\mathrm{Var}\left[ f \right] \leq p^{\Omega(1)}$.

Here $f(x) = \sum_{S \subseteq [n]} \widehat{f}(S) \prod_{i \in S} x_i$ for all $x \in \{ \pm 1\}^n$ defines the usual Fourier transform. It's clear that $$\mathrm{Var}\left[ f \right] = \sum_{S \ne \emptyset} \widehat{f}(S)^2 \leq \sum_S p^{2|S|+2} = p^2 (1+p^2)^n,$$ but, unless $p \leq \tilde{O}(1/\sqrt{n})$, this is worse than the trivial $\mathrm{Var}\left[ f \right] \leq 1$. I'm interested in $p = (1/\log n)^{O(1)}$. I don't know exactly what the right bound on the variance of $f$ should be.

My motivation comes from the area of pseudorandomness, but this seems to be an interesting question about discrete Fourier analysis in its own right. In particular, this seems related to the majority is stablest theorem: Suppose $f = T_p(g)$ for some balanced $g : \{\pm 1\}^n \to \{\pm 1\}$ with $\mathrm{Inf}_i(g) \leq p^2$ for all $i$, where $T_p$ is the noise operator. Then $f$ satisfies the hypotheses of the conjecture and the variance of $f$ is the noise stability of $g$, which is bounded by $O(p)$ as a consequence of majority is stablest.



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.