Improve this page

#Newton polytopes

Given a polynomial \[f=\sum_{\alpha} c_\alpha \xvec^\alpha \in \setC[x_1,\dotsc,x_n],\] with \(\alpha\in\setN^n,\) the support of \(f\) is \[\operatorname{supp}(f)\coloneqq \{\alpha : c_\alpha \neq 0\}.\] The Newton polytope of \(f\) is the convex hull of the support. We denote it by \(\operatorname{Newton}(f).\)

Newton polytopes turn questions about monomial supports into questions about lattice points and convex geometry. In algebraic combinatorics, this is useful for Schur, key, Schubert, Grothendieck, chromatic, and related polynomials. The same language also appears naturally in Lorentzian polynomials, where the support is controlled by \(M\)-convexity.

#Saturated Newton polytopes

A polynomial has a saturated Newton polytope (SNP) if \[\operatorname{Newton}(f)\cap \setZ^n = \operatorname{supp}(f).\] Equivalently, every lattice point in the Newton polytope occurs as the exponent vector of a monomial with nonzero coefficient.

Several classical polynomials, such as Schur polynomials and Stanley symmetric functions, have saturated Newton polytopes. A foundational source for this circle of questions is the paper of C. Monical, N. Tokcan, and A. Yong [MTY19], where many conjectures were formulated.

Key polynomials and Schubert polynomials have SNP [FMD18]. Key polynomials in other types (\(A_r,\) \(B_r,\) \(C_r,\) \(F_4,\) \(G_2\)) also have SNP; see [BJK23]. G. Panova and C. Zhao prove special cases of the Monical–Tokcan–Yong conjecture that Kronecker products of Schur functions have saturated Newton polytopes [PZ23]. Their arguments use Horn inequalities for Littlewood–Richardson coefficients and imply necessary conditions for positivity of Kronecker coefficients.

M. Sanchez studies when matroid polytopes, flag matroid polytopes, Bruhat interval polytopes, and Schubitopes are Mirković–Vilonen polytopes [San23]. In particular, the Newton polytopes of Schubert polynomials and key polynomials are Mirković–Vilonen polytopes.

J. Dou, N. J. Y. Fan, and K. Liu characterize when a Schubitope is lattice-free, meaning that its only lattice points are its vertices [DFL26]. This is equivalent to its Ehrhart polynomial factoring as the product of the Ehrhart polynomials of the column Schubert-matroid polytopes. For Schubert and Grothendieck Newton polytopes, lattice-freeness is characterized by avoidance of \(1423,1432,13254,\) and the result settles support conjectures for this class.

M. Besson, S. Jeralds, and J. Kiers extend part of this Demazure-polytope picture to affine Demazure modules [BJK24]. Their affine Demazure weight polytopes are cut out by inequalities governed by standard, opposite, and semi-infinite Bruhat orders, while their face vertices are described using twisted Bruhat orders.

SNP for chromatic symmetric polynomials obtained from incomparability graphs of \((3+1)\)-free posets was proved by J. P. Matherne, A. H. Morales, and J. Selover [MMS22].

For more background and results, see [WZZ24]. In [NNTN+23], the authors prove SNP for many families of symmetric functions, such as Schur-\(P\) and Schur-\(Q\) polynomials, as well as many of the families above. Moreover, they prove that \(\operatorname{Newton}(f)\) has the integer decomposition property in many cases.

#\(M\)-convexity

A subset \(J\subseteq\setN^n\) is \(M\)-convex if for all \(\alpha,\beta\in J,\) and any index \(i\in[n]\) with \(\alpha_i\gt{}\beta_i,\) there is some index \(j\) with \(\alpha_j\lt{}\beta_j\) and \[\alpha-e_i+e_j\in J.\] Here \(e_i\) is the \(i^\thsup\) unit vector. This is the integer-lattice version of the exchange axiom: for a matroid, the indicator vectors of the bases form an \(M\)-convex subset of \(\{0,1\}^n.\)

Theorem (See [Diz20]).

A homogeneous polynomial \(f\) is \(M\)-convex if and only if \(f\) has a saturated Newton polytope and this Newton polytope is a generalized permutohedron.

Key polynomials are \(M\)-convex; this was conjectured earlier by C. Monical, N. Tokcan, and A. Yong [MTY19], and proved in [FGPS20]. In [WZZ24], it is proved that affine Stanley symmetric functions and cylindric skew Schur functions are \(M\)-convex.

S. An, K. Tung, and Y. Zhang characterize the support of dual Schubert polynomials as a Minkowski sum over the inversions of the indexing permutation [Thm. 1.2, ATZ24]. This gives an elementary proof that dual Schubert polynomials are \(M\)-convex, have saturated Newton polytopes, and have Newton polytopes which are generalized permutohedra [Cor. 1.3, ATZ24]. They also give a combinatorial description of the vertices of these Newton polytopes.

