Mark Dow

Geek art

Simple recursive systems and fractal patterns

"It seems to me that more could be done to elicit ... the nature of associations, with computers providing the means for experimentation. Such a study would have to involve a gradation of notions, of symbols, of classes of symbols, of classes of classes, and so on, in the same way that the complexity of mathematical or physical structures is investigated.

There must be a trick to the train of thought, a recursive formula. A group of neurons starts working automatically, sometimes without external impulse. It is a kind of iterative process with a growing pattern. It wanders about in the brain, and the way it happens must depend on the memory of similar patterns." Stanislaw Ulam in "Adventures of a Mathematician", 1976

Difference and sum sequences of 1-D morphisms

    These are 1-D cellular automata operating on ergodic (non-periodic and recurrent) initial conditions.

Simplest 2-symbol iterated morphisms
Difference sequences of arithmetic subsequences of Fibonacci words, F( c*n )

Difference and sum operators, definitions
Notes and questions
Programs and code

Simplest 2-symbol iterated morphisms

    Note that the initial sequence is the bottom row of the sum matrix (top image) and the top row of the difference matrix (bottom image) and summ( 0 ) == S( 0 ) == 0. See difference and sum operator definitions.

Fibonacci word
0;
0->01
1->0
 
or

0;
0->010   1->10
Period-doubling
0;
0->01  
1->00
Period-doubling
1;
0->11  
1->10
Thue-Morse 
0;
0->01
1->10
Thue-Morse 
0;
0->10
1->00

diff_of_system( 0, [0 1], [0], [ng], [0,1], 1, 0, 1, true, true );
[To Do: Considering the diff matrix as wrapped on a cylinder, left edge joined with right edge, how many triangles of each size fill the plane?]
diff_of_system( 0, [0 1], [0 0], [ng], [0,1], 1, 0, 1, true, true );		 diff_of_system( 1, [1 1], [1 0], [ng], [0,1], 1, 0, 1, true, true ); diff_of_system( 0, [0 1], [1 0], [ng], [0,1], 1, 0, 1, true, true ); diff_of_system( 0, [1 0], [0 1], [ng], [0,1], 1, 0, 1, true, true );
0; 0->011 1->00

0; 0->011   1->01

0;
0->101     1->01
0; 0->011 1->10

diff_of_system( 0, [0 1 1], [0 0], [ng], [0,1], 1, 0, 1, true, true );
diff_of_system( 0, [0 1 1], [0 1], [ng], [0,1], 1, 0, 1, true, true ); diff_of_system( 0, [1 0 1], [0 1], [ng], [0,1], 1, 0, 1, true, true ); diff_of_system( 0, [0 1 1], [1 0], [ng], [0,1], 1, 0, 1, true, true );
0; 0->001   1->0

diff_of_system( 0, [0 0 1], [0], [ng], [0,1], 1, 0, 1, true, true );

