Journeying through the fractal slopes of mount Meru with two-seeded recursive sequences

The Hindus have been fascinated by sequences and series from the beginning of their civilizational memory recorded in the Veda. This continues down to the medieval mathematician Nārāyaṇa paṇḍita, who discovered a general formula (sāmāsika paṅkti) that can be to obtain the ‘Meru-średhī’ (known in the west as Fibonacci’s sequence). He uses it as a model to explain the population dynamics of cows. In modern terms the formula goes thus:
Let f[1]=f[2]=1. These are two seeds of the sequence. Then,
f[n]=f[n-1]+f[n-2], where n=3,4,5....
One sees that this yields the famous sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… i.e. a version of Nārāyaṇa’s Dhenu-saṃkhya or cow-numbers. We may denote this special sequence as M[n]. It is well-known that,
\displaystyle \lim_{n \to \infty} \dfrac{M[n+1]}{M[n]}=\phi, where \phi is the Golden ratio.
Thus, as we have illustrated before, the Dhenu-saṃkhya can be obtained as integer values of a function based on \phi.

Closer to our times, following the discovery of a everywhere continuous but nowhere differentiable function by Bernhard Riemann, the Japanese mathematician Teiji Takagi discovered another remarkable curve of this type. Let function s(x) be defined as,
s\left(x\right)=\min \left(\left(x-\lfloor x \rfloor \right),\textrm{abs}\left(x-\lceil x \rceil \right)\right)

Then the Takagi function is defined as,
f\left(x\right)=\displaystyle \sum _{n=0}^\infty w^n \cdot s\left(2^n x \right) Parameter w=0.5 gives an aesthetically pleasing curve. As can be seen from the figure the curve as has fractal form keeping with its undifferentiable nature

Figure1_Takagi_curveFigure 1. The Takagi curve (red)

A lay person may wonder why we are mentioning these two seemingly disparate pieces of mathematics together. The connection between them becomes apparent via the remarkable sequences discovered by the scientist-philosopher Douglas Hofstadter. He first presented these ideas in his curious book ‘Gödel, Escher, Bach: An Eternal Golden Braid’.

Our own journey through these began in the days of our youth when we chanced upon Hofstadter’s book in a book-store. Not having the cash to procure it we spent sometime taking in its braided ideas right there. While that encounter was not enough to take in all the sequences he discussed in the book we got enough of the basic idea to experiment by ourselves. The basic idea behind the Hofstadter class of sequences is a generalization of the procedure behind the Meru-średhī. This can be illustrated with the sequence with which we first experimented:
f[n]=n-f[f[n-1]], where f[1]=f[2]=1 and n=3,4...
Like M[n] it is also initiated with two seed values but the definition of the subsequent elements involves a nested definition. The definition itself looks simple and yields the following sequence:
1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14…

One notices that unlike the Dhenu-saṃkhya-s this sequence covers all the positive integers. However, some are repeated multiple times. Interestingly, we observe that f[3]=2, f[5]=3, f[8]=5, f[13]=8, f[21]=13. Thus more generally f\left [M[n] \right ]=M[n-1]. Moreover, once we have this sequence we can also write out pairs of the form (f[n],n). The set of such pairs can be represented as edges of a graph (i.e. f[n] \rightarrow n), which turns out to be a tree.

Figure2_Meru_treeFigure 2. Graph of (f[n],n=1:50)

The tree displays an interesting structure which resembles an evolutionary process of descent through modification. In this we can recognize a “primitive” lineage which is the line of descent comprised of M[n]. The remain lines of descent branching off from it also display a Meru-średhī process albeit each at a different level. For e.g. we have the line of descent: 3, 4, 7, 11, 18, 29, 47…

Our next advance in understanding these sequences came from reading a paper by Clifford Pickover, which presented a means of graphically visualizing the structure of these sequences. Inspired by this we used a slightly different graphical representation to study the structure specified by these sequences. One of the notable Hofstadter sequences is,
f[n]=f[f[n-1]]+f[n-f[n-1]]

