Why semigroups could be important? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T18:53:20Z http://mathoverflow.net/feeds/question/55885 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55885/why-semigroups-could-be-important Why semigroups could be important? Victor 2011-02-18T18:09:34Z 2011-02-25T23:42:29Z <p>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 Mathematics? I understand that it is a research question, but may be somebody can hint me the direction to look on so that I would see sensibility of semigroups, if you see what I mean (so some replies like look for wikipedia are not working as they are anti-answers).</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55888#55888 Answer by Gerhard Paseman for Why semigroups could be important? Gerhard Paseman 2011-02-18T18:18:24Z 2011-02-18T18:18:24Z <p>Unary (1-variable) functions mapping a set X to itself under composition is a semigroup. Cayley's Theorem (one of them) says that every semigroup is isomorphic to one of this kind.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2011.02.18</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55892#55892 Answer by mhum for Why semigroups could be important? mhum 2011-02-18T18:49:13Z 2011-02-18T18:49:13Z <p>Semigroups provide a fundamental, algebraic tool in the analysis of regular languages and finite automata. <a href="http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf" rel="nofollow">This book chapter (pdf)</a> by J-E Pin gives a brief overview of this area. </p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55893#55893 Answer by Michal Kotowski for Why semigroups could be important? Michal Kotowski 2011-02-18T19:03:57Z 2011-02-18T19:03:57Z <p>An important application of semigroups and monoids is algebraic theory of formal languages, like regular languages of finite and infinite words or trees (one could argue this is more theoretical computer science than mathematics, but essentialy TCS <em>is</em> mathematics).</p> <p>For example, regular languages can be characterized using finite state automata, but can also be described by homomorphisms into finite monoids. The algebraic approach simplifies many proofs (like determinization of Buchi automata for infinite words or proving that FO = LTL) and gives deeper insight into the structure of languages.</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55896#55896 Answer by Apollo for Why semigroups could be important? Apollo 2011-02-18T19:40:23Z 2011-02-18T19:40:23Z <p>(Commutative) semigroups and their analysis shows up in the theory of misère combinatorial games. The "misère quotient" semigroup construction gives a natural generalization of the normal-play Sprague-Grundy theory to misere play which allows for complete analysis of (many) such games. (See <a href="http://miseregames.org/" rel="nofollow">http://miseregames.org/</a> for various papers and presentations.)</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55897#55897 Answer by Mark Sapir for Why semigroups could be important? Mark Sapir 2011-02-18T19:42:59Z 2011-02-18T19:42:59Z <p>Circuit complexity. See </p> <p>Straubing, Howard, Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1994. </p> <p>If you want a research problem relating circuit complexity with (finite) semigroups, there are many in the book and papers by Straubing and others. See also Eilenberg and Schutzenberger (that is in addition to Pin's book mentioned in another answer) - about connections between finite semigroups and regular languages and automata. </p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55901#55901 Answer by BSteinhurst for Why semigroups could be important? BSteinhurst 2011-02-18T19:51:29Z 2011-02-18T19:51:29Z <p>Semigroups of bounded $L^{2}$ operators are very important in probability. They in fact provide one of the main ways show the very close connection between a self-adjoint operator and a nice' Markov process (nice can be taken to mean strong Markov, cadlag, and quasi-left continuous.) So how does one get this semigroup from a Markov process? If $X_t$ is your process let $\mu_{t}(x,A)$ be measure with mass $\le 1$ with value $P(X_t \in A | X_0=x)$. Then $\int f(y) \mu_t(x,dy) = T_tf(x)$ gives a semigroup of bounded $L^{2}$ operators. </p> <p>Why are such constructions important and natural? If $f$ is your initial distribution of something (heat for example) and $X_t$ is Brownian motion. Then $T_t$ acts by letting the heat distribution $f$ diffuse the way heat should. This then gives a nice way to connect PDE and probability theory. I'd end by offering that semigroups are important, in part, because they do arise is so many places and can bridge between disciplines. There are other reasons as well. </p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55911#55911 Answer by András Bátkai for Why semigroups could be important? András Bátkai 2011-02-18T20:39:51Z 2011-02-18T20:39:51Z <p>Though you say that $C_0$ semigroups are not really semigroups, the structure of compact semitopological semigroups plays an important role in the investigation of their asymptotic behaviour. For example, Glicksberg-DeLeeuw type decompositions or Tauberian theorems are obtained such a way, see Engel-Nagel: One-Parameter semigroups for Linear evolution Equations, Springer, 2000, Chapter V.2.</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55972#55972 Answer by Denis Serre for Why semigroups could be important? Denis Serre 2011-02-19T10:35:36Z 2011-02-19T10:35:36Z <p>Victor, I don't understand your claim that $C^0$-semigroups aren't really semigroups. You are not free to decide for all the mathematical community what is a semigroup (I guess that you are interested only on discrete semigroups, aren't you ?).</p> <p>$C^0$-semigroups are fundamental in PDEs (in probability too as mentioned by Steinhurst). The reason is that a lot of evolution PDEs (basically all parabolic ones, like the heat equation, or Navier-Stokes) can be solved only forward but not backward. In linear PDEs, this is a consequence of the Uniform Boundedness Principle (= Banach-Steinhaus Theorem). There is a nice theory relating operators and semigroups, the former being the generator of the latter. In the linear case, a fundamental result is the Hille-Yosida Theorem. Subsequent tools are Duhamel's principle and Trotter's formula. A part of the theory extends to nonlinear semigroups.</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55996#55996 Answer by weakstar for Why semigroups could be important? weakstar 2011-02-19T17:33:13Z 2011-02-19T17:33:13Z <p>Given a group $G$, the Block Monoid $B(G)$ consists of sequences of elements in $G$ that sum to zero. So for example, an element of $B(\mathbb{Z})$ is $(-2,-3,1,1,3)$. The monoid operation is concatenation, and the empty block is the identity element. </p> <p>Given a Dedekind domain, one can take its ideal class group, and consider the block monoid over that group. Note that in the obvious way, elements of the block monoid can be irreducible or not. One can study irreducible factorization in the Dedekind domain by studying irreducible factorization in the block monoid.</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/56690#56690 Answer by Yemon Choi for Why semigroups could be important? Yemon Choi 2011-02-25T23:42:29Z 2011-02-25T23:42:29Z <p>Am slightly surprised no one has mentioned the Galvin-Glazer proof of Hindman's theorem via the existence of semigroup structure on $\beta{\mathbb N}$, the Stone-Cech compactification of the positive integers (see, for instance, part of this <a href="http://mysite.verizon.net/nhindman/research/jams.pdf" rel="nofollow">note by Hindman</a>.</p> <p>The relevance to the original question is that knowing that `compact right topological semigroups have idempotents'' may sound recondite, but it is just what was needed to answer Galvin's original question about translation-invariant ultrafilters, which was itself motivated by a "concrete" question in additive combinatorics.</p> <p>On a related note, while it is in general not possible to embed a locally compact group as a dense subgroup of something compact (the map from a group to its Bohr compactification need not be injective), you can always embed it densely into various semigroups equipped with topological structure that interacts with the semigroup action: there are various of these, perhaps the most common being the WAP-compactification and the LUC-compactification. Unfortunately this often says more about the complicated behaviour of compact semitopological semigroups (and their one-sided versions) than about anything true for all locally compact groups, but the compactifications are a useful resource in some problems in analysis, and the semigroup structure gives one some extra grip on how points in this compactification behave. (Disclaimer: this is rather off my own fields of core competence.)</p>