Characterizations of polymatroidal ideals

Caius Folkerts

Abstract. A monomial ideal is polymatroidal precisely when every monomial localization has a linear resolution; among equigenerated ideals, the same property is characterized by reverse lexicographic linear quotients for every variable ordering. The localization degrees recover a polymatroid polytope, while local socle degrees detect its missing lattice points, giving a third characterization by integral closedness and local equigeneration. On the order side, every failed exchange reduces to at most four coordinates. These two reductions yield sharp degree-dependent bounds on the localizations, syzygy positions, and variable orders needed to test polymatroidality. All results hold over an arbitrary field.

1. Introduction

The exchange axiom defining a polymatroidal ideal constrains pairs of monomial generators, whereas a linear resolution records relations among the whole generating family. We show that the exchange axiom can be recovered either from linear resolutions of monomial localizations or from linear quotients in reverse lexicographic orders. The proofs identify the obstructions to exchange closely enough to determine which localizations, syzygy positions, and variable orders are needed, so the characterizations and their sharp testing forms come from the same reductions.

Let , with and . Write for the minimal monomial generating set of , and put . For , write and ; let be the coordinate unit vectors. The ideal is polymatroidal if all its minimal generators have the same degree and

For , its monomial localization

is obtained by setting the variables outside equal to one. These localizations are transitive; for . We include the zero ideal by the empty-generator convention and regard as generated by in degree zero.

Theorem 1.1 (The two characterizations).

(A): A monomial ideal is polymatroidal if and only if every monomial localization , including , has a linear resolution.
(B): An equigenerated monomial ideal is polymatroidal if and only if its minimal generators have linear quotients in decreasing reverse lexicographic order for every ordering of the variables.

Part (A) proves the conjecture of Bandari and Herzog [1], previously known for squarefree ideals and several other classes, including all ideals in at most four variables [3]. Part (B) proves the reverse lexicographic characterization proposed by Bandari and Rahmati-Asghar [2], whose lexicographic characterization had established the corresponding result for that order.

The localization proof distinguishes the convex geometry of the exponents from their possible missing lattice points. When every is equigenerated, the local generator degrees form a supermodular subset function whose polymatroid ideal is exactly , by Theorem 2.11. A missing lattice point remains missing in a smallest localization, where it lies below a socle monomial. The degree of that socle monomial then violates one of the polymatroid inequalities unless it is larger than a linear resolution permits. This is why local linear resolutions recover exchange, and also why integral closedness together with local equigeneration gives a third characterization.

The order proof uses a different local reduction. A linear presentation connects the generators inside each coordinate box. Along such a path, the first failed exchange is already visible between two exponent vectors at -distance four. A suitable reverse lexicographic order detects it. The same exchange geometry shows that a polymatroidal ideal has linear quotients when its generators are listed decreasingly under any monomial term order, as proved in Theorem 3.12.

These reductions give sharp tests as well as characterizations. For the homological criterion, it suffices to inspect a specified band of localizations and syzygy positions depending on the generator degree. Ideals with one deleted generator attain the cutoffs. For the order criterion, the exact minimum number of variable orders in unrestricted degree is for ; for every fixed generator degree at least two, the minimum has order . Sections 2 and 3 establish the two reductions, and Sections 4 and 5 determine their sharp testing forms.

2. Local degrees, socles, and integral closure

A monomial outside remains outside a smallest localization, where it lies below a socle monomial. The socle degree translates failure of membership into a violated subset inequality. Equigeneration will make the subset degrees supermodular, while the socle condition will ensure that their inequalities recover every generator; the resulting description then yields exchange.

2.1. Linear resolutions and socles.

Lemma 2.1 (Linear quotients imply a linear resolution). If are minimal generators of one degree and each is generated by variables, then has a -linear resolution.

Proof. Put and . Adjoining gives

The quotient has its shifted Koszul resolution in degrees . Induction in the long exact Tor sequence gives the same concentration for the middle ideal. □

For later use, a nonzero ideal in polynomial variables has . Indeed, a top Koszul cycle would be an element of annihilated by every variable, and multiplication by a variable is injective in the polynomial ring.

Lemma 2.2 (Socle degree). Let , with , and let have an -linear resolution. If a monomial satisfies for every , then

Proof. In the Koszul complex of , the element is a nonzero cycle in top homological degree. There are no boundaries entering this degree, so

The resolution of is obtained by placing before the resolution of . Since is -linear, the displayed Tor group can be nonzero only in total degree . Hence , as required. This argument includes and uses no assumption on the characteristic. □

2.2. Local rank inequalities. For a nonzero monomial ideal, define the subset function

It is integer-valued, nondecreasing, and satisfies .

Lemma 2.3 (Projection preserves subset minima). For ,

In particular, if is equigenerated, its generator degree is .

Proof. Project the exponents of every generator of to . The minimal generators of are exactly the divisibility-minimal members of this projected list. Every discarded member has a retained divisor, which has no larger sum on ; every retained member is itself in the original projected list. The minima are consequently equal. □

Lemma 2.4 (Local degrees are supermodular). If every is equigenerated, then

Proof. Set and . Choose minimizing . Lemma 2.3 and equigeneration give

Therefore

□

Lemma 2.5 (Local socles recover the ideal). If every is generated in degree and is concentrated in degree , then

In particular, this holds if every has a linear resolution.

