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

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.

share|improve this question
    
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? –  Mikael de la Salle Jul 26 '11 at 15:40
    
@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. –  Mark Sapir Jul 26 '11 at 16:08
    
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? –  Gil Kalai Jul 26 '11 at 20:52
    
@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$. –  Mark Sapir Jul 26 '11 at 21:18
    
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. –  Mark Sapir Jul 27 '11 at 3:34

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
1  
The only finite 6-transitive permutation groups are the alternating and symmetric groups. –  Derek Holt Jul 26 '11 at 20:55
    
@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. –  Mark Sapir Jul 27 '11 at 3:20
    
I removed my comment about transitivity. –  Mark Sapir Jul 27 '11 at 3:23
    
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. –  Mark Sapir Jul 27 '11 at 7:17

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.