Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $f:R_+\to R_+$ be smooth on $(0,\infty)$, increasing, $f(0)=0$ and $\lim_{x\to\infty}=\infty$. Assume also that $f$ is subadditive: $f(x+y)\le f(x)+f(y)$ for all $x,y\ge 0$. Must $f$ be concave? The converse is obvious.

share|improve this question
add comment

5 Answers

up vote 7 down vote accepted

For not smooth surely not, take $f(x)=2x+|\sin x|$. I am nearly sure that for smooth answer is the same. For example, it looks like function $|\sin x|$ may be changed near points $\pi k$ so that it becomes smooth but still semiadditive.

well, more concrete construction is like follows (some details are however omited)

construct a function $f$ such that $f(x)=|\sin x|$ unless $|x-k\pi|<1/100$ for some positive integer $k$, $\sin 1/100\geq f(x) > \sin 1/100-1/1000000$ for $|x-k\pi| < 1/100$, $f$ is convex on $[k\pi-1.100,k\pi+1/100]$. When may $f(x+y) \le f(x)+f(y)$ fail? If $f(x+y)=|\sin(x+y)|$ then $f(x+y)\le |\sin x|+|\sin y|\le f(x)+f(y)$. If $f(x+y)\ne |\sin (x+y)|$, then $f(x+y)\le \sin(1/100)$, so if $f(x)+f(y) < f(x+y)$, then also $f(x) < \sin(1/100)$ and $f(y) < \sin(1/100)$. If both $x$ and $y$ are greater then $1/100$, then $f(x)+f(y) > 2(\sin(1/100)-1/1000000) > 1/100 > f(x+y)$.

Now without loss of generality $k\pi < y< x+y< k\pi+1/100$. Then $f(x+y)-f(y)=xf'(\theta)$ for some $\theta\in [y,x+y]$, by convexity $f'(\theta)\le \cos 1/100$. So, it suffices to prove that $x\cos(1/100)\le \sin x$, i.e. $\sin x/x\geq \cos 1/100$. Since $\sin t/t$ decreases on $[0,1/100]$, we have $\sin x/x\geq 100\sin 1/100\geq \cos 1/100$ as $\tan t > t$ for $t=1/100$

share|improve this answer
    
I'm not so sure about that intuition because x = k pi are where the subadditivity inequality is barely satisfied. –  Dan Brumleve Aug 16 '10 at 0:22
add comment

That the answer is "no" is also apparent (at least for the $C^0$ case) if you refer to the graphical interpretation of concavity and subadditivity of the function $f$ in terms of the sub-graph of $f$, here denoted S(f). "Concavity" is, of course: S(f) is convex; "subadditivity" is: a translation of S(f) that brings the origin to any point of graph(f), covers entirely graph(f) from that point on. Any increasing function with a suitable zig-zag shaped graph enjoys this property, while is not concave.

share|improve this answer
add comment

Let me try again (I deleted an earlier wrong post). First of all, a sufficient condition for subadditivity on $x>0$ is: $f(x)/x$ nonincreasing. This is easier to work with since it is a local condition. The proof is elementary (take $x\ge y>0$, then $f(x+y)\le f(x)(x+y)/x=f(x)+yf(x)/x\le f(x)+f(y)$). For smooth $f$ this is equivalent to $f'\le f/x$.

Thus it is sufficient to look for a non concave function $f(x)$ which is smooth on $(0,\infty)$, has right limit zero at zero, and satisfies on $x>0$ the inequalities $$ 0\le f'(x) \le \frac f x.$$

Now, take $f=x^a$ with $ 0 < a < 1 $; we may start with any example, but just to fix the ideas. This is a concave function satisfying all the requirements of the problem. Notice that actually there exists $d>0$ such that $$ d\le f'(x) \le f'(x)+d \le \frac f x \text{ on } (0,1].$$ Any function satisfying this condition is a good starting point. We shall modify $f$ on a compact subset of $(0,1)$ so to make it non concave near a point. Let us take a smooth non negative cutoff $g \in C^2_c(0,1)$ such that $|g'|\le 1$ and define $f_t=f+tg$, for $t$ a small positive constant. We have $f'_t=f'+tg'$, so if we restrict $t$ to $ 0 < t < d $ we have $$ 0 \le f_t'\le \frac {f_t} x $$ everywhere. It is clear that $f_t$ for all $ 0 < t < d $ satisfies all the requirements of the problem. Can we choose $g$ so to make $f_t''(1/2)>0$? We have $$ f''_t(x_0)=f''(x_0)+t g''(x_0) $$ so in conclusion we are looking for a smooth function supported in a compact subset of $(0,1)$, non negative, such that $$ |g'|\le1 \text{ and } g''(1/2)\ge N $$ for a fixed $N$ arbitrarily large. This obviously exists, e.g. take a piecewise linear function and approximate it with test functions.

share|improve this answer
add comment

Here is a sketch of how you could do this.

Start with a concave function f (ADDED: also, f satisfies all the conditions stated in the question). Consider now the interval $(1,1.1)$. We will try to modify f by increasing its value on this interval while preserving the values at the endpoints. Let's set aside smoothness for now.

What properties should the modified f have? Subadditivity is threateneded only in cases where the $x + y$ happens to land inside $(1,1.1)$. Because of the concavity up to 1, we can see that it suffices to ensure that the new variant $f_1$ of f satisfy:

$$f_1(1 + \epsilon) \le f(1) + f(\epsilon)$$

Basically, we can move the subadditivity condition to the boundary because of the known concavity property of f.

Thus, $f_1$ can be chosen arbitrarily subject to taking the correct boundary values and to being bounded from above by the expression indicated. Assuming strict concavity, there is some free space between the actual current function $f$ and the upper bound for $f_1$ given by the equation. We can therefore choose a $f_1$ that works. Maintaining the condition of being increasing is not problematic -- even if it were, we could just add a huge coefficient linear function to $f_1$ and make it increasing. Smoothness is the relatively harder part, but it could be fixed using bump functions.

EDIT: There's another constraint, that again is achievable: subadditivity when both $x$ and $x + y$ are in the interval $(1,1.1)$.

I also think that functions such as $2x + \sqrt{x}e^{-(x-1)^2}$ or variants thereof may work directly, but I don't know of any easy analytical proof of it.

share|improve this answer
add comment

How about this one... $f'(x) = ((x-5)/(x+1))^2$. So (according to Maple) $$ f(x) = -\frac{-37x - x^{2} + 12 \ln (x + 1) + 12 \ln (x + 1) x}{x + 1} $$ Now $f$ is not concave, since $f'$ is increasing above $5$.

EDIT Next attempt ... $$ g(x) = \frac{x \bigl(53140 x^{3} + 212550 x^{2} + 314500 x + 240625 + x^{4}\bigr)}{(x + 1)^{4}} $$ so that $$ g'(x) = \frac{(x + 25) \bigl(x^{2} - 10 x + 385\bigr) (x - 5)^{2}}{(x + 1)^{5}} $$ and $$ g''(x) = \frac{-25920(x - 5) (x - 10)}{(x + 1)^{6}} $$

share|improve this answer
2  
why is this f subadditive? –  alex Aug 15 '10 at 23:26
1  
Nice. Another way to write f(x) is x - 12 (log(1 + x) + 3/(1 + x) - 3) which makes it more apparent to me that f is subadditive. –  Dan Brumleve Aug 15 '10 at 23:37
    
Except actually it's not: 922.658 = 2 * f(500) < f(1000) = 953.059 –  Dan Brumleve Aug 15 '10 at 23:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.