Commutative algebra of generalised Frobenius numbers

Manjunath, Madhusudan; Smith, Ben

doi:10.5802/alco.31

Manjunath, Madhusudan ¹; Smith, Ben ²

¹ Indian Institute of Technology Bombay, Powai, Mumbai 400076, India
² School of Mathematical Sciences, Queen Mary University of London, London, E1 4NS, United Kingdom

Algebraic Combinatorics, Volume 2 (2019) no. 1, pp. 149-171.

Abstract

We study commutative algebra arising from generalised Frobenius numbers. The $k$ -th (generalised) Frobenius number of relatively prime natural numbers $(a_{1}, \dots, a_{n})$ is the largest natural number that cannot be written as a non-negative integral combination of $(a_{1}, \dots, a_{n})$ in $k$ distinct ways. Suppose that $L$ is the lattice of integer points of ${(a_{1}, \dots, a_{n})}^{⊥}$ . Taking our cue from the concept of lattice modules due to Bayer and Sturmfels, we define generalised lattice modules $M_{L}^{(k)}$ whose Castelnuovo–Mumford regularity captures the $k$ -th Frobenius number of $(a_{1}, \dots, a_{n})$ . We study the sequence ${M_{L}^{(k)}}_{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.

Received: 2018-07-03
Accepted: 2018-07-04
Published online: 2019-02-04

MR Zbl

DOI: 10.5802/alco.31

Classification: 11D07, 13D02, 52C07, 06A07
Keywords: Frobenius number, syzygy, lattice, poset, Castelnuovo–Mumford regularity

Author's affiliations:

Manjunath, Madhusudan ¹; Smith, Ben ²

¹ Indian Institute of Technology Bombay, Powai, Mumbai 400076, India
² School of Mathematical Sciences, Queen Mary University of London, London, E1 4NS, United Kingdom

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2019__2_1_149_0,
     author = {Manjunath, Madhusudan and Smith, Ben},
     title = {Commutative algebra of generalised {Frobenius} numbers},
     journal = {Algebraic Combinatorics},
     pages = {149--171},
     publisher = {MathOA foundation},
     volume = {2},
     number = {1},
     year = {2019},
     doi = {10.5802/alco.31},
     zbl = {07024222},
     mrnumber = {3912171},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.31/}
}

TY  - JOUR
AU  - Manjunath, Madhusudan
AU  - Smith, Ben
TI  - Commutative algebra of generalised Frobenius numbers
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 149
EP  - 171
VL  - 2
IS  - 1
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.31/
DO  - 10.5802/alco.31
LA  - en
ID  - ALCO_2019__2_1_149_0
ER  -

%0 Journal Article
%A Manjunath, Madhusudan
%A Smith, Ben
%T Commutative algebra of generalised Frobenius numbers
%J Algebraic Combinatorics
%D 2019
%P 149-171
%V 2
%N 1
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.31/
%R 10.5802/alco.31
%G en
%F 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/articles/10.5802/alco.31/

References
Cited by

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

[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 (The IMA Volumes in Mathematics and its Applications), Volume 159, Springer, 2016, pp. 753-778 | DOI | MR | Zbl

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

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

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

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

[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 | Zbl

[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 | Zbl

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

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

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

[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 | DOI | MR | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

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

Cited by Sources: