Tits alternative(Tits, 1972)

• $H$ is a solvable group if there exists a normal series $1=H_1\triangleleft H_2\triangleleft\cdots\triangleleft H_n=H$ such that $H_i/H_{i-1}$ is abelian.
• "Free" means "not related to each other", analogue to "linear independent."

Banach-Tarski paradox

Can we divide a unit sphere into a finite number of pieces and then reconstruct these pieces, using only translations, into two identical spheres?

Strategy for constructing examples for Banach-Tarski paradox

• Let's denote the unit sphere as $\mathcal{S}$. We define $\text{Aut}(\mathcal{S})$ as the group of automorphisms of $\mathcal{S}$.
• For $x,\ y\in\mathcal{S}$, $x\sim y$ if and only if there exists a $g\in\text{Aut}(\mathcal{S})$ such that $g(x)=y$.
• We then find a subgroup $S$ of $\text{Aut}(\mathcal{S})$. The next step is to partition $S$ into finite, disjoint subsets $S=S_1\cup S_2\cup \cdots\cup S_n$ such that possibly $$S = g_1S_1\cup g_2S_2\text{ and }S=g_3S_3\cup g_4S_4$$ where $g_1,\ g_2,\ g_3$, and $g_4\in S$.

$\text{Aut}(\mathcal{S})$ contains a free subgroup of rank two.

$$\langle a,\ b\rangle = \{1\}\cup W(a) \cup W(b)\cup W(a^{-1}) \cup W(b^{-1})$$

Moreover, we have $$\begin{align*} \langle a,\ b\rangle &= aW(a^{-1})\cup W(a)\\\\ &= bW(b^{-1})\cup W(b). \end{align*}$$

von Neumann conjecture

• True:
  • Linear groups
  • Two dimensional Artin groups
• False:
  • Tarski monster groups
  • Burnside groups
  • More

sketch of the proof: Note that $$f^{*}g^{*}\cdots f^{*}:A\to B$$ cannot be an identity.

• case ($w=g^{*}f^{*}\cdots g^{*}$): we consider $fwf^{-1}$.
• case ($w=f^ag^{*}\cdots g^{*}$): for $n\neq a$ and $0$, we consider $f^{n}wf^{-n}$.
• case ($w=g^*f^*\cdots f^a$): for $n\neq a$ and $0$, we consider $f^{n}wf^{-n}$.

Our main result indicates that semigroups generated by rational functions adheres to the Tits alternative.

To comprehend the essence of our proof for the main result, perform the following steps:

• Use a naive height function $h:\mathbb{Q}^\times\to\mathbb{R}_{\geq 0}$.
• Let $f$ and $g$ be rational functions. Define both the dynamical canonical height of $f$ and the general multi-system dynamical canonical height $h_w$, where $w\in \Sigma^*$.
• Given $\alpha\in\mathbb{Q}$, define $X$ as the set of all $h_w(\alpha)$ where $w\in\Sigma^*$.
• Explain the action of $f$ and $g$ on $X$.
• Identify $A$ and $B$, which are disjoint subsets of $X$, and apply the ping-pong lemma.

Write a nonzero rational number $\frac{a}{b}$ in lowest terms. The naive height is $$\begin{align*} h(\alpha) &= \log(\max\{|a|,|b|\})\\ &= \log(\max\{1,|\frac{a}{b}|\})+\sum_{p\text{ prime}}\log(\max\{1,|\frac{a}{b}|_p\}), \end{align*}$$ e.g. $h(\frac{1}{2})=\log(2)$ and $h(\frac{1001}{2000})=\log(2000)$.

A well-known inequality

Let $f$ be a rational function. Let $d$ be the degree of $f$. Then, we have a constant $C$, dependent only on $f$, such that $$|h(f(\alpha))-dh(\alpha)| < C$$

Dynamical Canonical height

$$h_f(\alpha)=\lim_{n\to\infty}\frac{h(f^n(\alpha))}{d^n}$$

