A Schreier formula for the free monoid
(Conjecture proposed by Dominique Perrin)

Let A be a finite alphabet and let X be a finite subset of A*. Let f : A* --> M be the syntactic morphism of X* and let G be a maximal group in M such that f-1(G) is not a cyclic submonoid of A* (i.e., not of the form u* for some word u). Such a group admits a faithful representation as a permutation group. Let r be the rank (that is, the minimal number of generators) of G, let d be its degree and let c = Card(X).

Conjecture: d(r-1) ≤ c-1

Reminder. The Schreier formula states that if F is a free group of rank r and H is a finitely generated subgroup of rank c and degree d, then c-1 = d(r-1).

Example. Let X = {aaa, ba, abaa, aab}. The minimal automaton of X* is represented in Figure 1.

Schreier
Figure 1. The minimal automaton of X*.

Then the words aa and aabaa generate a subgroup G of M represented as a permutation group on {1, 2, 3}.

  1 2 3
aa 3 1 2
aabaa 3 2 1

This group is actually the symmetric group S3. Here we have c = 4, d = 3 and r = 2. Thus 3(2-1) = d(r-1) ≤ c-1 = 3.


The conjecture has been recently proved for r = 2 if X is a prefix code. See [3] for more details.

References.

  1. Dominique Perrin, Sur les groupes dans certains les monoïdes finis, Non commutative structures in Algebra and Geometric Combinatorics, Quaderni de la Ricerca scientifica 109, CNR, Roma (1981), 27--36.

  2. Dominique Perrin and Jean-François Perrot, A propos des groupes dans certains monoïdes syntactiques, Lecture Notes in Mathematics 855, Springer, Berlin (1980), 82--91.

  3. Dominique Perrin and Giuseppina Rindone, On syntactic groups, Bull. Belg. Math. Soc. Simon Stevin 10 (2003), suppl., 749-759.

  4. Dominique Perrin and Marcel Paul Schützenberger, Codes et sous-monoïdes possédant des mots neutres. Rapport IRIA 214 (1977)

  5. Giuseppina Rindone, Sur les groupes syntaxiques d'un langage, RAIRO Informatique Théorique 19, (1985), 57-70.

  6. Marcel Paul Schützenberger, The critical factorization theorem, Chap. 8 in M. Lothaire, Combinatorics on Words, Cambridge University Press, 1982.

Last modified 03/29/2008