7
$\begingroup$

There is a sequence of conditions on functions generalizing Lipschitz continuity; these conditions bear the same relationship to higher-order derivatives that Lipschitz continuity bears to first-order derivatives. Are these known and under what name?

To be specific, let $I$ be an interval in the real line, $f$ a real-valued function on $I$, and $C$ a positive real number.

  • $f$ is $0$-Lipschitz (aka bounded) on $I$ with constant $C$ if, for all $a \in I$, $\lvert{f(a)}\rvert \leq C$;
  • $f$ is $1$-Lipschitz (aka Lipschitz) on $I$ with constant $C$ if, for all $a < b \in I$, $\left| \frac {f(b) - f(a)} {b - a} \right| \leq C$;
  • $f$ is $2$-Lipschitz on $I$ with constant $C$ if, for all $a < b < c \in I$, $\left| \frac {\frac {f(c) - f(b)} {c - b} - \frac {f(b) - f(a)} {b - a}} {c - a} \right| \leq \frac 1 2 C$;
  • $f$ is $3$-Lipschitz on $I$ with constant $C$ if, for all $a < b < c < d \in I$, $\left| \frac {\frac {\frac {f(d) - f(c)} {d - c} - \frac {f(c) - f(b)} {c - b}} {d - b} - \frac {\frac {f(c) - f(b)} {c - b} - \frac {f(b) - f(a)} {b - a}} {c - a}} {d - a} \right| \leq \frac 1 6 C$;
  • etc.

In general, $f$ is $n$-Lipschitz on $I$with constant $C$ if, for all $a_0 < \cdots < a_n \in I$, $$ \left| \frac {\det \begin{bmatrix} 1 & 1 & \cdots & 1 & 1 \\ a_0 & a_1 & \cdots & a_{n-1} & a_n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_0^{n-1} & a_1^{n-1} & \cdots & a_{n-1}^{n-1} & a_n^{n-1} \\ f(a_0) & f(a_1) & \cdots & f(a_{n-1}) & f(a_n) \end{bmatrix}} {\det \begin{bmatrix} 1 & 1 & \cdots & 1 & 1 \\ a_0 & a_1 & \cdots & a_{n-1} & a_n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_0^{n-1} & a_1^{n-1} & \cdots & a_{n-1}^{n-1} & a_n^{n-1} \\ a_0^n & a_1^n & \cdots & a_{n-1}^n & a_n^n \end{bmatrix}} \right| \leq \frac 1 {n!} C .$$ (The denominator is a Vandermonde determinant, and the numerator is the same with the highest powers replaced the values of the function.)

Of course, in this case, then the same inequality holds if $a_0, \ldots, a_n$ are out of order (since this amounts to swapping columns in the determinants), as long as they are distinct, and they don't even have to be distinct if you clear fractions: $$ n! \left| \det \begin{bmatrix} 1 & 1 & \cdots & 1 & 1 \\ a_0 & a_1 & \cdots & a_{n-1} & a_n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_0^{n-1} & a_1^{n-1} & \cdots & a_{n-1}^{n-1} & a_n^{n-1} \\ f(a_0) & f(a_1) & \cdots & f(a_{n-1}) & f(a_n) \end{bmatrix} \right| \leq C \left| \det \begin{bmatrix} 1 & 1 & \cdots & 1 & 1 \\ a_0 & a_1 & \cdots & a_{n-1} & a_n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_0^{n-1} & a_1^{n-1} & \cdots & a_{n-1}^{n-1} & a_n^{n-1} \\ a_0^n & a_1^n & \cdots & a_{n-1}^n & a_n^n \end{bmatrix} \right| ;$$ if the list $(a_0, \ldots, a_n)$ has any repetition, then this just says that $0 = 0$. But I like to think of using an increasing list, since that shows where the formulas come from. For example, the expression inside the absolute value in the $2$-Lipschitz condition is a sort of second-order difference quotient, saying how much the difference quotient (which appears in the ordinary $1$-Lipschitz condition) changes as we move from $(a,b)$ to $(b,c)$, relative the overall range. (I don't have any slick reason for why the result can be neatly packed up as a ratio of determinants, but it's easy enough to prove this using induction and basic facts about Vandermonde determinants.)

Some basic results:

  • Assuming that $f$ is differentiable $n$ times on $I$, then $f$ is $n$-Lipschitz on $I$ with constant $C$ if and only if the $n$th derivative $f^{(n)}$ is bounded (on $I$ with constant $C$).
  • More generally, assuming that $f$ is differentiable $k$ times on $I$, then $f$ is $n$-Lipschitz if and only if $f^{(k)}$ is $(n - k)$-Lipschitz. (The factorials guarantee the same constant.)

