Dynamics And Hierarchies

Daniel Geisler

1617 Humboldt St.

Santa Rosa CA, 95404

[email protected]

January 31, 2005

 

A combinatorial paradigm of dynamical systems is presented that provides a closed form solution for the dynamics of complex analytic systems with a non-zero Lyapunov exponent. The problem of simplifying the master equation reduces to the problem of simplifying the recurrence equation,  with each solution of the recurrence equation reflected in a corresponding case of simplification of the master equation. Exploration of the recurrence equation yields the classification of fixed points, yet the approach makes no use of topology.

Introduction

The search for closed form solutions of dynamical systems is a famous open problem in mathematics. With closed form solutions out of reach, Poincaré developed topology to derive qualitative solutions for dynamical systems. This paper demonstrates a non-topological approach to dynamical systems founded on combinatorics. The intent is to develop the simplest formulation of the theory, complex analytic dynamics, for a broad audience. The primary constraint is that only dynamical systems with a non-zero Lyapunov exponent are considered, although this may not pose a problem when considering physical systems, as it is not known whether Lyapunov exponents can be robustly zero for dissipative systems [20]. The combinatorial approach is based on the combinatoric structure hierarchies and from a single observation, consider the following derivation of the second derivative of the dynamical system,

,

evaluated at a fixed point,

,

where

·        The function’s dynamics are denoted as

,

 with the rule .

·         is a fixed point, ,

·        , a standard convention from differential equations.

Observe that the resultant expression is a recurrence equation, but that there are both differential recurrences and dynamical recurrences. The differential recurrences create an isomorphism between the combinatoric structure referred to as hierarchies, and the derivatives of the dynamical system, . Hierarchies enumerate the ways in which a given number of items may be classified. Figure 1 shows the four hierarchies possible with three items, while Table 1 lists the integer sequences associated with three different combinatoric structures including hierarchies. The three items are represented by the three leafs of the hierarchies, while the root and internal nodes are not counted.


Figure 1 – Hierarchies with 3 items

The combinatoric approach allows us to reason in terms of combinatorial structures instead of incredibly complex equations, since the equations are actually in the form of hierarchies. The primary purpose of this paper is to foster an understanding of the connection between hierarchies and dynamical systems and to develop the tools to exploit that understanding. Baez and Dolan discuss how areas of mathematics can be reformulated in a simpler and more powerful format by understanding that many mathematical structures arise from interpreting categories as set and isomorphisms as equations [1].

 

Feynman diagrams and Hierarchies

The modeling of quantum fields provides a familiar example of the utility of combinatorics. Quantum fields can be represented using Feynman diagrams and in a real sense are nothing more than the summation of all possible Feynman diagrams constructible from a primitive Feynman diagram. This is the basis of combinatorics, to start with a basic structure and a set of rules, sequentially generating a series of more complex structures from simpler structures. The process of generating all possible or valid Feynman diagrams is a combinatorial process. Each of the Feynman diagrams must then be evaluated according to the appropriate rules to determine its weight.

A similar scheme can be used to solve for the general equations of complex analytic dynamics. Hierarchies replace the Feynman diagrams. Each of the hierarchies must be evaluated, just as Feynman diagrams must be evaluated. The rules that Feynman diagrams are evaluated by are based on the type of particle interaction being modeled, while the rules that hierarchies are evaluated by are based on the classification of the fixed point. The four hierarchies of three items in Figure 1 are evaluated and summed in order to derive . The evaluation of hierarchies is far simpler than Feynman diagram since nested summations are involved instead of integration; additionally, hierarchies are trees and thus devoid of the loops and the infinities that Feynman diagrams possess.

1        Complex Analysis

The following conventions will be used throughout this paper unless explicitly stated otherwise,

a)      is an analytic function, and as such can be expressed as a Taylor series[18].

b)      , the case of the function being linear is not considered since the dynamics are trivial.

c)      is the multiplier, while , is the Lyapunov exponent which assumed non-zero in this paper.

d)      A notational conflict arises between the standard usage of n in combinatoric and dynamics. In situations where n would be used in both contexts, m will replace one of the usages of n. For example, .

e)      Issues regarding Riemann branches are not dealt with in the paper.

Theorem 1 -   Nonlinear analytic functions must have at least one fixed point.

Proof. Consider the equation , which holds for fixed points, if the equation has a solution then the function, has a fixed point. The equation can be expanded into a Taylor’s series  and since all polynomials satisfy  the function has at least one fixed point.


Theorem 2 -   Let a function be analytic, then it’s iterates are analytic.

Proof. The composite of analytic functions is an analytic function. Using general induction, if is analytic thenis analytic. is analytic, therefore is analytic.

Theorem 3 -   .

Proof.   

Theorem 4 -   Assume all derivatives ofhave a closed form solution at the fixed point , thenhas a closed form solution.

Proof. The functionis analytic, therefore it can be expressed as a Taylor series. Evaluating the series at a fixed point giveswhich proves the theorem.

This establishes the groundwork for the combinatorial portion of the paper where the higher derivatives ofare derived.

2        Combinatoric Structures

This section reviews some of the basics of combinatorics, both as a theory and practice. Three specific combinatoric structures are also covered, each based on a different type of partitioning; the partition function - partitioning unlabeled items, Bell numbers - partitioning labeled items, and hierarchies - hierarchically partitioning labeled items. A variety of mathematical problems often lead to a single combinatoric structure. This structure can then be generalized back into a more universal form. The Bell polynomials are the generalization of set partitions and are related to the equation, while the inverse Bell polynomials are the generalization of hierarchies and are related to, where  [15]. Set partitions provide a new way to work with composite functions. Since recursive functions are a type of composite functions, is it possible that there is a combinatoric structure that is representative of recursive functions? Consider the inverse Bell polynomial where,. This indicates that a dynamical system with a rationally neutral fixed point can be associated to the hierarchies combinatoric structure.

