Equivariant lattice bases

Le, Dinh; Römer, Tim

doi:10.1090/tran/9193

Equivariant lattice bases
HTML articles powered by AMS MathViewer

by Dinh Van Le and Tim Römer;

Trans. Amer. Math. Soc. 377 (2024), 4865-4893

DOI: https://doi.org/10.1090/tran/9193

Published electronically: May 21, 2024

HTML | PDF | Request permission

Abstract:

We study lattices in free abelian groups of infinite rank that are invariant under the action of the infinite symmetric group, with emphasis on finiteness of their equivariant bases. Our framework provides a new method for proving finiteness results in algebraic statistics. As an illustration, we show that every invariant lattice in $\mathbb {Z}^{(\mathbb {N}\times [c])}$, where $c\in \mathbb {N}$, has a finite equivariant Graver basis. This result generalizes and strengthens several finiteness results about Markov bases in the literature.

References

4ti2 team, 4ti2 – A software package for algebraic, geometric and combinatorial problems on linear spaces. Available at https://4ti2.github.io.
Satoshi Aoki, Hisayuki Hara, and Akimichi Takemura, Markov bases in algebraic statistics, Springer Series in Statistics, Springer, New York, 2012. MR 2961912, DOI 10.1007/978-1-4614-3719-2
Satoshi Aoki and Akimichi Takemura, Minimal basis for a connected Markov chain over $3\times 3\times K$ contingency tables with fixed two-dimensional marginals, Aust. N. Z. J. Stat. 45 (2003), no. 2, 229–249. MR 1983834, DOI 10.1111/1467-842X.00278
Matthias Aschenbrenner and Christopher J. Hillar, Finite generation of symmetric ideals, Trans. Amer. Math. Soc. 359 (2007), no. 11, 5171–5192. MR 2327026, DOI 10.1090/S0002-9947-07-04116-5
Winfried Bruns and Joseph Gubeladze, Polytopes, rings, and $K$-theory, Springer Monographs in Mathematics, Springer, Dordrecht, 2009. MR 2508056, DOI 10.1007/b105283
Thomas Church and Benson Farb, Representation theory and homological stability, Adv. Math. 245 (2013), 250–314. MR 3084430, DOI 10.1016/j.aim.2013.06.016
Jesús A. De Loera, Raymond Hemmecke, and Matthias Köppe, Algebraic and geometric ideas in the theory of discrete optimization, MOS-SIAM Series on Optimization, vol. 14, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013. MR 3024570
Jesús A. De Loera and Shmuel Onn, Markov bases of three-way tables are arbitrarily complicated, J. Symbolic Comput. 41 (2006), no. 2, 173–181. MR 2197153, DOI 10.1016/j.jsc.2005.04.010
Persi Diaconis and Bernd Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998), no. 1, 363–397. MR 1608156, DOI 10.1214/aos/1030563990
Reinhard Diestel, Graph theory, 5th ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. MR 3644391, DOI 10.1007/978-3-662-53622-3
Adrian Dobra, Markov bases for decomposable graphical models, Bernoulli 9 (2003), no. 6, 1093–1108. MR 2046819, DOI 10.3150/bj/1072215202
Adrian Dobra and Seth Sullivant, A divide-and-conquer algorithm for generating Markov bases of multi-way tables, Comput. Statist. 19 (2004), no. 3, 347–366. MR 2096204, DOI 10.1007/BF03372101
Jan Draisma, Finiteness for the $k$-factor model and chirality varieties, Adv. Math. 223 (2010), no. 1, 243–256. MR 2563217, DOI 10.1016/j.aim.2009.08.008
Jan Draisma, Noetherianity up to symmetry, Combinatorial algebraic geometry, Lecture Notes in Math., vol. 2108, Springer, Cham, 2014, pp. 33–61. MR 3329086, DOI 10.1007/978-3-319-04870-3_{2}
Jan Draisma, Rob Eggermont, Robert Krone, and Anton Leykin, Noetherianity for infinite-dimensional toric varieties, Algebra Number Theory 9 (2015), no. 8, 1857–1880. MR 3418745, DOI 10.2140/ant.2015.9.1857
Jan Draisma and Jochen Kuttler, Bounded-rank tensors are defined in bounded degree, Duke Math. J. 163 (2014), no. 1, 35–63. MR 3161311, DOI 10.1215/00127094-2405170
Mathias Drton, Bernd Sturmfels, and Seth Sullivant, Lectures on algebraic statistics, Oberwolfach Seminars, vol. 39, Birkhäuser Verlag, Basel, 2009. MR 2723140, DOI 10.1007/978-3-7643-8905-5
Arka Ghosh, Piotr Hofman, and Sławomir Lasota, Orbit-finite linear programming, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE Comput. Soc. Press, Los Alamitos, CA, [2023] ©2023, pp. 14. MR 4617682
Jack E. Graver, On the foundations of linear and integer linear programming. I, Math. Programming 9 (1975), no. 2, 207–226. MR 386673, DOI 10.1007/BF01681344
D. Grayson and M. Stillman, Macaulay2, a software system for research in algebraic geometry. Available at https://macaulay2.com.
Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326–336. MR 49867, DOI 10.1112/plms/s3-2.1.326
Christopher J. Hillar and Abraham Martín del Campo, Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals, J. Symbolic Comput. 50 (2013), 314–334. MR 2996883, DOI 10.1016/j.jsc.2012.06.006
Christopher J. Hillar and Seth Sullivant, Finite Gröbner bases in infinite dimensional polynomial rings and applications, Adv. Math. 229 (2012), no. 1, 1–25. MR 2854168, DOI 10.1016/j.aim.2011.08.009
Serkan Hoşten and Seth Sullivant, A finiteness theorem for Markov bases of hierarchical models, J. Combin. Theory Ser. A 114 (2007), no. 2, 311–321. MR 2293094, DOI 10.1016/j.jcta.2006.06.001
Kei-ichiro Iima and Yuji Yoshino, Gröbner bases for the polynomial ring with infinite variables and their applications, Comm. Algebra 37 (2009), no. 10, 3424–3437. MR 2561854, DOI 10.1080/00927870802502878
Thomas Kahle, Robert Krone, and Anton Leykin, Equivariant lattice generators and Markov bases, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 264–271. MR 3239935, DOI 10.1145/2608628.2608646
Thomas Kahle, Dinh Van Le, and Tim Römer, Invariant chains in algebra and discrete geometry, SIAM J. Discrete Math. 36 (2022), no. 2, 975–999. MR 4407600, DOI 10.1137/20M1385652
Joseph B. Kruskal, The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A 13 (1972), 297–305. MR 306057, DOI 10.1016/0097-3165(72)90063-5
Dinh V. Le and Tim Römer, Theorems of Carathéodory, Minkowski-Weyl, and Gordan up to symmetry, SIAM J. Appl. Algebra Geom. 7 (2023), no. 1, 291–310. MR 4568011, DOI 10.1137/22M148865X
E. Levin and V. Chandrasekaran, Free Descriptions of Convex Sets. Preprint, 2023, available at arXiv:2307.04230.
E. Levin and M. Díaz, Any-dimensional equivariant neural networks. Preprint, 2023, available at arXiv:2306.06327.
Uwe Nagel and Tim Römer, Equivariant Hilbert series in non-noetherian polynomial rings, J. Algebra 486 (2017), 204–245. MR 3666212, DOI 10.1016/j.jalgebra.2017.05.011
Francisco Santos and Bernd Sturmfels, Higher Lawrence configurations, J. Combin. Theory Ser. A 103 (2003), no. 1, 151–164. MR 1986836, DOI 10.1016/S0097-3165(03)00092-X
Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR 1363949, DOI 10.1090/ulect/008
Bernd Sturmfels, Robert Weismantel, and Günter M. Ziegler, Gröbner bases of lattices, corner polyhedra, and integer programming, Beiträge Algebra Geom. 36 (1995), no. 2, 281–298. MR 1358427
Seth Sullivant, Algebraic statistics, Graduate Studies in Mathematics, vol. 194, American Mathematical Society, Providence, RI, 2018. MR 3838364, DOI 10.1090/gsm/194