Gröbner Lattice-Point Enumerators and Signed Tiling by k-in-line Polyominoes
Download PDF
Authors: M. MUZIKA DIZDAREVIć, M. TIMOTIJEVIć AND R. T. ŽIVALJEVIć
DOI: 10.46793/KgJMat2503.443D
Abstract:
Conway and Lagarias observed that a triangular region T2(n) in a hexagonal lattice admits a signed tiling by 3-in-line polyominoes (tribones) if and only if n ∈{32d − 1, 32d}d∈ℕ. We apply the theory of Gröbner bases over integers to show that T3(n), a three dimensional lattice tetrahedron of edge-length n, admits a signed tiling by tribones if and only if n ∈{33d − 2, 33d − 1, 33d}d∈ℕ. More generally we study Gröbner lattice-point enumerators of lattice polytopes and show that they are (modular) quasipolynomials in the case of k-in-line polyominoes. As an example of the “unusual cancelation phenomenon”, arising only in signed tilings, we exhibit a configuration of 15 tribones in the 3-space such that exactly one lattice point is covered by an odd number of tiles.
Keywords:
Signed polyomino tiling, Gröbner bases, Lattice-point enumerators.
References:
[1] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics 3, American Mathematical Society, Providence, 1994.
[2] A. Barvinok, Integer Points in Polyhedra, European Mathematical Society, 2008.
[3] M. Beck and S. Robins, Computing the Continuous Discretely, Springer, 2007.
[4] T. Becker and V. Weispfenning, Gröbner Bases: A Computational Approach to Commutative Algebra, Springer-Verlag, New York, 1993.
[5] O. Bodini and B. Nouvel, Z-Tilings of polyominoes and standard basis, in: Combinatorial Image Analysis, Springer, 2004, 137–150.
[6] J. H. Conway and J.C. Lagarias, Tiling with polyominoes and combinatorial group theory, J. Combin. Theory Ser. A 53 (1990), 183–208. https://doi.org/10.1016/0097-3165(90)90057-4
[7] D. Cox, J. Little and D. O’Shea, Ideals, Varieties and Algorithms, Third Edition, Springer-Verlag, New York, 2007.
[8] D. Cox, J. Little and D. O’Shea, Using Algebraic Geometry, Second Edition, Springer-Verlag, New York, 2005.
[9] M. Muzika Dizdarević and R. T. Živaljević, Symmetric polyomino tilings, tribones, ideals, and Gröbner bases, Publ. Inst. Math. (Beograd) (N.S.) 98(112) (2015), 1–23. https://doi.org/10.2298/PIM1512001M
[10] M. Muzika Dizdarević, M. Timotijević, R. T. Živaljević, Signed polyomino tilings by n-in-line polyominoes and Gröbner bases, Publ. Inst. Math. (Beograd) (N.S.) 99(113) (2016), 31–42. https://doi.org/10.2298/PIM1613031M
[11] D. Lichtblau, Revisiting strong Gröbner bases over Euclidean domains, Illinois J. Math. 56(1) (2012), 177–194. http://library.wolfram.com/infocenter/MathSource/7522
[12] M. Reid, Tile homotopy groups, Enseign. Math. 49(1–2) (2003), 123–155.
[13] R. Stanley, Enumerative Combinatorics, Volume 1, Second Edition, Cambridge University Press, 2011.
[14] B. Sturmfels, What is ... a Gröbner Basis, Notices A.M.S., 2005.
[15] W. Thurston, Conway’s tiling groups, Amer. Math. Monthly 97 (1990), 757–773. https://doi.org/10.1080/00029890.1990.11995660
Login:
