# 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.

## 1 Answer

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 & \text{if } \sum_i x_i > 0, \\ 0 & \text{if } \sum_i x_i < 0, \\ \ast & \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\}) &\leq 2^{-n} \sum_{k \geq n/2} (k-(n-k)) \binom{n}{k} \\ &= 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} \\ &= 2^{-n} n \binom{n-1}{ \lceil n/2 \rceil - 1 } \\ &= 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.