SEMINARANKÜNDIGUNG

Im Sommersemster 2004 werde ich ein Seminar anbieten über

endliche dynamische Systeme.

Endliche dynamische Systeme sind durch Abbildungen f : X → X einer endlichen Menge X in sich beschrieben. Man ist am Verhalten der interierten Abbildungen f^{n} : X → X interessiert, dem dynamischen Verhalten des Systems. Voraussagen darüber sind sind schon in den einfachsten Fällen recht schwierig. Von besonderem Interesse sind Fixpunkte und periodische Punkte.

Eine umfangreiche Theorie befaßt sich mit Abbildungen der Form f : K^{n} → K^{n}, wobei K ein endlicher Körper ist. Alle solchen Abbildungen werden durch Polynome über K beschrieben. Falls f eine lineare oder affine Abbildung ist, kann man das dynamische Verhalten von f vollständig beschreiben. Falls die Polynome von f ausschließlich Monome sind und K = 𝔽_{2} ist, ist viel über Fixpunkte und periodische Punkte bekannt. Ein solches System kann als boolsches Netz mit AND Operatoren aufgefaßt werden.

Umfangreiche Anwendungen sind in der Informatik, den Biowissenschaften, der Verkehrstechnik, den Elekrizitätsnetzen und vielen anderen Wissenschaften zu finden.

Wir werden auch spezielle dynamische Systeme studieren, sogenannte sequenzielle dynamische Systeme, bei denen die Abbildung f durch eine besondere Konstruktion gegeben ist.

Anmeldungen können ab sofort gerichtet werden an

• Herrn Dr. Y. Sommerhäuser, Zi. Nr. ,

• Frau S. Kaiser, Zi. Nr. 430,

• oder an mich per Email.

gez. B. Pareigis

Date: 29. April 2004.

2 SEMINAR SS04

Inhaltsverzeichnis

1. Graphentheorie 2 1.1. Schlichte Graphen 2 1.2. Gerichtete Graphen – Digraphs 5 1.3. Categories 5 1.4. More on graphs 6 2. Finite dynamical systems 7 2.1. Finite dynamical systems 7 2.2. Cellular automata 9 2.3. The state space or phase graph 10 2.4. Real dynamical systems 11 2.5. The functional graph 13 2.6. 13 3. Polynomial systems 13

1. Graphentheorie

1.1. Schlichte Graphen. Definition 1.1. Die Menge A ∘ A = {{a, b}|a, b ∈ A} ⊂ P(A) heißt Menge der ungeordneten Paare in A. Definition 1.2. Ein Graph ist ein Tripel (V, E, π) bestehend aus der Menge V der Knoten (engl. vertex, vertices), der Menge E der Kanten (engl. edge) und der Endpunktbildung π : E → V ∘ V. Für eine Kante k ∈ E heißen die Knoten a und b mit π(k) = {a, b} Endpunkte von k. Eine Kante k und ein Knoten a heißen inzident, wenn a ein Endpunkt von k ist. Eine Kante k heißt eine Schlinge, wenn π(k) = {a} eine einelementige Menge ist. Ein Graph heißt schlicht, wenn π injektiv ist und der Graph ohne Schlingen ist. Ein Graph heißt endlich, wenn er nur endlich viele Kanten und Knoten besitzt. Bemerkung 1.3. Ein endlicher schlichter Graph wird häufig durch seine Adjazenzmatrix dargestellt; z.B.

\begin{aligned}& v_{1} & v_{2} & v_{3} & v_{4} \\ v_{1} & 0 & 0 & 1 & 0 \\ v_{2} & 0 & 0 & 1 & 1 \\ v_{3} & 1 & 1 & 0 & 1 \\ v_{4} & 0 & 1 & 1 & 0 \end{aligned} = (\begin{matrix}0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix})

wobei V = {v_{1}, …, v_{4}} und E dargestellt ist durch die 1-en in der Matrix. Diese Matrix stellt den Graphen

[figure]

