Sum over Subadditive functions

203 Views Asked by At

Suppose $f(x)$ is a non-decreasing sub-additive convex function

In order words,

$f(x+y)\leq f(x)+f(y)$ for all $x,y$

and $f(x)\leq f(y)$ if $x\leq y$

Let $x_1,x_2\ldots x_i$ are $i$ positive integers such that their sum is $n$.

What will be the minimum and maximum value of $f(x_1)+f(x_2)+f(x_3)+\ldots+f(x_i)$ regardless of values of $x_1,x_2\ldots x_i$?

An ideal solution which I am looking for would of the form devoid of $x_j$ and just in terms of $n,f$ and $i$

1

There are 1 best solutions below

1
On BEST ANSWER

If f is convex and sub-additive then $g(t)=\frac {f(t)} t$ is a decreasing function : let $0<a<b$. Then $f(b) \leq (\frac a b)f(a)+(1-\frac a b) f(a+b)$ by convexity because $b=(\frac a b)a+(1-\frac a b) (a+b)$. By sub-additivity we get $f(b) \leq (\frac a b)f(a)+(1-\frac a b) \{f(a)+f(b)\}$ which gives $\frac {f(b)} b \leq \frac {f(a)} a$. Hence $m=\equiv inf_{ t \in [1,n]} \frac {f(t)} t =\frac {f(n)} n >0$ (assuming that $f(n) >0$). Hence $f(x_1)+f(x_2)+...+f(x_i) \geq mn$. See my earlier comment for an upper bound.