#Relation with Lorentzian polynomials

The support condition in the definition of a Lorentzian polynomial is exactly \(M\)-convexity. Thus Lorentzian polynomials combine a discrete convex support condition with a Hessian-signature condition. In particular, if \(B\) is the set of bases of an integral polymatroid, then the normalized support polynomial \[\sum_{\alpha\in B} \frac{\xvec^\alpha}{\alpha_1!\alpha_2!\dotsm\alpha_n!}\] is Lorentzian [BH20]. For ordinary matroids this recovers the basis-generating polynomial.

Bibliography

  1. [ATZ24]Serena An, Katherine Tung and Yuchong Zhang. Newton polytopes of dual Schubert polynomials. arXiv:2411.16654, 2024.
    .bib
    @article{AnTungZhang2024x,
  author = {Serena An and Katherine Tung and Yuchong Zhang},
  title = {Newton polytopes of dual {S}chubert polynomials},
  year = {2024},
  eprint = {2411.16654},
  url = {https://arxiv.org/abs/2411.16654},
  journal = {arXiv e-prints}
}
  2. [BJK23]Marc Besson, Sam Jeralds and Joshua Kiers. Weight polytopes and saturation of Demazure characters. Mathematische Annalen, May 2023.
    .bib
    @article{BessonJeraldsKiers2023,
  title = {Weight polytopes and saturation of {D}emazure characters},
  ISSN = {1432-1807},
  url = {http://dx.doi.org/10.1007/s00208-023-02617-7},
  DOI = {10.1007/s00208-023-02617-7},
  journal = {Mathematische Annalen},
  publisher = {Springer Science and Business Media LLC},
  author = {Besson,  Marc and Jeralds,  Sam and Kiers,  Joshua},
  year = {2023},
  month = may 
}
  3. [BJK24]Marc Besson, Sam Jeralds and Joshua Kiers. Affine Demazure Weight Polytopes and Twisted Bruhat Orders. arXiv:2404.03142, 2024.
    .bib
    @article{BessonJeraldsKiers2024x,
  author = {Marc Besson and Sam Jeralds and Joshua Kiers},
  title = {Affine {D}emazure {W}eight {P}olytopes and {T}wisted {B}ruhat
    {O}rders},
  year = {2024},
  eprint = {2404.03142},
  url = {https://arxiv.org/abs/2404.03142},
  journal = {arXiv e-prints}
}
  4. [BH20]Petter Brändén and June Huh. Lorentzian polynomials. Annals of Mathematics, 192(3), November 2020.
    .bib
    @article{BrandenHuh2020,
  title = {Lorentzian polynomials},
  volume = {192},
  ISSN = {0003-486X},
  url = {http://dx.doi.org/10.4007/annals.2020.192.3.4},
  DOI = {10.4007/annals.2020.192.3.4},
  number = {3},
  journal = {Annals of Mathematics},
  publisher = {Annals of Mathematics},
  author = {Br{\"{a}}nd{\'{e}}n,  Petter and Huh,  June},
  year = {2020},
  month = nov
}
  5. [Diz20]Avery J St. Dizier. Combinatorics of Schubert polynomials. Cornell university, 2020.
    .bib
    @phdthesis{DizierPhDThesis,
  author       = {Dizier, Avery J St.},
  school       = {Cornell university},
  title        = {Combinatorics of {S}chubert Polynomials},
  doi          = {10.7298/an87-a834},
  year         = {2020},
}
  6. [DFL26]Jinren Dou, Neil J. Y. Fan and Kunwen Liu. Lattice-free Schubitopes. arXiv:2605.10016v1, 2026.
    .bib
    @article{DouFanLiu2026x,
  author = {Jinren Dou and Neil J. Y. Fan and Kunwen Liu},
  title = {Lattice-free {S}chubitopes},
  year = {2026},
  eprint = {2605.10016v1},
  url = {https://arxiv.org/abs/2605.10016v1},
  journal = {arXiv e-prints}
}
  7. [FGPS20]Neil J. Y. Fan, Peter L. Guo, Simon C. Y. Peng and Sophie C. C. Sun. Lattice points in the Newton polytopes of key polynomials. SIAM Journal on Discrete Mathematics, 34(2):1281–1289, January 2020.
    .bib
    @article{FanGuoPengSun2020, 
  title={Lattice Points in the {N}ewton Polytopes of Key Polynomials}, 
  volume={34}, 
  ISSN={1095-7146}, 
  url={http://dx.doi.org/10.1137/19M1305562}, 
  DOI={10.1137/19m1305562}, 
  number={2}, 
  journal={SIAM Journal on Discrete Mathematics}, 
  publisher={Society for Industrial & Applied Mathematics (SIAM)}, 
  author={Fan, Neil J. Y. and Guo, Peter L. and Peng, Simon C. Y. and Sun, Sophie C. C.}, 
  year={2020}, 
  month=jan, 
  pages={1281--1289}
}
  8. [FMD18]Alex Fink, Karola Mészáros and Avery St. Dizier. Schubert polynomials as integer point transforms of generalized permutahedra. Advances in Mathematics, 332:465–475, July 2018.
    .bib
    @article{FinkMeszarosDizier2018,
  doi = {10.1016/j.aim.2018.05.028},
  url2 = {https://doi.org/10.1016/j.aim.2018.05.028},
  year  = {2018},
  month = jul,
  publisher = {Elsevier {BV}},
  volume = {332},
  pages = {465--475},
  author = {Alex Fink and Karola M{\'{e}}sz{\'{a}}ros and Avery St. Dizier},
  title = {Schubert polynomials as integer point transforms of generalized permutahedra},
  journal = {Advances in Mathematics}
}
  9. [MMS22]Jacob P. Matherne, Alejandro H. Morales and Jesse Selover. The Newton polytope and Lorentzian property of chromatic symmetric functions. arXiv:2201.07333, 2022.
    .bib
    @article{MatherneMoralesSelover2022x,
Author = {Jacob P. Matherne and Alejandro H. Morales and Jesse Selover},
Title = {The {N}ewton polytope and {L}orentzian property of chromatic symmetric functions},
Year = {2022},
Eprint = {2201.07333},
  url = {https://arxiv.org/abs/2201.07333},
journal = {arXiv e-prints}
}
  10. [MTY19]Cara Monical, Neriman Tokcan and Alexander Yong. Newton polytopes in algebraic combinatorics. Selecta Mathematica, 25(5), October 2019.
    .bib
    @article{MonicalTokcanYong2019,
  title = {Newton polytopes in algebraic combinatorics},
  volume = {25},
  ISSN = {1420-9020},
  url = {http://dx.doi.org/10.1007/s00029-019-0513-8},
  DOI = {10.1007/s00029-019-0513-8},
  number = {5},
  journal = {Selecta Mathematica},
  publisher = {Springer Science and Business Media LLC},
  author = {Monical,  Cara and Tokcan,  Neriman and Yong,  Alexander},
  year = {2019},
  month = oct 
}
  11. [NNTN+23]Duc-Khanh Nguyen, Giao Nguyen Thi Ngoc, Hiep Dang Tuan and Thuy Do Le Hai. Newton polytope of good symmetric polynomials. Comptes Rendus. Mathématique, 361(G4):767–775, May 2023.
    .bib
    @article{NguyenNgocTuanHai2023,
  title = {Newton polytope of good symmetric polynomials},
  volume = {361},
  ISSN = {1778-3569},
  url = {http://dx.doi.org/10.5802/crmath.430},
  DOI = {10.5802/crmath.430},
  number = {G4},
  journal = {Comptes Rendus. Mathématique},
  publisher = {Cellule MathDoc/CEDRAM},
  author = {Nguyen,  Duc-Khanh and Nguyen Thi Ngoc,  Giao and Dang Tuan,  Hiep and Do Le Hai,  Thuy},
  year = {2023},
  month = may,
  pages = {767–775}
}
  12. [PZ23]Greta Panova and Chenchen Zhao. The Newton polytope of the Kronecker product. arXiv:2311.10276, 2023.
    .bib
    @article{PanovaZhao2023x,
  author = {Greta Panova and Chenchen Zhao},
  title = {The {N}ewton polytope of the {K}ronecker product},
  year = {2023},
  eprint = {2311.10276},
  url = {https://arxiv.org/abs/2311.10276},
  journal = {arXiv e-prints}
}
  13. [San23]Mario Sanchez. Mirković-Vilonen Polytopes from Combinatorics. arXiv:2311.16979, 2023.
    .bib
    @article{Sanchez2023x,
  author = {Mario Sanchez},
  title = {Mirković-{V}ilonen {P}olytopes from {C}ombinatorics},
  year = {2023},
  eprint = {2311.16979},
  url = {https://arxiv.org/abs/2311.16979},
  journal = {arXiv e-prints}
}
  14. [WZZ24]Bo Wang, Candice X. T. Zhang and Zhong-Xue Zhang. Newton polytopes of dual $k$-Schur polynomials. arXiv:2401.14632, 2024.
    .bib
    @article{WangZhangZhang2024x,
Author = {Bo Wang and Candice X. T. Zhang and Zhong-Xue Zhang},
Title = {Newton polytopes of dual $k$-{S}chur polynomials},
Year = {2024},
Eprint = {2401.14632},
url = {https://arxiv.org/abs/2401.14632},
journal = {arXiv e-prints}
}

I use cookies to detect website issues and track search terms.