On the Representational Geometry of Dynamic Programs

# On the Representational Geometry of Dynamic Programs
Source: [https://arxiv.org/html/2608.25034](https://arxiv.org/html/2608.25034)
Richard F\. M\. LimEmail:[rlim@bowdoin\.edu](mailto:)Affiliation:Departments of Mathematics and Computer Science, Bowdoin College, Brunswick, MaineAffiliation:Department of Operations Research, Naval Postgraduate School, Monterey, CaliforniaRuriko YoshidaEmail:[ry@math\.aau\.dk](mailto:)Affiliation:Department of Mathematical Sciences, Aalborg University, DenmarkAffiliation:Department of Operations Research, Naval Postgraduate School, Monterey, California

###### Abstract

Standard neural architectures often fail to generalize to longer inputs for dynamic programming \(DP\) targets\. We investigate what makes this hard geometrically\. Every finite min\-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins\. We prove these three descriptions \(graph, polynomial, polyhedron\) form isomorphic semirings at two levels — formal polynomials and their computed functions — connected by operations that characterize all structural redundancies\. We then address the length\-generalization question geometrically: does the decision boundary at lengthTTdecide the boundary atT\+1T\+1? We present two structural negatives\. The semiring’s two native ways to reduce dimension \(setting a variable to each identity\) are neither injective nor always closed within the DP\. Series and parallel composition fail to construct all DAG topologies from smaller sub\-DAGs, and even all terminal\-only operations do not capture all DP compositions\.

## 1Introduction

A dynamic program is defined by a recurrence that does not depend on the size of its input, so a model that has truly learned the recurrence would run at any length\. Standard sequence architectures do not\. Trained on combinatorial optimization targets, they fit the training lengths and then degrade sharply beyond them, a failure documented across recurrent and attention\-based models and robust to scale\([Delétang et al\., 2023](https://arxiv.org/html/2608.25034#bib.bib3);[Anil et al\., 2022](https://arxiv.org/html/2608.25034#bib.bib1)\)\. Tropical Attention\([Hashemi et al\., 2025](https://arxiv.org/html/2608.25034#bib.bib6)\)is a conspicuous exception; replacing addition and multiplication with max\-plus \(tropical\) operations\(max,\+\)\(\\max,\+\), it achieves strong length out\-of\-distribution \(OOD\) generalization on classic DP problems\.

The premise is classical\. After unrolling, every finite min\-plus dynamic program is: \(1\) a single\-pair shortest\-path problem on a decision DAG with a single sourcessand single sinkzz, which we call*two\-terminal*\([Bellman, 1957](https://arxiv.org/html/2608.25034#bib.bib2);[Gondran and Minoux, 1979](https://arxiv.org/html/2608.25034#bib.bib5)\); and \(2\) a tropical polynomial\([Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7)\)\. For alignment with the shortest\-path formulation, we work throughout in the dual\(min,\+\)\(\\min,\+\)semiring𝕋=ℝ∪\{\+∞\}\\mathbb\{T\}=\\mathbb\{R\}\\cup\\\{\+\\infty\\\}, equivalent to\(max,\+\)\(\\max,\+\)under negation\([Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7)\)\. We writea⊕b=min⁡\(a,b\)a\\oplus b=\\min\(a,b\)anda⊙b=a\+ba\\odot b=a\+bwhen emphasizing the semiring structure\.

Our work is focused on length generalization: a learner observes small graphs with at mostTTvariables and must predict every graph after that\. We therefore investigate whether this is possible via the questions: \(1\) What algebraic structure in DP allows algorithms to work on every length? \(2\) Does this structure allow us to infer larger instances from smaller ones?

Composing two\-terminal DAGs in series adds their path lengths; composing them in parallel takes the minimum \(Figure[3](https://arxiv.org/html/2608.25034#A1.F3)in Appendix[A](https://arxiv.org/html/2608.25034#A1)\)\. We first formalize the relationship between graphs, polynomials, and geometry via a triple semiring isomorphism \(Section[2](https://arxiv.org/html/2608.25034#S2)\)\. Multiple*formal*polynomials may map to the same*function*—min⁡\(0,x,2​x\)=min⁡\(0,2​x\)\\min\(0,x,2x\)=\\min\(0,2x\)for allxxdespite different supports — so we construct the formalism at both levels and relate them with congruence quotients\. Graph structures are even richer than their polynomials, so we provide a canonical*deshared*normal form for every tropical polynomial and a list of invariant operations that traverse equivalence classes on DAGs \(Section[3](https://arxiv.org/html/2608.25034#S3)\)\.

A natural way to relate larger instances to smaller ones is substitution at the semiring identities: setting a variable to\+∞\+\\inftyremoves it from a shortest\-path or knapsack instance, while setting it to00removes it from a min\-subarray or assignment instance\. We employ the above framework to provide a characterization of length recovery under substitution in terms of graph, polynomial, polyhedron, and the*decision boundary*𝒯⁡\(f\)\\mathcal\{T\}\(f\), known as the*tropical hypersurface*\([Zhang et al\., 2018](https://arxiv.org/html/2608.25034#bib.bib11)\)\. We show in Section[4](https://arxiv.org/html/2608.25034#S4)that both substitutions are not always closed within the DP, and do not recover length even when they are: theTT\-th instance does not determine the\(T\+1\)\(T\{\+\}1\)\-th\. Finally, Section[5](https://arxiv.org/html/2608.25034#S5)identifies series and parallel composition as the two faces of Bellman’s equation on decision DAGs, then exposes a two\-layered topological insufficiency: together they do not generate all topologies of terminal\-only operations, and terminal\-only operations do not capture all DP compositions\.

## 2The triality: one problem, three languages

Appendix[B](https://arxiv.org/html/2608.25034#A2)details the tropical geometry background used throughout\. A*formal tropical polynomial*inddvariables is a finite tropical sum of monomials,f⁡\(x\)=⨁αcα⊙x⊙α=minα⁡\(cα\+⟨α,x⟩\)f\(x\)=\\bigoplus\_\{\\alpha\}c\_\{\\alpha\}\\odot x^\{\\odot\\alpha\}=\\min\_\{\\alpha\}\(c\_\{\\alpha\}\+\\langle\\alpha,x\\rangle\), with exponentsα∈ℤ≥0d\\alpha\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{d\}and coefficientscα∈𝕋c\_\{\\alpha\}\\in\\mathbb\{T\}\(cα=\+∞c\_\{\\alpha\}=\{\+\}\\inftymeaning the term is absent\)\. Its*support*isS⁡\(f\)=\{α:cα≠\+∞\}S\(f\)=\\\{\\alpha:c\_\{\\alpha\}\\neq\{\+\}\\infty\\\}, and its*lifted support*S^​\(f\)=\{\(α,cα\):α∈S⁡\(f\)\}\\hat\{S\}\(f\)=\\\{\(\\alpha,c\_\{\\alpha\}\):\\alpha\\in S\(f\)\\\}raises each point to its coefficient height\. Terms sharing an exponent keep only the lesser coefficient,\(c⊕c′\)⊙x⊙α\(c\\oplus c^\{\\prime\}\)\\odot x^\{\\odot\\alpha\}; call this per\-exponent reductionvmin\\vmin\(vertical minimum\), and sayffis in*normal form*once reduced by it, one coefficient per exponent\. The normal\-form lifted supportsℒd\\mathcal\{L\}\_\{d\}— finite subsets ofℤ≥0d×ℝ\\mathbb\{Z\}\_\{\\geq 0\}^\{d\}\\times\\mathbb\{R\}with at most one point over each exponent — form a commutative idempotent semiring undervmin\(⋅∪⋅\)\\vmin\(\\cdot\\cup\\cdot\)and Minkowski addition \(Proposition[9](https://arxiv.org/html/2608.25034#Thmtheorem9)\)\. The*extended Newton polyhedron*isΓ⁡\(f\)=conv⁡\(S^​\(f\)\)\+ℝ≥0​ed\+1\\Gamma\(f\)=\\operatorname\{conv\}\(\\hat\{S\}\(f\)\)\+\\mathbb\{R\}\_\{\\geq 0\}\\,e\_\{d\+1\}, the convex hull of the lifted support extended upward\. Two polynomials compute the same function if and only if their extended Newton polyhedra agree\([Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7)\)\. Thus, convexity is the second quotient, andvmin\\vminbecomesconv\\operatorname\{conv\}\. The ordinary*Newton polytope*𝒩⁡\(f\)=conv⁡\(S⁡\(f\)\)\\mathcal\{N\}\(f\)=\\operatorname\{conv\}\(S\(f\)\)is its vertical projection, constructed via monomials but not their coefficients\.

Every two\-terminal weighted DAGGGcomputes a min\-plus*path polynomial*\. This may be constructed by enumerating pathsπ\\pifrom sourcessto sinkzzas follows:fG=minπ:s→z∑e∈πwef\_\{G\}=\\min\_\{\\pi:s\\to z\}\\sum\_\{e\\in\\pi\}w\_\{e\}, the minimum overss–zzpaths in normal form\. For DAGsAAandBB,fA;B=fA\+fBf\_\{A;B\}=f\_\{A\}\+f\_\{B\}andfA\|B=min⁡\(fA,fB\)f\_\{A\\\|B\}=\\min\(f\_\{A\},f\_\{B\}\)\(Proposition[14](https://arxiv.org/html/2608.25034#Thmtheorem14)\)\. However, two graphs may have different topologies but compute exactly the same shortest\-path function, so we define equivalence relations that erase exactly this excess:G≈fG′G\\approx\_\{\\mathrm\{f\}\}G^\{\\prime\}iffS^​\(fG\)=S^​\(fG′\),\\hat\{S\}\(f\_\{G\}\)=\\hat\{S\}\(f\_\{G^\{\\prime\}\}\),andG≈vG′G\\approx\_\{\\mathrm\{v\}\}G^\{\\prime\}ifffG,fG′​compute the same function\.f\_\{G\},f\_\{G^\{\\prime\}\}\\text\{ compute the same function\.\}

Both are congruences \(compatible with;and∥\\\|\)\. The following theorem says each quotient produces a semiring isomorphic to its associated polynomial and polyhedron: at each level, graph, algebra, and geometry are the*same*semiring\.

###### Theorem 1\.

The following diagram of commutative idempotent semirings commutes; horizontal maps are isomorphisms, vertical maps are surjective homomorphisms\.

DAGs/≈f\\mathrm\{DAGs\}/\{\\approx\_\{\\mathrm\{f\}\}\}\(∥,;\)\(\\\|,\\;\{;\}\)formal trop\. polynomials\(min,\+\)\(\\min,\\,\{\+\}\)ℒd\\mathcal\{L\}\_\{d\}\(vmin\(⋅∪⋅\),\+\)\(\\vmin\(\\cdot\\\!\\cup\\\!\\cdot\),\\,\{\+\}\)DAGs/≈v\\mathrm\{DAGs\}/\{\\approx\_\{\\mathrm\{v\}\}\}\(∥,;\)\(\\\|,\\;\{;\}\)𝕋d→𝕋\\mathbb\{T\}^\{d\}\\\!\\to\\\!\\mathbb\{T\}\(min,\+\)\(\\min,\\,\{\+\}\)ext\. Newton polyhedra\(conv\(⋅∪⋅\),\+\)\(\\operatorname\{conv\}\(\\cdot\\\!\\cup\\\!\\cdot\),\\,\{\+\}\)\[G\]↦fG\[G\]\\\!\\mapsto\\\!f\_\{G\}≅\\congf↦S^​\(f\)f\\\!\\mapsto\\\!\\hat\{S\}\(f\)≅\\cong\[G\]↦fG\[G\]\\\!\\mapsto\\\!f\_\{G\}≅\\congf↦Γ⁡\(f\)f\\\!\\mapsto\\\!\\Gamma\(f\)≅\\cong≈v\\approx\_\{\\mathrm\{v\}\}same functionS↦conv⁡\(S\)\+ℝ≥0​ed\+1S\\\!\\mapsto\\\!\\operatorname\{conv\}\(S\)\{\+\}\\mathbb\{R\}\_\{\\geq 0\}e\_\{d\+1\}

The proof is in Appendix[D](https://arxiv.org/html/2608.25034#A4)\. The practical consequence is that a claim may be formulated and checked in whichever of the three languages makes it easiest, then translated to the others\.

## 3A complete calculus of invariant operations on DAG equivalences

We now give the operations relating two≈\\approx\-equivalent graphs\. The*deshared normal form*Df​\(G\)D\_\{\\mathrm\{f\}\}\(G\)is the parallel bundle of chains giving each monomial offGf\_\{G\}its ownss–zzpath, edges in variable order: the graph\-language canonical form of the polynomial as amin\\minof monomials\. Mediant deletion \(dropping dominated chains\) then gives the*function normal form*Dv​\(G\)D\_\{\\mathrm\{v\}\}\(G\)\. Four local operations, each realizing a semiring property \(Table[1](https://arxiv.org/html/2608.25034#A5.T1)in Appendix[E](https://arxiv.org/html/2608.25034#A5)\), carry any graph to these forms\.

###### Theorem 2\.

For all two\-terminal DAGsG,G′G,G^\{\\prime\}:

- \(i\)*Reduction\.*A finite sequence of formal moves carriesGGtoDf​\(G\)D\_\{\\mathrm\{f\}\}\(G\), using one vertex split per path intersection \(Lemma[16](https://arxiv.org/html/2608.25034#Thmtheorem16)\)\. Mediant deletions \(Lemma[18](https://arxiv.org/html/2608.25034#Thmtheorem18)\) then carryDf​\(G\)D\_\{\\mathrm\{f\}\}\(G\)toDv​\(G\)D\_\{\\mathrm\{v\}\}\(G\)\.
- \(ii\)*Canonicity\.*Df​\(G\)=Df​\(G′\)D\_\{\\mathrm\{f\}\}\(G\)=D\_\{\\mathrm\{f\}\}\(G^\{\\prime\}\)iffG≈fG′G\\approx\_\{\\mathrm\{f\}\}G^\{\\prime\}, andDv​\(G\)=Dv​\(G′\)D\_\{\\mathrm\{v\}\}\(G\)=D\_\{\\mathrm\{v\}\}\(G^\{\\prime\}\)iffG≈vG′G\\approx\_\{\\mathrm\{v\}\}G^\{\\prime\}; the chains ofDv​\(G\)D\_\{\\mathrm\{v\}\}\(G\)are exactly the vertices ofΓ⁡\(fG\)\\Gamma\(f\_\{G\}\)\. Both congruences are therefore decidable\.

Connectivity follows: two graphs are joined by formal moves iff they are≈f\\approx\_\{\\mathrm\{f\}\}, and by formal moves plus mediant deletions iff they are≈v\\approx\_\{\\mathrm\{v\}\}, since each side can reduce to its normal form\. The complete argument is in Appendix[E](https://arxiv.org/html/2608.25034#A5)\.

## 4Substitution geometry

To relate lengths we need an operation on congruence\-classes that is well\-defined across all three languages and reduces the variable count\. The semiring offers two identity substitutions: writePiP\_\{i\}forxi↦\+∞x\_\{i\}\\mapsto\+\\infty\(themin\\min\-identity\) andQiQ\_\{i\}forxi↦0x\_\{i\}\\mapsto 0\(the\+\+\-identity\)\. Over a field, two slices and subtraction recover affine dependence on a coordinate; tropically there is no subtraction, so a slice can only restrict\. Does the restriction suffice? We present two mechanisms of identification failure\.

###### Proposition 3\.

LetfGf\_\{G\}be a tropical polynomial int\+1t\+1variables\. Writingπi\\pi\_\{i\}for deletion of coordinateiiandπ^i\\hat\{\\pi\}\_\{i\}for its height\-preserving lift, each ofPiP\_\{i\}andQiQ\_\{i\}acts by a single transformation across the three languages, andQi​\(fG\)≤Pi​\(fG\)Q\_\{i\}\(f\_\{G\}\)\\leq P\_\{i\}\(f\_\{G\}\)pointwise \(a face lies inside the shadow\):

The two graph rows carry the two routes of the opening paragraph: forPiP\_\{i\}, “delete everyxix\_\{i\}\-edge” descends to classes; forQiQ\_\{i\}, “reweight everyxix\_\{i\}\-edge to00, then merge” is a rule on the deshared canonical form, since contraction on a general graph can create or destroy anss–zzpath\. The hypersurface row reads the same operations on the tropical hypersurface𝒯⁡\(fG\)\\mathcal\{T\}\(f\_\{G\}\), the decision boundary of the DP \(Section[1](https://arxiv.org/html/2608.25034#S1);[Zhang et al\., 2018](https://arxiv.org/html/2608.25034#bib.bib11)\):PiP\_\{i\}restricts to the strategies that ignore positionii, whileQiQ\_\{i\}slices through the boundary atxi=0x\_\{i\}=0\. Neither substitution is injective, and occasionally they are not*closed*; in Figure[1](https://arxiv.org/html/2608.25034#S4.F1), neitherPiP\_\{i\}norQiQ\_\{i\}sends the proper\-subset instance to a proper\-subset instance\. The exact fiber is computed in Corollary[21](https://arxiv.org/html/2608.25034#Thmtheorem21)\(Appendix[F](https://arxiv.org/html/2608.25034#A6)\)\.

\(L\)f=minS⊆\[3\]⁡x𝟏Sf=\\min\_\{S\\subseteq\[3\]\}x^\{\\mathbf\{1\}\_\{S\}\}\(min\-subset\-sum\)sszz00x1x\_\{1\}00x2x\_\{2\}00x3x\_\{3\}\(1,1,1\)\(1,1,1\)𝒩⁡\(f\)=\[0,1\]3\\mathcal\{N\}\(f\)=\[0,1\]^\{3\}x1x\_\{1\}x2x\_\{2\}x3x\_\{3\}𝒯⁡\(f\)\\mathcal\{T\}\(f\): the threeplanesxi=0x\_\{i\}\{=\}0;23=82^\{3\}=8chambers\{1,2,3\}\\\{1,2,3\\\}the orthantx<0x<0seenalong the diagonal:one chamber\(R\)g=minS⊊\[3\]⁡x𝟏Sg=\\min\_\{S\\subsetneq\[3\]\}x^\{\\mathbf\{1\}\_\{S\}\}\(proper subsets only\)b=0b\{=\}0b=1b\{=\}1sszzx1x\_\{1\}x2x\_\{2\}00000000x2x\_\{2\}00x3x\_\{3\}\(1,1,1\)\(1,1,1\)absent𝒩⁡\(g\)\\mathcal\{N\}\(g\): the cubecut at∑iαi≤2\\sum\_\{i\}\\alpha\_\{i\}\\leq 2x1x\_\{1\}x2x\_\{2\}x3x\_\{3\}𝒯⁡\(g\)\\mathcal\{T\}\(g\): dotted wallsreplaced byxi=xjx\_\{i\}\{=\}x\_\{j\};77chambers\{1,2\}\\\{1,2\\\}\{1,3\}\\\{1,3\\\}\{2,3\}\\\{2,3\\\}the orthantx<0x<0seenalong the diagonal: threechambers, meeting atxi=xjx\_\{i\}\{=\}x\_\{j\}observed:minS⊆\[2\]⁡x𝟏S\\min\_\{S\\subseteq\[2\]\}x^\{\\mathbf\{1\}\_\{S\}\}sszz00x1x\_\{1\}00x2x\_\{2\}α1\\alpha\_\{1\}α2\\alpha\_\{2\}Γ\\Gamma: the unit square∅\\emptyset\{1\}\\\{1\\\}\{2\}\\\{2\\\}\{1,2\}\\\{1,2\\\}x1x\_\{1\}x2x\_\{2\}𝒯\\mathcal\{T\}: two lines,44chambersP3,Q3P\_\{3\},\\,Q\_\{3\}P3,Q3P\_\{3\},\\,Q\_\{3\}

Figure 1:Two length\-33problems that no substitution distinguishes\.\(L\)min\-subset\-sum, support\{0,1\}3\\\{0,1\\\}^\{3\};\(R\)the same over proper subsets, support\{0,1\}3∖\{\(1,1,1\)\}\\\{0,1\\\}^\{3\}\\setminus\\\{\(1,1,1\)\\\}\. Middle panels show the decision boundaries \(positive half\-axes behind, dotted\)\. The all\-ones monomial is off the coordinate face and redundant under the projection, so bothP3P\_\{3\}andQ3Q\_\{3\}, applied to either problem, yield the same length\-22object \(bottom\)\.
## 5A hierarchy beyond series and parallel

Since substitution is insufficient, cross\-length structure must come from operations that*build*a longer instance from shorter ones\. Consider Bellman’s equation of optimal substructure,ft\+1​\(x\)=mind⁡\(wd\+ft\(d\)​\(x\)\)f\_\{t\+1\}\(x\)=\\min\_\{d\}\\bigl\(w\_\{d\}\+f\_\{t\}^\{\(d\)\}\(x\)\\bigr\)\. Series and parallel composition correspond to two ways of modifying a Bellman expression at timett: extending the time step and updating the prior, respectively\. We show that these operations are doubly insufficient to express the topology of DP instances\.

#### Series\-parallel⊊\\subsetneqterminal\-only\.

A terminal\-only operation may be thought of as an*edge substitution*ΦH\\Phi\_\{H\}on a template \(unweighted\) DAGHH, replacing each edge with a sub\-DAG \(Appendix[G](https://arxiv.org/html/2608.25034#A7)\)\. Series and parallel composition are the two simplest edge substitutions \(templates with one or two edges\), but they do not generate all edge\-substitution topologies: the witness is the Wheatstone graphWW\(Figure[2](https://arxiv.org/html/2608.25034#S5.F2), left\)\.

###### Proposition 4\.

The Wheatstone edge substitutionΦW\\Phi\_\{W\}\(Figure[2](https://arxiv.org/html/2608.25034#S5.F2)\) is not generated by series and parallel composition sinceWWis non\-series\-parallel\([Duffin, 1965](https://arxiv.org/html/2608.25034#bib.bib4);[Valdes et al\., 1982](https://arxiv.org/html/2608.25034#bib.bib10)\)\.

#### Terminal\-only⊊\\subsetneqall DP compositions\.

Clamped min\-subarray \(Figure[2](https://arxiv.org/html/2608.25034#S5.F2), right\) composes two instances by gluingsA=sBs\_\{A\}\{=\}s\_\{B\},zA=zBz\_\{A\}\{=\}z\_\{B\},*and*the last internal vertex ofAAto the first ofBB, so that a subarray may cross the boundary — an identification of*internal*vertices\.

A1A\_\{1\}A2A\_\{2\}A3A\_\{3\}A4A\_\{4\}A5A\_\{5\}ΦW​\(A1,…,A5\)\\Phi\_\{W\}\(A\_\{1\},\\dots,A\_\{5\}\)⋯\\cdotsx1Ax\_\{1\}^\{A\}xtA−1Ax\_\{t\_\{A\}\-1\}^\{A\}AA: all taps weight00⋯\\cdotsx1Bx\_\{1\}^\{B\}xtB−1Bx\_\{t\_\{B\}\-1\}^\{B\}BB: all taps weight00mergemergemerge

Figure 2:\(L\)The Wheatstone edge substitutionΦW​\(A1,…,A5\)\\Phi\_\{W\}\(A\_\{1\},\\dots,A\_\{5\}\)\.\(R\)Merging two instances of clamped min\-subarray: the two sources, the two sinks, and the last internal vertex ofAAwith the first internal vertex ofBB\.

## 6Conclusion

The triality \(Theorem[1](https://arxiv.org/html/2608.25034#Thmtheorem1)\) means that compositional structure discovered in any one of the three languages — graph, algebra, polyhedron — transfers exactly to the others\. The invariant calculus then characterizes the full redundancy in the DAG encoding, identifying which structural differences are artifacts of the representation rather than intrinsic properties of the computed function\. The negative results constrain equivariant architecture design\. Semiring\-native substitutions cannot lift the polyhedral geometry from lengthTTto lengthT\+1T\{\+\}1\(Section[4](https://arxiv.org/html/2608.25034#S4)\), and the compositional symmetries available to Bellman\-style reasoning are doubly incomplete: series\-parallel does not generate all DAG topologies, and terminal\-only operations do not capture all DP compositions \(Section[5](https://arxiv.org/html/2608.25034#S5)\)\. Together these bound what\(min,\+\)\(\\min,\+\)structure alone in an architecture can achieve for length generalization, and point toward richer compositional operations that would be needed\.

## Acknowledgments and Disclosure of Funding

This work was partially supported by the NSF Division of Mathematical Sciences: Statistics Program DMS 2409819, and by the Peter Buck Student Internship Fund administered by Bowdoin College\. The authors thank Baran Hashemi \(Postdoctoral Scholar, MPI MiS Leipzig\) for his generous feedback prior to submission\.

## References

- Anil et al\. \[2022\]Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur\-Ari, Ethan Dyer, and Behnam Neyshabur\.Exploring length generalization in large language models\.In*Advances in Neural Information Processing Systems*, volume 35, 2022\.
- Bellman \[1957\]Richard Bellman\.*Dynamic Programming*\.Princeton University Press, 1957\.
- Delétang et al\. \[2023\]Grégoire Delétang, Anian Ruoss, Jordi Grau\-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A\. Ortega\.Neural networks and the chomsky hierarchy\.In*The Eleventh International Conference on Learning Representations*, 2023\.
- Duffin \[1965\]R\. J\. Duffin\.Topology of series\-parallel networks\.*Journal of Mathematical Analysis and Applications*, 10\(2\):303–318, 1965\.
- Gondran and Minoux \[1979\]Michel Gondran and Michel Minoux\.*Graphes et algorithmes*\.Eyrolles, 1979\.English translation: Graphs and Algorithms, Wiley, 1984\.
- Hashemi et al\. \[2025\]Baran Hashemi, Kurt Pasque, Chris Teska, and Ruriko Yoshida\.Tropical attention: Neural algorithmic reasoning for combinatorial algorithms\.In*The Thirty\-ninth Annual Conference on Neural Information Processing Systems*, 2025\.URL[https://openreview\.net/forum?id=3CbwwCpsSk](https://openreview.net/forum?id=3CbwwCpsSk)\.
- Joswig \[2021\]Michael Joswig\.*Essentials of Tropical Combinatorics*, volume 219 of*Graduate Studies in Mathematics*\.American Mathematical Society, 2021\.
- Maclagan and Sturmfels \[2015\]Diane Maclagan and Bernd Sturmfels\.*Introduction to Tropical Geometry*, volume 161 of*Graduate Studies in Mathematics*\.American Mathematical Society, 2015\.
- Rockafellar \[1970\]R\. Tyrrell Rockafellar\.*Convex Analysis*\.Princeton University Press, 1970\.
- Valdes et al\. \[1982\]Jacobo Valdes, Robert E\. Tarjan, and Eugene L\. Lawler\.The recognition of series parallel digraphs\.*SIAM Journal on Computing*, 11\(2\):298–313, 1982\.
- Zhang et al\. \[2018\]Liwen Zhang, Gregory Naitzat, and Lek\-Heng Lim\.Tropical geometry of deep neural networks\.In*Proceedings of the 35th International Conference on Machine Learning*, pages 5824–5832, 2018\.

## Appendix ASeries and parallel composition

sAs\_\{A\}AAzA=sBz\_\{A\}\{=\}s\_\{B\}BBzBz\_\{B\}seriesA;BA;B:distA;B=distA\+distB\\ \\dist\_\{A;B\}=\\dist\_\{A\}\+\\dist\_\{B\}ssAABBzzparallelA\|BA\\\|B:distA\|B=min⁡\(distA,distB\)\\ \\dist\_\{A\\\|B\}=\\min\(\\dist\_\{A\},\\dist\_\{B\}\)Figure 3:Series and parallel composition of two\-terminal DAGs: series identifieszAz\_\{A\}withsBs\_\{B\}, parallel identifies the two sources and the two sinks\.
## Appendix BTropical geometry in a nutshell

This appendix collects the definitions and examples needed to read the main text\. We follow the conventions of Joswig\[[Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7)\]and Maclagan–Sturmfels\[[Maclagan and Sturmfels, 2015](https://arxiv.org/html/2608.25034#bib.bib8)\]; proofs and formal statements are in Appendix[C](https://arxiv.org/html/2608.25034#A3)\.

### B\.1The tropical semiring

The*tropical semiring*is the set𝕋=ℝ∪\{\+∞\}\\mathbb\{T\}=\\mathbb\{R\}\\cup\\\{\+\\infty\\\}equipped with the operations:*tropical addition*a⊕b≔min⁡\(a,b\)a\\oplus b\\coloneqq\\min\(a,b\)and*tropical multiplication*a⊙b≔a\+ba\\odot b\\coloneqq a\+b\. The additive identity is\+∞\+\\infty\(min⁡\(a,\+∞\)=a\\min\(a,\{\+\}\\infty\)=a\) and the multiplicative identity is00\(a\+0=aa\+0=a\)\. Every finite element has a multiplicative inverse \(a⊙\(−a\)=0a\\odot\(\-a\)=0\), but tropical addition is*idempotent*:a⊕a=aa\\oplus a=a, so no finite element has an additive inverse and𝕋\\mathbb\{T\}is a semiring, not a ring\. The\(max,\+\)\(\\max,\+\)convention is equivalent under negation; we use\(min,\+\)\(\\min,\+\)throughout, aligned with shortest\-path formulations\.

### B\.2Tropical polynomials

A*tropical monomial*c⊙x1⊙α1⊙⋯⊙xd⊙αdc\\odot x\_\{1\}^\{\\odot\\alpha\_\{1\}\}\\odot\\cdots\\odot x\_\{d\}^\{\\odot\\alpha\_\{d\}\}\(withα∈ℤ≥0d\\alpha\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{d\},c∈ℝc\\in\\mathbb\{R\}\) evaluates to the affine functionc\+α1​x1\+⋯\+αd​xd=c\+⟨α,x⟩c\+\\alpha\_\{1\}x\_\{1\}\+\\cdots\+\\alpha\_\{d\}x\_\{d\}=c\+\\langle\\alpha,x\\rangle, since tropical exponentiation is repeated addition:x⊙k=k​xx^\{\\odot k\}=kx\.

A*tropical polynomial*is a finite tropical sum of monomials:

f⁡\(x\)=⨁α∈Scα⊙x⊙α=minα⁡\(cα\+⟨α,x⟩\)\.f\(x\)=\\bigoplus\_\{\\alpha\\in S\}c\_\{\\alpha\}\\odot x^\{\\odot\\alpha\}=\\min\_\{\\alpha\}\\bigl\(c\_\{\\alpha\}\+\\langle\\alpha,x\\rangle\\bigr\)\.Its graph is the lower envelope of finitely many affine functions — piecewise linear and concave\.

###### Example 5\(A univariate tropical polynomial\)\.

Letf⁡\(x\)=4⊕\(2⊙x\)⊕\(1⊙x⊙2\)⊕\(3⊙x⊙3\)=min⁡\(4,2\+x,1\+2​x,3\+3​x\)f\(x\)=4\\oplus\(2\\odot x\)\\oplus\(1\\odot x^\{\\odot 2\}\)\\oplus\(3\\odot x^\{\\odot 3\}\)=\\min\(4,\\;2\{\+\}x,\\;1\{\+\}2x,\\;3\{\+\}3x\)\. Its graph is the lower envelope of four lines \(Figure[4](https://arxiv.org/html/2608.25034#A2.F4)\)\. The envelope bends atx=−2,1,2x=\-2,1,2; this is the tropical vanishing set \(the points where two or more monomials tie for the minimum\)\.

#### Formal vs\. function\.

Two formal polynomials can evaluate to the same function: for instance,min⁡\(0,x,2​x\)=min⁡\(0,2​x\)\\min\(0,x,2x\)=\\min\(0,2x\)for allxx, because the monomialxxis never the unique minimizer\. This formal/function distinction is what the two rows of the triality \(Theorem[1](https://arxiv.org/html/2608.25034#Thmtheorem1)\) capture\.

#### Support and lifted support\.

The*support*S⁡\(f\)=\{α:cα≠\+∞\}S\(f\)=\\\{\\alpha:c\_\{\\alpha\}\\neq\{\+\}\\infty\\\}records which monomials are present\. The*lifted support*S^​\(f\)=\{\(α,cα\):α∈S⁡\(f\)\}⊂ℝd×ℝ\\hat\{S\}\(f\)=\\\{\(\\alpha,c\_\{\\alpha\}\):\\alpha\\in S\(f\)\\\}\\subset\\mathbb\{R\}^\{d\}\\times\\mathbb\{R\}raises each exponent to its coefficient height\. When two terms share an exponent, their tropical sum keeps the lesser coefficient; this per\-exponent reduction is calledvmin\\vmin\(vertical minimum\), and a polynomial in*normal form*has been reduced byvmin\\vmin\.

### B\.3The geometric dictionary

#### The dome\.

The region weakly below the graph,𝒟⁡\(f\)=\{\(x,s\)∈ℝd×ℝ:s≤f⁡\(x\)\}\\mathcal\{D\}\(f\)=\\\{\(x,s\)\\in\\mathbb\{R\}^\{d\}\\times\\mathbb\{R\}:s\\leq f\(x\)\\\}, is a convex polyhedron cut out by one half\-space per monomial\. Each facet of𝒟⁡\(f\)\\mathcal\{D\}\(f\)is the locus where one monomial is the unique minimizer; the function bends exactly at the ridges \(codimension\-22faces\) of𝒟⁡\(f\)\\mathcal\{D\}\(f\)\.

3\+3​x3\{\+\}3x1\+2​x1\{\+\}2x2\+x2\{\+\}x44xxss𝒟⁡\(f\)\\mathcal\{D\}\(f\)Figure 4:The dome𝒟⁡\(f\)\\mathcal\{D\}\(f\)off=min⁡\(4,2\+x,1\+2​x,3\+3​x\)f=\\min\(4,\\;2\{\+\}x,\\;1\{\+\}2x,\\;3\{\+\}3x\)from Example[5](https://arxiv.org/html/2608.25034#Thmtheorem5)\. Each facet is a monomial’s locus of dominance; the three vertices of the dome project to the tropical zeroes\{−2,1,2\}\\\{\-2,1,2\\\}\.
#### Newton polytope and extended Newton polyhedron\.

The*Newton polytope*𝒩⁡\(f\)=conv⁡\(S⁡\(f\)\)⊆ℝd\\mathcal\{N\}\(f\)=\\operatorname\{conv\}\(S\(f\)\)\\subseteq\\mathbb\{R\}^\{d\}records which monomials are present, forgetting coefficients\. The*extended Newton polyhedron*

Γ⁡\(f\)=conv⁡\(S^​\(f\)\)\+ℝ≥0​ed\+1\\Gamma\(f\)=\\operatorname\{conv\}\\bigl\(\\hat\{S\}\(f\)\\bigr\)\+\\mathbb\{R\}\_\{\\geq 0\}\\,e\_\{d\+1\}retains the coefficients: it is the convex hull of the lifted support, extended upward by an infinite ray\. Its lower faces encode the polynomial’s evaluation, and the key fact is thatΓ⁡\(f\)=Γ⁡\(g\)\\Gamma\(f\)=\\Gamma\(g\)if and only ifffandggagree as functions\[[Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7), Thm\. 1\.13\]\.

#### Tropical hypersurface\.

The*tropical hypersurface*

𝒯\(f\)=\{x∈ℝd:the minimum inf\(x\)is attained by≥2monomials\}\\mathcal\{T\}\(f\)=\\\{x\\in\\mathbb\{R\}^\{d\}:\\text\{the minimum in \}f\(x\)\\text\{ is attained by \}\{\\geq\}\\,2\\text\{ monomials\}\\\}is the locus where strategies tie for optimality, i\.e\. a decision boundary\. It is a polyhedral complex of pure dimensiond−1d\-1, the projection of the codimension\-22skeleton of the dome\.

###### Example 6\(The tropical line\)\.

The polynomialf⁡\(x,y\)=0⊕x⊕y=min⁡\(0,x,y\)f\(x,y\)=0\\oplus x\\oplus y=\\min\(0,x,y\)has three monomials\. The tropical hypersurface𝒯⁡\(f\)\\mathcal\{T\}\(f\)consists of three rays emanating from the origin \(Figure[5](https://arxiv.org/html/2608.25034#A2.F5)\):\{x=0≤y\}\\\{x=0\\leq y\\\},\{y=0≤x\}\\\{y=0\\leq x\\\}, and\{x=y≤0\}\\\{x=y\\leq 0\\\}\. Each ray separates two regions of linearity, one per monomial that dominates there\.

x=0x\{=\}0y=0y\{=\}0x=yx\{=\}ys=0s\{=\}0s=xs\{=\}xs=ys\{=\}yFigure 5:The tropical line of Example[6](https://arxiv.org/html/2608.25034#Thmtheorem6): the hypersurface off=min⁡\(0,x,y\)f=\\min\(0,x,y\)is three rays meeting at the origin, separating the three regions on which a single monomial attains the minimum\.

### B\.4Two\-terminal DAGs and path polynomials

A*two\-terminal DAG*is an acyclic directed graph with a designated sourcessand sinkzzsuch that every vertex lies on somess–zzpath\. Its*path polynomial*is

fG\(x\)=⨁π:s→z⨀e∈πwe=minπ:s→z∑e∈πwe,f\_\{G\}\(x\)=\\bigoplus\_\{\\pi\\,:\\,s\\to z\}\\;\\bigodot\_\{e\\in\\pi\}w\_\{e\}=\\min\_\{\\pi\\,:\\,s\\to z\}\\sum\_\{e\\in\\pi\}w\_\{e\}\\,,the tropical sum over allss–zzpaths of the tropical product of edge weights\. Each path contributes one monomial; the polynomial is their tropical sum\.

Series composition \(A;BA;B, identifyingzA=sBz\_\{A\}=s\_\{B\}\) givesfA;B=fA⊙fB=fA\+fBf\_\{A;B\}=f\_\{A\}\\odot f\_\{B\}=f\_\{A\}\+f\_\{B\}; parallel composition \(A\|BA\\\|B, identifying sources and sinks\) givesfA\|B=fA⊕fB=min⁡\(fA,fB\)f\_\{A\\\|B\}=f\_\{A\}\\oplus f\_\{B\}=\\min\(f\_\{A\},f\_\{B\}\)\. ThusG↦fGG\\mapsto f\_\{G\}preserves both∥\\\|and;from two\-terminal DAGs to tropical polynomials — the starting point of the triality in Section[2](https://arxiv.org/html/2608.25034#S2)\.

## Appendix CPolynomials, configurations, and polyhedra

###### Definition 7\.

For a formal tropical polynomialf=minα⁡\(cα\+xα\)f=\\min\_\{\\alpha\}\(c\_\{\\alpha\}\+x^\{\\alpha\}\)inddvariables in normal form \(one least coefficient per exponent\), the*support*isS⁡\(f\)=\{α:cα≠\+∞\}S\(f\)=\\\{\\alpha:c\_\{\\alpha\}\\neq\+\\infty\\\}and the*lifted configuration*isS^​\(f\)=\{\(α,cα\):α∈S⁡\(f\)\}⊆ℝd×ℝ\\hat\{S\}\(f\)=\\\{\(\\alpha,c\_\{\\alpha\}\):\\alpha\\in S\(f\)\\\}\\subseteq\\mathbb\{R\}^\{d\}\\times\\mathbb\{R\}\.

###### Definition 8\.

For finiteS⊆ℤ≥0d×ℝS\\subseteq\\mathbb\{Z\}^\{d\}\_\{\\geq 0\}\\times\\mathbb\{R\},vmin⁡\(S\)\\vmin\(S\)keeps over each exponent occurring inSSonly the least point above it; thusvmin⁡\(S\)=S\\vmin\(S\)=SiffSShas at most one point over each exponent\.

###### Proposition 9\.

Letℒd\\mathcal\{L\}\_\{d\}be the finite subsets ofℤ≥0d×ℝ\\mathbb\{Z\}^\{d\}\_\{\\geq 0\}\\times\\mathbb\{R\}with at most one point over each exponent, with additionvmin⁡\(S∪T\)\\vmin\(S\\cup T\)and multiplicationvmin⁡\{\(α\+α′,cα\+cα′\)\}\\vmin\\\{\(\\alpha\+\\alpha^\{\\prime\},c\_\{\\alpha\}\+c\_\{\\alpha^\{\\prime\}\}\)\\\}\. Thenℒd\\mathcal\{L\}\_\{d\}is a commutative idempotent semiring \(identities∅\\emptysetand\{\(0,0\)\}\\\{\(0,0\)\\\}\), andf↦S^​\(f\)f\\mapsto\\hat\{S\}\(f\)is a semiring isomorphism from normal\-form formal tropical polynomials ontoℒd\\mathcal\{L\}\_\{d\}\.

###### Proof\.

Formal tropical Laurent polynomials are a semiring\[[Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7), Observation 2\.15\]; nonnegative\-exponent configurations form a sub\-semiring containing∅\\emptysetand\{\(0,0\)\}\\\{\(0,0\)\\\}, andf↦S^​\(f\)f\\mapsto\\hat\{S\}\(f\)is a relabelling carrying tropicalmin\\mintovmin\\vminof the union and\+\+tovmin\\vminof the sumset\. ∎

###### Definition 10\.

Forffwith supportSS,Γ⁡\(f\)=conv⁡\{\(α,cα\):α∈S\}\+\(\{0\}×ℝ≥0\)⊆ℝd×ℝ\\Gamma\(f\)=\\operatorname\{conv\}\\\{\(\\alpha,c\_\{\\alpha\}\):\\alpha\\in S\\\}\+\(\\\{0\\\}\\times\\mathbb\{R\}\_\{\\geq 0\}\)\\subseteq\\mathbb\{R\}^\{d\}\\times\\mathbb\{R\}\. Its*lower faces*\(outer normal\(y,1\)\(y,1\)\) project onto𝒩⁡\(f\)=conv⁡\(S\)\\mathcal\{N\}\(f\)=\\operatorname\{conv\}\(S\)\[[Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7), §1\.1\]\.

###### Lemma 11\.

\(i\)Γ⁡\(f\)\\Gamma\(f\)is its lower hull plus the upward ray, so the lower hull determines it\. \(ii\)Γ⁡\(f\)↦f\\Gamma\(f\)\\mapsto fis a bijection from extended Newton polyhedra onto tropical polynomial functions\.\[[Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7), Observation 1\.8, Theorem 1\.13\]

###### Lemma 12\.

Onℒd\\mathcal\{L\}\_\{d\}setS∼TS\\sim Tiffconv⁡\(S\)\+ℝ≥0​ed\+1=conv⁡\(T\)\+ℝ≥0​ed\+1\\operatorname\{conv\}\(S\)\+\\mathbb\{R\}\_\{\\geq 0\}e\_\{d\+1\}=\\operatorname\{conv\}\(T\)\+\\mathbb\{R\}\_\{\\geq 0\}e\_\{d\+1\}\. Then∼\\simis a congruence for\(min,\+\)\(\\min,\+\), andγ:S↦conv⁡\(S\)\+ℝ≥0​ed\+1\\gamma:S\\mapsto\\operatorname\{conv\}\(S\)\+\\mathbb\{R\}\_\{\\geq 0\}e\_\{d\+1\}induces a semiring isomorphismℒd/∼→≅\(\{Γ\},conv\(⋅∪⋅\),\+\)\\mathcal\{L\}\_\{d\}/\\\!\\sim\\ \\xrightarrow\{\\cong\}\(\\\{\\Gamma\\\},\\operatorname\{conv\}\(\\cdot\\cup\\cdot\),\+\)\.

###### Proof of Lemma[12](https://arxiv.org/html/2608.25034#Thmtheorem12)\.

WriteR=ℝ≥0​ed\+1R=\\mathbb\{R\}\_\{\\geq 0\}e\_\{d\+1\}\. EachΓ\\GammasatisfiesΓ\+R=Γ\\Gamma\+R=\\Gamma, hence is determined by its lower support function — the mapx↦min\(α,c\)∈Γ⁡\(⟨α,x⟩\+c\)x\\mapsto\\min\_\{\(\\alpha,c\)\\in\\Gamma\}\(\\langle\\alpha,x\\rangle\+c\), which is exactly the tropical polynomial function carried by the configuration\. The lower support function of a convex hull of a union is the pointwise minimum of the two\[[Rockafellar, 1970](https://arxiv.org/html/2608.25034#bib.bib9), Cor\. 16\.5\.1\], i\.e\.min\\min; the support function of a Minkowski sum is the sum\[[Rockafellar, 1970](https://arxiv.org/html/2608.25034#bib.bib9), Thm\. 13\.3\], i\.e\.\+\+\. A point discarded byvmin\\vminlies onRRabove a retained point and is invisible toγ\\gamma, soγ\\gammaintertwines the operations; that this holds forces∼\\simto be a congruence\.γ⁡\(∅\)=∅\\gamma\(\\emptyset\)=\\emptyset,γ⁡\(\{\(0,0\)\}\)=R\\gamma\(\\\{\(0,0\)\\\}\)=Rare the identities\. ∎

###### Lemma 13\.

Letφ:R→R′\\varphi:R\\to R^\{\\prime\}be a semiring isomorphism andθ,θ′\\theta,\\theta^\{\\prime\}congruences witha𝜃b⇔φ⁡\(a\)θ′φ⁡\(b\)a\\mathbin\{\\theta\}b\\iff\\varphi\(a\)\\mathbin\{\\theta^\{\\prime\}\}\\varphi\(b\)\. Then there is a uniqueφ¯:R/θ→R′/θ′\\bar\{\\varphi\}:R/\\theta\\to R^\{\\prime\}/\\theta^\{\\prime\}withφ¯∘q=q′∘φ\\bar\{\\varphi\}\\circ q=q^\{\\prime\}\\circ\\varphi, and it is a semiring isomorphism\.

###### Proof\.

We must showφ¯​\(\[a\]\)≔\[φ⁡\(a\)\]θ′\\bar\{\\varphi\}\(\[a\]\)\\coloneqq\[\\varphi\(a\)\]\_\{\\theta^\{\\prime\}\}is a well\-defined semiring isomorphismR/θ→R′/θ′R/\\theta\\to R^\{\\prime\}/\\theta^\{\\prime\}\.

*Well\-defined\.*If\[a\]θ=\[b\]θ\[a\]\_\{\\theta\}=\[b\]\_\{\\theta\}, thena𝜃ba\\mathbin\{\\theta\}b, so by hypothesisφ⁡\(a\)θ′φ⁡\(b\)\\varphi\(a\)\\mathbin\{\\theta^\{\\prime\}\}\\varphi\(b\), hence\[φ⁡\(a\)\]θ′=\[φ⁡\(b\)\]θ′\[\\varphi\(a\)\]\_\{\\theta^\{\\prime\}\}=\[\\varphi\(b\)\]\_\{\\theta^\{\\prime\}\}\.

*Injective\.*Ifφ¯​\(\[a\]\)=φ¯​\(\[b\]\)\\bar\{\\varphi\}\(\[a\]\)=\\bar\{\\varphi\}\(\[b\]\), i\.e\.φ⁡\(a\)θ′φ⁡\(b\)\\varphi\(a\)\\mathbin\{\\theta^\{\\prime\}\}\\varphi\(b\), the reverse implication givesa𝜃ba\\mathbin\{\\theta\}b, so\[a\]=\[b\]\[a\]=\[b\]\.

*Surjective\.*For any\[r′\]∈R′/θ′\[r^\{\\prime\}\]\\in R^\{\\prime\}/\\theta^\{\\prime\}, surjectivity ofφ\\varphigivesaawithφ⁡\(a\)=r′\\varphi\(a\)=r^\{\\prime\}, soφ¯​\(\[a\]\)=\[r′\]\\bar\{\\varphi\}\(\[a\]\)=\[r^\{\\prime\}\]\.

*Homomorphism\.*For either operation∗\*\(with∗′\*^\{\\prime\}its counterpart inR′R^\{\\prime\}\):

φ¯​\(\[a\]∗\[b\]\)=φ¯​\(\[a∗b\]\)=\[φ⁡\(a∗b\)\]θ′=\[φ⁡\(a\)∗′φ⁡\(b\)\]θ′=\[φ⁡\(a\)\]θ′∗′\[φ⁡\(b\)\]θ′=φ¯​\(\[a\]\)∗′φ¯​\(\[b\]\),\\bar\{\\varphi\}\(\[a\]\*\[b\]\)=\\bar\{\\varphi\}\(\[a\*b\]\)=\[\\varphi\(a\*b\)\]\_\{\\theta^\{\\prime\}\}=\[\\varphi\(a\)\*^\{\\prime\}\\varphi\(b\)\]\_\{\\theta^\{\\prime\}\}=\[\\varphi\(a\)\]\_\{\\theta^\{\\prime\}\}\*^\{\\prime\}\[\\varphi\(b\)\]\_\{\\theta^\{\\prime\}\}=\\bar\{\\varphi\}\(\[a\]\)\*^\{\\prime\}\\bar\{\\varphi\}\(\[b\]\),using thatφ\\varphiis a homomorphism \(third equality\) and thatθ′\\theta^\{\\prime\}is a congruence \(fourth equality\)\. The identity elements map correctly sinceφ\\varphipreserves them\.

*Uniqueness\.*Anyψ\\psiwithψ∘q=q′∘φ\\psi\\circ q=q^\{\\prime\}\\circ\\varphisatisfiesψ⁡\(\[a\]\)=q′​\(φ⁡\(a\)\)=\[φ⁡\(a\)\]θ′=φ¯​\(\[a\]\)\\psi\(\[a\]\)=q^\{\\prime\}\(\\varphi\(a\)\)=\[\\varphi\(a\)\]\_\{\\theta^\{\\prime\}\}=\\bar\{\\varphi\}\(\[a\]\)\. ∎

###### Proposition 14\.

For two\-terminal DAGs,fA;B=fA\+fBf\_\{A;B\}=f\_\{A\}\+f\_\{B\}andfA\|B=min⁡\(fA,fB\)f\_\{A\\\|B\}=\\min\(f\_\{A\},f\_\{B\}\); hence the two congruences≈f,≈v\\approx\_\{\\mathrm\{f\}\},\\approx\_\{\\mathrm\{v\}\}are compatible with;and∥\\\|\.

###### Proof\.

Thess–zzpaths ofA;BA;Bare concatenations of anAA\-path and aBB\-path, weight the sum, so distributivity givesfA\+fBf\_\{A\}\+f\_\{B\}; those ofA\|BA\\\|Bare the disjoint union, so themin\\minsplits asmin⁡\(fA,fB\)\\min\(f\_\{A\},f\_\{B\}\)\. Normal form commutes with both\. ∎

## Appendix DProof of the triality \(Theorem[1](https://arxiv.org/html/2608.25034#Thmtheorem1)\)

###### Proof\.

WriteΦ:\[G\]↦fG\\Phi:\[G\]\\mapsto f\_\{G\}\.

*\(1\) Formal row\.*Since≈f\\approx\_\{\\mathrm\{f\}\}is a congruence \(Proposition[14](https://arxiv.org/html/2608.25034#Thmtheorem14)\),∥\\;\\\|\\;and;are well\-defined on classes\.

- •*Injective:*by the definition of≈f\\approx\_\{\\mathrm\{f\}\}\.
- •*Operation\-preserving:*by Proposition[14](https://arxiv.org/html/2608.25034#Thmtheorem14)\.
- •*Identities:*the single\+∞\+\\infty\-edge maps to∅\\emptyset, the single00\-edge to\{\(0,0\)\}\\\{\(0,0\)\\\}\.
- •*Surjective:*given normal\-formff, build one chain per support monomial —αi\\alpha\_\{i\}edges labelledxix\_\{i\}and one edge of weightcαc\_\{\\alpha\}— and place the chains in parallel\. Its path polynomial isff\.

SoΦ\\Phiis an isomorphism onto the formal polynomials, a semiring by Proposition[9](https://arxiv.org/html/2608.25034#Thmtheorem9); composing withf↦S^​\(f\)f\\mapsto\\hat\{S\}\(f\)gives the chain\.

*\(2, 3\) Function row\.*Two graphs compute the same function iff their polynomials do iff their extended Newton polyhedra agree, so the three congruences match under the formal\-row isomorphisms and the descent lemma applies\. Concretely, letθG,θF,θℒ\\theta\_\{\\mathrm\{G\}\},\\theta\_\{\\mathrm\{F\}\},\\theta\_\{\\mathcal\{L\}\}be, respectively:

- •\[G\]fθG\[H\]f\[G\]\_\{\\mathrm\{f\}\}\\mathbin\{\\theta\_\{\\mathrm\{G\}\}\}\[H\]\_\{\\mathrm\{f\}\}iffG≈vHG\\approx\_\{\\mathrm\{v\}\}H;
- •fθFgf\\mathbin\{\\theta\_\{\\mathrm\{F\}\}\}giff they evaluate to the same function;
- •∼\\simof Lemma[12](https://arxiv.org/html/2608.25034#Thmtheorem12)\.

NowG≈vHG\\approx\_\{\\mathrm\{v\}\}HifffG,fHf\_\{G\},f\_\{H\}evaluate equally, soθG\\theta\_\{\\mathrm\{G\}\}andθF\\theta\_\{\\mathrm\{F\}\}correspond under\[G\]↦fG\[G\]\\mapsto f\_\{G\}; andfθFgf\\mathbin\{\\theta\_\{\\mathrm\{F\}\}\}giffΓ⁡\(f\)=Γ⁡\(g\)\\Gamma\(f\)=\\Gamma\(g\)\(Lemma[11](https://arxiv.org/html/2608.25034#Thmtheorem11)\(ii\)\) iffS^​\(f\)∼S^​\(g\)\\hat\{S\}\(f\)\\sim\\hat\{S\}\(g\), soθF\\theta\_\{\\mathrm\{F\}\}andθℒ\\theta\_\{\\mathcal\{L\}\}correspond\.θℒ\\theta\_\{\\mathcal\{L\}\}is a congruence \(Lemma[12](https://arxiv.org/html/2608.25034#Thmtheorem12)\), hence so are the others by transport\. Applying Lemma[13](https://arxiv.org/html/2608.25034#Thmtheorem13)to the two isomorphisms of \(1\) with these matched congruences yields the function\-row isomorphisms, and since the vertical maps are the quotient maps, both squares commute\. No operation onΓ\\Gammais recomputed\. ∎

## Appendix EInvariance: normal form and completeness

###### Definition 15\.

A two\-terminal DAG is*deshared*if distinctss–zzpaths meet only atssandzz\(a parallel bundle of chains\)\.Df​\(G\)D\_\{\\mathrm\{f\}\}\(G\)has one canonicalized chain per support monomial offGf\_\{G\};Dv​\(G\)D\_\{\\mathrm\{v\}\}\(G\)deletes additionally every chain whose lifted point lies weakly above the lower hull of the others\. Both may be constructed directly from the path polynomial itself, so DAGsG,G′G,G^\{\\prime\}are equal exactly when their path polynomials are equal\.

###### Lemma 16\.

For a two\-terminal DAGGG, withP⁡\(v\)P\(v\)the number ofss–zzpaths through internal vertexvv, putΠ⁡\(G\)=∑v\(P⁡\(v\)−1\)\\Pi\(G\)=\\sum\_\{v\}\(P\(v\)\-1\)\. Then \(1\)GGis deshared iffΠ⁡\(G\)=0\\Pi\(G\)=0; \(2\) a vertex split is available iffΠ⁡\(G\)\>0\\Pi\(G\)\>0; \(3\) exactlyΠ⁡\(G\)\\Pi\(G\)splits carryGGto deshared form\.

###### Proof\.

By two\-terminality each internalvvhasP⁡\(v\)≥1P\(v\)\\geq 1\.

- \(1\)Π⁡\(G\)=0\\Pi\(G\)=0iff everyP⁡\(v\)=1P\(v\)=1iff every internal vertex has in\- and out\-degree11on the path subgraph, which is desharedness\.
- \(2\)Π⁡\(G\)\>0\\Pi\(G\)\>0iff some vertex has in\- or out\-degree\>1\>1, which admits a split\.
- \(3\)A split ofvvintov1,v2v\_\{1\},v\_\{2\}hasP⁡\(v1\)\+P⁡\(v2\)=P⁡\(v\)P\(v\_\{1\}\)\+P\(v\_\{2\}\)=P\(v\)and changes no otherP⁡\(v′\)P\(v^\{\\prime\}\), so Π​drops by​\(P⁡\(v\)−1\)−\(P⁡\(v1\)−1\)−\(P⁡\(v2\)−1\)=1;\\Pi\\text\{ drops by \}\(P\(v\)\-1\)\-\(P\(v\_\{1\}\)\-1\)\-\(P\(v\_\{2\}\)\-1\)=1;with \(2\), exactlyΠ⁡\(G\)\\Pi\(G\)splits reach deshared form\.

∎

###### Proposition 17\.

The following preserve≈f\\approx\_\{\\mathrm\{f\}\}: \(1\)*series\-run reweighting*— permuting and contracting the edges within a chain, preserving its sum; \(2\)*parallel\-bundle bookkeeping*— reordering parallel branches, combining two with equal exponent bymin\\minof coefficients \(idempotency when equal\), and deleting or adjoining a branch dominated at its own exponent; \(3\)*tropical\-zero adjunction*— adding or removing a parallel\+∞\+\\infty\-edge or a subdividing00\-edge; \(4\)*vertex splitting and merging*\(Figure[6](https://arxiv.org/html/2608.25034#A5.F6)\)\.

###### Proof\.

Write𝒫⁡\(G\)\\mathcal\{P\}\(G\)for the multiset ofss–zzpath monomials\. SincefGf\_\{G\}is themin\\minover𝒫⁡\(G\)\\mathcal\{P\}\(G\)in normal form, it suffices to show each operation leaves𝒫⁡\(G\)\\mathcal\{P\}\(G\)unchanged up to dominated entries\.

- \(1\)The run is unbranched, so every path through it picks up the\+\+\-product of the run’s weights; paths avoiding it are untouched\.
- \(2\)Permuting branches permutes𝒫⁡\(G\)\\mathcal\{P\}\(G\)\. Deletion: the surviving branchAAat the same exponent withcA≤cCc\_\{A\}\\leq c\_\{C\}already attains themin\\min\-least coefficient there\.
- \(3\)A path through a\+∞\+\\infty\-edge has constant\+∞\+\\inftyand is dominated or unsupported; deletion reads the argument backwards\.
- \(4\)Out\-split atwwalongout⁡\(w\)=O1⊔O2\\mathrm\{out\}\(w\)=O\_\{1\}\\sqcup O\_\{2\}; in\-split is symmetric\.*Acyclicity:*a cycle ofG′G^\{\\prime\}throughwjw\_\{j\}maps to a cycle ofGGthroughww\.*Path bijection:*anss–zzpath ofGGmeetingww, entering alonge∈in⁡\(w\)e\\in\\mathrm\{in\}\(w\)and leaving alonge′∈Oje^\{\\prime\}\\in O\_\{j\}, lifts to anss–zzpath ofG′G^\{\\prime\}throughwjw\_\{j\}of the same weight; conversely, a path ofG′G^\{\\prime\}meets at most one ofw1,w2w\_\{1\},w\_\{2\}\(else a cycle exists\), and identifying them recovers a path ofGG\. So𝒫⁡\(G′\)=𝒫⁡\(G\)\\mathcal\{P\}\(G^\{\\prime\}\)=\\mathcal\{P\}\(G\)\. Merging is the inverse\.

∎

p1p\_\{1\}p2p\_\{2\}wwq1q\_\{1\}q2q\_\{2\}e1e\_\{1\}e2e\_\{2\}g1g\_\{1\}g2g\_\{2\}originalp1p\_\{1\}p2p\_\{2\}w1w\_\{1\}w2w\_\{2\}q1q\_\{1\}q2q\_\{2\}e1e\_\{1\}e2e\_\{2\}e1e\_\{1\}e2e\_\{2\}g1g\_\{1\}g2g\_\{2\}out\-split,O1=\{g1\}O\_\{1\}=\\\{g\_\{1\}\\\},O2=\{g2\}O\_\{2\}=\\\{g\_\{2\}\\\}p1p\_\{1\}p2p\_\{2\}w1w\_\{1\}w2w\_\{2\}q1q\_\{1\}q2q\_\{2\}e1e\_\{1\}e2e\_\{2\}g1g\_\{1\}g2g\_\{2\}g1g\_\{1\}g2g\_\{2\}in\-split,I1=\{e1\}I\_\{1\}=\\\{e\_\{1\}\\\},I2=\{e2\}I\_\{2\}=\\\{e\_\{2\}\\\}

Figure 6:The two vertex splits, realizing the distributivity clause of Proposition[17](https://arxiv.org/html/2608.25034#Thmtheorem17)\. Left: an internal vertexwwwith in\-edgese1,e2e\_\{1\},e\_\{2\}and out\-edgesg1,g2g\_\{1\},g\_\{2\}\. Middle: the out\-split alongO1=\{g1\}O\_\{1\}=\\\{g\_\{1\}\\\},O2=\{g2\}O\_\{2\}=\\\{g\_\{2\}\\\}, with each ofw1,w2w\_\{1\},w\_\{2\}carrying its own copy ofe1e\_\{1\}ande2e\_\{2\}\. Right: the in\-split alongI1=\{e1\}I\_\{1\}=\\\{e\_\{1\}\\\},I2=\{e2\}I\_\{2\}=\\\{e\_\{2\}\\\}, with each ofw1,w2w\_\{1\},w\_\{2\}carrying its own copy ofg1g\_\{1\}andg2g\_\{2\}\. In both panels everypi→qjp\_\{i\}\\to q\_\{j\}path of the original survives exactly once\.###### Lemma 18\.

On a bundle of chains with pairwise distinct exponents and no\+∞\+\\infty\-edge, deleting a chain preserves the computed function iff its lifted point\(α,cα\)\(\\alpha,c\_\{\\alpha\}\)lies weakly above the lower hull of the others, iff it is not a vertex ofΓ\\Gamma, iff it is nowhere the unique minimizer \(Figure[7](https://arxiv.org/html/2608.25034#A5.F7)\); and at mostd\+1d\+1chains \(d=dim𝒩⁡\(f\)d=\\dim\\mathcal\{N\}\(f\)\) are needed\. The forward direction \(a certificate⇒\\Rightarrowdeletion preserves the function\) is unconditional\.

###### Proof\.

WritefC​\(x\)=⟨αC,x⟩\+cCf\_\{C\}\(x\)=\\langle\\alpha\_\{C\},x\\rangle\+c\_\{C\}andfAi​\(x\)=⟨αi,x⟩\+cif\_\{A\_\{i\}\}\(x\)=\\langle\\alpha\_\{i\},x\\rangle\+c\_\{i\}; setS′=\{\(αi,ci\)\}i≤rS^\{\\prime\}=\\\{\(\\alpha\_\{i\},c\_\{i\}\)\\\}\_\{i\\leq r\}\.

*Certificate⇒\\Rightarrowdeletion \(unconditional\)\.*A certificate givesN​αC=∑iki​αiN\\alpha\_\{C\}=\\sum\_\{i\}k\_\{i\}\\alpha\_\{i\}andN​cC≥∑iki​ciNc\_\{C\}\\geq\\sum\_\{i\}k\_\{i\}c\_\{i\}, so for everyxx,

N​fC​\(x\)=⟨N​αC,x⟩\+N​cC≥∑iki​fAi​\(x\)≥N​minj​fAj​\(x\)\.Nf\_\{C\}\(x\)=\\langle N\\alpha\_\{C\},x\\rangle\+Nc\_\{C\}\\geq\\sum\_\{i\}k\_\{i\}f\_\{A\_\{i\}\}\(x\)\\geq N\\min\_\{j\}f\_\{A\_\{j\}\}\(x\)\.HencefC≥minj⁡fAjf\_\{C\}\\geq\\min\_\{j\}f\_\{A\_\{j\}\}pointwise, and a branch that never strictly beats the others may be dropped from amin\\minwithout changing it\.

*Equivalences \(under distinctness and no\+∞\+\\infty\)\.*

- •*Not a vertex⇔\\Leftrightarrownowhere the unique minimizer\.*Γ⁡\(fB\)\\Gamma\(f\_\{B\}\)recedes in theed\+1e\_\{d\+1\}direction, so every supporting functional with positive last coordinate scales to\(α,c\)↦⟨α,x⟩\+c\(\\alpha,c\)\\mapsto\\langle\\alpha,x\\rangle\+cfor somexx; its minimum onΓ⁡\(fB\)\\Gamma\(f\_\{B\}\)is the bundle’s value atxx, attained uniquely at\(αC,cC\)\(\\alpha\_\{C\},c\_\{C\}\)iffCCis the unique minimizer there\.
- •*Nowhere unique minimizer⇔\\Leftrightarrowdeletion preserves the function\.*The value of the bundle changes atxxiffCCis the unique minimizer atxx\.
- •*Weakly above the lower hull⇔\\Leftrightarrownot a vertex\.*Γ⁡\(fB\)=conv⁡\(S′∪\{\(αC,cC\)\}\)\+ℝ≥0​ed\+1\\Gamma\(f\_\{B\}\)=\\operatorname\{conv\}\(S^\{\\prime\}\\cup\\\{\(\\alpha\_\{C\},c\_\{C\}\)\\\}\)\+\\mathbb\{R\}\_\{\\geq 0\}e\_\{d\+1\}\. If\(αC,cC\)∈Γ⁡\(S′\)\(\\alpha\_\{C\},c\_\{C\}\)\\in\\Gamma\(S^\{\\prime\}\)it is a convex combination of points other than itself, hence not extreme; conversely, if not extreme it lies inΓ⁡\(S′\)\\Gamma\(S^\{\\prime\}\)because all other extreme points belong toS′S^\{\\prime\}\.

*Support bound\.*Weakly above the lower hull meansαC∈conv⁡\(\{αi\}\)\\alpha\_\{C\}\\in\\operatorname\{conv\}\(\\\{\\alpha\_\{i\}\\\}\)withcC≥h⁡\(αC\)c\_\{C\}\\geq h\(\\alpha\_\{C\}\), wherehhis the lower\-hull function ofS′S^\{\\prime\}\. By Carathéodory,αC\\alpha\_\{C\}lies in a simplex of at mostd\+1d\+1vertices ofconv⁡\(\{αi\}\)\\operatorname\{conv\}\(\\\{\\alpha\_\{i\}\\\}\), with rational barycentric coordinatesλi≥0\\lambda\_\{i\}\\geq 0,∑λi=1\\sum\\lambda\_\{i\}=1, and∑λi​ci=h⁡\(αC\)≤cC\\sum\\lambda\_\{i\}c\_\{i\}=h\(\\alpha\_\{C\}\)\\leq c\_\{C\}\. Clearing the common denominatorNNgiveski=N​λi∈ℕk\_\{i\}=N\\lambda\_\{i\}\\in\\mathbb\{N\}: a certificate supported on at mostd\+1d\+1chains\. ∎

sszz00xxxxc≥0c\\geq 0xxmiddle chain deleted

α\\alphaheight001122\(1,c\)\(1,c\)

Figure 7:Mediant deletion \(Lemma[18](https://arxiv.org/html/2608.25034#Thmtheorem18)\) on the familyGc=0​‖\(x;x\)‖​\(c,x\)G\_\{c\}=0\\,\\\|\\,\(x;x\)\\,\\\|\\,\(c;x\), computingmin⁡\(0,c\+x,2​x\)\\min\(0,\\,c\+x,\\,2x\)\. Left: the middle chain \(weightc≥0c\\geq 0thenxx\) is deleted for everyc≥0c\\geq 0, leavingmin⁡\(0,2​x\)\\min\(0,2x\)\. Right: the lifted points and extended Newton polyhedron\.###### Proof of Theorem[2](https://arxiv.org/html/2608.25034#Thmtheorem2)\.

- \(i\)*Reduction\.*By Lemma[16](https://arxiv.org/html/2608.25034#Thmtheorem16),Π⁡\(G\)\\Pi\(G\)vertex splits deshareGG\. Within each chain, Proposition[17](https://arxiv.org/html/2608.25034#Thmtheorem17)\(1\) sorts the variable edges and contracts the trailing constants to one edge; a\+∞\+\\infty\-chain contracts to a single\+∞\+\\infty\-edge and is deleted by \(3\)\. Two chains sharing an exponent have equal variable prefixes and differ only in a final constant; merging their prefix vertices \(inverse out\-splits\) leaves a parallel pairc\|c′c\\\|c^\{\\prime\}, replaced bymin⁡\(c,c′\)\\min\(c,c^\{\\prime\}\)via \(2\) \(idempotency deletes exact duplicates\)\. What remains is one chain per support monomial, i\.e\.Df​\(G\)D\_\{\\mathrm\{f\}\}\(G\)\. For the mediant pass, the vertices ofΓ⁡\(fG\)\\Gamma\(f\_\{G\}\)are fixed and every non\-vertex chain fails Lemma[18](https://arxiv.org/html/2608.25034#Thmtheorem18), so is deletable against the vertices; performing all such deletions leavesDv​\(G\)D\_\{\\mathrm\{v\}\}\(G\)\.
- \(ii\)*Canonicity\.*Df​\(G\)D\_\{\\mathrm\{f\}\}\(G\)is a function offGf\_\{G\}alone \(Definition[15](https://arxiv.org/html/2608.25034#Thmtheorem15)\), soDf​\(G\)=Df​\(G′\)D\_\{\\mathrm\{f\}\}\(G\)=D\_\{\\mathrm\{f\}\}\(G^\{\\prime\}\)ifffG=fG′f\_\{G\}=f\_\{G^\{\\prime\}\}, i\.e\.≈f\\approx\_\{\\mathrm\{f\}\}\. The mediant pass keeps exactly the vertices ofΓ\\Gamma, and two functions agree iff their polyhedra, hence vertex sets, agree \(Lemma[11](https://arxiv.org/html/2608.25034#Thmtheorem11)\(ii\)\), giving the≈v\\approx\_\{\\mathrm\{v\}\}statement and decidability\.
- \(iii\)*Connectivity\.*Each formal move is invertible \(merging inverts splitting, adjunction inverts deletion, etc\.\), so the reduction path of \(i\) can be reversed\. Two graphsG,G′G,G^\{\\prime\}with the same canonical form are therefore connected byG→D⁡\(G\)=D⁡\(G′\)→G′G\\to D\(G\)=D\(G^\{\\prime\}\)\\to G^\{\\prime\}; by \(ii\), same canonical form is equivalent to congruence\. Conversely each move preserves the class\.

∎

Table 1:The calculus of invariant operations on DAGs derived from tropical semiring properties\.
## Appendix FGeometry of the two substitutions

###### Definition 19\.

Writeπi:ℝd→ℝd−1\\pi\_\{i\}:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{d\-1\}for deletion of coordinateii,α−i=πi​\(α\)\\alpha\_\{\-i\}=\\pi\_\{i\}\(\\alpha\), andπ^i=πi×idℝ\\hat\{\\pi\}\_\{i\}=\\pi\_\{i\}\\times\\mathrm\{id\}\_\{\\mathbb\{R\}\}for its lift keeping the height\. The shadow usesπ^i​\(Γ​\(f\)\)\\hat\{\\pi\}\_\{i\}\(\\Gamma\(f\)\), which retains coefficients;πi​\(𝒩​\(f\)\)\\pi\_\{i\}\(\\mathcal\{N\}\(f\)\)forgets them\.

###### Definition 20\.

For a polyhedral complex𝒞\\mathcal\{C\}andv≠0v\\neq 0,recv⁡\(𝒞\)=\{C∈𝒞:v∈rec⁡\(C\)\}\\operatorname\{rec\}\_\{v\}\(\\mathcal\{C\}\)=\\\{C\\in\\mathcal\{C\}:v\\in\\operatorname\{rec\}\(C\)\\\}is the subcomplex of cells stable under translation byvv\[[Joswig, 2021](https://arxiv.org/html/2608.25034#bib.bib7), §A\]\.

###### Proof of Proposition[3](https://arxiv.org/html/2608.25034#Thmtheorem3)\.

PiP\_\{i\}acts by a single transformation across the three languages by the triality \(Theorem[1](https://arxiv.org/html/2608.25034#Thmtheorem1)\): the rule “setxi=\+∞x\_\{i\}=\+\\infty” respects≈f\\approx\_\{\\mathrm\{f\}\}, hence descends to classes and has one avatar in each language\.

*Algebra\.*WithS^=S^​\(fG\)\\hat\{S\}=\\hat\{S\}\(f\_\{G\}\), the sign ofαi\\alpha\_\{i\}partitionsS^=S^i\>⊔S^i0\\hat\{S\}=\\hat\{S\}^\{\>\}\_\{i\}\\sqcup\\hat\{S\}^\{0\}\_\{i\}\(αi\>0\\alpha\_\{i\}\>0resp\.=0=0\)\. Since\+∞\+\\inftyis absorbing for\+\+, settingxi=\+∞x\_\{i\}=\+\\inftykills every monomial withαi≥1\\alpha\_\{i\}\\geq 1and fixes the rest with coefficients, soS^​\(Pi​\(fG\)\)=S^i0\\hat\{S\}\(P\_\{i\}\(f\_\{G\}\)\)=\\hat\{S\}^\{0\}\_\{i\}; writinghhfor theS^i\>\\hat\{S\}^\{\>\}\_\{i\}block,fG=min⁡\(h,Pi​\(fG\)\)f\_\{G\}=\\min\(h,P\_\{i\}\(f\_\{G\}\)\)\.

*Geometry\.*The exponents lie inℤ≥0t\+1\\mathbb\{Z\}^\{t\+1\}\_\{\\geq 0\}and the upward ray fixes coordinateii, soΓ\(fG\)⊆\{αi≥0\}\\Gamma\(f\_\{G\}\)\\subseteq\\\{\\alpha\_\{i\}\\geq 0\\\}; hence\{αi=0\}\\\{\\alpha\_\{i\}=0\\\}is supporting andΓ\(fG\)∩\{αi=0\}\\Gamma\(f\_\{G\}\)\\cap\\\{\\alpha\_\{i\}=0\\\}is a \(possibly empty\) face, carrying exactlyS^i0\\hat\{S\}^\{0\}\_\{i\}\. For the hypersurface, takefGf\_\{G\}in function form\. A cell of𝒯⁡\(fG\)\\mathcal\{T\}\(f\_\{G\}\)has an argmin setσ\\sigma; those withσ⊆S^i0\\sigma\\subseteq\\hat\{S\}^\{0\}\_\{i\}are stable under increasingxix\_\{i\}\(noxix\_\{i\}appears\), while anyσ\\sigmacontaining a monomial withαi\>0\\alpha\_\{i\}\>0is eventually dominated by a surviving one, so leaves the cell\. Thus the cells stable in directioneie\_\{i\}are exactly those onS^i0\\hat\{S\}^\{0\}\_\{i\}, i\.e\.recei⁡\(𝒯⁡\(fG\)\)\\operatorname\{rec\}\_\{e\_\{i\}\}\(\\mathcal\{T\}\(f\_\{G\}\)\); projecting byπi\\pi\_\{i\}gives𝒯​\(Pi​\(fG\)\)\\mathcal\{T\}\(P\_\{i\}\(f\_\{G\}\)\), providedS^i0≠∅\\hat\{S\}^\{0\}\_\{i\}\\neq\\emptyset\(elsePi​\(fG\)=\+∞P\_\{i\}\(f\_\{G\}\)=\+\\infty\)\.

*Graph\.*Thess–zzpaths through anxix\_\{i\}\-edge acquire weight\+∞\+\\inftyand drop out of themin\\min; those avoidingEiE\_\{i\}are the paths ofG∖EiG\\setminus E\_\{i\}with unchanged weight, sofG\|xi=\+∞=fG∖Eif\_\{G\}\|\_\{x\_\{i\}=\+\\infty\}=f\_\{G\\setminus E\_\{i\}\}\.

*TheQiQ\_\{i\}column\.*QiQ\_\{i\}is evaluation atxi=0x\_\{i\}=0, a semiring homomorphism, so it acts term by term: the term atα\\alphabecomescα\+x−iα−ic\_\{\\alpha\}\+x\_\{\-i\}^\{\\alpha\_\{\-i\}\}, eachxix\_\{i\}contributing the\+\+\-identity00\.

*Algebra\.*In lifted coordinatesQi​\(fG\)Q\_\{i\}\(f\_\{G\}\)is themin\\minover the projected setA=π^i​\(S^​\(fG\)\)A=\\hat\{\\pi\}\_\{i\}\(\\hat\{S\}\(f\_\{G\}\)\); asπi\\pi\_\{i\}need not be injective on the support,AAmay carry several points over one exponent, and normal form keeps the least:

S^​\(Qi​\(fG\)\)=vmin⁡\(A\),support​πi​\(S⁡\(fG\)\),coefficient​min⁡\{cα:πi​\(α\)=β\}\.\\hat\{S\}\(Q\_\{i\}\(f\_\{G\}\)\)=\\vmin\(A\),\\quad\\text\{support \}\\pi\_\{i\}\(S\(f\_\{G\}\)\),\\quad\\text\{coefficient \}\\min\\\{c\_\{\\alpha\}:\\pi\_\{i\}\(\\alpha\)=\\beta\\\}\.
*Geometry\.*Adding the upward rayRRabsorbs the pointsvmin\\vmindiscards, each lying onRRabove a retained one, so

Γ⁡\(Qi​\(fG\)\)=conv⁡\(A\)\+R=π^i​\(Γ⁡\(fG\)\),\\Gamma\(Q\_\{i\}\(f\_\{G\}\)\)=\\operatorname\{conv\}\(A\)\+R=\\hat\{\\pi\}\_\{i\}\(\\Gamma\(f\_\{G\}\)\),sinceπ^i\\hat\{\\pi\}\_\{i\}is linear and fixesRR\.

*Hypersurface\.*AsQi​\(fG\)Q\_\{i\}\(f\_\{G\}\)isfGf\_\{G\}restricted to\{xi=0\}\\\{x\_\{i\}=0\\\}, a tie ofQi​\(fG\)Q\_\{i\}\(f\_\{G\}\)is one offGf\_\{G\}on that slice and conversely, save that two monomials sharing aπi\\pi\_\{i\}\-image agree on the whole slice and merge into one; their common wall fills a full\-dimensional cell on which a single monomial ofQi​\(fG\)Q\_\{i\}\(f\_\{G\}\)dominates, and removing those relative interiors is the stated correction\.

*Graph\.*ReweightingEiE\_\{i\}to00substitutesxi=0x\_\{i\}=0into every path monomial, and the two normalizing moves are invariant; this is reweighting rather than contraction, which can create or destroy anss–zzpath and so misrepresentsQiQ\_\{i\}\.

*Qi≤PiQ\_\{i\}\\leq P\_\{i\}\.*The coordinate face lies in the coordinate shadow:

Γ\(Pi\(fG\)\)=π^i\(Γ\(fG\)∩\{αi=0\}\)⊆π^i\(Γ\(fG\)\)=Γ\(Qi\(fG\)\),\\Gamma\(P\_\{i\}\(f\_\{G\}\)\)=\\hat\{\\pi\}\_\{i\}\\\!\\bigl\(\\Gamma\(f\_\{G\}\)\\cap\\\{\\alpha\_\{i\}=0\\\}\\bigr\)\\subseteq\\hat\{\\pi\}\_\{i\}\\\!\\bigl\(\\Gamma\(f\_\{G\}\)\\bigr\)=\\Gamma\(Q\_\{i\}\(f\_\{G\}\)\),and since tropical addition of functions is the convex hull of the union of their polyhedra,min⁡\(Qi​\(fG\),Pi​\(fG\)\)=Qi​\(fG\)\\min\(Q\_\{i\}\(f\_\{G\}\),P\_\{i\}\(f\_\{G\}\)\)=Q\_\{i\}\(f\_\{G\}\), i\.e\.Qi​\(fG\)≤Pi​\(fG\)Q\_\{i\}\(f\_\{G\}\)\\leq P\_\{i\}\(f\_\{G\}\)\. ∎

###### Corollary 21\.

For a tropical polynomialggin the variables\{xj:j≠i\}\\\{x\_\{j\}:j\\neq i\\\},

Pi−1​\(g\)=\{g⊕h:every monomial of​h​has​αi≥1\},P\_\{i\}^\{\-1\}\(g\)=\\bigl\\\{\\,g\\oplus h\\;:\\;\\text\{every monomial of \}h\\text\{ has \}\\alpha\_\{i\}\\geq 1\\,\\bigr\\\},Qi−1\(g\)=\{⨁β∈S⁡\(g\)cβg⊙x−i⊙β⊙xi⊙kβ⊕r:kβ∈ℕ,πi\(S\(r\)\)⊆S\(g\),cαr≥cπi​\(α\)g\}\.Q\_\{i\}^\{\-1\}\(g\)=\\Bigl\\\{\\,\\bigoplus\_\{\\beta\\in S\(g\)\}c\_\{\\beta\}^\{g\}\\odot x\_\{\-i\}^\{\\odot\\beta\}\\odot x\_\{i\}^\{\\odot k\_\{\\beta\}\}\\;\\oplus\\;r\\;:\\;k\_\{\\beta\}\\in\\mathbb\{N\},\\;\\pi\_\{i\}\(S\(r\)\)\\subseteq S\(g\),\\;c\_\{\\alpha\}^\{r\}\\geq c\_\{\\pi\_\{i\}\(\\alpha\)\}^\{g\}\\,\\Bigr\\\}\.The shapes are opposite:PiP\_\{i\}pins theαi=0\\alpha\_\{i\}=0layer and frees everything above positionii, whileQiQ\_\{i\}frees the exponentkβk\_\{\\beta\}at positioniiand constrains everything above the fiber minimum\.

###### Proof of Corollary[21](https://arxiv.org/html/2608.25034#Thmtheorem21)\.

*PiP\_\{i\}\-fiber\.*By the algebraic clause, everyf=min⁡\(g,h\)f=\\min\(g,h\)with each monomial ofhhcarryingαi≥1\\alpha\_\{i\}\\geq 1hasS^​\(f\)=S^​\(g\)⊔S^​\(h\)\\hat\{S\}\(f\)=\\hat\{S\}\(g\)\\sqcup\\hat\{S\}\(h\)andPi​\(f\)=gP\_\{i\}\(f\)=g\. Conversely anyffnot of that form either omits a monomial ofgg, forcingS⁡\(Pi​\(f\)\)⊊S⁡\(g\)S\(P\_\{i\}\(f\)\)\\subsetneq S\(g\), or contributes a monomial withαi=0\\alpha\_\{i\}=0beyondgg, forcingS⁡\(g\)⊊S⁡\(Pi​\(f\)\)S\(g\)\\subsetneq S\(P\_\{i\}\(f\)\)\.

*QiQ\_\{i\}\-fiber\.*QiQ\_\{i\}is a homomorphism, so any

gk=minβ⁡\(cβg\+x−iβ\+kβ​xi\)g\_\{k\}=\\min\_\{\\beta\}\\bigl\(c\_\{\\beta\}^\{g\}\+x\_\{\-i\}^\{\\beta\}\+k\_\{\\beta\}x\_\{i\}\\bigr\)hasQi​\(gk\)=gQ\_\{i\}\(g\_\{k\}\)=g, since eachkβ​xik\_\{\\beta\}x\_\{i\}evaluates to00\. Forf=min⁡\(gk,r\)f=\\min\(g\_\{k\},r\),

Qi\(f\)=min\(g,Qi\(r\)\)=g⇔Qi\(r\)≥gpointwise;Q\_\{i\}\(f\)=\\min\(g,\\,Q\_\{i\}\(r\)\)=g\\quad\\iff\\quad Q\_\{i\}\(r\)\\geq g\\text\{ pointwise\};by the algebraic clause that isπi​\(S⁡\(r\)\)⊆S⁡\(g\)\\pi\_\{i\}\(S\(r\)\)\\subseteq S\(g\)together withcαr≥cπi​\(α\)gc\_\{\\alpha\}^\{r\}\\geq c\_\{\\pi\_\{i\}\(\\alpha\)\}^\{g\}at every monomial ofrr\. ∎

## Appendix GEdge substitutions and the series\-parallel boundary

###### Definition 22\.

For a two\-terminal DAGHHwithrrlabeled edges, the*edge substitution*ΦH\\Phi\_\{H\}sends two\-terminal DAGsA1,…,ArA\_\{1\},\\dots,A\_\{r\}to the two\-terminal DAG obtained by replacing edgeiiofHHwithAiA\_\{i\}, identifying the edge’s endpoints withAiA\_\{i\}’s source and sink\. Series composition is the edge substitution into a two\-edge path; parallel composition is the edge substitution into a pair of parallel edges\.

###### Definition 23\.

A two\-terminal DAG is*series\-parallel*\(SP\) if built from a singles→zs\\to zedge by series and parallel compositions\. The*Wheatstone graph*WWisK4K\_\{4\}minus an edge, the smallest non\-SP two\-terminal DAG\.

###### Theorem 24\([Duffin, 1965](https://arxiv.org/html/2608.25034#bib.bib4),[Valdes et al\., 1982](https://arxiv.org/html/2608.25034#bib.bib10)\)\.

A two\-terminal DAG is SP iff it contains no subgraph homeomorphic toWW\.

###### Proof of Proposition[4](https://arxiv.org/html/2608.25034#Thmtheorem4)\.

Specializing eachAiA\_\{i\}to a single edge, a series\-parallel composite of single edges is SP \(Definition[23](https://arxiv.org/html/2608.25034#Thmtheorem23)\); butΦW\\Phi\_\{W\}on five single edges isWW, non\-SP by Theorem[24](https://arxiv.org/html/2608.25034#Thmtheorem24)\. ∎