10
$\begingroup$

Let $f: R \rightarrow R$, $y_0,y_1,y_2 \in R$. We define divided differences: $$[y_0;f]=f(y_0),$$ $$[y_0,y_1;f]=\frac{f(y_1)-f(y_0)}{y_1-y_0},$$ $$[y_0,y_1,y_2;f]=\frac{[y_1,y_2;f]-[y_0,y_1;f]}{y_2-y_0}.$$

Assume that for each $x \in R$ and $\varepsilon>0$ there exists a $\delta>0$ such that $$|[y_0,y_1,y_2;f]-[y_0',y_1',y_2';f]|< \varepsilon$$ for arbitrary sets $\{y_0,y_1,y_2\}$, $\{y_0',y_1',y_2'\}$ of distinct points such that $|y_i-x|<\delta$, $|y_i'-x|<\delta$ ($i=0,1,2$).

Is it $f$ of class $C^2$ ?

  • 2
    I personally like the pointwise version more: is $\displaystyle f''(x)=\lim_{y_1,y_2,\to x}[x,y_1,y_2;f]$ whenever the limit exists? If the answer is yes, the continuity of $f''$ in your case follows at once. But maybe you ask in this form because you have a counterexample to the pointwise version?2012-08-26
  • 1
    @LVK: a) I think it should be $\frac12f''(x)$? b) I don't understand your comment. In the first-order version, $f'(x)=\lim_{y\to x}[x,y;f]$ is just the definition of the derivative, which doesn't guarantee continuity -- why is this different in the second-order version? Why would $\displaystyle f''(x)=\lim_{y_1,y_2,\to x}[x,y_1,y_2;f]$ fail to hold for discontinuous second derivative?2012-08-26

3 Answers 3

2

I'll try to provide a proof of the general case $[y_0,\ldots,y_n;f]$. This proof has many similarities to that of timur, but I'll formulate things more in terms of limits rather than using $\epsilon$s and $\delta$s. My other answer was wrong, but I leave it since it had some useful bits, one of which I'll redo here.

Hope I didn't overlook anything grave this time. However, I'm sure I've taken a few technical short-cuts which could need filling in: the lemma provided at the end is an attempt at that.

Notation: Let $R^{n+1}_k\subset\mathbb{R}^{n+1}$ consist of the points $y=(y_0,\ldots,y_n)$ for which at most $k$ coefficients have the same value: i.e. $R^{n+1}_1$ are those where all $y_i$ are distinct, while $R^{n+1}_{n+1}=\mathbb{R}^{n+1}$. We then have $[\cdot;f]:R^{n+1}_1\rightarrow\mathbb{R}$ defined as $$ [y_0,\ldots,y_n;f]=\frac{[y_1,\ldots,y_n;f]-[y_0,\ldots,y_{n-1};f]}{y_n-y_0} \tag{1} $$ for $y\in R^{n+1}_{1}$: generalised from the cases $n=0,1,2$ stated in the original problem.

