7
$\begingroup$

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

$\endgroup$

3 Answers 3

8
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Could you give me an example of a such a function that will obey the inequality? A reference would also suffice. I have not been able to come up with one... $\endgroup$
    – Ivan
    Oct 5, 2017 at 14:50
  • 1
    $\begingroup$ It is consistent with the negation of AC that no such example exists, so I can't give one. This discussion mathoverflow.net/questions/57426/… and many, many similar MO and MSE questions may help. $\endgroup$
    – LSpice
    Oct 5, 2017 at 16:06
  • $\begingroup$ I edited with a slightly more detailed version of the construction. $\endgroup$
    – LSpice
    Oct 5, 2017 at 19:46
  • $\begingroup$ I didn't want to link lots of posts in my comment about the lack of explicit counterexamples, but it turns out that @MartinSleziak already compiled a long list in his wonderful post Overview of basic facts about Cauchy functional equation. $\endgroup$
    – LSpice
    Oct 5, 2017 at 19:57
  • $\begingroup$ One more link: in case, for whatever reason, you like citing published papers better than citing MO, it seems that the place to look for all these 'well-known' statements is Sierpiński - Sur les fonctions convexes mesurables. $\endgroup$
    – LSpice
    Oct 5, 2017 at 20:14
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Not familiar with convex analysis, why do mean convexity and local boundedness imply full convexity? Thanks $\endgroup$
    – Ivan
    Oct 5, 2017 at 15:15
  • 1
    $\begingroup$ It seems inadvisable to call all additive functions linear; probably "$\mathbb Q$-linear" (or just 'additive'!) is better. $\endgroup$
    – LSpice
    Oct 5, 2017 at 19:50
  • $\begingroup$ @Ivan, without any claim that it's the best reference, some Googling turned up Theorem, p. 12, of Donoghue - Distributions and Fourier transforms. $\endgroup$
    – LSpice
    Oct 5, 2017 at 20:04
0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ This seems to answer the question only implicitly, without the crucial observation that there are discontinuous functions satisfying the proposed inequality (so that it is not a correct definition of convexity). $\endgroup$
    – LSpice
    Oct 5, 2017 at 19:08

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.