The tag has no wiki summary.

learn more… | top users | synonyms (1)

24
votes
5answers
2k views

How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each be ...
24
votes
3answers
618 views

What is the probability two random maps on n symbols commute?

It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
19
votes
2answers
591 views

Mapping from a finite index subgroup onto the whole group

Dear All, here is the question: Does there exist a finitely generated group $G$ with a proper subgroup $H$ of finite index, and an (onto) homomorphism $\phi:G\to G$ such that $\phi(H)=G$? My guess ...
14
votes
12answers
2k views

Why semigroups could be important?

There is known a lot about the use of groups -- they just really appear a lot, and appear naturally. Is there any known nice use of semigroups in Maths to sort of prove they are indeed important in ...
12
votes
2answers
803 views

Economical hard word problem

Can anyone give me an example of a very simple word problem, where by "simple" I mean that it has very few generators and relations, that is nevertheless insoluble. To make the question easier, I am ...
12
votes
1answer
1k views

Do these conditions on a semigroup define a group?

As is well known, if $S$ is a semigroup in which the equations $a=bx$ and $a=yb$ have solutions for all $a$ and $b$, then $S$ is a group. This question arose when someone misunderstood the conditions ...
11
votes
1answer
372 views

Automorphisms of $P(\Bbb N)$

I believe I've proved that the power semigroup of non-negative integers with addition has a trivial automorphism group. The proof is a bit long, completely elementary and rather unremarkable (as the ...
9
votes
3answers
477 views

The concept “conjugate class” in monoids.

Is there any concept in monoids that is similar to the concept "conjugate class" in groups? For example, are there any such similar concept in symmetric inverse monoids? Thank you very much.
9
votes
5answers
625 views

References/literature for pushouts in category of commutative monoids? [ed. - amalgams]

This is more of a request for pointers to relevant literature than a question per se. I am, erm, looking at a paper which uses a kind of iterated pushout construction to obtain a commutative monoid ...
9
votes
3answers
207 views

Does the generator of a 1-parameter group of Banach space isometries know which elements are entire?

Let $X$ be a complex Banach space. Let $(\sigma_t)_{t \in \mathbb{R}}$ be a 1-parameter group of linear isometries of $X$ which is strongly continuous i.e. $t \mapsto \sigma_t(x)$ is continuous for ...
8
votes
3answers
582 views

What is the smallest variety of algebras containing all fields?

A field is a ring whose nonzero elements form a commutative group under multiplication. A field is also a commutative inverse semigroup with respect to multiplication. The unique multiplicative ...
8
votes
1answer
441 views

Magma “actions” (or alternatively, “What is the Yoneda lemma for magmas?”)

Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all ...
7
votes
2answers
296 views

Is there a general result that theorems about finite structures proved in ZFC can be proved in ZF?

The title question is too vague so let me be specific. Much of modern finite semigroup theory uses profinite semigroups and properties of profinite semigroups that depend on the existence of prime ...
7
votes
5answers
796 views

Examples of left reversible semigroups

I am looking for concrete examples of cancellative, left reversible semigroups. Left reversible semigroups are also called "Ore semigroups". See this wikipedia page for the definition of a left ...
7
votes
1answer
639 views

How is called a semigroup…

Does anyone know, how is called a semigroup in which every equation $ax=b$ has only a finite set (maybe empty) of solutions?
7
votes
1answer
322 views

About the convergence rate for an approximation to the heat kernel

Let $G(t,x)$ be the heat kernel $$ G(t,x)=\frac{1}{\sqrt{2\pi t}}e^{-\frac{x^2}{2t}}, \quad t>0, \:x\in\mathbb{R}. $$ Here is one approximation to $G(t,x)$: $$ G_\epsilon(t,x)=e^{-t/\epsilon} ...
6
votes
2answers
301 views

Wants: Polynomial Time Algorithm for Decomposing a Multiset of Rationals into Two Additive Subsets.

First, allow me to say that this problem was posed to me by a professor in the department. It is related to his research in a way that I do not know. However, since I couldn't come up with anything ...
6
votes
3answers
294 views

Haar Measure on Locally Compact Semigroups

I'm reading on Haar measure and we know that every locally compact group admits a Haar measure, is the same true for semigroups? if not, is there a class of semigroups that admits a Haar measure? ...
6
votes
1answer
190 views

Positive cone of a subgroup of Z^n

