The basic tropical polynomials generate the semifield of $r$-symmetric tropical rational functions

Abstract

Let the symmetric group $S_n$ act on the space of $n\times r$ real matrices by permuting rows, so orbits are multisets of $n$ points in ${\mathbb{R}}^r$. The basic $r$-symmetric tropical polynomials form a family of $\left(\genfrac{}{}{0ex}{}{n+r}{r}\right)-1$ nonconstant invariants of degree at most $n$ that separates orbits and embeds the orbit space bi-Lipschitzly. We prove that this family generates the semifield of all $r$-symmetric tropical rational functions, answering a question raised in [J. Pure Appl. Algebra 223 (2019) 72-85]. Derksen showed that the invariant semifield of any permutation group $G\le S_N$ is generated in degree at most $N{p}_1\cdots p_{|G|}$ ($p_i$ the $i$th prime), which for the row action is $nr{p}_1\cdots p_{n!}$; the present result replaces this by generators of degree at most $n$. The generating expression is a finite minimum over the ways of re-assembling a multiset from its sorted columns, with penalties from the basic values that, via the bi-Lipschitz inequality, dominate a wrong re-assembly. The same penalties describe the image of the basic coordinate map as the zero set of a single tropical rational function and yield an expression algorithm. Subfamilies of the basic family containing the single-column values generate if and only if they separate. For any permutation group $G\le S_N$ the same mechanism generates the invariant semifield in degree at most $\max \{N,(\genfrac{}{}{0ex}{}{N}{2})\}$, a quadratic bound independent of the group order; combined with a genericity theorem of Cahill, Iverson, Mixon, and Packer, it yields $2N+1$ invariant tropical polynomials that separate orbits and $3N$ that generate, with at least $N$ necessary for each task. The quadratic bound is optimal: every $A_N$-invariant tropical polynomial of degree less than $\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ is $S_N$-invariant, so every separating family for the alternating group $A_N$ contains a member of degree at least $\left(\genfrac{}{}{0ex}{}{N}{2}\right)$.

arXiv comment13 pages