Weierstrass function

November 7, 2013

Weierstrass function from 1872 is the function f=f_{a,b} defined by

\displaystyle f(x)=\sum_{n=0}^\infty a^n\cos(b^n\pi x).

Weierstrass showed that if

  • 0<a<1,
  • b is an odd positive integer, and
  • \displaystyle ab>1+\frac32\pi,

then f is a continuous nowhere differentiable function. Hardy proved in 1916 that one can relax the conditions on a,b to

  • 0<a<1,
  • b>1, and
  • ab\ge 1.

Here, I just want to show some graphs, hopefully providing some intuition to help understand why we expect f to be non-differentiable. The idea is that the cosine terms ensure that the partial sums  \displaystyle f(m,x)=\sum_{n=0}^m a^n\cos(b^n\pi x), though smooth, have more and more “turns” on each interval as m increases, so that in the limit, f has “peaks” everywhere. Below is an animation (produced using Sage) comparing the graphs of f(m,x) for 0\le m<20 (and -10\le x\le 10), for a=1/2 and b=11, showing how the bends accumulate. (If the animations are not running, clicking on them solves the problem. As far as I can see, they do not work on mobiles.)

sage0Below the fold, we show the same animation, zoomed in around 0 by factors of 100, 10^4, and 10^6, respectively, illustrating the fractal nature of f.

Read the rest of this entry »


Analysis – On praise

November 4, 2013

Orders of infinity is Hardy’s monograph from 1910 on the work of Du Bois Reymond. From the preface:

There is, in Du Bois-Reymond’s original memoirs, a good deal that would not be accepted as conclusive by modern analysts. He is also at times exceedingly obscure; his work would beyond doubt have attracted much more attention had it not been for the somewhat repugnant garb in which he was unfortunately wont to clothe his most valuable ideas.

305 – A lower bound for n(3)

February 14, 2012

This continues the previous post on Friedman’s theorem.

I want to give a brief idea of the size of Friedman’s n(3), as defined on homework 2. The reference for what follows is

  • Harvey Friedman, Long finite sequences,  J. Combin. Theory Ser. A, 95 (1) (2001), 102–144.

Recall that n(3) is the largest possible size n of a sequence x_1 x_2 x_3\dots x_{n-1} x_n with property *, all of whose terms are 1, 2, or 3. Here, to have property * means that if i<j\le n/2, then the sequence x_i x_{i+1}\dots x_{2i} is not a subsequence of the sequence x_j x_{j+1}\dots x_{2j}.

In lecture we gave an example of such a sequence, of length 216, namely


where we use exponential notation to indicate the number of times a symbol appears consecutively, so the sequence begins


Actually, n(3) is much larger than 216. We know it is finite but, as Friedman mentions in his paper, it is an incomprehensibly large number. To explain this, we should mention the Ackermann hierarchy of functions. These are functions A_1,A_2,\dots, with each A_i:{\mathbb Z}^+\to{\mathbb Z}^+ a strictly increasing function.

Define A_1(n)=2n. Also, set


where there are n occurrences of A_k.

This is perhaps best understood by computing a few examples. We have A_1(1)=2, A_1(A_1(1))=A_1(2)=4=2^2, A_1(A_1(A_1(1)))=A_1(4)=8=2^3 and, by an easy induction, A_2(n)=2^n.

Now, A_2(1)=2, A_2(A_2(1))=A_2(2)=2^2, A_2(A_2(A_2(1)))=A_2(2^2)=2^{2^2} and, in general, A_3(n) is an exponential tower of 2s of height n.

The descriptions become more complicated now. For example, A_4(n) is an exponential tower of 2s, but its height is itself an exponential tower of 2s (of height n). For example,

\displaystyle A_4(4)=2^{\vdots ^2},

where the tower has height \displaystyle 2^{2^{2^2}}=65536.

Let me now quote from Friedman’s paper:

I submit that A_4 ( 4) is a ridiculously large number, but it is not an incomprehensibly large number. One can imagine a tower of 2’s of a large height, where that height is 65,536, and 65,536 is not ridiculously large.

However, if we go much further, then a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another.

For instance, A_4( 5 ) is an exponential tower of 2’s of height A_4( 4 ).

It seems safe to assert that, say, A_5( 5 ) is incomprehensibly large. We propose this number as a sort of benchmark. In Section 4 we prove that n( 3 ) >A_7( 184 ), which is considerably larger.

Friedman actually goes much further than this. Using computer data provided by Randall Dougherty, Friedman proves in the last section of the paper that


For all I know, this could still be very far from the actual value of n(3). And I do not know a reasonable description of an upper bound.

In technical terms, Friedman proves that the function n(k) is not primitive recursive, and actually grows much faster than the usual examples of recursive functions that are not primitive recursive. He also describes a function H (a member of the so-called Hardy hierarchy) that grows faster than n(k). This means that n(k)<H(k) for all sufficiently large k, but the argument does not give a specific bound when k=3.