tropical arithmetic

Tropical arithmetic replaces addition with minimization and multiplication with addition.

Tropical arithmetic is just like regular arithmetic but with two operations swapped out. Instead of addition you use min or max, and instead of multiplication you use addition. See also Lunar Arithmetic.

tropical_add(a, b) = min(a, b) or max(a, b)
tropical_mul(a, b) = a + b

The notation gives a way to rewrite mathematical expressions programmatically, which are easier for me to manipulate and reason about. Multisets are more natural than sets, counting multiplicities reduces everything to integer arithmetic which is a space I like.

+ 123   × 153
  260      61
  ---     ---
  263     1b4

The positional encoding does not allow for doing this kind of representation as numbers do not carry over. I could write digits beyond 9 as hex: a=10, b=11 .. but the trick of representing arithmetic like that does not work well, for that reason I'll use a linear postfix notation where bags are within brackets for the documentation. The multiset representation makes this natural: b^11 is simply eleven instances of b, requiring no alphabet beyond the token names themselves.

Tropical Multisets

If you have a bag of items and track how many times each item appears, then all the operations you'd want to do on those bags correspond exactly to max, min, and addition. So manipulating multisets in tropical arithmetic reduces to manipulating plain integers.

a ∪ b is max

You can think of max as the smallest bag that covers both bags, or the LCM.

( bag x ) [x:cat^4 x:fox]
( bag y ) [y:cat^2 y:fox^2 y:owl]

@max ( :cat :fox :owl -- cat fox owl )
	'cat/[x:cat y:cat] 'cat/x:cat 'cat/y:cat
	'fox/[x:fox y:fox] 'fox/x:fox 'fox/y:fox
	'owl/[x:owl y:owl] 'owl/x:owl 'owl/y:owl

[cat^4 fox^2 owl]

a ∩ b is min

To check if a set contains a specific item, it comes down to looking up whether the min of an item is greater than zero, or the GCD:

( bag x ) [x:cat^4 x:fox]
( bag y ) [y:cat^2 y:fox^2 y:owl]

@min ( :cat :fox :owl -- cat fox owl )
	'cat/[x:cat y:cat]
	'fox/[x:fox y:fox]
	'owl/[x:owl y:owl]

[.. cat^2 fox]

a + b is mul

To combine two multisets together:

( bag x ) [x:cat^4 x:fox]
( bag y ) [y:cat^2 y:fox^2 y:owl]

@mul ( :cat :fox :owl -- cat fox owl )
	'cat/x:cat 'cat/y:cat
	'fox/x:fox 'fox/y:fox
	'owl/x:owl 'owl/y:owl

[cat^6 fox^3 owl]

To dive deeper, see Fractran and Rejoice.

incoming: lunar arithmetic