Equations in finite semigroups: Explicit enumeration and asymptotics of solution numbers

2003/03/16 by Christian Krattenthaler, Thomas Müller
Mathematics · #math.CO #msc:05A16 #msc:05A15 #msc:05E99 #msc:16W22 #msc:20M20

paper · pdf

published as J. Combin. Theory Ser. A 105 (2004), 291-334. · 39 pages, AmS-LaTeX; several typos corrected

arxiv created 2003/03/16 · arxiv updated 2009/11/30

Abstract

We study the number of solutions of the general semigroup equation in one variable, X^\al=X^\be, as well as of the system of equations X²=X, Y²=Y, XY=YX in H\wr T_n, the wreath product of an arbitrary finite group H with the full transformation semigroup T_n on n letters. For these solution numbers, we provide explicit exact formulae, as well as asymptotic estimates. Our results concerning the first mentioned problem generalize earlier results by Harris and Schoenfeld (J. Combin. Theory Ser. A 3 (1967), 122-135) on the number of idempotents in T_n, and a partial result of Dress and the second author (Adv. in Math. 129 (1997), 188-221). Among the asymptotic tools employed are Hayman's method for the estimation of coefficients of analytic functions and the Poisson summation formula.

Related

• On equations over Brandt semigroups
• On the number of tuples of group elements satisfying a first-order formula
• Equations in wreath products
• Polynomial Equations in Subgroups and Applications
• Quadratic word equations with regular constraints and the exponent of periodicity