7
$\begingroup$

This question is related to that (if $s$ is co-prime with prime $p$ and a permutation in $S_s$ has order $p$, then it fixes a point).

Let us fix two (finite) numbers $p\gg 1, n\gg 1$. Say, $p=47, n=18999$. Take a sequence $s_1,s_2,...$ of numbers not divisible by $p$. For each $s$ compute $p(s)$ as follows. Take two permutations $a, b$ in the symmetric group $S_s$ such that $\langle a,b\rangle$ is highly (say, $3$-)transitive on $\{1,...,s\}$. Compute the probability $p(s,a,b)$ that for a word $w(x,y)$ of length $n$, $w(a,b)$ has a fixed point. Then $p(s)$ is the maximum of $p(s,a,b)$ for all (such) $a,b$.

Question. Is it true that $$\lim_{i\to\infty} p(s_i) = 0?$$

Note. As Doron Puder explained to me, one cannot replace "highly transitive" by "transitive" because $a,b$ can generate a dihedral group of order $2s_i$ in which case $p(s_i,a,b)$ will be at least $1/5$. F. Ladisch explains in his answer to the previous version of the question below that "2-transitive" is not enough either.

Update Perhaps the "correct" condition instead of "highly transitive" should be "$\langle a,b\rangle$ contains "few" permutations having fixed points, that is the portion of such permutations in $\langle a,b\rangle$ tends to 0 as $i\to \infty$. Examples of Puder and Ladisch contain "many" permutations fixing a point and the arguments were based on that fact. Thus the problem is this: if for many words $w(x,y)$ of length $n$ the permutation $w(a,b)$ has a fixed point, then many elements in $\langle a,b\rangle$ have fixed points, a local-to-global property.

$\endgroup$
5
  • $\begingroup$ Just to make sure I understood your question: the probability is the uniform probability over the (fixed) set of words of length $n$ with $2$ letters, right? Your question is therefore whether $p(s_i)=0$ for $i$ large enough, or did I miss something? $\endgroup$ Commented Jul 26, 2011 at 15:40
  • $\begingroup$ @Mikael: $p(s,a,b)$ is the fraction $\frac uv$ where $v$ is the total number of reduced group words of length $n$ in 2 letters (that is $4\cdot 3^{n-1}$) and $u$ is the number of reduced group words of length $n$ in two letters for which the permutation $w(a,b)$ has fixed points. $\endgroup$
    – user6976
    Commented Jul 26, 2011 at 16:08
  • $\begingroup$ Dear Mark, what is the role of the integer p in the question? (Is m=p?). Your question is about two elements a and b which generate a sufficiently large symmetric group, and every word of length n in two variables, when we substitute a and b in the word then with high probability there are no fixed points. Can you explain and motivate the nondivisibility property? $\endgroup$
    – Gil Kalai
    Commented Jul 26, 2011 at 20:52
  • $\begingroup$ @Gil: Yes, $m=p$. It is a result of my edit. It was $m$ everywhere, then I decided that it should be a prime, hence $p$. $\endgroup$
    – user6976
    Commented Jul 26, 2011 at 21:18
  • $\begingroup$ In fact the formulation with the portion of permutations with fixed points as in the update seems to be not good also because in $S_n$ the number of fixed point-free permutations is approximately $n!/e$. Looks like fixed points do not help at all and I need to return to the cycle structure (= exponent of permutations) as in the original formulation. $\endgroup$
    – user6976
    Commented Jul 27, 2011 at 3:34

1 Answer 1

4
$\begingroup$

Update: It just occured to me that if you fix the length $n$, then $p(s,a,b)$ is always a fraction with denominator $4\cdot 3^{n-1}$, so only finitely many values are possible. Thus for a sequence $(s_i,a_i,b_i)$ with $\langle a_i, b_i\rangle\leq S_{s_i}$, the sequence $p(s_i, a_i, b_i)$ can converge only if it is constant eventually. It converges to zero only if $\langle a_i, b_i \rangle$ contains no reduced words of length $n$ with fixed points for all but finitely many $i$. So I doubt that only looking at words of length $n$ can tell you much. Also, transitive but nonregular permutation groups always seem to have a large portion of elements with fixed points.

(The following was my original answer to a previous version of the question:)
Take $C_{p-1} \ltimes C_p$ (or somewhat more generally, the affine group of a finite field of order $q=p^k$). This is generated by two elements, has order $(p-1)p$, and all but $p-1$ elements have fixed points. So whithout taking into account the restriction on the length, the probability for fixed points is $\frac{1}{p}$. For $p\gg n$, the probability will be similar, I think. So if you take a sequence of primes tending to infinity for $s_i$, this shows that $\lim_{i\to \infty} p(s_i)$ can be big (probably $1$, in this case).

EDIT: I justed realized that I misunderstood the question, since you are asking for the fraction of reduced words, and not the fraction of group elements itself. However, if we take $a$ and $b$ to be generators of the cyclic groups of order $p-1$ and $p$ respectively, then the reduced words mapping into the regular subgroup $C_p= \langle b \rangle$ are those where the numbers of $a$'s and $a^{-1}$'s occurring is equal $\mod p-1$, that is, equal, if $p\gg n$. The number of these words is independent of $p$, and there are other words, so $\lim_{i\to \infty} p(s_i)\neq 0$. Hope now it's correct.

$\endgroup$
4
  • 1
    $\begingroup$ The only finite 6-transitive permutation groups are the alternating and symmetric groups. $\endgroup$
    – Derek Holt
    Commented Jul 26, 2011 at 20:55
  • $\begingroup$ @Derek: You are right. I think that transitivity is not the right thing here. I like the local-to-global formulation in the update better. $\endgroup$
    – user6976
    Commented Jul 27, 2011 at 3:20
  • $\begingroup$ I removed my comment about transitivity. $\endgroup$
    – user6976
    Commented Jul 27, 2011 at 3:23
  • $\begingroup$ I accept this answer because it answers the original question. The problem is that the question was not well-formulated. I need to think about a better formulation. $\endgroup$
    – user6976
    Commented Jul 27, 2011 at 7:17

You must log in to answer this question.