text:
# A note on the classical lower bound for a quantum walk algorithm

## 1 Introduction

Almost all the quantum algorithms with exponential speedup over their best known classical counterparts use some type of quantum Fourier transform—even for problems (such as shifted quadratic characters) which are not obvious instances of the Hidden Subgroup problem. However, a recent paper on quantum walks \[CCD+03\] does not fall into this category. They demonstrate that exponential speedup can be achieved by a different algorithmic technique, the quantum walk. They give a polynomial-time quantum algorithm to solve a black-box graph traversal problem, based on a continuous time quantum walk. Their paper contains three major results: the continuous time quantum walk algorithm itself, its implementation by a circuit with (discrete) quantum gates, and an exponential lower bound for solving the problem classically. We refer to their paper for a detailed description. Here we concentrate on improving their classical lower bound.

They showed that any classical algorithm solving the problem of traversing $`G_n^{}`$ (see Figure 2 in \[CCD+03\]) requires exponential time:

###### Theorem 1.1 (\[CCD+03, Theorem 6\])

Any classical algorithm that makes at most $`2^{n/6}`$ queries to the oracle finds the EXIT with probability at most $`42^{n/6}`$.

In this note we use a more straightforward approach to analyze this problem. Our analysis also considers some cases Childs et al. neglected. Furthermore, we obtain an improved lower bound, as stated in the following theorem.

###### Theorem 1.2

Any classical algorithm that makes at most $`2^{n/3}`$ queries to the oracle finds the EXIT with probability at most $`O(n2^{n/3})`$.

## 2 An improved analysis on the classical lower bound

In this section we generally refer to the set-up in Childs et al. \[CCD+03\]. Our improvement essentially comes from the calculation of the probability that a classical randomized algrorithm wins Game 4. We do not need to consider subtrees of $`G_n^{}`$ of height $`n/2`$.

###### Lemma 2.1 (cf. \[CCD+03, Lemma 10\])

For any rooted tree $`T`$ of at most $`2^{n/3}`$ vertices,

$$\underset{T}{\mathrm{max}}E_G[P^G(T)]=O(n2^{n/3}).$$

Proof. Let $`T`$ be a tree with $`t`$ vertices, $`t2^{n/3}`$, with image $`\pi (T)`$ in $`G_n^{}`$ under the random embedding $`\pi `$. For any nonroot node $`uT`$, let $`p(u)T`$ be the parent of $`u`$.

We assume that in $`G_n^{}`$, the ENTRANCE is at level $`0`$ and the EXIT is at level $`2n+1`$, and the middle layer is between levels $`n`$ and $`n+1`$. Thus both binary trees have height $`n`$. To reach the EXIT from the column $`n+1`$, $`\pi `$ has to move right $`n`$ times in a row, which has probability $`2^n`$. Since there are at most $`t`$ tries on each path of $`T`$, and there are at most $`t`$ such paths, the probability of finding the EXIT $`\mathrm{Pr}[T\text{ exits on }G_n^{}]`$ is bounded by $`t^22^n`$.

Now assume that $`\pi (T)`$ does not exit. It is easy to see that

$`\mathrm{Pr}[\pi \text{ is improper}]`$ $`=`$ $`{\displaystyle \underset{a,bT}{}}\mathrm{Pr}[\pi (a)=\pi (b)\&\pi (p(a))\pi (p(b))]`$ (1)
$`=`$ $`{\displaystyle \underset{a,bT}{}}{\displaystyle \underset{uG_n^{}}{}}\mathrm{Pr}[\pi (a)=\pi (b)=u\&\pi (p(a))\pi (p(b))].`$ (2)
We calculate $`\mathrm{Pr}[\pi (a)=\pi (b)=u]`$ first for fixed $`a,bT`$, and $`uG_n^{}`$. Let the *height* of $`u`$ be the distance $`h`$ from $`u`$ to a leaf of the subtree that $`u`$ is in. That is, if $`u`$ is at level $`\mathrm{}n`$, then $`h=n\mathrm{}`$, and if $`u`$ is at level $`\mathrm{}n+1`$, then $`h=\mathrm{}n1`$.

Look at the two paths $`p_a`$ and $`p_b`$ in $`T`$ from the root to $`a`$ and to $`b`$, respectively. Either both paths go through the middle layer of $`G_n^{}`$ or only one path goes through the middle layer (at least one path must go through the middle layer). Assume first that both paths go through the middle layer.

Assume WLOG that $`p_b`$ goes through the middle layer at least as many times as $`p_a`$. From the last time $`p_a`$ goes through the middle layer, in order to reach $`u`$ it must first reach some (possibly improper) ancester $`v`$ of $`u`$. If $`v`$ has height $`h^{}`$, then the probability of $`p_a`$ getting to $`v`$ from just before the last middle layer is $`2^h^{}2^h^{}/(2^nt)=1/(2^nt)`$. Once reaching $`v`$, the probability of then going to $`u`$ is then $`2^{hh^{}}`$. So the probability of $`p_a`$ reaching $`u`$ is at most

$$\underset{h^{}=h}{\overset{n}{}}\frac{2^{hh^{}}}{2^nt}<\frac{2}{2^nt}.$$

By our WLOG assumption, there is a final subpath $`p_b^{}`$ of $`p_b`$ not on $`p_a`$ that goes through the middle layer before reaching $`u`$. By the same analysis, we get that $`p_b^{}`$ reaches $`u`$ with probability less than $`2/(2^nt)`$. The probabilities of both paths reaching $`u`$ is thus less than $`4/(2^nt)^2`$. (The two paths $`p_a`$ and $`p_b^{}`$ are almost independent, but not quite; the dependence only decreases the true probability from the product above, however. With a finer analysis, one can reduce the probability to $`3/[2(2^nt)^2]`$.)

Now assume that only one path, say $`p_b`$ goes through the middle layer, and that $`\pi (a)=\pi (b)=u`$. Then $`a`$ is an ancestor of $`b`$ with depth $`n`$ in $`T`$, and $`\pi (a)`$ is the leftmost point of the cycle, lying in the left half of $`G_n^{}`$. The probability that $`p_a`$ ends with $`u`$ is thus at most $`2^{hn}`$, where $`h`$ is the height of $`u`$. Let $`p_b^{}`$ be defined as before. Then by an analysis similar to that above, $`p_b^{}`$ ends in $`u`$ with probability $`1/(2^nt)`$ (note that $`p_b^{}`$ approaches $`u`$ from the right, i.e., it cannot go through a proper ancestor of $`u`$ first). By (almost) independence, we then have in this case,

$$\mathrm{Pr}[\pi (a)=\pi (b)\&\pi (p(a))\pi (p(b))]\frac{2^{hn}}{2^nt}.$$

Summing this probability over $`u`$ in the left half of $`G_n^{}`$, we get

$$\underset{u}{}\frac{2^{hn}}{2^nt}=\underset{h=0}{\overset{n}{}}2^{nh}\frac{2^{hn}}{2^nt}=\frac{n+1}{2^nt}.$$

We can now easily compute the sum (1). We get that $`\pi `$ is improper with probability less than

$`{\displaystyle \underset{a,bT}{}}\left(2^{n+2}{\displaystyle \frac{4}{(2^nt)^2}}+{\displaystyle \frac{n+1}{2^nt}}\right)`$
$``$ $`{\displaystyle \frac{t^2}{2^nt}}\left({\displaystyle \frac{2^{n+2}}{2^nt}}+n+1\right)`$
$`=`$ $`O(n2^{n/3})`$
if $`t2^{n/3}`$. $`\mathrm{}`$


format: text

text:
# On the Topology and H-Flux of T-Dual Manifolds

## Abstract

We present a general formula for the topology and $`H`$-flux of the T-dual of a type II compactification. Our results apply to T-dualities with respect to any free circle action. In particular we find that the manifolds on each side of the duality are circle bundles whose curvatures are given by the integral of the dual $`H`$-flux over the dual circle. As a corollary we conjecture an obstruction to multiple T-dualities, generalizing the obstruction known to exist on the twisted torus. Examples include $`SU(2)`$ WZW models, Lens spaces and the supersymmetric string theory on the non-$`spin`$ $`\text{AdS}^5\times P^2\times S^1`$ compactification.

T-duality is a generalization of the $`R1/R`$ invariance of string theory compactified on a circle of radius $`R`$. The local transformation rules of the low energy effective fields under T-duality, known as the Buscher rules Bus , have been known for some time. However in cases in which there is a topologically nontrivial NS 3-form $`H`$-flux the Buscher rules only make sense on each local spacetime patch. Several examples of T-duals to such backgrounds have been found AABL ; DLP ; GLMW ; KSTT  and in each case it was seen that T-duality changes not only the $`H`$-flux but also the spacetime topology. While any new set of equivalences between compactifications may be useful for model-building, T-dualities involving $`H`$-flux have also led to the surprising discovery of the new physical phenomenon “supersymmetry without supersymmetry” in Refs. Bak ; DLP .

In this letter, which is a physicists perspective of Ref. us , we will present a general formula for the topology and $`H`$-flux of a compactification from the topology and $`H`$-flux of its T-dual. As supporting evidence, we have shown us  that locally our formula agrees with the Buscher rules and that globally it yields an isomorphism of the twisted K-theory-valued conserved RR charges MM ; Wib ; BM . Here we will demonstrate that our formula reproduces the old examples of topology change and easily generates many more. Proofs, physical motivations, more complete referencing and several applications (including some tantalizingly mysterious clues to F-theory) may be found in the companion paper Ref. us .

Henceforth we will restrict our attention to type IIA and IIB string theory on 10-manifolds $`E`$ and $`\widehat{E}`$, respectively, which admit the free circle actions

$$f:S^1\times EE,\widehat{f}:\widehat{S^1}\times \widehat{E}\widehat{E}.$$
(1)
The space of orbits of these actions are 9-manifolds which we call $`M`$ and $`\widehat{M}`$. The freeness of the actions implies that each orbit is a loop and that none of these loops degenerate. As a result $`E`$ and $`\widehat{E}`$ are circle bundles over the bases $`M`$ and $`\widehat{M}`$, and so their topologies are entirely determined by the topology of their bases together with the curvatures $`F`$, $`\widehat{F}`$ (the first Chern classes of the bundles).

As we will see nontrivial bundles are T-dual to configurations with $`H`$-flux. Thus we will need to include the fluxes $`H`$ and $`\widehat{H}`$ in our two compactifications. The two configurations are then topologically determined by the triplets $`(M,F,H)`$ and $`(\widehat{M},\widehat{F},\widehat{H})`$ where $`M`$ and $`\widehat{M}`$ are 9-manifolds, $`F`$ and $`\widehat{F}`$ are two-forms on $`M`$ and $`\widehat{M}`$, and $`H`$ and $`\widehat{H}`$ are three-forms on the total spaces $`E`$ and $`\widehat{E}`$. To capture the topology of a configuration it will suffice to consider the fieldstrengths and Chern classes as elements of integral cohomology. This perspective is useful in that it automatically identifies some gauge equivalent configurations, excludes configurations not satisfying some equations of motion and imposes the Dirac quantization conditions.

Our Result: The compactifications topologically specified by $`(M,F,H)`$ and $`(\widehat{M},\widehat{F},\widehat{H})`$ are T-dual if

$$M\widehat{M},F=_{\widehat{S^1}}\widehat{H},\widehat{F}=_{S^1}H.$$
(2)
This condition determines, at the level of cohomology, the curvatures $`F`$ and $`\widehat{F}`$. However the NS fieldstrengths are only determined up to the addition of a three-form on the base $`M`$, because the integral of such a form over the circle fiber vanishes. We further impose that the two dual three-forms on $`M`$ must be equal, as is made precise in Ref. us , where the duality map of the RR fields (viewed both as elements of cohomology and of K-theory) can also be found.

In the remainder of this letter we will provide examples and applications of our result. When the curvatures $`F`$ and $`\widehat{F}`$ are topologically trivial (in the second cohomology of $`M`$) the bundles are trivial and so our two spacetimes are both topologically the trivial bundle $`M\times S^1`$. Using the Künneth formula we may decompose the third cohomology of the total space $`M\times S^1`$

$`H^3(M\times S^1)=H^3(M)H^0(S^1)`$
$`H^2(M)H^1(S^1)=H^3(M)H^2(M),`$ (3)
and so the NS fluxes $`H`$ and $`\widehat{H}`$, being elements of $`H^3(M\times S^1)`$, decompose as $`H=\alpha +\beta d\theta ,\widehat{H}=\widehat{\alpha }+\widehat{\beta }d\theta ,`$ where $`\alpha ,\widehat{\alpha }H^3(M)`$, $`\beta ,\widehat{\beta }H^2(M)`$, and $`d\theta `$ is the generator of $`H^1(S^1)=`$. Integrating $`H`$ and $`\widehat{H}`$ over the circle, using the normalization $`𝑑\theta =1`$, our result yields $`\alpha =\widehat{\alpha }`$, $`\beta =\widehat{\beta }=0`$. Thus we reproduce the original examples of T-duality, in which spacetime is the product of a 9-manifold and a circle and the $`H`$-flux is an element of the cohomology of the 9-manifold. As expected the T-dual is also a product manifold and carries the same $`H`$-flux.

