# about fixed points of permutations

This is another attempt to make a feasible approximation of this question. Two previous (unsuccessful) attempts are here.

Let $n\gg 1$ be a fixed number (say, $n=10^{10}$), $k\gg 1$ a natural number. Let $a,b$ be two permutations from $S_k$. Suppose that for every word $w(x,y)$ of length $\le n$, the permutation $w(a,b)$ has a fixed point. Is it true that every permutation in $\langle a, b\rangle$ has a fixed point?

-
If k is much much larger than n, say about the square of the size of the number of group words of length at most n generated by two letters, then I think the answer is no by a simple construction of a disjoint union of pieces. Do you intend to have restrictions on k? Gerhard "Ask Me About System Design" Paseman, 2011.07.27 – Gerhard Paseman Jul 27 '11 at 17:15
@Gerhard: no, there are no restrictions on $k$, it can be arbitrary large. If you can construct a counterexample, it would be nice Although it would mean that this approximation of the original problem is not successful too, but nobody can guarantee that the answer to the original problem is positive either. – Mark Sapir Jul 27 '11 at 17:36

If $k$ is allowed to be much, much larger than $n$, then no.

A consequence of the assumption is that $a$ and $b$ each have fixed points. Let's take a toy example and see for what $n$ the example works. Let $a$ be the cycle that moves the numbers 1 to 7 in an increasing fashion, and $b$ moves 6 to 10 in a decreasing fashion. Then this example works for $n=1$, and almost works for $n=2$. A word which may not have a fixed point is $ab^{-1}$.

That's ok. Let us copy the example above, and have $b$ move elements in an increasing fashion. Now the disjoint union will be an example for $n=2$. However, for any word, we can create a slice on which that word has a fixed point; taking thw disjoint union of enough examples (and enlarging the domains so that eventually there is a fixed-point free permutation generated by $a$ and $b$), we get an answer of no for very large $k$.

EDIT 2011.07.27

Since a conjugate of an element with a fixed point has a fixed point, I am going to attempt some optimization in my example.  Let $W$ be the set of reduced group words of length at most $n$ on two variables (so there are about $4^n$ such words, most likely less).  If $x$ is one of the variables and $w$ is a short enough word in $W$, then $xwx^[-1}$ may be in $W$; if it isn't, an equivalent reduced form is in $W$, so let us label this new form if needed $w'$, and say that $w$ and $w'$ are in the same conjugacy class.  It should be clear that this relation can be extended to an equivalence relation on $W$.  Further, when a word $w$ is realized in a permutation group $G$ by replacing the variables $x$ and $y$ by elements $a$ and $b$ from $G$, and we call the realization $v$, and similarly for $w'$ and $v'$, then $v$ has a fixed point iff $v'$ has a fixed point.