dar. Die Matrix muß spiegelsymmetrisch zur Diagonalen sein, weil jeder Kante nur ein ungeordnetes Paar {v_{i}, v_{j}} zugeordnet wird. Definition 1.4. Ein Teilgraph eines Graphen (V, E, π) besteht aus Teilmengen E_{1} ⊂ E, V_{1} ⊂ V, so daß π(E_{1}) ⊂ V_{1} ∘ V_{1} gilt. Ein Teilgraph (V_{1}, E_{1}) heißt spannender Teilgraph, wenn V_{1} = V ist. Ein Teilgraph (V_{1}, E_{1}) heißt gesättigter Teilgraph oder von V_{1} induziert, wenn π^{−1}(V_{1} ∘ V_{1}) = E_{1}. Definition 1.5. Sei X = (V, E, π) ein endlicher Graph. Der Grad d(a) eines Knotens a ∈ V ist die Anzahl der mit a inzidierenden Kanten, wobei eine Schlinge mit Endpunkt a doppelt zu zählen ist. a ∈ V heißt isolierter Punkt, wenn d(a) = 0 ist.

Allgemein gilt für einen endlichen schlichten Graphen 0 ≤ d(a) ≤ |V | − 1. a ∈ V heißt ein Endknoten in X, wenn d(a) = 1.

Sind je zwei verschiedene Knoten eines endlichen schlichten Graphen X durch eine Kante verbunden, so heißt X vollständig. Die Vervollständigung eines endlichen schlichten Graphen X = (V, E, π) ist (V, V ∘V \V, id), wobei V ∘V \V = {{a, b}|a, b ∈ V; a ≠ b}.

Ein erstes einfaches aber weitreichendes Abzählprinzip ist in dem folgenden Satz angegeben. Satz 1.6. In einem endlichen schlichten Graphen X = (V, E, π) gilt

∑_{a∈V} d(a) = 2|E|.

Proof. Jede Kante in E hat zwei Endpunkte, die beide in der linken Summe berücksichtigt werden. Sie wird also links genau zweimal gezählt. □

Folgerung 1.7. Die Anzahl der Knoten ungeraden Grades in einem endlichen schlichten Graphen ist gerade.

Proof. Die Knoten geraden Grades tragen nur gerade Summanden in der linken Summe bei. □

Ebenso wie bei algebraischen Grundstrukturen gibt es auch bei Graphen Homomorphismen, also Abbildungen, die die besondere Struktur von Graphen berücksichtigen. Definition 1.8. Seien X = (V, E, π) und Y = (V′, E′, π′) Graphen. Ein Homomorphismus f : X → Y besteht aus zwei Abbildungen f_{V} : V → V′, f_{E} : E → E′ mit

∀k ∈ E[π(k) = {a, b} ⟹ π′f_{E}(k) = {f_{V} (a), f_{V} (b)}].

Es werden also Knoten auf Knoten und Kanten auf Kanten so abgebildet, daß ihre Inzidenz erhalten bleibt.

Ein Isomorphismus f : X → Y ist ein Homomorphismus, zu dem ein weiterer Homomorphismus g : Y → X existiert mit gf = id_{X} und fg = id_{Y}. Zwei Graphen heißen isomorph, wenn zwischen ihnen ein Isomorphismus existiert.

Selbst bei endlichen Graphen ist es oft nicht leicht, zu erkennen, ob zwei gegebene Graphen isomorph sind. Für diesen Zweck wollen wir jetzt ein kleines Hilfsmittel entwickeln. Definition 1.9. Sei Y = (V′, E′) ein Teilgraph des schlichten Graphen X = (V, E, π). Dann ist X \ Y := (V, E \ E′) ein Teilgraph von X, genannt Komplement von Y in X. Das Komplement eines schlichten Graphen X = (V, E, π) ist sein Komplement in der Vervollständigung. Beispiele 1.10. 1. Das Komplement von

[figure: in; ist]

2. Das Komplement von

[figure: ist]

Satz 1.11. Zwei schlichte Graphen sind genau dann isomorph, wenn ihre Komplemente isomorph sind.

Proof. Da das doppelte Komplement eines Graphen der Graph selbst ist, genügt es aus der Isomorphie X ≅ Y auf die Isomorphie X′ ≅ Y′ zu schließen. Wir identifizieren entlang π, also E ⊂ V ∘ V. Sei f : V_{X} → V_{Y} bijektiv und f(E_{X}) = E_{Y}, wobei f(E_{X}) = {{f(a), f(b)}|{a, b} ∈ E}. Dann ist f(V_{X} ∘ V_{X} \ E_{X}) = V_{Y} ∘ V_{Y} \ E_{Y} . □