Definition: We say that a function $f$ is $\mathcal{F}^n$ if for any $y,y'\in R^{n+1}_1$, $$\lim_{y,y'\rightarrow x^{[n+1]}}\Big|[y;f]-[y';f]\Big|=0\tag{2}$$ where, for $x\in\mathbb{R}$, the point $x^{[n+1]}=(x,\ldots,x)\in\mathbb{R}^{n+1}$. This is just the equivalent of the $\epsilon$-$\delta$ formulation in terms of limits.

(i) Assume $f$ is $\mathcal{F}^n$. If we take any sequence $y^{(k)}\in R^{n+1}_1$ which converges to $x^{[n+1]}$, then $[y^{(k)};f]$ becomes a Cauchy sequence: i.e. for $p,q\ge k$, $\big|[y^{(p)};f]-[y^{(q)};f]\big|\rightarrow0$ as $n\rightarrow\infty$. Hence, $[f^{(k)};f]$ must converge. Let's denote the limit $[x^{[n+1]};f]=g_n(x)$.

(ii) Let's prove by induction that $[y_0,\ldots,y_n;f]$ is symmetric in the $y_i$. Obviously, it holds for $n=0,1$. Assume it holds for $n

(iii) Again, we use induction, assuming the following holds for $n$f$ is $\mathcal{F}^n$ if and only if it is $C^n$, i.e. $\mathcal{F}^n=C^n$: in particular, it is also $\mathcal{F}^k$ for all $k

For $n=0,1$, the asumption holds true. So we let $n=N\ge2$.

In order to utilise the induction hypothesis, we first need to show that when $f$ is $\mathcal{F}^n$, it is also $\mathcal{F}^{n-1}$. To do this, we rewrite equation (1) $$(u-v)[u,A,v;f]=[u,A;f]-[A,v;f]$$ for $A=(a_1,\ldots,a_{n-1})$. For $u=(u_1,\ldots,u_n)$ and $v=(v_1,\ldots,v_n)$, both in $R^n_1$, we then get $$ \begin{split} (u_1-v_1)[u_1,\ldots,u_n,v_1;f]&+(u_2-v_2)[u_2,\ldots,u_n,v_1,v_2;f]\\ &+\cdots+(u_n-v_n)[u_n,v_1,\ldots,v_n;f]\\ =&[u_1,\ldots,u_n;f]-[v_1,\ldots,v_n;f]\\ \end{split}\tag{3} $$ where $u,v\rightarrow x^{[n]}$ leads to $\big|[u;f]-[v;f]\big|\rightarrow0$, i.e. the definition of $f$ being $\mathcal{F}^{n-1}$.

For any $y\in R^{n+1}_n$, i.e. not all $y_i$ are equal, we can rearrange the $y_i$ to make $[y;f]=[u,A,v;f]$ where $u\not=v$ and use (1) to get $[y;f]$ expressed in terms of $[u,A;f]$ and $[A,v;f]$, both of which are defined on the whole $\mathbb{R}^n$. This provides us with an extension of $[y;f]$ to all $y\in R^{n+1}_n$.

Finally, in equation (3), we let $u=x^{[n]}$, $v=x'^{[n]}$: by continuity, we can do that, or alternatively we can take limits $u\rightarrow x^{[n]}$ and $v\rightarrow x'^{[n]}$ (and we take these limits before the later limit). Dividing by $x-x'$ on both sides then gives $$ \frac{g_{n-1}(x)-g_{n-1}(x')}{x-x'} =[x,\ldots,x,x';f]+\cdots+[x,x',\ldots,x';f] $$ where $x'\rightarrow x$ gives $g_{n-1}'(x)=n\cdot[g_n(x)]$. Hence, $g_n(x)=f^{(n)}/n!$.

The only remaining thing to point out is that the final extension of $[y;f]$ from $y\in R^{n+1}_n$ to all of $\mathbb{R}^{n+1}$ is continuous. This basically follows from the definition, but we have to use the following lemma (which I have implicitly used further up as well), to ensure the limit in (2) holds true even if the sequence even if $y\in R^{n+1}_n$ rather than $R^{n+1}_1$.

Lemma: Given $x,v_i,u^{(i)}_j\in\mathbb{R}$ so that $v_i\rightarrow x$ and $u^{(i)}_{j}\rightarrow v_i$, then we can pick $j_i$ so that $u^{(i)}_{j_i}\rightarrow x$.

One use of the lemma is that if $y^{(i)}\in R^{n+1}_n$, $z^{(i,j)}\in R^{n+1}_1$, we can set $v_i=[y^{(i)};f]$, $u^{(i)}_j=[z^{(i,j)};f]$, and replace the limit of $[y^{(i)};f]$, which is taken in $R^{n+1}_n$, with a limit taken in $R^{n+1}_1$.

5

