By the 2-shift map I mean the map $T:\{0,1\}^\mathbb{Z}\to \{0,1\}^\mathbb{Z}$ that shifts the sequence leftwise. By a root I mean an homeomorphism $\psi:\{0,1\}^\mathbb{Z}\to\{0,1\}^\mathbb{Z}$ that commutes with $T$ and such that $\psi^2=T$.


I read somewhere that it does not have one, but could not find a proof.



Does the 2-shift map have a root automorphism?
**(05/05/2015)** If $T$ is a permutation of any set $X$ with a (finite) odd number of 2-cycles, then $T$ is not a square in the group of permutations of $X$ (because if $T=U^2$ then $T$ commutes with $U$ --this assumption in the question is thus redundant--, hence $U$ preserves the union $J$ of 2-cycles of $T$ and acts on $J$ so that $U^2$ has no fixed point, hence only with 4-cycles, so if $J$ is finite then its cardinal is a multiple of 4). 


This applies to the 2-sided shift in 2 letters, which has a single orbit of cardinal 2 (this follows the argument in the comment). Hence $T$ is not even a square in the full group of permutations of the Cantor set $\{0,1\}^\mathbf{Z}$.


More generally one can wonder whether we can write $T=U^p$ for any given prime $p$; then the argument works if the union of $p$-cycles has cardinal not divisible by $p$ or equivalently if we do not have $2^{p-1}\neq 1\mod p^2$. This seems to hold for most primes... a computer search shows that the first two primes $p$ such that $2^{p-1}\equiv 1\mod p^2$ are... 1093 and 3511. I looked up Sloane's Encyclopedia about this sequence, who knows it: [Wieferich primes; Sloane's sequence A001220](https://oeis.org/A001220), see also [Wikipedia](http://en.wikipedia.org/wiki/Wieferich_prime); these are the only two known such primes, and there is no other smaller than $10^{17}$ ! Thus shows that $T$ is not a cube, etc, but for these Wieferich primes I do not know what's going on.


**Edit (12/06/2015)**: it is easy to check that if conversely $p$ is a Wieferich prime, then $T$ is a $p$-power in the full group of permutations of $\{0,1\}^\mathbf{Z}$. Indeed it amounts to checking that for every multiple $n$ of $p$ (including $\infty$), the number of $n$-cycles is divisible by $p$ (allowing $\infty$). This is trivial for $\infty$ (infinitely many $\infty$-cycles). Otherwise this is done by induction on $n/p$. Write $n=p^km$ with $m$ coprime to $p$. The number of $n$-periodic elements is $2^n$; those $m$-periodic is $s=2^m$. So the number of $n$-periodic elements whose period is divisible by $p$ is $2^n-2^m=2^m(2^{m(p^k-1)}-1)$. Write $m(p^k-1)=(p-1)\ell$. Then $2^{m(p^k-1)}-1=2^{\ell (p-1)}-1$ is divisible by $2^{p-1}-1$, which is divisible by $p^2$. So the number of $n$-periodic elements with period divisible by $p$ is divisible by $p^2$. Since by induction the number of $n'$-periodic elements is divisible by $p^2$ for every proper divisor of $n$ divisible by $p$, we deduce that the number of elements of period $n$ is also divisible by $p^2$.


So $T$ really has a 1093rd power in the full group of permutations, and 1093 is the smallest number greater than one with this property! But it's unclear [**now answered negatively below**] if we can find this permutation in the group of self-homeomorphisms, or even in the group of topological group automorphisms of $(\mathbf{Z}/2\mathbf{Z})^\mathbf{Z}$. 




---


**Edit (04/04/2017).** From Mike Boyle I got the answer to the previous question: the 2-sided shift on 2 letters has no $p$-root for any $p$. More generally, 



> 
> the 2-sided shift $T\_k$ on $k$ letters has a $n$-root in the group of self-homeomorphisms of $\{0,\dots,k-1\}^\mathbf{Z}$ if and only if $k$ is an $n$-power.
> 
> 
> 


Proof: the obvious part is that if $k=\ell^n$ is an $n$-power, this can be viewed as the $n$-th power of the 2-sided shift on $\ell$ letters. 


Conversely, we first use that $T\_k$ has topological entropy $h(T\_k)=\log(k)$ (Proposition 8.16 in [these lectures](http://www.maths.manchester.ac.uk/~cwalkden/magic/lecture08.pdf)). If $T\_k=V^n$, then we obtain $h(V)=\log(k)/n=\log(k^{1/n})$ (Exercise 8.4 for topological entropy of powers, same reference).


Then $V$ is clearly isomorphic to an subshift (because for a self-homeomorphism of a totally disconnected compact space, this means that there is a finite clopen partition whose translates separate the points); furthermore this has to be a subshift of finite type, because a subshift of finite type cannot be written as intersection of a properly decreasing sequence of invariants subsets of a 2-sided shift. Furthermore it has to be irreducible, because periodic points are dense. It is also primitive, because the shift itself has an element $w$ such that for every $k$, the $k\mathbf{Z}$-translates of $w$ form a dense sequence (this proves that the shift has no continuous finite equivariant quotient other than a singleton, and hence its root as well). 


Now for an irreducible subshift of finite type, the topological entropy is $\log(\lambda)$, where $\lambda$ is the largest modulus of eigenvalues of the corresponding $\{0,1\}$-valued matrix (and actually $\lambda$ itself is eigenvalue). In the primitive case, it is the unique eigenvalue of such modulus. In particular, it is an algebraic number that is (strictly) greater in modulus than all its conjugates. This is not the case of $k^{1/n}$ if $k$ is not an $n$-power, so we have a contradiction.


In particular, the 2-sided shift on 2 letters is a 1093-power in the group of permutations of $\{0,1\}^{\mathbf{Z}}$, but not in the group of self-homeomorphisms of $\{0,1\}^{\mathbf{Z}}$.