Beispiel 1.12.

[figure: ≅; , denn]

[figure: ≅]

Übung 1.1. (1) Zeigen Sie, daß die Graphen

[figure: ≅]

isomorph sind.

(2) Sei X ein schlichter Graph mit 15 Kanten und 12 Knoten, so daß alle Knoten ungeraden Grad haben. Zeigen Sie, daß X mindestens 3 Endknoten besitzt.

(3) Wieviele Kanten hat ein vollständiger schlichter Graph K_{n} mit n Knoten?

(4) Sei X ein schlichter Graph mit sechs Knoten. Zeigen Sie, daß X oder sein Komplement X′ ein vollständiges Dreieck K_{3} als Teilgraphen enthält.

1.2. Gerichtete Graphen – Digraphs. Definition 1.13. Ein gerichteter Graph (directed graph, digraph) ist ein Tripel (V, E, π) bestehend aus der Menge V der Knoten (engl. vertex, vertices), der Menge E der Kanten (engl. edge) und der Endpunktbildung π : E → V × V. Für eine Kante k ∈ E heißen die Knoten a und b mit π(k) = (a, b) Anfangs- bzw. Endpunkt von k. Eine Kante k und ein Knoten a heißen inzident, wenn a ein Anfangs- oder Endpunkt von k ist. Eine Kante k heißt eine Schlinge, wenn π(k) = (a, a) ist. Ein gerichteter Graph heißt schlicht, wenn π injektiv ist und der Graph ohne Schlingen ist. Ein Graph heißt endlich, wenn er nur endlich viele Kanten und Knoten besitzt. Bemerkung 1.14. Ein endlicher schlichter gerichteter Graph kann ebenfalls durch seine Adjazenzmatrix dargestellt werden; z.B.

\begin{aligned}& v_{1} & v_{2} & v_{3} & v_{4} \\ v_{1} & 0 & 0 & 0 & 0 \\ v_{2} & 0 & 0 & 0 & 0 \\ v_{3} & 1 & 1 & 0 & 1 \\ v_{4} & 0 & 1 & 0 & 0 \end{aligned} = (\begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{matrix})

wobei V = {v_{1}, …, v_{4}} und E dargestellt ist durch die 1-en in der Matrix. Diese Matrix stellt den Graphen

[figure]

dar. Die Matrix ist nicht mehr spiegelsymmetrisch zur Diagonalen.

Jeder gerichtete Graph hat einen ”unterliegenden“ Graphen mit denselben Knoten und Kanten und der Abbildung \overline{π} : E →^{π} V × V → V ∘ V, wobei die Abbildung V × V → V ∘ V gegeben ist durch (a, b) ↦ {a, b}. Definition 1.15. Seien X = (V, E, π) und Y = (V′, E′, π′) gerichtete Graphen. Ein Homomorphismus f : X → Y besteht aus zwei Abbildungen f_{V} : V → V′, f_{E} : E → E′ mit

∀k ∈ E[π(k) = (a, b) ⟹ π′f_{E}(k) = (f_{V} (a), f_{V} (b))].

Es werden also Knoten auf Knoten und Kanten auf Kanten so abgebildet, daß ihre Inzidenz und Richtung erhalten bleiben.

Ein Isomorphismus f : X → Y ist ein Homomorphismus, zu dem ein weiterer Homomorphismus g : Y → X existiert mit gf = id_{X} und fg = id_{Y}. Zwei Graphen heißen isomorph, wenn zwischen ihnen ein Isomorphismus existiert.

1.3. Categories. Definition 1.16. Let C consist of

(1) a class ObC whose elements A, B, C, … ∈ ObC are called objects,

(2) a family {Mor_{C}(A, B)|A, B ∈ ObC} of mutually disjoint sets whose elements f, g, … ∈ Mor_{C}(A, B) are called morphisms, and

(3) a family

{Mor_{C}(A, B) × Mor_{C}(B, C) ∋ (f, g) ↦ gf ∈ Mor_{C}(A, C)|A, B, C ∈ ObC}