A. First order case. By definition of the first derivative, we have $$ [x,z;f]\to f'(x), \qquad\textrm{as}\quad z\to x, $$ at each $x$. In the following, let us fix $x$. By assumption, for any $\varepsilon>0$, there exists $\delta>0$ such that $$ |[x,z;f]-[y,t;f]|<\varepsilon, \qquad\textrm{for all}\quad z,y,t\in B_\delta(x), $$ where $B_\delta(x)=\{t:|t-x|<\delta\}$. Now we fix $\varepsilon>0$, and will show that with $\delta>0$ given by assumption as above, it holds for each $y\in B_\delta(x)$ that $$ |f'(x)-f'(y)|<3\varepsilon. $$ To prove the claim, first, pick $z\in B_\delta(x)$ satisfying $$ |[x,z;f]-f'(x)|<\varepsilon. $$ Then, pick $t\in B_\delta(x)$ satisfying $$ |[y,t;f]-f'(y)|<\varepsilon. $$ Combining the above inequalities, we get the claim.

B. Second order case. One can prove as in Einar's answer that the divided differences converge to some function $g$ pointwise. Then the argument from Part A shows that $g$ is continuous. So the only remaining question is the existence of $f''$ and whether or not $f''=2g$.

Let $G$ be a function satisfying $G''=2g$. Then it is well known that the second order divided differences of $G$ converge pointwise to $g$. Hence by linearity, the same divided differences of $u=f-G$ converge pointiwse to $0$. If we could show that $u''$ exists everywhere and $u''\equiv0$, this would imply that $f''$ exists and $f''=2g$ everywhere. Therefore from now on, we can assume $g\equiv0$. We have $$ [x,y,z;f]=\frac{[x,y;f]-[y,z;f]}{x-z}=\frac{[y,x;f]-[y,z;f]}{x-z}\to0, $$ as $\max\{|x-y|,|z-y|\}\to0$, for each $y$. This means $$ [y,x;f]-[y,z;f]=o(\delta), $$ with the $o(\delta)$-term being uniform in $x,z\in B_\delta(y)$. In particular, $[y,x;f]$ is convergent as $x\to y$, and so $f'(y)=[y,y;f]$ exists everywhere. Now the idea is to consider $$ [x,x_1,y;f]+[x,y_1,y;f]=\frac{[x,x_1;f]-[y,x_1;f]+[x,y_1;f]-[y,y_1;f]}{x-y}, $$ which goes to $0$ as $x_1,y_1,y\to x$, and somehow take the limits $x_1\to x$ and $y_1\to y$, before taking the other limits.

