Friday, February 28, 2014

Nonpermutational stuff, again

So.
We've seen that when S is a subsemigroup of Tn, whose members have exactly one fixed point each, then we can group them by their fixed points: let Si be the subsemigroup of S consisting of those guys having i as fixed point.
We've also seen that Si is indeed a semigroup and for each i, there exists a partial ordering <i of [n] such that when pf=q for some f in Si, then p<iq. Except when p=i. This <i has i as maximal element.
Without loss of generality we can assume that

  • Sn is (one of) the largest among those Si guys and
  • <n is consistent with the standard <,
i.e. for each f in Sn, p<pf whenever p<n.

We show that if Sn is "large enough" then the other Si guys are "small". Namely,
Lemma. Suppose for each i<j, i'<j' with i'<>j' there exists some f in Sn with if=j, i'f=j'.
Then for each i and f in Si we have

  1. if j<i, then j < jf;
  2. if i<=j, then i=jf.
Observe that this lemma implies that |Si| <= (n-1)! / (n-i)! since one can choose the value only for the elements smaller than i some larger value and all the others have to be mapped to i. Summing these values we get an upper bound e(n-1)! for the size of these semigroups.
The other option is that Sn does not satisfy the conditions for the lemma. It's routine to check that in this case |Sn| <= (n-1)! - (n-3)! (this bound is sharp). Since Sn was chosen to be the largest, we have that |S| <= n((n-1)! - (n-3)!).
Now for the proof of the lemma...

  1. For i = n, the claims get satisfied: guys below n get elevated and n is mapped to n, okay. So assume i < n. And let f be a member of Si.
  2. Then, nf < n (since n is not a fixed point of f).
  3. Assume pf < p for some p and that pf <> nf. Then by the assumption, nfg = n and pfg = p for some g in Sn. Thus the composition fg has two fixed points p and n, a contradiction. Hence if pf < p, then pf = nf. In particular, if p < nf, then p <= pf. (That is, all backward arrows share their target.)
  4. Assume nf < i. Note that if = i. Then by assumption nfg = i and ig=n for some g in Sn, and fgfg has two fixed points n and i, a contradiction. Thus, i <= nf.
  5. Assume i < nf. Also nfffff..f is eventually i < nf (since f is nonpermutational with target i), hence there exists some smallest k such that nf^{k+1} < nf. However, this involves a second backward jump with target different from nf, a contradiction. Thus i = nf.
  6. Observe that 3, part b and 5 together prove Statement 1.
  7. Assume i < j < jf. Then for some g, jfg = n and ig = j and fgfg has two fixed points n and j, a contradiction. Hence if i < j, then jf < j, thus jf = i, proving Statement 2.
That's all. It turned out to be not that horrible at all...
...I'd guess the bound is not strict. I would be surprised if some S with |S| >= 3(n-1)! could be actually constructed...