A Category of Topological Spaces Encoding Acyclic Set-Theoretic Dynamics (and other Collatz fun) Ken Monks University of Scranton

1 History: How I got interested

• 1991: Faculty Student Research Program (FSRP) formed at Scranton.

2 Undergraduate Papers

• C. Farruggia, M. Lawrence, B. Waterhouse; The Elimination of a Family of Periodic Parity Vectors in the 3x + 1 Problem, Pi Mu Epsilon Journal, 10 (4), Spring (1996), 275-280

• Fusaro, Marc, A Visual Representation of Sequence Space, Pi Mu Epsilon Journal, Pi Mu Epsilon Journal 10 (6), Spring 1997, 466-481

• Joseph, J.; A Chaotic Extension of the 3x + 1 Function to ℤ_{2} [i], Fibonacci Quarterly, 36.4 (Aug 1998), 309-316

• Fraboni, M.;Conjugacy and the 3x+1 Conjecture, submitted

3 Cast of Characters

• ℤ_{2} -the ring of 2-adic integers

• ℚ_{odd} -the “oddrats”; \{ \frac{a}{b} : a, b ∈ ℤ, b odd \}

• T -the Collatz function

T (x) = \{ \begin{matrix}\frac{x}{2} & if x is even \\ \frac{3x+1}{2} & if x is odd \end{matrix} – T : ℤ_{2} → ℤ_{2}. Consider T |ℚ_{odd}, T |ℤ, and

T |ℤ^{+} when needed.

• σ -the shift map on ℤ_{2}, σ (s_{0}s_{1}s_{2} …_{(2)}) = s_{1}s_{2}s_{3} …_{(2)}

• Q - the parity vector function

4 J. Joseph

• In search of the “Collatz fractal”!

• Extension to ℤ_{2} [i]

• Even and odd correspond to equivalence classes in ℤ/2ℤ.

• ℤ_{2} [i] /2ℤ_{2} [i] = {[0] , [1] , [i] , [1 + i]} Definition: Let

T̃ : ℤ_{2} [i] → ℤ_{2} [i]

by

T̃ (x) = \{ \begin{matrix}\frac{x}{2} & if x ∈ [0] \\ \frac{3x+1}{2} & if x ∈ [1] \\ \frac{3x+i}{2} & if x ∈ [i] \\ \frac{3x+1+i}{2} & if x ∈ [1 + i] \end{matrix}

4.1 A Nontrivial Matter?

Theorem (J. Joseph)

(a) T̃|ℤ_{2} = T. (i.e. it is an extension)

(b) T̃ is not conjugate to T × T via a ℤ_{2}-module isomorphism. (i.e. it is nontrivial)

(c) T̃ is topologically conjugate to T × T.

(d) Q̃ is a homeomorphism.

(e) T̃ : ℤ_{2} [i] → ℤ_{2} [i] is chaotic.

4.2 Some Empirical Results on T̃|ℤ [i]

(An Extended Finite Cycles Conjecture?)

Period # of T |ℤ cycles # of T̃|ℤ [i] cycles
1  2  4
2  1  3
3  1  9
4  0  0
5  0  2
6  0  0
7  0  0
8  0  10
11  1  5^{∗}
19  0  24^{∗}
46  0  2^{∗}
103  0  2^{∗}

∗Empirical search only.

5 The “Collatz Fractal”

• Wanted: a continuous (preferably entire) function that interpolates T |ℚ_{odd} or T̃|ℚ_{odd} [i]

• No way!

• M. Chamberland:

f (x) = \frac{x}{2} cos^{2} (\frac{π}{2}x) + \frac{3x + 1}{2} sin^{2} (\frac{π}{2}x)

is entire and extends T |ℤ.

5.1 An analytic extension of T̃|ℤ[i]

Definition: Let {a_{0}, a_{1}, a_{2}, … } = ℤ [i] be the enumeration of the points of ℤ [i] as shown:

Theorem (Joseph, Monks) Let F : ℂ → ℂ by

f_{0} (z) = 0, and for n > 0
f_{n} (z) = π_{n} (z) (\frac{z}{a_{n}})^{m_{n}} (T̃^{n} (a_{n}) − n−1 ; ∑ ; k=0 f_{k} (a_{n})) ,

π_{n} (z) = n ; ∏ ; k=1 \frac{(z − a_{k})}{(a_{n} − a_{k})},

p_{n} = ⌊\frac{\sqrt{n} + 1}{2}⌋ ,

K_{n} = |T̃^{n} (a_{n}) − n−1 ; ∑ ; k=0 f_{k} (a_{n})| ,
m_{n} = ⌈log_{2} ((1 + 2\sqrt{2})^{n−1} p_{n}^{n−1}) K_{n}⌉
F (z) = ∞ ; ∑ ; n=0 f_{n} (z) .

F is an entire function which extends T̃|ℤ[i].

6 M. Fraboni

6.1 Approach: attack via conjugacies

• Two extreme cases:

Q - hard, σ - easy  1_{ℤ_{2}} - easy, T - hard
\begin{matrix}ℤ_{2} & ⟶^{T} & ℤ_{2} \\ Q ↓ & & ↓ Q \\ ℤ_{2} & ⟶_{σ} & ℤ_{2} \end{matrix} vs. \begin{matrix}ℤ_{2} & ⟶^{T} & ℤ_{2} \\ 1_{ℤ_{2}} ↓ & & ↓ 1_{ℤ_{2}} \\ ℤ_{2} & ⟶_{T} & ℤ_{2} \end{matrix}

• Q: Can we find a conjugacy h and a map s so

that

ℤ_{2} ⟶^{T} ℤ_{2}
h ↓  ↓ h
ℤ_{2} ⟶_{s} ℤ_{2}

commutes and both h and s are “not too hard”.

6.2 Nice Conjugates and Linear Conjugacies

Definition:Let a, b, c, d ∈ ℤ_{2}, b even, c ≡ d mod 2, and f_{a,b,c,d} : ℤ_{2} → ℤ_{2} by

f_{a,b,c,d} (x) = \{ \begin{matrix}\frac{ax+b}{2} & if x is even \\ \frac{cx+d}{2} & if x is odd \end{matrix}

Definition: Let F = {f_{a,b,c,d} : a, c, d are odd and b is even} .

Theorem (Fraboni)

(a) f_{a,b,c,d} is conjugate to T if and only if f ∈ F.

(b) Every f ∈ F, is topologically conjugate to T.

(c) s is conjugate to T via a linear conjugacy h (x) = px + q if and only if s = f_{1,q,3,p−q}, with p odd and q even, or s = f_{3,p−q,1,q} with p and q both odd.

7 Starting from Scratch

Monks, K.; A Category of Topological Spaces Encoding Acyclic Set Theoretic Dynamics, in preparation

• Q: What are the categories of dynamical systems we are interested in? What are their properties?

• Q: What invariants can we find for such dynamical systems?

• Observation: The set theoretic dynamics of the Collatz map is independent of the choice of metric or topology on ℤ_{2} ( or ℚ_{odd,} or ℤ or ℤ^{+}).

• Q: In such a situation, is there a “canonical” topology that is associated with the dynamics? To what extent is it an invariant?

7.1 More members of our cast

Definition: A set theoretic discrete dynamical system is a pair, Dyn (X, f) , where X is a set and f : X → X is a map.

The dynamical systems Dyn (X, f) , Dyn (Y, g) are said to be semi-conjugate if there exists a map h : X → Y such that

\begin{matrix}X & ⟶^{f} & X \\ h ↓ & & ↓ h \\ Y & ⟶_{g} & Y \end{matrix}

commutes.

In this situation h is called a semiconjugacy.

If h is bijective, then h is a conjugacy.

If X, Y are topological spaces and h is a homeomorphism, then h is a topological conjugacy.

Definition: A dynamical system is acyclic if its only cyclic points are fixed points.

• The f–orbit of x is

O_{f} (x) = {x, f (x) , f^{2} (x) , … }

7.2 Categories of Dynamical Systems

• SetDyn

– objects: set theoretic discrete dynamical systems

– morphisms: semiconjugacies

• ADyn

– objects: acyclic dynamical systems

– a full subcategory of SetDyn 7.2.1 Properties of SetDyn and ADyn

Theorem: In both SetDyn and ADyn :

(a) Conjugacies are isomorphisms.

(b) Semiconjugacies map cyclic points of order k to cyclic points of order d for some d dividing k.

(c) Semiconjugacies map orbits to orbits, i.e. if h is a semiconjugacy from Dyn (X, f) to Dyn (Y, g) and x ∈ X then h (O_{f} (x)) = O_{g} (h (x)) .

(d) Every monic morphism is injective.

(e) Every epic morphism is surjective.

(f) There exist injections which are not sections.

(g) There exist surjections which are not retractions.

(h) Every bimorphism is an isomorphism.

(i) Dyn (∅, ∅) is an initial object.

(j) Dyn ({∅} , id_{{∅}}) is a terminal object

(k) Both categories have arbitrary products.

7.3 Induced Topologies

Definition: Let X be a set and f : X → X a function. Define

τ_{f} = { A ⊆ X : f (A) ⊆ A } .

τ_{f} is a topology on X called the topology induced by f.

We say Top (X, τ) is an induced topological space if τ = τ_{f} for some map f.

If f is acyclic we say Top (X, τ_{f} ) is an acyclic topological space.

Theorem: The set of orbits forms a basis for the topology τ_{f}.

Corollary: O_{f} (x) = ⋂ ; \begin{matrix}x∈U \\ U∈τ_{f} \end{matrix} U.

7.3.1 What kind of spaces are these? Theorem: An induced topological space Top (X, τ_{f} ) is Hausdorff if and only if f = id_{X}.

7.3.2 Nice properties of the acyclic topologies

Theorem: Let f : X → X be acyclic and g : X → X. If τ_{f} = τ_{g} then f = g.

• Given an acyclic topology τ, we can recover the function f that induced it.

7.4 Categories of Induced Topological Spaces

• IndTop

– objects: induced topological spaces – morphisms: continuous maps

• ATop

– objects: acyclic topological spaces – a full subcategory of IndTop

7.5 Relationships between the categories

Theorem: Semiconjugacies are continuous with respect to the induced topologies.

(i.e. there is a functor κ (Dyn (X, f)) = Top (X, τ_{f} ) and κ (h) = h)

Theorem:

(a) If dynamical systems are conjugate then their induced topological spaces are homeomorphic.

(b) Two acyclic dynamical systems are conjugate if and only if their induced topological spaces are homeomorphic.

(c) In ADyn, h is a conjugacy if and only if it is a homeomorphism with respect to the induced topologies.

7.6 Applications to the Collatz Problem

• Recall, the Collatz graph of Dyn (X, f) is – a directed graph (V_{f}, E_{f} )

– V_{f} = X is the set of vertices

– E_{f} = {(x, f (x)) : x ∈ X} is the set of directed edges

• Known: The Collatz conjecture is true if and only if the Collatz graphs of T |ℤ^{+} is weakly connected.

Theorem: Let Dyn (X, f) be a dynamical system. The Collatz graph of f is weakly connected if and only if the topological space Top (X, τ_{f} ) is connected.

Corollary: The Collatz Conjecture is true if and only if Top (ℤ^{+}, τ_{T |ℤ^{+}}) is a connected topological space.

Corollary: If h is a semiconjugacy from Dyn (X, f) onto Dyn (ℤ^{+}, T |ℤ^{+}) and Top (X, τ_{f} ) is connected, then the Collatz conjecture is true.

Corollary: If h is a semiconjugacy from Dyn (ℤ^{+}, T |ℤ^{+}) onto Dyn (X, f) and Top (X, τ_{f} ) is not connected, then the Collatz conjecture is false

• Proof: Semiconjugacies are continuous!

These slides, papers, and fractal images are available at:

http://academic.uofs.edu/faculty/monks/talks.html