[To Do: Show how PD's differences can be seen as replacement systems.]

Difference sequences of arithmetic subsequences of Fibonacci words, F( c*n ) 

    These thumbnail links to F( c*n ) difference images are themselves every 16th value of those difference images.
c = 1, link to c = 2, link to c = 3, link toc = 4, link toc = 5, link toc = 6, link to c = 7, link toc = 8, link toc = 9, link toc = 10, link to c = 11, link toc = 12, link toc = 13, link toc = 14, link to c = 15, link toc = 16, link toc = 17, link toc = 18, link to c = 19, link toc = 20, link to c = 21, link toc = 22, link toc = 23, link to c = 24, link toc = 25, link toc = 26, link toc = 27, link to c = 28, link toc = 29, link toc = 30, link toc = 31, link to c = 32, link toc = 33, link toc = 34, link toc = 35, link to c = 36, link toc = 37, link toc = 38, link toc = 39, link to c = 40, link toc = 41, link toc = 42, link toc = 43, link to c = 44, link toc = 45, link toc = 46, link toc = 47, link to c = 48, link toc = 49, link toc = 50, link toc = 51, link to c = 52, link toc = 53, link toc = 54, link toc = 55, link to

Fibonacci word (odd) subsequences
F(c*n) 		differences (top down), link to large image every 8th of differences, link to every 4th of differnces .......... Fibonacci word (even) subsequences
F(c*n)		 differences (top down), link to large image every 8th of differences, link to every 4th of differnces
F( n ) F( 2*n )



F( 3*n ) F( 4*n )



F( 5*n ) F( 6*n )



F( 7*n ) F( 8*n )



F( 9*n ) F( 10*n )



F( 11*n ) F( 12*n )


F( 13*n ) F( 14*n )



F( 15*n ) F( 16*n )



F( 17*n ) F( 18*n )



F( 19*n ) F( 20*n )



F( 21*n ) F( 22*n )


F( 23*n ) F( 24*n )



F( 25*n ) F( 26*n )



F( 27*n ) F( 28*n )



F( 29*n ) F( 30*n )



F( 31*n ) F( 32*n )



F( 33*n ) F( 34*n )



F( 35*n ) F( 36*n )



F( 37*n ) F( 38*n )



F( 39*n ) F( 40*n )



F( 41*n ) F( 42*n )


F( 43*n ) F( 44*n )



F( 45*n ) F( 46*n )



What's with these funny "crystal grains"?
F( 47*n ) F( 48*n )


F( 49*n ) F( 50*n )


F( 51*n ) F( 52*n )



F( 53*n ) F( 54*n )


F( 55*n )


Difference and sum operators, definitions

    The image arrays on this page all share rules for their construction:  the top row of the difference matrix (bottom half) are 2-symbol sequences formed by simple replacement rules (iterated morphisms), and the adjacent rows are the result of a difference (bottom) or sum (top) operator acting on the row above or below.

    The difference operator, diff( n, S ), at an index n acting any 2-symbol sequence S = S(n) is here defined as:

diff( n, S ) = ( S(n+1) - S(n) ) modulo 2

and similarly, the sum operator, sum(n) is here defined as:

sum( n, S ) = ( sum( n-1, S ) + S(n-1) ) modulo 2


    There is one bit of information lost in the transform diff( n, S ). In particular,

diff( n, S ) = diff( n, S' ), where S' is the complement of S over these two symbols (or a cyclic permutation of the field of symbols)

    Also, sum( 1, S ) isn't fully defined because it depends on S( 0 ) which is not determined. To resolve these ambiguities, let:

summ( 0 ) == S( 0 ) == 0
or
summ( 0 ) == S( 0 ) == 1

These are arbitrary assignments. Why not make the sequence summ( 0 ) the sequence S itself, or some other sequence? Partly for economy -- it is easier to remember these as single bit arbitrary assignments. Unless otherwise noted, the diagrams all assume the convention summ( 0 ) == S( 0 ) == 0.


    The sum(n) definition can be rearranged as:
  S(n-1)  = (  sum(n) - sum(n-1) ) modulo 2
  S(n)     = (  sum(n+1) - sum(n) ) modulo 2

and the corresponding parts of the sum and diff operators identified (compare this expression of S(n) with the definition of diff(n) ).

With sum( 0 ) and S( 0 ) arbitrarily defined, diff and sum are mutually inverse operations:

S(n) = diff( sum( S(n) ) ) = sum( diff( S(n) ) )
So, for example, starting with the Period-doubling sequence on the symbols {0,1} with the usual meaning for "-" and "+", sequential differences and sums (diffm, summ) are formed below and above, respectively:

        n =   0   1 2 3 4 5 6 7 8 9 ...
 summ(PD)
 ...
 sum2(PD) = [0,1] 0 0 1 0 0 1 1 1 0 1 1 1 1...
 sum1(PD) = [0,1] 0 1 1 0 1 0 0 1 1 0 0 0 ...
      PD  = [0,1] 1 0 1 1 1 0 1 0 1 0 1 ...
diff1(PD) =       1 1 0 0 1 1 1 1 1 1 ...
diff2(PD) =       0 1 0 1 0 0 0 0 0 ...
...
diffm(PD)

where the prefix [0,1] indicates either 0 or 1 for all prefixes, not some mixture of both. These prefixes are not generally shown in the diagrams.

and these are represented in a matrix with black and white pixels like:
sum and difference matrices of Period-doubling sequence - sum and difference matrices of Period-doubling sequence modulo
2 =		 difference of sum and difference matrices of Period-doubling sequence
sum( 0 ) == S( 0 ) == 0
 or sum( 0 ) == S( 0 ) == 1 difference between two initializations
MATLAB commands:
>> imOut = diff_of_system( 1, [1 1], [1 0], 5, 1, 1, 0, 4, true, true );
>> imOut = diff_of_system( 1, [1 1], [1 0], 5, 0, 1, 0, 4, true, true );
Hardcoded:
sum_init = 0 or 1
Note that sum and diff operators, on any sequence S = S(n), are mutual inverses:

 summ( n, S ) = diff-m( n, S )
diffm( n, S ) =  sum-m( n, S )

In this example:

PD = diff1( TM ),
TM =  sum1( PD ), where
PD is the morphism  1; 0 -> 0 1, 1 -> 0 0
TM  is the morphism 0; 0 -> 0 1, 1 -> 1 0    for the sum( 0 ) == S( 0 ) == 0 prefixs (left)
and
TM  is the morphism 0; 0 -> 1 0, 1 -> 0 1    for the sum( 0 ) == S( 0 ) == 1 prefixs (center)

[To Do: Show the other PD diagrams, compare.]

    After  a symbol for S(0) is specified (arbitrarily), we find that diffm( n, S ) is defined for n = 0. What is the sequence diffn( 0, S )? I don't see a general way to specify diffn( 0, S )  for any sequence S. It looks as if this sequence is characteristic of S, because knowing the sequence diffm( 0, S ) over the natrual numbers n = 0, 1, 2, 3, ... allows S to be reconstructed using the sum operator. For the Period-doubling sequence diffm( 0, S ) starts with (red values):

        n =   0   1 2 3 4 5 6 7 8 9 ...
 summ(PD)
 ...
 sum2(PD) = [0,1] 0 0 1 0 0 1 1 1 0 1 1 1 1...
 sum1(PD) = [0,1] 0 1 1 0 1 0 0 1 1 0 0 0 ...
      PD  = [0,1] 1 0 1 1 1 0 1 0 1 0 1 ...
diff1(PD) = [1,0] 1 1 0 0 1 1 1 1 1 1 ...
diff2(PD) = [0,1] 0 1 0 1 0 0 0 0 0 ...
diff3(PD) = [0,1] 1 1 1 1 0 0 0 0 ...
diff4(PD) = [1,0] 0 0 0 1 0 0 0 ...
diff5(PD) = [1,0] 0 0 1 1 0 0 ...
diff6(PD) = [1,0] 0 1 0 1 0 ...
diff7(PD) = [1,0] 1 1 1 1 ...
diff8(PD) = [0,1] 0 0 0 ...
...
diffm(PD)

For the assumed values of S( 0 ) == 0 or 1 the two sequences are just complements (cyclic permutations over the 2-symbol field). Is there an iterated morphism with this as the fixed point?

 Si0 = 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 ... (OEIS A030300 and A030301)

where the run lengths increase by a factor of two, ad infinitum?

From OEIS A030300 and A030301:
 
An example of a sequence with property that the fraction of 1's in the first n terms does not converge to a limit. - N. J. A. Sloane (njas(AT)research.att.com), Sep 24 2007

a(n) = 0 iff n has an odd number of digits in binary, = 1 otherwise - Henry Bottomley (se16(AT)btinternet.com), Apr 06 2000

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences



    This sequence in some sense holds all the information content of the Period-doubling sequence. Given that the sequence is diffm( 0, S(n) ), the sequence S(n) can be derived from it using the sum operator.Every sequence, not just the Period-doubling, has a diffm( 0, S(n) ) sequence and the original sequence can be found from it. These pairs are conjugate in that
    Here are these prefix sequences represented as an additional left column of the sum and difference matrices:
zero-column of sum and difference Period-doubling sequence - sum and difference matrices of Period-doubling sequence modulo
2 =		 difference of sum and difference matrices of Period-doubling sequence
sum( 0 ) == S( 0 ) == 0
 or sum( 0 ) == S( 0 ) == 1 difference between two initializations
    Notice that the last (right) column of the PD( 0 ) == 0 case,  is identical with the diffm( 0, PD ) sequence (the left column)!

diffm( 0, PD ) = diffm( 2k, PD )  with PD( 0 ) == 0, m <= 2k and k an integer
   
For Thue-Morse (TM) 0; 0->01, 1->10
diffm( 1, TM ) = 1.1.0,1,0,0,0,1,0,0,0,0,0,0,0,1 ...   (OEIS A036987)

From OEIS A036987:
Fredholm-Rueppel sequence.
Sum {0..infinity} 1/10^(2^n) = 0.110100010000000100000000000000010...

a(n) = (product of digits of n; n in binary notation) mod 2. This sequence is a transformation of the Thue-Morse sequence (A010060), since there exists a function f such that f(sum of digits of n) = (product of digits of n). - Ctibor O. ZIZKA (ctibor.zizka(AT)seznam.cz), Feb 12 2008

Moebius transform of A001511. [From Mats Granvik (mats.granvik(AT)abo.fi), Jan 03 2009]

a(n) is also the number of orbits of length n for the map x->1-cx^2 on [ -1,1] at the Feigenbaum critical value c=1.401155... [From Thomas Ward (t.ward(AT)uea.ac.uk), Apr 08 2009]

[To Do: Show this for the Fibonacci word differences, but at indices that are Fibonacci numbers. No, this is better understood as prefix words being repeated, so words in columns get repeated too.]
0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0
[0,1]1,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1

Difference complement sequences

    [To Do:
    The first column of any difference matrix of a sequence is a sequence that is complementary to the sequence itself. It holds the same information, as there is a direct functional relationship between them. The difference operator applied repeatedly, diffm( n, S ),  provides the functional relationship. Mirroring a difference matrix across the n = m diagonal (top-left to bottom-right) results in the difference matrix of this complementary sequence.

    The difference complement, Sd, of a sequence S is

Sd = diffm( 1, S )
and
S  = diffm( 1, Sd )

    The example difference matrices on this page have very short descriptions, most in terms of iterated mophisms with just two rules and two symbols.

A000079 has an interesting diff matrix and difference complement.

    What sequence is the diagonal of a diff matrix? Can both S and Sd be found from this difference diagonal sequence?
]

Notes and questions

    These 2-automatic (or string rewriting, or uniform tag, or Lindenmayer) systems result in non-periodic and recurrent (ergodic) sequences. Are the diff sequences, diffm( S ) necessarily non-periodic and recurrent too? Are they necessarily the result of a similar type of system? One would think so, but what about F( 19*n )? Is F( 19*n ) the fixed point of such a dynamical system, and is it non-periodic?

    Black triangles in the difference sequence diagrams evolve from runs (1-periodic words) in the sequence at the top of the triangle. Are there systems for which difference runs never exceed a finite length? The Thue-Morse and Period-doubling differences are predictably unbounded, but it's not clear if runs are unbounded for any of the other systems.

Programs and code

    [To Do: Fix up and post diff_of_system.m, and give an example here.]

>>diff_of_system( arrayInit, rules1, rules2, nG, bSum, nDecimate, nOffset, nOversampleOut, bShow, bWrite, strOutFileStem )

------------------------------------
 Public Domain DedicationThis work is dedicated to the Public Domain.
There are no restrictions on use of the images or code on this page. Claiming to be the originator of the material, explicitly or implicitly, is bad karma. A link (if appropriate), a note to dow[at]uoregon.edu, and credit are appreciated but not required.

Comments are welcome (dow[at]uoregon.edu).