Thread: Problem in metric spaces

Hi and happy new year,

Here is a problem in metric spaces. And don't worry; it's not a homework. It's just that my exam is in 2 days so I have to be prepared. Here we are:

In the metric space (C[a,b] , dinf) consider

Ak = {g:[a,b]-->R | |g(t1) - g(t2)|<or = k|t1 - t2| for all t1,t2 in [a,b]}

Bk = {f:[a,b]-->R | f is differentiable and |f'(t)|< or = k for all t in [a,b]}

Show that:

1) Ak is closed.

2) Ak = the closure of Bk.

3) A = union of all Ak, k>0 is not closed.

4) The closure of A = C[a,b]

I solved (1) that Ak is closed and in (2) I was able to prove that the closure of Bk is a subset of Ak (which results from Lagrange and (1)). The problem now is to prove that Ak is a subset of the closure of Bk and to prove (3) and (4).

Thanks a lot

If you can show any member of A_k can be uniformly approximated by something in B_k arbitrarily well, you've got part 2. Some nice class of functions in B_k--polynomials, trigonometric polynomials--should do the trick. However, I haven't worked out any details. I would imagine that this works for part 4, too, and part 4 implies 3.

For part 4 we can use Weirstrass aprroximation theorem: any function in C[a,b] can be approximated by a polynomial. But since any polynomial is a Lipshitz function (provided the interval is closed), then any function in C[a,b] can be approximated by a Lipshitz function, so that all Lipshitz functions are indeed dense in C[a,b].

For part 3, it suffices to show that there is a function in C[a,b] that's not Lipshitz. This is not as straightforward as it seems because the interval is closed. Actually the function that does that is pretty tricky: it must be the limit of a sequence of functions that are uniformly convergent, and this limit must have a very extreme slope. Something like a saw-tooth sequence that gets more and more sharp but is unformly convergent. Such a sequence can be made of course, but it's not straightforward.

