Standard monomials and extremal point sets

Tam\'as M\'esz\'aros

REVIEW 1 major objections 4 minor 19 references

Standard monomials and extremal point sets

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Extremal point sets are exactly those whose vanishing ideal has a degree-dominated universal Gröbner basis, and n term orders suffice to test them.

desk verdict Solid, honest generalization of s-extremal set systems to point sets; Theorem 6 is new and correct, though its proof needs expanding. read the letter →

arxiv 1908.03045 v1 pith:JTYZ5XQO submitted 2019-08-08 math.CO

Tamás Mészáros This is my paper · ORCID

classification math.CO MSC 05D0513P10

keywords shattering-extremalsetsystemsstandardmonomialsGröbnerbasesextremalvectorVCdimensioneliminationorderszero-dimensionalidealsdownshifts

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Finite set systems that shatter exactly as many sets as they contain have a known algebraic description through standard monomials of a vanishing ideal; this paper extends that description from 0-1 vectors to arbitrary finite point sets over any field. It proves that a point set is extremal if and only if its vanishing ideal has a universal Gröbner basis consisting of degree-dominated polynomials, and that extremality is already detected by $n$ elimination orders, one with each variable on top. This yields an $O(n^2|V|k)$ decision algorithm and a purely combinatorial downshift characterization. As an application, the same $n$-order test is shown to characterize all zero-dimensional ideals over every field, strengthening a previous characteristic-zero result. The upshot is that 'extremal' is not an exotic algebraic condition: it is a term-order symmetry of standard monomials that can be checked cheaply and has a direct combinatorial meaning for point configurations.

What carries the argument

The load-bearing mechanism is the downshift operation $D_i$, which replaces each nonempty fiber of a point set over coordinate $i$ by $\{0,1,\ldots,|fiber|-1\}$; iterated downshifts compute lex standard monomials via $\mathrm{Sm}(I(V)) = D_{i_n,\ldots,i_1}(V)$. The algebraic engine is the class of degree-dominated polynomials, polynomials whose leading monomial divides every monomial that appears in them; because such a polynomial has the same leading monomial for every term order, a family of them can serve as a universal Gröbner basis and force the standard-monomial set to be independent of term order. Elimination orders with a single variable on top are the minimal probes used to detect any failure of this independence.

What would settle it

For $n=2$, check every zero-dimensional ideal $I$ in $\mathbb{F}_p[x_1,x_2]$ with quotient dimension at most 5, for a small prime $p$ like 2: if $I$ has the same standard monomials for the two lex orders $x_1 > x_2$ and $x_2 > x_1$ but different standard monomials for, say, the degree-reverse-lexicographic order, then Theorem 6 is false. The paper predicts no such ideal exists; a finite computer search over ideals with bounded generator degree would settle it.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that extremality of finite point sets has two equivalent faces. Theorem 4 states that $V\subseteq\{0,1,\ldots,k-1\}^n$ is extremal—its standard monomials are the same for every lexicographic term order—if and only if there is a finite family of degree-dominated polynomials forming a universal Gröbner basis of the vanishing ideal $I(V)$. Theorem 5 states a sharp finiteness principle: if $V$ is not extremal, then among the $n$ elimination orders with $x_i$ largest for $i=1,\ldots,n$, two already give different standard monomial sets; so extremality can be decided from those $n$ orders alone. Theorem 6 lifts this to arbitrary zero-dimensional ideals: over any field, the standard monomials of such an ideal are the same for every term order if and only if they are the same for the $n$ elimination orders. The paper also proves Theorem 2, which identifies lex standard monomials with an explicitly downshifted copy of the point set, giving the whole theory a combinatorial reading.

Load-bearing premise

The load-bearing premise is that the standard-monomial representation and the degree-dominated Gröbner basis argument transfer unchanged from vanishing ideals of finite point sets to all zero-dimensional ideals over all fields, even though the universality property that would justify the transfer is only established in the paper for finite point sets.

Editorial extensions

If this is right

