Tropical Polynomials

Construction

There are various ways to create a tropical polynomial.

Empty Sum

TropicalPolynomial() creates a polynomial with no terms:

julia> p = TropicalPolynomial()
∞

Since p is an empty sum, it represents a constant corresponding to the additive identity element, ∞.

Exponent/Coefficient Pairs

There are two ways to define a TropicalPolynomial by specifying exponents and coefficients. First, we can provide a list of exponent/coefficient pairs, like this:

julia> p = TropicalPolynomial([0=>3, 4=>1.5])
3.0⊗x⁰ ⊕ 1.5⊗x⁴

The pair 4 => 1.5 means the coefficient of x^4 is Tropical(1.5).

Note that the exponents may be negative integers:

julia> p = TropicalPolynomial([-1 => 4, 1 => 0])
4⊗x⁻¹ ⊕ 0⊗x¹

Alternatively, we may create a dictionary mapping integers to tropical numbers, and pass that to TropicalPolynomial.

julia> clist = Dict{Int, Tropical}()
Dict{Int64, Tropical}()

julia> clist[-1] = 4
4

julia> clist[0] = 1
1

julia> clist[2] = -5
-5

julia> p = TropicalPolynomial(clist)
4⊗x⁻¹ ⊕ 1⊗x⁰ ⊕ -5⊗x²

A comfortable way to create polynomials is to use an expression representing the variable $x$ and then combine it using coefficients and powers. To that end, we have the function tropical_x that returns the polynomial $0 \otimes x$.

julia> x = tropical_x()
0⊗x¹

julia> p = 2 + x^2 + (-4)*x^3
2⊗x⁰ ⊕ 0⊗x² ⊕ -4⊗x³

If k is an integer, tropical_x(k) returns $0 \otimes x^k$. This is a convenient way to create negative exponents.

julia> x = tropical_x()
0⊗x¹

julia> xinv = tropical_x(-1)
0⊗x⁻¹

julia> 2x + (-3)xinv
-3⊗x⁻¹ ⊕ 2⊗x¹

Coefficients

The coefs function returns a dictionary whose keys are the exponents and those corresponding values are the coefficients.

julia> x = tropical_x()
0⊗x¹

julia> p = 2 + 3x + (-5)x^2
2⊗x⁰ ⊕ 3⊗x¹ ⊕ -5⊗x²

julia> coefs(p)
Dict{Int64, Tropical} with 3 entries:
  0 => Tropical(2)
  2 => Tropical(-5)
  1 => Tropical(3)

Arithmetic

Addition and Multiplication

Polynomial addition and multiplication can be performed using the usual + and * operations, though ⊕ and ⊗ may be used instead. If a polynomial is added to (or multiplied by) a real number, that number is automatically converted to Tropical.

julia> x = tropical_x()
0⊗x¹

julia> p = 2 + x^2 + (-4)*x^3
2⊗x⁰ ⊕ 0⊗x² ⊕ -4⊗x³

julia> q = x+1
1⊗x⁰ ⊕ 0⊗x¹

julia> p+q
1⊗x⁰ ⊕ 0⊗x¹ ⊕ 0⊗x² ⊕ -4⊗x³

julia> p*q
3⊗x⁰ ⊕ 2⊗x¹ ⊕ 1⊗x² ⊕ -3⊗x³ ⊕ -4⊗x⁴

julia> p+0
0⊗x⁰ ⊕ 0⊗x² ⊕ -4⊗x³

julia> (-2)*p
0⊗x⁰ ⊕ -2⊗x² ⊕ -6⊗x³

Exponentiation

Given a tropical polynomial $p$, there are two ways to think about $p^n$ where $n$ is a positive integer. First, it is repeated multiplication $\underbrace{p \cdot p \cdots p}_n$. The other is to exploit a feature of tropical arithmetic that $(a \oplus b)^n = a^n \oplus b^n$. The latter is simpler and faster to compute, and that is how we have implemented exponentiation.

WARNING: Future versions of SimpleTropical might do things differently.

julia> p = 2x + 5x^2
2⊗x¹ ⊕ 5⊗x²

julia> p*p*p
6⊗x³ ⊕ 9⊗x⁴ ⊕ 12⊗x⁵ ⊕ 15⊗x⁶

julia> p^3
6⊗x³ ⊕ 15⊗x⁶

Note that p^3 and p*p*p are different polynomials, but they are identical as functions.

Evaluation

To evaluate a polynomial p for a number a, simply use p(a). If a is not already a Tropical number, it is converted to one.

julia> p = -2x + 5x^2
-2⊗x¹ ⊕ 5⊗x²

julia> p(0)      # min of -2 and 5
Tropical(-2)

julia> p(10)     # min of 8 and 25
Tropical(8)

julia> p(-10)    # min of -12 and -15
Tropical(-15)

Conversion to a `Function`

The output of a TropicalPolynomial is always a Tropical number. If we wish to use a tropical polynomial as a function from the reals to the reals, then make_function(p) converts p into a Function that can be used, for example, in plotting.

julia> p = -2x + 5x^2
-2⊗x¹ ⊕ 5⊗x²

julia> f = make_function(p);

julia> f(-10)
-15

Equality

Use == to test if two tropical polynomials are equal. This means that they have exactly the same terms (powers of $x$ and corresponding coefficients). Two polynomials might be equal as functions but will not be deemed equal by ==.

julia> p = 1 + 3x + x^2
1⊗x⁰ ⊕ 3⊗x¹ ⊕ 0⊗x²

julia> q = 1 + x^2
1⊗x⁰ ⊕ 0⊗x²

julia> all(p(a)==q(a) for a in -10:0.1:10)  # p and q give identical results
true

julia> p==q     # but they are different polynomials
false

To Do List

Implement a roots function. This seems feasible.
Implement a way to tell if two polynomials are equal as functions. Or find a way to reduce polynomials to a canonical form by eliminating unnecessary terms. Not clear exactly how to do this.