of maps called compositions.

C is called a category if the following axioms hold for C

(1) Associative Law: ∀A, B, C, D ∈ ObC, f ∈ Mor_{C}(A, B), g ∈ Mor_{C}(B, C), h ∈ Mor_{C}(C, D) :

h(gf) = (hg)f;

(2) Identity Law:

∀A ∈ ObC ∃1_{A} ∈ Mor_{C}(A, A) ∀B, C ∈ ObC, ∀f ∈ Mor_{C}(A, B), ∀g ∈ Mor_{C}(C, A) :

1_{A}g = g and f1_{A} = f.

Examples 1.17. 1. The category of sets Set.

2. The categories of R-modules R-Mod, k-vector spaces k-Vec or k-Mod, groups Gr, abelian groups Ab, monoids Mon, commutative monoids cMon, rings Ri, fields field, topological spaces Top.

Each category with a set of objects (a small category) has an ”underlying“ directed graph.

For arbitrary categories we adopt many of the customary notations. Notation 1.18. f ∈ Mor_{C}(A, B) will be written as f : A → B or A →^{f} B. A is called the domain, B the range of f.

The composition of two morphisms f : A → B and g : B → C is written as gf : A → C or as g ∘ f : A → C. Definition and Remark 1.19. A morphism f : A → B is called an isomorphism if there exists a morphism g : B → A in C such that fg = 1_{B} and gf = 1_{A}. The morphism g is uniquely determined by f since g′ = g′fg = g. We write f^{−1} := g.

An object A is said to be isomorphic to an object B if there exists an isomorphism f : A → B. If f is an isomorphism the so is f^{−1}. If f : A → B and g : B → C are isomorphisms in C then so is gf : A → C. We have: (f^{−1})^{−1} = f and (gf)^{−1} = f^{−1}g^{−1}. The relation of being isomorphic between objects is an equivalence relation.

1.4. More on graphs. The following has to be adapted to the previous definitions!

Definition 1.20. A digraph is called a rooted tree (Wurzelbaum), if there is a vertex w, the root (Wurzel), such that there is exactly one walk from every vertex a to w.

The root w of a rooted tree is uniquely determined.

2. Finite dynamical systems

2.1. Finite dynamical systems. Definition 2.1. A finite dynamical system consists of a finite set X and a map f : X → X. The elements of X are called states of the system, X is called the state space. Examples 2.2. (1) Any computer program can be viewed as an action on the set

X of all possible states of a computer. If The computer has 1 GB memory (and no other memory is used) then it has 8 · 10^{9} cells and each cell can be in two states (1 or 0), so the computer has 2^{8·10^{9}} ≈ 10^{24·10^{8}} states. In each time step the program will change the states of some of these cells, i.e. it will map X to X.

(2) A simple medical example: Each person in the world can be in two states, healthy or sick. We have 7 · 10^{9} people in the world, so mankind can be in any of 2^{7·10^{9}} health states. Everyday the state of a person changes according to the following rules: if he has met a sick person during the previous 24 hours he will be sick. If he has encountered only healthy persons, he will be healthy (possibly recovering from his own previous sickness). If we know which person meets which person within 24 hours we have a map from the health states of mankind into health states of mankind.

(3) Consider a set of four cells (a_{1}, …, a_{4}), each one allowing the states {false, true}. Then the state space of the system is

X = {(α_{1}, …, α_{4})|α_{i} ∈ {false, true}} = 𝕂^{4}

where 𝕂 = {false, true}. So the system has 2^{4} = 16 states. The function f : X → X is described as

(α_{1}, …, α_{4}) ↦ (α_{3}, α_{1} AND α_{4}, α_{4}, α_{1}).

Problems:

(a) Is f bijective, injective, surjective?

(b) Are there states c = (α_{1}, …, α_{4}) such that f^{n}(c) = c for some n ≥ 1, i.e. are there fixed points (n = 1) or periodic points (n > 1)?

(c) Find a state c which is not in the image of f, f(c′) ≠ c for all states c′.

(d) How many states c are there such that f^{3}(c) = c?

