Transitivity and synchronization

Let Sn be the symmetric group of all permutations of {1,…,n}, and Tn the full transformation monoid of all functions from this set to itself.

Recently I have come to the meta-conjecture that there is a fairly close analogy between transitive subgroups of Sn (those which can map any point to any other) and synchronizing submonoids of Tn (those containing an element mapping everything to a single point).

Here is a list of some (known or conjectured) similarities, and some differences, between these concepts.

  • The probability that a random permutation generates a transitive subgroup, and the probability that a random function generates a synchronizing submonoid, are both equal to 1/n.
  • The probability that two random permutations generate a transitive subgroup, or generate the symmetric or alternating group, are both 1-o(1) (indeed, 1-1/n+O(1/n2) as n→∞). I conjecture that the probability that two random functions generate a synchronizing monoid is 1-o(1). However, the probability that they generate the full transformation monoid is zero (see below).
  • The probability that a random permutation lies in no transitive subgroup of the symmetric group apart from the symmetric and possibly the alternating group is 1-o(1) (a lovely theorem of Luczak and Pyber, though we don’t have a good estimate of the rate of convergence). On the other hand, every function lies in a proper synchronizing submonoid of the full transformation monoid (again see below).

If M is a submonoid of Tn generated by a set A, then the permutations in M form a subgroup of Sn generated by the permutations in A. So, if A generates Tn, and n>2, then A must contain at least two permutations, and at least one non-permutation. This means that two random elements cannot generate the full transformation monoid. Moreover, permutations are exponentially rare in Tn, so a huge set of random elements is required to generate it with high probability. Furthermore, if g generates a synchronizing submonoid, then so do f and g for all functions f, and this monoid cannot be the whole of Tn.

I have been trying to prove the conjecture that two random functions generate a synchronizing monoid with high probability. Following the proof of Dixon’s theorem, we need to describe the maximal non-synchronizing submonoids of Tn, and to show that the number of pairs of elements contained in at least one of them is small compared to n2n.

I have now succeeded, after a fashion, in doing the first of these tasks. The maximal non-synchronizing monoids have a description as endomorphism monoids of rather special graphs (though there is still a puzzle here that I can’t answer). However, the counting part of the argument still eludes me. We need estimates for how many such submonoids there are, how large they are, and (unless we are very lucky) some information about their overlaps.

Of course, it is quite possible that a completely different strategy would succeed.

A final open problem: what about the submonoid generated by one random permutation and one random function? (It is easy to see that two random permutations and one random function synchronize with high probability.)


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s