Weierstrass functions: continuous but not differentiable anywhere | Hacker News Reader

Weierstrass functions: continuous but not differentiable anywhere

puzlet.com

78 pointsgballan43 comments

Open articleView on HN

This function produces an audio signal that sounds like an organ.

https://gist.github.com/improv32/8414717

http://vocaroo.com/i/s13ZO9QOMULL

All those lovely harmonics ... now dreaming of filter envelopes.

I am quite surprised it does not sound like white noise.

Anyway, I played the output of that script through some filters, and this sounds nice:

play -c 2 weierstrass.wav gain -12 loudness chorus 0.5 0.9 50 0.4 0.25 2 -t 60 0.32 0.4 2.3 -t 40 0.3 0.3 1.3 -s reverb gain 12

Ah, it's easy to see why it won't sound like white noise. The standard function is a Fourier series - a sum of sine waves. It's a power series where the b parameter must be an odd positive integer value 7 or greater. If we want the n = 0 case to map to 20 Hz (minimum of human hearing), and the maximum frequency we can hear is 20kHz (valid for children) then the highest term we can hear is the solution to 20000/7^n = 20; 7^n = 1000, n = 3.55, which means that we'll only be able to hear the first three terms.

This will sound quite interesting, but it's a really bad approximation of the Weierstrass function! http://www.wolframalpha.com/input/?i=sin%28x%29+%2B+0.9*sin%...

Makes sense now, thanks.

In white noise the power spectral density (power per Hz) is flat, that is, every frequency contributes equally. A Weierstrass frequency distribution is very far from that.

That's pretty much a defining feature of all (infinitely iterated) fractals [1]

[1] https://en.wikipedia.org/wiki/Fractal

Cool! I didn't appreciate that. I think its interesting to see that behavior in an everyday Fourier series though.

I'm not sure that I'd call something with an infinite number of non-zero Fourier coefficients an "everyday" Fourier series. :)

Heh. I hear you. But but on the other hand, a sawtooth is perfectly everyday with an infinite series of coeffs: http://en.wikipedia.org/wiki/Triangle_wave .

Any sharp edge in an image has an infinite number of frequencies once Fourier transformed.

This is why images get blurry when resized up! For some reason better algorithms never seem to become popular.

Every function with a Fourier series will have an infinite number of non-zero Fourier coefficients unless it's merely a finite sum of sinusoids. (Like, obviously.) So yeah, those are "everyday" Fourier series.

The construction of the Weierstrass function (http://en.wikipedia.org/wiki/Weierstrass_function) was new to me, even though I suffered through a semester of baby Rudin.

To me, the canonical example of a continuous but nowhere differentiable function is: any Brownian motion sample path.

Which, like the Weierstrass function, illustrates that functions that look simple may be so weird that our standard intuition does not apply.

any Brownian

Almost any. Although they have probability zero of actually occurring, a Brownian motion can generate a continuous path.

Nitpicky, but this is a comment thread about math.

As long as you're nit picking, I'd suggest you re read carefully what you wrote, because it is wrong.

What you meant to say is that on a set of measure zero, the paths can have points where continuity is not satisfied. But you did not say that.

In any case, the version of Brownian motion I studied was the version that excludes this null set. ;-)

Yes I meant to say differentiable, brownian motion is always continuous. But with probability zero, brownian motion can generate a differentiable curve.

Take the typical random walk construction as the limit of a piecewise continuous curve. I.e., 50% chance of being y=x, 50% chance of being y=-x on [0,1], then subdivide. With zero probability, the walk can converge to a straight line x=t, which is certainly differentiable.

It's early in the morning and I had no caffeine.