The next most trivial case is a trivial circle bundle with $`H`$-flux, which we see from (2) is T-dual to a nontrivial bundle without $`H`$-flux. In this case our result was demonstrated using S-duality and also using the $`E_8`$ gauge bundle formalism in Ref. us .

The simplest nontrivial circle bundle is the Hopf fibration over the 2-sphere. This bundle is constructed by cutting the 2-sphere into a northern $`S_N^2`$ and southern hemisphere $`S_S^2`$, over which the circle is trivially fibered. The two hemispheres are then glued together along the equator. In particular, each point on the equator is specified by a longitude $`\theta `$ and the attaching map identifies the point $`\varphi `$ on the fibre over one hemisphere to the point $`\varphi +\theta `$ on the other. The total space of this bundle is then the three-sphere $`S^3`$ and the curvature $`F`$ is the generator $`[1]`$ of $`H^2(S^2)=`$.

Now we may consider a type II string theory compactification on a 3-sphere crossed with an irrelevant 7-manifold, express the 3-sphere as the circle bundle above, and then T-dualize with respect to the circle fiber.

Let us begin with a case in which there is no $`H`$-flux, such as a type IIB compactification of $`\text{AdS}^3\times T^4\times S^3`$ supported by RR flux. Applying Eqn. (2) with $`F=[1]H^2(S^2)`$ and $`H=0`$ we find $`\widehat{F}=[0]`$ and $`\widehat{H}=[1]H^3(S^2\times S^1)`$. Thus our nontrivial bundle $`S^3`$ becomes the trivial bundle $`S^2\times S^1`$, supported by one unit of $`H`$-flux. Incidentally the construction in Ref. us  tells us that if there was RR 3-form flux $`G_3=[k]H^3(S^3)`$ on the $`S^3`$ then we will find $`\widehat{G}_2=[k]H^2(S^2)`$, whereas the $`G_3`$-flux on the $`\text{AdS}^3`$ becomes $`\widehat{G}_4`$-flux on $`\text{AdS}^3\times S^1`$. This is in accord with the usual intuition in which T-duality toggles whether an RR flux extends along the circle, except that here we see that this intuition may apply even when the circle is nontrivially fibered. One might think that this would be impossible in general because, for example here, there is no first cohomology class corresponding to the circle in the 3-sphere. This is potentially problematic because, for example, an arbitrary integral Romans mass $`\widehat{G}_0H^0(S^2\times S^1)`$ cannot be dual to an element $`G_1H^1(S^3)`$ since $`H^1(S^3)=0`$. Here we are saved from any contradiction by the supergravity equation of motion $`\widehat{G}_0H=0`$ which implies that $`\widehat{G}_0=[0]`$. More generally we are saved by the quantum corrected equations of motion, which are given by the Freed-Witten anomaly FW .

A famous application of the previous example is the T-duality of string theory on $`^{8,1}\times S^1`$ with an NS5-brane extended along the plane $`^{5,1}^{8,1}`$ and localized at a point $`\theta S^1`$. Such an NS5-brane is linked by an $`S^2\times S^1`$ where $`S^2^{8,1}`$ links the $`^{5,1}`$ plane. Recalling that NS5-branes are magnetic sources for NS-flux, Gauss’ law allows us to integrate $`_{S^2\times S^1}H=1`$ and so

$$H=[1]H^3(S^2\times S^1)=.$$
(4)
As we have seen a T-duality along this circle replaces $`S^2\times S^1`$ with a 3-sphere and the $`H`$-flux disappears. As the $`H`$-flux has disappeared the T-dual compactification has no NS5-brane, instead it has been replaced by a circle bundle which is nontrivially fibered over each sphere linking the 6-submanifold where the NS5-brane was. This submanifold is now a Kaluza-Klein monopole for the dual $`U(1)`$. Thus we have recovered the familiar fact that NS5-branes are T-dual to KK-monopoles (see, e.g., Ton  and references therein). If instead of a single NS5-brane we had considered a stack of $`k`$ NS5-branes then we would have had $`H=[k]`$ and so the dual bundle would again have been nontrivial, this time yielding a KK-monopole charge of $`k`$. More generally we may consider nontrivial circle bundles and nontrivial $`H`$-flux at the same time. For example, string theory on the Lens space $`S^3/_j`$ with $`k`$ units of $`H`$-flux is T-dual to string theory on $`S^3/_k`$ with $`j`$ units of $`H`$-flux MMS .

An example of T-duality that has recently received attention in the literature KSTT  is the duality between circle bundles over a 2-torus $`T^2`$. In particular one may start with a 3-torus, which is the trivial circle bundle over a 2-torus, with $`k0`$ units of $`H`$-flux and then T-dualize with respect to the circle fiber. As above, $`F=[0]H^2(T^2)=`$ and $`H=[k]H^3(T^3)=`$ determine the dual curvature and NS flux

$`\widehat{F}`$ $`=[k]H^2(T^2)=,`$
$`\widehat{H}`$ $`=[0]H^3(\widehat{E})=.`$ (5)
Here the dual manifold $`\widehat{E}`$, commonly refered to as a twisted torus or nilmanifold, is the circle bundle over $`T^2`$ characterized entirely by the curvature $`\widehat{F}=[k]`$.

We may also try to T-dualize a larger subtorus of the original $`T^3`$. This means that after T-dualizing with respect to the fiber circle we may then try to T-dualize with respect to one of the circles in the base. As has been found in Ref. KSTT , this is impossible. In particular after the first circle is T-dualized, the other two circles have ceased to be globally defined and so cannot be T-dualized. Had they both been globally defined we could have defined a nowhere-vanishing section of this nontrivial circle bundle. Thus in general we see that it is impossible to T-dualize with respect to any 3-torus supporting $`H`$-flux. In fact, the example in Ref. KSTT  suggests the stronger result that one cannot T-dualize on a 2-torus, unless $`_{T^2}H=0`$ in cohomology.

A critical check of any proposed duality is that the anomalies match on both sides. Although a more general matching of a particular gravitino anomaly was demonstrated in Ref. us , here we will describe one family of examples which illustrate the general pattern. Consider the famous type IIB string theory compactification on $`\text{AdS}^5\times S^5`$. The 5-sphere $`S^5`$ is a circle bundle over the projective plane $`\text{P}^2`$ with a single unit of curvature $`F=[1]H^2(\text{AdS}^5\times \text{P}^2)=H^2(\text{P}^2)=`$. The second equality is a result of the fact that $`\text{AdS}^5`$ is contractible and so it does not contribute to the cohomology groups; we may thus freely omit it from such equations. The third cohomology group of this spacetime is trivial and so the $`H`$-flux must be topologically trivial. In addition there is a RR 5-form fieldstrength $`G_5=[N]H^5(S^5)`$. There is also $`G_5`$-flux along the noncompact directions.

T-dualizing with respect to the fiber circle we find that the dual curvature $`\widehat{F}`$ vanishes. The dual manifold is thus $`\text{AdS}^5\times \text{P}^2\times S^1`$. Eqn. (2) is only satisfied if the dual NS fieldstrength is

$`\widehat{H}`$ $`=[1]H^3(\text{AdS}^5\times \text{P}^2\times S^1)`$
$`=H^2(\text{P}^2)H^1(S^1)==.`$ (6)
The $`G_5`$-flux becomes $`\widehat{G}_4=[N]H^4(\text{P}^2)=`$ and $`\widehat{G}_6`$ is supported in the noncompact directions crossed with the circle. In particular there is no $`\widehat{G}_2`$-flux and therefore the M-theory circle is trivially fibered, meaning that this configuration is dual to M-theory compactified on $`\text{AdS}^5\times \text{P}^2\times T^2`$. Notice that $`\text{P}^2`$ is not $`spin`$, and so this is an M-theory compactification on a non-$`spin`$ manifold. This might seem impossible, because the low energy effective supergravity has a gravitino and so there must be a $`spin`$ structure. But in fact this compactification was seen to be perfectly consistent and even supersymmetric (although the supergravity truncation is not supersymmetric, as the winding modes are required to complete the supermultiplets) in Ref. DLP . To see this, notice that the potential gravitino anomaly should be visible in the low energy theory, in which we throw away KK-modes along the torus. This leaves an effective 9-dimensional theory in which the gravitino is electrically charged under a $`U(1)`$ gauge fieldstrength which is the integral of $`H`$ over the dual circle. By Eqn. (2) this integral is just the original curvature $`F`$, so we see that our result implies that the original (IIB) circle is the $`U(1)`$ gauge bundle under which the gravitino is charged. This fact would have been obvious if we had dimensionally reduced the IIB side instead. When $`F`$ is odd the Skyrme effect then assures that the gravitino is in fact a boson and so its phase is well-defined even on a spacetime which is not $`spin`$. In our case $`F=[1]`$ and so the compactification is consistent.

On the other hand, in the case $`F=[2]`$ the gravitino still behaves as a fermion and so the IIA configuration is inconsistent. In this case the IIB spacetime is $`\text{AdS}^5\times \text{P}^5`$ which is an inconsistent background in the absence of an orientifold plane. Our result only applies to oriented theories, and in particular this IIB compactification is inconsistent in an oriented theory, in agreement with the inconsistency of the IIA side of the duality. In fact, the total anomalies on both sides always agree: it seems as though both sides are free from this anomaly when the F-theory 12-manifold is $`spin`$ us . This connection to F-theory is tantalizing and mysterious.

The Roček-Verlinde RV  approach to T-duality should be applicable to circle bundles with nontrivial H-flux as well, hopefully reproducing our result directly within the non-linear sigma model context. In fact such an approach has already been attempted in Ref. AABL , but this program may be significantly easier with a proposal already at hand. We hope that such an approach would also shed light on the observed obstruction to T-dualizing 2-subtorii that support a topologically nontrivial $`H`$ flux. A more difficult problem is to generalize our results to non-free circle actions DP , this may yield a formula for the topology of mirror manifolds.

Acknowledgements
We would like to thank Nick Halmagyi, Michael Schulz and Eric Sharpe for help and crucial references. PB and VM are financially supported by the Australian Research Council and JE by the INFN Sezione di Pisa.


text:
# Evidence for Black Hole Spin in GX 339-4: XMM-Newton EPIC-pn and RXTE Spectroscopy of the Very High State

## 1. Introduction

Irradiation of an accretion disk orbiting a black hole by a source of hard X-rays can produce a fluorescent Fe K$`\alpha `$ emission line, which should bear the signatures of the strong Doppler shifts and gravitational redshifts (Fabian et al. 1989; see also George & Fabian 1991). If the black hole has near-maximal spin ($`a0.998`$, where $`a=cJ/GM^2`$), the innermost stable circular orbit (ISCO) around the black hole can be as small as $`r_{in}=1.24r_g`$ (where $`r_g=GM/c^2`$, note $`r_{in}=6r_g`$ for $`a=0`$); this proximity is expected to produce Fe K$`\alpha `$ emission line profiles with strong red wings because of the relative importance of gravitational red-shifts in comparison to Doppler shifts (Laor 1991).

In the X-ray spectra of supermassive black holes in AGN and stellar-mass black holes in Galactic black hole candidates, skewed Fe K$`\alpha `$ line profiles have proved to be extremely important diagnostics of the innermost relativistic regime (for AGN, see, e.g., Tanaka et al. 1995; for BHCs, see, e.g., Miller et al. 2002a; for a review see Reynolds & Nowak 2003). In some cases, evidence for black hole spin may be inferred by the line shape (for AGN, see, e.g., Iwasawa et al. 1999, Wilms et al. 2001, Fabian et al. 2003; for BHCs see, e.g., Miller et al. 2002b, Miller et al. 2004, Miniuti, Fabian, & Miller 2004).

GX 339$``$4 is a recurrent, dynamically-constrained BHC ($`M_{BH}5.8M_{}`$; Hynes et al. 2003) in which radio jets with $`v/c>0.9`$ have recently been observed (Gallo et al. 2004). Herein, we report on the time-averaged 76 ksec XMM-Newton/EPIC-pn and 10 ksec RXTE spectra of GX 339$``$4, obtained during a bright phase (near 1 Crab in soft X-rays) of its 2002–2003 outburst.

## 2. Observation and Data Reduction

