Timeline for Proving that a semigroup is regular
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 30, 2014 at 6:05 | answer | added | Pace Nielsen | timeline score: 2 | |
| Dec 4, 2013 at 4:00 | answer | added | James Propp | timeline score: 1 | |
| Dec 2, 2013 at 17:21 | comment | added | Benjamin Steinberg | Commuting doesn't help either, but today I am a bit overwhelmed with end of the term work. If you really want an example to show that there is no hope, I can do it in a few days (maybe over the weekend if lucky). | |
| Dec 2, 2013 at 17:20 | comment | added | Benjamin Steinberg | @James Propp, no the semigroup you are describing in your last comment is not regular. It is the BiHecke monoid of arxiv.org/pdf/1012.1361v3.pdf. It is a beautiful monoid with nice representation theory. | |
| Dec 2, 2013 at 13:43 | comment | added | James Propp | Here's a different sort of example: Let $X$ be the set of linear orderings of 1 through $n+1$, and for $1 \leq i \leq n$ let $a_i$ resp. $b_i$ be the operation on $X$ that sorts the $i$th and $i+1$st elements of a sequence into increasing resp. decreasing order. (Note that the $a_i$'s resp. $b_i$'s no longer commute with one another.) Is the semigroup generated by these $2n$ operations regular? | |
| Dec 2, 2013 at 7:19 | comment | added | Victor | From own experience on trying to resolve the question whether every f.p. monoid embeds in a f.p. regular monoid, I would say it's a very difficult task sometimes even in a given monoid to cook up an inverse for a product of letters each of which is regular | |
| Dec 2, 2013 at 6:07 | history | edited | Ricardo Andrade |
added top level tag
|
|
| Dec 2, 2013 at 5:58 | history | edited | James Propp | CC BY-SA 3.0 |
Gave link to motivating problems.
|
| Dec 2, 2013 at 5:12 | comment | added | James Propp | The simplest of the three semigroups to define is Sportiello's (but only if you already know about the abelian sandpile model). If $v$ is the $i$th vertex of the graph, let $a_i$ be the usual add-a-chip-at-$v$-and-relax operator, and let $b_i = U a_i U$ where the operator $U$ sends a sandpile $\sigma$ to the unique sandpile $\sigma'$ such that for each vertex $w$, $\sigma(w)+\sigma'(w)$ equals 1 less than the degree of $w$. See "What is a ... Sandpile?" by Lionel Levine and me for basic definitions: ams.org/notices/201008/rtx100800976p.pdf | |
| Dec 2, 2013 at 4:32 | comment | added | Benjamin Steinberg | Can you describe the semigroup you are interested in? If you can describe it as a collections of functions, you can probably easily check in GAP exactly how many regular elements it has, etc. SAGE also has some semigroup capability. | |
| Dec 2, 2013 at 4:28 | comment | added | Benjamin Steinberg | If $a$ and $a'$ have quasi-inverses $b,b'$ respectively, then the easiest condition to guarantee $aa'$ has a quasi-inverse is to have the idempotents $ba,a'b'$ and $ab,b'a'$ commute. Then $b'b$ with be the quasi-inverse of $aa'$ because $aa'b'baa'= abaa'b'a'=aa'$ and similarly $b'baa'b'b=b'b$. In general the regular elements of a semigroup do not form a subsemigroup and a semigroup can be generated by idempotents and not be regular, | |
| Dec 2, 2013 at 4:25 | comment | added | Benjamin Steinberg | You can have an element with a quasi-inverse whose square does not. | |
| Dec 2, 2013 at 4:15 | comment | added | James Propp | I just noticed yet another blemish in the original post: knowing that every product of a multiset of $a$-generators (resp. $b$-generators) has a quasi-inverse doesn't immediately imply (does it?) that every element of the semigroup has a quasi-inverse. But it certainly would be nice if every element did, i.e., if the semigroup were regular, as in the title. Like Benjamin, I suspect that this won't follow in the absence of further properties satisfied by the semigroup. Is there some weakened abelian property that implies that a product of two quasi-invertible elements is quasi-invertible? | |
| Dec 2, 2013 at 3:44 | comment | added | Benjamin Steinberg | I am pretty sure one can write down a finite semigroup generated by elements $a,a',b,b',z$ such that $a,a'$ commute, $b,b'$ commute, $a,b$ are inverses, $a',b'$ are inverses and $z$ commutes with everybody and is idempotent such that $aa'$ is not regular. I'll try to do it tomorrow when I am less sleepy. I think thought something along the following lines work. Take the semigroup with presentation $\langle a,b,a',b',z\mid z=0,aa'=a'a,bb'=b'b,aba=a,bab=b,a^2=b^2=b'a=ab'=a'b=ba'=0\rangle$ where $z=0$ is short for saying that $z$ is a multiplicative zero. | |
| Dec 2, 2013 at 3:17 | history | edited | James Propp | CC BY-SA 3.0 |
I clarified the connection (or lack thereof) with pre-existing notions.
|
| Dec 2, 2013 at 3:02 | history | edited | James Propp | CC BY-SA 3.0 |
I inserted a line break for readability.
|
| Dec 1, 2013 at 22:36 | history | edited | James Propp | CC BY-SA 3.0 |
I removed $U$ from the statement of the problem, with a bracketed reference to the change so that Boris Novikov's query would still be intelligible.
|
| Dec 1, 2013 at 22:27 | comment | added | James Propp | I was going to write "Yes, $U^2=e$", but then I realized that in the applications I'm interested in, $U$ isn't even an element of the semigroup, but is in a larger semigroup. So I will update the statement of the question to fix this. | |
| Dec 1, 2013 at 16:21 | comment | added | Sam Hopkins | For those of us who didn't know what is meant by a "regular semigroup", I'll put this link to wikipedia here: en.wikipedia.org/wiki/Regular_semigroup | |
| Dec 1, 2013 at 16:02 | history | asked | James Propp | CC BY-SA 3.0 |