Have you ever wondered as a kid as you watched someone use an Etch-a-Sketch, and were still adapting to using the knobs, how to draw a pen stroke curve? It turns out that you don’t really need to be an expert on the knobs, but with a lot of patience you can draw a pen stroke curve to any degree of accuracy just using the up-down, left-right in jagged steps, making shorter and shorter lines at each approximation to whatever line you’re trying to draw. Mathematically, we can say we are approximating a continuous curve on a finite interval with dyadic step functions. We will cover many topics, as I work my way through(doing exercises where needed) David Walnut’s book to try to understand uniform convergence of dyadic step functions to continuous functions on finite closed intervals, Generalized Fourier Series and orthonormal bases, and most importantly that the Haar series converges in and interestingly enough also uniformly, the intricate proof of which is at the end. I use the Theorems and Definitions directly from the book, and maybe add in a little extra detail or two that helped me better understand the proofs or exercises. To begin we go over the Heine-Cantor Theorem, that a continuous function on a compact set is uniformly continuous, the proof uses metric spaces, but less generally, the result can be used to show that a real continuous function defined on a closed and bounded interval , , with   is also uniformly continuous.

If is continuous, where and are metric spaces, and is compact, then is uniformly continuous, that is, for every there exists a such that for all with , .

The proof of the theorem can be found on Wikipedia and I’ll rewrite it here in my own words.

The proof takes full advantage of the definition of compact in a metric space, that is if every open covering of has a finite subcovering, i.e., there is a finite collection such that .

First, by definition of continuous, is continuous at each point , i.e., for every , for every there is a such that if , then . Now letting be arbitrary, since is continuous at every we can find a (note here that the is indexed by to denote that it is specific to that ) such that if is at most apart from , , then .

Note that is the ball centered at of radius and in particular these balls form an open covering for , because for every by the definition of metric, . Since is compact, there exists a finite subcovering such that .

Now we can pick the smallest because there are only finitely many of them, and denote it by , Wikipedia asserts that , but I think that should be obvious, you can’t pick out a negative number or zero out of a finite set of positive numbers. The emboldened will be the used in the definition of uniform convergence. It is important to note before proceeding that by the definition of a metric, for all , otherwise known as the triangle inequality. I used in this case but the same applies for because these properties hold for arbitrary metrics.

Given any such that , since , must be an element of some for some . Thus , and making our center point between and , by the triangle inequality:

where the last inequality follows by the definition of . Note that both , and by the definition of continuity and the way things were set up above for the deltas indexed by , . Now with in the role of the center point, a second use of the triangle inequality gives

.

In particular, thanks to the Heine-Cantor theorem we know that a continuous real function on a closed and bounded interval is uniformly continuous. Thus, if is continuous, then is uniformly continuous by Heine-Cantor. This fact is particularly useful when trying to prove Lemma 5.23 in David Walnut’s Book which is left as an exercise.

I will use/copy the definitions presented in the book for the infinity norm, or norm, and the norm, here for reference and so that the uninitiated reader is not completely lost, these are the usual definitions.

A piecewise continuous function defined on an interval is bounded (or ) on if there is a number such that for all
The -norm of a function is defined by

A piecewise continuous function defined on an interval is square-integrable (or of class or simply ) on if the integral

is finite
The -norm of a function is defined by

I also need to show what a dyadic interval is, all they are is the partitioning of the real line into intervals of length a power of two, here’s the definition directly from the book:

For each pair of integers , define the interval by

The collection of all such intervals is called the collection of dyadic subintervals of

Given , with either or , then either

or

In the latter two cases, the smaller interval is contained in either the right half or left half of the larger.

This is left as an exercise but the result should be intuitive. Given two intervals, one is the smaller one, and you can slide the smallest interval up and down the real line and it will fit snuggly inside the target zone of the larger interval if it so lands there. Either the smaller interval is outside the larger interval, they are disjoint, or it is contained inside the larger one. Since every finer partition divides every interval in two, and then the two halves in two again, and so on and so on, if a smaller interval is contained in a larger one it must be in one of the two halves, the right or the left.

Given a dyadic interval at scale , , we write , where and are dyadic intervals at scale , to denote the left half and right half of the interval In fact, and

has midpoint , and the end points can be written as and

I could also formally present the definition of a scale dyadic step function, as you can imagine it is a step function that is constant on the dyadic intervals:

A dyadic step function is a step function with the property that for some , is constant on all dyadic intervals , . We say in this case that is a scale dyadic step function.
For any interval , a dyadic step function on is a dyadic step function that is supported on .