The great problem is in part 2. The problem is that many Lipshitz functions are not differentiable. So, first I assumed that g(t) in Ak is not differentiable at a certain t0. Then I finally got a sequence of functions (using some kind of smoothing) in Bk that approach that g(t), so that g(t) is in the closure of Bk. And the same applies if g(t) is not differentiable for a finite number of points. The real problem is that some Lipshitz functions observed in Brownian motion are not differentiable at an infinite number of points. Naturally my smoothing argument now fails because the intervals intersect no matter what you do (I can explain in more details if you don't get what I mean). So the problem is tough, no doubts about that.

I went to my professor, he had a solution using "convolutions" I think, something I haven't studied yet. He also had an idea that combined this smoothing idea and the mean value theorem, but it became very complicated to write.

Whatever, it was a nice problem, if one gets a simpler answer (even after the exam) I'd be pleased to read it.

For 3: how about f(x) = x^1/2 on [0,1] (or suitably modified for [a,b])?

For 2: Okay, so we know from Weierstrass that polynomials are dense in C[a,b]. If we have some f in A_k, we approximate it by polynomials p_n. Let k_n = sup{|p_n(x)-p_n(y)|/|x-y|} over x≠y in [a,b], i.e. this is the smallest value of k so that p_n is in B_{k_n}. Then k_n approaches a limit less than or equal to k, and we may as well assume it approaches k. Now (k/k_n)p_n is an element of B_k, and I bet you a nickel you can go through the computations to show that the sequence (k/k_n)p_n converges uniformly to f.

I can't tell you how I laughed when I tried again. You definitely inspired me the solution of part 2... so simple and we complicated it so much in the faculty... here we are

Let f in Ak. Then from Weirstrass th, there is a sequence of polynomials {pn}n in C[a,b] such that pn--->f.
==> for all eps > 0 there is an n0 in N such that sup|pn(t) - f(t)| < eps for all n > n0. ==> |pn(t) - f(t)| < eps for all t in [a,b] for all n> n0.
let eps = 1/2m, then |pn(t) - f(t)| < 1/2m for all t in [a,b] for all n>n0.

Now, |pn(t1) - pn(t2)| < or = |pn(t1) - f(t1)| + |pn(t2) - f(t2)| + |f(t1) - f(t2)| by applying the triangle inequality twice. But f is in Ak. Hence
|pn(t1) - pn(t2)| < 1/m + k|t1 - t2| for all n > n0
as m --> inf we have
|pn(t1) - pn(t2)| < k|t1 - t2| for all n>n0 for all t1, t2 in [a,b]
==> pn(t) is in Ak for all n > n0.
now, let {qn(t)}n a new sequence of polynomials such that q1(t) = pn0(t), q2(t) = pn0+1(t)...etc then {qn}n is a sequence of polynomials included in Ak and qn--> f. Furthermore, {qn}n is differentiable for any n since it is a polynomial.

Finally, |qn'(t)| = lim |qn(t) - qn(t0)| / |t - t0| as t-->t0 but qn is in Ak, hence |qn'(t)| < k

Hence, {qn(t)}n is in Bk
==> f is in the closure of Bk ==> Ak is a subset of the closure of Bk

Really thanks a lot, you've been a great help.

As for 3, beleive me it's not that simple. x^1/2 is actually a Lipshitz function on R, so what about a closed interval? If you don't beleive me, notice that on [a,b] at least, |(x1)^1/2 - (x2)^1/2| < or = |b^1/2 - a^1/2|.

I don't think we can find a function in one line. But thanks again, maybe you can find one.

x^1/2 is not Lipschitz on R. Note that a differentiable function which is Lipschitz has bounded derivative. x^1/2 has unbounded derivative as x goes to 0. (Evidently this must be the typical example of a non-Lipschitz function, as Wikipedia gives it here: http://en.wikipedia.org/wiki/Lipschitz_continuity.)

There's still a minor problem with your proof for 2. The index n₀ depends on epsilon and hence depends on m. So as you let m go to infinity, n₀ potentially goes to infinity. In fact, you may have that NONE of the polynomials p_n actually lie in A_k. That was the issue I was trying to address with my solution--I multiplied p_n by a constant c_n so that c_np_n is in A_k. Since f is in A_k, I may choose c_n tending to 1 as n goes to infinity. This modified sequence of polynomials still tends to f.

You're right about both...

Ok, so everything is taken care of except part 2. I still don't understand how exactly you get your Kn, the definition you gave is a bit obscure to me. But here is how I think I fixed my proof: we had

For all eps > 0 there is an n0 in N such that

|pn(t1) - pn(t2)| < eps + k|t1 - t2| for all n > n0

For eps = |t1 - t2|,
|pn0(t1) - pn0(t2)| < (k+1)|t1 - t2|
==> |(k/k+1)pn0(t1) - (k/k+1)pn0(t2)| < k|t1 - t2|
For eps = |t1 - t2|/2,
|pn0+1(t1) - pn0+1(t2)| < (k+ 1/2)|t1-t2|
==> |(k/k+1/2)pn0+1(t1) - (k/k+1/2)pn0+1(t2)| < k|t1 - t2|
and so on,
For eps = |t1 - t2|/n+1,
|pn0+n(t1) - pn0+n(t2)| < (k+ 1/n+1)|t1-t2|
==> |(k/k+1/n+1)pn0+1(t1) - (k/k+1/n+1)pn0+1(t2)| < k|t1 - t2|

Now, let {qn}n a sequence in C[a,b] such that
q1 = (k/k+1)pn0
q2 = (k/k+1/2)pn0+1
and so on.
qn = (k/k+1/n)pn0+n-1
Then {qn}n is in Ak. qn is a polynomial, hence differentiable and qn--> f since pn-->f.

The rest is the same. What do you think?

I think I may owe you a nickel. I think I found a mistake in the idea I originally suggested for number 2. I'm going to redouble my efforts to come up with a viable proof.

Your new proof is very similar to my old idea, and you actually get around the problem that I found in my proof: I claim for any e > 0, you can find N so that for n ≥ N, |p_n(t₁) - p_n(t₁₂)| < (k+e)|t₁ - t₂|; you correctly state that this inequality should be ≤ e + k|t₁ - t₂|. However, there's a small kink in the rest of your proof. You let your epsilon depend on a specific pair of points but then use the resulting inequality (which only holds for those points) to make a statement about uniform convergence, and this isn't kosher.

It seems to me that there could exist an e > 0 such that none of the polynomials is in A_k+e. The uniform metric doesn't prevent us from approximating anything by a differentiable function with arbitrarily large derivative.

How about this? Let's assume [a,b] = [0,1]. First, we approximate our function by piecewise linear functions. Let f be in A_k, and let's define f_n as follows:

If x is in the interval [i/2ⁿ, (i+1)/2ⁿ], 0 ≤ i < 2ⁿ, then we can we can write x = (1-t)(i/2ⁿ) + t((i+1)/2ⁿ) for some t in [0,1]. Then let:

f_n(x) = (1-t)f(i/2ⁿ) + tf((i+1)/2ⁿ)

The slope of any of these lines is at most k in absolute value, so our function is in A_k. It approximates f well:

|f(x) - f_n(x)| = |f(x) - (1-t)f(i/2ⁿ) + tf((i+1)/2ⁿ)| ≤ (1-t)|f(x) - f(i/2ⁿ)| + t |f(x) - f((i+1)/2ⁿ)| ≤ k(1-t)(x-i/2ⁿ) + kt((i+1)/2ⁿ) - x)

If you go through the arithmetic, this last quantity is equal to:

kt(1-t)/2^n-1 ≤ k/2ⁿ⁺¹

As t(1-t) takes its maximum at t = 1/2. Thus we've reduced the problem to approximating piecewise linear functions in A_k by differentiable functions in A_k. This isn't too hard, although describing it explicitly as above is a little tricky. I think it's best to just describe this process: to approximate a piecewise linear function, replace each vertex with a circular arc which meets up with the line segments so as to be differentiable, and you can do this in such a manner that the approximation is as good as you want.

I understand what you mean. Your idea is actually getting pretty close to the one we've been thinking about in the faculty... mmm, but we have a problem if the number of vertices of that piecewise linear function is infinite. Can this happen with your functions? because it happened with ours, which is what spoilt the whole thing.

But it seems my professor suddenly got more clever. I was in the exam and guess what, he put that problem in it. Then he came to me in the middle of the exam and said "think again about the problem... it actually has a very simple solution". "I did find one actually." "Good". (the one I found was my modified proof I wrote here). However, as I wasn't 100% sure it was correct I chose another question (we had to solve 4 from 6, I think I solved 5).

After that exam (which by the way was my final exam) he said "ah, I can't beleive you couldn't solve such a simple problem..." Here is what he got: (I can't use mathtype here so I'll use I(f)p->k to denote the integral of f from p to k

Let f(t) be in Ak and define F(t) as follows:
F(t) = I(f(x)dx a-->t. Then F'(t) = f(t).
But F'(t) = Lim n(F(t+1/n) - F(t)) as n-->inf. ---(*)
Let {fn}n a sequence in C[a,b] defined as
fn = n(F(t+1/n) - F(t)).
Then fn is differentiable for all n.
Furthermore |f'n| = n(f(t+1/n) - f(t)) < or = k
Hence {fn}n is in Bk. But from (*) fn --> f.
Hence f is in the closure of Bk ==> Ak is a subset of the closure of Bk.

Great Still, even if the problem had a simple answer, i'm glad we complicated it. That smoothing argument we've been thinking about will probably be useful for other problems.

Thanks very much for your time.

That's pretty nifty!