I'd like to say that, if $f$ is $n$-Lipschitz, then $f^{(n)}$ exists almost everywhere, still bounded by the same constant, but I haven't proved this.

I don't know how to make sense of this in an arbitrary metric space, or even in $\mathbb{R}^2$. Neither the form with the higher-order difference quotient nor the form with the determinants makes sense a priori for even a $2$-Lipschitz function. The metric-space derivative is defined by essentially putting absolute values around every subtraction in a difference quotient, changing $b - a$ into $\lvert{b - a}\rvert$, which is reinterpreted as $d(a,b)$. But for the $2$-Lipschitz condition, this applies the absolute value too soon, before a necessary additional subtraction, so it's not the same.

Anyway, if anybody has seen anything like this or has any thoughts on it, then I'm interested.

$\endgroup$
3
  • $\begingroup$ When you say "in an arbitrary metric space, or even in $\mathbb R^2$", do you mean changing the domain $I$? You can clearly use any normed vector space for the codomain, with exactly the same difference quotient formulas (just changing $|$ to $\|$). $\endgroup$
    – Dap
    Dec 7 '17 at 10:25
  • 1
    $\begingroup$ Generalization to $W^{m,p}$: hindawi.com/journals/jfs/2014/261565 $\endgroup$
    – Dap
    Dec 7 '17 at 16:41
  • $\begingroup$ @Dap : Yes, I meant changing $I$. $\endgroup$ Dec 9 '17 at 18:33
3
$\begingroup$

This ends up being the space $C^{n-1,1}$, the space of $(n-1)$ times differentiable functions with Lipschitz continuous derivative of order $(n-1)$. The reduction step is that a function is $n$-Lipschitz ($n\ge 2$) if and only if it is differentiable and $f'$ is $(n-1)$-Lipschitz. I will work with $n=2$, leaving the notationally cumbersome case $n>2$ for interested readers.

$2$-Lipschitz implies first derivative is $1$-Lipschitz

Let's write $[a,b] = \dfrac{f(a)-f(b)}{a-b}$. First, the existence of derivative $f'(a) $ follows from the fact that for every sequence $x_n\to a$ such that $x_n\ne a$, the quotients $[x_n,a]$ form a Cauchy sequence. Indeed, $$ |[x_n,a] - [x_m,a]| \le \frac{C}{2} |x_n-x_m| $$ by the $2$-Lipschitz condition.

Second, the $2$-Lipschitz condition says that $|[a,b] - [b,c]|\le \frac{C}{2}|a-c|$. Applying this twice we get, for any $a<b<c<d$, that $$ |[a,b] - [c,d]| \le |[a,b] - [b,c]| + |[b,c] - [c,d]| \le \frac{C}{2}(|a-c| + |b-d|)\le C |a-d| $$ Now pass to the limit $b\to a$ and $c\to d$ to conclude that $$ |f'(a)-f'(d)| \le C|a-d| $$ i.e., $f'$ is Lipschitz.

$2$-Lipschitz follows from the first derivative being $1$-Lipschitz

By the mean value theorem $[a,b] = f'(\xi) $ for some $\xi\in (a,b)$. So, for any $a<b<c$ we have $$ |[a,b] - [b,c]| = |f'(\xi_1) - f'(\xi_2)| \le L|a-c| $$ where $L$ is the Lipschitz constant of $f'$. This shows $f$ is $2$-Lipschitz.

References

Potentially relevant references can be found at the end of the Wikipedia article Divided differences.

$\endgroup$
1
  • $\begingroup$ Thanks! I didn't grasp that a 2-Lipschitz function is differentiable everywhere (not just almost everywhere by virtue of being a locally 1-Lipschitz function), but now that you've pointed that out, it all falls into place. $\endgroup$ Dec 9 '17 at 18:49
2
$\begingroup$

Here is a warts-and-all proof of Crazy Ivan's characterization of $n$-Lipschitz functions as $C^{n-1,1},$ also known as the Sobolev space $W^{n,\infty}$ (for bounded intervals).

Note that by Cramer's rule, the ratio-of-determinants is the leading coefficient of the interpolating polynomial through $(x_0,f(x_0)),\dots,(x_n,f(x_n)),$ which by the "Newton form" is the $n$'th divided difference.

I'll use a constructive characterization of $n$ times continuously differentiable functions.


