Looking for a permutation with disjoint image in a generated subgroup

90 Views Asked by At

Let $n,m$ be integers with $m\geq 2n, n \geq 1$, and $A=\lbrace 1,2,\ldots, n \rbrace$. Let $S_m$ be the symmetric group on $[|1..m|]$. For every $k\in[|1,n|]$, take a permutation $\sigma_k\in S_m$ satisfying $\sigma_k(k)=k+n$, and consider the subgroup $G$ of $S_m$ generated by $\sigma_1,\ldots,\sigma_n$.

Question: Must $G$ always contain a permutation $\sigma$ such that $\sigma A \cap A = \emptyset$ ?

My thoughts : I can show that the answer is yes for $n=2$. Suppose by contradiction that $\sigma A\cap A \neq \emptyset$ for every $\sigma \in G$. I will denote $\sigma_1$ by $a$ and $\sigma_2$ by $b$, so that $a(1)=3$ and $b(2)=4$.

From $aA\cap A \neq \emptyset$, we deduce $a(2)\in\lbrace 1,2 \rbrace$, and similarly $bA\cap A \neq \emptyset$ forces $b(1)\in\lbrace 1,2 \rbrace$.

Suppose first that $a(2)=1$. Then $a^2(2)=3$, so from $a^2A\cap A \neq \emptyset$ we deduce $a^2(1)\in\lbrace 1,2\rbrace$, or $a(3)\in\lbrace 1,2\rbrace$, which forces $a(3)=2$. We then have $ab(2)=a(4)\not\in \lbrace 1,2\rbrace$, so from $abA\cap A \neq \emptyset$ we deduce $ab(1)\in\lbrace 1,2\rbrace$, and hence $b(1) \in a^{-1}\lbrace 1,2\rbrace=\lbrace 2,3\rbrace$. But we already know that $b(1)\in\lbrace 1,2 \rbrace$, so $b(1)=2$. Next, we have $ba^{-1}(1)=4$, so $ba^{-1}(2)\in \lbrace 1,2\rbrace$, and hence $b(3)=1$. But then $b^2A=\lbrace 4,b(4)\rbrace$ is disjoint from $A$ which is excluded. We are therefore done with this $a(2)=1$ case.

We may therefore assume $a(2)=2$, and by symmetry we may also assume $b(1)=1$. Then $ab(1)=3$, so $a(4)=ab(2)\in \lbrace 1,2\rbrace$ and hence $a(4)=1$. Similarly, $ba(2)=4$, so $b(3)=ba(1)\in \lbrace 1,2\rbrace$ and hence $b(3)=2$. But then $ba^{-1}A=\lbrace 4,b(4)\rbrace$ is disjoint from $A$ which is absurd. This finishes the proof.

1

There are 1 best solutions below

1
On BEST ANSWER

If I understood the problem correctly, the answer is negative for $n\geq 3$.

Let $\psi_k$ be the transposition which swaps $k$ with $(k+n)$ and leaves other elements untouched. Then, set $\sigma_1=\psi_1\psi_2$, $\sigma_2=\psi_2\psi_3$, $\sigma_3=\psi_3\psi_1$ and $\sigma_k=\psi_k$ for $k\geq 4$.

All the $\psi$ permutations commute with each other and each of them is of order $2$, so any product of them is of the form $\prod_{i=1}^n \psi_i^{e_i}$ with $e_i\in \{0,1\}$. Since $\psi_i$ is the only transposition which moves element $i$, the condition $\sigma A\cap A=\emptyset$ implies $e_i=1$ for all $i$. However, $e_1+e_2+e_3=3$ is an odd number, while each of $\sigma_1$, $\sigma_2$ and $\sigma_3$ contain an even number of these transpositions so any product of them would result in even value of $e_1+e_2+e_3$.