This question sounds like it should be very well known, but for some reason I failed to find a decent answer anywhere. Let $G\subset\mathbb{Z}^n$ be a subgroup, and $G_+=G\cap\mathbb{Z}_{\ge0}^n$ be a ...
6
votes
1answer
190 views

Strongly continuous semigroups that cannot be contractions

Let $X$ be a Banach space, and $(P_t)_{t \ge 0}$ a strongly continuous semigroup of bounded operators on $X$. Using the uniform boundedness principle, it's simple to prove that there are constants ...
6
votes
2answers
281 views

need references regarding the elementary theory of free semigroup and free abelian groups

Recently, I read that two free abelian groups $S$ and $T$ have the same elementary theory if and only if rank$S$=rank$T$. Does anyone have a reference with a proof of this? Also, what is known about ...
6
votes
2answers
352 views

Is the class of inverse semigroups globally determined?

This question is a follow-up to this one I asked on math.stackexchange. I've decided to ask here because I believe this is a research-level question. I'm sorry if I'm wrong -- I'm not a researcher ...
5
votes
2answers
221 views

For a monoid with zero $M$, how many additive operations on $M$ can there be making $M$ a ring?

Let $(M,\times)$ be a monoid with zero. Let $\Sigma(M,\times)$ be the set of binary operations $+$ on $M$ such that $(M,+,\times)$ is a ring. Let $\sim$ be an equivalence relation on ...
5
votes
3answers
559 views

Reference on Semigroup Theory and Parabolics PDE'S

Recently started to study Semigroup Theory. My background is equivalent to the first three chapters of the Jack Hale's book, Asymptotic Behavior of Dissipative Systems. Looking for a reference to an ...
5
votes
3answers
170 views

Locally finite varieties which are not finitely generated

Let $\Sigma$ be a signature consisting of operations with finite arity. Let $\mathcal{V}$ be a variety of algebras for this signature. Further suppose that $\mathcal{V}$ is locally finite i.e. every ...
5
votes
2answers
474 views

Do all finitely generated nilpotent semigroups have polynomial growth?

The notion of nilpotency passes nicely from groups to semigroups. Define $q_1(x,y)=xy$ and $$q_{i+1}(x,y,z_1,\cdots,z_i)=q_i(x,y,z_1,\cdots,z_{i-1})z_iq_i(y,x,z_1,\cdots,z_{i-1})$$ inductively for all ...
5
votes
1answer
363 views

Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite $F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that, for all but finitely many $s\in S$, $$ ...
5
votes
1answer
414 views

an example of a semigroup with solvable word problem but unsolvable power problem

We say that a semigroup $S$ has solvable power problem if there is an algorithm that takes as input an element $s \in S$ and decides whether or not there exist $m,n \in \mathbb{N}$ with $m \neq n$ and ...
5
votes
1answer
118 views

A question about uniformly bounded semigroups

Let $A$ be an unbounded linear operator of domain $D(A)$ defined on a Banach space $X$. Suppose that $A$ generates a $C_0$-semigroup $T(t)$ which is uniformly bounded. I would like to know if there ...
5
votes
1answer
322 views

Representations of products of groups (and monoids)

I have very little knowledge of representation theory, but the following has come up in my summer undergrad research project (relates to conformal field theory and geometric function theory). Suppose ...
5
votes
1answer
145 views

Is irreducibility sufficient for uniqueness of invariant distribution for a Feller Semigroup?

Let $(T_t)$ be a strongly continuous semigroup of positive operators on $C(K)$, where $K$ is a compact space. Assume also that $T_t1 =1 $ for every $t\geq 0$. (This is also called a Feller Semigroup.) ...
5
votes
2answers
300 views

Existence of a possible counterexample in automaton semigroups

In an attempt to resolve a question posed by Cain in his paper on Automaton Semigroups (open problem 6.12), I would like to know if there exists a finite semigroup $S$ satisfying the following ...
5
votes
1answer
453 views

Percolation in Cayley graphs of semigroups.

Percolation in Cayley graphs of groups are studied by many researchers. There are also the concept Cayley graphs for semigroups. Are there any research about percolation in Cayley graphs for ...
4
votes
2answers
363 views

examples of finitely generated semigroups that are not residually finite

Does anybody know of any finitely generated semigroups that are not residually finite and whose group of units (if there is an identity) is trivial? Basically, I'm looking for finitely generated ...
4
votes
2answers
133 views

