Dynamics and Decidability
in Brin’s Group 2V

Jim Belk
Bard College

Joint with Collin Bleak
and Francesco Matucci

Definition of 2V

Matt Brin introduced the group 2V in 2004.

Properties of 2V

2V acts by homeomorphisms on the Cantor square.

Properties of 2V

2V acts by homeomorphisms on the Cantor square.

Theorem (Brin 2005)
2V is finitely presented and simple.

Brin’s presentation has 8 generators and 70 relations.

Properties of 2V

2V acts by homeomorphisms on the Cantor square.

Theorem (Brin 2005)
2V is finitely presented and simple.

Brin’s presentation has 8 generators and 70 relations.

Theorem (Kochloukova, Martínez-Pérez, Nucinkis 2010)
2V has type (Subscript[F, ∞]).

Open Question
Does 2V act properly by isometries on a CAT(0) space?

For Today

Theorem (B., Bleak)
There is no algorithm to decide whether a given element of 2V has finite order.

This is because 2V contains Turing machines, together with the following theorem:

Theorem (Kari, Ollinger - 2008)
There is no algorithm to decide whether a given complete, reversible Turing machine is uniformly periodic.

Theorem (B., Bleak)
There is no algorithm to decide whether a given collection of aynchronous automata generates a finite automata group.

The Torsion Problem

Torsion problem for a group:
Given a word w, does w represent an element of finite order in G?

Theorem (Baumslag, Boone, Neumann - 1959)
There exists a finitely presented group with unsolvable torsion problem.

Theorem (Arzhantseva, Lafont, Minasyan - 2012)
There exists a finitely presented group with solvable word problem and unsolvable torsion problem.

It seems that 2V is the first concrete example of such a group.

Dynamics

Dynamics in V

Dynamics of elements of V are well-understood (investigated by Salazar-Díaz and Belk & Matucci).

Dynamics in 2V

Brin observed that 2V contains the baker’s map.

This map is a classic example chaotic dynamics.

Action of the Baker’s Map

Brin observed that 2V contains the baker’s map.

Action of the Baker’s Map

Brin observed that 2V contains the baker’s map.

Action of the Baker’s Map

Brin observed that 2V contains the baker’s map.

Action of the Baker’s Map

Brin observed that 2V contains the baker’s map.

Action of the Baker’s Map

Digits move from the x coordinate to the y coordinate.

( 1 0 0 1 1 ⋯ , 0 0 1 0 0 1 ⋯ )

( 0 0 1 1 ⋯ , 1 0 0 1 0 0 1 ⋯ )

( 0 1 1 ⋯ , 0 1 0 0 1 0 0 1 ⋯ )

The orbit has sensitive dependence on the x coordinate.

Action of the Baker’s Map

The map looks simpler if we combine the sequences together:

( 1 1 0 0 0 ⋯ , 0 1 0 0 1 1 ⋯ )

becomes

⋯ 0 0 0 1 1 0 1 0 0 1 1 ⋯

Action of the Baker’s Map

The map looks simpler if we combine the sequences together:

( 1 1 0 0 0 ⋯ , 0 1 0 0 1 1 ⋯ )

becomes

⋯ 0 0 0 1 1 0 1 0 0 1 1 ⋯

Now the baker’s map acts as the right shift on (({0,1})^Z).

Aside: Topological Conjugacy

A dynamical system is a map from a space to itself:

Two dynamical systems are topologically conjugate if there exists a homeomorphism Φ making the following diagram commute:

Aside: Topological Conjugacy

Topologically conjugate dyamical systems are “the same”.

For example, the baker’s map is topologically conjugate to the full shift on two symbols.

Dynamics in 2V

Question
What kinds of dynamical systems are present in 2V ?

That is, given a dynamical system

can we find a topologically conjugate element of 2V ?

Yes for the full shift on (({0,1})^Z).

More Shifts

Full Shifts

What about the full shift on three symbols?

Is this present in 2V ?

Full Shifts

What about the full shift on three symbols?

Is this present in 2V ?

Yes.  Let A = 00, B = 01, and C = 1.

Full Shifts

A = 00        B = 01        C = 1

Full Shifts

Theorem
For every n, the full shift on n symbols is present in 2V.

This requires a choice of a complete prefix code on n symbols.

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

This subshift is present in 2V:

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

This subshift is present in 2V:

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

This subshift is present in 2V:

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

This subshift is present in 2V:

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

This subshift is present in 2V:

Subshifts

A subshift is any closed invariant subset of a full shift

Example.  All sequences in (({A,B,C})^Z) that do not contain the subsequence BC.

A subshift has finite type if it is obtained by forbidding finitely many subsequences.

