# Are the given sum of abolute value functions increasing?

We have the set $$\{0,\cdots,2^K-1\}$$ in binary representation, $$\{00,01,10,11\}$$ for $$K=2$$. Then each $$0$$ is replaced by $$b_k$$ and each $$1$$ is replaced by $$1-b_k$$, This gives the set $$B=\{b_1b_2,b_1(1-b_2),(1-b_1)b_2,(1-b_1)(1-b_2)\}$$ The same process is done in reverse order for the $$a_k$$s i.e., by replacing each $$0$$ by $$1-a_k$$ and each $$1$$ by $$a_k$$. The result is then $$A=\{(1-a_1)(1-a_2),(1-a_1)a_2,a_1(1-a_2),a_1a_2\}$$ Then, we find the absolute difference sum of these two sets: $$f(a_1,b_1,a_2,b_2)=|b_1b_2-(1-a_1)(1-a_2)|+|b_1(1-b_2)-(1-a_1)a_2|+|(1-b_1)b_2-a_1(1-a_2)|+|(1-b_1)(1-b_2)-a_1a_2|$$

Here, each $$(a_k,b_k)$$ satisfies $$1>a_K>\cdots>a_1>0$$ and $$0 and $$a_k+b_k<1$$.

Given any set of pairs $$(a_k,b_k)$$ for $$k\in\{1,\ldots,K\}$$, the function $$f$$ is non-increasing in every $$b_k$$.

Example: $$(a_1,b_1)=(0.1,0.2)$$ and $$(a_2,b_2)=(0.2,0.1)$$. Then if we take $$b_1$$ as variable we expect that $$f(0.1,b_1,0.2,0.1)$$ is decreasing for $$0. I verified that this is true in Mathematica. If we take $$b_2$$ as variable we expect that $$f(0.1,0.2,0.2,b_2)$$ is decreasing for $$0. This is also true according to Mathematica.

I guess this should be general for any example. I dont have any idea how to prove it, however.

First, let us replace $$a_i$$ with $$1-a_i$$ to simplify notation. Note that we now have $$b_i < a_i$$. We denote $$b_i^0 = b_i$$ and $$b_i^1 = 1-b_i$$. Let $$f(\vec{a}, \vec{b}) = \sum_{v\in\{0, 1\}^n}|\prod_{i=1}^nb_i^{v_i} - \prod_{i=1}^na_i^{v_i}|$$. We wish to show that $$\frac{\partial f}{\partial{b_i}} \leq 0$$ for $$i\in [n]$$.
By symmetry it suffices to show that $$\frac{\partial f}{\partial{b_1}} \leq 0$$. The trick is to group the terms of $$f$$ in pairs, with each pair consisting of the $$v$$'s with $$v_0$$ either $$0$$ or $$1$$, and the remaining $$v_i$$'s fixed. For $$w\in \{0, 1\}^{n-1}$$, let $$f_w = |b_1\prod_{i=2}^nb_i^{w_{i-1}} - a_1\prod_{i=2}^na_i^{w_{i-1}}| + |(1-b_1)\prod_{i=2}^nb_i^{w_{i-1}} - (1-a_1)\prod_{i=2}^na_i^{w_{i-1}}|$$. Since $$f = \sum_w f_w$$, it suffices to show that for each $$w$$, that $$\frac{\partial f_w}{\partial{b_1}} \leq 0$$.
Fix $$w$$ and note that $$f_w$$ consists of two terms. For $$\frac{\partial f_w}{\partial{b_i}}$$ to be positive, we must have that the first term without the absolute value sign is positive and the second is negative. But suppose $$b_1\prod_{i=2}^nb_i^{w_{i-1}} > a_1\prod_{i=2}^na_i^{w_{i-1}}$$. Then since $$(1-b_1)/b_1 > (1-a_1)/a_1$$, we can multiply to get $$(1-b_1)\prod_{i=2}^nb_i^{w_{i-1}} > (1-a_1)\prod_{i=2}^na_i^{w_{i-1}}$$. Thus each $$\frac{\partial f_w}{\partial{b_i}} \leq 0$$ and we are done.
• So this is proof by contradiction right? I have some confusion with the construction of $w$. For $n=2$, we need to have $w=0$ and $w=1$ cases. Inside multiplications we have $w_1$, which should always be $1$? It is not very clear to me. Other point is the symmetry. I think we can just flip the things like instead of $b_1(1-b_2)$ we can say $(1-b_2)b_1$, do this for all other cases and the result that we find for $b_1$ is what we also need for $b_2$, since this is true for all $b_i$, then just a single $b_i$ is sufficient. Did I get you right? May 21 '21 at 23:30
• I am writing $w = (w_1, \ldots, w_{n-1})$. So for $n = 2$, $w_1 = 0$ and $w_1 = 1$ are the two cases. For $w_1 = 0$, we have $f_w = |b_1b_2 - a_1a_2| + |(1-b_1)b_2 - (1-a_1)a_2|$. For $w_1 = 1$, we have $f_w = |b_1(1-b_2) - a_1(1-a_2)| + |(1-b_1)(1-b_2) - (1-a_1)(1-a_2)|$. You can check that for each of these $f_w$'s the derivatives are at most $0$ using the argument I give. Regarding symmetry, the point is that we don't use anything special about $b_1$ in the above argument, so the same argument can be made for any $b_i$. May 22 '21 at 18:51
• Yes. Exactly what I said and thought. But this argument can be made by reordering the multiplicative elements of the function. The About $w$ I had understood just found not perfectly clear. Thank you for the explanation. May 23 '21 at 14:24