# additive discrepancy under a multiplicative constraint

Consider four sequences of numbers, $$0 \le a_i, b_i, c_i, d_i \le 1$$, suppose they satisfy the following constraints:

(1). $$\sum_{i=1}^K a_i, \sum_{i=1}^K b_i, \sum_{i=1}^K c_i \ge 1/2 + \epsilon$$;

(2). $$\sum_{i=1}^K d_i \le 1/2 - \epsilon$$;

(3). $$a_i d_i = b_i c_i$$ for all $$i=1, \ldots, K$$.

Is it true that $$\begin{equation} \sum_{i=1}^K (|a_i - b_i| + |a_i - c_i|) = \Omega(\epsilon) ? \end{equation}$$

The following example shows that the absolute value and the sum is necessary: \begin{align*} a_1 = 1/2 + \epsilon, \quad &a_2 = \epsilon^2, \\ b_1 = 1/2 + \epsilon + \epsilon^2, \quad &b_2 = 0, \\ c_1 = 0, \quad &c_2 = 1/2 + \epsilon + \epsilon^2, \\ d_1 = 0, \quad &d_2 = 0. \end{align*}

Note that the following case is easy: if we have an explicit lower bound $$b_i \ge c > 0$$ for all $$i$$, then let $$j$$ be the index that maximizes $$c_i/d_i$$, then $$\begin{equation} a_j / b_j = c_j/d_j \ge (\sum_i c_i)/(\sum_i d_i) \ge 1 + \epsilon. \end{equation}$$ Hence $$\begin{equation} a_i - b_i \ge c\epsilon. \end{equation}$$ Similarly if we have a lower bound for $$c_i$$. Note that in these cases we don't even need the assumption that $$\sum_i a_i \ge 1/2 + \epsilon$$.

• There is no $d_i$ in that sum: did you mean that, or is it a mistake? Also, are the various conditions understood to hold for all $K \in \mathbb N$ (and the sequences to be infinite), or is $K$ fixed? – Alex M. Sep 21 '18 at 15:47
• Even though this problem has a pretty simple solution, I think it is nontrivial and somewhat intriguing. So, I don't understand the down vote. – Iosif Pinelis Sep 21 '18 at 17:38

$$\newcommand{\ep}{\epsilon}$$
It is not hard to show (see the proof at the end of this answer) that for any real $$a,b,c,d\ge0$$ such that $$ad=bc$$ we have $$\begin{equation}\tag{1} |a-b|+|a-c|\ge a-d. \end{equation}$$ Replacing here $$a,b,c,d$$ by $$a_i,b_i,c_i,d_i$$ and summing in $$i$$, we have $$\begin{equation} \sum_i (|a_i - b_i| + |a_i - c_i|)\ge\sum_i a_i-\sum_i d_i\ge2\ep, \end{equation}$$ as desired. (The conditions that $$\sum_i b_i, \sum_i c_i \ge 1/2 + \ep$$ were not needed or used here.)
Proof of (1). If $$a=0$$, then $$a-d\le0$$, so that (1) holds. So, without loss of generality (wlog), $$a>0$$, whence $$d=bc/a$$ and $$a-d=(a^2-bc)/a$$. So, wlog $$a^2>bc$$ and hence $$a\ge b\wedge c$$. Also, wlog $$c\le b$$. So, one of the following two cases takes place.
Case 1: $$0\le c\le b\le a$$. Here (1) can be rewritten as $$f(a,b,c):=a-b-c+bc/a\ge0,$$ which follows because $$f(a,b,c)$$ is nonincreasing in $$b$$ (given that $$c/a\le1$$) and hence $$f(a,b,c)\ge f(a,a,c)=0$$. So, (1) holds in Case 1.
Case 2: $$0\le c\le a\le b$$. Here (1) can be rewritten as $$g(a,b,c):=b-c+bc/a-a\ge0,$$ which follows because $$g(a,b,c)$$ is nondecreasing in $$b$$ and hence $$g(a,b,c)\ge g(a,a,c)=0$$. So, (1) holds in Case 2 as well.