C. Proof that $f''$ exists and $f''\equiv0$. Let $x$ be a point and let $\varepsilon>0$. Then pick $\delta>0$ such that $|[x,z,y;f]|<\varepsilon$ for any $y,z\in B_\delta(x)$. We will show that $$ \left|\frac{f'(x)-f'(y)}{x-y}\right|<5\varepsilon, \qquad\textrm{for any}\quad y\in B_\delta(x)\setminus\{x\}. $$ To this end, choose $x_1,y_1\in B_\delta(x)$ such that $$ |f'(x)-[x,x_1;f]|<\varepsilon|x-y|, \qquad |f'(y)-[y_1,y;f]|<\varepsilon|x-y|, $$ and that $$ |[x,y_1;f]-[x_1,y;f]|<\varepsilon|x-y|. $$ This is possible because $[x,x_1;f]\to f'(x)$ as $x_1\to x$, $[y,y_1;f]\to f'(y)$ as $y_1\to y$, and $[z,t;f]$ is a continuous function of $z$ and $t$. Note the higher order smallness in the right hand sides, which formalizes "taking the limits $x_1\to x$ and $y_1\to y$ first". Finally, we use the simple decompositions $$ f'(x) = \left(f'(x)-[x,x_1;f]\right) +\left([x,x_1;f]-[x_1,y;f]\right) +[x_1,y;f], $$ and $$ -f'(y) = -[x,y_1;f] +\left([x,y_1;f]-[y_1,y;f]\right) +\left([y_1,y;f]-f'(y)\right), $$ to conclude that $$ \left|\frac{f'(x)-f'(y)}{x-y}\right| < \varepsilon+|[x,x_1,y;f]|+\varepsilon+|[x,y_1,y;f]|+\varepsilon <5\varepsilon. $$

  • 1
    Timur, do you only answer questions with bounties? I'm joking but I noticed recently you had the most reputation in the last week, and it was because you had collected 3 bounties for a total of 1100 reputation. And, here you are again.2012-08-26
  • 0
    Why are only $z,y,t$ freely chosen and $x$ fixed? Wouldn't the first-order analogue of the statement in the question have all four of them within $\delta$ of some common value?2012-08-26
  • 0
    @joriki: Yes, but having $x$ fixed is assuming less than what you wrote, right?2012-08-26
  • 2
    @Graphth: Partly because of the bounties, partly because they are intrinsically interesting. The fact that they have bounties means maybe something interesting about them. In any case, what is the point of bounty if it is not for attracting good answers? On the other hand, you can check from my user page that I spent a lot of effort on questions without bounties as well.2012-08-26
  • 1
    @Graphth: It is worth mentioning that many of the bounties are given by some experienced users other than the asker, and many of them have an eye towards how to improve the site, by diversifying and deepening the collected knowledge on the site. When I have sufficient reputation I will use my reputation for this purpose as well.2012-08-26
  • 0
    Sorry, I wrote that comment before you finished the answer, and I thought you were trying to disprove the statement, like Einar. Since you're trying to prove it, of course you're right and you can fix $x$. Another question: Why can you assume $g\equiv0$ by subtracting $G$ with $G''=g$ from $f$ *before* you prove $g=f''$?2012-08-26
  • 0
    @joriki: Because then it would prove that $(G-f)''=0$, which means $f''=G''=g$. I realize that you don't have to do this, it just simplifies some formulas.2012-08-26
  • 0
    I don't understand. How do you know anything about $g$ *before* you prove $g=f''$? At that point you don't know anything about $g$ -- how can *assuming* that it's identically zero prove that $(G-f)''=0$? For all you know at that point, it might never be identically zero, no matter what you subtract from $f$. Am I missing something? (I'm familiar with this general technique of subtracting something out to reduce to a case where something is zero; I'm just saying I don't see how it applies in this case.)2012-08-26
  • 0
    @joriki: We know something about $g$, that is the pointwise limit of the second differences of $f$. On the other hand, the second differences of $G$ converge to $g$ by a standard result. Then the second differences of $u=f-G$ will converge to $0$.2012-08-26
  • 0
    @timur I'm mostly joking. I don't mind if you answer questions with bounties. In fact, the fact that you can answer so many questions with bounties is very impressive.2012-08-27
  • 0
    I see; I didn't realize you were taking that result as given. What threw me off was "Now the question is if $g=f''$". So if I understand correctly, what you mean there is mainly whether $f''$ exists, and you're taking as given that if it does exist then it equals $g$? Perhaps you should clarify that. One more question (sorry about all the questions; it's a great proof! :-) -- when you use the continuity of $[z,t;f]$ to fulfill $|[x,y_1;f]-[x_1,y;f]|<\varepsilon|x-y|$, don't you have to adjust $\delta$? Why does this work with the $\delta$ you chose further up?2012-08-27
  • 0
    On a minor note, $g$ actually converges to $f''/2$.2012-08-27
  • 0
    @joriki: This result is not related to the choice of $\delta$. Choose $x_1$ close enough to $x$, and $y_1$ close enough to $y$, and use $[x,y_1;f]-[x_1,y;f]=[x,y_1;f]-[x,y;f]+[x,y;f]-[x_1,y;f]$. I will clarify the point about $g=f''$ tomorrow. Thanks for the suggestion!2012-08-27
  • 0
    To @joriki's comment just before my last one: Thanks for spotting this!2012-08-27
  • 0
    On $\delta$: Ah, I see, makes sense. Shall we remove all those comments? A long thread like that tends to throw doubt on a proof for the casual reader, and all my doubts have been removed now :-) About the factor of $2$: Well, I had to spot *something* in asking so many questions ;-)2012-08-27
  • 0
    Nicely done! Although I have to admit $\epsilon$s and $\delta$s tend to make me a bit dizzy. I think this argument can be generalised to prove that $[y_0,\ldots,y_n;f]\rightarrow g_n(x)$ when $y\rightarrow x$ makes $f\in C^n$. E.g. one may note that $[y_0,\ldots,y_n;f]$ extends to a continuous function on $\mathbb{R}^{n+1}$ which is symmetric in the $y$s.2012-08-27
  • 1
    @joriki: No need to delete the comments. I think they can be useful to read.2012-08-27
  • 0
    @Einar: It would be good to have a general argument for higher order cases. It seems plausible, but I don't know how to do it nicely (maybe induction on $n$?).2012-08-27
  • 0
    Your rewriting of the $2g=f''$ part doesn't correspond to what I thought I'd understood your argument to be. I agree that you can prove as in part A that $g$ converges to a continuous function; you don't have to take that as given. What I believe you're taking as given is that *if* $f''$ exists, then it is $2g$. Without that, I don't see how your subtraction argument gets off the ground. Above you had written "the second differences of $G$ converge to $g$ by a standard result". Presumably this is by virtue of $G''=2g$, and then the same result yields $f''=2g$ if $f''$ exists.2012-08-27
  • 0
    @joriki: I think I misunderstood your earlier comment. So I believe actually there is nothing taken as given. Please have a look at the update.2012-08-27
  • 0
    I'm afraid we're still taking past each other. By "taking for given" I mean nothing more than what you meant by "a standard result", or by "it is well known" in the update. You're taking it as well known that if $G''=2g$, then the second-order divided differences of $G$ converge to $g$. All I'm saying is that if you do, then there's no need to prove $f''=2g$, since as long as $f''$ exists, it is equally well known that its second-order divided differences converge to $f''/2$, and since we already know they converge to $g$, that implies $f''=2g$.2012-08-27
  • 0
    @joriki: Ok. I think now I understand what you meant. I leave the post as it is, even though some of the steps seem to be redundant as you observe.2012-08-27
