This question on MathOverflow: http://mathoverflow.net/questions/179390/standard-name-for-a-monoid-semigroup-with-ab-a-b?noredirect=1#comment449777_179390
lead me to the definition of a partially ordered monoid, or pomonoid: http://books.google.com/books?id=ZO5Z-zZijDgC&pg=PA248&lpg=PA248&dq=pomonoid+definition&source=bl&ots=lX2PietcDd&sig=k79BcAh0s5Y8OGC12Kclmn4Tkgw&hl=en&sa=X&ei=1Mr8U6HGKYu6ogTL3oGYAQ&ved=0CCYQ6AEwATgK#v=onepage&q=pomonoid%20definition&f=false
Pomonoid: if x <= y, then zx <= zy for all x,y,z in X. Integral Pomonoid if x <= 1 for all x in X.
Lemma: If you have an Integral Pomonoid, then xy <= x. yx <= x Proof: x <= 1, so, and by definition: yx <= y. likewise for xy <= x.
-
Normal addition on any submonoid of the reals, is clearly a pomonoid.
-
Multiplication, on any submonoid of nonnegative reals is a pomonoid (nonnegativity is needed).
-
logical-and on the set 0, 1 (which is really an example of the next case, the min-pomonoid).
-
xy = min(x, y). 1 = infinity (Integral pomonoid). Proof: given x <= y, Look at zx and zy. There are three cases: z <= x. x < z <= y. y < z. If y < z, then zx = x and zy = y, so zx <= zy. if x < z <= y, then zx = x and zy = z. so zx < zy if z <= x, then zx = z, zy = z, and zx = zy. 1 is clearly >= all elements, so this is an integral pomonoid.
-
xy = max(x, y). 1 = -infinity Proof: given x <= y. Look at zx and zy. There are three cases: z <= x. x < z <= y. y < z. If y < z, then zx = z and zy = z, so zx = zy. if x < z <= y, then zx = z and zy = y. so zx <= zy if z <= x, then zx = x, zy = y, and zx <= zy. Note that 1 <= all elements, so this implies xy >= x, y (by the same proof for Integral Pomonoid).
-
harmonic sum: ab = ab/(a + b) = 1(1/a + 1/b) where a, b are non-negative reals. 1 is infinity. Proof: assume x <= y. look at d = xz/(x + z) - yz/(y + z). We want to see that d <= 0. d = z(x(y + z) - y(x + z))/((x+z)(y+z)) = z^2(x - y)/((x+z)(y+z)) <= 0, due to x, y, z >= 0,and x <= y. 1 (infinity) is clearly >= all elements, so this is an integral pomonoid.
It appears, though I did not yet do the proof (I checked a few examples, and the proof should be easy), that harmonic sum and max form a Ring:
class HarmMax extends Ring[NonNegativeReal] {
type NNR = NonNegativeReal
def plus(a: NNR, b: NNR) = max(a, b)
def times(a: NNR, b: NNR) = harmonicSum(a, b)
def zero = 0 // numeric zero
def one = infinity
}The Harmmax ring seems to be in play with hyperloglog. Though, it does not appear (except perhaps in the proof in a subtle way) that distributive nature of the ring is used. Sketches (such as Bloomfilter, CMS, Hyperloglog use two monoids, but it is not clear they need them to be related in a ring structure).