# Hierarchical zonotopal power ideals.

1 Introduction

Let X = ([x.sub.1], ..., [x.sub.N]) [subset or equal to] [R.sup.r] be a sequence of vectors that span [R.sup.r]. For a vector [eta], let m([eta]) denote the number of vectors in X that are not perpendicular to [eta]. A vector v [member of] [R.sup.r] defines a linear polynomial [p.sub.v] := [[summation].sub.i] [v.sub.i][t.sub.i] [member of] R[[t.sub.1], ..., [t.sub.r]]. For Y [subset or equal to] X, let [p.sub.Y] := [[PI].sub.x[member of]Y] [p.sub.x]. Then define

P(X) := span{py : X \ Y spans [R.sup.r]} and I(X) := ideal{[p.sup.m([eta]).sub.[eta]] : [eta] [not equal to] 0} (1.1)

The following theorem and several generalizations are well known:

Theorem 1.1 ([1,5, 11]).

P(X) = kerI(X) := span {q [member of] R[[t.sub.1], ..., [t.sub.r]] : f([partial derivative]/[partial derivative][t.sub.1], ..., [partial derivative]/[partial derivative][t.sub.r]) q = 0 for all f [member of] I(X)} (1.2)

In addition, I(X) = I'(X) := {[p.sup.m([eta]).sub.[eta]] : the vectors in X that are perpendicular to n span a hyperplane}

We show that a statement as in Theorem 1.1 holds in a far more general setting: we study the kernel of the hierarchical zonotopal power ideal

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3)

where k [greater than or equal to] -1 is an integer and [[chi].sub.J] is the indicator function of an upper set J in the lattice of flats of the matroid defined by X. We study those spaces in a slightly more abstract setting, e. g. P(X, k, J) is contained in the symmetric algebra over some K-vector space, where K is a field of characteristic zero.

The choice of a sequence of vectors X defines a large number of objects in various mathematical fields which are all related to zonotopal algebra [11]. Examples include combinatorics (matroids, matroid and graph polynomials, generalized parking functions and chip firing games if X is graphic [15, 18]), discrete geometry (hyperplane arrangements, zonotopes and tilings of zonotopes), approximation theory (box splines [6], least map interpolation) and algebraic geometry (Cox rings, fat point ideals [1, 10, 19]).

Central P-spaces (in our terminology the kernel of I'(X, 0, {X})) were introduced in the literature on approximation theory around 1990 (e. g. [5]). A dual space called D(X) appeared almost 30 years ago. See [11, Section 1.2] for a historic survey.

Recently, Olga Holtz and Amos Ron coined the term zonotopal algebra [11]. They introduced internal (k = -1) and external (k = +1) P-spaces and D-spaces. Federico Ardila and Alexander Postnikov constructed P-spaces for arbitrary integers k [greater than or equal to] -1 (Combinatorics and geometry of power ideals [1], presented at FPSAC 2009). Olga Holtz, Amos Ron, and Zhiqiang Xu [12] introduced hierarchical zonotopal spaces, i. e. structures that depend on the choice of an upper set J in addition to X and k. They studied semi-internal and semi-external spaces (i. e. k = -1 and k = 0 and some special upper sets J). The central case was treated in an algebraic setting in [8]. Other related results include [2, 20].

The least map [7] assigns to a finite set S [subset or equal to] [R.sup.r] of cardinality m an m-dimensional space of homogeneous polynomials in R [[t.sub.1], ..., [t.sub.r]]. Holtz and Ron [11] showed that in the internal, central and external case, P-spaces can be obtained via the least map if X [subset or equal to] [Z.sup.r] is unimodular. In those cases, the P-spaces are obtained by choosing the set S as a certain subset of the set of integral points in the zonotope

Z(X) := {[Nsummation over (i=1)][[lambda].sub.i][x.sub.i] :0 [less than or equal to] [[lambda].sub.i] [less than or equal to] 1} (1.4)

There is also a discrete theory, where differential operators are replaced by difference operators. ([8] and A Tutte polynomial for toric arrangements (Luca Moci) [16], presented at FPSAC 2010). In this theory, the connection with lattice points in zonotope remains valid even if X is not unimodular.

As an example for the connections between zonotopal algebra and combinatorics, we now explain various relationships between zonotopal spaces and matroid/graph polynomials. They can be deduced from the fact that both, the matroid/graph polynomials [9] and the Hilbert series of the zonotopal spaces [1] are evaluations of the Tutte polynomial.

Hilb(P(X, 0, {X}), t) equals the shelling polynomial [3] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of the matroid dual to X with the coefficients reversed. The [t.sup.N-r-i] coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] equals the number of independent sets of cardinality i in the matroid X. Let [X.sub.G] denote the reduced oriented incidence matrix of a connected graph G, i. e. the matrix that is obtained from the oriented incidence matrix by removing one row so that it has full rank. The Hilbert series of P([X.sub.G], -1, {[X.sub.G]}) is related to the flow polynomial [[phi].sub.G]. By duality it is also related to the chromatic polynomial of the graph resp. the characteristic polynomial of the matroid in the general case. The connection is as follows: if G is connected, then

[[phi].sub.G](t) = [(t - 1).sup.N-r] Hilb(P([X.sub.G], -1, {[X.sub.G]}), 1/(1 - t)) (1.5)

The four color theorem is equivalent to the following statement: if G is a planar graph and [G.sup.*] denotes its dual, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.6)

Organization of the article: In Section 2, we introduce our notation and review the mathematical background. In Section 3, we define hierarchical zonotopal power ideals. A simple description of their kernels is given by our Main Theorem. In Section 4, we construct bases for the vector spaces P(X, k, J) and we deduce several formulas for their Hilbert series. In Section 5, we apply our results to prove a statement about zonotopal Cox modules that were defined by Bernd Sturmfels and Zhiqiang Xu [19]. In Section 6, we give some examples. The full paper is available on the arXiv [14].

2 Preliminaries

Notation: The following notation is used throughout this paper: K is a fixed field of characteristic zero. V denotes a finite-dimensional K-vector space of dimension r [greater than or equal to] 1 and U := [V.sup.*] its dual. Our main object of study is a finite sequence X = ([x.sub.1], ..., [x.sub.N]) [subset or equal to] U whose elements span U. We slightly abuse notation by using the symbol [subset or equal to] for subsequences. For Y [subset or equal to] X, the deletion X \ Y denotes the deletion of a subsequence and not the deletion of a subset, i.e. ([x.sub.1], [x.sub.2]) \ ([x.sub.1]) = ([x.sub.2]) even if [x.sub.1] = [x.sub.2]. The order of the elements in X is irrelevant except in Section 4.

Matroids and posets: Let X = ([x.sub.1], ..., [x.sub.N]) be a finite sequence whose elements span U. Let M(X) := {I [subset or equal to] {1, ..., N} : {[x.sub.i] : i [member of] I} linearly independent}. Then M(X) is a matroid of rank r on N elements. X is called a K-representation of the matroid M(X). For more information about matroids, see Oxley's book [17].

We now introduce some additional matroid theoretic concepts. To facilitate notation, we always write X instead of M(X). The rank of Y [subset or equal to] X is defined as the cardinality of a maximal independent set contained in Y. It is denoted rk(Y). The closure of Y in X is defined as [cl.sub.X] (Y) := {x [member of] X : rk(Y [[union].sub.x]) = rk(Y)}. C [subset or equal to] X is called a flat if C = cl(C). A hyperplane is a flat of rank r - 1. The set of all hyperplanes in X is denoted by H = H(X).

Given a flat C [subset or equal to] X, we call [eta] [member of] V a defining normal for C if C = {x [member of] X : [eta](x) = 0}. Note that for hyperplanes, there is a unique defining normal (up to scaling). The set of bases of the matroid X (i. e. the subsequences of X of cardinality r and rank r) is denoted B(X). If x = 0, then x is called a loop. If rk( X \ x) = r - 1 , then x is called a coloop.

The set of flats of a given matroid X ordered by inclusion forms a lattice (i. e. a poset with joins and meets) called the lattice of flats L(X). An upper set J [subset or equal to] L(X) is an upward closed set, i. e. C [subset or equal to] C', C [member of] J implies C' [member of] J. We call C [member of] L(X) a maximal missing flat if C [not member of] J and C is maximal with this property.