Items

1

2

3

4

5

6

7

8

9

10

Partition Function

1

2

3

5

7

11

15

22

30

42

Bell Numbers

1

2

5

15

52

203

877

4140

21147

115975

Hierarchies

1

1

4

26

236

2752

39208

660032

12818912

282137824

Table 1 - The Enumeration of Some Combinatoric Structures

 

The development of the combinatorial approach of this paper occurred quickly due to the power and simplicity of combinatorial analysis, and it’s proponents leveraging of the Internet. Two Internet sites were so important in the interactive development of this paper that had they been humans they would have been considered co-authors. The concern that the equations of dynamical systems would be too complex to work with or understand is well founded. Fortunately, understanding the combinatoric structure of the equations mitigates this problem.

Sloane’s On-Line Encyclopedia of Integer Sequences, or EIS contains over 50,000 integer sequences, allowing combinatorial structures to be identified by the integer sequences they produce. The EIS listing contain extensive references to articles and web links as well as links to related EIS integer sequences and entries in the next service. The partition function, Bell numbers, and hierarchies combinatorial structures in this paper were identified using EIS.

The INRIA Algorithms Project hosts the Encyclopedia of Combinatorial Structures, or ECS, focusing more on the grammatical construction of combinatorial structures. The formal grammar is implemented in Combstruct, a software package for Maple, and based on very elegant mathematics. [8] Working from the grammatical specification of a structure, Combstruct can compute a combinatorial structure‘s generating function, enumerate the structure, and derive random examples of the structure. The reference section list the main combinatorial structures addressed in this paper and their EIS and ECS numbers.

Specification

Structure

A=Z·set(A)

Non plane trees

B=Z+B·B

Plane binary trees

C=Z·sequence(C)

Plane general trees

D=set(cycle(Z))

Permutations

E=set(cycle(A))

Functional graphs

F=set(set(Z, card≥1))

Set Partitions

H=Z+set(H, card≥2)

Hierarchies

Table 2 - The Specifications of Some Combinatoric Structures [9]

There are two types of generating functions. Exponential generating functions (egf), express labeled combinatoric structures like Bell numbers and hierarchies, while ordinary generating functions (ogf) express unlabeled combinatoric structures, like the partition function.

Figure 2 – The generating function of the partition function, Bell numbers, and hierarchies

2.1       Integer Partitions - The Partition Function

A count of the number of additive terms in Dnf(g(z)) reveals that the number of terms is determined by the partition function of n. Consider the five ways that four identical items may be partitioned {{x,x,x,x}}, {{x,x,x},{x}}, {{x,x},{x,x}}, {{x,x},{x},{x}}, {{x},{x},{x},{x}}. A more typical way to express this is as the five ways that the number four may be expressed as the sum of positive integers 4, 3+1, 2+2, 2+1+1, 1+1+1+1. The partition function, p(n), defined as the number of ways that a positive integer n may be partitioned into positive numbers, has a long and active history in number theory. The integer partitions are visualized using Ferrer diagrams.


Figure 3 – The Ferrer diagrams of the number four

Ramanujan derived the approximation [4]

as well as discovering the partition congruence for the number 5, p(5n+4) = 0 (mod 5). Ken Ono recently discovered that the partition function has partition congruencies for all primes larger than 5.

The generating function of the partition function is

.

2.2       Set Partitions - The Bell Numbers

A summation of the coefficients of the terms of Dnf(g(z)) produce the Bell numbers of n [3,11]. Set partitions, the partitioning of labeled items, is a variation of combinatoric problem of partitioning identical or unlabeled items. Four labeled items can be partitioned 15 ways. A common idiom is that there are 15 ways to place four balls into urns or boxes. The number of set partitions of n is referred to as Bn, the Bell number of n.

Partitions

Labeled Partitions

Bell Polynomial Terms

Bell Number Diagrams

4

{{1}, {2}, {3}, {4}}

3

{{1, 2}, {3}, {4}}

{{1, 3}, {2}, {4}}

{{1}, {2, 3}, {4}}

{{1, 4}, {2}, {3}}

{{1}, {2, 4}, {3}}

{{1}, {2}, {3, 4}}

2

{{1, 2}, {3, 4}}

{{1, 3}, {2, 4}}

{{1, 4}, {2, 3}}

2

{{1, 2, 3}, {4}}

{{1, 2, 4}, {3}}

{{1, 3, 4}, {2}}

{{1}, {2, 3, 4}}

1

{{1, 2, 3, 4}}

Table 3 - Bell Number Diagrams of B4

Bell number diagrams provide a visual enumeration of the Bell numbers; the Bell number diagrams of B4 are shown in Table 2. The labeled partitions column provides the same information as the Bell number diagrams but in list format.

The exponential generating function for Bell numbers can be derived from its specification [8],

A second way to generate the Bell numbers is by using Stirling numbers of the second kind, the number of ways that n labeled items can be placed into k groups [3]. Sterling numbers of the second kind obey the identity,

                                                                                           (1)

The Bell number n is the sum of Sterling numbers of the second kind

                                                                                                               (2)

                                                                (3)

Theorem 5 -   The Bell number diagrams of Bn+1 can be generated from the Bell number diagrams of Bn.

Proof. A Bell number diagram containing n items in k partitions may include the n+1 item in two ways. The new item may be inserted into a new partition producing a Bell number diagram containing n+1 items in k+1 partitions. The other alternative is for the new item to be inserted into one of the k pre-existing partitions. See Equation (3) for algebraic version of proof.