Extremality of a point set $V\subseteq\{0,\ldots,k-1\}^n$ can be decided in $O(n^2|V|k)$ time by comparing standard monomials for $n$ elimination orders.
A point set is extremal iff its vanishing ideal has a universal Gröbner basis of degree-dominated polynomials; in the $k=2$ case this recovers the classical $f_{S,H}$-polynomial characterization of s-extremal set systems.
The $n$-order criterion for zero-dimensional ideals holds over every field, not only characteristic zero: agreement on $n$ elimination orders forces agreement on all term orders.
Every coordinate-wise down-set (and up-set) in $\{0,\ldots,k-1\}^n$ is extremal, since downshifts fix them; Corollary 3 makes extremality a purely combinatorial fixed-point condition on downshift sequences.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because standard monomials are unchanged by independently relabeling the values in each coordinate, extremality is an order-combinatorial property of the configuration, not an arithmetic one; this suggests classifying extremal point sets by the poset structure of their coordinate fibers.
If the transfer behind Theorem 6 is sound, the degree-dominated universal Gröbner basis characterization of Theorem 4 should also hold for arbitrary zero-dimensional ideals with term-order-independent standard monomials; the paper only states the standard-monomial form for such ideals, leaving this as a natural extension to test.
The $n$-order test could be used as a generator: enumerating point sets fixed by all downshift compositions would produce a census of small extremal configurations and likely reveal families beyond down-sets and up-sets.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear [Colleague], here's my take on arXiv:1908.03045.

The paper does what it says and does it well. Mészáros extends the algebraic theory of shattering-extremal set systems to finite point sets over arbitrary fields. The key new result is Theorem 6, which removes the characteristic-zero assumption from Li-Zhang-Dong's criterion: for any zero-dimensional ideal, if the standard monomials agree for n elimination orders (one per variable), they agree for all term orders. That's a genuine strengthening, and the proof is correct even though it is compressed into one sentence. I checked the transfer from Theorem 5 myself: it only needs that standard monomials form a basis of the quotient and that degree-dominated polynomials have the same leading monomial in every term order. Neither radicality nor characteristic zero enters.

The rest of the paper is solid as well. Theorem 2 gives a downshift description of lex standard monomials for point sets, Theorem 4 characterizes extremal point sets as those whose vanishing ideal has a universal Gröbner basis of degree-dominated polynomials, and Theorem 5 says n elimination orders suffice to test extremality, giving an O(n^2|V|k) algorithm. Proofs are clear, and the paper is honest that much of the point-set framework already appeared in the author's thesis and the EuroComb abstract; the full presentation here is still useful.

Soft spots are minor. The one-sentence proof of Theorem 6 is the biggest presentation issue; a few lines of explanation would prevent a reader from stumbling. The definition of extremal is algebraic at first sight, but Corollary 3 gives a purely combinatorial downshift characterization, so the concept is well anchored. I see no fatal gaps or overclaims. The citation pattern is fair and builds on prior work with proper acknowledgment.

Who should read this? People working at the intersection of VC theory, shattering, and Gröbner bases. It's a competent, correct, specialized paper. I would send it to a serious referee and ask for an expanded proof of Theorem 6 before publication; the result itself holds. My recommendation: accept with minor revisions.

Referee Report

1 major / 4 minor

Summary. This paper generalizes the notion of shattering-extremal set systems to finite point sets over arbitrary fields. A finite point set V is called extremal if the sets of standard monomials of its vanishing ideal I(V) coincide for all lexicographic term orders. The paper proves that extremality is equivalent to the coincidence of standard monomials for all term orders (Proposition 10), gives a downshift description of lex standard monomials (Theorem 2), a purely combinatorial characterization of extremality via downshifts (Corollary 3), and an algebraic characterization via the existence of a universal Grobner basis of I(V) consisting of degree-dominated polynomials (Theorem 4). It then shows that extremality can be tested using n elimination orders, one per variable (Theorem 5), which yields an O(n^2|V|k) algorithm. Finally, as an application, it extends a result of Li, Zhang and Dong: for any zero-dimensional ideal over an arbitrary field, the standard monomials are the same for every term order if and only if they are the same for n elimination orders (Theorem 6).

Significance. If the results are correct, this paper provides a natural and clean generalization of the theory of s-extremal set systems, with characterizations that are both combinatorially and algebraically appealing. Theorems 2 and 4 generalize known results from set systems to vector systems, and Theorem 5 gives an efficient extremality test. Theorem 6 strengthens a result in computational algebra by removing the characteristic-zero assumption. The proofs are mostly self-contained and rely on standard facts about Grobner bases and standard monomials; the degree-dominated polynomial argument is elegant and is applied consistently. The paper also gives constructive proofs and explicit algorithms, which is a strength.

major comments (1)