The Tutte polynomial [4] Tx(x,y) := [[summation].sub.A[subset or equal to]X] [(x - 1).sup.r-rk(A)][(y -1).sup.[absolute value of A]-rk(A)] captures a lot of information about the matroid M(X).

Algebra: Sym(V) denotes the symmetric algebra over V. This is a base-free version of the ring of polynomials over V. The choice of a basis B = {[b.sub.1], ..., [b.sub.n]} [congruent to] V yields an isomorphism Sym(V) [congruent to] K[[b.sub.1], ..., [b.sub.r]].

A derivation on Sym(V) is a K-linear map D satisfying Leibniz's law, i. e. D(fg) = D(f)g + f D(g) for f, g [member of] Sym(V). For v [member of] V, we define the directional derivative in direction v, [D.sub.v] : Sym(U) [right arrow] Sym(U) as the unique derivation which satisfies [D.sub.v](u) = v(u) for all u [member of] U. For K = R and K = C, this definition agrees with the analytic definition of the directional derivative. It follows that Sym(V) can be identified with the ring of differential operators on U.

Now we define a pairing <*, *> : Sym(U) x Sym(V) [right arrow] K by <f, q> := (q(D)f )(0) where q(D)f means that q acts as a differential operator on f.

A graded vector space is a vector space V that decomposes into a direct sum V = [[direct sum].sub.i[greater than or equal to]0] [V.sub.i]. For a graded vector space, we define its Hilbert series as the formal power series [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A graded algebra V has the additional property [V.sub.i][V.sub.j] [subset or equal to] [V.sub.i+j]. We use the symmetric algebra with its natural grading. This grading is characterized by the property that the degree 1 elements are exactly the ones that are contained in V. A [Z.sup.n]-multigraded ring R is defined similarly: R decomposes into a direct sum [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [R.sub.a][R.sub.b] [subset or equal to] [R.sub.a+b].

A linear map f : V [right arrow] W induces an algebra homomorphism Sym(f) : Sym(V) [right arrow] Sym(W).

Homogeneous ideals and their kernels: An ideal I [subset or equal to] Sym(V) is called a power ideal [1] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some Z [subset or equal to] V \ {0} and e [member of] [Z.sup.Z.sub.[greater than or equal to]>0]. (i) [D.sub.[eta]] denotes the image of [eta] under the canonical injection V [??] Sym(V). By definition, power ideals are homogeneous.

Definition 2.1. Let I [subset or equal to] Sym(V) be a homogeneous ideal. Its kernel (or inverse system) is defined as

ker I := {f [member of] Sym(U) : <f, q> =0 for all q [member of] I} (2.1)

It is known that for a homogeneous ideal I [subset or equal to] Sym(V) of finite codimension the Hilbert series of ker I and Sym(V)/I are equal. (ii)

A remark on the notation: As zonotopal spaces were studied by people from different fields, the notation and the level of abstraction used in the literature varies. Authors with a background in spline theory usually work over [R.sup.n] while other authors prefer an abstract setting as we do.

Since the Euclidean setting captures all the important parts of the theory, a reader with no background in abstract algebra may safely make the following substitutions: K = R, U [congruent to] V [congruent to] [R.sup.n]. f [member of] R[[t.sub.1], ..., [t.sub.r]] = Sym(V) acts on R[[t.sub.1], ..., [t.sub.r]] = Sym(U) as the differential operator that is obtained from f by substituting [t.sub.i] [??] [partial derivative]/[partial derivative][t.sub.i].

Some authors work in the dual setting and consider a central hyperplane arrangement instead of a finite sequence of vectors X. While hierarchical zonotopal power ideals can be defined in both settings, it is natural for us to work with vectors as we are also interested in the zonotope Z(X).

3 Hierarchical zonotopal power ideals and their kernels

In this section, we define hierarchical zonotopal power ideals. Our Main Theorem gives a simple description of their kernels.

Definitions and the Main Theorem: Recall that U = [V.sup.*] denotes an r-dimensional vector space over a field K of characteristic zero and X = ([x.sub.1], ..., [x.sub.N]) denotes a finite sequence whose elements span U.

A vector [eta] [member of] V defines a flat C [subset or equal to] X. Define [m.sub.X](C) = [m.sub.X]([eta]) := [absolute value of X \ C]. Given an upper set J [subset or equal to] L(X), [[chi].sub.J] : L(X) [right arrow] {0,1 } denotes its indicator function. The index of [chi] and m is omitted if it is clear which upper set is meant. We define [chi] for arbitrary sets A [subset or equal to] X as [chi](A) := [chi](cl(A)).

For a given x [member of] U, we denote the image of X under the canonical injection U [??] Sym(U) by [p.sub.x]. For Y [subset or equal to] X, we define [p.sub.Y] := [[PI].sub.x[member of]Y] [p.sub.x]. For [eta] [member of] V, we write [D.sub.[eta]] for the image of [eta] under the canonical injection V [??] Sym( V) in order to stress the fact that we mostly think of Sym(V) as the algebra generated by the directional derivatives on Sym(U).

Definition 3.1 (Hierarchical zonotopal power ideals and P-spaces). Let K be a field of characteristic zero, V be a finite-dimensional K-vector space of dimension r [greater than or equal to] 1 and U = [V.sup.*]. Let X = ([x.sub.1], ..., [x.sub.N]) [subset or equal to] U be a finite sequence whose elements span U. Let k [greater than or equal to] -1 be an integer and let J [subset or equal to] L(X) be a non-empty upper set, where L(X) denotes the lattice of flats of the matroid defined by X.

Let [chi] : L(X) [right arrow] {0,1} denote the indicator function of J. Let E : L(X) [right arrow] V be a function that assigns a defining normal to every flat. Now define

I'(X, k, J, E) := ideal{[D.sup.m(C)+k+[chi](C).sub.E(C)] : C hyperplane or maximal missing flat} (3.1)

I(X, k, J) := ideal{[D.sup.m([eta])+k+[chi]([eta]).sub.[eta]] : [eta] [member of] V \ {0}} [subset or equal to] Sym(V) (3.2)

P(X, k, J) := span S(X, k, J) [subset or equal to] Sym(U) (3.3)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the definition of S(X, 0, J) can be seen as a special case of the definition of S(X, k, J) for k [greater than or equal to] 1. For examples, see Section 6, Remark 3.7, and Proposition 3.8.

Theorem 3.2 (Main Theorem). We use the same terminology as in Definition 3.1. For k = -1, we assume in addition that J [contains or equal to], i. e. J contains all hyperplanes in X. Then,

P(X, k, J) = ker I(X, k, J) [subset or equal to] ker I'(X, k, J, E) (3.4)

Furthermore, for k [member of] {-1, 0}, I'(X, k, J, E) is independent of the choice of E and P(X, k, J) = ker I(X, k, J) = ker I'(X, k, J, E).

Corollary 3.3. In the setting of the Main Theorem, P (X, k, L(X)) = P (X, k + 1, {X}).

Corollary 3.4. The Hilbert series of P(X, k, J) depends only on the matroid M(X), but not on the representation X.

Remark 3.5. One might wonder if similar theorems can be proved for k [less than or equal to] -2. One would of course need to impose extra conditions on X to ensure that the exponents appearing in the definition of the ideals are non-negative. It is easy to prove that I and I' are equal in this case. However, we do not know how to construct a generating set for the kernel. A different approach would be required: in general, it is not spanned by a set of polynomials of type [p.sub.Y] for some Y [subset or equal to] X [1].

Basic results: In this paragraph, we state an important lemma and we give an explicit formula for P(X, k, J) in two particularly simple cases.

Lemma 3.6. P (X, k, J) [subset or equal to] ker I (X, k, J) [subset or equal to] ker I'(X, k, J) holds for all k [greater than or equal to] -1 and all J [subset or equal to] L(X).

Remark 3.7. Suppose that dim U = 1 and that X contains N' non-zero entries. Let x [member of] U and y [member of] V be non-zero vectors. Note that 0 is the only hyperplane in X. Hence, I'(X, k, J) = I(X, k, J) = ideal{[D.sup.N'+k+[chi](0).sub.y]} and P(X, k, J) = span{[p.sup.i.sub.x] : i [member of] {0, 1, ..., N' - 1 + k + [chi](0)}}.

Proposition 3.8. We use the same terminology as in Definition 3.1. Let X = ([x.sub.1], ..., [x.sub.r]) be a basis for U. Then P (X, k, J) = ker I (X, k, J) [subset or equal to] ker I'(X, k, J, E). Furthermore, for k [member of] {-1, 0}, ker I (X, k, J) = ker I'(X, k, J, E) for arbitrary E.

More precisely, writing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as shorthand notation, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.5)

For k = 0, this specializes to P(X, 0, J) = span {[p.sub.Y] : X \ Y [member of] J}. For k = -1, P(X, -1, J) = span{1} if J [contains or equal to] H and P(X, -1, J) = {0} otherwise.

For a two-dimensional example, see Example 6.1 and Figure 1.

Deletion and Contraction: In this paragraph, we define deletion and contraction for matroids X and upper sets J.

Fix an element x [member of] X. The deletion of x is the matroid defined by the sequence X \ x. Let [[pi].sub.x] : U [right arrow] U/x denote the projection to the quotient space. The contraction of x is the matroid defined by the sequence X/x which contains the images of the elements of X \ x under [[pi].sub.x].

Let Y [subset or equal to] X \ x. We write Y to denote the subsequence of X/x with the same index set as Y and vice versa.

Let J [subset or equal to] L(X) be an upper set. Then define

J \ x := {C \ x : C [member of] J and C = cl(C \ x)} [subset or equal to] L(X \ x) (3.6)

J/x := {[bar.(C \ x)] : x [member of] C [member of] J} [subset or equal to] L(X/x) (3.7)

On the proof of the Main Theorem: The Main Theorem can be proven by induction. Proposition 3.8 is used as the base case. Deletion-contraction gives rises to a short exact sequence from which the result follows. This short exact sequence is recorded in the following proposition:

Proposition 3.9. We use the same terminology as in Definition 3.1. Suppose that x [member of] X is neither a loop nor a coloop. For k = -1, we assume in addition that J [contains or equal to] H or J = {X}. Then, the following sequence is exact:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.8)