GX 339$``$4 was observed with XMM-Newton for 75.6 ksec, starting on 29 September 2002 09:06:42 UT (revolution 514). The EPIC-pn camera (Strüder et al. 2001) was operated in “burst” mode to accommodate the high count rate expected during this observation. The “thin” optical blocking filter was used. The data were reduced using the XMM-Newton suite SAS version 5.4.1, and the guidelines described in the MPE “cookbook” (see http://wave.xray.mpe.mpg.de/xmm/cookbook). Events were extracted in a stripe in RAWX (31.5–40.5) versus RAWY (2.5–178.5) space. Due to the extremely high source flux background events were not extracted. The events were then filtered by requiring “FLAG=0” (to reject bad pixels and events too close to chip edges) and “PATTERN $``$ 4” (to accept singles and doubles), and the spectral channels were grouped by a factor of 5 to create a spectrum. The appropriate canned burst mode response file was used to fit the spectrum.

RXTE observed GX 339$``$4 for 9.6 ksec starting on 29 September 2002 09:12:11:28. The data were reduced using the suite LHEASOFT version 5.2. Standard time filtering (primarily, filtering-out the SAA) returned net PCA and HEXTE exposures of 9.3 ksec and 3.3 ksec, respectively. For this analysis, we have only made use of the spectra from PCU-2 (the best-calibrated PCU at the time of writing) and HEXTE-A. Events from all layers of PCU-2 were combined to make spectra; “pcabackest” and the bright source background model were used to make background spectra. We added 0.75% systematic errors to the spectrum from PCU-2 using the tool “grppha”. A response matrix (combining rmf and arf files) was generated using “pcarsp”. The HEXTE spectral files were made using the standard recipes, and the standard canned responses were used to fit the data. The PCU-2 spectrum was fit in the 2.8–25.0 keV band (standard for RXTE analysis; see, e.g., Park et al. 2003), and the HEXTE spectrum was fit on the 20.0–100.0 keV band (the upper bound was fixed by the upper bound over which the ionized disk reflection model is valid). These RXTE spectra were fit jointly with an overall normalizing constant allowed to float between them. An edge was added at 4.78 keV with $`\tau =0.1`$ to correct for an instrumental Xe edge at this energy in fits to the PCA spectrum.

## 3. Analysis and Results

Fits to the XMM-Newton/EPIC-pn spectrum, and joint fits to the EPIC-pn and RXTE spectra do not yield formally acceptable fits for the models discussed below. A number of sharp, narrow calibration uncertainties remain in the EPIC-pn detector response. For the most part, these appear as absorption lines or edges in the 2–3 keV range (a feature at 2.31 keV appears as an emission line), though similar features are present in the 0.7–2.0 keV band. Most of these features are likely due to Au M-shell edges and Si features in the detector; they are revealed clearly in this observation due to the high signal-to-noise achieved. These narrow-band features do not affect measurements of the Fe K$`\alpha `$ emission line profile, but they do affect the overall $`\chi ^2`$ fit statistic. Due to these complications, within this analysis we use the broad-band capacity of RXTE to characterize the continuum to serve as a guide for fitting the EPIC-pn data, and reserve detailed joint fits for future work. All fits were made using XSPEC version 11.2.0 (Arnaud 1996). All errors in this work are 90% confidence errors.

The “Laor” model (Laor 1991) describes the line profiles expected around a Kerr black hole. The parameters of this model are the line energy $`E_{Laor}`$, the disk emissivity index $`q`$ (where the emissivity is assumed to have a power-law form of $`J(r)r^q`$; $`q=3`$ is expected for a standard disk), the inner radius of the line emission region $`r_{in}`$ in units of $`r_g=GM/c^2`$ (with a lower limit of $`r_{in}=1.235r_g`$ for $`a=0.998`$), the outer line emission radius (fixed to the model limit of $`R_{out}=400r_g`$), the disk inclination, and the line normalization.

The “pexriv” reflection model (Magdziarz & Zdziarksi 1995) describes reflection from an ionized accretion disk, and does not explicitly include Fe K$`\alpha `$ line emission. The important parameters in this model are the reflection fraction $`f`$ ($`f=\mathrm{\Omega }/2\pi `$),

the disk temperature, ionization ($`\xi =L_X/nr^2`$), and inclination, the power-law folding energy ($`E_{fold}`$), and the index and normalization of the power-law flux irradiating the disk. The “constant density ionized disk” reflection model (CDID; Ross, Fabian, & Young 1999; Ballantyne, Iwasawa, & Fabian 2001) is a reflection model which includes Fe K$`\alpha `$ line emission, and is especially well-suited to high ionization regimes. The relevant parameters of this model are $`\mathrm{log}(\xi )`$, $`f`$, and the index and normalization of the power-law flux irradiating the disk.

These disk reflection spectra are calculated in the co-rotating or fluid frame, and so must be convolved (or, “blurred”) with the Laor line element describing the Doppler shifts and gravitational red-shifts expected for an observer in a stationary frame at infinity. In blurring the reflected spectra (and, therefore, the power-law continuum), we linked the parameters of the emission line and blurring function. The disk components were not blurred as the multicolor disk blackbody model (MCD; Mitsuda et al. 1984) — only an approximation to the Shakura & Sunyaev (1973) disk model because it lacks an inner boundary term — may be the best–available model for a disk orbiting a spinning black hole when torques are present at the inner boundary.

### 3.1. Fits to the RXTE Spectra

In fits to the RXTE spectra, the equivalent neutral hydrogen column density was fixed at $`N_H=5.3\times 10^{21}\mathrm{cm}^2`$ (Dickey & Lockman 1990) using the “phabs” model. No reasonable continuum model gives an acceptable fit to the RXTE spectra without the addition of a broad Fe K$`\alpha `$ emission line. In the absence of added line components, the best-fit “canonical” MCD plus power-law model gives $`\chi ^2/\nu =279.8/74`$, the bulk-motion Comptonization model (Shrader & Titarchuk 1999) gives $`\chi ^2/\nu =766.1/74`$, and an MCD plus CompTT (Titarchuk 1994) continuum gives $`\chi ^2/\nu =284.9/72`$ (where $`\nu `$ is the number of degrees of freedom). Adding Gaussian emission line and smeared edge (“smedge”) components to the MCD plus power-law model as an approximation to a reflection model, a good fit is achieved ( $`\chi ^2/\nu =68.2/68`$). The parameters measured via this model are: $`kT=0.84_{0.04}^{+0.06}`$ keV, $`K_{MCD}=2800\pm 600`$, $`\mathrm{\Gamma }=2.5_{0.1}^{+0.2}`$, $`K_{pl}=2.6\pm 0.4`$, $`E_{Gauss}=5.8_{0.8}^{+0.6}`$ keV, FWHM$`=3_2^{+1}`$ keV, $`K_{Gauss}=3_2^{+3}\times 10^2`$, EW$`=300_{100}^{+300}`$ eV, $`E_{smedge}=8.7_{0.9}^{+0.6}`$ keV, $`\tau =0.2_{0.2}^{+0.8}`$, and $`W_{sm}=2_1^{+2}`$ keV (where $`K`$ denotes model normalizations, and the “smedge” energy was constrained to lie in the 7.1–9.3 keV range).

Fits were also made with blurred CDID and pexriv models. Blurring the models for the $`1.24400r_g`$ range and assuming a power-law emissivity of $`q=3.0`$, we found that the data are consistent with strong reflection ($`f1`$) from a highly ionized inner disk ($`\mathrm{log}(\xi )=4.34.4`$). A line equivalent width of $`EW200\pm 80`$ eV was meausured using the pexriv model.

### 3.2. Fits to the XMM-Newton/EPIC-pn Spectrum

Due to the hints of an extremely skewed spectrum found with RXTE, we began by fitting more physical models to the XMM-Newton/EPIC-pn spectrum. Broad line residuals extend down to $``$3 keV regardless of whether models with additive components or single-component (e.g., bulk motion Comptonization) models are used to fit the continuum, which indicates that the continuum does not strongly affect the red wing of the line. The first model we considered included MCD and power-law continuum components, with added Laor line and smeared edge components. The power-law index was constrained to lie within $`\mathrm{\Delta }(\mathrm{\Gamma })0.1`$ of the RXTE-measured values. With this model, we measure the following values: $`N_H=5.1\pm 0.1\times 10^{21}\mathrm{cm}^2`$, $`kT=0.76\pm 0.01`$ keV, $`K_{MCD}=2300_{200}^{+100}`$, $`\mathrm{\Gamma }=2.60_{0.05}`$, $`K_{pl}=2.2_{0.1}^{+0.3}`$, $`E_{Laor}=6.97_{0.20}`$ keV, $`q=5.5_{0.1}^{+0.5}`$, $`r_{in}=2.1_{0.1}^{+0.2}r_g`$, $`i=11_1^{+5}`$ deg., $`K_{laor}=7.7_{1.5}^{+0.5}\times 10^2`$, $`EW_{Laor}=200_{40}^{+10}`$ eV, $`E_{sm}=7.9_{0.4}^{+0.1}`$ keV, $`\tau =0.6_{0.1}^{+0.4}`$, and a smeared edge width of $`W=1.0\pm 0.3`$ keV. An inner radius of $`r_{in}=6r_g`$ (as per a black hole with $`a=0`$) is excluded at more than the 8$`\sigma `$ level of confidence, as is a standard emissivity index of $`q=3`$. This model gives $`\chi ^2/\nu =3456.5/1894`$; the formally unacceptable fit is due to the calibration problems discussed in Section 3.0. A joint fit to the XMM-Newton/EPIC-pn and RXTE spectra using these continuum parameters is shown in Figure 1. These spectral parameters, and the timing properties of the source at the time of this observation (Homan et al. 2004), indicate that GX 339$``$4 was observed in the “very high” state.

Using this model, we measure an unabsorbed flux of $`2.1\times 10^8\mathrm{erg}\mathrm{cm}^2\mathrm{s}^1`$ in the 0.5–10.0 keV band; the power-law contributes 35% of this flux. The total line flux is measured to be $`5.3\times 10^{10}\mathrm{erg}\mathrm{cm}^2\mathrm{s}^1`$, or $`8.4\times 10^2\mathrm{ph}\mathrm{cm}^2\mathrm{s}`$. It should be noted that the best fit without a line component gives $`\chi ^2/\nu =7552/1902`$. Clearly, a broad line component is required at far more than the $`8\sigma `$ level of confidence.

Models which allow the disk emissivity law to assume a broken power-law form, with $`J(r)r^{q_{in}}`$ within radius $`r_q`$, and $`J(r)r^{q_{out}}`$ outside of $`r_q`$, yield statistically improved fits over models assuming simple power-law emissivity laws at more than the $`8\sigma `$ level of confidence.

Allowing for a broken power-law form for the emissivity and a blurred CDID reflection model, we measure: $`N_H=5.5\pm 0.1\times 10^{21}\mathrm{cm}^2`$, $`kT=0.79\pm 0.01`$ keV, $`K_{MCD}=1860\pm 20`$,

$`\mathrm{\Gamma }=2.61_{0.01}^{+0.09}`$, $`K_{CDID}=2.8\pm 0.2\times 10^{26}`$, $`\mathrm{log}(\xi )=4.5_{0.1}^{+0.5}`$, $`f=2.0_{0.2}`$, $`r_{in}=2.9\pm 0.1`$, $`q_{in}=5.5_{0.7}^{+0.5}`$, $`q_{out}=3.0^{+0.6}`$, $`r_q=7\pm 2r_g`$, and $`i=11_1^{+5}`$ deg., for $`\chi ^2/\nu =3887.3/1895`$. This fit to the EPIC-pn spectrum is shown in Figure 2.

Fits with a blurred pexriv model with a broken power-law emissivity ($`\xi =3.0\times 10^4`$, $`kT_{disk}=1.0`$ keV as per Young et al. 2001, $`E_{fold}=200`$ keV, $`r_q=6r_g`$, and $`q_{out}=3`$ were fixed) yielded the following fit parameters: $`N_H=5.3\pm 0.1\times 10^{21}\mathrm{cm}^2`$, $`kT=0.76\pm 0.01`$ keV, $`K_{MCD}=2200\pm 300`$, $`\mathrm{\Gamma }=2.61_{0.01}^{+0.09}`$, $`K_{PL,pexriv}=1.5\pm 0.1`$, $`i=12_2^{+4}`$ deg., $`E_{laor}=6.97_{0.07}`$ keV, $`r_{in}=2.1_{0.3}^{+0.5}`$, $`q_{in}=5.5_{0.2}^{+0.5}`$, $`K_{laor}=7.2\pm 0.3\times 10^2`$, $`EW=210_{60}^{+60}`$ eV, and $`f=1.0_{0.1}^{+0.5}`$, giving $`\chi ^2/\nu =3481.3/1896`$.

The measured inner disk color temperature and high disk ionizations are expected in the very high state. Reflection fractions greater than unity might be taken as indications of light bending effects. All fits show negative residuals above $`E8.08.5`$ keV. Reflection models predict a steeper continuum and also account for ionized Fe K-shell absorption in this range. The observed residuals can be corrected with a phenomenological smeared edge component “$`\tau `$” $`0.5`$,but would be better modeled by refinements to reflection models.

At high mass accretion rates, disks around black holes likely extend to the ISCO. Although the Laor model assumes maximal black hole spin, it is likely broadly valid over a range of high spin parameters. Assuming that $`r_{in}=r_{ISCO}`$ (equivalent to assuming that the inner disk drags matter in the plunging region minimally; see Krolik & Hawley 2002, Reynolds & Begelman 1997, and Young, Ross, & Fabian 1998); equation 2.21 in Bardeen, Press, & Teukolsky (1972) may be used to estimate the spin parameter of the black hole in GX 339$``$4. Using this procedure, the line and reflection fits detailed above suggest that GX 339$``$4 harbors a black hole with $`a0.80.9`$.

## 4. Discussion

We have discovered an extremely skewed Fe K$`\alpha `$ emission line in an XMM-Newton/EPIC-pn spectrum of the Galactic black hole GX 339$``$4. Spectral fits with the Laor relativistic disk line model and a phenomenological continuum, and with the Laor model and self-consistent blurred disk reflection models, provide tight constraints on the nature of the black hole and inner accretion flow in GX 339$``$4. Our fits indicate that the inner disk likely extends to $`r_{in}=23r_g`$, translating to a black hole spin parameter of $`a0.80.9`$. Moreover, an enhanced inner disk emissivity index of $`q=4.86.0`$ is required within $`59r_g`$. Fits with the same models which fix either $`r_{in}=6.0r_g`$ (as per an $`a=0`$ Schwarzschild hole) or $`q=3.0`$ (as per a standard disk), are more than 8$`\sigma `$ worse than the best-fit values summarized here and detailed in the previous section.

X-ray spectroscopy of XTE J1650$``$500 (Miller et al. 2002b, Miniutti, Fabian, & Miller 2003) and MCG–6-30-15 (Wilms et al. 2001, Fabian et al. 2002) has revealed remarkably similar line profiles and inner disk emissivity properties; both XTE J1650$``$500 and MCG–6-30-15 may have spin parameters which are similar to GX 339$``$4. Comparisons of the timing phenomena observed in stellar-mass Galactic black holes and Seyfert galaxies have shown that noise properties may simply scale with mass (Uttley & McHardy 2001). It has also recently been shown that Galactic black holes may have AGN-like warm absorbers (Miller et al. 2004). Our results extend these findings in that they suggest that — at least in certain states — details like enhanced inner disk emissivity are likely similar.

The models we have considered not only constrain the black hole spin parameter, but also the nature of the inner accretion flow geometry. The inner disk must be strongly illuminated by a centrally-concentrated source of hard X-rays. Miniutti & Fabian (2003) have calculated the effects of light bending on Fe K$`\alpha `$ line variability. This model can explain the complex time variability seen in MCG–6-30-15, and appears to describe the behavior of the line strength in XTE J1650$``$500 remarkably well (Miniutti, Fabian, & Miller 2004; Rossi et al. 2003). The light bending model assumes a power-law source of hard X-ray emission above the black hole which moves “vertically” along the black hole and inner disk angular momentum axis. While models for jets in Galactic black holes require that X-ray emission be focused away from the disk (see, e.g., Markoff, Falcke, & Fender 2001), at the base of the jet the flow is less relativistic and the beaming therefore less extreme. It is possible that synchrotron self-Compton emission from the base of a jet may be focused onto the inner disk by light bending (this would represent an extension to the jet reflection considered by Markoff & Nowak 2004). This does not rule-out additional hard X-ray emission from a corona.

Heightened inner disk emissivity of the kind seen in GX 339$``$4 can plausibly be explained by the dissipation of the black hole’s rotational energy via magnetic connections to the inner disk (Blandford & Znajek 1977; see also Gammie 1999 and Li 2003). The emissivity we have measured is above that predicted by magnetic connections to matter in the plunging region ($`q=7/2`$, Agol & Krolik 2000), though it is possible this process could also be at work. It is possible that such processes and the putative illumination of the inner disk region by the base of a jet might be intimately related; indeed, the extraction of black hole spin energy is often invoked as a possible means of powering relativistic jets in AGN.

We are grateful for thoughtful comments of the anonymous referee. JMM gratefully acknowledges support from the NSF through its Astronomy and Astrophysics Postdoctoral Fellowship program. This work is based on observations obtained with XMM-Newton, an ESA science mission with instruments and contributions directly funded by ESA Member States and the USA (NASA).


text:
# The Tropical Totally Positive Grassmannian

## 1. Introduction

Tropical algebraic geometry is the geometry of the tropical semiring $`(,\mathrm{min},+)`$. Its objects are polyhedral cell complexes which behave like complex algebraic varieties. Although this is a very new field in which many basic questions have not yet been addressed (see  for a nice introduction), tropical geometry has already been shown to have remarkable applications to enumerative geometry (see ), as well as connections to representation theory (see , , ).

The classical theory of total positivity concerns matrices in which all minors are positive. However, in the past decade this theory has been extended by Lusztig (see  and ), who introduced the totally positive variety $`G_{>0}`$ in an arbitrary reductive group $`G`$ and the totally positive part $`B_{>0}`$ of a real flag variety $`B`$. In the process, Lusztig discovered surprising connections between his theory of canonical bases for quantum groups and the theory of total positivity.

In this paper we introduce the totally positive part (or positive part, for short) of the tropicalization of an arbitrary affine variety over the ring of Puiseux series, and then investigate what we get in the case of the Grassmannian $`Gr_{k,n}`$. First we give a parameterization of the totally positive part of the Grassmannian, largely based on work of Postnikov , and then we compute its tropicalization, which we denote by $`\mathrm{Trop}^+Gr_{k,n}`$. We identify $`\mathrm{Trop}^+Gr_{k,n}`$ with a polyhedral subcomplex of the $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$-dimensional Gröbner fan of the ideal of Plücker relations, and then show that this fan, modulo its $`n`$-dimensional lineality space, is combinatorially equivalent to an $`(nk1)(k1)`$-dimensional fan which we explicitly describe. As a special case, we show that $`\mathrm{Trop}^+Gr_{2,n}`$ is a fan which appeared in the work of Stanley and Pitman (see ), which parameterizes certain binary trees, and which is combinatorially equivalent to the (type $`A_n`$) associahedron. We also show that $`\mathrm{Trop}^+Gr_{3,6}`$ and $`\mathrm{Trop}^+Gr_{3,7}`$ are fans which are closely related to the fans of the types $`D_4`$ and $`E_6`$ associahedra, which were first introduced in . These results are strikingly reminiscent of the results of Fomin and Zelevinsky , and Scott , who showed that the Grassmannian has a natural cluster algebra structure which is of type $`A_n`$ for $`Gr_{2,n}`$, type $`D_4`$ for $`Gr_{3,6}`$, and type $`E_6`$ for $`Gr_{3,7}`$. (Fomin and Zelevinsky proved the $`Gr_{2,n}`$ case and stated the other results; Scott worked out the cluster algebra structure of all Grassmannians in detail.) Finally, we suggest a general conjecture about the positive part of the tropicalization of a cluster algebra.

## 2. Definitions

In this section we will define the tropicalization and positive part of the tropicalization of an arbitrary affine variety over the ring of Puiseux series. We will then describe the tropical varieties that will be of interest to us.

Let $`𝒞=_{n=1}^{\mathrm{}}((t^{1/n}))`$ and $`=_{n=1}^{\mathrm{}}((t^{1/n}))`$ be the fields of Puiseux series over $``$ and $``$. Every Puiseux series $`x(t)`$ has a unique lowest term $`at^u`$ where $`a^{}`$ and $`u`$. Setting $`\mathrm{val}(f)=u`$, this defines the valuation map $`\mathrm{val}:(𝒞^{})^n^n,(x_1,\mathrm{},x_n)(\mathrm{val}(x_1),\mathrm{},\mathrm{val}(x_n))`$. We define $`^+`$ to be $`\{x(t)𝒞|\text{ the coefficient of the lowest term of }x(t)\text{ is real and positive}\}`$. We will discuss the wisdom of this definition later; for practically all purposes, the reader may think of $`𝒞`$ as if it were $``$ and of $`^+`$ as if it were $`^+`$.

Let $`I𝒞[x_1,\mathrm{},x_n]`$ be an ideal. We define the tropicalization of $`V(I)`$, denoted $`\mathrm{Trop}V(I)`$, to be the closure of the image under $`\mathrm{val}`$ of $`V(I)(𝒞^{})^n`$, where $`V(I)`$ is the variety of $`I`$. Similarly, we define the positive part of $`\mathrm{Trop}V(I)`$, which we will denote as $`\mathrm{Trop}^+V(I)`$, to be the closure of the image under $`\mathrm{val}`$ of $`V(I)(^+)^n`$. Note that $`\mathrm{Trop}V`$ and $`\mathrm{Trop}^+V`$ are slight abuses of notation; they depend on the affine space in which $`V`$ is embedded and not solely on the variety $`V`$.

If $`f𝒞[x_1,\mathrm{},x_n]\{0\}`$, let the initial form $`\mathrm{in}(f)[x_1,\mathrm{},x_n]`$ be defined as follows: write $`f=t^ag`$ for $`a`$ chosen as large as possible such that all powers of $`t`$ in $`g`$ are nonnegative. Then $`\mathrm{in}(f)`$ is the polynomial obtained from $`g`$ by plugging in $`t=0`$. If $`f=0`$, we set $`\mathrm{in}(f)=0`$. If $`w=(w_1,\mathrm{},w_n)^n`$ then $`\mathrm{in}_w(f)`$ is defined to be $`\mathrm{in}(f(x_it^{w_i}))`$. If $`I𝒞[x_1,\mathrm{},x_n]`$ then $`\mathrm{in}_w(I)`$ is the ideal generated by $`\mathrm{in}_w(f)`$ for all $`fI`$. It was shown in  that $`\mathrm{Trop}V(I)`$ consists of the collection of $`w`$ for which $`\mathrm{in}_w(I)`$ contains no monomials. The essence of this proof was the following:

###### Proposition 2.1.

 If $`w^n`$ and $`\mathrm{in}_w(I)`$ contains no monomial then $`V(\mathrm{in}_w(I))(^{})^n`$ is nonempty and any point $`(a_1,\mathrm{},a_n)`$ of this variety can be lifted to a point $`(\stackrel{~}{a}_1,\mathrm{},\stackrel{~}{a}_n)V(I)`$ with the leading term of $`\stackrel{~}{a}_i`$ equal to $`a_it^{w_i}`$.

We now prove a similar criterion to characterize the points in $`\mathrm{Trop}^+V(I)`$.

###### Proposition 2.2.

A point $`w=(w_1,\mathrm{},w_n)`$ lies in $`\mathrm{Trop}^+V(I)`$ if and only if $`\mathrm{in}_w(I)`$ does not contain any nonzero polynomials in $`^+[x_1,\mathrm{},x_n]`$.

In order to prove this proposition, we will need the following result of , which relies heavily on a result of .

###### Proposition 2.3.

 An ideal $`I`$ of $`[x_1,\mathrm{},x_n]`$ contains a nonzero element of $`^+[x_1,\mathrm{},x_n]`$ if and only if $`(^+)^nV(\mathrm{in}_\eta (I))=\mathrm{}`$ for all $`\eta ^n`$.

We are now ready to prove Proposition 2.2.

###### Proof.

Define $`T^n`$ to be the image of $`V(I)(^+)^n`$ under $`\mathrm{val}`$. Let $`U`$ denote the subset of $`^n`$ consisting of those $`w`$ for which $`\mathrm{in}_w(I)`$ contains no polynomials with all positive terms. By definition, $`\mathrm{Trop}^+V(I)`$ is the closure of $`T`$ in $`^n`$. We want to show that the closure of $`T`$ is $`U`$.

It is obvious that $`T`$ lies in $`U`$. $`U`$ is closed, as the property that $`\mathrm{in}_w(f)`$ has only positive terms is open as $`w`$ varies. Thus, the closure of $`T`$ lies in $`U`$.

Conversely, suppose that $`wU`$. Then, by Proposition 2.3, for some $`\eta ^n`$, $`(^+)^nV(\mathrm{in}_\eta (\mathrm{in}_w(I)))\mathrm{}`$. For $`ϵ>0`$ sufficently small, we have $`\mathrm{in}_\eta (\mathrm{in}_w(I))=\mathrm{in}_{ϵ\eta +w}(I)`$. Therefore we can find a sequence $`w_1`$, $`w_2`$, …approaching $`w`$ with $`(^+)^nV(\mathrm{in}_{w_i}(I))\mathrm{}`$.

As $`w`$ varies, $`\mathrm{in}_w(I)`$ takes on only finitely many values, and the subsets of $`^n`$ on which $`\mathrm{in}_w(I)`$ takes a specific value form the relative interiors of the faces of a complete rational complex known as the Gröbner complex (see ). These complexes are actually fans when $`I`$ is defined over $``$ (). Therefore, we may perturb each $`w_i`$, while preserving $`\mathrm{in}_{w_i}(I)`$, in order to assume that the $`w_i^n`$ and we still have $`w_iw`$. Then, by Proposition 2.1, each $`w_iT`$, so $`w`$ is in the closure of $`T`$ as desired. ∎

###### Corollary 2.4.

$`\mathrm{Trop}V(I)`$ and $`\mathrm{Trop}^+V(I)`$ are closed subcomplexes of the Gröbner complex. In particular, they are polyhedral complexes. If $`I`$ is defined over $``$, then $`\mathrm{Trop}V(I)`$ and $`\mathrm{Trop}^+V(I)`$ are closed subfans of the Gröbner fan.

One might wonder whether it would be better to modify the definition of $`^+`$ to require that our power series lie in $``$. This definition, for example, is more similar to the appearance of the ring of formal powers series in . One can show that in the case of the Grassmanian, this difference is unimportant. Moreover, the definition used here has the advantage that it makes it easy to prove that the positive part of the tropicalization is a fan.

Suppose $`V(I)𝒞^m`$ and $`V(J)𝒞^n`$ are varieties and we have a rational map $`f:𝒞^m𝒞^n`$ taking $`V(I)V(J)`$. Unfortunately, knowing $`\mathrm{val}(x_i)`$ for $`1im`$ does not in general determine $`\mathrm{val}(f(x_1,\mathrm{},x_m))`$, so we don’t get a nice map $`\mathrm{Trop}V(I)\mathrm{Trop}V(J)`$. However, suppose that $`f`$ takes the positive points of $`V(I)`$ surjectively onto the positive points of $`V(J)`$ and suppose that $`f=(f_1,\mathrm{},f_n)`$ is subtraction-free, that is, the formulas for the $`f_i`$’s are rational functions in the $`x_i`$’s whose numerators and denominators have positive coefficients. Define $`\mathrm{Trop}f:^m^n`$ by replacing every $`\times `$ in $`f`$ with a $`+`$, every $`/`$ with a $``$, every $`+`$ with a $`\mathrm{min}`$ and every constant $`a`$ with $`\mathrm{val}(a)`$.

###### Proposition 2.5.

Suppose $`V(I)𝒞^m`$ and $`V(J)𝒞^n`$ are varieties. Let $`f:𝒞^m𝒞^n`$ be a subtraction-free rational map taking $`V(I)`$ to $`V(J)`$ such that $`V(I)(^+)^m`$ surjects onto $`V(J)(^+)^n`$. Then $`\mathrm{Trop}f`$ takes $`\mathrm{Trop}^+V(I)`$ surjectively onto $`\mathrm{Trop}^+V(J)`$.

###### Proof.

This follows immediately from the formulas $`\mathrm{val}(x+y)=\mathrm{min}(\mathrm{val}(x),\mathrm{val}(y))`$ and $`\mathrm{val}(xy)=\mathrm{val}(x)+\mathrm{val}(y)`$ for $`x`$ and $`y^+`$. ∎

We now define the objects that we will study in this paper. Fix $`k`$ and $`n`$, and let $`N=\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$. Fix a polynomial ring $`S`$ in $`N`$ variables with coefficients in a commutative ring. The Plücker ideal $`I_{k,n}`$ is the homogeneous prime ideal in $`S`$ consisting of the algebraic relations (called Plücker relations) among the $`k\times k`$ minors of any $`k\times n`$-matrix with entries in a commutative ring.

Classically, the Grassmannian $`Gr_{k,n}`$ is the projective variety in $`_{}^{N1}`$ defined by the ideal $`I_{k,n}`$ of Plücker relations. We write $`Gr_{kn}(𝒞)`$ for the variety in $`_𝒞^{N1}`$ defined by the same equations. Similarly, we write $`Gr_{k,n}()`$ for the real points of the Grassmannian, $`Gr_{k,n}(^+)`$ for the real positive points, $`Gr_{k,n}(^+)`$ for those points of $`Gr_{k,n}(𝒞)`$ all of whose coordinates lie in $`^+`$ and so on. We write $`Gr_{k,n}()`$ when we want to emphasize that we are using the field $``$, and use $`Gr_{k,n}`$ when discussing results that hold with no essential modification for any field. The *totally positive Grassmannian* is the set $`Gr_{k,n}(^+)`$.

An element of $`Gr_{k,n}`$ can be represented by a full rank $`k\times n`$ matrix $`A`$. If $`K\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$ we define the Plücker coordinate $`\mathrm{\Delta }_K(A)`$ to be the minor of $`A`$ corresponding to the columns of $`A`$ indexed by $`K`$. We identify the element of the Grassmannian with the matrix $`A`$ and with its set of Plücker coordinates (which satisfy the Plücker relations).

Our primary object of study is the tropical positive Grassmannian $`\mathrm{Trop}^+Gr_{k,n}`$, which is a fan, by Corollary 2.4. As in , this fan has an $`n`$-dimensional lineality space. Let $`\varphi `$ denote the map from $`(^{})^n`$ into $`(^{})^{\left(\genfrac{}{}{0pt}{}{n}{k}\right)}`$ which sends $`(a_1,\mathrm{},a_n)`$ to the $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$-vector whose $`(i_1,\mathrm{},i_k)`$-coordinate is $`a_{i_1}a_{i_2}\mathrm{}a_{i_k}`$. We abuse notation by also using $`\varphi `$ for the same map $`(𝒞^{})^n(𝒞^{})^{\left(\genfrac{}{}{0pt}{}{n}{k}\right)}`$. Let $`\mathrm{Trop}\varphi `$ denote the corresponding linear map which sends $`(a_1,\mathrm{},a_n)`$ to the $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$-vector whose $`(i_1,\mathrm{},i_k)`$-coordinate is $`a_{i_1}+a_{i_2}+\mathrm{}+a_{i_k}`$. The map $`\mathrm{Trop}\varphi `$ is injective, and its image is the common lineality space of all cones in $`\mathrm{Trop}Gr_{k,n}`$.

## 3. Parameterizing the totally positive Grassmannian $`Gr_{k,n}(^+)`$

In this section we explain two equivalent ways to parameterize $`Gr_{k,n}(^+)`$, as well as a way to parameterize $`Gr_{k,n}(^+)/\varphi ((^+)^n)`$. The first method, due to Postnikov , uses a certain directed graph $`\mathrm{Web}_{k,n}`$ with variables associated to each of its $`2k(nk)`$ edges. The second method is closely related to the first and uses the same graph, but this time variables are associated to each of its $`k(nk)`$ regions. This has the advantage of giving a bijection between $`(^+)^{k(nk)}`$ and $`Gr_{k,n}(^+)`$. Finally, we use $`\mathrm{Web}_{k,n}`$ with variables labelling each of its $`(k1)(nk1)`$ inner regions in order to give a bijective parameterization of $`Gr_{k,n}(^+)/\varphi ((^+)^n)`$.

Let $`\mathrm{Web}_{k,n}`$ be the directed graph which is obtained from a $`k`$ by $`nk`$ grid, as shown in Figure 1. It has $`k`$ incoming edges on the right and $`nk`$ outgoing edges on the bottom, and the vertices attached to these edges are labelled clockwise from $`1`$ to $`n`$. We denote the set of $`2k(nk)`$ edges by $`E`$. Let us associate a formal variable $`x_e`$ with each edge $`eE`$, and if there is no ambiguity, we abbreviate the collection $`\{x_e\}`$ by $`x`$. If $`p`$ is a path on $`\mathrm{Web}_{k,n}`$ (compatible with the directions of the edges), then we let $`\mathrm{Prod}_p(x)`$ denote $`_{ep}x_e`$. And if $`S`$ is a set of paths on $`\mathrm{Web}_{k,n}`$, then we let $`\mathrm{Prod}_S(x)`$ denote $`_{pS}\mathrm{Prod}_p(x)`$.

As in , we define a $`k\times n`$ matrix $`A_{k,n}(x)`$, whose entries $`a_{ij}(x)`$ are polynomials in the variables $`x_e`$, by the following equation:

$$a_{ij}(x)=(1)^{i+1}\underset{p}{}\mathrm{Prod}_p(x),$$

where the sum is over all directed paths $`p`$ from vertex $`i`$ to vertex $`j`$. Note that the $`k\times k`$ submatrix of $`A_{k,n}(x)`$ obtained by restricting to the first $`k`$ columns is the identity matrix. In particular, $`A_{k,n}(x)`$ is a full rank matrix and hence we can identify it with an element of $`Gr_{k,n}`$. Also note that every element of the totally positive Grassmannian $`Gr_{k,n}(^+)`$ has a unique matrix representative whose leftmost $`k\times k`$ submatrix is the identity. We shall see that as the $`\{x_e\}`$ vary over $`(^+)^{2k(nk)}`$, the $`A_{k,n}(x)`$ range over all of $`Gr_{k,n}(^+)`$.

We now show it is possible to express the maximal minors (Plücker coordinates) of $`A_{k,n}(x)`$ as subtraction-free rational expressions in the $`x_e`$, as shown in . If $`K\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, then let $`\mathrm{Path}(K)`$ denote the set

$$\{S:S\text{ is a set of pairwise vertex-disjoint paths from }[k]\backslash (K[k])\text{ to }K\backslash ([k]K)\}.$$

Note that for $`K=[k]`$, we consider the empty set to be a legitimate set of pairwise vertex-disjoint paths.

Applied to $`\mathrm{Web}_{k,n}`$, Theorem 15.4 of  implies the following.

###### Proposition 3.1.

The Plücker coordinates of $`A_{k,n}(x)`$ are given by

$$\mathrm{\Delta }_K(A_{k,n}(x))=\underset{S\mathrm{Path}(K)}{}\mathrm{Prod}_S(x).$$

###### Proof.

We give a brief proof of this result: the main idea is to use the well-known Gessel-Viennot trick . First note that $`a_{ij}(x)`$ has a combinatorial interpretation: it is a generating function keeping track of paths from $`i`$ to $`j`$. Thus, the determinant of a $`k\times k`$ submatrix of $`A_{k,n}(x)`$ corresponding to the column set $`K`$ also has a combinatorial interpretation: it is a generating function for all sets of paths from $`[k]\backslash (K[k])`$ to $`K\backslash ([k]K)`$, with the sign of each term keeping track of the number of crossings in the corresponding path set. What we need to show is that this is equal to the sum of the contributions from path sets which are pairwise vertex-disjoint. To see this, consider a path set which does have an intersection. Look at its lexicographically last intersection, and compare this path set to the one obtained from it by switching the two path tails starting at that point of intersection. These two path sets get different signs, but have equal weights, and hence they cancel each other out. ∎

Proposition 3.1 allows us to define a map $`\mathrm{\Phi }_0:(^+)^{2k(nk)}Gr_{k,n}(^+)`$ as follows. Let $`K\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, and define $`P_K:(^+)^{2k(nk)}^+`$ by

$$P_K(x):=\underset{S\mathrm{Path}(K)}{}\mathrm{Prod}_S(x).$$

Clearly if we substitute positive values for each $`x_e`$, then $`P_K(x)`$ will be positive. We now define $`\mathrm{\Phi }_0`$ by

$$\mathrm{\Phi }_0(x)=\{P_K(x)\}_{K\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)}.$$