Let $f:I\to\mathbb R$ be a function defined on some bounded interval $I.$ Suppose there are functions $f_0,\dots,f_n$ defined on $I,I^2,\dots,I^{n+1}$ respectively, satisfying: $$f_0(x_0) = f(x_0),$$ $$f_0(x_1) − f_0(x_0) = (x_1 − x_0)f_1(x_0, x_1),$$ $$\dots,$$ $$f_{n−1}(x_0, \dots, x_{n−2}, x_n) − f_{n−1}(x_0, \dots, x_{n−2}, x_{n−1}) = (x_n − x_{n−1})f_n(x_0, \dots, x_n)$$ for all $x_0, \dots, x_n$ in $I.$

Theorem (Coquand, Spitters, Theorem 3.1). If $f_n$ is uniformly continuous then $f$ has a uniformly continuous $n$'th derivative, $$f^{(n)}(x) = n!f_n(x, \dots, x).$$

Proof. (Based on the same paper, but with more detail for the inductive step.) Since $f_n$ is uniformly continuous and $I$ is bounded, the functions $f_{n-1},\dots,f_0$ are uniformly continuous. Observe that the functions $f_i$ are symmetric under permutations of their arguments on the set where the arguments are all distinct (they're just divided differences), and since this set is dense they must be symmetric everywhere.

We have $f^{(0)}(x)=f(x).$ Assuming inductively the formula $f^{(k)}(x)=k!f_k(x,x,\dots,x),$ we get

\begin{align*} f^{(k)}(y)-f^{(k)}(x)&=f_k(y,y,\dots,y)-f_k(x,x,\dots,x)\\ &=\sum_{i=0}^{k+1}(f_k(\underbrace{y,y,\dots,y}_{k+1-i\text{ times}},\underbrace{x,x,\dots,x}_{i\text{ times}})-f_k(\underbrace{y,y,\dots,y}_{k-i\text{ times}},\underbrace{x,x,\dots,x}_{i+1\text{ times}}))\\ &=(y-x)\sum_{i=0}^{k+1}f_{k+1}(\underbrace{y,y,\dots,y}_{k+1-i\text{ times}},\underbrace{x,x,\dots,x}_{i+1\text{ times}}) \end{align*} where the first equality is a telescoping sum, and the second equality makes use of permutation symmetry. This implies $f^{(k+1)}(x)=(k+1)!f_{k+1}(x,x,\dots,x)$ as required.


To apply this to $n$-Lipschitz functions, for each $0\leq i\leq n$ take $f_i$ to be the $i$'th divided difference, defined for the subset of $I^{i+1}$ where all the co-ordinates are distinct. The $n$-Lipschitz condition implies that $f_n$ is bounded. This implies that $f_0,\dots,f_{n-1}$ are uniformly continuous where defined, hence extend to the closures $I,I^2,\dots,I^n.$ By the theorem above (applied with $n-1$ instead of $n$), $f$ is $n-1$ times continuously differentiable. And we have $f^{(n-1)}(x)=(n-1)!f_{n-1}(x,x,\dots,x)$; note $f_{n-1}$ is the extension of a Lipschitz function to $I^n$ so is Lipschitz, so the $n-1$'th derivative is Lipschitz.

For the converse we are given a function $f\in C^{n-1,1}(I)$ and want to show it is $n$-Lipschitz. By definition, the $n-1$'th derivative is $1$-Lipschitz. Recall that a 1-Lipschitz function is absolutely continuous, and in fact the $n$'th weak derivative of $f$ is equal to an $L^{\infty}(I)$ function which we may denote by $f^{(n)}.$ We can then use the Hermite-Genocchi formula for the divided difference for all $0\leq k\leq n$:

$$f_k(x_0, \dots, x_k) = \int_{\Sigma_k} f^{(k)}(t_0x_0 + \cdots + t_kx_k)dt_0 \dots dt_k$$ where $\Sigma_k = \{(t_0, \dots, t_k) \in [0, 1]^{k+1} \mid t_0 + \dots + t_k = 1\}.$ This is easy to verify for distinct $x_0,\dots,x_k$ - see the Coquand and Spitters paper. For $k=n$ we need that the fundamental theorem of calculus $f^{(n-1)}(y)-f^{(n-1)}(x)=\int_x^y f^{(n)}(z)dz$ generalizes to absolutely continuous functions $f^{(n-1)}.$ The volume of $\Sigma_n$ is $1/n!,$ so if $f^{(n)}$ is bounded by $C$ then $f_n$ is bounded by $C/n!.$

$\endgroup$

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.