Remark 3.10. We do not know if the Main Theorem holds for k = -1 and J [not contain or equal to] H. In general, our proof does not work in this case and Proposition 3.9 is false. The difficulty of the case k = -1 was already observed by Holtz and Ron. They conjectured that the Main Theorem holds in the internal case i. e. for k = -1 and J = {X}, but they were unable to prove it [11, Conjecture 6.1]. An incorrect prove of this special case has appeared in the literature [1, Part 3 of Proposition 4.5].

4 Bases and Hilbert series

In this section, we show how to select a basis for P(X, k, J) from S(X, k, J) for k [greater than or equal to] 0 and we give several formulas for the Hilbert series of P(X, k, J).

Bases: Our construction of a basis depends on the order on X. This order is used to define internal and external activity with respect to a given basis (see [4, Section 6.6.] for a reference). Recall that B(X) denotes the set of all bases B [contains or equal to] X. Fix a basis B [member of] B(X). b [member of] B is called internally active if b = max(X \ cl(B \ b)), i. e. b is the maximal element of the unique cocircuit contained in (X \ B) [union] b. The set of internally active elements in B is denoted I(B). x [member of] X \ B is called externally active if x [member of] cl{b [member of] B : b [less than or equal to] x}, i. e. x is the maximal element of the unique circuit contained in B [union] x. The set of externally active elements with respect to B is denoted E(B).

We generalize [1, Proposition 4.21] to hierarchical spaces:

Definition 4.1. We use the same terminology as in Definition 3.1. In addition, let k [greater than or equal to] 0. Then define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.1)

Theorem 4.2 (Basis Theorem). We use the same terminology as in Definition 3.1. Let k [greater than or equal to] 0. Then B(X, k, J) is a basis for P (X, k, J).

Remark 4.3. We do not know if there is a simple method to construct bases for P(X, -1, J). This difficulty was already observed in the internal case by Holtz and Ron [11].

Recursive formulas for the Hilbert series: The following statement is a direct consequence of Proposition 3.9 and of the Main Theorem:

Corollary 4.4. We use the same terminology as in Definition 3.1. Let x [member of] X be an element that is not a coloop. For k = -1, we assume in addition that J [contains or equal to] H or J = {X}, i. e. J contains either all or no hyperplanes. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For coloops, the situation is more complicated and requires an additional definition. Fix a coloop x [member of] X. Then, X \ x is a hyperplane and the following is an upper set:

[??] := {[bar.C] : x [not member of] C [member of] J} [union] {[bar.X \ x]} [subset or equal to] L(X/x) (4.2)

[??] forgets about the flats containing x, whereas J/x forgets about the flats not containing x. While the latter is always an upper set in L(X/x), some elements of [??] are not closed unless X \ x is a hyperplane.

Theorem 4.5. We use the same terminology as in Definition 3.1. Let x [member of] X be a coloop and k [greater than or equal to] 0. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.3)

For k = -1, Hilb(ker I(X, -1, J)), t) = Hilb(ker I(X/x, k, J/x)), t) if X \ x [member of] J and otherwise Hilb(ker I (X, -1, J)), t) = 0. This holds for arbitrary non-empty upper sets J [subset or equal to] L(X).

For an example, see Example 6.1. We actually prove a more general statement, namely decomposition formulas for the P-spaces of type P(X, k, J) [congruent to] P(X/x, k, J/x) [direct sum] [[direct sum].sub.j] [p.sup.j+1.sub.x] P(X/x, k - j, [??]).

Combinatorial formulas for k [greater than or equal to] 0: Theorem 4.2 provides a method to compute the Hilbert series of a P-space combinatorially:

Corollary 4.6. We use the same terminology as in Definition 3.1. Let k [greater than or equal to] 0. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.4)

where E(B) and I(B) denote the sets of externally resp. internally active elements.

From this, we can deduce a result, which relates the dimension of P(X, 0, J) and the number of independent sets satisfying a certain property. This was already proven with a different method by Holtz, Ron, and Xu [12].

Corollary 4.7. dim P(X, 0, J) = [absolute value of {Y [subset or equal to] X : Y independent, cl(Y) [member of] J}]

Corollary 4.6 gives a formula in terms of the internal and external activity of the bases of X. For k = 0, there is also a subset expansion formula similar to the one for the Tutte polynomial. In the internal, central and external case, the Hilbert series of the P-spaces are evaluations of the Tutte polynomial [1]. In particular, Hilb(P(X, 0, {X}),t) = [t.sup.N-r][T.sub.X] (1, 1/t) and Hilb(P(X, 1, {X}),t) = [t.sup.N-r][T.sub.X] (1 + t, 1/t). The following theorem provides a formula for the semi-external case which "interpolates" between those two formulas:

Theorem 4.8. We use the same terminology as in Definition 3.1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.5)

The case k = -1 : For k = -1 , we do not know if there is such a nice formula as in Corollary 4.6 or Theorem 4.8. However, in a special case, a formula is known.

Fix [C.sub.0] [member of] L(X) and set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. All maximal missing flats in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are hyperplanes. They have unique defining normals (up to scaling). Holtz, Ron, and Xu [12] showed that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Fix an independent set K [subset or equal to] X that spans [C.sub.0]. Choose an order on X s. t. K is maximal and define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, the following theorem holds:

Theorem 4.9 ([12, p. 20]). We use the same terminology as in Definition 3.1. In addition, let [C.sub.0] [member of] L(X). Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.6)

5 Zonotopal Cox Rings

In this section, we briefly describe the zonotopal Cox rings defined by Sturmfels and Xu [19] and we show that our Main Theorem can be used to generalize a result on zonotopal Cox modules due to Ardila and Postnikov [1].

Fix m vectors [D.sub.1], ..., [D.sub.m] [member of] V and u = ([u.sub.1], ..., [u.sub.m]) [member of] [Z.sup.m.sub.[greater than or equal to]0]. Sturmfels and Xu [19] introduced the Cox-Nagata ring [R.sup.G] [subset or equal to] K[[s.sub.1], ..., [s.sub.m], [t.sub.1], ..., [t.sub.m]]. This is the ring of polynomials that are invariant under the action of a certain group G which depends on the vectors [D.sub.1], ..., [D.sub.m]. It is multigraded with a [Z.sup.m+1]-grading. For r [greater than or equal to] 3, [R.sup.G] is equal to the Cox ring of the variety [X.sub.G] which is gotten from [P.sup.r-1] by blowing up the points [D.sub.1], ..., [D.sub.m]. Cox rings have received a considerable amount of attention in the recent literature in algebraic geometry. See [13] for a survey.

