1

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$

Vk1
  • 99
  • 1
    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 05 '18 at 06: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 06 '18 at 04:39
  • 1
    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 06 '18 at 04: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 06 '18 at 06: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 07 '18 at 05:50

1 Answers1

1

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.

Kavi Rama Murthy
  • 311,013
  • Thanks for the comments. Is this the only possible upper bound and lower bound which can be achieved?

    Is there any other technique which could be used here?

    For example, some technique which gives solution without using inf and sup functions? Or some other formula?

     – Vk1 Mar 05 '18 at 17:41