Theorem (B., Matucci)
Every subshift of finite type can be found in 2V.

Hyperbolic Elements

An element ƒ ∈ 2V is stretching if (Subscript[ƒ, x]) > 1 and (Subscript[ƒ, y]) < 1 everywhere.

ƒ is hyperbolic if (ƒ^n) is stretching for some n.

Theorem (B., Matucci)
Every hyperbolic element of 2V is topologically conjugate to a subshift of finite type.

The proof involves a theory of Markov partitions for hyperbolic elements of 2V.

On Conjugacy

Open Problem
Does 2V have a solvable conjugacy problem?

It would be interesting to have a solution just for hyperbolic elements.

Major Open Problem
Does there exist an algorithm to determine whether two subshifts of finite type are topologically conjugate?

Note that conjugacy in 2V implies topological conjugacy, but not vice-versa.

Turing Machines

Turing Machines

A Turing machine consists of:
      1.	A finite set Q of states.
      2.	A finite tape alphabet A.
      3.	A transition rule for each state.

A tape is any function Z -> A.

The transition rule says what to do with the tape (move or read/write).

Transition Rules

Each state has a transition rule.  There are two types:

Move Rule
      1.  Move in a certain direction (left or right).
      2.  Go to a certain state.

Read/Write Rule
      1.  Read the current letter.
      2.  Write a letter, depending on what was read.
      3.  Go to a certain state, depending on what was read.

Note:  We will assume that Turing machines are deterministic,
i.e. each state has only one transition rule.

Example Turing Machine

Example Turing Machine

Notes:
    1.  This Turing machine is complete (it never halts).

Example Turing Machine

Notes:
    1.  This Turing machine is complete (it never halts).
    2.  This Turing machine is reversible (it can be run backwards).

Dynamics of Turing Machines

A configuration of a Turing machine is a (state, tape) pair.

The configuration space is the space Q × (A^Z) of all configurations.

Fact
A complete, reversible Turing machine defines a homeomorphism on its configuration space.

The study of Turing machines as dynamical systems was initiated by Kůrka (1997).

Turing Machines in 2V

Theorem (B., Bleak)
Every complete, reversible Turing machine is topologically conjugate to an element of 2V.

Turing Machines in 2V

Theorem (B., Bleak)
Every complete, reversible Turing machine is (computably) topologically conjugate to an element of 2V.

A Turing machine is uniformly periodic if the corresponding homeomorphism has finite order.

Theorem (Kari, Ollinger 2008)
There is no algorithm that decides whether a given complete, reversible Turing machine is uniformly periodic.

Therefore, there is no algorithm that decides whether a given element of 2V has finite order.

Proving the Theorem

Theorem (B., Bleak)
Every complete, reversible Turing machine is (computably) topologically conjugate to an element of 2V.

Proving the Theorem

Theorem (B., Bleak)
Every complete, reversible Turing machine is (computably) topologically conjugate to an element of 2V.

Given:  A complete, reversible Turing machine T.

Construct:  A homeomorphism Φ and an ƒ ∈ 2V so that:

Basic Idea

It is easy to encode the tape as a point in the Cantor square.

( 0 0 0 1 0 0 0 0 1 ⋯ , 0 0 1 1 0 1 0 0 ⋯ )

Here A -> 00, B -> 01, and C -> 1.

Basic Idea

It is easy to encode the tape as a point in the Cantor square.

We already know how to shift the tape left and right.

But how can we encode the states?

The Homeomorphism Φ

Choose a complete prefix code for the states:

We will store the state at the beginning of the x-coordinate:

This defines the homeomorphism

Φ : (configuration space) ⟶ (square Cantor set)

The Homeomorphism Φ

We have now defined the homeomorphism Φ.

Let  ƒ  =  (Φ^(-1))∘ T ∘ Φ.  We must show that  ƒ ∈ 2V.

Geometry of the Encoding

Each configuration corresponds to a point in the square Cantor set.

Geometry of the Encoding

States correspond to vertical rectangles.

Transitions map between these rectangles.

Geometry of the Encoding

Within each state, the current letter corresponds to a horizontal subrectangle.

Geometry of the Encoding

The first letter on the left corresponds to a vertical subrectangle.

A Right Move

A Right Move

A Right Move

A Left Move

A Read/Write

An Example

Consequences

Consequences

Theorem
The group 2V has unsolvable torsion problem.

Define Ω : N -> N by

Ω ( n) = max{ | ƒ |  :  ƒ ∈ 2V has finite order and length ≤ n}

Corollary
The function Ω ( n) grows more quickly than any computable function.