Cox-Nagata rings are closely related to power ideals: let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let [I.sup.-1.sub.d,u] denote the homogeneous component of grade d of ker [I.sub.u]. Then, [R.sup.G.sub.(d, u)], the homogeneous component of [R.sup.G] of grade (d, u), is naturally isomorphic to [I.sub.d,u] ([19, Proposition 2.1]).

Cox-Nagata rings are an object of great interest but in general, it is quite difficult to understand their structure. However, for some choices of the vectors [D.sub.1], ..., [D.sub.m], we understand a natural subring of the Cox-Nagata ring very well.

Let H = {[H.sub.1], ..., [H.sub.m]} denote the set of hyperplanes in L(X). Let H [member of] [{0,1}.sup.m x N]] denote the non-containment vector-hyperplane matrix, i. e. the 0-1 matrix whose (i, j) entry is 1 if and only if [x.sub.j] is not contained in Hi.

Sturmfels and Xu defined the following structures: the zonotopal Cox ring

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5.1)

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the zonotopal Cox module of shift w for w [member of] [Z.sup.n].

Let X(a) denote the sequence of [[summation].sub.i] [a.sub.i] vectors in U that is obtained from X by replacing each [x.sub.i] by [a.sub.i] copies of itself and let e := (1, ..., 1) [member of] [Z.sup.m.sub.[greater than or equal to]0]. Ardila and Postnikov prove the following isomorphisms [1, Proposition 6.3]: [R.sup.G.sub.(d,ha))] [congruent to] P[(X(a), 1, {X}).sub.d], [R.sup.G.sub.(d, ha-e)] [congruent to] P[(X(a), 0, {X}).sub.d], and [R.sup.G.sub.(d, h a-2e)] [congruent to] P[(X(a), -1, {X}).sub.d]

Using the Main Theorem, we can generalize those results. Let [J.sub.b] := {C [member of] L(X) : [b.sub.H] = 1 for all H [subset or equal to] C} . We have the following results on hierarchical zonotopal Cox modules and their Hilbert series:

Proposition 5.1. We use the same terminology as in Definition 3.1. For the graded components of the semi-external zonotopal Cox module Z (X, Ha - e + b), the following holds:

[R.sup.G.sub.(d, ha-e+b)] [congruent to] P[(X(a), 0, [J.sub.b]).sub.d] for all d (5.2)

Proposition 5.2. We use the same terminology as in Definition 3.1. Let [C.sub.0] [member of] L(X) be a fixed flat and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (cf. Subsection 4). If b [member of] [{0,1}.sup.H] satisfies [b.sub.H] = 1 if and only if H [contains or equal to] [C.sub.0], then for the graded components ofthe semi-internal zonotopal Cox module Z(X, Ha - 2e + b)), the following holds:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5.3)

Corollary 5.3. In the setting of Proposition 5.1, the dimension of [R.sup.G.sub.(d,ha-e+b)] equals the coefficient of [t.sup.d] in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 5.4. In the setting of Proposition 5.2, the dimension of [R.sup.G.sub.(d, ha-2e+b)] equals the coefficient of [t.sup.d] in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5.4)

6 Examples

In this section, we give examples for the structures and constructions appearing in this extended abstract. Here, we do the following identifications: Sym(V) = Sym(U) = K[x, y] and K[x, y]/x = K[y].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6.1)

Let [J.sub.1] := {X, ([x.sub.1]), ([x.sub.3])}. The set of bases is B(X) = {([x.sub.1][x.sub.2]), ([x.sub.1][x.sub.3]), ([x.sub.2][x.sub.3])} and the ideal is I([X.sub.1], 0, [J.sub.1]) = ideal{[x.sup.2], [xy.sup.2], [y.sup.3]}.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now we consider the deletion and contraction of [x.sub.1] . For the upper set [J.sub.1], we obtain [J.sub.1] \ [x.sub.1] = {([x.sub.2], [x.sub.3]), ([x.sub.3])} and [J.sub.1]/[x.sub.1] = {([x.sub.2], [x.sub.3]), [bar.0]}.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Example 6.1. This is an example for the recursion in Theorem 4.5 and for Proposition 3.8. Let [X.sub.2] :=

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Fig. 1: On the left, we see P([X.sub.2], 2, [J.sub.3]) and on the right we see P([X.sub.2], 2, [J.sub.2]). For both spaces, the decompositions Corresponding to Theorem 4.5 are shown.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [J.sub.3] := {[X.sub.2], ([x.sub.1])}. This implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For a graphic description of the P-spaces involved in the decomposition, see Figure 1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Acknowledgements

I would like to thank my advisor Olga Holtz for fruitful discussions of this work and Federico Ardila for suggesting the possibility of the results in Section 5.

References

[1] F. Ardila and A. Postnikov. Combinatorics and geometry of power ideals. Trans. Amer. Math. Soc., 362(8):4357-4384, 2010. arXiv:0809.2143.

[2] A. Berget. Products of linear forms and Tutte polynomials. European J. Combin., 31(7):1924-1935, October 2010. arXiv:arXiv:0906.4774.

[3] A. Bjorner. The homology and shellability of matroids and geometric lattices. In Matroid applications, volume 40 of Encyclopedia Math. Appl. Cambridge Univ. Press, Cambridge, 1992.

[4] T. Brylawski and J. Oxley. The Tutte polynomial and its applications. In Matroid applications, volume 40 of Encyclopedia Math. Appl. Cambridge Univ. Press, Cambridge, 1992.

[5] C. de Boor, N. Dyn, and A. Ron. On two polynomial spaces associated with a box spline. Pacific J. Math., 147(2):249-267, 1991.

[6] C. de Boor, K. Hollig, and S. Riemenschneider. Box splines, volume 98 of Applied Mathematical Sciences. Springer-Verlag, New York, 1993.

[7] C. de Boor and A. Ron. The least solution for the polynomial interpolation problem. Math. Z., 210(3):347-378, 1992.

[8] C. de Concini and C. Procesi. Topics in hyperplane arrangements, polytopes and box-splines. Springer-Verlag, 2010.

[9] J. Ellis-Monaghan and C. Merino. Graph polynomials and their applications I: The Tutte polynomial. In M. Dehmer, editor, Structural analysis of complex networks. Birkhauser, 2010.

[10] J. Emsalem and A. Iarrobino. Inverse system of a symbolic power. I. J. Algebra, 174(3):1080-1090, 1995.

[11] O. Holtz and A. Ron. Zonotopal algebra. Advances in Mathematics, In Press, Corrected Proof:-, 2011. arXiv:0708.2632v3.

[12] O. Holtz, A. Ron, and Z. Xu. Hierarchical zonotopal spaces. Trans. Amer. Math. Soc., 2010. to appear, arXiv:0910.5543.

[13] A. Laface and M. Velasco. A survey on Cox rings. Geom. Dedicata, 139:269-287, 2009.

[14] M. Lenz. Hierarchical zonotopal power ideals, 2010. arXiv:1011.1136.

[15] C. Merino. The chip firing game and matroid complexes. In Discrete Mathematics and Theoretical Computer Science Proceedings, 2001.

[16] L. Moci. A Tutte polynomial for toric arrangements. to appear in Trans. Amer. Math. Soc., 2010.

[17] J. G. Oxley. Matroid theory. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1992.

[18] A. Postnikov and B. Shapiro. Trees, parking functions, syzygies, and deformations of monomial ideals. Trans. Amer. Math. Soc., 356(8):3109-3142, 2004.

[19] B. Sturmfels andZ. Xu. Sagbi bases of Cox-Nagata rings. J. Eur. Math. Soc. (JEMS), 12(2):429-459, 2010.

[20] D. G. Wagner. Algebras related to matroids represented in characteristic zero. European J. Combin., 20(7):701-711, 1999.

Matthias Lenz (1) ([dagger])

(1) Technische Universitat Berlin, Berlin, Germany

([dagger]) This work was supported by a Kovalevskaya Research Prize of Alexander von Humboldt Foundation awarded to Olga Holtz.

(i) In the original definition in [1], 1 is added to every exponent.

(ii) ker I is sometimes defined slightly differently in the literature: The pairing (*, *) is defined on [Sym(V).sup.*] x Sym(V) and ker I is the subset of [Sym(V).sup.*] that is annihilated by I. In our setting, both definitions agree.

