3
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ $\psi$ would have to map the $2$-periodic point (wrt $T$) $x=\ldots 0101\ldots$ back to the same orbit, that is, $\psi(x)=x$ or $\psi(x)=Tx$, and neither choice works ($\psi^2(x)=x$ both times). $\endgroup$ May 1, 2015 at 0:33
  • $\begingroup$ I believe that 2-shift maps are commonly called "Bernoulli shifts" (or maybe that term is reserved for the one-sided shift space; the two-sided one would be the "Baker's map") $\endgroup$
    – Linas
    Dec 26, 2018 at 19:17

2 Answers 2

6
$\begingroup$

(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, see also Wikipedia; 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). 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}}$.

$\endgroup$
3
  • $\begingroup$ Yves, your argument holds for general cycles (and not just for $p$-cycles), right? I mean, given a $p$-root candidate $U$ (in fact, given any shift-commuting $U$) it should act on $J_{p'}$, the union of $p'$-cycles for any prime $p'$ (and not just $p$). And then, since $U$ is a $p$-root (which means any orbit of the action on $J_{p'}$ has cardinal $p$), one has it that $p$ must divide the cardinal of this union, which is $\frac{2^{p'}-2}{p'}$. Then $p$ must satisfy $2^{p'-1}-2\equiv 0\quad (pp')$ for any $p'$, which implies that the 2-shift has no roots at all. $\endgroup$ Jun 5, 2015 at 15:22
  • $\begingroup$ @EvaristoCarriego: no. A necessary and sufficient condition for a permutation to be a $p$-power ($p$ prime) is that for every multiple $n$ of $p$, the number of $n$-cycles is divisible by $p$. For instance, a single $p'$-cycle is a $p$-power when $p'\neq p$ is prime. And actually if $p$ is a Wieferich prime, then it is not hard to check that this is fulfilled, so that the 2-sided shift on 2 letters is a $p$-power in the full group of permutations. $\endgroup$
    – YCor
    Jun 5, 2015 at 17:13
  • $\begingroup$ yes, right, in the context of permutations that are not necessarily homeomorphisms you can make a $p$-root fix any $p'$-cycle (for $p'\neq p$) but I was almost sure that if $U$ is an homeomorphism (so that, by Hedlund-Curtis-Lyndon theorem it is induced by a block coding with a fixed block size) then this combinatorial constraint should prevent $U$ from fixing any $p'$-cycle in $T$ for infinitely many $p'$ (whence $p$ must divide the number of $p'$-cycles in $T$). Yet it seems that I can't prove it. $\endgroup$ Jun 17, 2015 at 4:12
3
$\begingroup$

A detailed study of the group of automorphisms of a shift of finite type (including the 2-shift mentioned here) is contained in The Automorphism Group of a Shift of Finite Type, Trans. Amer. Math. Soc. 308 (1988), 71-114 by me, Mike Boyle, and Dan Rudolph. I believe that the lack of square roots of the 2-shift goes back to a couple of papers of Ryan from the 1970s, referred to in this paper, which show in particular that the center of this group is just the powers of the shift.

This paper contains a lot of information about the possible algebraic properties of such automorphism groups, and their actions on aspects of the space such as periodic points (and a delicate consistency for different periods called the sign-gyration compatibility condition).

One basic question that is still open is: are the automorphism groups of the 2-shift and the 3-shift algebraically isomorphic as groups? Note that the 4-shift has a square root, and so by Ryan's theorem the automorphism groups of the 2-shift and the 4 shift cannot be isomorphic, since the center for the 4-shift is generated by an element with a square root, while the generator of the center for the 2-shift does not have a square root.

$\endgroup$
3
  • $\begingroup$ link to the Trans. AMS 1988 paper: ams.org/journals/tran/1988-306-01/S0002-9947-1988-0927684-2 $\endgroup$
    – YCor
    Jun 5, 2015 at 21:16
  • $\begingroup$ That the 2-shift has no square root is easy as already observed, but what about the 5-shift? $\endgroup$
    – YCor
    Jun 5, 2015 at 21:48
  • $\begingroup$ @YCor Thanks for adding the link. I'd imagine that characterizing which full shifts have square roots can be answered by techniques in this paper, but it's been a while since I've thought about such things. Another open question: Is there an automorphism of a full shift having infinite order and also having an nth root for infinitely many n? $\endgroup$ Jun 6, 2015 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.