The definition of submodularity led me to define a type of function on numbers (I suppose ordered rings, but consider the reals for now) as $f(x) + f(y) \ge f(x+y) + f(xy)$. Such functions exist: for example, the constant functions.

I can infer some basic properties of these functions: plugging in $x = 1$ and $y = c-1$ yields $f(1) \ge f(c)$ so 1 is a global maximum; similarly, $x = 2$ and $y = 2$ yields $f(2) \ge f(4)$. Another property of interest is that if $f$ is differentiable at $x$ and 0, $y = \epsilon$ gives $f(x+\epsilon) - f(x) \le f(\epsilon) - f(x\epsilon)$ and letting $\epsilon \rightarrow 0$ yields $f'(x) \le (1-x)f'(0)$. (edit: thanks kingW3)

Can anyone characterize such functions more completely? Are there any such functions beside the constant ones? I am having difficulty coming up with one.

  • 1
    $\begingroup$ Doesn't plugging in $y=\epsilon$ gives $f(x+\epsilon)-f(x)\leq f(\epsilon)-f(x\epsilon)$? $\endgroup$
    – kingW3
    May 1, 2014 at 21:10

1 Answer 1


The differentiable functions satisfying the inequality are functions of the form $f(x) = \left(x-\frac{x^2}{2}\right)a+b$ for constants $a \ge 0$ and $b$.

As mentioned in the OP, plugging in $y=\epsilon$ gives $f(x+\epsilon)-f(x) \le f(\epsilon)-f(x\epsilon)$ and letting $\epsilon \rightarrow 0$, we get $f'(x) \le (1-x)f'(0)$; furthermore, plugging in $y=-\epsilon$ gives $f(x-\epsilon)-f(x) \le f(-\epsilon)-f(x\epsilon)$ and letting $\epsilon \rightarrow 0$ gives $f'(x) \ge (1-x)f'(0)$. Thus $f'(x) = (1-x)f'(0)$ so $f(x) = \left(x-\frac{x^2}{2}\right)a + b$ for some $a$ and $b$.

We can see that any such function with $a \ge 0$ works. For arbitrary inputs $x=u$ and $y=v$, $f(u)+f(v)-f(uv)-f(u+v)$ = $\left(u-\frac{u^2}{2}\right)a + \left(v-\frac{v^2}{2}\right)a - \left(uv-\frac{(uv)^2}{2}\right)a - \left(u+v-\frac{(u+v)^2}{2}\right)a$ = $a\frac{(uv)^2}{2}$. This expression $ \ge 0$, which is equivalent to satisfying the original inequality, iff $a \ge 0$.


You must log in to answer this question.

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