Subset on boolean cube with largest sum of biases On the boolean cube $\mathcal{B}=\{0,1\}^n$, we assign each vertex a value by $p:\mathcal{B}\rightarrow[0,1]$. Let
$$\tilde{p}_i=\sum_{x\in\mathcal{B}}(-1)^{x_i}p(x).$$
What is the value of $\max_p\sum_{i=1}^n|\tilde{p}_i|$?



Since the objective $\sum_{i=1}^n|\tilde{p}_i|$ is convex on $p$, we can safely assume that $p(x)$ is either $0$ or $1$. So $p$ represents a subset of $\mathcal{B}$, and $|\tilde{p}_i|$ indicates the 'bias' of this subset on the direction of $x_i$. That's where the title comes from, but you can also think of it as bounding the L1 sum of some specific Fourier coefficients.

I tried to solve it combinatorially: let $f(n,k)$ denote the maximum value when $p$ represents a subset of size $k$. By considering the size of the intersection with $\{x\in\mathcal{B}\mid x_n=0\}$, we have the following recursive relation:
$$f(n,k)=\max_{0\leq\ell\leq k} f(n-1,\ell)+f(n-1,k-\ell)+|k-2\ell|,$$
for all $0\leq k\leq 2^{n-1}$. And clearly $f(n,2^n-k)=f(n,k)$. I ran a program to compute the first several terms of $\max_k f(n,k)$, which is always $f(n,2^{n-1})$:
$$1,2,6,12,30,60,140,280,630,\cdots$$
It seems to be $n\cdot\binom{n-1}{\lfloor n/2\rfloor}$, and this value can indeed by achieved when the subset consists of those $x$ with Hamming weight at most $\lfloor n/2\rfloor$.

It would be great to have a formal proof of this observation. A direct proof via the properties of Fourier coefficients on the boolean cube would be even better. Thanks in advance.
It will be slightly cleaner to replace $\{0,1\}^n$ with $\{-1,1\}^n$, and to normalize your function $\tilde{p}_i$ so that we get the $i$'th Fourier coefficient
$$
\hat{p}(\{i\}) = \mathbb{E}[x_i p].
$$
Let $\sigma_1,\ldots,\sigma_n \in \{ \pm 1 \}$. Then
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n \sigma_i x_i\right)p\right].
$$
If we define a function
$$ q(x_1,\ldots,x_n) = p(\sigma_1 x_1, \ldots, \sigma_n x_n) $$
then $q \in [0,1]$ and
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n x_i\right) q\right].
$$
Under the constraint $q \in [0,1]$, the right-hand side is clearly maximized when
$$
q = \begin{cases} 1 &amp; \text{if } \sum_i x_i &gt; 0, \\
0 &amp; \text{if } \sum_i x_i &lt; 0, \\
\ast &amp; \text{if } \sum_i x_i = 0, \end{cases}
$$
where $\ast$ means that the value doesn't matter. In other words, $q$ is the majority function, and so
$$
\begin{align}
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) &amp;\leq 2^{-n} \sum_{k \geq n/2} (k-(n-k)) \binom{n}{k} \\ &amp;=
2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k-1} - 2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k} \\ &amp;=
2^{-n} n \binom{n-1}{ \lceil n/2 \rceil - 1 } \\ &amp;=
2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
\end{align}
$$
Therefore
$$
\sum_{i=1}^n |\hat{p}(\{i\})| \leq \max_\sigma \sum_{i=1}^n \sigma_i \hat{p}(\{i\}) \leq 2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
$$
Furthermore, this is achieved for the majority function.