# 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

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