In other words, $`\mathrm{\Phi }_0`$ is the map which sends a collection of positive real numbers $`\{x_e\}`$ to the element of $`Gr_{k,n}`$ with Plücker coordinates $`P_K(x)`$ (which is identified with the matrix $`A_{k,n}(x)`$).

By Theorem 19.1 of , the map $`\mathrm{\Phi }_0`$ is actually surjective: any point in $`Gr_{k,n}(^+)`$ can be represented as $`A_{k,n}(x)`$ for some positive choices of $`\{x_e\}`$. In summary, we have the following result (which will also be a consequence of our Theorem 3.3).

###### Proposition 3.2.

The map $`\mathrm{\Phi }_0:(^+)^{2k(nk)}Gr_{k,n}()`$ is a surjection onto $`Gr_{k,n}(^+)`$.

Unfortunately, the method we have just described uses $`2k(nk)`$ variables to parameterize a space of dimension $`k(nk)`$. We will now explain how to do a substitution of variables which will reduce the number of variables to $`k(nk)`$.

We define an inner region of $`\mathrm{Web}_{k,n}`$ to be a bounded component of the complement of $`\mathrm{Web}_{k,n}`$ (viewed as a subset of $`^2`$). And we define an outer region of $`\mathrm{Web}_{k,n}`$ to be one of the extra inner regions we would obtain if we were to connect vertices $`i`$ and $`i+1`$ by a straight line, for $`i`$ from $`1`$ to $`n1`$. A region is an inner or outer region. Note that there are $`k(nk)`$ regions, which we denote by $`R`$, and there are $`(k1)(nk1)`$ inner regions.