Let X = ([x.sub.1], ..., [x.sub.N]) [subset or equal to] [R.sup.r] be a sequence of vectors that span [R.sup.r]. For a vector [eta], let m([eta]) denote the number of vectors in X that are not perpendicular to [eta]. A vector v [member of] [R.sup.r] defines a linear polynomial [p.sub.v] := [[summation].sub.i] [v.sub.i][t.sub.i] [member of] R[[t.sub.1], ..., [t.sub.r]]. For Y [subset or equal to] X, let [p.sub.Y] := [[PI].sub.x[member of]Y] [p.sub.x]. Then define

P(X) := span{py : X \ Y spans [R.sup.r]} and I(X) := ideal{[p.sup.m([eta]).sub.[eta]] : [eta] [not equal to] 0} (1.1)

The following theorem and several generalizations are well known:

Theorem 1.1 ([1,5, 11]).

P(X) = kerI(X) := span {q [member of] R[[t.sub.1], ..., [t.sub.r]] : f([partial derivative]/[partial derivative][t.sub.1], ..., [partial derivative]/[partial derivative][t.sub.r]) q = 0 for all f [member of] I(X)} (1.2)

In addition, I(X) = I'(X) := {[p.sup.m([eta]).sub.[eta]] : the vectors in X that are perpendicular to n span a hyperplane}

We show that a statement as in Theorem 1.1 holds in a far more general setting: we study the kernel of the hierarchical zonotopal power ideal

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3)

where k [greater than or equal to] -1 is an integer and [[chi].sub.J] is the indicator function of an upper set J in the lattice of flats of the matroid defined by X. We study those spaces in a slightly more abstract setting, e. g. P(X, k, J) is contained in the symmetric algebra over some K-vector space, where K is a field of characteristic zero.

The choice of a sequence of vectors X defines a large number of objects in various mathematical fields which are all related to zonotopal algebra [11]. Examples include combinatorics (matroids, matroid and graph polynomials, generalized parking functions and chip firing games if X is graphic [15, 18]), discrete geometry (hyperplane arrangements, zonotopes and tilings of zonotopes), approximation theory (box splines [6], least map interpolation) and algebraic geometry (Cox rings, fat point ideals [1, 10, 19]).

Central P-spaces (in our terminology the kernel of I'(X, 0, {X})) were introduced in the literature on approximation theory around 1990 (e. g. [5]). A dual space called D(X) appeared almost 30 years ago. See [11, Section 1.2] for a historic survey.

Recently, Olga Holtz and Amos Ron coined the term zonotopal algebra [11]. They introduced internal (k = -1) and external (k = +1) P-spaces and D-spaces. Federico Ardila and Alexander Postnikov constructed P-spaces for arbitrary integers k [greater than or equal to] -1 (Combinatorics and geometry of power ideals [1], presented at FPSAC 2009). Olga Holtz, Amos Ron, and Zhiqiang Xu [12] introduced hierarchical zonotopal spaces, i. e. structures that depend on the choice of an upper set J in addition to X and k. They studied semi-internal and semi-external spaces (i. e. k = -1 and k = 0 and some special upper sets J). The central case was treated in an algebraic setting in [8]. Other related results include [2, 20].

The least map [7] assigns to a finite set S [subset or equal to] [R.sup.r] of cardinality m an m-dimensional space of homogeneous polynomials in R [[t.sub.1], ..., [t.sub.r]]. Holtz and Ron [11] showed that in the internal, central and external case, P-spaces can be obtained via the least map if X [subset or equal to] [Z.sup.r] is unimodular. In those cases, the P-spaces are obtained by choosing the set S as a certain subset of the set of integral points in the zonotope

Z(X) := {[Nsummation over (i=1)][[lambda].sub.i][x.sub.i] :0 [less than or equal to] [[lambda].sub.i] [less than or equal to] 1} (1.4)

There is also a discrete theory, where differential operators are replaced by difference operators. ([8] and A Tutte polynomial for toric arrangements (Luca Moci) [16], presented at FPSAC 2010). In this theory, the connection with lattice points in zonotope remains valid even if X is not unimodular.

As an example for the connections between zonotopal algebra and combinatorics, we now explain various relationships between zonotopal spaces and matroid/graph polynomials. They can be deduced from the fact that both, the matroid/graph polynomials [9] and the Hilbert series of the zonotopal spaces [1] are evaluations of the Tutte polynomial.

Hilb(P(X, 0, {X}), t) equals the shelling polynomial [3] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of the matroid dual to X with the coefficients reversed. The [t.sup.N-r-i] coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] equals the number of independent sets of cardinality i in the matroid X. Let [X.sub.G] denote the reduced oriented incidence matrix of a connected graph G, i. e. the matrix that is obtained from the oriented incidence matrix by removing one row so that it has full rank. The Hilbert series of P([X.sub.G], -1, {[X.sub.G]}) is related to the flow polynomial [[phi].sub.G]. By duality it is also related to the chromatic polynomial of the graph resp. the characteristic polynomial of the matroid in the general case. The connection is as follows: if G is connected, then

[[phi].sub.G](t) = [(t - 1).sup.N-r] Hilb(P([X.sub.G], -1, {[X.sub.G]}), 1/(1 - t)) (1.5)

The four color theorem is equivalent to the following statement: if G is a planar graph and [G.sup.*] denotes its dual, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.6)

Organization of the article: In Section 2, we introduce our notation and review the mathematical background. In Section 3, we define hierarchical zonotopal power ideals. A simple description of their kernels is given by our Main Theorem. In Section 4, we construct bases for the vector spaces P(X, k, J) and we deduce several formulas for their Hilbert series. In Section 5, we apply our results to prove a statement about zonotopal Cox modules that were defined by Bernd Sturmfels and Zhiqiang Xu [19]. In Section 6, we give some examples. The full paper is available on the arXiv [14].

2 Preliminaries

Notation: The following notation is used throughout this paper: K is a fixed field of characteristic zero. V denotes a finite-dimensional K-vector space of dimension r [greater than or equal to] 1 and U := [V.sup.*] its dual. Our main object of study is a finite sequence X = ([x.sub.1], ..., [x.sub.N]) [subset or equal to] U whose elements span U. We slightly abuse notation by using the symbol [subset or equal to] for subsequences. For Y [subset or equal to] X, the deletion X \ Y denotes the deletion of a subsequence and not the deletion of a subset, i.e. ([x.sub.1], [x.sub.2]) \ ([x.sub.1]) = ([x.sub.2]) even if [x.sub.1] = [x.sub.2]. The order of the elements in X is irrelevant except in Section 4.

Matroids and posets: Let X = ([x.sub.1], ..., [x.sub.N]) be a finite sequence whose elements span U. Let M(X) := {I [subset or equal to] {1, ..., N} : {[x.sub.i] : i [member of] I} linearly independent}. Then M(X) is a matroid of rank r on N elements. X is called a K-representation of the matroid M(X). For more information about matroids, see Oxley's book [17].

We now introduce some additional matroid theoretic concepts. To facilitate notation, we always write X instead of M(X). The rank of Y [subset or equal to] X is defined as the cardinality of a maximal independent set contained in Y. It is denoted rk(Y). The closure of Y in X is defined as [cl.sub.X] (Y) := {x [member of] X : rk(Y [[union].sub.x]) = rk(Y)}. C [subset or equal to] X is called a flat if C = cl(C). A hyperplane is a flat of rank r - 1. The set of all hyperplanes in X is denoted by H = H(X).

Given a flat C [subset or equal to] X, we call [eta] [member of] V a defining normal for C if C = {x [member of] X : [eta](x) = 0}. Note that for hyperplanes, there is a unique defining normal (up to scaling). The set of bases of the matroid X (i. e. the subsequences of X of cardinality r and rank r) is denoted B(X). If x = 0, then x is called a loop. If rk( X \ x) = r - 1 , then x is called a coloop.

The set of flats of a given matroid X ordered by inclusion forms a lattice (i. e. a poset with joins and meets) called the lattice of flats L(X). An upper set J [subset or equal to] L(X) is an upward closed set, i. e. C [subset or equal to] C', C [member of] J implies C' [member of] J. We call C [member of] L(X) a maximal missing flat if C [not member of] J and C is maximal with this property.

The Tutte polynomial [4] Tx(x,y) := [[summation].sub.A[subset or equal to]X] [(x - 1).sup.r-rk(A)][(y -1).sup.[absolute value of A]-rk(A)] captures a lot of information about the matroid M(X).

