# subadditive implies concave

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.

-

## 6 Answers

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$

-
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

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.

-

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.

-

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.

-

Subadditivity + $f(0)=0$ do not imply concavity, neither for regular functions. Counterexamples are in Bruckner "Some relationships between locally superadditive functions and convex functions", Proc. Amer. Math. Soc., 15, 1964, 61-65, and in Bruckner-Ostrow "Some function classes related to the class of convex functions", Pacific J. Math. 12, 1962, 1203--1215.

-

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}}$$

-
why is this f subadditive? – alex Aug 15 '10 at 23:26
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