Does the following statement imply convexity?

Question

I apologize if this is a simple question or if this is not the right forum for it. Some background: the subadditivity of Shannon's entropy is credited to the concavity of $-x\log(x)$. So this got me thinking about the inverse:

Let $f:\mathbb{R}\to\mathbb{R}$ be such that for any $h>0$ and $y>x$ we have $$f(x+h)-f(x)\le f(y+h)-f(y)$$ Does this imply that $f$ is convex?

The statement is true if $f$ is continuous, but I have no idea about the general case. My gut feeling is that it's not and probably a counterexample would be some sort of a "hairy" function. I am looking for suggestions...

Answer 1

Your proposed inequality is certainly true, and indeed an equality, whenever $f$ is additive, but one can build almost-arbitrarily-bad additive functions by considering a Hamel basis for $\mathbb R$ as a $\mathbb Q$-vector space. Such functions (if not continuous) are bounded neither above nor below on any interval, hence not convex.

EDIT with more details: As @LiviuNicolaescu points out, every convex function is continuous, so it suffices to produce an example of a discontinuous such function. These exist (given choice, at least) in abundance, but here's one example. Let $\mathcal B$ be a Hamel basis of $\mathbb R$ (i.e., a basis for $\mathbb R$ as a $\mathbb Q$-vector space) containing $1$, and let $x$ be any element of $\mathcal B \setminus \{1\}$. Let $f$ be the unique $\mathbb Q$-linear extension to $\mathbb R$ of the characteristic function of $\{x\}$, viewed as a function $\mathcal B \to \mathbb R$. Since $f$ satisfies $f(a + b) = f(a) + f(b)$ for all $a, b \in \mathbb R$ (by $\mathbb Q$-linearity), it satisfies your proposed inequality, and indeed makes it an equality. Since $f$ vanishes on $\mathbb Q$ (because it vanishes at $1$ and is $\mathbb Q$-linear), if continuous, it would have to vanish everywhere; but it takes the value $1$ at $x$.

Answer 2

Any linear function ($f(x+y)=f(x)+f(y)$)satisfies the above, and there are linear functions which are not convex assuming choice (using basis $\mathbb R/\mathbb Q$); measurability or local boundedness near a point excludes those.

Picking small $h$ (s.t. $x+h<y$) and using above inequality for $x+h$, $y$, $y+h$, $y-2x$, we get that above inequality implies convexity for the mean of two numbers ($2f(y)\le f(x)+f(y-2x)$) and that implies full convexity whenever $f$ is locally bounded near a point (which is equivalent to measurable in this context).

Answer 3

Any convex function $\newcommand{\bR}{\mathbb{R}}$ $f:\bR^n\to\bR$ is continuous; see Corollary 10.1.1. of R. T. Rockafellar's book Convex Analysis.