# Is a positive, monotone and sub-additive function concave?

Consider a function $f : [0, 1] \to \mathbb{R}^+$ such that $f(0) = 0$ and $f(x) \leq f(y)$ for all $x \leq y$ (i.e $f$ is monotone). Additionally, I also restrict $f$ to be a sub-additive function i.e $f(x+y) \leq f(x) + f(y)$.

I am trying to prove that such a function need not be concave. I believe that such a function does exist but cannot find a counter example. Is there a function that satisfies my requirements?

Ideally, I would like to find a function which is also continuous and differentiable but any function not satisfying these conditions would also be fine. I believe (no formal reason) that continuous and differentiable does force the function to become concave.

• Do you mean "concave", or "convex"? Sep 10, 2018 at 0:57
• I mean concave. Is this trivial? Sep 10, 2018 at 0:58
• @karmanaut See the related subadditive implies concave on MO.
– dxiv
Sep 10, 2018 at 1:30

Subadditivity is implied by a requirement that $$g(x) := \frac{f(x)}{x}$$ be monotonically decreasing. If $$g(x) \geq g(x+y)$$ and $$g(y) \geq g(x+y)$$, then $$f(x) + f(y) = x g(x) + y g(y) \geq x g(x+y) + y g(x+y) = f(x+y).$$ So any function $$f$$ that satisfies the other requirements can be subadditive as long as it does not intersect any line through the origin twice other than at the origin itself (though a single interval of coincidence with a given line through the origin, in addition to the intersection at the origin itself, is licit). This criterion is weaker than concavity (which requires that no line whatsoever intersect $$f$$ three times, including at the origin), and a large family of non-concave subadditive functions can be constructed as follows:

1. Take an increasing concave function $$g: [0, 1] \to \mathbb{R}$$ satisfying $$g(0) = 0$$.

2. Take some $$\xi \in (0, 1)$$.

3. Define $$f(x) = \max \left\{g(x), \frac{g(\xi) x}{\xi}\right\}$$. That is, $$f = g$$ on the interval $$[0, \xi]$$, and $$f$$ follows a continuation of the secant line from $$(0, 0)$$ to $$(\xi, g(\xi))$$ on the interval $$[\xi, 1]$$.

One function in this family is $$f(x) = \begin{cases} \sqrt{x} & x \leq \frac{1}{4} \\ 2x & x \geq \frac{1}{4}. \end{cases}$$

More generally, it's trivial to prove that if $$f$$ and $$g$$ are two subadditive functions, then $$\max\{f, g\}$$ is also subadditive, and not concave anywhere that $$f$$ and $$g$$ intersect and have different slopes.

EDIT: Since OP also asked for a smooth function, one example is $$f(x) = 3x^3 - 6x^2 + 4x = \frac{(3x-2)^3 + 8}{9} = [3(x-1)^2 + 1]x.$$ $$f$$ is not concave on the whole interval $$[0, 1]$$ (it has an inflection point at $$x = 2/3$$), but it is subadditive because $$f(x)/x$$ is monotone decreasing on $$[0, 1]$$.

• Excellent answer! Would you happen to have any intuition about what happens when $f$ is required to be differentiable in addition to continuity? Sep 10, 2018 at 1:48
• @karmanaut Any function can be approximated arbitrarily closely by smooth functions (for example, by convolutions with a Gaussian bump: en.wikipedia.org/wiki/Bump_function), so I don't think requiring differentiability should change anything. Sep 10, 2018 at 13:10