The technique we used to visualize the sequence is to subtract a certain factor proportional to n from the f[n] in order to render the values along the x-axis rather than as along the curve which the increasing f[n] follows. We call this rectification. Thus we rectify the above sequence by plotting (n, f[n]-\tfrac{n}{2})

Figure3_Hofstadter_batrachionFigure 3. (n, f[n]-\tfrac{n}{2}) for f[n]=f[f[n-1]]+f[n-f[n-1]]

Remarkably we get ever larger copies of the Takagi curve, with each loop progressing in width as 2, 4, 8, 16, … i.e. the powers of 2 (Figure 3). Thus, the curve captures the binary base representation of integers up to a give integer and the fractal has a predictable form. The successive loops of the structure also represent a journey into the fractal structure of the Takagi curve.

Figure4_MallowsFigure 4. f[n]=f[f[n-2]]+f[n-f[n-2]] rectified as f[n]-.68n

Another such sequence was discovered by Mallows (Figure 4), which has an overall similar behavior as the above sequence of Hofstadter. However, rather than the regular symmetric Takagi curve generated by the sequence it has a more jagged fractal curve with a distinct pattern of two peaks followed by three peaks.

Returning to the original sequence we studied, f[n]=n-f[f[n-1]], we can rectify it using f[n]-\tfrac{n}{\phi}.

Figure5_Hofstader_one_by_phi_doubly_recursiveFigure 5. f[n]=n-f[f[n-1]]

It has a very different structure from the above sequences. Instead of ever-increasing loops this is characterized by rapid but fixed bandwidth of oscillation with basic reoccurring units incorporated into higher order reoccurring units, reflective of its tree structure discussed above.

One would notice that the generative formulae for these sequences, unlike that of the Meru-średhī, involve doubly nested specifications. Such specifications mostly lead to sterile sequences because the index n for a given f[n] can drop below 1 or above the current value thus killing the sequence. Nevertheless, there are several additional productive formulae beyond the above that lead to a range of interesting behavior. These are illustrated before.

Figure6_Hofstadter_pseudo_repetitiveFigure 6. f[n]=f[n-f[n-1]]+f[n-f[n-2]-1] rectified using f[n]-\tfrac{n}{2}.

Somewhat similar theme to the above case with similar looking motifs nested at multiple levels giving rise to a pseudo-repetitive appearance.

Figure7_Hofstadter_pulsationsFigure 7. f[n]=f[n-f[n-1]]+f[n-f[n-2]] rectified using f[n]-\tfrac{n}{2}

This is one of Hofstadter’s discoveries which has ever larger pulses of high intensity fluctuations of similar form separated by regions of low intensity fluctuations. The repetition of the same basic form albeit with variation at larger and larger scales resembles the formula generating the Takagi curve.

Figure8_Hofstadter_sinusoidFigure 8. f[n]=f[f[n-1]]+f[n-f[n-2]-1] rectified using f[n]-\tfrac{n}{2}

Another Hofstadter sequence similar to the above but the pulses themselves are arranged on waves of ever-increasing wave-length giving it the form of ever-larger sigmoids.

Figure9_Hofstadter_Wolfram_wavyFigure 9. f[n]=f[f[n-1]]+f[n-2\cdot f[n-1]+1].

This is non-linear in terms of its central growth curve and cannot be perfectly rectified. Hence, the factor f[n]-.42n^{.818} is used. This was discovered by Stephen Wolfram in an excellent introduction to these sequences for a lay reader although he does little to acknowledge his predecessors’ work. It shows a higher order wavy pattern of increasing wavelength but within it the pulsations show much more irregularity.

Figure10_Hofstadter_randomFigure 10. f[n]=f[n-f[n-1]-1]+f[n-f[n-2]-1] rectified using f[n]-\tfrac{n}{2}

Unlike the above this shows neither regions of reduced intensity pulsation nor a higher order wavy pattern. Instead is simply shows a chaotic pattern of fluctuations which grow in magnitude with n.

