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$

• If $n \leq t < (n+1)$ then $\frac {f(t)} t \leq \frac {f(n+1)} n \leq \frac {(n+1)f(1)} n$ so $M \equiv \sup \frac {f(t)} t <\infty$. Now $f(x_1)+f(x_2)+...+f(x_i) \leq M(x_1+x_2+...+x_i)=nM$. This takes care of the maximum. I am yet to work on the minimum. – Kavi Rama Murthy Mar 5 '18 at 6:41
• Dear Sir, Can you please explain, how did you deduce that $\frac{f(t)}{t}\leq \frac{f(n+1)}{n}$ Since $f(t)$ is sub-additive, is it safe to say that $M\leq1$? As sub-additive functions always have the property that $f(t)\leq t$ – Vk1 Mar 6 '18 at 4:39
• Just note that $f(t) \leq f(n+1)$ and $t \geq n$, so $\frac {f(t)} t \leq \frac {f(n+1)} n$. If your function is also continuous at 0 then we can show that $f(x)=ax+b$ for some constants a and b and the answer to the question becomes trivial. However there are other convex sub-additive functions on $(0,\infty)$ an example being $f(x)=x+\frac 1 x$. For such functions I cannot think of better bounds. – Kavi Rama Murthy Mar 6 '18 at 4:58
• Thank you Sir... One last question. Is it true that if $f(x)$ (defined for $x>0$) is a convex, non-decreasing and sub-additive function, then $\sup f(t)/t$ is $O(1)$ aka some constant? OR can u show a counter example which does not have a constant as the sup – Vk1 Mar 6 '18 at 6:22
• If you are asking if $\frac {f(t)} t$ is bounded as $t \to \infty$ the answer is yes, but the bound of course depends on the function f. – Kavi Rama Murthy Mar 7 '18 at 5:50

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.