2

NB: The main argument in this answer, that the clause does not imply $C^2$, is wrong.

I'll leave the answer since it contains some useful arguments about the existence of a limit ($[y_0,\ldots,y_n;f]\rightarrow g_n(x)$ as $y\rightarrow x$) as well as some examples high-lighting the difference between having a derivative and it being continuous.


As has been commented already, the expression is essentially the definition of second derivative, however there are some technical problems (which I realised from the comment by timur).

For any $n$, having $$\big|[y_0,\ldots,y_n;f]-[y'_0,\ldots,y'_n;f]\big|<\epsilon$$ for all $y_i, y'_i$ sufficiently close to $x$, guarantees that there is a limit $g_n(x)$ with $$\big|[y_0,\ldots,y_n;f]-g_n(x)\big|<\epsilon.$$ E.g. if you pick a sequence of $n+1$-tuples $y^{(k)}=(y^{(k)}_0,\ldots,y^{(k)}_n)$ with $|y^{(k)}_i-x|<\delta_k$, where $\delta_k\rightarrow0$ as $\epsilon_k\rightarrow0$, by plugging in $y=y^{(k)}$ and $y'=y^{(l)}$ for some $l>k$, we find that $[y^{(k)};f]$ is a Caucy sequence, so we know it converges.

I'm fairly confident the limiting function will be be $g_n(x)=f^{(n)}(x)/n!$, where $f^{(n)}$ is the $n$th derivative, provided the $n$th derivative exists. (I thought I had an example where the limit exists but $f$ does not have $n$th derivative, which I claimed in a previous version of this answer, but this was not correct.)

For $f$ to be $C^n$, a function must not only have an $n$th derivative, but it must be continuous. This need not be the case, and it fails already at $n=1$ with $f(x)=x^2\sin(1/x)$ (setting $f(0)=\lim_{x\rightarrow 0}f(x)=0$). This has $f'(x)=0$ due to the $x^2$ factor. Accordingly, $[y_0,y_1;f]\rightarrow 0$ when $y_i\rightarrow 0$. However, $f'(x)=2x\sin(1/x)-\cos(1/x)$ which is not continuous at $x=0$ as $\cos(1/x)$ fluctuates between $1$ and $-1$.