Let us label each region $`rR`$ with a new variable $`x_r`$, which we define to be the product of its counterclockwise edge variables divided by the product of its clockwise edge variables.

For example, the new variables $`A,B,C`$ shown in Figure 2 would be defined by

$$A:=\frac{x_1x_2}{x_3x_4},\text{ }B:=\frac{x_5x_6}{x_7},\text{ }C:=x_8x_9.$$

It is easy to check that for a path $`p`$ on $`\mathrm{Web}_{k,n}`$, $`\mathrm{Prod}_p(x)`$ is equal to the product of the variables attached to all regions below $`p`$. Since $`\mathrm{Prod}_S(x)`$ and $`A_{k,n}(x)`$ were defined in terms of the $`\mathrm{Prod}_p(x)`$’s, we can redefine these expressions in terms of the $`k(nk)`$ region variables. Proposition 3.2 still holds, but our map is now a map $`\mathrm{\Phi }_1`$ from $`(^+)^{k(nk)}`$ onto $`Gr_{k,n}(^+)`$, taking the region variables $`\{x_r\}`$ to the element of $`Gr_{k,n}(^+)`$ represented by $`A_{k,n}(x)`$.

Since we are now parameterizing a space of dimension $`k(nk)`$ with $`k(nk)`$ variables, we should have a bijection. We shall prove that this is so by constructing the inverse map.