Since Bell diagrams are rooted trees the uniqueness of the Bell diagrams is guaranteed. Note that adding a new item to the partition of a Bell diagram is analogous to adding a new partition to a Bell diagram, it is just happening one level lower in the tree.

Bell Polynomials

Riordan studied a generalization of Bell numbers using Dnf(g(z)), with ,  naming them Bell polynomials [2,11] and representing them as Yn. Comtet refers to generalization of Stirling numbers of the second kind, as partial Bell polynomials, Bn,k, but we will use Riordan’s notation of Yn,k for consistency. The following is from Riordan’s Combinatoric Identities [15],

 

                                                               (4)

where π(n) denotes a partition of n, usually denoted by, with ; where ki is the number of parts of size i. The partition function p(n) is a decategorized version of π(n), the function π(n) enumerates the partitions of n, while p(n) is the cardinality of the enumeration of π(n).

Letevaluated at

 then .

The notation  directs us to collect instances of  as powers and then convert the result to a derivative, as in .

                                                                (5)

Riordan provides the first two identities, and Comtet [3] the last,

                                                                                                             (6)

                                                                                                                           (7)

                                                                                                                      (8)

Theorem 6 -   The set partitions are isomorphic to the Bell polynomials.

Proof.  Consider the Bell polynomial in the form,

.

Note that no coefficients or exponents are used, 2 g¢(z)2 f²(g(z)) is expressed as g¢(z) g¢(z)  f²(g(z)) +  g¢(z) g¢(z) f²(g(z)).

This is Equation (5) in a different form, but it is also isomorphic to Theorem 5. The process of transforming the set partitions for Bn into Bn+1 is isomorphic to the process of differentiating Yn to obtain Yn+1.

Bell numbers and the partition function

An informal argument is made regarding the connection between the partition function and Bell numbers. They both address the same combinatoric problem but the partition function uses unlabeled balls, while Bell numbers use labeled balls.  The reason the number of terms of Dnf(g(z)) depend on the partition function is that the labels can’t be explicitly expressed using the derivatives of f(g(z)) and g(z), in part due to their multiplicative commutability. This is analogous to placing labeled balls in boxes that hide the labels but not the balls. The Bell diagrams in Table 3 are grouped by the integer partition they are associated with.

2.3       Total partitions – Hierarchies

The combinatoric structure hierarchies was discovered by Schröder and published in his 1870 paper, Vier combinatorische Probleme [16], and is also known as Schröder’s fourth problem, total partitions, and phylogenetic trees [EIS A000311]. Ironically, Schröder introduced topological conjugancy in Über iterirte Functionen [17] just one year later, in what many consider the first work on dynamical systems. The term hierarchies and the function hier(n) are from Flajolet [6,7] and used in this paper. The concept of classification as recursive partitioning is explored before continuing with an exposition of the hierarchies structure. It will be shown that the hierarchies combinatoric structure is the result of this process of classification.

Recursive partitioning and classification diagrams

The similarity between adding partitions to Bell diagrams and adding items to partitions of Bell diagrams leads to the idea of recursively or hierarchically partitioning a set. Classification diagrams will be used to represent the process of recursive partitioning. It will be shown that the combinatoric structure associated with the problem of recursive partitioning is the combinatoric structure known as hierarchies.

A new rule needs to be added for recursive partitioning, stating that internal nodes must have two or more child nodes. The absence of this rule would allow an internal node with one child node to be recursively partitioned indefinitely, creating an infinite number of trees. A new type of diagram is introduced, the classification diagram. The hexagon Bell number diagram in Figure 4 has two partitions of three items each, but a group of three items may be further partitioned in four ways. A tree structure of Bell number diagrams allows recursive partitioning to be displayed in a less visually confusing manner that displaying it with a standard tree graph.

Definition 1 -  Classification refers to the process of hierarchicalization. In other words, it is the verb associated with the noun hierarchies, as in the hierarchies combinatoric structure.

Definition 2 -  A classification diagram represents the process of recursive partitioning in the form of a tree with Bell number diagrams for nodes. Bell number diagrams containing only one partition are forbidden, as in Figure 3. The absence of this rule would allow an internal node with one child node to be recursively partitioned indefinitely, creating an infinite number of trees. Later it will be shown that these diagrams are forbidden because they are left hand values. Figure 3 represent the third, fourth, and fifth derivatives of a recursive function.


Figure 3 – Examples of Bell Number Diagrams Forbidden in Classification Diagrams

Partitions with 1 or 2 items are not displayed as their own separate Bell number diagram since no additional information would be forthcoming; a single item can’t be sub-partitioned, and two items can only be recursively partitioned in one way due to the prohibition against placing all items in a single partition.

All Bell number diagram partitions of 3 or more items have a second representation as child node Bell number diagram containing the same number of items as the original partition.

Child nodes are sorted from left to right in chronological order; a child node containing the first label would be to the left of the other child nodes.

Items and partitions are commingled in classification diagrams rather that have partitions with only one item. A “naked” single item replaces partitions containing a single item.

 
 

Figure 4 – The classification diagram and tree graph of {{{1, 5}, 3}, {{2, 4}, 6}}

An enumeration of the classification diagrams for different number of items produces the integer sequence 1, 1, 4, 236, 2752, which the EIS list as sequence A000311.  The connection between set partitions and hierarchies occur in several places, the hierarchies of n are also referred to as the total partitions of n, and hierarchical partitions. Conversely, the combinatoric structure hierarchies of height 2 [ECS 291] is a truncated version of the hierarchies structure and produces an integer sequence almost identical to the Bell numbers. Riordan’s Bell polynomials are based on set partitions while inverse Bell polynomials are based on hierarchies.

