## Tropical semimodules of dimension two

HTML articles powered by AMS MathViewer

- by Ya. Shitov
- St. Petersburg Math. J.
**26**(2015), 341-350 - DOI: https://doi.org/10.1090/S1061-0022-2015-01341-1
- Published electronically: February 3, 2015
- PDF | Request permission

## Abstract:

The tropical arithmetic operations on $\mathbb {R}$ are defined as $a\oplus b=\min \{a,b\}$ and $a\otimes b=a+b$. In the paper, the concept of a semimodule is discussed, which is rather ill-behaved in tropical mathematics. The semimodules $S\subset \mathbb {R}^n$ having topological dimension two are studied and it is shown that any such $S$ has a finite weak dimension not exceeding $n$. For a fixed $k$, a polynomial time algorithm is constructed that decides whether $S$ is contained in some tropical semimodule of weak dimension $k$ or not. This result provides a solution of a problem that has been open for eight years.## References

- Marianne Akian, Stéphane Gaubert, and Alexander Guterman,
*Linear independence over tropical semirings and beyond*, Tropical and idempotent mathematics, Contemp. Math., vol. 495, Amer. Math. Soc., Providence, RI, 2009, pp. 1–38. MR**2581511**, DOI 10.1090/conm/495/09689 - François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat,
*Synchronization and linearity*, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR**1204266** - Alexander I. Barvinok,
*Two algorithmic results for the traveling salesman problem*, Math. Oper. Res.**21**(1996), no. 1, 65–84. MR**1385867**, DOI 10.1287/moor.21.1.65 - Mike Develin,
*The moduli space of $n$ tropically collinear points in $\Bbb R^d$*, Collect. Math.**56**(2005), no. 1, 1–19. MR**2131129** - Mike Develin and Bernd Sturmfels,
*Tropical convexity*, Doc. Math.**9**(2004), 1–27. MR**2054977** - Mike Develin, Francisco Santos, and Bernd Sturmfels,
*On the rank of a tropical matrix*, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 213–242. MR**2178322** - Manfred Einsiedler, Mikhail Kapranov, and Douglas Lind,
*Non-Archimedean amoebas and tropical varieties*, J. Reine Angew. Math.**601**(2006), 139–157. MR**2289207**, DOI 10.1515/CRELLE.2006.097 - Jeanne Ferrante and Charles Rackoff,
*A decision procedure for the first order theory of real addition with order*, SIAM J. Comput.**4**(1975), 69–76. MR**389572**, DOI 10.1137/0204006 - Stéphane Gaubert and Max Plus,
*Methods and applications of $(\max ,+)$ linear algebra*, STACS 97 (Lübeck), Lecture Notes in Comput. Sci., vol. 1200, Springer, Berlin, 1997, pp. 261–282. MR**1473780**, DOI 10.1007/BFb0023465 - Jonathan S. Golan,
*Semirings and their applications*, Kluwer Academic Publishers, Dordrecht, 1999. Updated and expanded version of*The theory of semirings, with applications to mathematics and theoretical computer science*[Longman Sci. Tech., Harlow, 1992; MR1163371 (93b:16085)]. MR**1746739**, DOI 10.1007/978-94-015-9333-5 - Grigori L. Litvinov and Victor P. Maslov,
*The correspondence principle for idempotent calculus and some computer applications*, Idempotency (Bristol, 1994) Publ. Newton Inst., vol. 11, Cambridge Univ. Press, Cambridge, 1998, pp. 420–443. MR**1608383**, DOI 10.1017/CBO9780511662508.026 - Yaroslav Shitov,
*The complexity of tropical matrix factorization*, Adv. Math.**254**(2014), 138–156. MR**3161095**, DOI 10.1016/j.aim.2013.12.013 - Oleg Viro,
*Dequantization of real algebraic geometry on logarithmic paper*, European Congress of Mathematics, Vol. I (Barcelona, 2000) Progr. Math., vol. 201, Birkhäuser, Basel, 2001, pp. 135–146. MR**1905317** - Edouard Wagneur,
*Moduloïds and pseudomodules. I. Dimension theory*, Discrete Math.**98**(1991), no. 1, 57–73. MR**1139597**, DOI 10.1016/0012-365X(91)90412-U

## Bibliographic Information

**Ya. Shitov**- Affiliation: National Research University–Higher School of Economics, Myasnitskaya Ulitsa 20, Moscow 101000, Russia
- MR Author ID: 864960
- Email: yaroslav-shitov@yandex.ru
- Received by editor(s): June 27, 2013
- Published electronically: February 3, 2015
- © Copyright 2015 American Mathematical Society
- Journal: St. Petersburg Math. J.
**26**(2015), 341-350 - MSC (2010): Primary 15A03, 15A23, 15A80
- DOI: https://doi.org/10.1090/S1061-0022-2015-01341-1
- MathSciNet review: 3242042