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 '14 at 21:10

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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