# Monoids (or semigroups) with a "finite decomposition" property

In my research I have come across the following condition on a monoid.

Every element $x$ satisfies the following property: there exists a natural number $n$ such that for any $m \geq n$ and any decomposition $x = x_1 \cdot x_2 \cdot \cdots \cdot x_m$ of $x$ it must be that at least one of $x_i$ is an idempotent.

Free monoids obviously satisfy this property, and every monoid which has only idempotent elements. And of course natural numbers under multiplication due to prime factorization.

A non-example is any monoid with a unit which is not the identity and things like positive rationals or reals under addition.

Decompositions of monoid elements seem to be studied in certain areas such as language theory, however I have not found a reference for this exact notion of "finitely decomposable", so I would like to know whether such a condition (or a condition close to it) has been encountered before, and if so, when.

If it helps in answering the question, all the monoids I am considering are commutative.

• A more usual thing to ask is that any sufficiently long factorization of x, some subword has product an idempotent. This weaker statement is true for finite monoids and is essentially the pumping lemma from automata theory. Commented Apr 30, 2017 at 14:53
• > A non-example is any monoid with an element which has an inverse, but is not its own inverse, You probably meant "a unit which is not the identity element".
– user6976
Commented Apr 30, 2017 at 16:36
• This will fail in any semigroup containing generalized inverses a,b with aba=a and bab=b with a,b not idempotents. This is quite rare for finite semigroups. Commented Apr 30, 2017 at 16:45
• Every element of finite order must be an idempotent. If x is finite order and not an idempotent it has arbitrarily long powers that are the same element Commented Apr 30, 2017 at 19:57
• @AlešBizjak I think you don't mean "A non-example is [something] and things like positive rationals or reals under multiplication", since the latter are groups, so they are already included in [something]. I think you mean the positive rationals (respectively, reals) under addition: More in general, any non-trivial, divisible, cancellative monoid is a non-example. Commented Apr 30, 2017 at 20:54

Reduced BF-monoids fit the bill here.

If $H$ is a multiplicatively written monoid with identity $1_H$, then an atom of $H$ is an element $a \in H \setminus H^\times$ for which there do not exist $x, y \in H \setminus H^\times$ such that $a = xy$, where $H^\times$ is the group of units of $H$. In particular, $H$ is called atomic if every non-unit of $H$ is a (finite) product of atoms, and is a BF-monoid if the factorizations (into atoms) of a fixed element cannot get arbitrarily long. On the other hand, we say that $H$ is reduced if $H^\times = \{1_H\}$.

There is a vast literature on the factorization theory of atomic monoids, though most of it is centered on the commutative and cancellative setting, for which you may want to have a look to:

A. Geroldinger and F. Halter-Koch, Non-Unique Factorizations. Algebraic, Combinatorial and Analytic Theory, Pure Appl. Math. 278, Chapman & Hall/CRC, Boca Raton (FL), 2006.

If, on the other hand, you are also interested in non-cancellative or non-commutative monoids, then it's a totally different story, and the best I can do is to address you to my own work with Yushuang Fan, where you will find some pointers to relevant literature (most notably, Smertnig's and Baeth and Smertnig's papers on cancellative categories) and an entire section devoted to basic aspects of the theory (namely, Sect. 2):

Y. Fan and S. Tringali, Power monoids: A bridge between Factorization Theory and Arithmetic Combinatorics, preprint (arXiv:1701.09152).

Lastly, if you find yourself wondering about sufficient conditions for a monoid to be BF, then there might be just the thing for you in another thread: Among many others, free monoids and free abelian monoids are BF-monoids (this is obvious), and so is the multiplicative monoid of non-zero elements of a Noetherian integral domain (this is less obvious). Moreover, if $H$ is a unit-cancellative BF-monoid ("unit-cancellative" means that $xy=x$ or $yx=x$, for some $x, y \in H$, implies $y \in H^\times$) and $M$ is a submonoid of $H$ with $M^\times = M \cap H^\times$, then $M$ is a BF-monoid too (Theorem 2.22(iv) + Corollary 2.23 in the above preprint). In point of fact, some of the examples mentioned in the OP are a special case of these.