Algebra: Sym(V) denotes the symmetric algebra over V. This is a base-free version of the ring of polynomials over V. The choice of a basis B = {[b.sub.1], ..., [b.sub.n]} [congruent to] V yields an isomorphism Sym(V) [congruent to] K[[b.sub.1], ..., [b.sub.r]].

A derivation on Sym(V) is a K-linear map D satisfying Leibniz's law, i. e. D(fg) = D(f)g + f D(g) for f, g [member of] Sym(V). For v [member of] V, we define the directional derivative in direction v, [D.sub.v] : Sym(U) [right arrow] Sym(U) as the unique derivation which satisfies [D.sub.v](u) = v(u) for all u [member of] U. For K = R and K = C, this definition agrees with the analytic definition of the directional derivative. It follows that Sym(V) can be identified with the ring of differential operators on U.

Now we define a pairing <*, *> : Sym(U) x Sym(V) [right arrow] K by <f, q> := (q(D)f )(0) where q(D)f means that q acts as a differential operator on f.

A graded vector space is a vector space V that decomposes into a direct sum V = [[direct sum].sub.i[greater than or equal to]0] [V.sub.i]. For a graded vector space, we define its Hilbert series as the formal power series [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A graded algebra V has the additional property [V.sub.i][V.sub.j] [subset or equal to] [V.sub.i+j]. We use the symmetric algebra with its natural grading. This grading is characterized by the property that the degree 1 elements are exactly the ones that are contained in V. A [Z.sup.n]-multigraded ring R is defined similarly: R decomposes into a direct sum [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [R.sub.a][R.sub.b] [subset or equal to] [R.sub.a+b].

A linear map f : V [right arrow] W induces an algebra homomorphism Sym(f) : Sym(V) [right arrow] Sym(W).

Homogeneous ideals and their kernels: An ideal I [subset or equal to] Sym(V) is called a power ideal [1] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some Z [subset or equal to] V \ {0} and e [member of] [Z.sup.Z.sub.[greater than or equal to]>0]. (i) [D.sub.[eta]] denotes the image of [eta] under the canonical injection V [??] Sym(V). By definition, power ideals are homogeneous.

Definition 2.1. Let I [subset or equal to] Sym(V) be a homogeneous ideal. Its kernel (or inverse system) is defined as

ker I := {f [member of] Sym(U) : <f, q> =0 for all q [member of] I} (2.1)

It is known that for a homogeneous ideal I [subset or equal to] Sym(V) of finite codimension the Hilbert series of ker I and Sym(V)/I are equal. (ii)

A remark on the notation: As zonotopal spaces were studied by people from different fields, the notation and the level of abstraction used in the literature varies. Authors with a background in spline theory usually work over [R.sup.n] while other authors prefer an abstract setting as we do.

Since the Euclidean setting captures all the important parts of the theory, a reader with no background in abstract algebra may safely make the following substitutions: K = R, U [congruent to] V [congruent to] [R.sup.n]. f [member of] R[[t.sub.1], ..., [t.sub.r]] = Sym(V) acts on R[[t.sub.1], ..., [t.sub.r]] = Sym(U) as the differential operator that is obtained from f by substituting [t.sub.i] [??] [partial derivative]/[partial derivative][t.sub.i].

Some authors work in the dual setting and consider a central hyperplane arrangement instead of a finite sequence of vectors X. While hierarchical zonotopal power ideals can be defined in both settings, it is natural for us to work with vectors as we are also interested in the zonotope Z(X).

3 Hierarchical zonotopal power ideals and their kernels

In this section, we define hierarchical zonotopal power ideals. Our Main Theorem gives a simple description of their kernels.

Definitions and the Main Theorem: Recall that U = [V.sup.*] denotes an r-dimensional vector space over a field K of characteristic zero and X = ([x.sub.1], ..., [x.sub.N]) denotes a finite sequence whose elements span U.

A vector [eta] [member of] V defines a flat C [subset or equal to] X. Define [m.sub.X](C) = [m.sub.X]([eta]) := [absolute value of X \ C]. Given an upper set J [subset or equal to] L(X), [[chi].sub.J] : L(X) [right arrow] {0,1 } denotes its indicator function. The index of [chi] and m is omitted if it is clear which upper set is meant. We define [chi] for arbitrary sets A [subset or equal to] X as [chi](A) := [chi](cl(A)).

For a given x [member of] U, we denote the image of X under the canonical injection U [??] Sym(U) by [p.sub.x]. For Y [subset or equal to] X, we define [p.sub.Y] := [[PI].sub.x[member of]Y] [p.sub.x]. For [eta] [member of] V, we write [D.sub.[eta]] for the image of [eta] under the canonical injection V [??] Sym( V) in order to stress the fact that we mostly think of Sym(V) as the algebra generated by the directional derivatives on Sym(U).

Definition 3.1 (Hierarchical zonotopal power ideals and P-spaces). Let K be a field of characteristic zero, V be a finite-dimensional K-vector space of dimension r [greater than or equal to] 1 and U = [V.sup.*]. Let X = ([x.sub.1], ..., [x.sub.N]) [subset or equal to] U be a finite sequence whose elements span U. Let k [greater than or equal to] -1 be an integer and let J [subset or equal to] L(X) be a non-empty upper set, where L(X) denotes the lattice of flats of the matroid defined by X.

Let [chi] : L(X) [right arrow] {0,1} denote the indicator function of J. Let E : L(X) [right arrow] V be a function that assigns a defining normal to every flat. Now define

I'(X, k, J, E) := ideal{[D.sup.m(C)+k+[chi](C).sub.E(C)] : C hyperplane or maximal missing flat} (3.1)

I(X, k, J) := ideal{[D.sup.m([eta])+k+[chi]([eta]).sub.[eta]] : [eta] [member of] V \ {0}} [subset or equal to] Sym(V) (3.2)

P(X, k, J) := span S(X, k, J) [subset or equal to] Sym(U) (3.3)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the definition of S(X, 0, J) can be seen as a special case of the definition of S(X, k, J) for k [greater than or equal to] 1. For examples, see Section 6, Remark 3.7, and Proposition 3.8.

Theorem 3.2 (Main Theorem). We use the same terminology as in Definition 3.1. For k = -1, we assume in addition that J [contains or equal to], i. e. J contains all hyperplanes in X. Then,

P(X, k, J) = ker I(X, k, J) [subset or equal to] ker I'(X, k, J, E) (3.4)

Furthermore, for k [member of] {-1, 0}, I'(X, k, J, E) is independent of the choice of E and P(X, k, J) = ker I(X, k, J) = ker I'(X, k, J, E).

Corollary 3.3. In the setting of the Main Theorem, P (X, k, L(X)) = P (X, k + 1, {X}).

Corollary 3.4. The Hilbert series of P(X, k, J) depends only on the matroid M(X), but not on the representation X.

Remark 3.5. One might wonder if similar theorems can be proved for k [less than or equal to] -2. One would of course need to impose extra conditions on X to ensure that the exponents appearing in the definition of the ideals are non-negative. It is easy to prove that I and I' are equal in this case. However, we do not know how to construct a generating set for the kernel. A different approach would be required: in general, it is not spanned by a set of polynomials of type [p.sub.Y] for some Y [subset or equal to] X [1].

Basic results: In this paragraph, we state an important lemma and we give an explicit formula for P(X, k, J) in two particularly simple cases.

Lemma 3.6. P (X, k, J) [subset or equal to] ker I (X, k, J) [subset or equal to] ker I'(X, k, J) holds for all k [greater than or equal to] -1 and all J [subset or equal to] L(X).

Remark 3.7. Suppose that dim U = 1 and that X contains N' non-zero entries. Let x [member of] U and y [member of] V be non-zero vectors. Note that 0 is the only hyperplane in X. Hence, I'(X, k, J) = I(X, k, J) = ideal{[D.sup.N'+k+[chi](0).sub.y]} and P(X, k, J) = span{[p.sup.i.sub.x] : i [member of] {0, 1, ..., N' - 1 + k + [chi](0)}}.

Proposition 3.8. We use the same terminology as in Definition 3.1. Let X = ([x.sub.1], ..., [x.sub.r]) be a basis for U. Then P (X, k, J) = ker I (X, k, J) [subset or equal to] ker I'(X, k, J, E). Furthermore, for k [member of] {-1, 0}, ker I (X, k, J) = ker I'(X, k, J, E) for arbitrary E.

More precisely, writing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as shorthand notation, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.5)

For k = 0, this specializes to P(X, 0, J) = span {[p.sub.Y] : X \ Y [member of] J}. For k = -1, P(X, -1, J) = span{1} if J [contains or equal to] H and P(X, -1, J) = {0} otherwise.

For a two-dimensional example, see Example 6.1 and Figure 1.

Deletion and Contraction: In this paragraph, we define deletion and contraction for matroids X and upper sets J.

Fix an element x [member of] X. The deletion of x is the matroid defined by the sequence X \ x. Let [[pi].sub.x] : U [right arrow] U/x denote the projection to the quotient space. The contraction of x is the matroid defined by the sequence X/x which contains the images of the elements of X \ x under [[pi].sub.x].

Let Y [subset or equal to] X \ x. We write Y to denote the subsequence of X/x with the same index set as Y and vice versa.

Let J [subset or equal to] L(X) be an upper set. Then define

J \ x := {C \ x : C [member of] J and C = cl(C \ x)} [subset or equal to] L(X \ x) (3.6)

J/x := {[bar.(C \ x)] : x [member of] C [member of] J} [subset or equal to] L(X/x) (3.7)

On the proof of the Main Theorem: The Main Theorem can be proven by induction. Proposition 3.8 is used as the base case. Deletion-contraction gives rises to a short exact sequence from which the result follows. This short exact sequence is recorded in the following proposition:

Proposition 3.9. We use the same terminology as in Definition 3.1. Suppose that x [member of] X is neither a loop nor a coloop. For k = -1, we assume in addition that J [contains or equal to] H or J = {X}. Then, the following sequence is exact:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.8)

Remark 3.10. We do not know if the Main Theorem holds for k = -1 and J [not contain or equal to] H. In general, our proof does not work in this case and Proposition 3.9 is false. The difficulty of the case k = -1 was already observed by Holtz and Ron. They conjectured that the Main Theorem holds in the internal case i. e. for k = -1 and J = {X}, but they were unable to prove it [11, Conjecture 6.1]. An incorrect prove of this special case has appeared in the literature [1, Part 3 of Proposition 4.5].

4 Bases and Hilbert series

In this section, we show how to select a basis for P(X, k, J) from S(X, k, J) for k [greater than or equal to] 0 and we give several formulas for the Hilbert series of P(X, k, J).

Bases: Our construction of a basis depends on the order on X. This order is used to define internal and external activity with respect to a given basis (see [4, Section 6.6.] for a reference). Recall that B(X) denotes the set of all bases B [contains or equal to] X. Fix a basis B [member of] B(X). b [member of] B is called internally active if b = max(X \ cl(B \ b)), i. e. b is the maximal element of the unique cocircuit contained in (X \ B) [union] b. The set of internally active elements in B is denoted I(B). x [member of] X \ B is called externally active if x [member of] cl{b [member of] B : b [less than or equal to] x}, i. e. x is the maximal element of the unique circuit contained in B [union] x. The set of externally active elements with respect to B is denoted E(B).

We generalize [1, Proposition 4.21] to hierarchical spaces:

Definition 4.1. We use the same terminology as in Definition 3.1. In addition, let k [greater than or equal to] 0. Then define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.1)

Theorem 4.2 (Basis Theorem). We use the same terminology as in Definition 3.1. Let k [greater than or equal to] 0. Then B(X, k, J) is a basis for P (X, k, J).

Remark 4.3. We do not know if there is a simple method to construct bases for P(X, -1, J). This difficulty was already observed in the internal case by Holtz and Ron [11].

Recursive formulas for the Hilbert series: The following statement is a direct consequence of Proposition 3.9 and of the Main Theorem:

Corollary 4.4. We use the same terminology as in Definition 3.1. Let x [member of] X be an element that is not a coloop. For k = -1, we assume in addition that J [contains or equal to] H or J = {X}, i. e. J contains either all or no hyperplanes. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For coloops, the situation is more complicated and requires an additional definition. Fix a coloop x [member of] X. Then, X \ x is a hyperplane and the following is an upper set:

[??] := {[bar.C] : x [not member of] C [member of] J} [union] {[bar.X \ x]} [subset or equal to] L(X/x) (4.2)

[??] forgets about the flats containing x, whereas J/x forgets about the flats not containing x. While the latter is always an upper set in L(X/x), some elements of [??] are not closed unless X \ x is a hyperplane.

Theorem 4.5. We use the same terminology as in Definition 3.1. Let x [member of] X be a coloop and k [greater than or equal to] 0. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.3)

For k = -1, Hilb(ker I(X, -1, J)), t) = Hilb(ker I(X/x, k, J/x)), t) if X \ x [member of] J and otherwise Hilb(ker I (X, -1, J)), t) = 0. This holds for arbitrary non-empty upper sets J [subset or equal to] L(X).

For an example, see Example 6.1. We actually prove a more general statement, namely decomposition formulas for the P-spaces of type P(X, k, J) [congruent to] P(X/x, k, J/x) [direct sum] [[direct sum].sub.j] [p.sup.j+1.sub.x] P(X/x, k - j, [??]).

Combinatorial formulas for k [greater than or equal to] 0: Theorem 4.2 provides a method to compute the Hilbert series of a P-space combinatorially:

Corollary 4.6. We use the same terminology as in Definition 3.1. Let k [greater than or equal to] 0. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.4)

where E(B) and I(B) denote the sets of externally resp. internally active elements.

From this, we can deduce a result, which relates the dimension of P(X, 0, J) and the number of independent sets satisfying a certain property. This was already proven with a different method by Holtz, Ron, and Xu [12].

Corollary 4.7. dim P(X, 0, J) = [absolute value of {Y [subset or equal to] X : Y independent, cl(Y) [member of] J}]

Corollary 4.6 gives a formula in terms of the internal and external activity of the bases of X. For k = 0, there is also a subset expansion formula similar to the one for the Tutte polynomial. In the internal, central and external case, the Hilbert series of the P-spaces are evaluations of the Tutte polynomial [1]. In particular, Hilb(P(X, 0, {X}),t) = [t.sup.N-r][T.sub.X] (1, 1/t) and Hilb(P(X, 1, {X}),t) = [t.sup.N-r][T.sub.X] (1 + t, 1/t). The following theorem provides a formula for the semi-external case which "interpolates" between those two formulas:

Theorem 4.8. We use the same terminology as in Definition 3.1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.5)

The case k = -1 : For k = -1 , we do not know if there is such a nice formula as in Corollary 4.6 or Theorem 4.8. However, in a special case, a formula is known.

Fix [C.sub.0] [member of] L(X) and set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. All maximal missing flats in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are hyperplanes. They have unique defining normals (up to scaling). Holtz, Ron, and Xu [12] showed that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Fix an independent set K [subset or equal to] X that spans [C.sub.0]. Choose an order on X s. t. K is maximal and define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, the following theorem holds:

Theorem 4.9 ([12, p. 20]). We use the same terminology as in Definition 3.1. In addition, let [C.sub.0] [member of] L(X). Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.6)

5 Zonotopal Cox Rings

In this section, we briefly describe the zonotopal Cox rings defined by Sturmfels and Xu [19] and we show that our Main Theorem can be used to generalize a result on zonotopal Cox modules due to Ardila and Postnikov [1].

Fix m vectors [D.sub.1], ..., [D.sub.m] [member of] V and u = ([u.sub.1], ..., [u.sub.m]) [member of] [Z.sup.m.sub.[greater than or equal to]0]. Sturmfels and Xu [19] introduced the Cox-Nagata ring [R.sup.G] [subset or equal to] K[[s.sub.1], ..., [s.sub.m], [t.sub.1], ..., [t.sub.m]]. This is the ring of polynomials that are invariant under the action of a certain group G which depends on the vectors [D.sub.1], ..., [D.sub.m]. It is multigraded with a [Z.sup.m+1]-grading. For r [greater than or equal to] 3, [R.sup.G] is equal to the Cox ring of the variety [X.sub.G] which is gotten from [P.sup.r-1] by blowing up the points [D.sub.1], ..., [D.sub.m]. Cox rings have received a considerable amount of attention in the recent literature in algebraic geometry. See [13] for a survey.

Cox-Nagata rings are closely related to power ideals: let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let [I.sup.-1.sub.d,u] denote the homogeneous component of grade d of ker [I.sub.u]. Then, [R.sup.G.sub.(d, u)], the homogeneous component of [R.sup.G] of grade (d, u), is naturally isomorphic to [I.sub.d,u] ([19, Proposition 2.1]).

Cox-Nagata rings are an object of great interest but in general, it is quite difficult to understand their structure. However, for some choices of the vectors [D.sub.1], ..., [D.sub.m], we understand a natural subring of the Cox-Nagata ring very well.

Let H = {[H.sub.1], ..., [H.sub.m]} denote the set of hyperplanes in L(X). Let H [member of] [{0,1}.sup.m x N]] denote the non-containment vector-hyperplane matrix, i. e. the 0-1 matrix whose (i, j) entry is 1 if and only if [x.sub.j] is not contained in Hi.

Sturmfels and Xu defined the following structures: the zonotopal Cox ring

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5.1)

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the zonotopal Cox module of shift w for w [member of] [Z.sup.n].

Let X(a) denote the sequence of [[summation].sub.i] [a.sub.i] vectors in U that is obtained from X by replacing each [x.sub.i] by [a.sub.i] copies of itself and let e := (1, ..., 1) [member of] [Z.sup.m.sub.[greater than or equal to]0]. Ardila and Postnikov prove the following isomorphisms [1, Proposition 6.3]: [R.sup.G.sub.(d,ha))] [congruent to] P[(X(a), 1, {X}).sub.d], [R.sup.G.sub.(d, ha-e)] [congruent to] P[(X(a), 0, {X}).sub.d], and [R.sup.G.sub.(d, h a-2e)] [congruent to] P[(X(a), -1, {X}).sub.d]

Using the Main Theorem, we can generalize those results. Let [J.sub.b] := {C [member of] L(X) : [b.sub.H] = 1 for all H [subset or equal to] C} . We have the following results on hierarchical zonotopal Cox modules and their Hilbert series:

Proposition 5.1. We use the same terminology as in Definition 3.1. For the graded components of the semi-external zonotopal Cox module Z (X, Ha - e + b), the following holds:

[R.sup.G.sub.(d, ha-e+b)] [congruent to] P[(X(a), 0, [J.sub.b]).sub.d] for all d (5.2)

Proposition 5.2. We use the same terminology as in Definition 3.1. Let [C.sub.0] [member of] L(X) be a fixed flat and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (cf. Subsection 4). If b [member of] [{0,1}.sup.H] satisfies [b.sub.H] = 1 if and only if H [contains or equal to] [C.sub.0], then for the graded components ofthe semi-internal zonotopal Cox module Z(X, Ha - 2e + b)), the following holds:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5.3)

Corollary 5.3. In the setting of Proposition 5.1, the dimension of [R.sup.G.sub.(d,ha-e+b)] equals the coefficient of [t.sup.d] in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 5.4. In the setting of Proposition 5.2, the dimension of [R.sup.G.sub.(d, ha-2e+b)] equals the coefficient of [t.sup.d] in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5.4)

6 Examples

In this section, we give examples for the structures and constructions appearing in this extended abstract. Here, we do the following identifications: Sym(V) = Sym(U) = K[x, y] and K[x, y]/x = K[y].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6.1)

Let [J.sub.1] := {X, ([x.sub.1]), ([x.sub.3])}. The set of bases is B(X) = {([x.sub.1][x.sub.2]), ([x.sub.1][x.sub.3]), ([x.sub.2][x.sub.3])} and the ideal is I([X.sub.1], 0, [J.sub.1]) = ideal{[x.sup.2], [xy.sup.2], [y.sup.3]}.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now we consider the deletion and contraction of [x.sub.1] . For the upper set [J.sub.1], we obtain [J.sub.1] \ [x.sub.1] = {([x.sub.2], [x.sub.3]), ([x.sub.3])} and [J.sub.1]/[x.sub.1] = {([x.sub.2], [x.sub.3]), [bar.0]}.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Example 6.1. This is an example for the recursion in Theorem 4.5 and for Proposition 3.8. Let [X.sub.2] :=

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Fig. 1: On the left, we see P([X.sub.2], 2, [J.sub.3]) and on the right we see P([X.sub.2], 2, [J.sub.2]). For both spaces, the decompositions Corresponding to Theorem 4.5 are shown.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [J.sub.3] := {[X.sub.2], ([x.sub.1])}. This implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For a graphic description of the P-spaces involved in the decomposition, see Figure 1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Acknowledgements

I would like to thank my advisor Olga Holtz for fruitful discussions of this work and Federico Ardila for suggesting the possibility of the results in Section 5.

References

[1] F. Ardila and A. Postnikov. Combinatorics and geometry of power ideals. Trans. Amer. Math. Soc., 362(8):4357-4384, 2010. arXiv:0809.2143.

[2] A. Berget. Products of linear forms and Tutte polynomials. European J. Combin., 31(7):1924-1935, October 2010. arXiv:arXiv:0906.4774.

[3] A. Bjorner. The homology and shellability of matroids and geometric lattices. In Matroid applications, volume 40 of Encyclopedia Math. Appl. Cambridge Univ. Press, Cambridge, 1992.

[4] T. Brylawski and J. Oxley. The Tutte polynomial and its applications. In Matroid applications, volume 40 of Encyclopedia Math. Appl. Cambridge Univ. Press, Cambridge, 1992.

[5] C. de Boor, N. Dyn, and A. Ron. On two polynomial spaces associated with a box spline. Pacific J. Math., 147(2):249-267, 1991.

[6] C. de Boor, K. Hollig, and S. Riemenschneider. Box splines, volume 98 of Applied Mathematical Sciences. Springer-Verlag, New York, 1993.

[7] C. de Boor and A. Ron. The least solution for the polynomial interpolation problem. Math. Z., 210(3):347-378, 1992.

[8] C. de Concini and C. Procesi. Topics in hyperplane arrangements, polytopes and box-splines. Springer-Verlag, 2010.

[9] J. Ellis-Monaghan and C. Merino. Graph polynomials and their applications I: The Tutte polynomial. In M. Dehmer, editor, Structural analysis of complex networks. Birkhauser, 2010.

[10] J. Emsalem and A. Iarrobino. Inverse system of a symbolic power. I. J. Algebra, 174(3):1080-1090, 1995.

[11] O. Holtz and A. Ron. Zonotopal algebra. Advances in Mathematics, In Press, Corrected Proof:-, 2011. arXiv:0708.2632v3.

[12] O. Holtz, A. Ron, and Z. Xu. Hierarchical zonotopal spaces. Trans. Amer. Math. Soc., 2010. to appear, arXiv:0910.5543.

[13] A. Laface and M. Velasco. A survey on Cox rings. Geom. Dedicata, 139:269-287, 2009.

[14] M. Lenz. Hierarchical zonotopal power ideals, 2010. arXiv:1011.1136.

[15] C. Merino. The chip firing game and matroid complexes. In Discrete Mathematics and Theoretical Computer Science Proceedings, 2001.

[16] L. Moci. A Tutte polynomial for toric arrangements. to appear in Trans. Amer. Math. Soc., 2010.

[17] J. G. Oxley. Matroid theory. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1992.

[18] A. Postnikov and B. Shapiro. Trees, parking functions, syzygies, and deformations of monomial ideals. Trans. Amer. Math. Soc., 356(8):3109-3142, 2004.

[19] B. Sturmfels andZ. Xu. Sagbi bases of Cox-Nagata rings. J. Eur. Math. Soc. (JEMS), 12(2):429-459, 2010.

[20] D. G. Wagner. Algebras related to matroids represented in characteristic zero. European J. Combin., 20(7):701-711, 1999.

Matthias Lenz (1) ([dagger])

(1) Technische Universitat Berlin, Berlin, Germany

([dagger]) This work was supported by a Kovalevskaya Research Prize of Alexander von Humboldt Foundation awarded to Olga Holtz.

(i) In the original definition in [1], 1 is added to every exponent.

(ii) ker I is sometimes defined slightly differently in the literature: The pairing (*, *) is defined on [Sym(V).sup.*] x Sym(V) and ker I is the subset of [Sym(V).sup.*] that is annihilated by I. In our setting, both definitions agree.

Printer friendly Cite/link Email Feedback | |

Author: | Lenz, Matthias |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 4EUGE |

Date: | Jan 1, 2011 |

Words: | 6285 |

Previous Article: | Minkowski decompositions of associahedra. |

Next Article: | Special cases of the parking functions conjecture and upper-triangular matrices. |

Topics: |