A convex function is differentiable at all but countably many points

Let $f:\Bbb R\to\Bbb R$ be a convex function. Then $f$ is differentiable at all but countably many points.

It is clear that a convex function can be non-differentiable at countably many points, for example $f(x)=\int\lfloor x\rfloor\,dx$.

I just made this theorem up, but my heuristic for why it should be true is that the only possible non-differentiable singularities I can imagine in a convex function are corners, and these involve a jump discontinuity in the derivative, so since the derivative is increasing (where it is defined), you get an inequality like $f'(y)-f'(x)\ge \sum_{t\in(x,y)}\omega_t(f')$, where $\omega_t(f')$ is the oscillation at $t$ (limit from right minus limit from left) and the sum is over all real numbers between $x$ and $y$. Since the sum is convergent (assuming that $x\le y$ are points such that $f$ is differentiable at $x$ and $y$ so that this makes sense), there can only be countably many values in the sum which are non-zero, and at all other points the oscillation is zero and so the derivative exists. Thus there are only countably many non-differentiable points in the interval $(x,y)$, so as long as there is a suitable sequence $(x_n)\to-\infty$, $(y_n)\to\infty$ of differentiable points, the total number of non-differentiable points is a countable union of countable sets, which is countable.

Furthermore, I would conjecture that the set of non-differentiable points has empty interior-of-closure, i.e. you can't make a function that is non-differentiable at the rational numbers, but as the above discussion shows there are still a lot of holes in the proof (and I'm making a lot of unjustified assumptions regarding the derivative already being somewhat well-defined). Does anyone know how to approach such a statement?

The set of points of nondifferentiability can be dense.

But you correctly conjectured that it is at most countable. First, convexity implies that for $s<u\le v<t$ we have $$\frac{f(u)-f(s)}{u-s}\leq\frac{f(t)-f(v)}{t-v} \tag{1}$$ Sketch of the proof of (1). First, use the 3-point convexity definition to show this for $u=v$. When $u<v$, proceed as $$\frac{f(u)-f(s)}{u-s}\leq\frac{f(t)-f(u)}{t-u}\leq\frac{f(t)-f(v)}{t-v}\qquad \Box$$

From (1) it follows that $f$ has one-sided derivatives ${f}_-'$ and $f_+'$ at every point, and they satisfy $${f}_-'(x)\le f_+'(x)\le {f}_-'(y)\le f_+'(y), \quad x<y \tag{2}$$

For every point where ${f}_-'(x)< f_+'(x)$, pick a rational number $q$ such that ${f}_-'(x)< q< f_+'(x)$. Inequality (2) implies all these rationals are distinct. Therefore, the set of points of nondifferentiability is at most countable.

• Ah, yes, I should have figured that some rapidly-enough converging sequence like $\sum_{n=0}^\infty\frac{2^{-n}}{|r_n|+1}|x-r_n|$ where $(r_n)$ enumerates $\Bbb Q$ could be have discontinuous derivative at all the rationals. And your proof for my original statement goes exactly the way I was hoping. Spot on! – Mario Carneiro Sep 26 '14 at 5:41
• Do you know a "named" function with the behavior exhibited by the derivative here? That is, it is a monotonic function that is discontinuous at all the rationals (with jump discontinuities of various sizes). That feels like one of those "standard counterexample"-type functions, but the only examples I can think of are like the Cantor function, which is actually continuous (and probably was the source of my poor intuition here). – Mario Carneiro Sep 26 '14 at 5:46

I'm going to post an alternative answer for those who wish to avoid the Axiom of Choice (although that argument is much simpler than the one below).

It's fairly trivial to demonstrate that whenever $f$ is a convex map (on an open set), then $f$ is both left-differentiable and right-differentiable at every point of its domain. It's also quite typically easy to show that both $f_l'$ and $f_r'$ are both increasing functions. Furthermore, it's also typically easy to show that $f_l'(x)\leq f_r'(x)$ for every $x$ in the domain. However, another property that holds (which is much less frequently invoked however quite important here) is that whenever $x< y$, then $f_r'(x)\leq f_l'(y)$. Each of these can be readily proved from the Three Chord lemma.

The idea behind this proof is to use the fact that increasing functions have at most countably many points of discontinuity (which both $f_l'$ and $f_r'$ are). And to use this fact that we are about to prove: if either $f_l'$ or $f_r'$ are continuous at some fixed point, then both of these functions are going to agree at that point.

From the inequalities above, we can conclude for any $x$ that $$\lim_{y\rightarrow x^-}f_r'(y)\leq f_l'(x)\leq f_r'(x) \quad\text{and}\quad f_l'(x)\leq f_r'(x)\leq\lim_{y\rightarrow x^+}f_l'(y).$$

The assertion of equality in the presence of continuity is quickly deduced from these inequalities.

Now let $D$ be the set of points where $f$ is not differentiable. By the lemma we just proved, this set is contained in the set of points where either $f_l'$ or $f_r'$ is discontinuous, which is of course countable.

• I like the argument from the countability of the discontinuities of a monotonic function. (It's the one I think of first.) But picking a rational $f_{-}'(x) < q < f_{+}'(x)$ doesn't need the axiom of choice either, one can easily give explicit rules, e.g. among the rationals with smallest denominator (writing all rationals with a positive denominator), pick the smallest in that interval. – Daniel Fischer Jul 19 '18 at 19:59