Monoidal sparks

Posted on October 1, 2018 by Brent

While at ICFP in St. Louis this past week, I discovered an interesting construction on monoids that no one I talked to (including Kenny Foner and Edward Kmett) seemed to have heard of or thought about before. In this post I’ll present the abstract construction itself, and in another post I’ll explain the particular context in which I first came up with it. (Normally I would put the examples first, before explaining the idea in general; but I only know of one example so far, and I’m curious to see if anyone will come up with more. I don’t want to bias people’s thinking too much with my one example!)

The bigger context here is thinking about different ways of putting a monoid structure on a product type A \times B, assuming A and B are themselves monoids. Previously I knew of two ways to do this. The obvious way is to just have the two sides operate in parallel, without interacting at all: (a_1,b_1) \diamond (a_2,b_2) = (a_1 \diamond a_2, b_1 \diamond b_2) and so on. Alternatively, if A acts on B, we can form the semidirect product.

But here is a third way. Suppose (A, \varepsilon_A, \diamond) is a monoid, and (B, \varepsilon_B, \oplus) is a commutative monoid. To connect them, we also suppose there is another binary operation - \cdot - : A \to A \to B, which I will pronounce “spark”. The way I like to think of it is that two values of type A, in addition to combining to produce another A via the monoid operation, also produce a “spark” of type B. That is, values of type B somehow capture information about the interaction between pairs of A values.

Sparking needs to interact sensibly with the monoid structures on A and B: in particular, fixing either argument must result in a monoid homomorphism from A to B. That is, for any choice of a \in A, we have a \cdot \varepsilon_A = \varepsilon_B (i.e. \varepsilon_A is boring and can never produce a nontrivial spark with anything else), and a \cdot (a_1 \diamond a_2) = (a \cdot a_1) \oplus (a \cdot a_2) (i.e. sparking commutes with the monoid operations). Similar laws should hold if we fix the second argument of - \cdot - instead of the first.

Given all of this, we can now define a monoid on A \times B as follows:

(a_1, b_1) \otimes (a_2, b_2) = (a_1 \diamond a_2, b_1 \oplus b_2 \oplus (a_1 \cdot a_2))

That is, we combine the A values normally, and then we combine the B values together with the “spark” of type B produced by the two A values.

