Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Being motivated by this recent post of mine, I am thinking about the base 2 decimal expansion of irrational algebraic numbers. My main question is whether or not the reasoning I outline below contains any major flaws.

First of all, it should be clear that in the base 2 decimal expansion of an irrational number on the interval [0,1], the digits 0 and 1 appear infinitely often; since otherwise the decimal expansion would terminate and the number would be not be irrational.

Therefore, I consider permutations of the sequence $I$ = 101010101010....

Let $K$ be the group of all permutations of $I$, and let $Q$ be an infinite subgroup of $K$.

Then I claim that every $Q$ has a basis in terms of the fundamental permutation of switching the position of two elements. This amounts to the claim that every permutation in $Q$ can be written as a countably infinite composition of switching operations.

(to be clear, a switch is a permutation $A$ik which exchanges the $i$ and $k$ positions of some infinite binary sequence)

I conjecture that $Q$ is a countably infinite subgroup of $K$ if and only if it has a basis whose elements commute (i.e. the basis of $Q$ never switches the same position in the sequence twice)

In the first direction, assume $Q$ has a commuting basis; then it's clear that the elements of $Q$ can be listed according to the order of lowest to highest positions of switches, and therefore can be counted.

In the other direction, assume $Q$ has a non-commuting basis, but is countable. Then by writing the elements of $Q$ in a list where each element is written in terms of an ordered composition of basis elements, it's clear that we can apply the diagonal method to construct an element of $Q$ which is not on the list; which is a contradiction.

(EDIT: to clarify the comment below, I originally called Q a subset, but edited it to subgroup)

share|improve this question
I don't understand what you mean by a basis of a subset of a group. –  Qiaochu Yuan Jul 31 '10 at 17:20
In any case, I am pretty sure both directions of your argument are invalid. Being orderable doesn't imply be countable: a counterexample is the subgroup generated by the transpositions (2i-1, 2i) for positive integers i, which is uncountable. AS for the other direction, the subgroup of permutations which switch only finitely many locations is nonabelian but countable. –  Qiaochu Yuan Jul 31 '10 at 17:32
I think this is the weak point of my argument. I am trying to mimic the case of permutations of a finite sequence. Any permutation of a finite sequence can be written as the composition of a finite number of switching operations. So the "basis" elements are the switch operations. For the case of permutations of an infinite sequence, I believe/assume that every permutation can be written as the countably infinite ordered composition of switching operations. –  Matt Calhoun Jul 31 '10 at 17:36
Ah, sorry: in the first example I just mean the subgroup of all elements which switch 2i-1 with only 2i. In any case, whether that's true or not (with the right definition of countably infinite composition) your last two arguments are still invalid if you mean what I think you mean by "basis." –  Qiaochu Yuan Jul 31 '10 at 17:43
What is meant by "a countably infinite composition of switching operations"? As you apply the operations, one after another, a number might get moved infinitely often; where should such number be mapped under the composite permutation? For a specific example, what is the composition of $A_{12}$ followed by $A_{23}$ followed by $A_{34}$ followed by $\dots$? The number 1 gets mapped to 2 by the first switch, then to 3 by the next switch, then to 4, etc. Where does the composite permutation send 1? –  Andreas Blass Jul 31 '10 at 21:53

1 Answer 1

Regarding Andreas Blass's comment:

I believe we cannot afford pushing 1 to infinity since its image will be undefined. The question whether every permutation of the naturals could be obtained as some composition of transpositions $t_1,t_2,\dots$ is cute, and I think that the answer is ``Yes'': It suffices to prove this where the $t_i$ are allowed to be any finitely supported permutations, and then we pick each $t_n$ such that $t_n\cdots t_1$ restricted to $\{1,\dots,n\}$ is equal to the values of the prescribed permutation on $\{1,\dots,n\}$. Then the permutation $$\cdots t_2t_1$$ is then well defined and equal to the prescribed one.

share|improve this answer

Your Answer


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.