Corollary
There exists an element  ƒ ∈ 2V of infinite order such that the statement “ƒ has infinite order” is not provable in ZFC.

Other Groups

Observation
Let G be a f.g. group.  If G has solvable torsion problem, then so does any f.g. subgroup of G.

Corollary
Any f.g. group that contains 2V has unsolvable torsion problem

In particular nV  has unsolvable torsion problem for all n ≥ 2.

Note:  This provides another proof that 2V does not embed into V.

Consequences for Conjugacy

Open Question
Is the conjugacy problem in 2V solvable?

In F, T and V, the solution to the conjugacy problem also reveals whether an element has finite order.  The solution in 2V would have to be very different.

By the way, it’s easy in 2V to enumerate the conjugacy classes of finite-order elements.

Theorem
If the conjugacy problem is solvable in 2V, it is not possible to computably enumerate the conjugacy classes of infinite-order elements.

Consequences for Dynamics

It’s not hard to modify the construction to allow halting.

Consequences for Dynamics

It’s not hard to modify the construction to allow halting.

Consequences for Dynamics

It’s not hard to modify the construction to allow halting.

Consequences for Dynamics

It’s not hard to modify the construction to allow halting.

Theorem (B., Bleak)
Given an element of 2V and dyadic points p and q, it is undecidable whether the orbit of p converges to q.

Related Questions

Open Question
Does every element of 2V have at least one periodic point?

No for complete Turing machines (Blondel, Cassaigne, Nichitiu 2002), but unknown for complete, reversible Turing machines.

Open Question
Is it possible to compute the (digits of the) entropy of an
element of 2V ?

Yes for Turing machines (Jeandel 2013).

Consequences for Automata Groups

An automata group (e.g. Grigorchuk’s group) is a group of tree automorphisms described by finite-state automata.

Consequences for Automata Groups

By allowing asynchronous automata, Thompson’s groups F, T, and V can also be described as automata groups.

(See Grigorchuk, Nekrashevych, Sushchanskii,
            “Automata, Dynamical Systems, and Groups”.)

The Finiteness Question

Question (Grigorchuk, Nekrashevich, Sushchanskii - 2000)
Is it possible to decide whether a given set of automata generate a finite automata group?

•  Bondarenko, Bondarenko, Sidki, and Zapata (2010): Yes for groups generated by a single “bounded” automaton.

•  Akhavi, Klimann, Lombardy, Mairesse, and Picantin (2011) give several partial results.

•  Klinman (2012): Yes for two-state automata, and yes for invertible-reversible automata over a two-letter alphabet.

•  Gillibert (2013): No in the case of automata semigroups.

Consequences for Automata Groups

Theorem (B., Bleak)
The group 2V can be realized as an (asynchronous) automata group.

Theorem (B., Bleak)
There is no algorithm to decide whether a given automaton defines a transformation of finite order.
In particular, there is no algorithm to decide whether a given set of automata generates a finite automata group.

This settles the finiteness question in the asychronous case.

Sketch of Proof

An Asynchronous Automaton

Elements of 2V as Automata

Given a point in the square Cantor set, we can combine the two coordinates together:

( 0 1 0 1 0 1 0 1 0 ⋯ , 1 1 1 0 0 0 1 1 1 ⋯ )

01, 11, 01, 10, 00, 10, 01, 11, 01, ⋯

This gives a homeomorphism:

Ψ : (square Cantor set) ⟶ {00, 01, 10, ((11})^∞).

Elements of 2V as Automata

Using this homeomorphism, any ƒ ∈ 2V induces a map on
{00, 01, 10, ((11})^∞).

We must construct an automaton for α.

Elements of 2V as Automata

Elements of 2V act as prefix replacements.

Elements of 2V as Automata

Elements of 2V act as prefix replacements.

So the automaton has two tasks:

     1.  Input digits until we recognize the prefix.

     2.  Ouput the new prefix, followed by the remaining digits.

Elements of 2V as Automata

Recognizing the prefix is easy.  There’s a tree of possibilities.

Elements of 2V as Automata

Outputting the new prefix requires a trick.

Elements of 2V as Automata

Outputting the new prefix requires a trick.

The Trick
Automata can remember things.

Here’s a synchronous automaton that adds the letter “A” to the beginning of a string:

It’s always one letter behind, but it “remembers” this letter using the state.

An Automaton that Remembers

This automaton adds a “0” to the beginning of the x-coordinate.

Adding the New Prefix

Using this trick, we can add a prefix to x and a prefix to y.

Adding the New Prefix

Using this trick, we can add a prefix to x and a prefix to y.

We must remember a queue of digits for each coordinate.

Putting it Together

We need one of these prefix-adding automata for each part.

The End