Lecture notes on semi group theory for linear evolution equations

I am reading (or trying to read :)) One parameter semigroups for Linear Evolution equations by Klaus-Jochen Engel and Rainer Nagel. I was wondering if someone was aware of a good set of lecture notes ...
4
votes
1answer
173 views

Is the monoid of taking iterated images and inverse images freely generated by the image and inverse image operation?

Let $\mathcal{F}$ denote the class of all functions. Let $U,L:\mathcal{F}\rightarrow\mathcal{F}$ denote the mappings where if $f:X\rightarrow Y$, then $U(f):P(X)\rightarrow P(Y),L(f):P(Y)\rightarrow ...
4
votes
2answers
344 views

Membership problem in monoids

What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ ...
4
votes
1answer
243 views

Reference for subsemigroups of $\mathbb{N}^n$

A well known result about the natural numbers $\mathbb{N}$ says that for any finite subset $A \subset \mathbb{N}$ there exists $R \ge 0$ such that if $n$ is in the subgroup of $\mathbb{Z}$ generated ...
4
votes
2answers
524 views

Which semigroups can be linearly ordered?

As usual I consider a semigroup to be a structure $(A, +)$ such that $+$ is an associative binary function over the set $A$. The notion of linearly-ordered semigroup corresponds to structures of the ...
4
votes
1answer
133 views

Progress on group languages characterizations

Def. A group language is a recognizable language whose syntactic monoid is a group. q1. Is it known a "nice" combinatorial characterization of group languages ? q1.1. If no, is it well understood ...
4
votes
2answers
443 views

Normality of an affine semigroup

An affine monoid is a finitely generated commutative submonoid of $\mathbb Z^k$ for some positive integer k. Let S be an affine monoid and let G(S) be the group generated by S. We say the monoid S is ...
4
votes
1answer
263 views

One-parameter semigroups of bimodules

Suppose M is a von Neumann algebra. Consider a monoidal category of bimodules over M. Here a bimodule is a Hilbert space with two normal representations of M. The monoidal structure is given by ...
4
votes
2answers
112 views

What's the current state of one-rule semi-Thue system termination problem?

What's the current state of one-rule semi-Thue system termination problem? Search produces a lot of references, but it's hard to find out if decidability of this problem has been proven or not.
4
votes
2answers
158 views

Embedding a linearly ordered free monoid into a linearly ordered group

A linearly ordered (shortly, l.o.) monoid is a triple $\mathbb M = (M, \cdot, \le)$ for which $(M, \cdot)$ is a (multiplicatively written) monoid and $\le$ is a total order on $M$ such that $xy < ...
4
votes
1answer
138 views

Generator of a $C_0$-semigroup restricted to a subspace

Suppose we have a decreasing filtration of Banach spaces $(E_t)\_{t\geq0}$, inclusions $V_{s+t,t}:E_{s+t}\to E_t$ and projections $P_{t,s+t}:E_t\to E_{s+t}$ such that $P_{t,s+t}V_{s+t,t}=I_{E_{s+t}}$. ...
4
votes
1answer
209 views

Proving that a semigroup is regular

In a number of diverse situations of interest to me (mostly associated with something called the abelian sandpile model), one can define a nonabelian semigroup generated by commuting elements ...
4
votes
1answer
252 views

semigroups acting as continuous functions on regular rooted trees

Let $T$ be a regular rooted tree. Make $T$ into a metric space by making each edge isometric to the unit interval. What is known about what semigroups can act as continuous functions on $T$ such ...
4
votes
0answers
164 views

Computing the pro-solvable closure of a finitely generated subgroup of a free group

The pro-solvable topology on a group $G$ is the unique group topology such that the set of normal subgroups $N\lhd G$ with $G/N$ a finite solvable group is a fundamental system of neighborhoods of the ...
4
votes
0answers
83 views

How much do idempotent ultrafilters generate in terms of semigroups?

It is known that the set of ultrafilters on, say, the natural numbers $\mathbb{N}$, can naturally be endowed with the structure of a compact topological left semigroup (which fails to be anything ...
4
votes
0answers
214 views

What is the pro-algebraic completion of the free semigroup on one generator?

This question is motivated by an attempt to understand what is going on in Tom's post from a certain point of view. Let $\mathbb N^+$ be the free semigroup on one generator (so the positive natural ...