On dynamic algorithms for factorization invariants in numerical monoids

Barron, Thomas; O’Neill, Christopher; Pelayo, Roberto

doi:10.1090/mcom/3160

On dynamic algorithms for factorization invariants in numerical monoids
HTML articles powered by AMS MathViewer

by Thomas Barron, Christopher O’Neill and Roberto Pelayo PDF

Math. Comp. 86 (2017), 2429-2447 Request permission

Abstract:

Studying the factorization theory of numerical monoids relies on understanding several important factorization invariants, including length sets, delta sets, and $\omega$-primality. While progress in this field has been accelerated by the use of computer algebra systems, many existing algorithms are computationally infeasible for numerical monoids with several irreducible elements. In this paper, we present dynamic algorithms for the factorization set, length set, delta set, and $\omega$-primality in numerical monoids and demonstrate that these algorithms give significant improvements in runtime and memory usage. In describing our dynamic approach to computing $\omega$-primality, we extend the usual definition of this invariant to the quotient group of the monoid and show that several useful results naturally extend to this broader setting.

References

David F. Anderson, Scott T. Chapman, Nathan Kaplan, and Desmond Torkornoo, An algorithm to compute $\omega$-primality in a numerical monoid, Semigroup Forum 82 (2011), no. 1, 96–108. MR 2753835, DOI 10.1007/s00233-010-9259-5
T. Barron, C. O’Neill, and R. Pelayo, On the set of elasticities in numerical monoids, preprint, available at arXiv:1409.3425. To appear in Semigroup Forum.
V. Blanco, P. A. García-Sánchez, and A. Geroldinger, Semigroup-theoretical characterizations of arithmetical invariants with applications to numerical monoids and Krull monoids, Illinois J. Math. 55 (2011), no. 4, 1385–1414 (2013). MR 3082874
Craig Bowles, Scott T. Chapman, Nathan Kaplan, and Daniel Reiser, On delta sets of numerical monoids, J. Algebra Appl. 5 (2006), no. 5, 695–718. MR 2269412, DOI 10.1142/S0219498806001958
Scott T. Chapman, Marly Corrales, Andrew Miller, Chris Miller, and Dhir Patel, The catenary and tame degrees on a numerical monoid are eventually periodic, J. Aust. Math. Soc. 97 (2014), no. 3, 289–300. MR 3270769, DOI 10.1017/S1446788714000330
S. T. Chapman, P. A. García-Sánchez, and D. Llena, The catenary and tame degree of numerical monoids, Forum Math. 21 (2009), no. 1, 117–129. MR 2494887, DOI 10.1515/FORUM.2009.006
Scott T. Chapman, Rolf Hoyer, and Nathan Kaplan, Delta sets of numerical monoids are eventually periodic, Aequationes Math. 77 (2009), no. 3, 273–279. MR 2520501, DOI 10.1007/s00010-008-2948-4
M. Delgado, P. García-Sánchez, and J. Morais, GAP Numerical Semigroups Package, http://www.gap-system.org/Manuals/pkg/numericalsgps/doc/manual.pdf.
Peter Freyd, Redei’s finiteness theorem for commutative semigroups, Proc. Amer. Math. Soc. 19 (1968), 1003. MR 227290, DOI 10.1090/S0002-9939-1968-0227290-4
J. I. García-García, M. A. Moreno-Frías, and A. Vigneron-Tenorio, Computation of delta sets of numerical monoids, Monatsh. Math. 178 (2015), no. 3, 457–472. MR 3411252, DOI 10.1007/s00605-015-0785-9
J. I. García-García, M. A. Moreno-Frías, and A. Vigneron-Tenorio, Computation of the $\omega$-primality and asymptotic $\omega$-primality with applications to numerical semigroups, Israel J. Math. 206 (2015), no. 1, 395–411. MR 3319645, DOI 10.1007/s11856-014-1144-6
P. García-Sánchez, D. Llena, and A. Moscariello, Delta sets for numerical semigroups with embedding dimension three, preprint. Available at arXiv: math.AC/1504.02116
Franz Halter-Koch, On the asymptotic behaviour of the number of distinct factorizations into irreducibles, Ark. Mat. 31 (1993), no. 2, 297–305. MR 1263556, DOI 10.1007/BF02559488
C. O’Neill, On factorization invariants and Hilbert functions, preprint. Available at arXiv: math.AC/1503.08351.
Christopher O’Neill and Roberto Pelayo, On the linearity of $\omega$-primality in numerical monoids, J. Pure Appl. Algebra 218 (2014), no. 9, 1620–1627. MR 3188860, DOI 10.1016/j.jpaa.2014.01.002
Christopher O’Neill and Roberto Pelayo, How do you measure primality?, Amer. Math. Monthly 122 (2015), no. 2, 121–137. MR 3324682, DOI 10.4169/amer.math.monthly.122.02.121
J. C. Rosales and M. B. Branco, Decomposition of a numerical semigroup as an intersection of irreducible numerical semigroups, Bull. Belg. Math. Soc. Simon Stevin 9 (2002), no. 3, 373–381. MR 2016576
J. C. Rosales and P. A. García-Sánchez, Numerical semigroups, Developments in Mathematics, vol. 20, Springer, New York, 2009. MR 2549780, DOI 10.1007/978-1-4419-0160-6