Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\sigma$ be a permutation of $\mathbf Q.$ We call $\sigma$ bounded (the term might be somewhat misleading, but however it is used in a couple of papers) if there is a real number $M$ such that $$ \mathrm{dist}(\sigma x,x) =|\sigma x-x| \le M $$ for all $x \in \mathbf Q.$

Now can a bounded infinite cycle $$ \pi=(\ldots,-2,-1,0,1,2,\ldots) $$ be written as a product of bounded involutions (permutations of order two)? Notice that "nice" bounded products of, say two, disjoint infinite cycles can be written as products of bounded involutions, e.g. the permutation $$ (\ldots,-4,-2,0,2,4,\ldots) (\ldots,-3,-1,1,3,\ldots). $$

EDIT: to clarify a bit chandok's argument below: suppose $\pi$ is a product of two involutions $\sigma$ and $\tau$: $\pi=\sigma \tau.$ Then $$ \sigma \tau \sigma(n+1)=\sigma(n+1)+1. $$ for all integers $n.$ On the other hand, $n+1=\pi(n)$ and $\tau \sigma=\pi^{-1},$ whence $$ \sigma (\tau \sigma) \pi(n) = \sigma \pi^{-1} \pi(n)=\sigma(n)=\sigma(n+1)+1. $$ Thus $\sigma(n+1)=\sigma(n)-1$ and $\sigma(n)=a-n$ for all naturals $n.$ Thus $\sigma$ is unbounded.

The argument seems to be not easily adaptable for products of more than two involutions.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Suppose you have involutions $\sigma, \tau$ such that $\sigma \tau (n) = n+1$ forall $n \in \mathbb{Z}$, and $\sigma \tau (n) = n$ otherwise

Then forall $n \in \mathbb{Z}$, we have $\sigma \tau (n) = n+1$, so $\tau (n) = \sigma\sigma\tau(n) = \sigma(n+1)$, and $\sigma\tau\sigma(n+1) = \sigma\tau\tau(n) = \sigma(n)$. Moreover, $\sigma \tau (n-1) = n \neq n+1 = \sigma \tau (n)$, so $\sigma(n) = \tau(n-1) \neq \tau(n) = \sigma(n+1)$, so $\sigma(n+1)$ is not fixed by $\sigma \tau$.

Therefore $\sigma(n+1)$ is an integer, and $\sigma(n+1)+1 = \sigma(n)$, and likewise for $\tau$. So there exists integers $a$ and $b$ such that $\sigma(n) = a-n$ and $\tau(n) = b-n$. And these involutions are not bounded.

Edit : So it can't be written as a product of only two involutions (I missed the part not being restricted to products of more than 2 involutions, I will think about it)

As you noticed, using a product of 2 bounded involutions you can form the product of two infinite cycles going opposite directions. For $(a,b) \in \mathbb{R}$, call $\tau_{(a,b)} = \prod_{n \in \mathbb{Z}} ((n+a) (n+b))$. $\tau_{(a,b)}$ is a bounded involution, and $\sigma_{(a,b)} = \tau_{(a+1,b)} \tau_{(a,b)}$ is a permutation that adds $1$ to numbers of the form $n+a$ and substracts $1$ to numbers of the form $n+b$.

Now consider the (infinite) product $\sigma = \sigma_{(0,1/2)} \sigma_{(1/2,1/3)} \sigma_{(1/3,1/4)} \ldots$. $\sigma$ is just the permutation you want.

To write it as a finite product of bounded involutions, first rewrite it as a product of two permutations so that the things inside a product all have disjoint support so the involutions later can commute between themselves : $\sigma = (\sigma_{(0,1/2)} \sigma_{(1/3,1/4)} \ldots) (\sigma_{(1/2,1/3)} \sigma_{(1/4,1/5)} \ldots)$

Then expand each $\sigma_{(a,b)}$ into its product of two involutions $\sigma = ((\tau_{(1,1/2)}\tau_{(0,1/2)})(\tau_{(4/3,1/4)}\tau_{(1/3,1/4)})\ldots) ((\tau_{(3/2,1/3)}\tau_{(1/2,1/3)})(\tau_{(5/4,1/5)}\tau_{(1/4,1/5)}) \ldots)$

Commute them to get a product of 4 bounded involutions (with infinite support):

$\sigma = (\tau_{(1,1/2)}\tau_{(4/3,1/4)}\ldots)(\tau_{(0,1/2)}\tau_{(1/3,1/4)}\ldots) (\tau_{(3/2,1/3)}\tau_{(5/4,1/5)}\ldots)(\tau_{(1/2,1/3)}\tau_{(1/4,1/5)}\ldots)$

share|improve this answer
    
This does not answer the OP's question. It might be that $\sigma\tau$ can be written as some other product of involutions that are bounded. It is clear that any permutation can be written as a product of involutions some of which are unbounded. Your example is an instance of that. –  Alex B. Apr 4 '11 at 17:29
    
thanks! @Alex: Right. Moreover, what I asked was about productS, products of two, three, four, etc. bounded involutions. –  Olod Apr 4 '11 at 17:38
    
A neat idea! Thank you very much indeed. –  Olod Apr 4 '11 at 20:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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