###### Theorem 3.3.

The map $`\mathrm{\Phi }_1:(^+)^{k(nk)}Gr_{k,n}(^+)`$, which maps $`\{x_r\}_{rR}`$ to the Grassmannian element represented by $`A_{k,n}(x)`$, is a bijection.

Before we prove this theorem, we need a lemma about matrices and their minors. We use a very slight generalization of a lemma which appeared in . For completeness, we include the proof of this lemma. First we must define some terminology. Let $`M`$ be a $`k\times n`$ matrix. Let $`\mathrm{\Delta }_{I,J}`$ denote the minor of $`M`$ which uses row set $`I`$ and column set $`J`$. We say that $`\mathrm{\Delta }_{I,J}`$ is solid if $`I`$ and $`J`$ consist of several consecutive indices; if furthermore $`IJ`$ contains $`1`$, we say that $`\mathrm{\Delta }_{I,J}`$ is initial. Thus, an initial minor is a solid minor which includes either the first column or the first row.

###### Lemma 3.4.

 A matrix $`M`$ is uniquely determined by its initial minors provided that all these minors are nonzero.

###### Proof.

Let us show that each matrix entry $`x_{ij}`$ of $`M`$ is uniquely determined by the initial minors. If $`i=1`$ or $`j=1`$, there is nothing to prove, since $`x_{ij}`$ is an initial minor. Assume that $`\mathrm{min}(i,j)>1`$. Let $`\mathrm{\Delta }`$ be the initial minor whose last row is $`i`$ and last column is $`j`$, and let $`\mathrm{\Delta }^{}`$ be the initial minor obtained from $`\mathrm{\Delta }`$ by deleting this row and column. Then $`\mathrm{\Delta }=\mathrm{\Delta }^{}x_{ij}+P`$, where $`P`$ is a polynomial in the matrix entries $`x_{i^{}j^{}}`$ with $`(i^{},j^{})(i,j)`$ and $`i^{}i,j^{}j`$. Using induction on $`i+j`$, we can assume that each $`x_{i^{}j^{}}`$ that occurs in $`P`$ is uniquely determined by the initial minors, so the same is true of $`x_{ij}=(\mathrm{\Delta }P)/\mathrm{\Delta }^{}`$. ∎

We now define a reflected initial minor to be a solid minor $`\mathrm{\Delta }_{I,J}`$ such that $`I`$ contains $`k`$ or $`J`$ contains $`1`$. Thus, a reflected initial minor is a solid minor which includes either the first column or the last row. A trivial corollary of Lemma 3.4 is the following.

###### Corollary 3.5.

A matrix $`M`$ is uniquely determined by its reflected initial minors provided that all these minors are nonzero.

Now we are ready to prove Theorem 3.3.

###### Proof.

To prove the theorem, we will construct an explicit inverse map $`\mathrm{\Psi }:Gr_{k,n}(^+)(^+)^{k(nk)}`$. The first step is to prove that $`\mathrm{\Psi }\mathrm{\Phi }_1=\mathrm{id}`$.

Let us index the regions in $`\mathrm{Web}_{k,n}`$ by ordered pairs $`(i,j)`$ as follows. Given a region, we choose $`i`$ to be the label of the horizontal wire which forms the upper boundary of the region, and choose $`j`$ to be the label of the vertical wire which forms the left boundary of the region. Now we define a map $`K`$ from the set of regions to $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$ by

$$K(i,j):=\{1,2,\mathrm{},i1\}\{i+jk,i+jk+1,\mathrm{},j1,j\}.$$

If $`(i,j)`$ is not a region of $`\mathrm{Web}_{k,n}`$, then we define $`K(i,j):=\mathrm{}`$.

Let $`A`$ be a $`k\times n`$ matrix whose initial $`k\times k`$ minor is the identity. We define $`\mathrm{\Psi }(A)`$ by

(1)
$$(\mathrm{\Psi }(A))_{(i,j)}:=\frac{\mathrm{\Delta }_{K(i,j)}(A)\mathrm{\Delta }_{K(i+1,j2)}(A)\mathrm{\Delta }_{K(i+2,j1)}(A)}{\mathrm{\Delta }_{K(i,j1)}(A)\mathrm{\Delta }_{K(i+1,j)}(A)\mathrm{\Delta }_{K(i+2,j2)}(A)}.$$

Note that by convention, we define $`\mathrm{\Delta }_{\mathrm{}}`$ to be $`1`$.

See Figure 3 for the definition of $`\mathrm{\Psi }`$ in the case of $`Gr_{3,6}(^+)`$. Note that for brevity, we have omitted the $`A`$’s from each term.

We claim that if $`A=\mathrm{\Phi }_1x`$, then $`\mathrm{\Psi }\mathrm{\Phi }_1x=x`$. To prove this, we note that the variable in region $`(i,j)`$ can be expressed in terms of vertex-disjoint paths as follows.

First observe that if $`K(i,j)\mathrm{}`$ then there is a unique set of pairwise vertex-disjoint paths from $`[k]([k]K(i,j))`$ to $`K(i,j)([k]K(i,j))`$. If one examines the terms in (1) and draws in the six sets of pairwise vertex-disjoint paths on $`\mathrm{Web}_{k,n}`$ (say the three from the numerator in red and the three from the denominator in blue) then it is clear that every region in $`\mathrm{Web}_{k,n}`$ lies underneath an equal number of red and blue paths – except the region $`(i,j)`$, which lies underneath only one red path. Thus, by definition of the maps $`P_K`$, it follows that

$$(\mathrm{\Psi }\mathrm{\Phi }_1(x))_{(i,j)}=\frac{P_{K(i,j)}(x)P_{K(i+1,j2)}(x)P_{K(i+2,j1)}(x)}{P_{K(i,j1)}(x)P_{K(i+1,j)}(x)P_{K(i+2,j2)}(x)}=x_{(i,j)}.$$

To complete the proof, it remains to show that $`\mathrm{\Psi }`$ is injective. This will complete the proof because we know that $`\mathrm{\Psi }\mathrm{\Phi }_1\mathrm{\Psi }=\mathrm{\Psi }`$, and $`\mathrm{\Psi }`$ injective then implies that $`\mathrm{\Phi }_1\mathrm{\Psi }=\mathrm{id}`$.

Choose an element of $`Gr_{k,n}(^+)`$, which we identify with its unique matrix representative $`A`$ whose leftmost $`k\times k`$ minor is the identity. Let $`𝒱`$ denote the set of rational expressions which appear in the right-hand side of (1) for all regions $`(i,j)`$ in $`\mathrm{Web}_{k,n}`$. Let $`𝒫`$ denote the set of all individual Plucker coordinates which appear in $`𝒱`$. We prove that $`\mathrm{\Psi }`$ is injective in two steps. First we show that the values of the expressions in $`𝒱`$ uniquely determine the values of the Plücker coordinates in $`𝒫`$. Next we show that the values of the Plücker coordinates in $`𝒫`$ uniquely determine the matrix $`A`$.

The first step is clear by inspection. We illustrate the proof in the case of $`Gr_{3,6}(^+)`$. By the choice of $`A`$, $`\mathrm{\Delta }_{123}=1.`$ Looking at the rational expressions in Figure 3, we see that knowing the value $`\frac{\mathrm{\Delta }_{124}}{\mathrm{\Delta }_{123}}`$ determines $`\mathrm{\Delta }_{124}`$; the value $`\mathrm{\Delta }_{124}`$ together with the value $`\frac{\mathrm{\Delta }_{134}}{\mathrm{\Delta }_{124}}`$ determines $`\mathrm{\Delta }_{134}`$; and similarly for $`\mathrm{\Delta }_{234},\mathrm{\Delta }_{125},\mathrm{\Delta }_{126}`$. Next, these values together with the value $`\frac{\mathrm{\Delta }_{145}\mathrm{\Delta }_{123}}{\mathrm{\Delta }_{125}\mathrm{\Delta }_{134}}`$ determines $`\mathrm{\Delta }_{145}`$, and so on.

For the second step of the proof, let $`A^{}`$ denote the $`k\times (nk)`$ matrix obtained from $`A`$ by removing the leftmost $`k\times k`$ identity matrix. Note that the values of the Plücker coordinates $`\mathrm{\Delta }_{K(i,j)}(A)`$ (which are all elements of $`𝒫`$) determine the values of all of the reflected initial minors of $`A^{}`$. (Each such Plücker coordinate is equal to one of the reflected initial minors, up to sign.) Thus, by Corollary 3.5, they uniquely determine the matrix $`A^{}`$ and hence $`A`$. This completes the proof of Theorem 3.3. ∎

Now let us parameterize $`Gr_{k,n}(^+)/\varphi ((^+)^n)`$. We shall show that we can do this by using variables corresponding to only the $`(k1)(nk1)`$ inner regions of $`\mathrm{Web}_{k,n}`$.

First recall that the $`n`$-dimensional torus acts on $`Gr_{k,n}(^+)`$ by scaling columns of a matrix representative for $`AGr_{k,n}(^+)`$. (Although the torus has dimension $`n`$, this is actually just an $`(n1)`$-dimensional action as the scalars act trivially.) Namely,

$$(\lambda _1,\mathrm{},\lambda _n)\left(\begin{array}{ccc}a_{11}& \mathrm{}& a_{1n}\\ \mathrm{}& & \mathrm{}\\ a_{k1}& \mathrm{}& a_{kn}\end{array}\right):=\left(\begin{array}{ccc}\lambda _1a_{11}& \mathrm{}& \lambda _na_{1n}\\ \mathrm{}& & \mathrm{}\\ \lambda _1a_{k1}& \mathrm{}& \lambda _na_{kn}\end{array}\right)$$

If $`AGr_{k,n}(^+)`$ then we let $`\overline{A}`$ denote the torus orbit of $`A`$ under this action. Note that if $`K=\{i_1,\mathrm{},i_k\}`$, then $`\mathrm{\Delta }_K(\lambda A)=\lambda _{i_1}\lambda _{i_2}\mathrm{}\lambda _{i_k}\mathrm{\Delta }_K(A)`$.

We will now determine the corresponding torus action on $`(^+)^{k(nk)}`$ such that the above bijection commutes with the actions. If $`r`$ is an internal region then $`x_r`$ is a ratio of Plücker coordinates with the same indices appearing on the top and bottom, so $`x_r`$ is not modified by the torus action. A simple computation shows that the torus acts transitively on the values of the outer region variables. Thus, taking the quotient by $`\varphi ((^+)^n)`$ on the right hand side of the equation corresponds to forgetting the outer variables on the left.

Define a map $`\mathrm{\Phi }_2:(^+)^{(k1)(nk1)}Gr_{k,n}(^+)/\varphi ((^+)^n)`$ by lifting a point $`c(^+)^{(k1)(nk1)}`$ to any arbitrarily chosen point $`\stackrel{~}{c}(^+)^{k(nk)}`$ and then mapping $`c`$ to $`\overline{\mathrm{\Phi }_1(\stackrel{~}{c})}`$. We have just proven:

###### Theorem 3.6.

The map $`\mathrm{\Phi }_2:(^+)^{(k1)(nk1)}Gr_{k,n}(^+)/\varphi ((^+)^n)`$ is a bijection.

## 4. A fan associated to the tropical positive Grassmannian

In this section we will construct a lower-dimensional fan associated to the tropical positive Grassmannian $`\mathrm{Trop}^+Gr_{k,n}`$. By methods precisely analogous to those above, we can prove an analogue of Theorem 3.6 for the field of Puiseux series.

###### Theorem 4.1.

The map $`\mathrm{\Phi }_2:(^+)^{(k1)(nk1)}Gr_{k,n}(^+)/\varphi ((^+)^n)`$ is a bijection.

This theorem allows us to compute $`\mathrm{Trop}^+Gr_{k,n}/(\mathrm{Trop}\varphi )(^n)`$ by applying the valuation map to the image of $`\mathrm{\Phi }_2`$. By Proposition 2.5 we can tropicalize the map $`\mathrm{\Phi }_2`$, obtaining the following surjective map.

$$\mathrm{Trop}\mathrm{\Phi }_2:^{(k1)(nk1)}\mathrm{Trop}^+Gr_{k,n}/(\mathrm{Trop}\varphi )(^n)$$

