Can every bijection f: $\mathbb Z \to \mathbb Z$ be written as the composition of at most two (other) such bijections with order 2? I came across a problem stating any element $\sigma$ in $S(\mathbb Z )$, the set of bijections from $\mathbb Z$ to itself, can be written as $\sigma = \tau_1 \tau_2$ with $\tau_i \in S(\mathbb Z)$ having order at most two, i.e. $\tau_i(\tau_i(x))=x$. Is this true (I assume the book is correct!) and if so what’s the idea of a proof?
For example I can’t even find such $\tau_i$ for the bijection defined by the cycle $( 1 2 3 4 5 6)$. An example given in the book was $\sigma = x+1 = 1-(-x) = \tau_1 \tau_2$ where $\tau_1 = 1-x, \tau_2 = -x$ which indeed have order 2.
 A: I will first treat the finite case, as it is indicative of the strategy in the $S(\mathbb Z)$ case.
For any element $\sigma\in S_n$, it is known that $\sigma$ is a product of disjoint cyclic permutations. That is, $\sigma=(k_1\cdots k_r)(\ell_1\cdots\ell_m)\cdots$ where $\{k_1,\dots,k_r\}$ and $\{\ell_1,\dots,\ell_m\}$ are disjoint, so on. The idea is, the set $\{1,\dots,n\}$ can be decomposed into sets of the form $\{\sigma^i(k)\}_{i\in\mathbb Z}$. Then, it is clear that $\sigma$ acts cyclically on such sets.
Each cycle $(k_1\cdots k_r)$ decomposes as the product of the two permutations $k_i\mapsto k_{-i}$ and $k_i\mapsto k_{1-i}$, as described in the example in the textbook. Now, $\sigma$ decomposes as the product:
$$\sigma=((k_i\mapsto k_{1-i})(\ell_i\mapsto\ell_{1-i})\cdots)\circ ((k_1\mapsto k_{-i})(\ell_i\mapsto \ell_{-i})\cdots),$$
where both these compositions have order $2$.
Example: Say $\sigma=\begin{pmatrix}1&2&3&4&5\\2&3&1&5&4\end{pmatrix}$. Then $\sigma$ decomposes as $(123)\circ(45)$. The textbook tells us how to decompose $(123)$ and $(45)$ as a product of two order $2$ permutations: $(123)=(13)\circ(12)$ and $(45)=(45)\circ id$. Thus, $\sigma=(13)(45)\circ(12)id$ is the desired decomposition.

For $S(\mathbb Z)$: Now, the set $S(\mathbb Z)$ decomposes into sets of the form $A_k:=\{\sigma^i(k)\}_{i\in\mathbb Z}$. Now, there are two possibilities: $A_k$ is finite, or $A_k$ is infinite. If $A_k$ is finite, then the construction in the textbook tells us the action of $\sigma$ on $A_k$ decomposes into a product of two order $2$ permutations supported on $A_k$. Otherwise, if $A_k$ is infinite, the same formula still works! Consider the two permutations $\sigma^i(k)\mapsto\sigma^{-i}(k)$ and $\sigma^i(k)\mapsto\sigma^{1-i}(k)$.
More formally, let $\sigma\in S(\mathbb Z)$ be an arbitrary bijection $\mathbb Z\to\mathbb Z$. Then, for $a,b\in\mathbb Z$, defining $a\sim b$ iff there exists an integer $i$ such that $a=\sigma^i(b)$ defines an equivalence relation on $\mathbb Z$. Let $A$ be the set of representatives for $\mathbb Z/\sim$. Then, define the two permutations:
$$\tau_1\colon\sigma^i(k)\mapsto\sigma^{-i}(k)$$
and
$$\tau_2\colon\sigma^i(k)\mapsto\sigma^{1-i}(k),$$
where $k\in A$. Once can check these functions are well-defined, they have order $2$, and that moreover $\sigma=\tau_2\circ\tau_1$.
