Stable complete coordinates for multisets of points via basic r-symmetric tropical polynomials
Pith reviewed 2026-06-30 03:23 UTC · model grok-4.3
The pith
Binomial(n+r,r) basic r-symmetric tropical polynomials separate all S_n orbits on R^{nr} for every n and r.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that for all n ≥ 1 and r ≥ 1, the binomial(n+r,r) basic r-symmetric tropical polynomials of degree at most n separate the orbits of the symmetric group S_n on R^{nr}. This means they form a complete set of permutation-independent coordinates for multisets of n points in R^r. The proof is elementary and constructive, identifying the values with a transportation problem and recovering the multiset from the dual by an explicit algorithm. The map is moreover a bi-Lipschitz embedding.
What carries the argument
the binomial(n+r,r) basic r-symmetric tropical polynomials of degree at most n, which serve as invariants that separate orbits by functioning as an injective max filter bank
If this is right
- The coordinates are stable and explicit for point clouds and for persistence barcodes when r=2.
- The embedding has an explicit Lipschitz constant for the forward bound and a fully explicit dimension-free distortion when r=1.
- Pairwise values suffice precisely when n ≤ 3.
- In general, invariants involving at least three columns and of degree n are necessary due to non-uniqueness configurations from discrete tomography.
Where Pith is reading between the lines
- These coordinates could supply stable and complete distances between persistence diagrams.
- The transportation-problem view may permit efficient numerical recovery of the multiset via linear programming.
- For r=1 the distortion bound being dimension-free hints at possible extensions to other semirings or algebraic settings.
- Running the recovery algorithm on sampled point clouds would provide direct computational checks of separation.
Load-bearing premise
The polynomial values can be identified with a transportation problem whose solution dual yields an explicit algorithm that recovers the original multiset uniquely.
What would settle it
Two different multisets of n points whose corresponding basic r-symmetric tropical polynomials evaluate to the same values would disprove the separation result.
read the original abstract
A multiset of $n$ unordered points in $\mathbb{R}^r$ -- a point cloud, or, for $r=2$, a persistence barcode of birth-death pairs -- is a point of the orbit space $\mathbb{R}^{nr}/S_n$ for the symmetric group $S_n$ permuting the rows of an $n \times r$ matrix; a separating family of invariants on this space is exactly a complete set of permutation-independent coordinates. We provide one that is explicit, small, and stable, in the max-plus (tropical) setting: for all $n \geq 1$ and $r \geq 1$, the $\binom{n+r}{r}$ basic $r$-symmetric tropical polynomials, of degree at most $n$, separate the orbits of $S_n$ on $\mathbb{R}^{nr}$. This settles in full a problem left open in [Kubo, J. Pure Appl. Algebra 223 (2019) 72-85], where separation was known only for $r=2$ and special cases of $r \geq 3$, and yields a family far smaller and of lower degree than the general separating sets from Derksen's recent theory of tropical invariants for permutation actions ($nr + (nr)!/n!$ invariants of degree $O(n^2 r^2)$). The proof is elementary and constructive: the basic values are identified with a transportation problem, and the multiset is recovered from the dual by an explicit algorithm. We further show the coordinate map is a bi-Lipschitz embedding for all $n$ and $r$, being an injective max filter bank (via the bi-Lipschitz theory of max filtering), with an explicit Lipschitz constant for the forward bound and a fully explicit, dimension-free distortion when $r=1$. Finally we determine when the pairwise values suffice (exactly $n \leq 3$) and show that invariants on at least three columns and of degree less than $n$ are necessary in general, the obstruction being a standard non-uniqueness configuration from discrete tomography.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that the inom{n+r}{r} basic r-symmetric tropical polynomials of degree at most n form a complete separating family for the orbits of S_n acting on \mathbb{R}^{nr} (i.e., on unordered n-point multisets in \mathbb{R}^r) for all n,r \geq 1. The proof is elementary and constructive: the polynomial values are identified with the costs of a transportation problem whose supply/demand data encode the multiset, after which the multiset is recovered uniquely from an optimal dual solution by an explicit algorithm. The coordinate map is further shown to be bi-Lipschitz (via max-filtering theory), with an explicit forward Lipschitz constant and a dimension-free distortion bound when r=1. The paper also determines that pairwise values suffice precisely when n \leq 3 and exhibits a discrete-tomography obstruction showing that degree <n or fewer than three columns cannot separate in general.
Significance. If the central claims hold, the work supplies an explicit, small, and stable complete coordinate system for multisets that is dramatically smaller and lower-degree than the general separating sets furnished by Derksen's tropical invariant theory. The constructive transportation-duality argument, the bi-Lipschitz embedding, and the necessity results constitute concrete strengths; the explicit algorithm and dimension-free distortion for r=1 are particularly useful for applications such as persistence barcodes.
minor comments (3)
- §2 (or wherever the transportation identification is stated): the precise correspondence between the basic r-symmetric tropical polynomial evaluations and the transportation costs should be written as an explicit equality (rather than left implicit) so that the subsequent dual-recovery algorithm can be checked line-by-line.
- The bi-Lipschitz section invokes the general max-filtering theory; a short self-contained paragraph recalling the precise statement of the forward and reverse Lipschitz bounds used would improve readability for readers outside that subfield.
- The necessity argument via the discrete-tomography configuration is convincing, but the explicit counter-example matrices for r=2, n=4 should be displayed in a small table to make the obstruction immediately verifiable.
Simulated Author's Rebuttal
We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the report, so there are no individual points requiring response or manuscript changes.
Circularity Check
No significant circularity; explicit constructive proof is self-contained.
full rationale
The derivation identifies the basic r-symmetric tropical polynomial values with a transportation problem and recovers the multiset via an explicit algorithm, directly establishing orbit separation for all n,r. This is an independent constructive argument, not a reduction to fitted parameters, self-definition, or a load-bearing self-citation chain. The citation to Kubo (2019) only records the prior open problem status; the new proof does not rely on it for correctness. Reference to max-filtering bi-Lipschitz theory supports the embedding property but is not required for the separation claim itself. No quoted step equates the result to its inputs by construction.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math The max-plus (tropical) semiring structure on R
- domain assumption The identification of basic values with a transportation problem
Reference graph
Works this paper leans on
-
[1]
Max-Linear Systems: Theory and Algorithms , publisher =
Butkovi. Max-Linear Systems: Theory and Algorithms , publisher =
-
[2]
and Mixon, Dustin G
Cahill, Jameson and Iverson, Joseph W. and Mixon, Dustin G. and Packer, Daniel , title =. Found. Comput. Math. , volume =
-
[3]
2023 , note =
Balan, Radu and Tsoukanis, Efstratios , title =. 2023 , note =
2023
-
[4]
Symmetric and r -symmetric tropical polynomials and rational functions , journal =
Carlsson, Gunnar and Kali. Symmetric and r -symmetric tropical polynomials and rational functions , journal =
-
[5]
2025 , note =
Derksen, Harm , title =. 2025 , note =
2025
-
[6]
and Gritzmann, Peter , title =
Gardner, Richard J. and Gritzmann, Peter , title =. Trans. Amer. Math. Soc. , volume =
-
[7]
Advances in Discrete Tomography and Its Applications , editor =
Hajdu, Lajos and Tijdeman, Robert , title =. Advances in Discrete Tomography and Its Applications , editor =
-
[8]
, title =
Itenberg, Ilia and Mikhalkin, Grigory and Shustin, Eugenii I. , title =
-
[9]
Kubo, Susumu , title =. J. Pure Appl. Algebra , volume =
-
[10]
The 28th Symposium of Japanese Society of Applied Statistics , year =
Matsui, Kiyoshi , title =. The 28th Symposium of Japanese Society of Applied Statistics , year =
-
[11]
Weyl, Hermann , title =
-
[12]
Tropical Sufficient Statistics for Persistent Homology , journal =
Monod, Anthea and Kali. Tropical Sufficient Statistics for Persistent Homology , journal =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.