2.2. Cellular automata. Cellular automata were invented by John von Neumann and Stanislav Ulam in order to simulate certain natural systems and the phenomenon of self-reproduction. The most popular example of a cellular automaton is the so-called ”Game of Life“ introduced by Conway in the 70’s. The reference is: J. H. Conway, 1970 unpublished. Other references are the articles of M. Gardner in 1970-1972 in Scientific American or^{1}, and the books^{2}. Note that this game is named after Conway and Golay^{3} (Golay’s game has an underlying hexagonal tiling^{4}). This game is defined as follows. We have an infinite two-dimensional board whose elementary squares are called cells. A cell can be living or dead. The neighbors of a cell are defined to be the eight cells surrounding it. There is a regular time period. At each time step the cells are updated in a parallel way:

(1) if the number of living neighbors of a cell is exactly 2, then the cell keeps the same value (living or dead);

(2) if the number of living neighbors of a cell is exactly 3, then the cell will take the value living whatever the previous value was;

(3) if the number of living neighbors of a cell is any other number, then the cell will take the value dead whatever the previous value was.

In other words a cell dies either if it is isolated or in an overcrowded environment. It comes to life or survives if the number of living neighbors is just right.

Instead of considering an infinite board, we can replace each elementary square by its southwest corner. The corner (instead of the cell) will take the values living or dead. The board itself will thus be replaced by the square lattice ℤ^{2}. We will use this alternative representation in the formal definition below.

1M. Gardner, Wheels, life and other mathematical amusements, W. H. Freeman and Company, 1983

2E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning ways for your mathematical plays, vol.2, Academic Press, 1982, and J. L. Casti, Alternate realities. Mathematical models of nature and man, John Wiley & Sons, 1989.

3C. P. van Nieuwkasteele, K. A. Post, Some investigations on the Conway-Golay game Life, EUT-Rep., Eindhoven 84-WSK-03 (1984) 282–296. (Zentralblatt 582.92019.)

4M. Garzon, Models of massive parallelism. Analysis of cellular automata and neural networks, Texts in Theoretical Computer Science, Springer, 1995.

Typical problems studied in the Life game are: structures that propagate (the so called gliders), structures that give birth to structures identical to themselves (this question is close to the original problem), patterns that have a periodic time evolution, crashes between structures, existence of configurations without predecessors (called gardens of Eden), computations achieved by evolving patterns...

We begin with an intuitive definition of a cellular automaton. We start from a set that can be finite or infinite (this set is usually a grid). For each element a in this set we are given a finite number of elements of the set including the element a itself that are called the neighbors of a. We have a map from this set to a set of states (usually finite): this map is called a configuration. The images of configurations can be seen as observables. We also have an updating function called the local function (or local rule): to obtain the new value assigned to an element, we need the element itself, and the values of all its neighbors (we insist that the set of neighbors of an element contains this element). The update is done in parallel: the new values are computed simultaneously. Definition 2.3. • A cellular automaton on a set F is defined as follows: we are

given for each element a ∈ F (also called a cell) a finite subset N(a) of F that contains a and is called the set of neighbors of the cell a. We are also given a set of values k (usually finite). Finally we are given for each a ∈ F a local map f_{a} from k^{N(a)} to k (where k^{N(a)} is the set of maps from N(a) to k). A configuration is an element of k^{F}, i.e., a map from F to k.

• The local maps f_{a} induce a global map f from the set of configurations to itself as follows. Let c be a configuration. We define the configuration f(c) by:

for each a ∈ F, f(c)(a) := f_{a}(c|_{N(a)})

where c|_{N(a)} is the restriction of c to the set N(a).

• The time evolution of the cellular automaton, starting from an initial configuration c, is the orbit of c under f, i.e., the sequence of configurations

c, f(c), f(f(c)) = f^{2}(c) …, f^{t}(c), …

2.3. The state space or phase graph. Definition 2.4. Let f : X → X be a dynamical system. The state space, phase space, or phase graph is the digraph S(f) with vertex set V_{S(f)} := X and edge set E_{S(f)} := {(x, f(x))|x ∈ X}. The incidence map π is the embedding E_{S(f)} ⊆ X × X. Remark 2.5. A digraph D is the state space S(f) of a dynamical system f : X → X, iff every vertex x ∈ V_{D} has out-degree 1. (Proof?) Example 2.6. The state space of Example 3 is Definition 2.7. A vertex a in a state space S(f) is called

