# submodular-like functions on $\mathbb{R}$

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.

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

## 1 Answer

The differentiable functions satisfying the inequality are functions of the form $f(x) = (x-\frac{x^2}{2})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) = (x-\frac{x^2}{2})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)$ = $(u-\frac{u^2}{2})a + (v-\frac{v^2}{2})a - (uv-\frac{(uv)^2}{2})a - (u+v-\frac{(u+v)^2}{2})a$ = $a\frac{(uv)^2}{2}$. This expression $\ge 0$, which is equivalent to satisfying the original inequality, iff $a \ge 0$.