We can now proceed to proving the lemma.

Given continuous on , and , there is a , and a scale dyadic step function supported in   such that , for all ; that is, .

Since is continuous, by Heine-Cantor, is uniformly continuous, and so for all there is a such that for all , if , then . Let be such that . If and are in the dyadic interval , then . Given a scale dyadic step function supported on , that is is constant on the intervals for , fix any point in the dyadic interval , define for all . By the uniform continuity of , what happens on one dyadic interval happens for the rest. By above (that is uniformly continuous), for every , there is a and a such that where for all , implies , for .

Since is continuous, by Heine-Cantor, is uniformly continuous, and so for all there is a such that for all , if , then . Let be such that and fix be the midpoint of the dyadic interval . If is in the dyadic interval , then satisfies . Given a scale dyadic step function supported on , that is is constant on the intervals for , define for all . By the uniform continuity of , what happens on one dyadic interval happens on the rest. By above (that uniformly continuous), for every , there is a such that such that for all , implies , for .

Less formally, we can always find dyadic intervals of length less than , and given the uniform continuity of , all points inside these intervals satisfy which implies . Fixing any point in the dyadic intervals , and letting (our dyadic step function supported on ) be equal to on each respective interval, since for all , but for all thus .

Thus it is possible to approximate a continuous function on to any degree of accuracy with dyadic step functions supported on . In fact, this is true for any closed and bounded interval , but will have some convenient properties as I will show shortly. We will develop a collection of special functions with special properties, but first the concept of orthogonality and correspondingly, orthonormality, must be defined. As stated in Walnut’s book:

A collection of functions , on an interval is a (general) orthogonal system on provided that

The collection is a (general) orthonormal system on provided that it is an orthogonal system on and

I will only consider real valued functions, thus there is no need for the notation denoting the complex conjugate. Part of Remark 2.46 also states:

… we will use the inner product notation to represent the integrals in Definition 2.45. That is, we write for any functions , and on ,

This means in particular that

I will make use of the same convenient notation as well. The question now arises about Generalized Fourier Series, which section 2.3.2 treats splendidly:

Given a function , on an interval , and an orthonormal system on , the (generalized) Fourier coefficients, of with respect to are defined by

The (generalized) Fourier series of with respect to is

and then goes on to determine when the can be replaced with . First two useful Lemmas are proved

Let be an orthonormal system on an interval . then for every , on , and every ,

it is stated as well in the text, but, the proof takes full advantage of the orthonormality of

but by the orthonormality of , if , and if , thus

and since we are only dealing with real valued functions,

, thus we have

and the desired result follows,

Let be an orthonormal system on . Then for every , on , and every finite sequence of numbers ,

Let be given, and let be an orthonormal system. Then

again as in the previous lemma, by the orthonormality of

by the previous lemma.

The two lemmas, especially 2.51, will now come in handy to show that if a generalized Fourier Series does converge to it’s infinite sum, then the generalized Fourier coefficients are precisely of the form

Given a collection of functions , on an interval , the span of , denoted , is the collection of all finite linear combinations of the elements of . In other words, if and only if for some finite sequence .

Where the related notion of mean-square (or ) closure of , denoted is defined as, if for every , there is a function such that

Let be an orthonormal system on . Then is complete on provided that every function , on , is in . A complete orthonormal system is called an orthonormal basis.

We will see that we can replace an arbitrary function with it’s Fourier series precisely when the collection of functions is complete. Theorem 2.57 contains several equivalent criteria to determine when an orthonormal system of functions is complete but I will only prove , that is, is complete on if and only if for every , on , in on , which follow by Theorem 2.55. will also be useful later, that is, is complete on if and only if every function on is in

Let be an orthonormal system on on interval . Then a function , on , is in if and only if

in on .

The statement in is equivalent to the statement of uniform convergence in , for every , there is an such that for every and , or more succinctly but it turns out the expanded definition is more useful using the

definition of mean-square closure of since we need to find a linear combination

such that , for every . That is exactly it, for every we can find an

such that and thus .

Supposing that , if , then by definition, there is a finite sequence for some , such that

Since , , therefore certainly

but the right hand side of the inequality is precisely the result of Lemma 2.51, and thus

David Walnut now leaves it as an exercise to prove that the result holds for all , this is not a difficult application of Lemma 2.50. To note that is a decreasing sequence, remember by Lemma 2.50, , where is fixed and , thus as increases, we are subtracting by a nonnegative number each time, and so