Finally, Comtet [3] provides a connection between hierarchies and set partitions by the classic derivation of the Bell numbers from sums of Stirling numbers of the second kind (2), and deriving the hierarchies from sums of associated Stirling numbers of the second kind (11). S(n,k) is the number of ways that n items can be placed into k groups. Sr(n,k) is a subset of S(n,k), where each of the k groups contain at least r items.

                                                                  

                                                                                (9)

Items

1

2

3

4

5

6

Bell Numbers

1

2

5

15

52

203

Hierarchies of height 2

0

2

5

15

52

203

Hierarchy Cross-Sections

0

1

4

14

51

202

Table 4 - The Enumeration of Some Similar Combinatoric Structures

Classification diagrams provide a way to display cross-sections of hierarchies, the fact that they are trees of height 2 allow them to capture the connectivity information.  Figure 5 shows how a hierarchy can be decomposed into overlapping hierarchy cross-sections, denoted by the gray boxes.

Definition 3 -  A hierarchy cross section is defined as a set partition with the member containing all items in a single partition excluded and all partitions containing a single item replaced by the item itself. Modeling cross sections of hierarchies must account for trees of height one as well as height two since we are considering finite hierarchies that must terminate.

Theorem 7 -   Recursive partitioning is a representation of the hierarchies combinatoric structure.

Proof. Consider the expansion of the specification for set partitions

set(set(Z, 1£card)) =

                 set(set(Z, 1£card), 0=card)

+set(set(Z, 1=card), 1=card)

+set(set(Z, 1=card), 2£card)

+set(set(Z, 2£card), 1=card)

+set(set(Z, 2£card), 2£card)

and the specification for hierarchies

H = Z + set(H, 2£card)

                   = Z + set(Z, 2£card) + set(set(H, 2£card), 2£card)

    = Z + set(Z, 2£card) + set(set(Z, 2£card), 2£card) + set(set(set(H, 2£card), 2£card), 2£card)

Set Partitions

Hierarchy cross section

set(set(Z, 1£card), 0=card)

Ø, n=0

set(set(Z, 1=card), 1=card)

Z, n=1

set(set(Z, 1=card), 2£card)

set(Z, 2£card)

set(set(Z, 2£card), 1=card)

Forbidden (left hand values)

set(set(Z, 2£card), 2£card)

Hierarchies of height=2, n>1

Table 5 - Isomorphisms

The isomorphisms between set partitions and hierarchy cross sections are summarized in Table 5. This proves that hierarchy cross sections at the root node are isomorphic to hierarchies of height£2.

H = Z + set(H, 2£card) implies that any sub-tree of a hierarchies is also a hierarchies. Therefore the hierarchy cross section taken at any node is isomorphic to hierarchies of height£2 and recursive partitioning is a representation of the hierarchies combinatoric structure.

 


Figure 5 – A Hierarchy Decomposed into Overlapping Hierarchies Cross Section

Hierarchies

Phylogenetic trees model how biological organisms are evolutionarily related, how they are classified. The Dewey Decimal Classification System and the Library of Congress Classification System are examples of phylogenetic trees; they provide a hierarchical partitioning of written human knowledge. In fact, writing this paper is an example of the hierarchical partitioning of a given set of ideas, searching for the hierarchy that minimize a cost function, where the cost function is in terms of readability. Personnel at INRIA working on a problem in classification theory originally wrote the Combstruct package for the study and generation of random hierarchies. The hierarchies structure also provides a way to model different computer hardware and software architectures.

The generating function for hierarchies [9] is derived from its specification function,

                          

                                                                                       (10)

                                                                                               

where W(z) is Lambert’s W, defined by .

A second identity for hierarchies [3] is

                                             (11)

Inverse Bell Polynomials

An interesting connection between Bell polynomials and dynamical systems is now presented.

Definition 4 -  A Lyapunov polynomial Ln is a special case of the Bell polynomial Yn, where  and the coordinate system is translated into the coordinate systems of a fixed point.

is an example of a Bell polynomial, since it is the first derivative of a composite function. In this case the composite function is a recursive function.

Consider L4

Theorem 8 -   Lyapunov polynomials are recurrence equations.

Proof.

              

                                   (12)

Note the recurrence equation is not primitively recursive; the recurrence is both dynamical and differential. As a note, while many of the presented techniques are applicable to dynamical systems in higher dimensions, equation (12) is invalid for matrices. The summand no longer consist of  terms when matrices are invoked, another related combinatoric structure must be found, one whose size is greater than the partition function but less than the Bell numbers. For an example of a more visual way of looking at the recurrence equation, let


              

 

 

Figure 6 – A graphical view of the recurrence equation for Y3

The reason for forbidding Bell number diagram with a single partition in classification diagrams becomes clear, the terms are absent from the right hand side of the equation as they are the terms we wish to solve for.

Definition 5 -  The Lyapunov recurrence equation is the recurrence equation (12) formed by Lyapunov polynomials with a non-zero Lyapunov exponent.

Theorem 9 -   When the Lyapunov exponent is non-zero

                                          (13)

Proof. Consider the Lyapunov recurrence equation (12) where .

Theorem 10 -  The hierarchies of n are isomorphic to the Lyapunov polynomial Ln.       

Proof. The Lyapunov polynomials invoke the same recursive partitioning that transforms the set partitions into the hierarchies. Since the set partitions are isomorphic to Bell polynomials, the recursive partitioned set partitions are isomorphic to the recursive partitioned Bell polynomials. Therefore, hierarchies are isomorphic to the Lyapunov polynomials.

