# sequences with a fractal dimension

This is inspired by the self-similarity of the celebrated Golay-Rudin-Shapiro sequence, more exactly, of its alternating partial sums. (This latter one is oeis 020990). The pictures show the 550 first terms, then the 9000 first terms.

It makes sense to define a certain fractal $$F$$ as the "limit" of the graph $$\Gamma=\{(n,a_n)\}_{n\ge0}$$.
More precisely:
Fix a rectangle $$R\subset\mathbb R^2$$, e.g. the unit square. Take the part $$\Gamma_k$$ of $$\Gamma$$ between $$n=2^{2k-1}$$ and $$n=2^{2k+1}-1$$ and rescale it to a graph $$\Gamma^0_k$$ that fits $$R$$ best.
Then because of the geometrical (almost-) similarity of the $$\Gamma^0_k$$, the limit $$F:=\lim\limits_{k\to\infty}\Gamma^0_k\subset\mathbb R^2$$ is well-defined. Note that its Hausdorff dimension is $$d=3/2$$.

Other examples:

• the sequence oeis 004074 that defines likewise the Blancmange curve, dimension $$d=1$$
• sequences linked to the Gray code, like 003188 or 006068, both with $$d=1$$
• Stern's diatomic series yields a fractal with dimension $$d=\frac{\ln 3}{\ln 2}$$
• it makes sense to relate (if not to identify) the Cantor set with the sequence $$1,0,1,0,0,0,1,0,1,...$$ where $$a_n=1$$ iff the ternary representation of $$n$$ has only 0's and 2's (equivalently, the cellular automaton where at each step $$1 \mapsto 101$$ and $$0 \mapsto000$$), and to say this sequence has dimension $$\frac{\ln2}{\ln3}$$. Likewise for the "fat Cantor set" iterating 11100111 (dimension $$\frac{\ln5}{\ln8}$$) and all other sorts of Cantor dust.
• the devil's staircase, obtained by "integrating" the Cantor set, corresponds to this sequence, and a "mirrored" version of it can be found here.
Like for most other sequences of this kind, the ressemblance is best seen when looking at a range from either $$1$$ to $$2^n$$, or (for some, like the Blancmange curve) from $$2^{n-1}$$ to $$2^n$$.
• Other sequences of Toothpick and Cellular Automata type

Note that it is not at all straightforward or even possible to define a fractal for every self-similar integer sequence $$a=(a_n)_{n\ge0}$$ (self-similar meaning as usual that there is a $$k\ge2$$ and $$\lambda$$ such that $$a_n=\lambda a_{kn}$$). On the other hand, there are also sequences with a fractal-like appearance without being self-similar in the above sense.

Question:

• Has the idea of the "fractal dimension" of certain sequences been treated before?

## 2 Answers

Interestingly, fractal dimensions of the human DNA sequence have been analyzed and different embeddings considered: http://biocomplexity.indiana.edu/jglazier/docs/papers/20_DNA_Analysis.pdf.

• "...indicating the presence of signiﬁcant information content in DNA sequences not explained by base or dimer frequencies". Interesting indeed! – Wolfgang Jan 7 '13 at 8:53

Taking a truncated integer sequence is essentially the same as defining the "heights" of the line endpoints of a 2-dimensional curve, similar to http://www.gameprogrammer.com/fractal.html my guess is that this is not really new, but rather a cumbersome way to define self-similar curves.

Making a reasonable scaling will in some examples, as above, give a well-defined limit curve. Maybe it is possible to compute the Hausdorff dimension by doing a discrete Fourier transform of the sequence. The spectrum should be quite interesting, I think.