Geometry and algorithms for upper triangular tropical matrix identities (Q2417805)

The weakly upper-triangular matrices of tropical numbers form a semigroup, and this paper's concern is with identities for this semigroup. The recent interest in this question appears to stem from \textit{Z. Izhakian} and \textit{S. W. Margolis} [Semigroup Forum 80, No. 2, 191--218 (2010; Zbl 1215.20055)], where finding identities for unrestricted \(2\times 2\) tropical matrices was reduced to the upper-triangular case. By an identity in a semigroup \(G\) is meant a statement like ``\(abbaababba = abbabaabba\) for all \(a, b \in G\)'': that is, it is a pair of elements of a free monoid \(F\) which have the same image under any map from \(F\) to \(G\). In essence, this paper is a follow-up to [\textit{L. Daviaud} et al., J. Algebra 501, 503--525 (2018; Zbl 1403.20066)]. Daviaud et al. [loc. cit.] gave a criterion for detecting whether a pair of words is an identity by comparing tropical polynomials, more efficient than the naive criterion which is also of this form (to wit, multiply out matrices of indeterminates and check equality entrywise). The present work reinterprets the criterion using polyhedral geometry (in place of equalities of tropical polynomial functions), making it more amenable to computer implementation. One of the main new theorems is a set of runtime analyses of algorithms for testing whether a pair of words form an identity, listing all words equivalent to a given one, and listing all equivalence classes. Helpfully the authors have provided a website where their code for these is to be found. With their software, the authors have confirmed a theorem of \textit{S. I. Adian} [Proc. Steklov Inst. Math. 85, 152 p. (1966; Zbl 0204.01702); translation from Tr. Mat. Inst. Steklov 85, 123 p. (1966)] on the shortest identities for \(2\times2\) matrices, newly provided the shortest for \(3\times3\) matrices, and made several experiments by random sampling prompting them to make some structural and enumerative conjectures. The other main theorem is structural, and pertains to \(2\times2\) upper-triangular tropical matrices and alphabet size 2. Daviaud et al. [loc. cit.] proved that the identities satisfied by these matrices are the same as those satisfied by the bicyclic monoid \(\langle p,q \mid pq=1\rangle\). In this setting, the authors provide a lattice structure on the set of words on two letters such that every identity equivalence class of words is an interval. They use these insights to give specially optimised algorithms for these parameter values.