Interesting and challenging examples for Normaliz

Some interesting and challenging examples document the power of Normaliz. Please send examples that you would like to add to the collection to one of the authors!

Each example is provided as a separate zip file containing input and output. The mathematical background and more information is provided by the references specified. All examples have been computed with a pre-release version of Normaliz 3.1.1.

  1. nonICP: An example of a normal lattice polytope that has no unimodular cover and even violates the integral Carathéodory property [BG, Section 2.D], [BG2], [BGHMW].
  2. ICPnonUHC: An example of a lattice polytope satisfying ICP, but without unimodular cover [B].
  3. VeryampleNonNormal: An example of a non-normal very ample lattice polytope [BG1]. (See [BG, p. 87] for further examples.)
  4. dim3tight: A 3-dimensional tight cone [BG, Section 2.D].
  5. cube210: Ehrhart polynomial. The period of the Ehrhart quasipolynomial of a rational polytope divides the least common multiple of the denominators of the vertices. Usually one has equality, but there are exceptions. In particular there exist non-lattice polytopes whose Ehrhart quasipolynomial is a polynomial. We give a 3-dimensional example with the face lattice of the cube.
  6. NonNormal3polytope: A nonnormal rectangular simplex of dimension 3 [BG0].
  7. Magic: (Magic) squares of nonnegative integers for which all row and column sums and the two diagonal sums are equal.
  8. contingency: The missing cases in the Ohsugi-Hibi classification of normal monoids derived from contingency tables (4x4x3, 5x4x3, 5x5x3) and the first nonnormal case (6x4x3); see [OH], [BHIKS]. (Run with -N for Hilbert basis computation.)
  9. semigraphoid5: The semi-graphoid for N = 5 [HMSSW], [BHIKS]. (Run with -N for Hilbert basis computation.)
  10. cut_monoids: Verification of a conjecture of Sturmfels and Sullivant on normality of cut polytopes for some specific graphs [SS], [BHIKS], [O], [S].
  11. SturmfelsWelker: Two models of statistical ranking discussed in [SW], the inversion model for n = 6 (lo6) and the ascending model for n = 5 (bo5).
  12. VotingHilbertSeries: Some examples of Hilbert (or Ehrhart) series computations for elections with four candidates: the Condorcet paradox, the Condorcet efficiency of plurality voting, plurality voting vs. cutoff for 4 candidates. See [BS] and [BIS2] where some more models of voting theory are discussed. The computations use symmeztrization based on [BS]. The computations require Normaliz 3.6.0 or higher.
  13. VotingVolumes: Examples of volume computations for elections with four candidates, for which Hilbert series are out of reach or take very long: the strict Borda paradox [BIS] and “4 rules” [BI]. Also the three models from VotingHilbertSeries have been included with restriction to volume computation. The computations require Normaliz 3.6.0 or higher.
  14. Cyclotomic: Cyclotomic monoids; see [BeHo]. The computations just confirm a theorem of Beck and Hosten. The first open case of 105th roots of unity is not yet reachable.
  15. VanishingSums: The aim is to find all linear combinations of the n-th roots of unity with nonnegative integer coefficients that sum to 0. See for the [LL] mathematical background. The solution of the problem requires a Gilbert basis calculation.  This application of Normaliz was used for a project in mathematical music; see http://www.dynamictonality.com/xronomorph.htm and [Mi]. We include input and output files for n=66,70,78, The first impossible case seems to be n=105. But Normaliz can compute the extreme rays in this case. Because of their large number, we list only the lexicographic largest component of each orbit under the group of rotations.PolytopeVolumes
  16. CyclicPolytopes: The face numbers of cyclic polytopes attain the maximum set by the upper bound theorem (for example, see [BH]. We include two examples that show Normaliz’ power in computing convex hulls for polytopes defined by vertices with very large coordinates. (Suggested by D. Avis and Ch. Jordan.) The larger of the two examples requires a large amount of RAM (~ 60 GB).
  17. ClassicalPolyhedra: Classical polyhedra like the icosahedron and the dodecahedron require coordinates in subfields of the real numbers that are algebraic over the rational numbers. QNormaliz computes such polyhedra, and from version 3.7.0 on Normaliz itself will do it.
  18. PolytopeVolumes: This zip file contains input files for the computations on the paper Polytope volume by descent in the face lattice and applications in social choice by W. Bruns and B. Ichim. The input files for vinci are in the subdirectory vinci, those for Normaliz are distributed to several subdirectories. The file names are explained in the paper.
  19. InputAndResults: This file contains the input and result files of the volume computations in [BI2] by the Lawrence algorithm.

References

  • [BeHo] M. Beck and S. Hosten. Cyclotomic polytopes and growth series of cyclotomic lattices. Math. Res. Lett. 13 (2006), no. 4, 607–622.
  • [BH] W. Bruns and J. Herzog. Cohen-Macaulay rings. Rev. ed. Cambridge University Press 1998.
  • [B] W. Bruns. On the integral Carathéodory property. Experiment. Math. 16 (2007), no. 3, 359–365.
  • [BG] W. Bruns and J. Gubeladze. Polytopes, rings, and K-theory. Springer Monographs in Mathematics, Springer, 2009.
  • [BG0] W. Bruns and J. Gubeladze. Rectangular simplicial semigroups. In: D. Eisenbud (ed.), Commutative algebra, algebraic geometry, and computational methods, 201–213, Springer 1999.
  • [BG1] W. Bruns and J. Gubeladze, Polytopal linear groups. J. Algebra 218 (1999), no. 2, 715–737.
  • [BG2] W. Bruns and J. Gubeladze. Normality and covering properties of affine semigroups. J. Reine Angew. Math. 510 (1999), 161–178.
  • [BGHMW] W. Bruns, J. Gubeladze, M. Henk, A. Martin, and R. Weismantel. A counterexample to an integer analogue of Carathéodory’s theorem. J. Reine Angew. Math. 510 (1999), 179–185.
  • [BHIKS] W. Bruns, R. Hemmecke, B. Ichim, M. Köppe, and C. Söger. Challenging computations of Hilbert bases of cones associated with algebraic statistics. Exp. Math. 20 (2011), no. 1, 25–33.
  • [BI] W. Bruns and B. Ichim. Polytope volume by descent in the face lattice and applications in social choice. Math. Program. Comput. 13 (2021), no. 2, 415–442.
  • [BI2] W. Bruns and B. Ichim. Computations of volumes in five candidates elections. arXiv:2109.00473.
  • [BIS] W.Bruns, B. Ichim and C. Söger. The power of pyramid decompositions in Normaliz. J. Symbolic Comput. 74 (2016), 513–536.
  • [BIS2] W. Bruns, C. Söger and B. Ichim. Computations of volumes and Ehrhart series in four candidates elections. Ann. Oper. Res. 280 (2019), no. 1-2, 241–265.
  • [BS] W.Bruns and C. Söger. The computation of generalized Ehrhart series in Normaliz. J. Symbolic Comput. 68 (2015), part 2, 75–86.
  • [HMSSW] R. Hemmecke, J. Morton, A. Shiu, B. Sturmfels, and O. Wienand. Three counter-examples on semi-graphoids. Combin. Probab. Comput. 17 (2008), no. 2, 239–257.
  • [LL] T. Y. Lam and K. H. Leung. On vanishing sums of roots of unity. J. Algebra 224 (2000), 91–109.
  • [Mil] A. J. Milne et al. XronoMorph: Algorithmic generation of perfectly balanced and well-formed rhythms. Use of Normaliz communicated by D. Bulger. Available at http://www.nime.org/proceedings/2016/nime2016_paper0077.pdf.
  • [O] H. Ohsugi. Normality of cut polytopes of graphs in a minor closed property. Discrete Math. 310 (2010), no. 6-7, 1160–1166.
  • [OH] H. Ohsugi and T. Hibi. Toric ideals arising from contingency tables. In: R.V. Gurjar, S. A. Katre, R.A. Rao and J.K. Verma (ed.), Commutative algebra and combinatorics, Ramanujan Mathematical Society Lecture Notes Series 4, 91–115, Ramanujan Mathematical Society, 2007.
  • [S] C. Söger. Parallel Algorithms for Rational Cones and Affine Monoids. Dissertation thesis (2014), urn:nbn:de:gbv:700-2014042212422.
  • [SS] B. Sturmfels and S. Sullivant. Toric geometry of cuts and splits. Michigan Math. J. 57 (2008), 689–709.
  • [SW] B. Sturmfels and V. Welker. Commutative Algebra of Statistical Ranking. J. Algebra 361 (2012), 264–286.