2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.