from which it follows by taking the square root of both sides, since the arguments being squared are known to be positive and the square root function is an increasing function

and is a decreasing sequence. We can now replace above with any and the result would still hold, and so .

By the definition of complete, is complete on if every function , on , is in , by Theorem 2.55, a function , on , is in if and only if , in on .
is complete if and only if for every function , on , .

The question is, is if we can find a collection of step-functions that is an orthonormal basis on ? As it will turn out, there will be many. Let’s begin by defining some functions

The dilation and translation operators can now be specified with their definitions:

Given , the dilation operator, , defined on functions , or on , is given by

Given , the translation operator, , defined on functions , or on , is given by

Given the definition of , we can then consider all dilations of and translations by of , for , that is

The collection is known as the Haar system on We will show the orthonormality of the system The orthonormality of the Haar system is shown in Theorem 5.13

The Haar system on is an orthonormal system on

If is fixed, then orthonormality can be shown in a given scale Since it is known by Lemma 5.2 that

If , then because the functions are supported on disjoint intervals, hence,

If , then

To show orthonormality between scales, suppose that where we can assume that with Again Lemma 5.2 comes in handy, there are three possibilities

As before

because the functions are supported on disjoint intervals.

is the constant on , and so also on , thus

is the constant on and so also on , thus

Theorem 5.13 does most of the heavy lifting to prove that the system is orthonormal, all that is left to check is that and , but these are easy to see

and if , then and clearly , but if , then

as well, and  is an orthonormal system.

Back to our special interval we can always consider a subset of the latter collection, namely the Haar system on ,  or , which we know must be orthonormal since it is a subset of . To show that the Haar system on is complete the book makes use of the Splitting Lemma, which I quite like thus I will present it here

(The Splitting Lemma) Let and let be a scale dyadic step function. Then can be written as where has the form

for some coefficients and is a scale dyadic step function.

Since is a scale dyadic step function, it is constant on the intervals Denote the value that take on the interval by For each interval define the scale step function on by

and takes the average values of on the left and right halves of Letting , since is a scale dyadic step function, so is Fixing a dyadic interval recall that Then

Since is a scale dyadic step function, it must be constant on the intervals and since it’s integral on is , and the interval has left and right intervals and it must be a multiple of on those intervals, and thus has the above form.

We can now prove that the Haar system on is a complete orthonormal system. It is convenient to use the equivalent statements of Theorem 2.57, in this case , that is the orthonormal system is complete if and only if every on is in Given and by Lemma 5.23 there exists and a scale dyadic step function on such that

where the second to last inequality follows because by definition of the infinity norm, thus

All that is needed is to show that is in that span of the Haar system on The Splitting Lemma can be used to write as where has the form where now since is a scale dyadic step function, the process can be repeated, and so on, until we get and where for some constants and is a scale dyadic step function on and must be constant on and is thus a multiple of It follows that is in the span of the Haar system on and and so the Haar system on is a complete orthonormal system.

By the completeness of the orthonormal system , we know that every function that is on can be replaced with its infinite generalized Fourier series

in the sense on , which is a very cool concept if you really think about it because of the counterintuitive notion of being able to build up any continuous function on with discontinuous step functions that are equally spaced above and below the -axis, and if we need to build a function that is always above the -axis, that is when the function comes to the rescue and bumps everything up!

In closing, one can show that the generalized Fourier series, or Haar series above is also uniformly convergent to , in addition to being convergent in sense. Before proving this we’re going to need the Mean Value Theorem for integrals.

Let be continuous, then there exists a such that

Consider where , then by the first part of the Fundamental Theorem of Calculus, is continuous on and differentiable on and for all and correspondingly the Mean Value Theorem applies on , and there must exist some such that

By the second part of the Fundamental Theorem of Calculus thus since ,

Lastly, some notation is needed, let’s denote the mean of a continuous function on by In other words the Mean Value Theorem for Integrals implies there is a such that Also, the function is handy in condensing notation, where is a set

If is a continuous function, then the Haar series

is uniformly convergent to

The argument will be by induction, first consider only , then and , and First note that

Now consider summing until , then , and together with the first term we get

I will include summing up to to illustrate the subtlety of the argument, and it will strengthen the perception of the apparent pattern.

Since and , , thus

Assuming for we have then adding to both sides yields

and

thus

and so the result holds for

By induction, for all

By the Mean Value Theorem for integrals, there is some such that , thus we have a dyadic step function on the right hand side that is uniformly convergent to by the first proof of Lemma 5.23.