For $n=2$, I previously used $f(x)=x^3\sin(1/x)$ as a counterexample: this is $C^1$, but does not have a second derivative at $x=0$. However, my claim that get$[y_0,y_1,y_2;f]\rightarrow 0$ as $y_i\rightarrow 0$ does not seem to be correct.

Instead, for $n=2$, we can set $f(x)=x^4\sin(1/x)$. This has second derivative defined everywhere, but which is not continuous.

My main doubt now is that it seems to me $|[y_0,\ldots,y_n;f]-g_n(x)|<\epsilon$ not only ensures that $f$ has an $n$th derivative in $x$, but that it also bounds the $n$th derivative in a neighbourhood of $x$ (by the same $\epsilon$--$\delta$ limit). Hence, the proposal in the original problem statement should be true.

  • 1
    In the counterexample, what about the value $f'(0)$? It seems that if the divided differences converge, it should be $f'(0)=0$, but I cannot see it from the analytic expression.2012-08-26
  • 0
    @timur In the first counterexample, although $f'(x)$ is discontinuous at $x=0$, due to the $x^2$ factor we get $f'(0)=0$. For the second counterexample, this is more problematic as $f'(x)$ contains $x\cos(1/x)$, so $f'(x)$ is continuous but not differentiable at $x=0$; however, $f(x)/x^2\rightarrow0$ as $x\rightarrow0$. Will edit the answer.2012-08-26
  • 0
    @timur Thanks for noting, by the way. Of course, this means that not only does $f$ (from the original problem) not have to be $C^2$, but unlike what I originally wrote it does not have to have a second derivative everywhere.2012-08-26
  • 0
    Isn't it $f'(x)=2x\sin(1/x)-x\cos(1/x)$ (with $x$ in front of $\cos$)? I think there is no question on the existence of the derivative though.2012-08-26
  • 1
    How do you get $[y_0,y_1,y_2;f]\rightarrow 0$ as $y_i\rightarrow 0$ in the last paragraph? As you say, $f'$ fluctuates between $1$ and $-1$; and the terms in the numerator of $[y_0,y_1,y_2;f]$ approximate $f'$; then why does $[y_0,y_1,y_2;f]$ converge? Also note that my comment under the question was only directed at LVK's "pointwise version"; I didn't say that the version in the question is just the second derivative, and I doubt that it is, because of the freedom in choosing $y_0$.2012-08-26
  • 0
    @timur For $f(x)=x^2\sin(1/x)$, you get $f'(x)=2x\sin(1/x)-\cos(1/x)$ since the derivative of the $1/x$ inside the sinus is $-1/x^2$.2012-08-27
  • 0
    @joriki I realise I may have been too fast in asserting $[y_0,y_1,y_2;f]\rightarrow0$ when $f(x)/x^3$ is bounded. I noted that $[ty_0,ty_1,ty_2;f]/t$ is bounded when $t\rightarrow0$, but see now this is not enough. As for the limit $g_2(x)=f''(x)/2$, I know this claim was not in the original question; yet, I think that if $f$ is twice differentiable at $x$ (even if not $C^2$), it should have to be true. Will have to work more on the proof though.2012-08-27
  • 0
    @Einar: Yes, certainly $g_2(x)=f''(x)/2$ if that exists, so the expression in the question is *at least* as strong as the definition of the second derivative. "As has been commented already, the expression is essentially the definition of second derivative" sounded as if it can't guarantee continuity because it's *nothing more* than the definition of the second derivative -- I just wanted to clarify that that's not what my comment under the question was meant to imply.2012-08-27
  • 0
    @joriki Sorry if my comment was unclear. What I was thinking of was actually the contrary: that, much like for the case of $n=1$, the definition of the second derivative is close to being a special case of the assumed limit. However, at that time I had not yet realised that the assumption also had implication for the second derivatives in a neighbourhood of $x$. And, of course, the second derivative is not defined from a single limit defined on $f$, but is based on $f'$, which is what makes the problem technically more challenging.2012-08-27