Secondary fans and Stanley Reisner ideals

Consider a collection of points $S \subset \mathbb R^d$. I would like to understand all possible fans $\Sigma$ whose support is the cone over $S$: $|\Sigma| = cone(S)$.

I have heard that the secondary fan does this for me, but I am having trouble parsing the relevant sections of GKZ. I would like to understand this completely, but to begin I would really like to know

How to construct the resulting set of Stanley-Reisner ideals for each possible $\Sigma$.

Can someone explain this and/or give a readable explanation of

How the secondary fan is built and how each cone gives a refinement of $cone(S)$?

-

Consider any function $f$ from $S \to \mathbb{R}$. Define a function $\tilde{f}: \mathrm{cone}(S) \to \mathbb{R}$ by $$\tilde{f}(w) = \max \{ \sum a_i f(s_i) : \ \sum a_i s_i = w,\ a_i \geq 0 \}.$$ That is, for every way of writing $w$ as a positive linear combination of the $a$'s, try extending $f$ linearly, and find the largest possible extension.

Then $\tilde{f}$ is a piecewise linear convex function. The domains of linearity for $\tilde{f}$ form a fan, each of whose cones is spanned by a subset of $S$.

Subdivide $\mathbb{R}^S$ into cones, where functions $f$ and $g$ are in the same cone if $\tilde{f}$ and $\tilde{g}$ have the same domains of linearity. This is the secondary fan.

Thus, the cones of the secondary fan are in bijection with fans $F$ whose support is $\mathrm{cone}(S)$, where every face of $F$ is of the form $\mathrm{cone}(T)$ for some $T \subseteq S$, and where there is a convex piecewise linear function whose domains of linearity are the faces of $F$.

Several warnings:

(0) You didn't say that you want every cone of your fan to be of the form $\mathrm{cone}(T)$, for $T \subseteq S$, but I assume that you meant to. If not, there will be infinitely many fans meetng your conditions, because you can always insert new vertices.

(1) There can be fans which do not support any convex piecewise linear function. Such fans are called non-coherent or non-regular. They do not correspond to cones of the secondary fan.

(2) As I have described it, the secondary fan lives in $\mathbb{R}^S$. Note that, if $\lambda$ is a linear function on $\mathbb{R}^d$, then $f$ and $f+\lambda$ always lie in the same cone of the secondary fan, so the secondary fan is invariant under this action of $(\mathbb{R}^d)^{\vee}$. Many references quotient by this action.

(3) Many references specialize to the case that $S$ lies in an affine hyperplane, and then draw their pictures in $\mathbb{R}^{d-1}$. I think GKZ does this, which might be part of your difficulty.

(4) You mention Stanley-Reisner ideals. You don't say what your motivation is, but it sounds like you might be computing Grobner degenerations of toric varieties. If so, remember that these can be nonreduced, and the secondary fan will only see the reduced structure. See Sturmfels paper Gröbner bases of toric varieties for details.

Have you tried reading the Billera, Filliman and Sturmfels paper, Constructions and complexity of secondary polytopes? I seem to remember it is very clear, although it also has weakness (3).

-
Thanks David! The codimension one problem has been throwing me for awhile. Something's wrong with the display of your first equation though; it should be $$\tilde{f}(w) = \max \{ \sum a_i f(s_i) : \ \sum a_i s_i = w,\ a_i \geq 0 \}.$$ –  James Davidoff Oct 3 '10 at 1:13
You're welcome! I'm confused though; on my laptop (mac, Firefox), your equation and mine look the same. –  David Speyer Oct 4 '10 at 0:57
It's apparently a bug in chrome for Linux. Do you happen to know of an algorithm to explicitly compute all coherent triangulations of a set $S$? –  James Davidoff Oct 11 '10 at 15:41
I think POLYMAKE opt.tu-darmstadt.de/polymake/doku.php/start can do this, but I don't remember how. –  David Speyer Oct 11 '10 at 16:03
David, do you know of any way to understand the non-coherent refinements of cone(S)? Put differently (if I understand correctly), let X be the affine toric variety associated to cone(S). The cones of the secondary fan classify projective toric maps Y->X that are bijective on orbits of codimension 0 or 1. The non-coherent refinements correspond to such maps that are proper but not projective. Can these be nicely classified? –  Nicholas Proudfoot Nov 20 '12 at 20:18