• a garden of Eden point, if a ∉ Im(f),

• a fixed point, if f(a) = a,

• a periodic point of period n ∈ ℕ, if n is the smallest number such that f^{n}(a) = a,

• a transient, if a is not a periodic point.

The set of points {a, f(a), f^{2}(a), …, f^{n}(a), …} is called the orbit of a.

A limit cycle is the orbit of a periodic point a. The length of a limit cycle is the period of the periodic point a. Lemma 2.8. Let f : X → X be a dynamical system. Assume that X is finite.

(1) The following are equivalent (a) f is bijective.

(b) S(f) has no garden of Eden points.

(c) All points are periodic points.

(d) There are no transients in S(f).

(2) Every point in a limit cycle has the same period.

(3) Every connected component of S(f) consists of one limit cycle (or fixed point) and trees attached to the points of the limit cycle as roots.

Proof. ? □

2.4. Real dynamical systems. Theorem 2.9. Let I = [a, b] ⊂ ℝ be a closed interval and f : I → I a continuous function. Then f has a fixed point.

Proof. If f(a) = a or f(b) = b, then we are done. Otherwise f(a) > a and f(b) < b. There the continuous function g(x) = f(x) − x is positive at a and negative at b. By the Intermediate Value Theorem of Analysis, there is c ∈ I such that g(c) = 0, hence f(c) = c. □

Theorem 2.10. Let I = [a, b] ⊂ ℝ be a closed interval and f : I → ℝ a continuous function. If I ⊆ f(I) (expanding function) or f(I) ⊆ I (contracting function), then f has a fixed point.

Proof. The image of I is a closed interval f(I) = [f(c), f(d)] with c, d ∈ I.

Case 1: We have f(c) ≤ a < b ≤ f(d). The continuous function g(x) = f(x) − x satisfies g(c) = f(c) − c ≤ a − c ≤ 0 and g(d) = f(d) − d ≥ b − d ≥ 0, hence there is x_{0} ∈ [c, d] ⊆ I such that g(x_{0}) = 0 or f(x_{0}) = x_{0}.

Case 2: We have a ≤ f(c) < f(d) ≤ b. The continuous function g(x) = f(x) − x satisfies g(a) = f(a) − a ≥ f(c) − a ≥ 0 and g(b) = f(b) − b ≤ f(d) − b ≤ 0, hence there is x_{0} ∈ [c, d] ⊆ I such that g(x_{0}) = 0 or f(x_{0}) = x_{0}. □

Theorem 2.11. (Sarkovskii’s Theorem (1964)): Let f : ℝ → ℝ be a continuous function and let f have a periodic point of order n. Then f has periodic points of any order m for all n > m in the following Sarkovskii order of ℕ: 3 > 5 > 7 … 2 · 3 > 2 · 5 > 2 · 7 … 2^{n} · 3 > 2^{n} · 5 > 2^{n} · 7 … 2^{3} > 2^{2} > 2 > 1.

We only show the following Corollary which is a much weaker version of this Theorem. Folgerung 2.12. Let f : ℝ → ℝ be a continuous function and let f have a periodic point of order 3. Then f has periodic points of any order n.

Proof. Let {a, b, c} be a periodic orbit of f. We may assume that a < b < c. We distinguish two cases: f(a) = b and f(a) = c. First suppose that f(a) = b. Then f(b) = c and f(c) = a. The proof for the case f(a) = c is similar.

Let I_{0} = [a, b] and I_{1} = [b, c]. The Intermediate Value Theorem implies that I_{1} ⊂ f(I_{0}) and I_{0} ∪ I_{1} ⊂ f(I_{1}). Namely, let dεI_{1} = [f(a), f(b)]. Let g(x) = f(x) − d, then the Intermediate Value Theorem implies that g has a zero in I_{0}. That is, I_{1} ⊂ f(I_{0}). Then f has a fixed point in I_{0} ∪ I_{1}, that is, f has a periodic point of period 1.

Now let n > 1 be an integer. If n = 3 we are done. To show that f has a periodic point of period n we will construct a nested sequence

A_{n} ⊂ … ⊂ A_{2} ⊂ A_{1} ⊂ A_{0} = I_{1}

of closed intervals with the following properties:

(1) f(A_{k}) = A_{k−1} for k = 1, ...n − 2;

(2) f^{k}(A_{k}) = I_{1} for k = 1, ..., n − 2;

(3) f^{n−1}(A_{n−1}) = I_{0};

(4) f^{n}(A_{n}) = I_{1}.

First we show that, if such a sequence of intervals exists, then f has a periodic point of period n. Since A_{n} ⊂ I_{1}, Property (4) implies that A_{n} ⊂ f^{n}(A_{n}), so that f^{n} has a fixed point in A_{n}, which just means that f has a periodic point p in A_{n} such that f^{n}(p) = p. It remains to show that n is the period of p.

Then Property (2) of the sequence implies that f^{i}(p) ∈ I_{1} = [b, c] for all i = 0, …, n − 2 (with the convention that f^{0}(x) = x), and f^{n−1}(p) ∈ I_{0} = [a, b]. First we show that p is not equal to either b or c. Suppose that p = c. Then f(p) = a ∉ I_{1}. The conditions on the sequence imply that f^{n−1}(p) is the only iterate of p that is not in I_{1}, hence n = 2. But this contradicts the fact that the period of c is 3. So p ≠ c. Now suppose that p = b. Again, the only iterate of p not in I_{1} is the (n − 1)st. Since f^{2}(p) = a ∉ I_{1}, this implies that n = 3. But this contradicts our assumption that n ≠ 3.

Now observe that f^{n−1}(p) ∈ I_{0} = [a, b], which is disjoint from the interval (b, c). This implies that f^{n−1}(p) ≠ p, so that p cannot have period n−1. If the period is less than n − 1, then Property (2) implies that the orbit of p is entirely contained in (b, c), but this contradicts Property (3). The only other possibility is that p has period n.

It remains to show that the above sequence of intervals exists. Let A_{0} = I_{1}, as required. Since A_{0} ⊂ f(A_{0}), we can find an interval A_{1} ⊂ A_{0} such that f(Al) = A_{0}. Again, since A_{1} ⊂ A_{0}, we obtain that A_{1} ⊂ f(A_{1}). As before, we find A_{2} ⊂ A_{1} such that f(A_{2}) = A_{1}. We continue in this manner to define A_{i}, i = 0, ...n − 2. To define A_{n−1}, note that

f^{n−1}(A_{n−2}) = f(f^{n−2}(A_{n−2})) = f(I_{1}).

Since I_{0} ⊂ f(I_{1}), we know that I_{0} ⊂ f^{n−1}(A_{n−2}). Hence there is A_{n−1} ⊂ A_{n−2} such that f(A_{n−1}) = I_{0}. Finally,

f^{n}(A_{n−1}) = f(f^{n−1}(A_{n−1})) = f(I_{0}),

and I_{1} ⊂ f(I_{0}). Thus, as before, there is A_{n} ⊂ A_{n−1} such that f(A_{n}) = I_{1}, as required. This completes the proof of the theorem. □

2.5. The functional graph. Definition 2.13. Let f : X → X be a finite dynamical system. Then {id, f, f^{2}, …, f^{m}, …} forms a monoid under composition as multiplication. Since there are only finitely many maps from X to X, there are least numbers r and n, such that f^{n+i} = f^{n−r+i} for all i ≥ 1. The map f defines a graph with vertices id, f, f^{2}, …, f^{n} and edges (f^{i}, f^{i+1}) for all i ≥ 0, called the functional graph of f. Bemerkung 2.14. The functional graph of f is the state graph of the finite dynamical system

{id, f, f^{2}, …, f^{n}} ∋ f^{i} ↦ f^{i+1} ∈ {id, f, f^{2}, …, f^{n}}.

The graph of a (finitely generated) monoid. Properties of the functional graph (connected - one garden of eden point)

2.6.

3. Polynomial systems

The operations performed by network elements (l)-(3) on this class of signals constitute the linear operations of delay, mod-p addition, and mod-p muhiplication by a constant scale factor, over the modular field of integers, J_{p} = (0, 1, 2, …, p − 1).