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. CombinatorialVoting: Three models of social choice: the Condorcet paradox, the Condorcet efficiency of plurality voting, and plurality voting vs. cutoff for 4 candidates. Condorcet efficiency of plurality voting, and plurality voting vs. cutoff have very high computation times; see [BIS]. It is much more efficient to compute these examples with NmzIntegrate; see [BS]. The input and output files for NmzIntegrate are included in the zip file.
  13. 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.
  14. 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.
  15. 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).

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.
  • [BIS] W.Bruns, B. Ichim and C. Söger. The power of pyramid decompositions in Normaliz. J. Symbolic Comput. 74 (2016), 513–536.
  • [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.