If the above sequences were generated using doubly nested specifications we also find complex behavior emerging from triply nested formulations. We discovered for ourselves some such sequences which are illustrated below.

Figure11_triply_nested_.6823Figure 11. f[n]=n-f[f[f[n-2]]] rectified using f[n]-0.6823n

This is a triply nested relative of the generative formula shown in Figure 5. Like it is shows a fixed bandwidth along with some basic motifs reoccurring at various scales.

Figure12_triply_nested_seahorseFigure 12. f[n]=f[f[f[n-1]]]+f[n-f[f[n-2]]-1] rectified using f[n]-0.45n

This formula resembles the doubly nested version seen in Figure 8 and like it shows a higher order wave-like structure with increasing wavelength. Each wave module is a “sea-horse”-like structure, which develops an increasingly complex pattern of fluctuations as it grows larger in size.

Figure13_Mt_MeruFigure 13. f[n]=f[f[f[n-1]]]+f[n-f[f[n-1]]] rectified using f[n]-\tfrac{n}{\phi}

This triply nested formula shows a link to the Meru-średhī and \phi similar to the one explored in Figure 5. The rectified form shows cycles of increasing size in the sequence 2, 5, 13, 34 … i.e. M[2k+1],\; k=1,2,3,4.... These cycles are a journey up and down a fractal mountain, which we term the journey through the slopes mount Meru. The mountain has some fractal faces and others which are sheer cliffs. Further, the set of edges f[n] \rightarrow n constitute a tree graph as seen with the above-described doubly nested version. Remarkably, there is one primitive lineage from which all other lineages branch off which is the Meru-średhī with the Dhenu-saṃkhya-s (Figure 14). Now the branches also show a curious relationship to the Dhenu-saṃkhya-s: at any section through a given level in the tree we have that many branches as the numbers that would count up to the corresponding Dhenu-saṃkhya in that level. Thus at the level of first branch the numbers are 4, 5 (2 branches); at the next level the numbers on the branches are 6,7,8 (3 branches); at the next level 9,10,11,12,13 (5 branches) and so on. Thus on each branch there is an inherent relationship to the underlying Dhenu-saṃkhya, which can be seen in the figure. Whereas the graph in Figure 2 shows a strict bifurcation this graph shows a pattern for n-furcation related to the Dhenu-saṃkhya: if a non-primitive branch emerges from a number the M[n] then it will display n-3-furcation (Figure 14). Thus, the branch from M[4]=3 will show 1-furcation; the branch from M[5]=5 will show 2-furcation; the branch from M[6]=8 with show 3-furcation and so on.

Figure14_meru_tree_triple_recursiveFigure 14. The branching graph for f[n]=f[f[f[n-1]]]+f[n-f[f[n-1]]]

One could explore other interesting features of these sequences but we stop here with the philosophical insight the imparted to us. Simple two-seeded sequences like the Meru-średhī represent a process that is directly dependent on the state of the system at two former time points. Thus they evolve directly as a function of time like the unconstrained growth of an organism under ideal conditions, which Nārāyaṇa tried to model. However, the doubly and triply nested generative formulae, while starting from the same seeds, do not develop directly dependent on time but rather as a second or third order consequence of states at former time points. Thus, while the simple case might be seen as a direct reaction of two former reactants leading to a current product, the nested specifications can be seen as reactants at former time leading to further reactants which in turn specify the current product. What we observer is that by the simple act of including this kind of higher order specification we get several different kinds of complexity: Some forms of complexity like the Takagi curve while intricate have a regular pattern to them. Other forms show different degrees of higher order pattern but are much more irregular in their immediate behavior. Finally there are those that are very irregular and not obviously predictable beyond some general statistical features. Actions on simple strings can generate complex forms — hence, these sequences could serve as an analogy for how higher order dependencies naturally generates complex structure in nature. Such processes could also be behind the patterns of other systems like human history. A question that leads to a deep philosophical puzzle is whether such processes might be active in biological systems.

Advertisements
This entry was posted in art, Scientific ramblings and tagged , , , , , , . Bookmark the permalink.