Theorem 11 -  The hierarchies of m are isomorphic to the.

Proof. This follows directly from the isomorphism between hierarchies of m and the Lyapunov polynomial Lm.

Theorem 12 -  .

Proof. The notation used in equation (4) provides a mechanism for counting partitions and associating a derivative to them. and thereforeare associated with Bell number diagrams with k partitions. Setting prohibits the presence of Bell number diagrams with k partitions, which adds the constraint card ≠ k to the specification of hierarchies.

Theorem 13 -  Hierarchies are isomorphic to dynamical systems in the coordinates of a fixed point,.

Proof. Consider Theorem 11 with m ranging , since the theorem holds for each instance individually it holds for each instance concurrently. 

Theorem 14 -  Complex analytic dynamical systems with a non-zero Lyapunov exponent can be expressed in closed form.

Proof. Combining the Taylor series with equation (13) gives can closed form expression.

          (14)

3        Combinatorial Dynamics

The necessary background has now been developed so that a combinatorial derivation of dynamics can begin. The Lyapunov recurrence equation decomposes  into terms of . The simplest case consist of the terms associates with set(Z, k=card) as shown below. 

 


The diagram is evaluated as a recurrence equation of the products of k Lyapunov exponent,. We will derive the most general solution for the hyperbolic case and then investigate it for exceptional cases.

Definition 6 -  The Lyapunov transform refers to, the canonical Lyapunov recurrence equation.

Theorem 15 -  The general solution of the recurrence equation  is

     .                                                                                                        (15)

Proof. Expand the Lyapunov transform

,

, then solve the geometrical progression for

.

Definition 7 -  A hyperbolic Lyapunov expression is defined as  where .

In the preceding equations constraining the integer k to be greater than one allows us to work with equation (15) without the needless complication of considering the case of k=1, which is prohibited by the constraint card≥2 in equation (10). This is true for the following theorem as well. Another interpretation of the constraint is that the condition k=1 represents an evaluated expression, either the expression , from one of the n external nodes of hier(n), or a the product of two or more hyperbolic Lyapunov expressions which the Lyapunov transform has already been applied to.

Theorem 16 -  The Lyapunov transform of the product of two or more hyperbolic Lyapunov expressions is a hyperbolic Lyapunov expression.

Proof. Let , then .

, therefore

.

 

Theorem 17 -  All derivatives of hyperbolic complex analytic dynamical systems are Lyapunov expressions.

Proof. From inspection the first derivative is a Lyapunov expression. Solving the Lyapunov recurrence equation though iterative application of the Lyapunov transform derives the higher derivatives, but from Theorem 16 the result must be a Lyapunov expression.

Dynamics is essentially the process of hierarchically applying the Lyapunov transform. Equation (15) is a variant of the problem of geometrical progressions. The investigations of the exceptional cases of the Lyapunov transform lead to the natural development of the classification of fixed points.

 

3.1       Combinatorial Subspaces

This paper has described a family of combinatorial structures, integer partitions, set partitions, and hierarchies.  Consider the idea of the hierarchies combinatoric structure as a space in which simpler combinatorial structures may be embedded. The dynamics of the quadratic map provide a nice example.

Theorem 18 -  Let  be the egf. of the series c0, c1, c2, c3, …, then  is the egf. of the series ck, ck+1, ck+2, … .

Proof.  The termtherefore , then.

Theorem 19 -  The set of Bell number diagrams where all partitions have exactly two items is isomorphic the dynamics of the quadratic map.

Proof.  Consider the problem of Bell number diagrams where all partitions have exactly two items, , which is the egf. of the involutions combinatoric structure [ECS 23] and the sequence 1, 0, 1, 0, 3, 0, 15, 0, 105, 0, 945, …. The set partitions of the odd values of n are zero because if each of the k partition contains two items, then the set partition must contain items.

Consider a set partition with 2 k items, two items in each of the k partitions. Only the second item added to a partition affects the number of ways that the sets partition can be expressed; because the partitions are indistinguishable, the association of the first item with its partition is arbitrary. Enumerating the set partitions with 2 k items therefore results in partitioning. This is the double factorial numbers 1, 3, 3·5, 3·5·7, 3·5·7·9, … or multiplied out 1, 3, 15, 105, 945, …. [EIS A001147, ECS 106]. This is the same as the involutions series, but without the alternating zeros. The double factorial numbers egf. is.

For the second part of the proof, consider the hierarchies isomorphism of the quadratic map using Theorem 12 , then . We are interested in exponential generating functions, so the Taylor series expansion should produce positive coefficients, therefore .

The first derivative of H(z) is the egf. of the double factorial numbers, using Theorem 18 it is seen that H(z) and the double factorial numbers are exponential generating functions of the same combinatorial structure. 

It is important to note that while the involutions combinatoric structure is isomorphic to the quadratic maps, that the rules to evaluate involutions can’t be assumed to be the same rules as used for hierarchies.

3.2       The Classification of Fixed Points

The standard treatment of this subject can be found in [2,6].

Superattracting fixed points

The Lyapunov transform reduces to , which is beyond the scope of this paper.

Attracting and repelling fixed points

, is the general case from (15).

Theorem 20 -  The linear map of the neighborhood of the fixed point determines the global dynamics of the system.

Proof. Collecting all terms independent of n in the general hyperbolic Lyapunov expression simplifies it to . Using the fact that all the derivatives are Lyapunov expressions from Theorem 18,

 .                                                                 (16)

Equation (16) shows that n is only expressed within the Lyapunov exponent.

Attracting fixed point,

Theorem 21 -  .

Proof.  .

Repelling fixed point,

Theorem 22 -  .

Proof.  .

Irrationally neutral fixed points

Theorem 23 -  Consider the dynamics of a system with an irrationally neutral fixed point, then Lyapunov transform reduces to .

Proof.  Substitute into equation (15).

The dynamics of this case are fundamentally the same as hyperbolic dynamics. Equation (15) and theorems 16 and 17 still hold true for this case, the tools developed for the hyperbolic case are still applicable, as opposed to the case of rationally neutral fixed points. The difference is that the dynamics simplify by collapsing into the unit circle, S1, from the complex plane.

Theorem 24 -  Let have a attracting, repelling, or irrationally neutral fixed point, then .

Proof. Using equation (16) and , where

. For each term on the left hand of the previous equation, there must be a matchingterm on the right hand of the equation, with no unmatched terms of or, otherwise the equationbecomes inconsistent. Let and , if then . This implies that if then , but this causes a contradiction, therefore . Let which finishes the proof.

Rationally neutral fixed point, k1

This is the case alluded to earlier where the derivatives are both Bell polynomials and inverse Bell polynomials. The derivatives in all other cases are indirectly inverse Bell polynomials, but in the case the derivatives are inverse Bell polynomials in their own right. Two conditions occur in equation (15) when ; , and the term becomes undefined. Referring back to the original geometrical progression it is seen that the change is caused by the fact that the sum of the roots of unity is zero. This leads to the following theorem.

Theorem 25 -  The canonical Lyapunov recurrence equation simplifies towhen the dynamical system has a rationally neutral fixed point with k>1.

Proof. Let be the canonical Lyapunov recurrence equation. Using .

Rationally neutral fixed point, k=1

Theorem 26 -  The Lyapunov transformation simplifies to  when .

Proof.  Using .

4        Experimental Results

The results of this paper have been validated by using Mathematica to compute  up to z39. and then testing the following conditions up to z39,

The function  provides a nice example as it has a fixed point at zero and . This results in a number theoretic result that can be subjected to a fully symbolic validation without worrying about floating point errors. Mathematica provides a leaf count function which indicative of the size of a mathematical expression in Mathematica. Experimental results up to z39 give a leaf count of 1771 for and the leaf count of 29,106 for , yet Mathematica evaluates these expressions as identical.

Note the expression MSin is only displays the terms up to z13 due to the size of the full expression, but was computed to z39.

 

5        Conclusions

Many results of this paper have been derived using only the hierarchies combinatoric structure and the Lyapunov transform. This helps validate the assertion of complex systems researchers that the properties of complex systems are determined by a few principles interacting in complex ways. It is also supportive of a second idea from complex systems, that dynamical systems are also computational systems, in the form of the isomorphism between dynamics and hierarchies. The meaning of this isomorphism is discussed in the subsection on self-organization.

The feature of my research that I find most remarkable is its preservation of the parity between continuous and discreet mathematics. My original line of research was into recursive exponentiation, also known as tetration or hyperpowers. Addition, multiplication, and exponentiation are defined for complex numbers and thereby are continuous; tetration is only realized in mathematical literature as the exponential map, which is discreet. The exponential map is displayed in Figure 7. It is ironic that the employment of combinatorics, which is the heart of discreet mathematics, is so powerful in extending continuity into the realm of chaotic systems. The subject of tetration is addressed in subsections 5.2 and 5.3.

 

5.1       Self-Organization

Consider a dynamical system as a genetic algorithm where the individuals are the set of all possible hierarchies. Since all hierarchies are considered the genetic algorithm doesn’t need to be run in discreet generations for the evolution and production of new hierarchies. When hierarchies are used in computer architecture, they are evaluated with a cost function to obtain an optimal hierarchy. Being a typical NP problem, a good candidate hierarchy can be found in polynomial time, the hierarchy with the optimal cost is found in NP time [14]. So, the genetic algorithm in question is looking at all possible architectures where the fitness function of the architecture is just the cost function of the hierarchy. The cost/fitness functions in this case are time dependent and continuous. The question becomes, what are the features of the dominant hierarchies and how do they relate to research into the heuristics of hierarchical partitioning in computer architecture? Whatever behavior dominates the system over time, that behavior is based in hierarchies. Classifier systems are an outgrowth of genetic algorithms where the process of classification actually provides an alternative to recursion [10].

Could the ubiquity of the self-organization of systems is driven by the isomorphism between hierarchies and dynamical systems? If this is true it could be very useful in focusing certain types of research into self-organizing system. As an example consider how hierarchies, as in the more generic and pervasive non-mathematical sense of the word, are studied in self-organizing system. What if many of these generic hierarchies were actually combinatorial hierarchies? One indication would be if some of these hierarchies could be better understood as actually being the ensemble of all possible hierarchies, but with hierarchies embodying certain architectural structures dominating.

5.2       Revisiting the Lambert W Function

The purpose of this section is to point out some interest connections between dynamics and Lambert’s W function. The source of the material is On the Lambert W Function [5]. Hierarchies represent recursive functions, but only one function typifies hierarchies, its generating function . Is there any insight to be gained from viewing the generating function as an archetypal representation of dynamical systems? How instrumental is the W function in deriving closed form expressions of dynamical systems? Some interesting connections follow. 
 

Tetration

