# Partition of 4-tuples

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Can we always partition $\{1,2,\dots,n\}$ into two subsets $X,Y$ so that $$1+\sum_Xa_i\geq \sum_Ya_i\text{ and } 1+\sum_Xb_i\geq \sum_Yb_i$$ and $$\sum_Xc_i\leq 1+\sum_Yc_i\text{ and } \sum_Xd_i\leq 1+\sum_Yd_i?$$

It is shown here that the partition is possible if we replace the $1$'s by $3$'s. What is the best possible value between $1$ and $3$?

• Extreme cases may be useful here; one is $(1, 1, 1, 0), (1, 1, 0, 1), (1, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1)$. – user44191 Nov 10 '18 at 21:23
• @user44191 Putting the first two vectors into $X$, you get the required inequalities even without `$1+$'. – Ilya Bogdanov Nov 13 '18 at 22:33
• Since nobody seems to have mentioned it yet, let me say that this problem is practically equivalent to determine the highest possible (combinatorial) discrepancy that 4 sets ($\{a_1,\ldots,a_n\}$,$\{b_1,\ldots,b_n\}$,$\{c_1,\ldots,c_n\}$,$\{d_1,\ldots,d_n\}$) can have. The fact that this is some constant is obvious and the value of the constant is usually studied as a function of the number of sets (here 4). See this seminal paper by Spencer: ams.org/journals/tran/1985-289-02/S0002-9947-1985-0784009-0/… – domotorp May 20 '19 at 11:40

Mike Earnest's answer at MSE may be improved even more, in order to get the estimate of $$2$$ --- but this is also non-sharp. Indeed, in his last part, we may assume that $$x_1\geq x_2\geq x_3\geq x_4$$. Next, we may assume that $$x_2\geq 0$$.
Now, if $$x_3+x_4\leq 0$$, then we may set $$x_3'=x_4'=-1$$, $$x_1'=x_2'=1$$, changing each coordinate by at most 2.
Asusume now that $$x_3+x_4\geq 0$$ --- this is more delicate; then $$x_3\geq 0$$. Choose an index $$i\in\{1,2,3\}$$ such that $$a_i$$ is not the strict minimum among $$a_1,a_2,a_3$$, and $$b_i$$ is not the strict minimum among $$b_1,b_2,b_3$$. Then we set $$x_i'=-1$$ and $$x_j'=1$$ for all other $$j$$. Surely, the $$c$$- and $$d$$-coorditnates increased by at most 2 (this could happen due to $$x_i'$$ only!). Now let us show that $$a$$-coordinate did so as well. Let $$a_k=\min(a_1,a_2,a_3)$$ with $$k\in\{1,2,3\}\setminus\{i\}$$, and set $$\ell=\{1,2,3\}\setminus\{i,k\}$$. Then $$\sum(x_j'a_j-x_ja_j)=(1-x_4)a_4+(1-x_\ell)a_\ell+(1-x_k)a_k+(-1-x_i)a_i \leq (1-x_4)+(1-x_\ell)+(1-x_k-1-x_i)a_k\leq (2-x_4-x_\ell)+0\leq 2,$$ as required. The $$b$$-coordinate argument is similar.
NB. It seems that such considerations (by making an argument more case distinctive) may lead to a constant of $$3/2$$. But this still would not give an optimal bound --- at least it seems so!