The upshot of the preceding paragraph is that I need worry only about distinct representatives of the equivalence relation for the construction, so let $C$ be a set of such representatives which has precisely one member from every equivalence class on $W$.  Let the underlying set $X$ be $C \times 2n +1$.  I will define the element $a$ to act on $X$ so that for all $c$ in $C$, $a((c,0)$ is $(c,0)$, $a((c,2n)) = (c,1)$, and otherwise $a((c, k))=(c,k+1)$.  So $a$ looks like $C$-many copies of the cycle $(1,...,2n)$.  I will define $b$ similarly, but with two key differences: $k > n$ will mean $b((c,k))=(c,k)$, and $k \leq n$ implies $j \leq n$, where $j$ is such that $b((c,k))=(c,j)$.  So $b$ looks like $C$-many different slices acting in different ways on $(0,...,n)$

At this point, it should be clear that $ba^n$ will have no fixed points, because $a^n$ will have moved for each slice $(1,...n)$ "out of the reach of $b$', and we will arrange that $b$ moves each copy of $0$.  I now want to ensure that for each $c$ in $C$, the realization of $c$ by $a$ and $b$ has a fixed point.

Choose a $c$ in $C$.  If $c$ has only one variable, let $b$ act like $a$ does, except on this slice indexed by $c$ have $b$ look like the cycle $(0,...,n)$ where we had $a$ look like the cycle $(1,...,2n)$. Otherwise, $c$ has fewer than $n$ instances of both variables used to make words in $W$.  Take the instances of one variable, say $x$, which will be replaced by $a$ in the realization of the word $c$, and divide $(1,...,n)$ into pieces to be acted on appropriately. If $x^k$ occurs in the word $c$ to the precise power $k$, we will need a piece of size $(k+1)$ consecutive integers inside $(1,...n)$.  For illustration, assume the word $c$ is $x^2y^2x^{-2}y$ Let us reserve the pieces $(1,2,3)$ and $(5,6,7)$ in anticipation. $a^2$ will take 1 to 3 and $a^{-2}$ will take 7 to 5. Let us define $b$ to look like a cycle on $(0,..,n)$, with the proviso that it takes 3 to 4, 4 to 7 and 1 to 5. Otherwise make the choices consistent with the provisos. If I did not make a mistake, it should be clear that for this word $c$, its realization on this slice has 1 as a fixed point. So however the realization of $c$ might affect the other slices, it will have at least one fixed point on this slice.

This works for each word $c$ since we can use $c$ as a template to break $(1,..,n)$ into pieces on which $a$ will act in a predetermined fashion, but we can choose a fixed point and have enough freedom to choose $b$ to "stitch the pieces together" and still look like some cycle on $(0,...,n)$.  I apologize for not having a more formal way to specify how $b$ acts on this slice.  Alternatively, choose a small number $d(c)$ such that there are actions $a$ and $b$ in the symmetric group on $d$ letters where the realization of $c$ by $a$ and $b$ in this group has a fixed point, AND at the same time $ba^n$ does not have a fixed point; use that $d$ to replace my slice for $c$ above.  I like my version because I can claim that $a and b$ are realizable by two members of  the symmetric group on $m$ letters, where $m= 2n+1 \times$ cardinality of $C$.

I cannot be more clear or more concise right now.  If this does not communicate the idea, I ask someone else to help Mark. END EDIT 2011.07.27

Gerhard "The Wheels Turn And Turn" Paseman, 2011.07.27

-
The idea that it is enough to consider one but arbitrary word of length $\le n$ seems to be good. As I understand, for every $w(x,y)$ with $|w|\le n$ you consider two permutations $a_w, b_w$ such that $w(a_w,b_w)$ has fixed points while some permutation in $\langle a_w, b_w\rangle$ has no fixed point. Then you take the disjoint using of the domains of these permutations, and define $a,b$ piece-wise. It probably will succeed but it is not clear to me how you define $a_w,b_w$. – Mark Sapir Jul 27 '11 at 18:02
For an arbitrary word w, focus on the orbit of one point, since you want that point to be fixed. If the orbit is the length of the word, you can fill in the rest of the behaviour so that a and b are large cycles. However, the cycles need to be so large that e.g. ba^l has no fixed points for l much larger than n. Gerhard "Ask Me About System Design" Paseman, 2011.07.27 – Gerhard Paseman Jul 27 '11 at 18:11
Sorry, I meant to say "if the length of the orbit is the length of the word". Gerhard "Ask Me About System Design" Paseman, 2011.07.27 – Gerhard Paseman Jul 27 '11 at 18:14
OK, but then when you combine all the permutations $a_w$ into $a$ and all $b_w$ into $b$, how do you show that $\langle a,b\rangle$ contains a fixed point-free permutation? Equivalently, you need one word $u(x,y)$ such that $u(a,b)$ has no fixed points. So far you have different words $u_w$ for different $w$. Right? – Mark Sapir Jul 27 '11 at 18:19
On each slice, it acts independently, but they all share a common property; for an l big enough, a^l "pushes b's elements out of b's reach". So as long as the cycle lengths are large compared to the common domain of what a and b move, ba^l will have no fixed points. You can probably arrange that l=n. Gerhard "Ask Me About System Design" Paseman, 2011.07.27 – Gerhard Paseman Jul 27 '11 at 18:25

Let me have a go at this one. We want to show that for any finite set $W$ of reduced words in $a,b$, we can find a subgroup $G = \langle a,b \rangle$ of some symmetric group $S_k$ such that all words in $W$ have fixed points when evaluated in $G$, but $G$ contains fixed-point-free elements.

Suppose inductively that we can do this for some set $W$, and we want to extend the construction to $W \cup \{w \}$ for some new word $w$. We may suppose that $w$ is cyclically reduced and that $w$ acts fixed-point-freely in $G$.

If $w$ has length $n$, then we can define partial permutations $a,b$ in the obvious way on $n$ points such that $w$ fixes the first of these. For any $p>n$, it is then easy to extend these partial permutations to permutations of a set of size $p$ that generate a transitive subgroup of $S_p$. In fact, by an old theorem of Jordan, if a primitive permutation group of degree $p$ contains a $q$-cycle for some prime $q<p-2$, then it must be the alternating or symmetric group and, by choosing $p$ to be a sufficiently large prime, we can make $b$ contains such a cycle, and thereby ensure that $a,b$ generate $A_p$ or $S_p$.

Do this for some prime $p > k$ to give a group $H \le S_p$, and let $K < S_{k+p}$ be generated by the disjoint actions of $a$ and $b$ in $G$ and in $H$. So all elements of $W \cup \{w\}$ have fixed points in $K$ and it remains to show that $K$ contains fixed-point free elements.

If all relations in $a,b$ that hold in $G$ held in $H$, then $H$ would be a quotient group of $G$, which is impossible, because $|H|$ is divisible by $p$, but $|G|$ isn't. So the permutations generated by the relations of $G$ generate a nontrivial normal subgroup of $H$ which, by the simplicity of $A_p$, must contain $A_p$. So, there exists a relation $v$ of $G$ such that $vw$ acts fixed-point-freely in $H$. Since $w$ acts fixed-point-freely in $G$, $vw$ is a fixed-point-free elemtn of $K$ as required.

-
@Derek: Thanks! – Mark Sapir Jul 28 '11 at 10:19