# On norms of Boolean functions

Let $$f: \mathbb{F}_2^n \rightarrow \{-1,1\}$$ be a Boolean function, represented by a $$N=2^n$$ dimensional vector, $$f \in \{-1,+1\}^N$$.

Define the Fourier transform of $$f$$ to be $$\hat{f}$$, where $$\hat{f}(x) = \frac{1}{N} \sum_{y \in \{0,1\}^n} (-1)^{x^T.y} f(y).$$

And lastly, define a function $$W: \{-1,+1\}^N \rightarrow \mathbb{R}$$, such that $$W(f)=\sum_i |\hat{f}(i)|$$. (See $$W$$ is the 1-norm of $$\hat{f}$$)

Now the question is

Given a vector $$f \in \{-1,1\}^N$$ such that $$W(f) = \delta \sqrt{N}$$, does there always exists a vector $$h \in \{-1,1\}^N$$, that differs from $$f$$ on atmost $$\epsilon N$$ coordinates and $$W(h) \geq W(f)+ \Omega(\epsilon) \sqrt{N}$$, for all $$\epsilon \leq 1 - \delta$$?

(This is asking can I always increase $$W(f)$$ (when $$W(f)$$ is not already the maximum) by changing any constant fraction of coordinates of $$f$$?) I can already prove that there exists such $$h$$ with $$W(h) \geq \Omega(\epsilon) \sqrt{N}$$. I conjecture the stronger version is also true.

Equivalently,

Let B being the Boolean hypercube, where each vertex $$u \in \{-1,1\}^N$$. And $$u$$ be a vertex with $$W(u)=\delta \sqrt{N}$$. For all vertices $$u$$, does there always exist a path of length $$\epsilon N$$ to a vertex $$v$$ with $$W(v) \geq W(u)+ \Omega(\epsilon) \sqrt{N}$$. for all $$\epsilon<1-\delta$$.

• interesting. can you indicate how your proof proceeds? – kodlu May 14 at 10:56