You have used a particular construction of B.M. that happens to admit a differentiable function (on a set of measure zero). But other constructions need not have this property; in fact, you could make a version (in the technical sense of that term, see http://almostsure.wordpress.com/2009/11/03/stochastic-proces...) of the B.M. that uses your construction, but removes the null set of differentiable sample paths.

In other words, this property ("differentiability on null sets") is not characteristic of a B.M., it is incidental to your construction. I can't believe you bothered to fuss about these hypothetical properties on null sets when we are dealing with cadlag processes on a separable index set. Sheesh.

I agree, no one cares in probability theory on the behaviour of BM on this null set. It could be as well a Weierstrass function that it will not change anything to the law of your process.

I was finding it hard to understand why it wasn't differentiable (guess my maths is getting a bit rusty) until I read the below[0] which helped it make sense to me:

>The function has detail at every level, so zooming in on a piece of the curve does not show it getting progressively closer and closer to a straight line. Rather between any two points no matter how close, the function will not be monotone.

[0] http://en.wikipedia.org/wiki/Weierstrass_function

Good point, thanks. I added the quote from wikipedia, and moved the link from the CoffeeScript to the HTML.

Also note that your code is for a differentiable finite approximation, unless you implement unlimited zoom.

Also fun is the Dirichlet function[1], which is discontinuous at every point yet is integrable everywhere. There's also a similar function that is discontinuous at all rational numbers but continuous at all irrational numbers[2].

[1] http://en.wikipedia.org/wiki/Dirichlet_function [2] http://en.wikipedia.org/wiki/Thomae%27s_function

In a similar vein, the cantor function [1] (also known as the devil's staircase) is continuous and has derivative 0 almost everywhere, but still manages to increase in value.

[1] http://en.wikipedia.org/wiki/Cantor_function#Properties

I believe that is only true when you consider certain types of integration. E.g. True for Lebesgue, false for Riemann

In analysis, people generally mean Lebesgue integrable unless otherwise specified.

Fractal curves like the Koch snowflake are likewise continuous and nowhere differentiable.

John McCarthy (yes, the inventor of Lisp) has a simpler to analyze construction of a Weierstrass-like function from a triangle wave:

http://www-formal.stanford.edu/jmc/weierstrass/weierstrass.h...

Here's the big picture. When you analyze variations in f at the kth scale by setting |dx| = 2^(-2^k), the only term that really contributes is the kth term, 2^(-k) g(2^(2^k) x), since the higher terms completely vanish and the lower terms are insignificant by comparison. Thus a difference quotient df/dx at the kth scale is very nearly the derivative of 2^(-k) g(2^(2^k) x), which is just +/- 2^(-k) 2^(2^k). This has unbounded magnitude as k increases (the exponential term 2^k outgrows the linear term -k). For a differentiable function the rate of variation should settle down at finer scales. Instead of settling down at finer scales, McCarthy's function actually gets progressively more jagged.

If you want to grok the details, step 3 in his proof may be too terse. When bounding max(n < k) |dg(2^(2^n) x)|, he uses that the greatest variation in g occurs when x and x+dx are on the same line segment. The max slope of any g(2^(2^n) x) for n < k occurs when n = k-1 and is +/- 2^(2^(k-1)). Hence

    max(n < k) |dg(2^(2^n) x)| <= 2^(2^(k-1)) |dx| = 2^(2^(k-1)) 2^(-2^k).

>Fractal curves like the Koch snowflake are likewise continuous and nowhere differentiable.

they nowhere "differentiable" in classic, smooth sense - ie. no tangent affine bundle of _whole_ dimension exist, ie. nowhere a tangent line (less tangent plane, etc...) exists. That isn't surprising of course and obviously calls for extended notion of differentiability - like a tangent "bundle" of non-whole, fractal dimension. One can even imagine a Taylor/power series using such differentiability...

I did some stuff with a professor in undergrad where I was a code monkey for his harmonic analysis research, and to be more useful(since I hadn't had much analysis) I went to the lectures of his HA course and this was one of the few things I retained.

Personally I think the cool thing about these(and also fractals, which display this as iterations go to infinity) is that they have infinite lengths in a finite(though obviously infinitely subdividable) span.

See also, smooth but analytic nowhere:

http://en.wikipedia.org/wiki/Fabius_function

Quick and dirty landscape/horizon generator for games?

That's more or less the idea behind Perlin noise. Start with a low frequency high amplitude smooth function, then sum it together while increasing the frequency and decreasing the amplitude.

See here for more: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

For anyone looking for more of these, you may enjoy the book Counterexamples in Analysis (http://www.amazon.com/Counterexamples-Analysis-Dover-Books-M...)

You can modify it slightly and get a function that has no integral, though it still has a well defined area under its curve (do the limit after the subtraction of the two otherwise-would-diverge sums).

Not sure what you mean by this, since your comment has no context -- there are no limits or sums in the link. However, even the humble Riemann integral would be able to find the area under the graph of a bounded function on a compact interval which is continuous on a set of full Lebesgue measure. Any other function only has a "well-defined area" for some seriously stunted notion of area; you can integrate more functions with a different integral, but what one calls a "well-defined area" pretty much depends on what kind of integral you're using at that point.

Consider this function:

    f(x) = sum[n = 0 to infinity]((1/2)^n sin((1/20)^n pi x))

It converges because each successive term is bounded by [-1/2, +1/2]. But if you integrate it you get:

    f(x) = sum[n = 0 to infinity](10^n / pi cos((1/20)^n pi x))

(Well... you get that if you play fast and loose about swapping the order of the integral and the sum)

Which diverges because the input to the cosine function limits to 0 as n -> infinity, so the cos limits to 1, and we get 10+100+1000+10000...

But if you integrate from two points and delay doing the limit until after then you get

    F(x1, x2)
    = sum[n = 0 to infinity](10^n / pi (cos((1/20)^n pi x2) - cos((1/20)^n pi x1)))
    = sum[n = 0 to infinity](10^n / pi (2*sin(pi/2 (1/20)^n (x1-x2))*sin(pi/2 (1/20)^n (x1+x2)))

Which, for large n, acts like:

    ~= sum[n = 0 to infinity](10^n / pi (2*(pi/2 (1/20)^n (x1-x2))*(pi/2 (1/20)^n (x1+x2)))
    = sum[n = 0 to infinity]((1/40)^n pi/2 *(x1-x2)(x1+x2))

Which converges.

Apologies for any math mistakes. This was all off the cuff. I wouldn't be surprised if some of the more general integration or summation strategies can also handle this case.

What you did in the limit in your second expression does not make any sense. You can't obtain the indefinite integral (the expression with cos()) and then take the limit as n -> infinity. This is not meaningful.

You can only do that with a definite integral (under conditions).

Using your reasoning, even a function like exp(x) would not integrate, because the terms in the integral of its series expansion would all go to zero as n -> infinity.

Another way to think about this is that each term in the indefinite integral you wrote has an arbitrary constant of integration, which can depend on n, that you did not include. This constant precludes you from actually finding the limit.

I mentioned that I was playing fast and loose when swapping them. But nevermind that exact process, let's be a bit more direct.

1. Can you give me any function whose derivative is the function I specified? (i.e. I give you permission to force all the integration constants to zero)

2. Can you compute the area under the curve from `x1` to `x2` of the function I specified?

3. Do you agree that you can do (2) but not (1)?

I see what you're getting at now. Let's check the conditions for integrability. Your function is bounded (everywhere, but let's restrict to [0,1]). But I'm not sure it is continuous due to the limit process.

If you can't show it's continuous almost everywhere (as noted by @clintonc) then it is not Riemann-integrable, therefore its integral will not exist. That would be the answer to (1).

If you go through some manipulations (i.e., (2)) and get an expression that seems correct, but the underlying function is not actually Riemann-integrable (as in (1)), then I'd suggest your manipulations have fooled you.

So, do you know the answers to these questions?

The function is continuous. The cumulative effect of the sum after the nth item are bounded by a [-2^-n, 2^-n] offset, and varies very slowly as x is changed (the argument to cos is divided by increasingly huge factors). I haven't done an explicit epsilon-delta proof, but I'm confident I could make one work by using those two facts.

So I don't expect to be able to show lack of Riemann-integrable-ness via that route. ... I just don't think it has an antiderivative.

... wait, this makes no sense. I've made a mistake because if the function is continuous then it must have an antiderivative by the first fundamental theorem of calculus. I will have to actually do the epsilon-delta proof and find out where I made the tricky mistake. Probably something to do with that infinity...

The series (of continuous functions) converges uniformly, which means that it's Reimann integrable. And you can compute its integral as a sum of the integrals inside the sum (which you showed upthread).

Also, as hinted upthread, just change

f(x) = - sum[n = 0 to infinity](10^n / pi cos((1/20)^n pi x))

f(x) = - sum[n = 0 to infinity](10^n / pi (cos((1/20)^n pi x) - 1))

That gives you an actual formula for the antiderivative that converges at every point.

Bingo. Very clear.

No, no! We don't want that!

What we want is differentiable everywhere but where the derivative is not Riemann integrable!!!!!! Everyone should have one of those, just to carry around.

We might keep in mind that a function is Riemann integrable iff it is continuous everywhere except on a set of measure 0. So, we want the points where the function is not continuous to be of positive measure!

Much more than you ever wanted to know about continuity, differentiability, and the Riemann integral!

Much simpler construction: http://en.wikipedia.org/wiki/Takagi_function

Reply on news.ycombinator.com