8
$\begingroup$

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.

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

1 Answer 1

9
$\begingroup$

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]$.

$\endgroup$
2
  • $\begingroup$ Excellent answer! Would you happen to have any intuition about what happens when $f$ is required to be differentiable in addition to continuity? $\endgroup$
    – karmanaut
    Sep 10, 2018 at 1:48
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 10, 2018 at 13:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .