Is Every Convex Function Differentiable at Most Points?

[Euge]

Here is this week's POTW:

-----
Suppose $f : (a,b) \to \Bbb R$ is a convex function. Show that $f$ is differentiable at all but countably many points and the derivative is nondecreasing.

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[jedishrfu]

Perhaps @Euge can provide the solution or some good hints for future readers.

 

[Office_Shredder]

Here are some starting steps. I don't have a proof, but I suspect these are necessary and will come back if I finish it

A convex function is one where if you draw a line connecting two points on the graph $a=(x_1, f(x_1))$ and $b=(x_2, f(x_2))$ then all the points $c=(x_3, f(x_3))$ lie on or below the line. Note this also means if $x_3>x_2$, then $c$ must lie on or above the line, as the line connecting $a$ and $c$ has $b$ on our below it, so $a-c$ has at least as large a slope as $a-b$ does. Similarly if $x_3<x_1$ then $c$ lies above the line.

In particular this means as you connect a specific value $x,f(x)$ to $z,f(z)$ for fixed $x$, the slope is a non decreasing function in $z$(even crossing $x$). We will use this last fact a lot.

Claim: right derivatives and left derivatives always exist.

Spoiler

consider $\frac{f(x+h)-f(x)}{h}$ for positive $h$. This is the slope of the line connecting the graph between $x$ and $x+h$. By convexity this is decreasing. It is also bounded from below. If it gets arbitrarily negative, then $f$ cannot satisfy convexity to the left of $x_0$ - picking any point to the left of $x_0$ and computing the slope connecting it to $x_0$ gives a slope that must be at least as small as all the slopes when connecting to the right.

Hence the limit exists as the slope decreases as $h$ goes to zero, and it has a lower bound Similarly the limit from the left (negative $h$ going to 0) must exist

Also, the left and right derivatives are non decreasing. Even better, we have the left derivative at $x$ is not larger than the right derivative at $x$, and if $z>x$, the left derivative at $z$ is at least as large as the right derivative at $x$

Spoiler

by convexity $\frac{f(x+h)-f(x)}{h}$ is an increasing function in $h$, hence is larger for when $h$ is positive than when it's negative. Hence the right derivative must be larger than the left.

Now consider for $0<h<(z-x)/2$,

$\frac{f(x+h)-f(x)}{h}$, $\frac{f(z-h)-f(x+h)}{z-x-2h}$ and
$\frac{f(z)-f(z-h)}{h}$.

These are the three slopes of the lines connecting $x$ and $x+h$, $x+h$ and $z-h$, and $z-h$ and $z$. By convexity and comparing slopes connected to $x+h$, the first is no larger than the second, and by comparing slopes connected to $z-h$, the second is no larger than the third. So the third is at least as large as the first. The right derivative at $x$ is the limit of the first as $h$ goes to zero, and the left derivative at $z$ is the limit of the third, proving the right derivative at $x$ is less than or equal to the left derivative at $z$ if $x<z$

So basically we have a derivative that is non decreasing and defined everywhere except at points where the right derivative is larger than the left derivative, which is where the derivative is not defined, but the non decreasing property continues to hold on the left and right derivatives.

Edit:
Oh here is the last piece. Every discontinuous point in the derivative is when there's a jump at a point between the left and right derivatives. Let $X$ be the set of all such points $x$ where a jump occurs and let $(l_x,r_x)$ be the open interval containing the left and right derivatives. These intervals are non overlapping, since if $x<y$, $r_x\let l_y$.
Hence for each interval we can pick a rational number and this gives us an injection from $X$ to $\mathbb{Q}$, proving $X$ is countable.