The map $`\mathrm{Trop}\mathrm{\Phi }_2`$ is the map we get by replacing multiplication with addition and addition with minimum in the definition of $`\mathrm{\Phi }_2`$. Explicitly, it is defined as follows. Let $`K\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, and let inner region variables take on values $`\{x_r\}`$ in $``$. Outer region variables are chosen arbitrarily. If $`p`$ is a path on $`\mathrm{Web}_{k,n}`$ then we let $`\mathrm{Sum}_p(x)`$ denote the sum of all variables which label regions below $`p`$. Similarly, if $`S`$ is a set of paths, then let $`\mathrm{Sum}_S(x)`$ denote $`_{pS}\mathrm{Sum}_p(x)`$. Now define $`\mathrm{Trop}P_K(x):^{(k1)(nk1)}`$ by

$$\mathrm{Trop}P_K(x):=\mathrm{min}\{\mathrm{Sum}_S(x):S\mathrm{Path}(K)\}.$$

The map $`\mathrm{Trop}\mathrm{\Phi }_2`$ is the map

$$\mathrm{Trop}\mathrm{\Phi }_2:^{(k1)(nk1)}\mathrm{Trop}^+Gr_{k,n}/(\mathrm{Trop}\varphi )(^n)^N/(\mathrm{Trop}\varphi )(^n)$$

given by

$$(\mathrm{Trop}\mathrm{\Phi }_2(x))_K=P_K(x).$$

###### Definition 4.2.

The fan $`F_{k,n}`$ is the complete fan in $`^{(k1)(nk1)}`$ whose maximal cones are the domains of linearity of the piecewise linear map $`\mathrm{Trop}\mathrm{\Phi }_2`$.

Because $`\mathrm{Trop}\mathrm{\Phi }_2`$ surjects onto $`\mathrm{Trop}^+Gr_{k,n}/(\mathrm{Trop}\varphi )(^n)`$, the fan $`F_{k,n}`$ reflects the combinatorial structure of the fan $`\mathrm{Trop}^+Gr_{k,n}/(\mathrm{Trop}\varphi )(^n)`$, which differs from $`\mathrm{Trop}^+Gr_{k,n}`$ only through modding out by the linearity space. However, $`F_{k,n}`$ is much easier to work with, as it lives in $`(k1)(nk1)`$-dimensional space as opposed to $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$-dimensional space.

Since the maps $`\mathrm{Trop}P_K`$ are piecewise linear functions, to each one we can associate a fan $`F(P_K)`$ whose maximal cones are the domains of linearity for $`\mathrm{Trop}P_K`$. It is clear that the fan $`F_{k,n}`$ is the simultaneous refinement of all of the fans $`F(P_K)`$.

From now on, by abuse of notation, we will refer to $`\mathrm{Trop}^+Gr_{k,n}/(\mathrm{Trop}\varphi )(^n)`$ as $`\mathrm{Trop}^+Gr_{k,n}`$.

## 5. $`\mathrm{Trop}^+Gr_{2,n}`$ and the associahedron

In this section we will describe the fan $`F_{2,n}`$ associated to $`\mathrm{Trop}^+Gr_{2,n}`$. We show that this fan is exactly the Stanley-Pitman fan $`F_{n3}`$, which appeared in the work of Stanley and Pitman in . In particular, the face poset of $`F_{2,n}`$, with a top element $`\widehat{1}`$ adjoined, is isomorphic to the face lattice of the normal fan of the associahedron, a polytope whose vertices correspond to triangulations of the convex $`n`$-gon. (In the language of , this is the associahedron of type $`A_{n3}`$.)

Let us first do the example of $`\mathrm{Trop}^+Gr_{2,5}`$.

We use the web diagram $`\mathrm{Web}_{2,5}`$, as shown in Figure 4. The maps $`\mathrm{Trop}P_K`$ are given by:

$`\mathrm{Trop}P_{1j}`$ $`=0\text{ for all }j`$
$`\mathrm{Trop}P_{23}`$ $`=0`$
$`\mathrm{Trop}P_{24}`$ $`=\mathrm{min}(x_1,0)`$
$`\mathrm{Trop}P_{25}`$ $`=\mathrm{min}(x_1+x_2,x_1,0)`$
$`\mathrm{Trop}P_{34}`$ $`=x_1`$
$`\mathrm{Trop}P_{35}`$ $`=\mathrm{min}(x_1,x_1+x_2)`$
$`\mathrm{Trop}P_{45}`$ $`=x_1+x_2`$
Each map $`\mathrm{Trop}P_K:^2`$ is piecewise linear and so gives rise to the complete fan $`F(P_K)`$. For example, the map $`\mathrm{Trop}P_{24}`$ is linear on the region $`\{(x_1,x_2):x_10\}`$, where it is the function $`(x_1,x_2)0`$, and on the region $`\{(x_1,x_2):x_10\}`$, where it is the function $`(x_1,x_2)x_1`$. Thus, $`F(P_{24})`$ is simply the subdivision of the real plane into the regions $`x_10`$ and $`x_10`$. The three nontrivial fans that we get from the maps $`\mathrm{Trop}P_J`$ are shown in Figure 5. In each picture, the maximal cones of each fan are separated by solid lines.

$`F_{2,5}`$, which is the simultaneous refinement of the three nontrivial fans, is shown in Figure 6.

In , it was shown that maximal cones of the fan $`\mathrm{Trop}Gr_{2,n}`$ correspond to trivalent trees on $`n`$ labelled leaves. It turns out that maximal cones of the fan $`\mathrm{Trop}Gr_{2,n}^+`$ correspond to trivalent planar trees on $`n`$ labelled leaves, as is illustrated in Figure 6.

We will now describe the fan that appeared in , but first, we must review some notions about trees. A plane binary tree is a rooted tree such that each vertex has either two children designated as left and right, or none at all; and an internal vertex of a binary tree is a vertex which is not a leaf. A trivalent planar tree is an (unrooted) tree such that every vertex has degree three, and such that the leaves are labelled in a clockwise fashion. It is known that both plane binary trees with $`n1`$ leaves, and trivalent planar trees with $`n`$ labelled leaves, are counted by the Catalan number $`c_{n2}=\frac{1}{n1}\left(\genfrac{}{}{0pt}{}{2(n2)}{n2}\right)`$.

There is a simple bijection between such trivalent planar trees and plane binary trees: if T a trivalent planar tree, then simply contract the edge whose leaf is labelled $`1`$, and make this the root. This bijection is illustrated in Figure 6.

Let us now define the Stanley-Pitman fan $`F_{n3}`$ in $`^{n3}`$. (Note that we use different indices than are used in ). The maximal cones of $`F_{n3}`$ are indexed by plane binary trees with $`n1`$ leaves, in the following manner. Let $`T`$ be a plane binary tree with $`n1`$ leaves. Label the internal vertices of $`T`$ with the numbers $`1,2,\mathrm{}n2`$ in the order of the first time we drop down to them from a child when doing a depth-first search from left to right starting at the root. (See Figure 6 for examples.) Let $`x_1,\mathrm{},x_{n3}`$ denote the coordinates in $`^{n3}`$. If the internal vertex $`i`$ of $`T`$ is the parent of vertex $`j`$, and $`i<j`$, then associate with the pair $`(i,j)`$ the inequality

$$x_i+\mathrm{}+x_{j1}0,$$

while if $`i>j`$ then associate with $`(i,j)`$ the inequality

$$x_i+\mathrm{}+x_{j1}0.$$

These $`n3`$ inequalities define a simplicial cone $`C_T`$ in $`^{n3}`$.

The result proved in  is the following.

###### Theorem 5.1 ().

The $`c_{n2}`$ cones $`C_T`$, as $`T`$ ranges over all plane binary trees with $`n1`$ leaves, form the chambers of a complete fan in $`^{n3}`$. Moreover, the face poset of $`F_{n3}`$, with a top element $`\widehat{1}`$ adjoined, is dual to the face lattice of the associahedron which parameterizes triangulations of the convex $`n`$-gon.

The key step in proving that our fan $`F_{2,n}`$ is equal to the Stanley-Pitman fan $`F_{n3}`$ is the following lemma, also proved in .

###### Lemma 5.2 ().

Let $`D_i=\{(x_1,\mathrm{},x_{n3})^{n3}:x_1+\mathrm{}+x_{i1}=\mathrm{min}(0,x_1,x_1+x_2,\mathrm{},x_1+\mathrm{}+x_{n3})\}`$. Let $`𝒯_i`$ consist of all plane binary trees with $`n1`$ leaves and root $`i`$. Then $`D_i=_{T𝒯_i}C_T`$.

###### Proposition 5.3.

The fan $`F_{2,n}`$ is equal to the fan $`F_{n3}`$.

###### Proof.

First let us describe the fan $`F_{2,n}`$ as explicitly as possible. Note that if we label the regions of $`\mathrm{Web}_{2,n}`$ with the variables $`x_1,\mathrm{},x_{n3}`$ from right to left, then all of the maps $`\mathrm{Trop}P_K`$ are of the form

$$\mathrm{min}(x_1+x_2+\mathrm{}+x_i,x_1+x_2+\mathrm{}+x_{i+1},\mathrm{},x_1+x_2+\mathrm{}+x_j),$$

where $`0ijn`$. Since this map has the same domains of linearity as the map

$$\theta _{ij}:=\mathrm{min}(x_i,x_i+x_{i+1},\mathrm{},x_i+\mathrm{}+x_j),$$

we can work with the maps $`\theta _{ij}`$ instead. Let $`F(i,j)`$ be the fan whose cones are the domains of linearity of $`\theta _{ij}`$. Then $`F_{2,n}`$ is the simultaneous refinement of all fans $`F(i,j)`$ where $`0ijn`$.

Now note that the previous lemma actually gives us an algorithm for determining which cone $`C_T`$ a generic point $`(x_1,\mathrm{},x_{n3})^{n3}`$ lies in. Namely, if we are given such a point, compute the partial sums of $`x_1+\mathrm{}+x_{i1}`$, for $`1in2`$. Choose $`i`$ such that $`x_1+\mathrm{}+x_{i1}`$ is the minimum of these sums. (If $`i=1`$, the sum is $`0`$.) Then the root of the tree $`T`$ is $`i`$. The left subtree of $`T`$ consists of vertices $`\{1,\mathrm{},i1\}`$, and the right subtree of $`T`$ consists of vertices $`\{i+1,\mathrm{},n2\}`$. We now compute $`\mathrm{min}\{0,x_1,x_1+x_2,\mathrm{},x_1+\mathrm{}+x_{i2}\}`$ and $`\mathrm{min}\{x_i,x_i+x_{i+1},\mathrm{},x_i+\mathrm{}+x_{n3}\}`$ in order to compute the roots of these two subtrees and so forth.

Now take a point $`(x_1,\mathrm{},x_{n3})`$ in a cone $`C`$ of $`F_{2,n}`$. This means that the point is in a domain of linearity for all of the piecewise linear functions $`\theta _{ij}=\mathrm{min}\{x_i,x_i+x_{i+1},\mathrm{},x_i+\mathrm{}+x_j\}`$ where $`0ijn`$, and we take $`x_0`$ to be $`0`$. In other words, for each $`i`$ and $`j`$, there is a unique $`k`$ such that $`x_i+\mathrm{}+x_k=\mathrm{min}\{x_i,x_i+x_{i+1},\mathrm{},x_i+\mathrm{}+x_j\}`$. In particular, we can reconstruct the tree $`T`$ such that $`(x_1,\mathrm{},x_{n3})C_T`$, and every point $`xC`$ belongs to this same cone $`C_T`$.

Finally, we can show by induction that $`C_TC`$. (We need to show that all of the functions $`\theta _{ij}`$ are actually linear on $`C_T`$.) This shows that each cone $`C`$ in $`F_{2,n}`$ is actually equal to a cone $`C_T`$ in $`F_{n3}`$, and conversely.

## 6. $`\mathrm{Trop}^+Gr_{3,6}`$ and the type $`D_4`$ associahedron

In connection with their work on cluster algebras, Fomin and Zelevinsky  recently introduced certain polytopes called generalized associahedra corresponding to each Dynkin type, of which the usual associahedron is the type $`A`$ example. When we computed $`F_{3,6}`$, the fan associated with $`\mathrm{Trop}^+Gr_{3,6}`$, we found that it was closely related to the normal fan of the type $`D_4`$ associahedron, in a way which we will now make precise. (We defer the explanation of our computations to the end of this section.)

###### Proposition 6.1.

The $`f`$-vector of $`F_{3,6}`$ is $`(16,66,98,48)`$. The rays of $`F_{3,6}`$ are listed in Table 1, along with the inequalities defining the polytope that $`F_{3,6}`$ is normal to.

Using the formulas of , we calculated the $`f`$-vector of the normal fan to the type $`D_4`$ associahedron: it is $`(16,66,100,50)`$. More specifically, our fan has two cones which are of the form of a cone over a bipyramid. (Type FFFGG in the language of .) If we subdivide these two bipyramids into two tetrahedra each, then we get precisely the $`D_4`$ associahedron.

In Section 8, we will give some background on cluster algebras and formulate a conjecture which explains the relation of $`F_{3,6}`$ to the normal fan to the type $`D_4`$ associahedron.

We depict the intersection of $`F_{3,6}`$ with a sphere in Figures 7 and 8. Each of the figures is homeomorphic to a solid torus, and the two figures glue together to form the sphere $`S^3`$. The bipyramids in question have vertices $`\{e_2+e_3e_4,e_1,e_2,e_3,e_1+e_4\}`$ and $`\{e_1e_2e_3,e_4,e_1e_2,e_1e_3,e_1e_4\}`$.

Now we will explain how we computed $`F_{3,6}`$. We used two methods: the first method was to use computer software (we used both cdd+ and Polymake) to compute the fan which we described in Section 4. The second method was to figure out which subfan of $`\mathrm{Trop}Gr_{3,6}`$ (which was explicitly described in ) was positive.

To implement our first method, we used the well-known result that if $`F_1`$ and $`F_2`$ are fans which are normal to polytopes $`Q_1`$ and $`Q_2`$, then the fan which is the refinement of $`F_1`$ and $`F_2`$ is normal to the Minkowski sum of $`Q_1`$ and $`Q_2`$. Since the fan $`F_{k,n}`$ is the simultaneous refinement of all the fans $`F(P_K)`$, we found explicit coordinates for polytopes $`Q(P_K)`$ whose normal fans were the fans $`F(P_K)`$, and had the programs cdd+ and Polymake compute the Minkowski sum $`Q_{k,n}`$ of all of these polytopes. We then got explicit coordinates for the fan which was normal to the resulting polytope.

For the second method, we used the results in : we checked which of the rays of $`\mathrm{Trop}Gr_{3,6}`$ did not lie $`\mathrm{Trop}^+Gr_{3,6}`$, and checked which facets of $`\mathrm{Trop}Gr_{3,6}`$ did lie in $`\mathrm{Trop}^+Gr_{3,6}`$. As $`\mathrm{Trop}^+Gr_{3,6}`$ is a closed subfan of $`\mathrm{Trop}Gr_{3,6}`$, this implied that every face of $`\mathrm{Trop}Gr_{3,6}`$ which lay in a totally positive facet was in $`\mathrm{Trop}^+Gr_{3,6}`$ and every face of $`\mathrm{Trop}Gr_{3,6}`$ which contained a non-totally positive ray was not in $`\mathrm{Trop}^+Gr_{3,6}`$; for every face of $`\mathrm{Trop}Gr_{3,6}`$, this proved sufficient to determine whether it was in $`\mathrm{Trop}^+Gr_{3,6}`$ or not.

## 7. $`\mathrm{Trop}^+Gr_{3,7}`$ and the type $`E_6`$ associahedron

As in the case of $`F_{3,6}`$, we used computer software to compute $`F_{3,7}`$, the fan associated to $`\mathrm{Trop}^+Gr_{3,7}`$.

###### Proposition 7.1.

The $`f`$-vector of $`F_{3,7}`$ is $`(42,392,1463,2583,2163,693)`$. Its rays are listed in Table 2, along with the inequalities defining the polytope that $`F_{3,7}`$ is normal to. Of the facets of this fan, $`595`$ are simplicial, $`63`$ have 7 vertices, $`28`$ have 8 vertices and $`7`$ have 9 vertices. All faces not of maximal dimension are simplicial.

Using the formulas of , we calculated the $`f`$-vector of the fan normal to the type $`E_6`$ associahedron: it is $`(42,399,1547,2856,2499,833)`$.

In Section 8, we will explain why $`F_{3,7}`$ differs from the $`E_6`$ fan, and how one can refine $`F_{3,7}`$ to get a fan combinatorially equivalent to the fan dual to the type $`E_6`$ associahedron. In this refinement, the simplicial facets remain facets. The $`7`$, $`8`$ and $`9`$ vertex facets split into $`2`$, $`3`$ and $`4`$ simplices respectively. The following table shows how the vertices of the $`7`$, $`8`$, and $`9`$ vertex facets are grouped into simplices.

$`<ABCDEFG>`$ $``$ $`<ABCDEF><ABCDEG>`$
$`<ABCDEFGH>`$ $``$ $`<ABCDEF><ABCDFG>`$
$`<ABCDGH>`$
$`<ABCDEFGHI>`$ $``$ $`<ABCDEF><ABCEFG>`$
$`<ABCFGH><ABCGHI>`$
## 8. Cluster Algebras

Cluster algebras are commutative algebras endowed with a certain combinatorial structure, introduced in  and expected to be relevant in studying total positivity and homogeneous spaces, such as Grassmannians.

We will not attempt to give a precise definition of a cluster algebra here, but will rather describe their key properties. Slightly varying definitions can be found in ,  and ; we follow  but do not believe these small variations are important.

A cluster algebra is an algebra $`𝒜`$ over a field $`k`$, which in our examples can be thought of as $``$. Additionally, a cluster algebra carries two subsets $`C`$ and $`X𝒜`$, known as the coefficient variables and the cluster variables. $`C`$ is finite, but $`X`$ may be finite or infinite. If $`X`$ is finite, $`𝒜`$ is known as a cluster algebra of finite type. There is also a nonnegative integer $`r`$ associated to a cluster algebra and known as the rank of the algebra.

There is a pure $`(r1)`$-dimensional simplicial complex called the cluster complex whose vertices are the elements of $`X`$ and whose maximal simplices are called clusters. We will denote the cluster complex by $`S(𝒜)`$. If $`xX`$ and $`\mathrm{\Delta }S(𝒜)`$ is a cluster containing $`x`$, there is always a unique cluster $`\mathrm{\Delta }^{}`$ with $`\mathrm{\Delta }\mathrm{\Delta }^{}=\mathrm{\Delta }\{x\}`$. Let $`\mathrm{\Delta }^{}=(\mathrm{\Delta }\{x\})\{x^{}\}`$. Then there is a relation $`xx^{}=B`$ where $`B`$ is a binomial in the variables of $`(\mathrm{\Delta }\mathrm{\Delta }^{})C`$.

For any $`xX`$ and any cluster $`\mathrm{\Delta }`$, $`x`$ is a subtraction-free rational expression in the members of $`\mathrm{\Delta }C`$ and is also a Laurent polynomial in the members of $`\mathrm{\Delta }C`$. Conjecturally, this Laurent polynomial has non-negative coefficients. Note that this conjecture does not follow from the preceding sentence: $`\frac{x^3+y^3}{x+y}=x^2xy+y^2`$ is a subtraction-free expression in $`x`$ and $`y`$, and a polynomial in $`x`$ and $`y`$, but it is not a polynomial with positive coefficients.

It was demonstrated in  that the coordinate rings of Grassmannians have natural cluster algebra structures. Usually these cluster algebras are of infinite type, making them hard to work with in practice, but in the cases of $`Gr_{2,n}`$, $`Gr_{3,k}`$ for $`k8`$ and their duals, we get cluster algebras of finite type.

In the case of $`Gr_{2,n}`$, the coefficient set $`C`$ is $`\{\mathrm{\Delta }_{12},\mathrm{\Delta }_{23},\mathrm{},\mathrm{\Delta }_{(n1)n},\mathrm{\Delta }_{1n}\}`$ and the set of cluster variables $`X`$ is $`\{\mathrm{\Delta }_{ij}:i<j\text{ and }ij\pm 1modn\}`$. (Note that these $`\mathrm{\Delta }`$’s are Plücker coordinates and not simplices.) Label the vertices of an $`n`$-gon in clockwise order with the indices $`\{1,2,\mathrm{},n\}`$ and associate to each member of $`XC`$ the corresponding chord of the $`n`$-gon. The clusters of $`Gr_{2,n}`$ correspond to the collections of chords which triangulate the $`n`$-gon. Thus, $`S(𝒜)`$ in this example is (as an abstract simplicial complex) isomorphic to the dual of the associahedron. Since we have shown that the fan of $`\mathrm{Trop}^+Gr_{2,n}`$ is combinatorially equivalent to the normal fan of the associahedron, it follows that $`\mathrm{Trop}^+Gr_{2,n}`$ is (combinatorially) the cone on $`S(𝒜)`$.

In the case of $`Gr_{3,6}`$, the coefficient set $`C`$ is equal to $`\{\mathrm{\Delta }_{123},\mathrm{\Delta }_{234},\mathrm{\Delta }_{345},\mathrm{\Delta }_{456},\mathrm{\Delta }_{561},\mathrm{\Delta }_{612}\}`$. $`X`$ contains the other $`14`$ Plücker coordinates, but it also contains two unexpected elements: $`\mathrm{\Delta }_{134}\mathrm{\Delta }_{256}\mathrm{\Delta }_{156}\mathrm{\Delta }_{234}`$ and $`\mathrm{\Delta }_{236}\mathrm{\Delta }_{145}\mathrm{\Delta }_{234}\mathrm{\Delta }_{156}`$. By definition, all Plücker coordinates are positive on the totally positive Grassmannian, so by the results above on subtraction-free rational expressions, these new coordinates are positive on the totally positive Grassmannian as well.

The new coordinates turn out to be Laurent polynomials with positive coefficients in the region variables of Section 3. Thus, we can tropicalize these Laurent polynomials and associate a fan to each of them. When we refine $`F_{3,6}`$ by these fans, the refinement subdivides the two bipyramids and yields precisely the normal fan to the $`D_4`$ associahedron, which is again the cone over $`S(𝒜)`$.

In the case of $`Gr_{3,7}`$, $`C`$ again consists of $`\{\mathrm{\Delta }_{i(i+1)(i+2)}\}`$ where indices are modulo $`7`$. $`X`$ contains all of the other Plücker variables and the pullbacks to $`Gr_{3,7}`$ of the two new cluster variables of $`Gr_{3,6}`$, along with the $`7`$ rational coordinate projections $`Gr_{3,7}Gr_{3,6}`$. Thus, $`X`$ contains $`28`$ Plücker variables and $`14`$ other variables.

As in the case of $`Gr_{3,6}`$, the 14 new variables are Laurent polynomials with positive coefficients in the region variables of Section 3, so to each one we can associate a corresponding fan. When we refine $`F_{3,7}`$ by these 14 new fans, we get a fan combinatorially equivalent to the fan normal to the $`E_6`$ associahedron.

We can describe what we have seen in each of these Grassmannian examples in terms of the general language of cluster algebras as follows:

###### Observation when $`𝒜`$ is the Coordinate Ring of a Grassmannian.

Embed $`\mathrm{Spec}𝒜`$ in affine space by the variables $`XC`$. Then $`\mathrm{Trop}^+\mathrm{Spec}𝒜`$ is a fan with lineality space of dimension $`|C|`$. After taking the quotient by this lineality space, we get a simplical fan abstractly isomorphic to the cone over $`S(𝒜)`$.

This observation does not quite hold for an arbitrary cluster algebra of finite type. For example, if we take the cluster algebra of $`Gr_{2,6}`$ and set all coefficient variables equal to $`1`$, we get a different cluster algebra which is still of type $`A_3`$. However, when we compute the positive part of the corresponding tropical variety, we get a fan whose lineality space has dimension $`1`$, not $`0`$ as the above would predict. Our fan is a cone over a hexagon cross a $`1`$-dimensional lineality space, which is a coarsening of the fan normal to the type $`A_3`$ associahedron. Based on this and other small examples, it seems that in order to see the entire cone over $`S(𝒜)`$, one needs to use “enough” coefficients.

###### Conjecture 8.1.

Let $`𝒜`$ be a cluster algebra of finite type over $``$ and $`S(𝒜)`$ its associated cluster complex. If the lineality space of $`\mathrm{Trop}^+\mathrm{Spec}𝒜`$ has dimension $`|C|`$ then $`\mathrm{Trop}^+\mathrm{Spec}𝒜`$ modulo its lineality space is a simplicial fan abstractly isomorphic to the cone over $`S(𝒜)`$. If the condition on the lineality space does not hold, the resulting fan is a coarsening of the cone over $`S(𝒜)`$.

Remark: The condition on the lineality space can be restated without mentioning tropicalizations. Consider the torus $`(^{})^{XC}`$ acting on the affine space $`^{XC}`$ and let $`G`$ be the subgroup taking $`\mathrm{Spec}𝒜`$ to itself. We want to require that $`dimG=|C|`$.

Remark: In the notation of  and , the condition on the dimension of the lineality space is equivalent to requiring that the matrix $`\stackrel{~}{B}`$ be of full rank. We thank Andrei Zelevinsky for pointing this out to us.

Note how surprising this conjecture is in light of how the two complexes are computed. The fan described in the conjecture is computed as the refinement of a number of fans, indexed by the vertices of $`S(𝒜)`$. That the rays of this fan, which arise as the intersections of many hypersurfaces, should again be in bijection with the vertices of $`S(𝒜)`$ is quite unexpected.

We expect an analogous statement to hold for infinite type cluster algebras.

## 9. Acknowledgements

We are grateful to Bernd Sturmfels for suggesting this problem to us, and for advice throughout our work. In addition, we thank Komei Fukuda and Michael Joswig for their help in performing the polyhedral computations and Joshua Scott, Richard Stanley, and Andrei Zelevinsky for their useful comments.


text:
# Untitled Document

This manuscript has been withdrawn because of some default.