Key argument: For $m>n$, $\left|\frac{h(f^m(\alpha))}{d^m} - \frac{h(f^n(\alpha))}{d^n}\right|$
$$\begin{align*} &= \left|\frac{h(f^m(\alpha))}{d^m} - \frac{h(f^{m-1}(\alpha))}{d^{m-1}}+\frac{h(f^{m-1}(\alpha))}{d^{m-1}} - \frac{h(f^{m-2}(\alpha))}{d^{m-2}} + \cdots + \frac{h(f^{n+1}(\alpha))}{d^{n+1}} - \frac{h(f^n(\alpha))}{d^n}\right|\\\\ &\leq \left|\frac{h(f^m(\alpha))}{d^m} - \frac{h(f^{m-1}(\alpha))}{d^{m-1}} \right| + \left|\frac{h(f^{m-1}(\alpha))}{d^{m-1}} - \frac{h(f^{m-2}(\alpha))}{d^{m-2}}\right| + \cdots + \left|\frac{h(f^{n+1}(\alpha))}{d^{n+1}} - \frac{h(f^n(\alpha))}{d^n}\right|\\\\ &< \frac{C}{d^{m}} + \frac{C}{d^{m-1}} + \cdots + \frac{C}{d^{n+1}} = \frac{\frac{C}{d^{m+1}}-\frac{C}{d^{n+1}}}{\frac{1}{d}-1} \end{align*}$$

Multi-system dynamical canonical height

Consider a sequence $$\{f_1(\alpha),\ f_2f_1(\alpha),\ f_3f_2f_1(\alpha),\ \cdots \}$$ where $f_i$ is equal to $f$ or $g$. Let $w_n= f_n\ldots f_2f_1$, and let $w$ be the formal composition $\ldots f_3f_2f_1$ ($w\in\Sigma^*_\infty$). We define $$h_w(\alpha) = \lim_{n\to\infty}\frac{h(w_n(\alpha))}{\deg(w_n)}.$$

Define $X$

Given $\alpha\in\mathbb{Q}\setminus\text{Perp}(f)\cap\text{Prep}(g)$, we define $$X=\{h_w(\alpha)| w\in\Sigma^*_\infty\}.$$

And, we define $$fX = \{h_{wf}(\alpha)| w\in\Sigma^*_\infty\}.$$

Note that $f^nX\subset B\left(\frac{h(f^n(\alpha))}{d^n}, \frac{C}{(\deg(f)-1)\deg(f)^n}\right).$

Define $A$ and $B$

Suppose $h_f(\alpha)\neq h_g(\alpha)$. Then, there exists an integer $n$ such that $f^nX\cap g^nX=\varnothing$. Let $$A = f^nX\text{ and }B=g^nX.$$

Obviously, $f^{nk}:B\to A$ and $g^{nk}:A\to B$ for any positive integer $k$.

Thus, by the ping-pong lemma, we can conclude that $\langle f^n, g^n\rangle$ is a free semigroup of rank $2$.

A Tits alternative for endomorphisms of the projective line

(Bell - Huang - :) - Tucker, upcoming on JEMS)

• We answered a conjecture posed by Cabrera and Makienko. If the measures of maximal entropy (julia set) for $f$ and $g$ are distinct, then there is a $j$ such that $\langle f^j, g^j\rangle$ is a free semigroup on two generators.
• Let $A$ be an abelian variety. Then $\text{End}(A)$ (finite morphisms from $A$ to itself) satisfies tits alternative.

Algorithm:$\langle f,g\rangle$ contains free semigroup

Input: polarized morphisms $f$ and $g$, and an integer $n$

Output: A Boolean indicating whether $f$ and $g$ have a composition relation, or "indeterminable" if the algorithm cannot determine by searching on a binary tree up to level $n$.

Idea of Algorithm

1. For simplicity, we assume $\deg f=\deg g$.
2. Composition has the property of right cancellation, i.e. $$h_1\circ f = h_2\circ f\implies h_1=h_2.$$

   Therefore, to verify a nontrivial composition relation, we can simply assume that the rightmost functions are distinct.

3. If there exists some $\alpha$ such that $$B\left(\frac{h(A(\alpha))}{d^n},\dfrac{C}{(d-1)d^n}\right)\bigcap B\left(\frac{h(B(\alpha))}{d^n},\dfrac{C}{(d-1)d^n}\right)=\varnothing$$ where $C=\max\{C_f, C_g\}$, $A=A_n\circ\cdots\circ A_1$ and $B=B_n\circ\cdots\circ B_1$, then any composition that starts with $A$ won't be equal to one that starts with $B$.

Pseudocode

Q = random()
check_list = [(f,g)] 
while check_list != []:
  a_pair = check_list.pop(0)
  check_list.extend(check(a_pair))
  if length of a_pair[0]>n:
    return "Undecidable"
return "Have no relation"
Q = random()
check_list = [(f,g)] 
while check_list != []:
  a_pair = check_list.pop(0)
  check_list.extend(check(a_pair))
  if length of a_pair[0]>n:
    return "Undecidable"
return "Have no relation"
Q = random()
check_list = [(f,g)] 
while check_list != []:
  a_pair = check_list.pop(0)
  check_list.extend(check(a_pair))
  if length of a_pair[0]>n:
    return "Undecidable"
return "Have no relation"
Q = random()
check_list = [(f,g)] 
while check_list != []:
  a_pair = check_list.pop(0)
  check_list.extend(check(a_pair))
  if length of a_pair[0]>n:
    return "Undecidable"
return "Have no relation"

def check(a_pair):  
  A = a_pair[0]
  B = a_pair[1]
  d = f.degree()
  diff = h(A(Q)/A.degree())-h(B(Q)/B.degree())
  C = max(f.resultant(),g.resultant())
  err = 2C/((d-1)d^n)
  if diff/2 > err:
    return []
  else:
    if A==B:
      return "find a relation A=B"
    else:
      return [(fA,fB),(fA,gB),(gA,fB),(gA,gB)]
def check(a_pair):  
  A = a_pair[0]
  B = a_pair[1]
  d = f.degree()
  diff = h(A(Q)/A.degree())-h(B(Q)/B.degree())
  C = max(f.resultant(),g.resultant())
  err = 2C/((d-1)d^n)
  if diff/2 > err:
    return []
  else:
    if A==B:
      return "find a relation A=B"
    else:
      return [(fA,fB),(fA,gB),(gA,fB),(gA,gB)]
def check(a_pair):  
  A = a_pair[0]
  B = a_pair[1]
  d = f.degree()
  diff = h(A(Q)/A.degree())-h(B(Q)/B.degree())
  C = max(f.resultant(),g.resultant())
  err = 2C/((d-1)d^n)
  if diff/2 > err:
    return []
  else:
    if A==B:
      return "find a relation A=B"
    else:
      return [(fA,fB),(fA,gB),(gA,fB),(gA,gB)]
def check(a_pair):  
  A = a_pair[0]
  B = a_pair[1]
  d = f.degree()
  diff = h(A(Q)/A.degree())-h(B(Q)/B.degree())
  C = max(f.resultant(),g.resultant())
  err = 2C/((d-1)d^n)
  if diff/2 > err:
    return []
  else:
    if A==B:
      return "find a relation A=B"
    else:
      return [(fA,fB),(fA,gB),(gA,fB),(gA,gB)]
def check(a_pair):  
  A = a_pair[0]
  B = a_pair[1]
  d = f.degree()
  diff = h(A(Q)/A.degree())-h(B(Q)/B.degree())
  C = max(f.resultant(),g.resultant())
  err = 2C/((d-1)d^n)
  if diff/2 > err:
    return []
  else:
    if A==B:
      return "find a relation A=B"
    else:
      return [(fA,fB),(fA,gB),(gA,fB),(gA,gB)]

demo

• Monomial $x^n$: The Julia set is the unit circle centered at the origin (0,0).
• Chebyshev polynomial: The Julia set is the closed interval $[-2,2]$
• Lattès map: The Julia set is the entire space.

The only remaining case is when we have a semigroup generated by monomials like $$\langle \zeta_1x^{n_1},\zeta_2x^{n_2},\ldots,\zeta_mx^{n_m}\rangle.$$

If $\zeta$ is a primitive fifth root of unity, then the semigroup generated by $f=x^2$ and $g=\zeta x^3$ has the following nine relations, none of which is generated by the other:

A finitely generated semigroup $G=\Sigma^*/\mathcal{R}$ with the following properties:

1. Let equivalent classes $[w_1]$ and $[w_2]$ belong to $G$. If $[w_1]=[w_2]$, then $|w_1|_s = |w_2|_s$ (counting the number of characters to be $s$) for all $s\in\Sigma$ (If two composition are the same, then they use the same number of $f$ and $g$.)
2. There exists a positive integer $N$ such that $\#\mathcal{U}_I/\mathcal{R}\leq N$ for all indices $I$ (Number of possible composition result is bounded.)
3. The semigroup $G$ has one-side cancellation property.

:) - Tsai (2023)