# ALGEBRAIC COMBINATORICS

Commutative algebra of generalised Frobenius numbers
Algebraic Combinatorics, Volume 2 (2019) no. 1, p. 149-171
We study commutative algebra arising from generalised Frobenius numbers. The $k$-th (generalised) Frobenius number of relatively prime natural numbers $\left({a}_{1},\cdots ,{a}_{n}\right)$ is the largest natural number that cannot be written as a non-negative integral combination of $\left({a}_{1},\cdots ,{a}_{n}\right)$ in $k$ distinct ways. Suppose that $L$ is the lattice of integer points of ${\left({a}_{1},\cdots ,{a}_{n}\right)}^{\perp }$. Taking our cue from the concept of lattice modules due to Bayer and Sturmfels, we define generalised lattice modules ${M}_{L}^{\left(k\right)}$ whose Castelnuovo–Mumford regularity captures the $k$-th Frobenius number of $\left({a}_{1},\cdots ,{a}_{n}\right)$. We study the sequence ${\left\{{M}_{L}^{\left(k\right)}\right\}}_{k=1}^{\infty }$ of generalised lattice modules providing an explicit characterisation of their minimal generators. We show that there are only finitely many isomorphism classes of generalised lattice modules. As a consequence of our commutative algebraic approach, we show that the sequence of generalised Frobenius numbers forms a finite difference progression i.e. a sequence whose set of successive differences is finite. We also construct an algorithm to compute the $k$-th Frobenius number.
Accepted : 2018-07-04
Published online : 2019-02-04
DOI : https://doi.org/10.5802/alco.31
Classification:  11D07,  13D02,  52C07,  06A07
Keywords: Frobenius number, syzygy, lattice, poset, Castelnuovo–Mumford regularity
@article{ALCO_2019__2_1_149_0,
author = {Manjunath, Madhusudan and Smith, Ben},
title = {Commutative algebra of generalised Frobenius numbers},
journal = {Algebraic Combinatorics},
publisher = {MathOA foundation},
volume = {2},
number = {1},
year = {2019},
pages = {149-171},
doi = {10.5802/alco.31},
language = {en},
url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_1_149_0}
}

Manjunath, Madhusudan; Smith, Ben. Commutative algebra of generalised Frobenius numbers. Algebraic Combinatorics, Volume 2 (2019) no. 1, pp. 149-171. doi : 10.5802/alco.31. https://alco.centre-mersenne.org/item/ALCO_2019__2_1_149_0/

[1] Alfonsín, J. L. Ramírez The Diophantine Frobenius problem, Oxford University Press, Oxford Lecture Series in Mathematics and its Applications, Volume 30 (2005), xvi+243 pages | Article | MR 2260521 | Zbl 1134.11012

[2] Aliev, Iskander; De Loera, Jesús A.; Louveaux, Quentin Parametric polyhedra with at least $k$ lattice points: their semigroup structure and the $k$-Frobenius problem, Recent trends in combinatorics, Springer (The IMA Volumes in Mathematics and its Applications) Volume 159 (2016), pp. 753-778 | Article | MR 3526430 | Zbl 1358.52016

[3] Aliev, Iskander; Fukshansky, Lenny; Henk, Martin Generalized Frobenius numbers: bounds and average behavior, Acta Arith., Volume 155 (2012) no. 1, pp. 53-62 | Article | MR 2982427 | Zbl 1297.11014

[4] Amini, Omid; Manjunath, Madhusudan Riemann-Roch for sub-lattices of the root lattice ${A}_{n}$, Electr. J. Comb., Volume 17 (2010) no. 1, R124, 50 pages | Zbl 1277.05105

[5] Bayer, Dave; Stillman, Mike Computation of Hilbert functions, J. Symb. Comput., Volume 14 (1992) no. 1, pp. 31-50 | Article | MR 1177988 | Zbl 0763.13007

[6] Bayer, Dave; Sturmfels, Bernd Cellular resolutions of monomial modules, J. Reine Angew. Math., Volume 502 (1998), pp. 123-140 | Article | MR 1647559 | Zbl 0909.13011

[7] Beck, Matthias; Diaz, Ricardo; Robins, Sinai The Frobenius problem, rational polytopes, and Fourier-Dedekind sums, J. Number Theory, Volume 96 (2002) no. 1, pp. 1-21 | MR 1931190 | Zbl 1038.11026

[8] Beck, Matthias; Robins, Sinai A formula related to the Frobenius problem in two dimensions, Number theory (New York, 2003), Springer (2004), pp. 17-23 | MR 2044510 | Zbl 1053.11023

[9] Beck, Matthias; Robins, Sinai Computing the continuous discretely. Integer-point enumeration in polyhedra, Springer, Undergraduate Texts in Mathematics (2015), xx+285 pages | Article | MR 3410115 | Zbl 1339.52002

[10] Dilworth, Robert P. A decomposition theorem for partially ordered sets, Ann. Math., Volume 51 (1950), pp. 161-166 | Article | MR 0032578 | Zbl 0038.02003

[11] Eisenbud, David The geometry of syzygies. A second course in commutative algebra and algebraic geometry, Springer, Graduate Texts in Mathematics, Volume 229 (2005), xvi+243 pages | MR 2103875 | Zbl 1066.14001

[12] Grayson, Daniel R.; Stillman, Michael E. Macaulay2, a software system for research in algebraic geometry, available at https://faculty.math.illinois.edu/Macaulay2/

[13] Kannan, Ravi Lattice translates of a polytope and the Frobenius problem, Combinatorica, Volume 12 (1992) no. 2, pp. 161-177 | Article | MR 1179254 | Zbl 0753.11013

[14] Lorenzini, Dino Two-variable zeta-functions on graphs and Riemann-Roch theorems, Int. Math. Res. Not. (2012) no. 22, pp. 5100-5131 | Article | MR 2997050 | Zbl 1286.14036

[15] Miller, Ezra; Sturmfels, Bernd Combinatorial commutative algebra, Springer, Graduate Texts in Mathematics, Volume 227 (2005), xiv+417 pages | MR 2110098 | Zbl 1090.13001

[16] Peeva, Irena; Sturmfels, Bernd Generic lattice ideals, J. Am. Math. Soc., Volume 11 (1998) no. 2, pp. 363-373 | Article | MR 1475887 | Zbl 0905.13005

[17] Sabzrou, Hossein; Rahmati, Farhad The Frobenius number and $a$-invariant, Rocky Mt. J. Math., Volume 36 (2006) no. 6, pp. 2021-2026 | Article | MR 2305643 | Zbl 1133.13023

[18] Scarf, Herbert E.; Shallcross, David F. The Frobenius problem and maximal lattice free bodies, Math. Oper. Res., Volume 18 (1993) no. 3, pp. 511-515 | Article | MR 1250555 | Zbl 0782.11009

[19] Sturmfels, Bernd Gröbner bases and convex polytopes, American Mathematical Society, University Lecture Series, Volume 8 (1996), xii+162 pages | MR 1363949 | Zbl 0856.13020