Nathan Grigg and Dr. Tyler Jarvis, Mathematics
Tropical algebra, also called “min-plus” or “max-plus” algebra, is a relatively new topic in mathematics that has recently caught the interest of algebraic geometers, computer scientists, combinatorists, and other mathematicians. According to Andreas Gathmann , tropical algebra was pioneered by mathematician and computer scientist Imre Simon in the 1980s but did not receive widespread attention until a few years ago. Interestingly, the title “tropical algebra” is nothing more than a reference to Simon’s home country—Brazil.
The tropical semi-ring, which is the basis of this problem-solving tool and our major object of study, is formed by replacing the standard addition operation with the minimum function and replacing multiplication with addition. Although many difficult problems can be translated into simpler tropical problems, even these simpler problems can be difficult if we do not understand the tropical algebraic system. Since tropical algebra is so new, several things about it are unknown. Our purpose in studying it, then, is to understand it better, since the more we understand about the mechanics of the tropical algebraic system, the more effective this tool becomes.
To provide a better understanding of this system, I concentrated on finding methods to factor tropical polynomials. There are two reasons we want to factor polynomials. First, it helps us to better study other areas of tropical algebra, which makes it easier to solve some of the problems mentioned above. Second, factoring tropical polynomials helps us to factor classical polynomials.
In my research, I discovered and formalized several results regarding the factorization of polynomials over the rational tropical semi-ring. I wrote and published an elementary proof of the Fundamental Theorem of Tropical Algebra. I showed that every tropical polynomial of a single variable can be factored completely into linear factors by a simple and straightforward process. I also discuss the ideas of functional equivalence of tropical polynomials and least-coefficient polynomials, two very important themes in tropical algebra.
I also discuss the factorization of polynomials of several variables. I prove that factorization is NP-complete, and give an algorithm that runs in polynomial time for some classes of polynomials. Since this algorithm depends on the properties of a polynomial’s zero locus, I also discuss the theory of tropical zero loci. While these results are beyond the scope of this summary article, they are published in my honors thesis.
Tropical Polynomials of One Variable
Fundamental Theorem of Tropical Algebra. Every tropical polynomial in one variable with rational coefficients can be factored uniquely as a product of linear tropical polynomials with rational coefficients, up to functional equivalence.
In the proof of this theorem (which is contained in my honors thesis), I first discuss the idea of functional equivalence. Tropically, it is most useful to consider two polynomials as equivalent if the functions they define are equivalent. Next, I discuss a best representative for each functional equivalence class, called a least-coefficient polynomial. Least-coefficient polynomials turn out to be very a very useful way to identify when two tropical polynomials define the same function. I prove that every tropical polynomial is equivalent to a least-coefficient polynomial and that each least-coefficient polynomial can be easily factored using a formula given in Section 2.3 of my thesis.
As in the classical case, the unique factorization of a polynomial gives us what could be considered the roots of the polynomial. This identification of tropical polynomial “roots,” which are analogous to but different from classical polynomial roots, helps us better understand tropical polynomials of more than one variable. Furthermore, we find that the fundamental theorem of tropical algebra holds over the semi-field formed by the rational numbers together with infinity, thereby making the rational numbers algebraically closed in the tropical sense.
Tropical Polynomials of Several Variables
Although we can factor every single-variable polynomial into linear factors, we have no hope of being able to do the same for polynomials of two or more variables. In fact, tropical polynomials in more than one variable do not always have unique factorizations. Nevertheless, the structure of the tropical zero locus makes it possible for us to learn a lot more about tropical factorization than we would expect to be able to. To make use of this structure, I discuss the tropical zero locus in detail. I discuss polyhedral complexes and a correspondence between weighted balanced complexes and tropical polynomials. I prove that factorization of tropical polynomials in two or more variables is NP-complete. I also present a method in which we use the structure of the tropical zero locus to find factorizations of polynomials.