Let’s see that this does indeed define a valid monoid:

  • The identity is (\varepsilon_A, \varepsilon_B), since

    (\varepsilon_A, \varepsilon_B) \otimes (a,b) = (\varepsilon_A \diamond a, \varepsilon_B \oplus b \oplus (\varepsilon_A \cdot a)) = (a, b \oplus \varepsilon_B) = (a,b)

    Notice how we used the identity laws for A (once) and B (twice), as well as the law that says \varepsilon_A \cdot a = \varepsilon_B. The proof that (\varepsilon_A, \varepsilon_B) is a right identity for \otimes is similar.

  • To see that the combining operation is associative, we can reason as follows:

    \begin{array}{rcl} & & ((a_1,b_1) \otimes (a_2,b_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1 \diamond a_2, b_1 \oplus b_2 \oplus (a_1 \cdot a_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus (a_1 \cdot a_2) \oplus b_3 \oplus ((a_1 \diamond a_2) \cdot a_3)) \\[0.5em] & = & \qquad \text{\{\begin{math}- \cdot a_3\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}

    and

    \begin{array}{rcl} & & (a_1,b_1) \otimes ((a_2,b_2) \otimes (a_3,b_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1,b_1) \otimes (a_2 \diamond a_3, b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus (b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \oplus (a_1 \cdot (a_2 \diamond a_3))) \\[0.5em] & = & \qquad \text{\{\begin{math}a_1 \cdot -\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}

    In a formal proof one would have to also explicitly note uses of associativity of \diamond and \oplus but I didn’t want to be that pedantic here.

In addition, if A is a commutative monoid and the spark operation - \cdot - commutes, then the resulting monoid (A \times B, \otimes) will be commutative as well.

The proof of associativity gives us a bit of insight into what is going on here. Notice that when reducing (a_1,b_1) \otimes (a_2,b_2) \otimes (a_3,b_3), we end up with all possible sparks between pairs of a’s, i.e. (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3), and one can prove that this holds more generally. In particular, if we start with a list of A values:

[a_1, a_2, \dots, a_n],

then inject them all into A \times B by pairing them with \varepsilon_B:

[(a_1, \varepsilon_B), (a_2, \varepsilon_B), \dots, (a_n, \varepsilon_B)],

and finally fold this list with \otimes, the second element of the resulting pair is

\displaystyle \bigoplus_{i \neq j} (a_i \cdot a_j),

that is, the combination (via the monoid on B) of the sparks between all possible pairings of the a_i. Of course there are O(n^2) such pairings: the point is that whereas computing this via a straightforward fold over the list may well take O(n^2) time, by using a balanced fold (i.e. splitting the list in half recursively and then combining from the leaves up) it may be possible to compute it in O(n \log n) time instead (at least, this is the case for the example I have in mind!).

Please leave a comment if you can you think of any instances of this pattern, or if you have seen this pattern discussed elsewhere. In a future post I will write about the instance I had in mind when coming up with this generalized formulation.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in math and tagged , , , , . Bookmark the permalink.

27 Responses to Monoidal sparks

  1. Naren Sundar says:
    October 1, 2018 at 1:22 pm

    Suppose U is some set. Let op1 be intersection, op2 be union on this set. Let the spark be de-morgan’s law, I.e, spark(a,b) = ~(a \cap b) = ~a \cup ~b. Then, the spark respects the two homomorphism requirement.

    Reply
    • Brent says:
      October 1, 2018 at 11:12 pm

      Yes, I guess it does! It doesn’t seem all that useful to me (though I would be happy to be wrong). If we start with a bunch of sets this would allow you to compute their intersection along with the union of their complements—which is just the complement of their intersection. So rather than using this monoid you should just compute their intersection by itself, and then complement it at the end.

      Reply
  2. Justin says:
    October 1, 2018 at 11:43 pm

    Neat operation! It reminds me a bit of a non-standard monoid on the real numbers:

    op(x, y) = c * x * y + x + y

    where c is any constant. I think this can be sort of interpreted as a spark, taking the product of two monoids on the reals—one with a multiplication operation and the other with an additive operation. I think I saw this operation in the context of composition theorems for certain statistical divergences, can send more information if you’re curious.

    Reply
    • Brent says:
      October 2, 2018 at 7:47 am

      Oh, very interesting monoid! I can’t remember if I’ve seen that before. The way you end up with sums of all possible products does seem similar to the way sparks combine. However, I can’t figure out how to get the laws to work out if we try taking this operation as the spark operation. It seems most obvious to try to make it a monoid homomorphism from + to itself, but this doesn’t work, since op(x, y + z) = cxy + cxz + x + y + z, but op(x,y) + op(x,z) = cxy + cxz + 2x + y + z — close, but off by x.

      Reply
      • Gesh says:
        October 2, 2018 at 4:25 pm

        I’ve seen a variant of this operation before as the “multiplicative group law” (see https://en.wikipedia.org/wiki/Formal_group_law), but only for $c=1$.
        Indeed, associativity fails here, as you verified.
        The special case can be easily shown to be a monoid isomorphic to the multiplication monoid on whatever ring you claim the original monoid to be grounded, via the identity $xy+x+y=(x+1)(y+1)-1$.
        This “sparky” product does tickle my brain, but all I have are vague associations at the moment. Will see if I can come up with something before your next post

        Reply
  3. sn0wleopard says:
    October 2, 2018 at 5:09 am

    Hey Brent! It’s a pity I couldn’t come to ICFP this year, but if I were there, I would give you an example of this construction! But, perhaps, this is exactly the example you have in mind? ;-) In this case I won’t spoil it!

    By the way, I like your generalisation via sparks a lot — it makes a lot of sense to me after having looked at my example from various angles. (Also, in some of the recent work I did on my example, a spark doesn’t come alone — it brings a whole family of sparks with!)

    Reply
    • sn0wleopard says:
      October 2, 2018 at 5:09 am

      …it!)

      Reply
    • Brent says:
      October 2, 2018 at 7:49 am

      Hi Andrey! Yeah, too bad, it would have been fun to see you (though I did very much enjoy SPJ’s presentation of your paper). The part about “bringing a whole family of sparks” makes me think that your example is NOT the same as the example I have in mind…

      Reply
      • sn0wleopard says:
        October 2, 2018 at 8:11 am

        So, in the published version of my example we have A = X and B = X*X. But now consider adding a set of labels L: A = X and B = X*L*X. Now, there is a spark associated with every element in L!

        Sorry to speak in riddles :-) To make it more concrete, here is the family of monoids generated by the sparks: https://github.com/snowleopard/alga/blob/master/src/Algebra/Graph/Labelled.hs#L112

        Reply
        • Brent says:
          October 2, 2018 at 8:25 am

          Ah, I think I see, very interesting!

          Reply
        • Brent says:
          October 2, 2018 at 9:10 am

          Upon reflection, the labels seem not to be really necessary here (although they are interesting). Even without the labels, what you have is a sort of free version of what I’ve described. That is, let A be the free commutative idempotent monoid on an underlying set U, and B is the free commutative idempotent monoid on ordered pairs UxU, then the spark operation is the operation induced by pairing a1 * a2 = (a1,a2); that is, it takes two subsets of U and forms the Cartesian product. I think what I’ve described is slightly more general since it doesn’t require anything to be idempotent (in the example I had in mind, neither monoid is idempotent).

          Reply
          • sn0wleopard says:
            October 2, 2018 at 10:43 am

            Yes, I think you are right: the case `Graph () a` may be interesting in its own right :)

            Good point about idempotence. In my formulation I require it because of the desire for some compatibility between the spark-based monoid (I’m going to denote it with *) and the direct monoid product (I’ll denote it with +). More specifically, I’d like to have distributivity:

            x * (y + z) = x * y + x * z

            But this forces idempotence! Indeed, let’s take y = z = (1A, 1B). Then:

            x
            = x * (1A, 1B)
            = x * ((1A, 1B) + (1A, 1B))
            = x * (1A, 1B) + x * (1A, 1B)
            = x + x

            So, if we’d like the spark monoid to interact nicely with the direct monoid, we need to require idempotence (on both of the underlying monoids over A and B).

            But if we are only interested in the spark monoid itself, then we can drop the idempotence requirement and then `Graph () a` may indeed be the free version of your construction.

            > in the example I had in mind, neither monoid is idempotent

            Aha, so your example is not the algebra of graphs — cool! I’m looking forward to reading your next blog post. Oh well, as always :)

  4. Yitz says:
    October 2, 2018 at 2:26 pm

    > The proof that (\varepsilon_A, \varepsilon_B) is a right identity for \otimes is similar.
    What am I missing? Doesn’t that require a \cdot \varepsilon_A = \varepsilon_B which is not one of your laws?

    Reply

  5. Pingback: Counting inversions with monoidal sparks | blog :: Brent -> [String]

  6. L Spice says:
    October 9, 2018 at 10:43 am

    This is very close to the construction of the Heisenberg group, for which $A$ is a symplectic space over an odd-characteristic field $B$, and the ‘spark’ is the symplectic pairing. In the case where $A \cong V \oplus V^*$, where $V$ is a vector space over $B$, with its natural symplectic pairing, one can realise the Heisenberg group as a group of upper unitriangular $(2n + 1)$-square matrices (where $n$ is the dimension of $V$). One can imagine a generalisation of this construction involving a matrix of (commutative, to be safe) monoids $M_{i j}$ and, for each tuple $(i, j, k)$, a ‘spark’ $M_{i j} \otimes M_{j k} \to M_{i k}$.

    Reply
  7. Edward Kmett says:
    October 10, 2018 at 12:09 am

    It is almost like this might be a useful building block for counting the number of inversions in an array or something. ;)

    Reply
  8. Philipp Schuster says:
    October 15, 2018 at 6:21 am

    Perhaps another example: Let A be the two-dimensional vector space over the reals with vector addition and let B be the real numbers with addition. Let “spark” be the dot product. What does your proposed combining operation mean geometrically?

    Reply

  9. Pingback: United Monoids | no time

  10. Xplat says:
    December 21, 2018 at 5:48 pm

    When you specialize to B an Abelian group, this is the same as a split central extension.

    Reply

Leave a reply to Brent Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.