<p>A <em>partial semigroup</em> (or PSG) consists of a set $X$ and of a partial composition law $*$ defined over $X$, that is to say:</p>

<p>(1) $x*y$ is not always defined,</p>

<p>(2) if $(x*y)*z$ is defined, so is $x*(y*z)$, and the two values are equal,</p>

<p>(3) if $x*(y*z)$ is defined, so is $(x*y)*z$, and the two values are equal.</p>

<p>Let $\mathbb{R}$ be a ring. We may then define a <em>convolution product</em> over $\mathbb{R}^X$ : given two functions $f,g$, we define a function $f*g$ such that</p>

<blockquote>
  <p>for every $w \in X$, $f*g(w) = \sum_{x,y \in X : x*y = w} f(x) g(y)$.</p>
</blockquote>

<p>By a <em>graded PSG</em>, we mean a pair $(S,r)$ consisting of a PSG $S = (X,*)$ and of a rank function $r : X \rightarrow \mathbb{N}$ such that whenever $x*y$ is defined, $r(x*y) = r(x)+r(y)$. This holds for instance for the <em>interval algebra</em> of an Eulerian poset (see On the Foundations of Combinatorial Theory I. Theory of Moebius Functions, by G.C. Rota).</p>

<p>By analogy with the situation in posets, we may define a 'triangular matrix' $\lambda \in \mathbb{R}^X$ by $\lambda(x) = 1$ for every $x \in X$, and a mapping $\zeta : \mathbb{R}^X \rightarrow \mathbb{R}^X$ by $\zeta(x) = \lambda * x$. It is known that for a partial semigroup obtained from the interval algebra of an Eulerian poset, the function $\lambda$ has an inverse $\mu \in \mathbb{R}^X$ given by $\mu([x,y]) = (-1)^{r(y)-r(x)}$. This suggests a possible extension to certain graded PSGs, which leads me to ask the following.</p>

<p>Question: for a graded PSG, under what conditions does $\lambda$ have an inverse $\mu$? When this holds, is it always true that $\mu(x) = (-1)^{r(x)}$?</p>

<p>(NOTE: I renamed the rank function $r$ instead of $l$ for greater consistency.)</p>

CC BY-SA 3.0
2014-04-08T14:32:52.930Z
Do you have a reference in the literature to partial semigroups? I would suggest brute force enumeration of legal PSG multiplication tables and looking for a pattern.
Chad Brewbaker
CC BY-SA 3.0
2014-04-08T19:11:26.670Z
I guess $0$ is not in the range of the rank $l$ ? Otherwise $l=0$ works for all PSG.
Denis
CC BY-SA 3.0
2014-04-08T19:14:49.140Z
Also you probably mean $\lambda \in\mathbb R^X$, and $\zeta$ instead of $\lambda$ as the inverse of $\mu$.
Denis
CC BY-SA 3.0
2014-04-08T21:03:32.593Z
@ChadBrewbaker: Google points to a ME entry with many references (http://mathoverflow.net/questions/123614/on-the-notion-of-partial-semigroup). As for the search of patterns, referring to Russian bell ringing I'd prefer 'trezvon' to 'perebor' (triple peal to brute force). Make of that what you will..
NisaiVloot
CC BY-SA 3.0
2014-04-08T21:05:44.577Z
@Denis: Actually my question assumes a fixed pair $(S,l)$ where $S$ is a PSG and $l$ a rank function. Its range may contain 0 e.g. if $S$ is a group. I have adressed your other comments, thanks.
NisaiVloot
CC BY-SA 3.0
2014-04-08T22:04:55.983Z
1) If $0$ is allowed to be in the range of $l$, then every PSG is graded, because $l(x) = 0\ \forall x$ does the job. However your definition says $\ell:X \rightarrow \mathbb{N}$ and usually $0 \not \in \mathbb{N}$, right? 2) The convolution $f*g$ seems to be defined only for those $w$ for which there exist $x, y \in X$ such that $x*y = w$. 3) When you say "inverse of $\lambda$", I assume you mean "as an element of the semigroup ($R^X$, $*$)"?
Sasho Nikolov
CC BY-SA 3.0
2014-04-08T22:15:07.210Z
1) and 3): correct, 2): an empty sum evaluates to 0 by convention.
NisaiVloot
CC BY-SA 3.0
2014-04-09T12:16:28.257Z
ah ok 3) is really useful, you should detail it a little bit in the question. It's not even trivial what is the neutral in this semigroup. It would have to be $n:e\mapsto e$ and undefined elsewhere, but for this you need a neutral $e\in X$, which is not defined for now.
Denis
CC BY-SA 3.0
2014-04-09T13:18:39.663Z
Fair point, it seems that the SG $(\mathbb{R}^X,*)$ has a unit only if the PSG $(X,*)$ does. The unit would be the 'delta' function defined by $\delta(e) = 1, \delta(x) = 0$ for $x \neq e$.
NisaiVloot
<order-theory>
Convolution products in partial semigroups
NisaiVloot
# Convolution products in partial semigroups