Of course, reduced BF-monoids are not the only semigroups that fit your requests. But, to the best of my knowledge, they are the only class for which a systematic theory of factorization has been so far developed.

Edit. In the comments to this answer, Mark Sapir writes, "This does not seem to answer the question. The OP likes idempotents and does not like units." So, let me try to clarify why this is an answer to the question, though not the only one possible (I'll continue with the same notations used in the above).

Given $x \in H \setminus \{1_H\}$, we denote by $\mathsf L_H(x)$ the set of all $k \in \mathbf N^+$ for which there exist atoms $a_1, \ldots, a_k \in \mathbf N^+$ such that $x = a_1 \cdots a_k$. Moreover, we take $\mathsf L_H(1_H) := \{0\}$. It can be proved (this is not for free) that ${\sf L}_H(u) = \emptyset$ for every $u \in H^\times \setminus \{1_H\}$. In addition, it is straightforward that $$\mathsf L_H(x) + \mathsf L_H(y) \subseteq \mathsf L_H(xy),\ \text{ for all }x, y \in H.$$ Lastly, $H$ is a BF-monoid iff $\mathsf L_H(x)$ is finite and non-empty for every $x \in H \setminus H^\times$.

With this in mind, assume $H$ is a reduced BF-monoid, so that $\mathsf L_H(x)$ is finite and non-empty for all $x \in H$. Accordingly, pick $\bar x \in H \setminus \{1_H\}$, and let $\rho(\bar x)$ be the maximum of $\mathsf L_H(\bar x)$. If $m$ is an integer $\ge 1 + \rho(\bar x)$ and $\bar x = x_1 \cdots x_m$ for some $x_1, \ldots, x_m \in H$, then $$\mathsf L_H(x_1) + \cdots + \mathsf L_H(x_m) \subseteq \mathsf L_H(\bar x),$$ and hence $$\max \mathsf L_H(x_1) + \cdots + \max \mathsf L_H(x_m) \le \max \mathsf L_H(\bar x) = \rho(\bar x),$$ which is possible only if $\mathsf L_H(x_i) = \{0\}$, and hence $x_i = 1_H$, for some $i \in [\![1,m]\!]$. []

• This does not seem to answer the question. The OP likes idempotents and does not like units.
– user6976
Commented Apr 30, 2017 at 16:39
• @MarkSapir I maintain it does. But I could have given more details: I did it now, you may want to give it a second try. In short, assume $H$ is a reduced BF-monoid: The basic point of this answer is that, for every fixed element $x \in H$, there exists $n_x \in \mathbf N^+$ s.t., if $m \ge n_x$ and $x=x_1\cdots x_m$ for some $x_1,\ldots,x_m \in H$, then at least $m-n_x$ of the factors $x_i$ must be equal to the identity, and the identity is an idempotent, so... Commented Apr 30, 2017 at 20:23
• The OP likes many idempotents and does not like units at all. I do not know the reason (it would be interesting to know) but it seems clear from the question. A typical example: a Rees quotient of the direct product of a reduced BF-monoid with trivial group of units and a semilattice.
– user6976
Commented Apr 30, 2017 at 23:52
• @MarkSapir Every monoid with the property of the OP must be reduced, so units are not at all an issue. On the other hand, I'm not so sure about your statement that the OP "likes many idempotents": 2 out of 3 of the examples he mentions (namely, free monoids and the natural numbers under multiplication) are reduced BF-monoids. So, I sympathize with you that the OP would be better to clarify his requests, but this doesn't change that reduced BF-monoids are a legitimate answer to the question (in fact, they supply a non-trivial and wide class of interesting examples), in the form it stands. Commented May 1, 2017 at 3:48
• If $a^{-1}$ exists, $a\ne 1$, then $a=aa^{-1}aa^{-1}...a$, and none of the factors is an idempotent. Non-trivial units cannot exist. If there are no idempotents, then the monoid simply is a BF monoid without non-trivial units. But that is not what the OP wants apparently.
– user6976
Commented May 1, 2017 at 8:26