Let W(z) be Lambert’s W function, defined by, and let T(z) be the tree function, defined by , so that . The tree function is the generating function of the rooted tree combinatoric structure. Hierarchies are comprised of the leaves or external nodes that serve as the labels and unlabeled internal nodes, while all nodes are labeled in rooted trees.

 
The generating function of hierarchies would be a logical starting point for an attempt to derive a closed form identity for tetration.  The limitation of this approach is that it would not provide information as to the location of the fixed point, as the equation is stated in the coordinates of a fixed point. The Lambert W function provides the missing piece, the location of the fixed point, . Adding this piece in result is a candidate equation to be evaluated, , but notice that the equation contains two instances of the Lambert W function, each derived from radically different principles, but appearing to reflect some dual principle. This draws an unexpected connection between the Combinatorial Applications and the Iterated Exponentiation sub-sections of [5]. 
 
 
 

Linear Constant-Coefficient Delay Equations

The paper contains a sub-section, Solution of Linear Constant-Coefficient Delay Equations. These equations are continuous analogs of the recurrence equations. 
 

The Navier-Stokes equation

The W function has been used in attempt at the integration of the Navier-Stokes equation in parametric form. 

5.3       The Ackerman Function

Mathematics holds two contrary visions of arithmetic, practical and formal. A physicist use of Lie group’s exponentiated matrices is an example of the richness of practical arithmetic. The first order arithmetic of Hilbert and Ackerman provide the basis for a formal arithmetic, lofty in its infinite progression of arithmetic operators of addition, multiplication, exponentiation, tetration, pentation, hexation, and so forth, but barren of features.

Figure 7 – The exponential map by period

First order arithmetic and the Ackerman function are important in the foundations of mathematics as they help delimit what can be done with primitive recursion, but only defining operations on the whole numbers, they provides little practical help in extending the power of arithmetic. A reconciliation of these two visions of arithmetic is desirable, defining the operators of tetration, pentation, hexation, and beyond, for complex numbers and matrices. Knobel’s paper Exponentials Reiterated [13] provides an extensive survey of mathematical work related to tetration in the form of iterated exponentials.

A popular attitude is that the qualitative knowledge of dynamical systems that topological conjugancy reveals is all that is important, that the quantitative knowledge that might be obtained from knowing the equations of dynamical systems is unimportant. A concern also expressed is that the reveled equations would probably be so complex that they wouldn’t be useful from a mathematical perspective. I disagree, even if the quantitative knowledge of a dynamical system is unimportant, that doesn’t imply that the mathematics providing such knowledge is. It doesn’t imply that the quantitative knowledge wouldn’t go hand in hand with new qualitative knowledge, that new directions wouldn’t be pointed out, that new connections wouldn’t be made. Consider the problem of analyzing a hypothetical physical system where pentation of complex numbers is involved. Figure 7 shows the exponential map generated with Fractint where the fractal is colored based on the period, beginning with red for period one, and moving towards violet as the period increases. Only the large red region is period one, the smaller reddish areas have a higher period. The fractal provides some insight into tetration, but it only complex numbers tetrated by whole numbers. The tetrational map could possibly provide some insight into pentation, but the tetrational map can’t be computed without being able to define tetration for complex numbers. If pentation of complex numbers was central to the hypothetical physical system, it is likely that the system would be an enigma.

The main distinction betweenas a recursive function and as a dynamical system is that n is an integer in the former and a real number in the later. Theorem 24 shows that ifis hyperbolic then n is complex, not merely real. The utilization of exponentiation creates a correspondence between the Lyapunov exponent and the global dynamical map and a Lie algebra and its Lie group. This caused me to question the possibility of dynamical symmetries similar to the symmetries in quantum mechanics. In the final chapter of Supersymmetry in Disorder and Chaos [7], the book’s author raises the issue of why Supersymmetry is useful in the analysis of chaotic and disordered systems and states that this is likely the result of a deep formal symmetry. I believe that the existence of dynamical symmetries could explain this unexpected utility of Supersymmetry.

The dynamical symmetries could be much more complex than in the case of tetration. Douglas Hofstadter [12] presents the idea of strange loops. Consider the Ackerman function a→b→c where

a→b→1 = a+b, a→b→2 = a∙b, a→b→3 = ab, where multiple levels of recursion are present. Strange loops involve multiple levels of recursion, but the levels can become “confused”. One item may recursively yield a second item and yet also be of the same recursive order. The Ackerman function as defined for the natural numbers is too simple to embody strange loops. I am interested understanding what the Ackerman function’s most general mathematical form is and what its most general physical implementation is. The Ackerman function is defined for , where . I believe thatis true, and I suspect that even is mathematically true. I hope to address the subject of what lies beyond exponentiation in a later paper.

6        References

Structure

EIS

ECS

Partition Function

A000041

74

Bell Numbers

A000110

15

Hierarchies

A000311

69

Hierarchies of Height 2

 

291

Involutions

A0001147

23

Links

[EIS] The On-Line Encyclopedia of Integer Sequences

http://www.research.oeis.org/~njas/sequences/

[ECS] Encyclopedia of Combinatorial Structures

http://algo.inria.fr/encyclopedia/formulaire.html

Articles

[1]    J. Baez, J. Dolan, From Finite Sets to Feynman Diagrams, Mathematics Unlimited — 2001 and Beyond, Springer, (2001)

[2]    L. Carleson, T. Gamelin, Complex Dynamics, Springer-Verlag, (1993), Section II

[3]    L. Comtet, Advanced Combinatorics, Reidel, (1974), p. 133-137, p. 204-212, p. 221-225

[4]    J. Conway, and R. Guy, The Book Of Numbers, Copernicus, (1996), p. 60-61, p. 91-96

[5]    R. Corless, G. Gonnet, D. Hare, D. Jeffrey, and D. Knuth, ``On the Lambert W Function", Advances in Computational Mathematics, volume 5, http://kong.apmaths.uwo.ca/~rcorless/frames/PAPERS/LambertW/LambertW.ps, (1996), p. 329-359.