Proof. Every generator of satisfies , so the forward containment holds. Let . Choose an inclusion-minimal subset such that

Such a subset exists because works, and it is nonempty because .

Put . For each , minimality gives . Thus, for some integer ,

Only finitely many multiples of can remain outside ; the exponent increment in coordinate must be less than . Choose a divisibility-maximal such multiple . It satisfies and for all . The socle assumption now gives

Hence , proving the reverse containment. For the final assertion apply Lemma 2.2 at each nonunit localization. □

Lemma 2.6 (Tight sets force exchange). Let be any supermodular function. Suppose is generated in degree and . Then is polymatroidal.

Proof. Take generator exponents and an index with . Put

This set is nonempty because . Suppose every , , fails to be a generator. These are nonnegative vectors of degree , so their monomials are outside . By (2.5), each has a violated subset inequality. Since satisfies every inequality, there is a set with

Call a set tight at if . If are tight, then

Thus every inequality is an equality, and tight sets are closed under both union and intersection. In particular,

is tight, contains , and contains no element of . Consequently for every , with strict inequality at . This gives the contradiction

The required exchange therefore exists. □

Proof of the converse in Theorem 1.1(A). Linear resolutions give equigeneration at every localization. Lemma 2.4 gives supermodularity, Lemma 2.5 gives the exact subset inequalities, and Lemma 2.6 proves the exchange axiom. □

Corollary 2.7 (Only the local socles are needed). A nonzero monomial ideal is polymatroidal if and only if every is equigenerated, say in degree , and

whenever . A zero socle satisfies this condition.

Proof. The converse is precisely Lemmas 2.4–2.6. The forward implication follows from Section 2.3 and Lemma 2.2. □

2.3. Exchange and localization.

Proposition 2.8. Every monomial localization of a polymatroidal ideal is polymatroidal.

Proof. It suffices to set . Let be the generator degree and let . Given , choose a base in the layer minimizing . If this sum is positive, exchange from toward at a surplus coordinate . The receiving coordinate satisfies , so it cannot be , since . The new base stays in the same layer and decreases the objective by one, a contradiction. Consequently for every , and the projection of divides the projection of . Thus the minimal projected generators are exactly the projections of the bases in the layer ; they all have degree .

Apply (1.1) to two bases in that layer. Their -th coordinates agree, so neither the chosen surplus coordinate nor the receiving deficit coordinate can be . Exchange remains in the same layer and descends to the projection. Iterating proves the assertion. □

Proposition 2.9. For every variable ordering, decreasing reverse lexicographic order gives linear quotients for a polymatroidal ideal.

Proof. Relabel so the variable order is . Suppose precedes , and let be the last differing coordinate. Then . Exchange from toward at gives with . Necessarily , so precedes , and

Thus every preceding colon ratio has a variable divisor supplied by an earlier generator, which is the linear-quotient condition. □

Propositions 2.8 and 2.9, together with Lemma 2.1, complete the forward implication in (A). Proposition 2.9 also proves the forward implication in (B).

Corollary 2.10 (Field independence). If every monomial localization of a fixed monomial ideal has a linear resolution over one field, then all of them have linear resolutions over every field.

Proof. Theorem 1.1(A) makes the exponent family polymatroidal. The forward proof works over every field. □

2.4. The integral closure. The local degrees determine more than the inequalities needed for the preceding proof; under local equigeneration, they recover the entire convex hull of the generators. The obstruction to polymatroidality therefore consists exactly of missing integer points, which integral closure supplies.

Theorem 2.11 (The polymatroidal integral closure). Suppose and every , including , is equigenerated. Let be the degree of , let be its generator exponents, and define by (2.2). Then

and

is polymatroidal, generated in degree . Consequently,

Proof. We first realize every greedy vector of the proposed polytope as a generator exponent of , thereby identifying the convex hull. Tight sets then lower every integral point above degree to that hull, identifying the whole monomial integral closure.

Fix a permutation and set . Starting with the generator of , successively lift a minimal generator of to a minimal generator of . Such a lift exists because every minimal projected generator is an actual member of the projected generating list. Equigeneration forces the exponent in the new coordinate to be . At the end this gives with

Certainly . Given any real vector , choose with . For , summation by parts gives

The vector attains equality. Thus every linear functional has the same minimum on and on . Both convex sets are compact, so separation proves (2.9).

Put . If an integer exponent satisfies the inequalities for and , some positive coordinate can be decreased by one while preserving every inequality. Otherwise each has a tight set containing it. Tight sets are closed under unions by supermodularity, so their union satisfies

a contradiction. Repeated reduction yields in with .

For a monomial , integrality over is equivalent to for some , by coefficient comparison in an integral equation. Clearing denominators in rational convex combinations gives the Newton criterion

The reduction above and (2.9) place every monomial of in this polyhedron, so . Conversely, let be the least total -degree of a term of a nonzero polynomial . If is integral over and , its integral equation has its leading power as the unique term of smallest -degree, a contradiction. Hence every term of belongs to every , proving . The reduction shows that is generated in degree ; Lemma 2.6 proves its exchange axiom.

For (2.11), the converse follows from (2.10). For the forward direction, Section 2.3 and Lemma 2.5 express a polymatroidal ideal as an intersection of prime powers. The same argument shows that each such prime power is integrally closed, and that their intersection is integrally closed. □

The equivalence (2.11) also holds for , since the zero ideal is integrally closed in the domain and the empty generator family satisfies exchange and local equigeneration by our convention.

Corollary 2.12 (An intersection-type characterization). A nonzero monomial ideal is polymatroidal if and only if it is an intersection of powers of monomial primes and every monomial localization is equigenerated.

Proof. An intersection of powers of monomial primes is integrally closed, as in the preceding proof. The converse therefore follows from Theorem 2.11; the forward implication follows from Lemma 2.5 and Proposition 2.8. This formulation connects the local socle argument with the ideals of intersection type studied in [4]. □

3. Local exchange and linear quotients

For monomials of one fixed degree, decreasing reverse lexicographic order compares exponents at the last differing variable; the smaller exponent comes first.

For an ordered minimal monomial generating set, linear quotients are equivalent to the following witness condition

Indeed, the ratios generate the colon ideal.

3.1. Connected boxes and nearby exchange. Let be a nonempty finite family of vectors of one total degree . For , put . Its unit-exchange graph joins two vectors when their difference is . The first syzygies have a direct interpretation in these graphs.

Lemma 3.1 (Linear presentations and connected boxes). A degree- monomial ideal has a linear presentation if and only if every nonempty has a connected unit-exchange graph. In particular, this holds whenever its generators admit a linear-quotient order.

Proof. In multidegree , the free module on the minimal generators has a basis indexed by . The first-syzygy space is the subspace of coefficient sum zero. Degree- syzygies, multiplied to degree , are spanned by the differences across unit-exchange edges. They span the whole sum-zero subspace exactly when the graph is connected. This argument is valid over every field. The last assertion follows from Lemma 2.1. □

Connectivity does not by itself prescribe which coordinate an exchange must decrease. To recover such a prescription, follow a path until the desired decrease first becomes possible. The preceding vertex and the new neighbor then differ by just two exchanges. This reduces every failure of the exchange axiom to the following local configuration.

Lemma 3.2 (A failed exchange at distance four). Suppose every nonempty has a connected unit-exchange graph. If is not polymatroidal, then the exchange axiom fails for two members with .

Proof. Choose a failed exchange from toward , with prescribed donor , and put coordinatewise. There is no -decreasing neighbor of in ; an allowed receiver would satisfy , hence , and that exchange was assumed absent.

Take a unit-exchange path in from to . Call a vertex good if it has a -decreasing neighbor in this graph. A good vertex occurs because the path must eventually lower coordinate . Let be the first good vertex and its predecessor. Up to this point the path cannot lower or raise it above its initial value . Thus

Choose a good neighbor . The case would give , making good. Hence , and

has -norm four, allowing . The only positive coordinates are . Either corresponding -decreasing exchange from would lie in the box and make good. Both are therefore absent, as required. □

Theorem 3.3 (A local exchange criterion). An equigenerated monomial ideal is polymatroidal if and only if it has a linear presentation and the exchange axiom holds for every pair of generators whose exponent vectors have -distance four.

Proof. The converse is Lemmas 3.1 and 3.2. A polymatroidal ideal has the exchange property and a linear resolution by Section 2.3. □

3.2. Reverse lexicographic quotients. To determine which variable orders suffice, we refine the nearby obstruction. Final pairs first force all exchanges having a unique receiver.

Lemma 3.4 (Orders with a prescribed final pair). Suppose that for every ordered pair of distinct variables , some linear-quotient reverse lexicographic order ends with . Then

Proof. Use an order ending in . The vector precedes , and its colon quotient is a positive power of . A variable witness must therefore have the form . It precedes only if comes after . The only possible is . □

Lemma 3.5 (A four-coordinate obstruction). Suppose every nonempty has a connected unit-exchange graph and (3.2) holds. If is not polymatroidal, there are and four distinct indices such that

and the following four vectors lie outside

Proof. The construction in Lemma 3.2 gives (3.3), with as the only possible coincidence, and with both -decreasing exchanges absent. If , the only positive coordinate of is , so (3.2) gives , a contradiction. Thus all four indices are distinct.

If belonged to , the only positive coordinate of would be , while . Formula (3.2) would give

contradicting the first absence. Interchanging proves the fourth absence. A vector with a negative coordinate is already absent from . □

Theorem 3.6 (Sufficient order coverage). Let be a nonempty family of variable orderings satisfying these two conditions

(i): every ordered pair of distinct variables occurs as the final two variables of some ordering in ;
(ii): for every and every two-element set , some ordering in ends with the two variables of , in either order, followed by .

If every reverse lexicographic order from gives linear quotients, then is polymatroidal.

Proof. Lemma 3.1 gives connectivity in every upper box, and condition (i) gives (3.2). If were not polymatroidal, take the configuration (3.3)–(3.4). By condition (ii), choose an available variable order ending with , then . The vector precedes , and its colon quotient is . A variable witness must receive at or . Its donor cannot lie before both receivers, since that neighbor would follow . The only other donors are the other receiver and , and all those exchanges are excluded by (3.4). There is no witness, a contradiction. □

Proof of Theorem 1.1(B). The forward implication is Proposition 2.9. For the converse, all variable orderings satisfy the two coverage conditions in Theorem 3.6. □

In at most three variables, the final-pair tests alone suffice; Lemma 3.5 would otherwise require four distinct indices.

3.3. Removing the degree hypothesis. The same order criterion can recover equigeneration itself if we compare monomials at their last differing coordinate without first comparing total degrees. On a finite family this gives pure reverse lexicographic order, a total order in which a proper divisor precedes a proper multiple. Although it is not a well-ordering of all monomials, it orders the finite generating set, and universal linear quotients in these orders force that set to have one degree.

Lemma 3.7 (The first generator has minimum degree). In any linear-quotient order of a minimal monomial generating set, the first generator has minimum total degree.

Proof. Let be the minimum generator degree, and let be the first degree- generator in the order. If an earlier generator exists, the nonzero colon before contains a variable, so some earlier generator satisfies

Thus . If , then , contradicting minimality of the generating set. Hence , so , contradicting the choice of . Therefore was the first generator. □

Lemma 3.8 (Coordinate bounds preserve linear quotients). Let be a finite monomial antichain having linear quotients in some order, and let . The subfamily

has linear quotients in the induced order.

Proof. For with the former earlier, take a witness in (3.1). Its exponents satisfy

The witness remains in , so the witness condition holds in the subfamily. □

Lemma 3.9 (Pure reverse lexicographic quotients force one degree). Let be a finite nonempty monomial antichain. Suppose that for every variable there is a pure reverse lexicographic linear-quotient order of whose variable ordering puts last. Then is equigenerated. In particular, this holds if every variable ordering gives pure reverse lexicographic linear quotients.

Proof. Let be the minimum degree and suppose has degree larger than . Among all degree- generators choose minimizing

The minimum is positive, since otherwise . Put coordinatewise and .

If has degree , it has no positive excess over outside , and on . Thus . Minimality forces equality, and each summand is individually bounded above by its counterpart. It follows that

Choose any and use the available variable ordering ending in . Since , the monomial precedes every degree- member of . Lemma 3.8 gives linear quotients for this subfamily, yet its first member cannot have its minimum degree , contrary to Lemma 3.7. This contradiction proves the claim. □

Corollary 3.10. For an arbitrary nonzero monomial ideal, without an equigeneration assumption, the following are equivalent

(i): is polymatroidal;
(ii): every variable ordering gives linear quotients when is ordered by pure reverse lexicographic order.

Proof. The converse follows by applying Lemma 3.9 first and then part (B). The forward implication is Proposition 2.9. □

Corollary 3.11 (Localization of universal quotients). If has linear quotients in pure reverse lexicographic order for every variable ordering, then the same is true of for every .

Proof. Corollary 3.10 makes polymatroidal. Apply Propositions 2.8 and 2.9. □

3.4. Arbitrary monomial orders.

Theorem 3.12. If is polymatroidal, its minimal generators, listed decreasingly under any monomial term order, have linear quotients. Thus the following three conditions on an equigenerated monomial ideal are equivalent

(i): is polymatroidal;
(ii): all variable-induced reverse lexicographic orders give linear quotients;
(iii): every monomial term order gives linear quotients.

Proof. For a general term order, an arbitrary allowed exchange need not move to an earlier generator. We will match every surplus unit of to a deficit unit through an exchange feasible at . Multiplicativity of the order then forces at least one of these exchanges to move earlier.

The lower-inequality description of the generator family is already proved. Fix two bases and put

Total demand equals total supply . Join to if is a base. There is a matching between copies of every donor and copies of every receiver, using these edges.

Here is the capacitated Hall verification. Fix . If , for each there is a tight set at containing and omitting . Their intersection is tight, contains , and avoids . Union over gives a tight set containing all those donors and avoiding . Use when there are none. Since ,

Subtracting from the equal total supply and demand proves

For the same inequality is immediate. Ordinary Hall matching after cloning the vertices proves the claim.

Now suppose in the chosen monomial term order. The matching pairs all factors of with all factors of , and each pair gives a feasible neighbor . If every matched , multiplicativity, followed by cancellation of the gcd, would give . Thus some pair has . For this pair

This is a linear-quotient witness. The equivalence follows from Theorem 1.1(B), since the reverse lexicographic order on an equigenerated family is the restriction of graded reverse lexicographic term order. □

Remark 3.13. The matching is one-sided; all its exchanges are feasible at the original base . It asserts neither simultaneous exchange of all matched units nor a symmetric base-ordering property.

4. Sharp homological tests

The local rank geometry identifies the missing generators. A minimal coordinate obstruction bounds the syzygy position where they are detected; rank increments then bound the localizations that must be examined. The sharp examples will reverse this procedure; deleting one generator creates a controlled socle class, and coordinate caps arrange for it to survive at just one chosen localization.

4.1. Minimal local obstructions. For a graded module, write . If a nonzero finite-length module has highest nonzero degree , its regularity is ; its Koszul groups in homological degree have total degrees at most , while a nonzero element of degree gives a top Koszul class.

Proposition 4.1 (A minimal localized obstruction). Suppose is generated in degree and every proper monomial localization is polymatroidal. Put . Then is polymatroidal, has finite length, and, if , then

In particular,

Proof. Every localization is equigenerated, so Theorem 2.11 applies. Monomial localization commutes with finite intersections, since coordinate projection commutes with least common multiples. In the expression , localization to discards exactly the nontrivial factors with . The remaining inequalities describe , by its polymatroidality and Lemma 2.3. Thus for every proper . In particular, for each variable. Since is finitely generated, a power of each variable annihilates it, and it has finite length.

Assume . Both ideals are generated in degree , so . The sequence , together with and , gives . A monomial of degree has for every . Its top Koszul class gives

so .

For completeness, is polymatroidal; in its lower inequalities increase from to and leave every proper-set value unchanged. Supermodularity is preserved, and the integer-reduction and tight-exchange proofs apply unchanged. The Newton polyhedra of and are equal, and Newton polyhedra add under products. Hence . If is polymatroidal, integral closedness forces equality with ; the converse is immediate. Since are generated in degree , this equality holds exactly when . Its least possible is . If , both sides are zero. □

4.2. How many syzygies are needed.

Theorem 4.2 (Degree-bounded localization test). A nonzero monomial ideal is polymatroidal if and only if every is equigenerated and, writing its positive generator degree as , one has

Units require no check. Equivalently, at it is enough to check positions through

Proof. Only the converse needs proof. For , let , the ideal obtained by setting variables outside equal to zero. Its minimal generators are exactly those members of supported on .

A mixed coordinate minor is obtained by setting disjoint sets of variables equal to zero and one. Local equigeneration is inherited by every nonzero such minor. Indeed, for and , put . The substitutions are disjoint, so

The right side retains some minimal generators of the equigenerated ideal . If nonzero, it has exactly the same generator degree.

Coordinate restriction also preserves multigraded Betti numbers in degrees supported on the retained variables

This is immediate from the multigraded Koszul complex. A wedge containing an omitted variable would require a negative coefficient exponent, so its multigraded component is zero.

Localization removes variables that are irrelevant to a failure, while restriction removes variables outside the support of a missing generator. A minor minimal under both operations must therefore have a missing generator of full support. Its degree will bound the number of remaining variables, and hence the position of the nonlinear socle class.

Suppose is not polymatroidal. Among its nonzero, non-polymatroidal mixed coordinate minors, choose with the fewest remaining variables, say . Let be its generator degree. By Theorem 2.11, is polymatroidal and generated in degree . Since is not, choose .

This exponent must have full support. By the Newton criterion (2.13), it lies in the convex hull of the generator exponents of ; their common total degree leaves no nonzero summand from the nonnegative orthant. If , every generator occurring with positive weight in a convex representation of is also supported on . Consequently is nonzero and . Minimality makes polymatroidal and hence integrally closed, so , a contradiction. Thus

Every proper localization of is polymatroidal and therefore satisfies the socle condition in Corollary 2.7. Since is not polymatroidal, that corollary gives a monomial socle element of of degree . A monomial can be chosen because the socle is multigraded and monomial classes form a basis of the quotient. Every lies in the degree- ideal , so and hence . As in Lemma 2.2, its top Koszul class gives

Write as a coordinate restriction of an original localization . Both have generator degree . By (4.6), the same nonlinear class occurs in . Its homological index satisfies , contradicting (4.3). This proves the converse. The forward implication follows from Theorem 1.1(A). The next proposition shows that the degree cutoff cannot be lowered uniformly. □

Proposition 4.3 (The nonlinear strand of a deleted generator). Let have and support of size , and set

Every proper monomial localization is the unit ideal. The only possible nonlinear entries are

where a binomial coefficient outside its usual range is zero. More precisely, the nonlinear multigraded entries are one in degrees with and , and zero otherwise. In particular, the first nonlinear position is . When has full support, the sole nonlinear entry is .

Proof. All pure powers are retained, so every proper localization is the unit ideal. Put . For every , choose ; the retained monomial divides . Hence . Both and have -linear resolutions. The long exact Tor sequence leaves only degrees and in , and identifies the latter with the cokernel of

Consider a target basis class . If , choose . Compute the boundary

in the ambient polynomial Koszul complex. All its coefficients have degree , so it is a cycle in , although its primitive need not belong to . It maps to the chosen class up to sign; every other coefficient is a retained generator. This lifts every target class whose exterior support misses a variable of . The remaining classes cannot lift; if , the map is zero in that fine degree. Indeed every ambient polynomial Koszul cycle of positive internal degree is a boundary. A boundary could have a nonzero coefficient at only from a term with and , which is impossible. Thus the cokernel has precisely the asserted basis. Counting the sets gives (4.8). □

Taking and shows that the cutoff in Theorem 4.2 cannot be lowered to .

4.3. Which localizations are needed. We next bound how many variables may be omitted from a localization that needs to be tested. If a bad localization is maximal, restoring any omitted variable raises its minimum generator degree by at least one. Supermodularity makes these increases add, bounding the number of omitted variables in terms of the original degree.

Lemma 4.4 (The degree cost of a maximal obstruction). Let be generated in degree , and let be inclusion-maximal among the sets whose localization is not equigenerated, or among those whose localization does not have a linear resolution. Then

In the second case, if all localizations are equigenerated, then .

Proof. The unit ideal and nonzero ideals in at most one variable satisfy both properties. Every strict superset of is equigenerated. For , equality would force every generator of to have zero -exponent; its projection cannot have degree below . This would make it a polynomial extension of , contradicting maximality. Each such rank increment is therefore at least one.

The supermodularity proof in Lemma 2.4 uses equigeneration only at the union. It consequently applies throughout . Successively adjoining the omitted variables gives . A nonunit localization has ; an equigenerated ideal of degree one is generated by variables, so a nonlinear one has degree at least two. □

Theorem 4.5 (Degree-dependent localization coverage). Let and let be generated in degree . It is polymatroidal if and only if has a linear resolution for every with

Every prime in this collection is individually necessary for a fixed family of localization tests valid for all degree- ideals. Thus the exact minimum number of tests is

If all monomial localizations are assumed equigenerated in advance, the sharp bound is instead , with minimum number .

Sufficiency. An inclusion-maximal localization without a linear resolution must lie in the stated range by Lemma 4.4. Thus the tests force all localizations to have linear resolutions, and Theorem 1.1(A) applies. Under prior local equigeneration the same lemma improves the codimension bound to . The constructions below prove necessity and the counts. □

Lemma 4.6 (A deleted bounded-Veronese generator). Let the variables be partitioned into and . Let be a positive-degree monomial in , let , and put . Take all degree- monomials with exponents at most one on , except . The resulting ideal has linear quotients in every decreasing reverse lexicographic order whose last variable belongs to .

For with , its localization to is generated by all degree- monomials capped by one on , except .

Proof. Fix an order whose last variable lies in . The full bounded family permits every surplus-to-deficit exchange. For an earlier target and a current base , take the usual witness , where is their last differing coordinate. If it is retained, there is nothing to prove. Otherwise it equals the deleted . The donor cannot be , since would then have -exponent two, violating the cap. The receiver cannot be , since the usual witness precedes . Thus has -exponent one. The alternative generator

satisfies every coordinate cap, differs from because , and precedes . Its colon quotient is , which divides the target’s colon quotient.

For the projection assertion, put . The caps on the omitted variables give the minimum projected degree . Every retained monomial of that degree lifts by adjoining all omitted variables, whereas has only the deleted lift . A higher-degree projection has a divisor of the minimum degree; only could be missing. Such a projection then has an extra factor with , since already saturates all surviving caps. Choose , possible by the support hypothesis. The retained monomial is another divisor of the minimum degree. Thus no higher-degree projection is minimal. □

Proposition 4.7 (Isolating a single bad localization). Fix with , and let , .

(i): There is a degree- monomial ideal for which every localization is equigenerated and is the only localization without a linear resolution.
(ii): If , there is such a unique bad localization for an ideal of degree , with not equigenerated.

These degrees are the smallest possible under the respective conditions. For , the smallest equigenerated example has degree two.

Proof. For (i), choose distinct , put , and let consist of all degree- monomials with exponents at most one on , except . All pure powers of the variables in remain, so a localization omitting any variable of is the unit ideal.

At , for , the minimal generators are exactly the degree- monomials capped by one on , except , by the projection assertion of Lemma 4.6.

When , Lemma 4.6 gives a linear resolution. When , the localization is with removed. That monomial is a socle element of degree two, whereas a linear resolution would force degree one. This proves (i).

For (ii), fix , and delete from the degree- family with the same caps. Again a localization omitting a -variable is the unit ideal. If , its minimal generators are the degree- capped family with removed, since still has support at least two. Lemma 4.6 gives both this description and linear quotients. The remaining localization is exactly

which is not equigenerated. The variables in this list lift by multiplying , and lifts by omitting any one -variable; itself would lift only to the deleted generator.

The lower degree bounds follow from Lemma 4.4, applied to the unique bad localization. When all locals are equigenerated it gives ; otherwise, for proper , it gives . An equigenerated ideal of degree zero or one is polymatroidal, proving the remaining maximal-prime claim. □

To finish the necessity assertion in Theorem 4.5, take the corresponding isolator and multiply it by a monomial to raise its degree to . Such multiplication merely shifts each localized resolution and each exchange vector; it preserves exactly which localizations are linear. Thus omitting any prime in the claimed test collection admits a counterexample passing all remaining tests. Counting subsets gives the stated sums.

Corollary 4.8 (Unbounded degree). For arbitrary generator degrees, every coordinate prime generated by at least two variables is individually necessary in a fixed localization-testing characterization. The exact number of necessary tests is .

4.4. The joint homological bound. The degree bounds in Sections 4.2 and 4.3 can be imposed simultaneously. Write .

Theorem 4.9 (Triangular homological characterization). Let be generated in degree . Then is polymatroidal if and only if, for every with and , the following conditions hold

(i): is equigenerated, say in degree ;
(ii): if , its resolution is linear through position

Equigeneration is the test in homological position zero. In particular, at no positive syzygy position needs to be checked. The assertion holds over every field.

Proof. Condition (i) forces every localization to be equigenerated; otherwise Lemma 4.4 places a maximal nonpure localization among the tested sets. Thus is globally supermodular.

If were not polymatroidal, the obstruction constructed in the proof of Theorem 4.2 would give a localization , of degree , with a nonlinear Betti number in some position . Choose inclusion-maximal subject to . Every degree- generator of projects into the degree- ideal , so its exponents on vanish. Therefore

The same nonlinear Betti number occurs in . Maximality gives for each . Supermodularity then yields

Since also and , this contradicts the required test (4.12). The forward implication is Theorem 1.1(A). □

Proposition 4.10 (Sharpness of the initial-segment depths). Fix , , and put . If , there is a degree- ideal whose only localization without a linear resolution is , for which every localization is equigenerated, and whose first nonlinear syzygy at has position

At every outer-band set , the generation test is individually necessary as well.

Proof. Suppose first . Put , choose with , and let . From all degree- monomials capped by one on , delete

Every localization omitting a variable of is the unit ideal. At , , the minimal generators are the degree- family capped by one on , with deleted. This is the projection assertion of Lemma 4.6, whose support hypothesis holds because . For , the same lemma gives linear quotients.

At , the ideal is with removed. Its deleted monomial has support size , so Proposition 4.3 gives first nonlinear position directly.

If , use this construction in degree , with , and multiply by a monomial of degree . Such multiplication preserves all localized linearity properties and their homological positions. The first nonlinear position is , as required. Finally, the mixed-degree isolator in Proposition 4.7(ii), with , proves the outer-band assertion. □

The sharpness statement concerns predetermined initial segments depending only on . It does not assert that every intermediate Betti position is indispensable in an arbitrary selection of homological tests; for example, Corollary 2.7 uses a different selection.

5. Sharp families of variable orders

The four-coordinate obstruction also determines the variable orders that a fixed testing family must contain. A prescribed final pair forces single-receiver exchanges, while a prescribed final triple rules out the remaining two-receiver failure. To show that neither pattern can be omitted, we construct ideals whose failing orders are exactly those realizing that pattern. The family here is chosen before the ideal and must work in every generator degree; the fixed-degree version will require only patterns on a bounded number of variables.

Lemma 5.1 (An exact final-pair obstruction). Let , fix distinct , and put . Take all degree- monomials with exponents at most one on , and remove the generator . The resulting ideal is not polymatroidal. Its reverse lexicographic order fails to have linear quotients exactly for the variable orderings ending in .

Proof. Before removing , every surplus-to-deficit unit exchange respects the coordinate bounds. Thus a failed prescribed exchange after removal must have a single receiver , and the current base must be . Since every -coordinate of is at its upper bound, the donor is or ; since , the receiver is or an element of . If , a target with as its only positive deficit can increase it by only one, so equality of degrees forces the target to be , which is absent. The sole remaining failure has current base

donor , and receiver . It occurs, for example, against , where .

Every pair outside this exceptional case has the ordinary last-differing-coordinate colon witness. At , the only variable witnesses for an exceptional target are , . Such a witness precedes exactly when comes before . Hence all these witnesses are unavailable exactly when all come before . Under that condition, an exceptional target precedes exactly when comes after . This is precisely the claimed final pair. □

Lemma 5.2 (An exact final-triple obstruction). Let , fix a two-element set and , and put . Take every degree- monomial such that

(i): each exponent on is at most one; and
(ii): either the exponent of is positive, or both exponents on are positive.

The resulting ideal is not polymatroidal. Its reverse lexicographic order fails to have linear quotients exactly when the final three variables are , in either order, then .

Proof. The coordinate bounds alone preserve every surplus-to-deficit exchange. Examine when condition (ii) can fail after a move. If the current -exponent is at least two, or is one and the donor is not , it persists. If that exponent is one and the donor is , a target with zero -exponent has both -coordinates positive. When the current base already has both positive, any exchange works; when it has exactly one positive, exchange into the other works. When it has neither, the degree and coordinate bounds force the unique current base

Finally, if the current -exponent is zero, the only move that could destroy condition (ii) decreases an -coordinate of exponent one. The target then has that coordinate zero and therefore has positive -exponent; exchanging into works. Thus the only failed prescribed exchanges are at , with donor , against targets of positive-deficit set . Such a target exists; , for .

At , the possible variable witnesses for such a target are exactly , for and . They all follow exactly when every -variable comes before both -variables. Under that condition a target precedes exactly when comes after both variables of . All other pairs have the ordinary exchange witness. This proves the exact failure signature. □

Theorem 5.3 (Exact coverage and minimum number of tests). For , a fixed family of variable orders characterizes polymatroidality among all equigenerated monomial ideals if and only if it satisfies both coverage conditions in Theorem 3.6. The minimum possible size is

Empty families are allowed in defining the minimum.

Proof. The two isolator lemmas show that each coverage condition is necessary, and Theorem 3.6 proves sufficiency. Each permutation supplies exactly one pointed final triple, so the triple isolators give the lower bound .

For the matching upper bound, fix the final variable . Orient the complete graph on so that every vertex has an incoming edge; orient a Hamilton cycle cyclically and orient all remaining edges arbitrarily. For every directed edge , choose one order ending in , with all other variables earlier. There is exactly one order per pointed final triple, and every final pair occurs because has an incoming edge. Doing this for all attains the bound.

In one variable every nonzero equigenerated ideal is principal. In two variables, one linear-quotient order makes the unit-exchange graph connected; the degree- monomials form a line, so a connected subset is an interval and is polymatroidal. Zero tests fail, as shows. For three variables all six orders suffice, and each of the six final-pair isolators fails exactly one of them, so all six are necessary. □

5.1. Coverage in a fixed degree. In degree , a current generator has at most positive donor coordinates besides a prescribed donor. Their relative positions are all that the colon-witness argument needs to control. Thus the final triples of the unrestricted test can be replaced by patterns on a bounded number of variables.

For pairwise disjoint , with , say that a variable ordering realizes the pattern if every element of comes before both elements of , and both elements of come before . Variables outside these sets may occur anywhere.

Theorem 5.4 (Degree-sensitive order coverage). Fix , , and . A fixed family of variable permutations characterizes polymatroidality among all degree- monomial ideals by its reverse lexicographic linear-quotient tests if and only if

(i): for every disjoint with and , some order in realizes ;
(ii): if , each ordered pair of distinct variables occurs as the final two variables of some order in .

When , condition (i) alone suffices. For , all six permutations are necessary and sufficient; for , any nonempty family suffices. If or , no tests are needed.

Proof. For necessity of (i), use the triple isolator of Lemma 5.2 on the active variables . It has degree . Extend it to and multiply by a monomial to raise its degree to . Unused variables and a common monomial factor affect neither generator comparisons nor colon quotients. Thus this nonpolymatroidal ideal fails exactly the orders realizing the given pattern. If , the degree- pair isolator, similarly padded, proves necessity of (ii).

For sufficiency, first establish the singleton-deficit exchange property (3.2). When , condition (ii) and Lemma 3.4 do this. Suppose . Let , let be the sole coordinate where , and fix a donor with . Put

Since , one has . Extend to a set of size disjoint from , and choose . This is possible since ; moreover . Use (i) with . In that order is the last differing coordinate of , so precedes . Any variable colon witness must receive . Every possible donor other than belongs to and precedes , so such a move would follow . The witness must therefore be . This proves (3.2).

Condition (i) supplies at least one order, so Lemma 3.1 gives connectivity in every upper box. If the ideal were not polymatroidal, Lemma 3.5 would give four distinct indices and

with the four absences in (3.4). Put and . Since , its size is at most . Extend it to a set of size , disjoint from , and choose an order realizing . The target precedes , since and is last among the four differing coordinates. A variable witness must receive or . A donor outside either lies in , giving a later generator, or has exponent zero. The remaining donors are excluded by the four absences. This contradicts linear quotients. The small- assertions follow from Theorem 5.3 and its degree-two pair examples. □

Corollary 5.5 (Numbers of degree- tests). Let be the minimum size of such a fixed family. For and ,

For , put

Then

For , if , one also has

Consequently for every fixed as tends to infinity.

Proof. For , the patterns are pointed final triples. Each permutation covers exactly one, so their isolators give the lower bound in (5.2). For , choose one orientation for each such triple. For larger degrees, the oriented-cycle construction in Theorem 5.3 also covers every final pair, with the same number of permutations.

For , there are required patterns. A uniformly random permutation realizes a fixed pattern with probability

For independent random permutations, the probability that at least one pattern is missed is at most . The stated upper bound makes this quantity less than one. Repeated permutations may be discarded. Every permutation covers exactly patterns, one for each active -set. Dividing by this number gives the lower bound in (5.3).

Pattern coverage also supplies every relative order on three distinct variables; put in , in , and take , filling the remaining disjoint slots. Fix . For each , form its binary signature across the orders, with a one exactly when precedes . For distinct , both and occur, so their signatures are incomparable. They form an antichain in the Boolean lattice on elements. Its size is at most the middle binomial coefficient; counting pairs consisting of an antichain member and a maximal chain gives . This proves (5.4), hence . The upper bound is , which proves the final assertion. □

5.2. The probability of detecting failure.

Theorem 5.6 (Sharp rejection fraction). Fix and , and put . For every nonpolymatroidal ideal generated in degree , a uniformly random ordering of the variables makes decreasing reverse lexicographic order fail to have linear quotients with probability at least

This bound is attained. For , the sharp probability is ; for , it is one.

Proof. If no variable ordering gives linear quotients, the assertion is immediate. Otherwise the upper-box connectivity lemma applies.

Suppose first that a singleton-deficit exchange fails, with unique receiver and donor . When , construct exactly as in the singleton-deficit part of the proof of Theorem 5.4. Every order realizing this fixed pattern fails; the target precedes the current generator and there is no variable witness. The pattern has active variables and occurs with probability . When , every order ending in fails. Its probability is

as .

If all singleton-deficit exchanges hold, Lemma 3.5 gives the four-coordinate configuration. The final part of the proof of Theorem 5.4 constructs a fixed pattern with , every realization of which fails. Its probability is again the value in (5.5).

For equality, use the triple isolator on active variables. It has degree . Extend by the remaining variables and multiply by a monomial of degree . Lemma 5.2 shows that its failure orders are exactly one of the displayed patterns, giving the claimed probability. For three variables the pair isolator fails exactly one of the six orders, and the full characterization forces at least one failure. For two variables, the proof of Theorem 5.3 shows that even one successful order would force polymatroidality. □

Thus independent random order tests miss a fixed nonpolymatroidal degree- ideal with probability at most , where is the sharp value in (5.5).

References

[1]: S. Bandari and J. Herzog, Monomial localizations and polymatroidal ideals, European Journal of Combinatorics 34 (2013), 752–763. arXiv 1206.3069.
[2]: S. Bandari and R. Rahmati-Asghar, On the polymatroidal property of monomial ideals with a view towards orderings of minimal generators, Bulletin of the Iranian Mathematical Society 45 (2019), 657–666. DOI 10.1007/s41980-018-0157-z. arXiv 1808.06438.
[3]: A. Mafi and D. Naderi, Linear resolutions and polymatroidal ideals, Proceedings of the Indian Academy of Sciences (Mathematical Sciences) 131 (2021), article 25. DOI 10.1007/s12044-021-00620-z.
[4]: J. Herzog and M. Vladoiu, Monomial ideals with primary components given by powers of monomial prime ideals, Electronic Journal of Combinatorics 21 (2014), no. 1, Paper P1.69. DOI 10.37236/3813.