多面体に含まれる lattice point の数に関する問題

凸多面体は, Euclid空間の部分空間として定義されるので, その中に含まれる lattice point の数を調べるという問題が考えられる。普通は頂点が lattice point になっている lattice polytope を考える。

  • lattice polytope

この問題に関する本として Beck と Robins の [BR15] が出た。解説としては, Breuer の [Bre15] もある。 Robins は [Rob] という解説も書いている。 Fourier transform を中心的な道具として使って書いてある。

多角形の場合, Pick の定理 [Pic99] という公式がある。 Higashitani と Masuda [HM] によると, 他に 格子多角形に関する重要な結果として twelve-point theorem と呼ばれるものがある。

  • Pick’s theorem
  • twelve-point theorem

凸多面体の操作の中で Minkowski sum は最も基本的なものの一つであるが, lattice polytope の Minkowski sum を取った時に lattice point の数がどう変わるかというのは, 未だによく分かっていないらしい。Hasse らの [Haa+08] によると, ある条件をみたす場合には Oda による予想があるらしい。 その\(3\)次元版を証明したのが, Fakhruddin の [Fak] である。Hasse らの論文はその拡張を証明している。 やはり\(3\)次元以上は難しいようであるが。

Brion の公式 [Bri88] は toric varietyequivariant \(K\)-theory を使っている点で興味深い。Beck と Haase と Sottile の [BHS09] にはその別証がある。 Hüttemann の [Hütb] にも別証がある。Hüttemann は, [Hüta] でその一般化も考えている。

  • Brion’s formula

Ehrhart の論文 [Ehr62] は, 多面体を拡大したときに lattice point の数がどのように増えるかを考察したものである。

  • Ehrhart polynomial

Ehrhart polynomial の係数が全て正になる多面体がどのようなものか, という問題について何が知られているかは, Castillo と Liu の [CL18] の §1.1 にまとめられている。

Stapledon の [Sta08] では, Erhart polynomial と, stacky fan に associate した Deligne-Mumford stackorbifold cohomology との関係が述べられていて興味深い。

Ehrhart polynomial に関する Khovanski と Pukholikov の結果 [PK92] を, 偏微分作用素の symbol に対し一般化したのが, Guillemin と Sternberg と Weitsman の [GSW] である。

De Concini と Procesi と Vergne [DPV10] は, Ehrhart polynomial の一般化として, ベクトル空間の lattice の有限部分集合を与えたとき, 与えられたベクトルを, それらの正の整数を係数とする一次結合で表わす個数を数える関数を考えている。 彼らはそれを partition function と呼んでいる。 多項式にはならないが, ある領域上では quasi-polynomial になるらしい。

  • partition function
  • quasi-polynomial

Dahmen と Micchelli の仕事 [DM88; DM89], つまり box spline がもとになっているようである。

References

[BHS09]

Matthias Beck, Christian Haase, and Frank Sottile. “Formulas of Brion, Lawrence, and Varchenko on rational generating functions for cones”. In: Math. Intelligencer 31.1 (2009), pp. 9–17. arXiv: math/ 0506466. url: http://dx.doi.org/10.1007/s00283-008-9013-y.

[BR15]

Matthias Beck and Sinai Robins. Computing the continuous discretely. Second. Undergraduate Texts in Mathematics. Integer-point enumeration in polyhedra, With illustrations by David Austin. Springer, New York, 2015, pp. xx+285. isbn: 978-1-4939-2968-9; 978-1-4939-2969-6. url: https://doi.org/10.1007/978-1-4939-2969-6.

[Bre15]

Felix Breuer. “An invitation to Ehrhart theory: polyhedral geometry and its applications in enumerative combinatorics”. In: Computer algebra and polynomials. Vol. 8942. Lecture Notes in Comput. Sci. Springer, Cham, 2015, pp. 1–29. arXiv: 1405 . 7647. url: https://doi.org/10.1007/978-3-319-15081-9_1.

[Bri88]

Michel Brion. “Points entiers dans les polyèdres convexes”. In: Ann. Sci. École Norm. Sup. (4) 21.4 (1988), pp. 653–663. url: http://www.numdam.org/item?id=ASENS_1988_4_21_4_653_0.

[CL18]

Federico Castillo and Fu Liu. “Berline-Vergne valuation and generalized permutohedra”. In: Discrete Comput. Geom. 60.4 (2018), pp. 885–908. arXiv: 1509. 07884. url: https://doi.org/10.1007/s00454-017-9950-3.

[DM88]

Wolfgang Dahmen and Charles A. Micchelli. “The number of solutions to linear Diophantine equations and multivariate splines”. In: Trans. Amer. Math. Soc. 308.2 (1988), pp. 509–532. url: http://dx.doi.org/10.2307/2001089.

[DM89]

Wolfgang Dahmen and Charles A. Micchelli. “On multivariate \(E\)-splines”. In: Adv. Math. 76.1 (1989), pp. 33–93. url: http://dx.doi.org/10.1016/0001-8708(89)90043-1.

[DPV10]

C. De Concini, C. Procesi, and M. Vergne. “Vector partition functions and generalized Dahmen and Micchelli spaces”. In: Transform. Groups 15.4 (2010), pp. 751–773. arXiv: 0805.2907. url: http://dx.doi.org/10.1007/s00031-010-9102-9.

[Ehr62]

Eugène Ehrhart. “Sur les polyèdres rationnels homothétiques à \(n\) dimensions”. In: C. R. Acad. Sci. Paris 254 (1962), pp. 616–618.

[Fak]

Najmuddin Fakhruddin. Multiplication maps of linear systems on smooth projective toric surfaces. arXiv: math/0208178.

[GSW]

Victor W. Guillemin, Shlomo Sternberg, and Jonathan Weitsman. The Ehrhart Function for Symbols. arXiv: math/0601714.

[Haa+08]

Christian Haase, Benjamin Nill, Andreas Paffenholz, and Francisco Santos. “Lattice points in Minkowski sums”. In: Electron. J. Combin. 15.1 (2008), Note 11, 5. arXiv: 0711.4393. url: http://www.combinatorics.org/Volume_15/Abstracts/v15i1n11.html.

[HM]

Akihiro Higashitani and Mikiya Masuda. Lattice multi-polygons. arXiv: 1204.0088.

[Hüta]

Thomas Hüttemann. A cohomological interpretation of Brion’s formula. arXiv: math/0607464.

[Hütb]

Thomas Hüttemann. On a theorem of Brion. arXiv: math/0607297.

[Pic99]

Georg Pick. “Geometrisches zur Zahlenlehre”. In: Sitzenber. Lotos (Prague) 19 (1899), pp. 311–319.

[PK92]

A. V. Pukhlikov and A. G. Khovanskiı̆. “The Riemann-Roch theorem for integrals and sums of quasipolynomials on virtual polytopes”. In: Algebra i Analiz 4.4 (1992), pp. 188–216.

[Rob]

Sinai Robins. A friendly introduction to Fourier analysis on polytopes. arXiv: 2104.06407.

[Sta08]

A. Stapledon. “Weighted Ehrhart theory and orbifold cohomology”. In: Adv. Math. 219.1 (2008), pp. 63–88. arXiv: 0711.4382. url: https://doi.org/10.1016/j.aim.2008.04.010.