[6]    R. Devaney, An Introduction To Chaotic Dynamical Systems, Benjamin/Cummings, (1986), p. 272-279

[7]    K. Efetov, Supersymmetry in Disorder and Chaos, Cambridge University Press, (1997)

[8]    P. Flajolet, P. Zimmerman, and B. Van Cutsem, RR-1830: A Calculus For The Random Generation of Combinatorial Structures, http://www.inria.fr/rrrt/rr-1830.html, (1993)

[9]    P. Flajolet, A Problem In Statistical Classification Theory, http://algo.inria.fr/libraries/autocomb/schroeder-html/schroeder1.html, (1997)

[10] G. Flake, The Computational Beauty of Nature, MIT Press, (1999), p. 361-379

[11]  J. Harris, J. Hirst, and M. Mossinghoff, Combinatorics And Graph Theory, Springer, (2000), p. 142-148

[12]  D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, New York: Basic Books, (1979)

[13]  R. Knobel, Exponentials Reiterated, Amer. Math. Monthly 88, (1981), p. 235-252

[14]  M. Möller, R. Alur, Heuristics for Hierarchial Partitioning with Application to Model Checking, BRICS RS-00-21, (2000)

[15]  J. Riordan, Combinatorial Identities, Wiley, (1968), p. 173-175, p. 177-182, p.197

[16]  E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.

[17]  E. Schröder, Über iterirte Functionen, Mathematische Annalen, (1871)

[18]  R. Silverman, Introductory Complex Analysis, Dover, (1972), p. 204, p. 216

[19]  M. Viana, Dynamical Systems: Moving into the Next Century, Mathematics Unlimited — 2001 and Beyond, Springer, (2001), p. 1172


Appendix

The first four derivatives of the dynamical maps of the diffeomorph f with fixed point z0 are derived; of course the first derivative is well known and included for completeness.

Let , ,  and.

First Derivative

The first derivative is ubiquitous in dynamics and is often represented by λ and referred to as the Lyapunov characteristic number, its logarithm is known as the Lyapunov exponent.

Second Derivative

The second derivative is found by using Bell polynomials, which are also used in Aldrovandi and Freitas. Here a specific class of the Bell polynomials is investigated where .

When λ is non-zero a recurrence equation is formed that is easily solved as a summation.

Third Derivative

Continuing on with the third derivative,

Note that the index k1 from the second derivative is renamed k2 in the final summation of the third derivative. A certain amount of renumbering is unavoidable in order to use a simple index scheme since the additional information a more complex indexing scheme could track would be redundant. “Concrete Mathematics” is recommended for its treatment of the products of summations. As with the second derivative, an expression for the superattracting case can be formed from the third derivative by restricting summations to there first term.

Fourth Derivative

The fourth derivative is,

Hierarchies

Summing the coefficients of the complete Bell polynomials gives the Bell numbers Bm 1, 2, 5, 15, 52, 203, while summing the coefficients of  produces the sequence 1, 1, 4, 26, 236, 2752. The Encyclopedia of Integer Sequences identifies this sequence with the combinatoric structure Schröeder’s Fourth Problem, which happens to be the combinatoric structure associated with inverse Bell polynomials. Schröeder’s Fourth Problem is also known by the names hierarchies and total partitions. The Bell number Bn is the number of ways that n labeled balls can be placed into different urns. Schröeder’s Fourth Problem asks how many ways can n letters be bracketed with parentheses. The partitioning process is continued creating trees of arbitrary height whereas the Bell numbers only create trees of height two. This is the origin of the name total partitions and reflects the fact that the isomorphism between differentiation and the pointing operator causes to produce trees of arbitrary height whereas  produces trees of height two.

The following table displays the total partitions grouped by their topology and the corresponding summation. A major goal of this section is the development of an analytic functor that transforms the total partitions of m into  creating a bridge between the analytic functions of the summations and combinatorics.

Labeled Hierarchies - A000311

Unlabeled Hierarchies - A000669

Schröeder’s Fourth Problem

 

Unlabeled Hierarchies

Labeled Hierarchies

Analytic Function

1

[Z]

{A}

2

[{[Z,Z]}]

{A,B}

3

[Z,{[Z,Z]}]

{A,{B,C}}, {{A,B},C}, {{A,C},B}

[Z,Z,Z]

{A,B,C}

4

[Z,{[Z,{[Z,Z]}]}]

{A,{B,{C,D}}}, {A,{{B,C},D}}, {A,{{B,D},C}}, {{A,{B,C}},D}, {{A,{B,D}},C}, {{A,{C,D}},B}, {{{A,B},C},D}, {{{A,B},D},C}, {{{A,C},B},D}, {{{A,D},C},B}, {{{A,C},D},B}, {{{A,D},B},C}

[{[Z,Z,Z]},Z]

{A,{B,C,D}}, {{A,B,D},C}, {{A,C,D},B}, {{A,B,C},D}

[{[Z,Z]},{[Z,Z]}]

{{A,B},{C,D}}, {{A,C},{B,D}}, {{A,D},{B,C}}

[{[Z,Z,{[Z,Z]}]}]

{A,B,{C,D}}, {A,{B,C},D}, {A,{B,D},C}, {{A,B},C,D}, {{A,C},B,D}, {{A,D},B,C}

[Z,Z,Z,Z]

{A,B,C,D}

The unlabeled hierarchies are taken from:

P. Flajolet, A Problem In Statistical Classification Theory, http://algo.inria.fr/libraries/autocomb/schroeder-html/schroeder1.html, (1997)