In an applied research problem I am currently working on, I am using non-commutative semiring convolution to formulate some interesting types of calculations on images and solid objects. For discrete groups, this is pretty easy to set up. Given a semiring, $(S, \oplus, \odot)$, and a discrete group $G$, define the semialgebra $S[G]$ as the collection of maps $S^G$ equipped with the bilinear operator $\star : S[G] \times S[G] \to S[G]$ such that for all $f, h \in S[G]$:

$(f \star h)(x) = \bigoplus \limits_{y \in G} f(y) \odot h(y^{-1}x)$

This works well, and is consistent with the usual definition of a group algebra when $S$ is a ring. However, in almost all of the interesting situations I can think of, I would like to take $G$ to be a Lie group. To make this happen, it seems that the right thing to do should be to define some kind of 'semiring valued Haar measure', $\mu : 2^G \to S$ which would allow one to compute $S$-valued integrals over $G$. Assuming this works just like it ought to in fields of characteristic 0, then convolution becomes some $S$-valued integral over $G$ like the following thing:

$(f \star h)(x) = \bigoplus \limits_{y \in G} f(y) \odot g(y^{-1}x) \odot d \mu(y)$

Where the symbol $\bigoplus$ means something like a 'semiring' Lebesgue integral over $G$. Unfortunately this definition is not very robust. One can easily pick plausible values of $S, G, \mu$ which catastrophically fail. For instance, if $S = \mathbb{Z} / n \mathbb{Z}$, then it seems to me that the convolution integral is divergent for any function with measurable support!

However, all is not lost. I can think of a few easy cases where one can construct a measure which is convergent and gives 'reasonable' results (and by reasonable, I mean that they are intuitively similar to the results one would get in the case of a discrete group). Consider, for example, the case where $S$ is the idempotent boolean semifield, $B = ( \mathbf{2}, OR, AND )$. Then take:

$\mu(\emptyset) = 0$

$\mu(S \neq \emptyset) = 1$

Now the elements $f, g \in B^G$ can be identified with subsets $X_f, X_g \subseteq G$, and moreover the convolution on $G$ over $B$ gives rise to a so-called generalized Minkowski product:

$f \star g \cong X_f \oplus X_g = \bigcup \limits_{x \in X_f} x X_g$

Which is indeed a useful calculation! Similarly, one can define a measure like this over the $(max, +)$ semiring via another ad-hoc construction. This begs the question: when does this convolution actually work? More specifically, what are the conditions on $S, G, \mu$ such that we can guarantee that convolution is convergent?

(Note: I am probably not being as careful as I should be with definitions. It is probably a good idea to restrict the elements of $S[G]$ to 'Haar-like' measurable functions, but I really don't have a good grasp of what this should mean until I know what the proper conditions on $\mu$ should be...)

  • 1
    $\begingroup$ If you write down all the axioms of measure theory the only one that doesn't make sense over a topological semiring is positivity. You can still make sense out of a G invariance. In the real case you still have essentially unique "signed Haar measure" anyway. The multiplicative structure is only relevant to the convergence of your convolutions and is subtle even over ${\mathbb R}$ (you can't convolve two $L^\infty$ functions on a noncompact group for instance.) You want a condition on $\mu$, but to ensure what? $\endgroup$ Mar 25 '10 at 7:58
  • $\begingroup$ Maybe I should clarify my question. If you know what kind of functions you want to convolve, then you can start studying what measures you should allow. If you know what measures you want, then you can study what kind of functions you can convolve. If you have some application in mind, then maybe it suggests certain types of functions or measures. However, like I said, even when ${\mathbb R}$ and $\mu$ is Lebesgue measure, you can't convollute any two functions you want. So, what type of functions would you like to convolve? $\endgroup$ Mar 28 '10 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.