# Combinatorial optimization problem on sums of differences between real numbers

We are given an increasing sequence $$S$$ of positive real numbers $$x_1, x_2, \ldots, x_n$$, such that $$x_{i+2}-x_{i+1} \ge c\,(x_{i+1}-x_i)$$ for all $$i=1, 2, \ldots n-2$$, where $$c\ge 1$$ is constant. Each number $$x_i\in S$$ is associated with a positive integer weight $$w_i$$ for all $$i=1, 2, \ldots, n$$. Let $$W$$ be the sequence formed by these weights.

Finally, let $$A=\sum_{1\le i < j < k\le n} w_i w_j w_k(x_j-x_i)~,$$ and $$B=\sum_{1\le i < j < k\le n} w_i w_j w_k\min(x_k-x_j, x_j-x_i)~.$$

Question: What is the minimum value for $$c$$ such that, for all $$S$$ and $$W$$, we have $$A \le 2B~$$? (I am also interested in tight upper bounds).

Conjectures: I believe that $$c\ge \frac{3}{2}$$ is a sufficient condition to obtain $$A \le 2B$$ as required (I do not know whether it is also necessary). Furthermore, I think that the worst case w.r.t. $$W$$ occurs when $$w_{n}\gg n$$ and $$w_{n-1} \gg n$$, while all the other weights $$w_1, w_2, \ldots, w_{n-2}$$ are equal to $$1$$. Finally, I also conjecture that, for any $$\alpha\ge 2$$, $$c\ge 1+\frac{1}{\alpha}$$ is a sufficient condition to obtain $$A \le \alpha B$$.

• For fixed $i,j,k$, we have $\sum_{i < j < k} w_i w_j w_k\min(x_k-x_j, x_j-x_i)=w_i w_j w_k\min(x_k-x_j, x_j-x_i)?$ Jun 24, 2020 at 6:33
• Now, as I see, given $i < j < k$ we have $$s_{i,j,k}=w_i w_j w_k\min(x_k-x_j, x_j-x_i)\le w_i w_j w_k(x_j-x_i)\le \sum_{i < j <\ell} w_i w_j w_\ell(x_j-x_i)= s_{i,j}.$$ Jun 24, 2020 at 6:45
• Yes, it's correct. I can modify the notation if it's misleading. Thanks. Jun 24, 2020 at 8:56
• The notation is confusing. If I understand correctly, the sums in the definitions of $s_{i,j}$ and $s_{i,j,k}$ are both over all tuples $1<i<j<k<n$. If this is correct, you should call the sums $A$ and $B$ or something. If I'm misunderstanding, and you want to be able to take, say $s_{2,4}$, then which variables are you varying as you take the sum? Jun 26, 2020 at 15:13
• You are right, the notation is confusing: Both sums are over all $i, j, k \in \{1, 2, \ldots, n\}$ such that $i < j < k$, that is over all tuples $1 \le i < j < k \le n$. Please note that we can have $i=1$ and $k=n$, which is different from writing "[...] over all tuples $1 < i < j < k < n$." Thank you very much for your answer, I will read it as soon as possible. Thereafter I will also change the notation according to your suggestions. Jun 26, 2020 at 18:31

I will assume $$c\le 2$$, since that seems to be the case you are interested in. The argument below is formulated in terms of taking a given $$c$$ and computing the optimal $$\alpha$$, but this is equivalent to your question and the result agrees with your conjecture.
Step 1: We can change the formulation of the question so that the weights can be any nonnegative real numbers. Say we have such weights. We can always convert them to positive integer weights while changing $$\frac{A}{B}$$ by arbitrarily small $$\epsilon$$. To do this, we approximate the real numbers by positive rational numbers, then scale all weights up by a large constant factor to make them all positive integers.
Step 2: We now pick some specific $$1\le i and set $$w_i=w_j=w_k=1$$ and set all other weights to $$0$$. Then $$\frac{A}{B}=\max\left(1,\frac{x_j-x_i}{x_k-x_j}\right)$$. Note that for $$\ell, we have $$x_{\ell+1}-x_\ell\le \frac{x_{j+1}-x_j}{c^{j-\ell}}\le\frac{x_k-x_j}{c^{j-\ell}}$$ with equality achieved when $$k=j+1$$ and all the ratios of successive differences are exactly $$c$$.
Then $$x_j-x_i=\sum_{\ell=i}^{j-1}x_{\ell+1}-x_\ell\le \sum_{\ell=i}^{j-1}\frac{x_k-x_j}{c^{j-\ell}}=(x_k-x_j)\sum_{a=1}^{j-1}\frac{1}{c^a}\le \frac{x_k-x_j}{c-1}$$ where equality is never achieved, but can be achieved to within an error of $$\epsilon$$ by taking $$k=j+1$$, taking $$j-i$$ large, and making all the ratios of successive differences be exactly $$c$$.
Thus for the special case of $$w_i=w_j=w_k=1$$ and all other weights being $$0$$, we have $$\frac{A}{B}\le \frac{1}{c-1}$$ and the bound is tight.
Step 3: Now if we allow arbitrary weights, we have that termwise the same inequality holds, that is $$w_iw_jw_k(x_j-x_i)\le \frac{1}{c-1}w_iw_jw_k\min(x_j-x_i,x_k-x_j)$$ and summing, we get $$A\le \frac{1}{c-1}B$$