[Section 3, Proof of Theorem 6] The proof of Theorem 6 is a single sentence and it invokes the universality property of standard monomials, which Section 2 establishes only for vanishing ideals of finite point sets. Since Theorem 6 is stated for arbitrary zero-dimensional ideals, this reference is confusing and leaves the transfer unproved. Please expand the proof to show explicitly that the argument of Theorem 5 applies verbatim to any zero-dimensional ideal: the standard monomials form an F-basis of F[x]/I, the number of standard monomials is dim_F(F[x]/I) for every term order, and the elimination-order argument uses only divisibility and the order property, not the radicality of the ideal or the characteristic of the field. The universality property is not needed for this transfer and should be removed or clarified.

minor comments (4)

[Section 2, Universality property paragraph] The text says 'Denote by \hat{F} the image of V'; this should be 'Denote by \hat{V} the image of V'.
[Section 3, Proof of Theorem 4] The letter S is used both for the set of standard monomials and for the set of minimal non-standard monomials; please use different notation, such as \mathcal{S}, to avoid ambiguity.
[Throughout] There are several typos, for example 'demonsrate' should be 'demonstrate', and 'zero dimensional' should be hyphenated as 'zero-dimensional' for consistency.
[Section 2, Paragraph on universality] The universality property is stated for lexicographic term orders only; it may be worth noting explicitly that this is sufficient for the reduction to V \subseteq \{0,1,\ldots,k-1\}^n, since extremality is defined via lex orders.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the point-set theorems are proved from standard monomial theory rather than from their own conclusions, and the cited prior work only supplies motivation or the set-system special case.

full rationale

The paper's derivation chain is self-contained. Extremality is defined algebraically as equality of standard monomial sets across lex orders, and Proposition 10 proves equivalence to equality across all term orders using only the basis property of standard monomials and a degree-domination argument; no theorem presupposes the conclusion. Theorem 4's two directions construct a degree-dominated universal Gröbner basis from the common standard set and, conversely, recover the common standard set from a universal Gröbner basis, with the leading-monomial divisibility characterization justifying the converse. Theorem 5 is proved by contraposition: assuming equality on the n elimination orders, any monomial outside the common set has a representation whose leading term must be that monomial for each elimination order, which forces degree domination and hence the same leading monomial for every term order; the cardinality of the standard monomial basis then gives equality everywhere. This proof uses only that the quotient is finite-dimensional and that standard monomials form a basis, so the transfer to arbitrary zero-dimensional ideals in Theorem 6 is mathematically sound; the one-sentence proof is terse but identifies exactly the features of Theorem 5 that carry over. The cited earlier results [12,18] motivate the definition and provide the set-system special case (Theorems 8 and 9), but the point-set theorems are reproved independently in the present paper rather than resting on those citations. There are no fitted parameters, no renaming of inputs as predictions, and no definitional equivalence between the claimed results and their assumptions.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no free parameters and no new postulational entities. Its results rest on standard Gröbner basis facts, the universality property for finite point sets, and the author's prior algebraic characterization of s-extremal set systems; the extremal point set concept is a definition rather than an added axiom.

assumptions (5)

standard math Standard monomials of a zero-dimensional ideal form a linear basis of F[x]/I, and their number equals dim_F(F[x]/I).
Invoked in the proofs of Proposition 10, Theorems 4, 5, and 6 to represent leading monomials by standard monomials and to compare counts of standard monomials.
domain assumption The universality property: for finite point sets V, lexicographic standard monomials are preserved under coordinate-wise injective maps and field changes.
Stated in Section 2 without proof and used to reduce all point sets to V subset {0,...,k-1}^n; it is load-bearing for Theorem 2 and the characterization results.
standard math Felszeghy-Ráth-Rónyai recursion for computing lexicographic standard monomials of finite point sets.
Cited from [8] and used in the proof of Theorem 2 and in the claimed O(n|V|k) computation of standard monomials.
standard math For set systems F, Sh(F) equals the union of Sm(I(F)) over all lex orders (Proposition 1 from [12,18]).
Used to motivate the definition of extremal point sets and to relate the new notion back to s-extremal set systems; not needed for the main point-set or zero-dimensional proofs.
standard math For a degree dominated polynomial, the dominating monomial is the leading monomial for every term order.
Proved in the text around Proposition 10 and used in Theorems 4 and 5 to ensure the leading term is term-order independent.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Standard monomials and extremal point sets." pith.science (2026). https://pith.science/paper/JTYZ5XQO

@misc{pith2026190803045,
  author       = {Pith},
  title        = {Pith review of: Standard monomials and extremal point sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JTYZ5XQO}},
  note         = {Machine review of arXiv:1908.03045}
}

abstract

We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a set $S\subseteq [n]$ if every possible subset of $S$ appears as the intersection of $S$ with some element of $\mathcal{F}$ and we denote by $\text{Sh}(\mathcal{F})$ the family of sets shattered by $\mathcal{F}$. According to the Sauer-Shelah lemma we know that in general, every set system $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets and we call a set system shattering-extremal if $|\text{Sh}(\mathcal{F})|=|\mathcal{F}|$. M\'esz\'aros and R\'onyai, among other things, gave an algebraic characterization of shattering-extremality, which offered the possibility to generalize the notion to general finite point sets. Here we extend the results obtained for set systems to this more general setting, and as an application, strengthen a result of Li, Zhang and Dong.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

[1]

Adams, P

W.W. Adams, P. Loustaunau, An Introduction to Gr¨ obner bases, Graduate Studies in Mathematics 3, American Mathematical Society, 1994

work page 1994
[2]

Anstee, L

R.P. Anstee, L. R´ onyai, A. Sali, Shattering News, Graphs and Co mbina- torics 18 (2002), 59–73. https://doi.org/10.1007/s0037302000 03

work page doi:10.1007/s0037302000 2002
[3]

Bandelt, V

H.-J. Bandelt, V. Chepoi, A. Dress, and J. Koolen, Combinatorics of lopsided sets, European Journal of Combinatorics 27 (2006), 669 –689. https://doi.org/10.1016/j.ejc.2005.03.001

doi:10.1016/j.ejc.2005.03.001 2006
[4]

Bollob´ as, I

B. Bollob´ as, I. Leader, A.J. Radcliﬀe, Reverse Kleitman Inequalit ies, Proceedings of the London Mathematical Society s3-58 (1989),15 3–168. https://doi.org/10.1112/plms/s3-58.1.153. 10

work page doi:10.1112/plms/s3-58.1.153 1989
[5]

Bollob´ as, A.J

B. Bollob´ as, A.J. Radcliﬀe, Defect Sauer Results, Journal of Co mbinato- rial Theory, Series A 72 (1995), 189–208. https://doi.org/10.101 6/0097- 3165(95)90060-8

work page 1995
[6]

Dress, Towards a theory of holistic clustering, in: B

A.W.M. Dress, Towards a theory of holistic clustering, in: B. Mirkin, F.R. McMorris, F.S. Roberts, A. Rzhetsky (Eds.), Mathematical Hierar chies and Biology, DIMACS Series in Discrete Mathematics and Theoretical Com - puter Science 37, American Mathematical Society, 1997, pp. 271– 289

work page 1997
[7]

Frankl, Extremal set systems, in: R.L

P. Frankl, Extremal set systems, in: R.L. Graham, M. Gr¨ otsch el, L. Lov´ asz (Eds.), Handbook of Combinatorics 2, MIT Press, Cambridge, 1996, pp.1293–1329

work page 1996
[8]

Felszeghy, B

B. Felszeghy, B. R´ ath, L. R´ onyai, The lex game and some ap- plications, Journal of Symbolic Computation 41 (2006), 663–681. https://doi.org/10.1016/j.jsc.2005.11.003

work page doi:10.1016/j.jsc.2005.11.003 2006

Show all 19 references

[9]

Kozma, S

L. Kozma, S. Moran, Shattering, graph orientations and conne ctivity, The Electronic Journal of Combintaorics 20-3 (2013) P44

2013
[10]

Lawrence, Lopsided sets and orthant-intersection of con - vex sets, Paciﬁc Journal of Mathematics 104 (1983), 155–173

J. Lawrence, Lopsided sets and orthant-intersection of con - vex sets, Paciﬁc Journal of Mathematics 104 (1983), 155–173. https://projecteuclid.org/euclid.pjm/1102723824

1983
[11]

Z. Li, S. Zhang, T. Dong, Finite sets of aﬃne points with unique as sociated monomial order quotient bases, Journal of Algebra and its Applicat ions 11- 2 (2012) 1250025, https://doi.org/10.1142/S021949881100549 X

2012 doi
[12]

M´ esz´ aros, S-extremal set systems and Gr¨ obner bases, Diploma Thesis, Budapest University of Technology and Economics (2010)

T. M´ esz´ aros, S-extremal set systems and Gr¨ obner bases, Diploma Thesis, Budapest University of Technology and Economics (2010)

2010
[13]

M´ esz´ aros, Algebraic Phenomena in Combinatorics: Shattering-Extremal Families and the Combinatorial Nullstellensatz, PhD Thesis, Central E u- ropean University, Budapest (2015)

T. M´ esz´ aros, Algebraic Phenomena in Combinatorics: Shattering-Extremal Families and the Combinatorial Nullstellensatz, PhD Thesis, Central E u- ropean University, Budapest (2015)

2015
[14]

M´ esz´ aros, L

T. M´ esz´ aros, L. R´ onyai, Shattering-extremal set syste ms of small VC-dimension, ISRN Combinatorics 2013 (2013) 126214, http://dx.doi.org/10.1155/2013/126214

2013 doi
[15]

M´ esz´ aros, L

T. M´ esz´ aros, L. R´ onyai, Shattering-extremal set systems of VC dimension at most 2, The Electronic Journal of Combintorics 21-4 (2014) P4.3 0

2014
[16]

M´ esz´ aros, L

T. M´ esz´ aros, L. R´ onyai, Standard monomials and extremalvector systems (extended abstract), Electronic Notes in Discrete Mathematics 6 1C (2017) 855–861. https://doi.org/10.1016/j.endm.2017.07.046

2017 doi
[17]

Moran, Shattering-extremal systems, Master Thesis, Sa arland University (2012)

S. Moran, Shattering-extremal systems, Master Thesis, Sa arland University (2012)

2012
[18]

R´ onyai, T

L. R´ onyai, T. M´ esz´ aros, Some combinatorial application of Gr¨ obner bases, in: F. Winkler (Ed.), Algebraic Informatics, CAI 2011, Lecture Note s in Computer Science 6742, Springer, 2011 pp. 65–83

2011
[19]

Shinohara, Complexity of computing Vapnik-Chervonekis dime nsion and some generalized dimensions, Theoretical Computer Science 13 7 (1995) 129–144

A. Shinohara, Complexity of computing Vapnik-Chervonekis dime nsion and some generalized dimensions, Theoretical Computer Science 13 7 (1995) 129–144. 11

1995

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Adams, P

W.W. Adams, P. Loustaunau, An Introduction to Gr¨ obner bases, Graduate Studies in Mathematics 3, American Mathematical Society, 1994

work page 1994

[2] [2]

Anstee, L

R.P. Anstee, L. R´ onyai, A. Sali, Shattering News, Graphs and Co mbina- torics 18 (2002), 59–73. https://doi.org/10.1007/s0037302000 03

work page doi:10.1007/s0037302000 2002

[3] [3]

Bandelt, V

H.-J. Bandelt, V. Chepoi, A. Dress, and J. Koolen, Combinatorics of lopsided sets, European Journal of Combinatorics 27 (2006), 669 –689. https://doi.org/10.1016/j.ejc.2005.03.001

doi:10.1016/j.ejc.2005.03.001 2006

[4] [4]

Bollob´ as, I

B. Bollob´ as, I. Leader, A.J. Radcliﬀe, Reverse Kleitman Inequalit ies, Proceedings of the London Mathematical Society s3-58 (1989),15 3–168. https://doi.org/10.1112/plms/s3-58.1.153. 10

work page doi:10.1112/plms/s3-58.1.153 1989

[5] [5]

Bollob´ as, A.J

B. Bollob´ as, A.J. Radcliﬀe, Defect Sauer Results, Journal of Co mbinato- rial Theory, Series A 72 (1995), 189–208. https://doi.org/10.101 6/0097- 3165(95)90060-8

work page 1995

[6] [6]

Dress, Towards a theory of holistic clustering, in: B

A.W.M. Dress, Towards a theory of holistic clustering, in: B. Mirkin, F.R. McMorris, F.S. Roberts, A. Rzhetsky (Eds.), Mathematical Hierar chies and Biology, DIMACS Series in Discrete Mathematics and Theoretical Com - puter Science 37, American Mathematical Society, 1997, pp. 271– 289

work page 1997

[7] [7]

Frankl, Extremal set systems, in: R.L

P. Frankl, Extremal set systems, in: R.L. Graham, M. Gr¨ otsch el, L. Lov´ asz (Eds.), Handbook of Combinatorics 2, MIT Press, Cambridge, 1996, pp.1293–1329

work page 1996

[8] [8]

Felszeghy, B

B. Felszeghy, B. R´ ath, L. R´ onyai, The lex game and some ap- plications, Journal of Symbolic Computation 41 (2006), 663–681. https://doi.org/10.1016/j.jsc.2005.11.003

work page doi:10.1016/j.jsc.2005.11.003 2006