(Asked by: username_0 on 2014-04-08)

A *partial semigroup* (or PSG) consists of a set $X$ and of a partial composition law $\*$ defined over $X$, that is to say:

(1) $x\*y$ is not always defined,

(2) if $(x\*y)\*z$ is defined, so is $x\*(y\*z)$, and the two values are equal,

(3) if $x\*(y\*z)$ is defined, so is $(x\*y)\*z$, and the two values are equal.

Let $\mathbb{R}$ be a ring. We may then define a *convolution product* over $\mathbb{R}^X$ : given two functions $f,g$, we define a function $f\*g$ such that

> for every $w \in X$, $f\*g(w) = \sum\_{x,y \in X : x\*y = w} f(x) g(y)$.

By a *graded PSG*, we mean a pair $(S,r)$ consisting of a PSG $S = (X,\*)$ and of a rank function $r : X \rightarrow \mathbb{N}$ such that whenever $x\*y$ is defined, $r(x\*y) = r(x)+r(y)$. This holds for instance for the *interval algebra* of an Eulerian poset (see On the Foundations of Combinatorial Theory I. Theory of Moebius Functions, by G.C. Rota).

By analogy with the situation in posets, we may define a 'triangular matrix' $\lambda \in \mathbb{R}^X$ by $\lambda(x) = 1$ for every $x \in X$, and a mapping $\zeta : \mathbb{R}^X \rightarrow \mathbb{R}^X$ by $\zeta(x) = \lambda \* x$. It is known that for a partial semigroup obtained from the interval algebra of an Eulerian poset, the function $\lambda$ has an inverse $\mu \in \mathbb{R}^X$ given by $\mu([x,y]) = (-1)^{r(y)-r(x)}$. This suggests a possible extension to certain graded PSGs, which leads me to ask the following.

Question: for a graded PSG, under what conditions does $\lambda$ have an inverse $\mu$? When this holds, is it always true that $\mu(x) = (-1)^{r(x)}$?

(NOTE: I renamed the rank function $r$ instead of $l$ for greater consistency.)

**Tags:** order-theory
> **Comments:**
> **username_1**: Do you have a reference in the literature to partial semigroups? I would suggest brute force enumeration of legal PSG multiplication tables and looking for a pattern.  
> **username_2**: I guess $0$ is not in the range of the rank $l$ ? Otherwise $l=0$ works for all PSG.  
> **username_2**: Also you probably mean $\lambda \in\mathbb R^X$, and $\zeta$ instead of $\lambda$ as the inverse of $\mu$.  
> **username_0**: @ChadBrewbaker: Google points to a ME entry with many references (http://mathoverflow.net/questions/123614/on-the-notion-of-partial-semigroup). As for the search of patterns, referring to Russian bell ringing I'd prefer 'trezvon' to 'perebor' (triple peal to brute force). Make of that what you will..  
> **username_0**: @Denis: Actually my question assumes a fixed pair $(S,l)$ where $S$ is a PSG and $l$ a rank function. Its range may contain 0 e.g. if $S$ is a group. I have adressed your other comments, thanks.  
> **username_3**: 1) If $0$ is allowed to be in the range of $l$, then every PSG is graded, because $l(x) = 0\ \forall x$ does the job. However your definition says $\ell:X \rightarrow \mathbb{N}$ and usually $0 \not \in \mathbb{N}$, right? 2) The convolution $f*g$ seems to be defined only for those $w$ for which there exist $x, y \in X$ such that $x*y = w$. 3) When you say "inverse of $\lambda$", I assume you mean "as an element of the semigroup ($R^X$, $*$)"?  
> **username_0**: 1) and 3): correct, 2): an empty sum evaluates to 0 by convention.  
> **username_2**: ah ok 3) is really useful, you should detail it a little bit in the question. It's not even trivial what is the neutral in this semigroup. It would have to be $n:e\mapsto e$ and undefined elsewhere, but for this you need a neutral $e\in X$, which is not defined for now.  
> **username_0**: Fair point, it seems that the SG $(\mathbb{R}^X,*)$ has a unit only if the PSG $(X,*)$ does. The unit would be the 'delta' function defined by $\delta(e) = 1, \delta(x) = 0$ for $x \neq e$.  

---

## 0 answers

