Source-linked AI summary
numericalsgps, a GAP package for numerical semigroups
Manuel Delgado, Pedro A. García Sánchez
TL;DR
Numerical-semigroup computations lacked a unified dedicated package, motivating numericalsgps. The manuscript surveys its GAP-based procedures for numerical and affine semigroups, including structural and factorization computations. It presents broad computational coverage, from foundational invariants to polynomial, affine, and nonunique-factorization methods.
Problem
Numerical-semigroup computations were previously dispersed across programming languages and interfaces, creating a need for a unified package.
Method
The manuscript surveys numericalsgps procedures for numerical and affine semigroups, including presentations, factorization invariants, polynomial constructions, and affine-semigroup computations.
Results
numericalsgps provides computations spanning basic semigroup structure, affine semigroups, polynomially defined semigroups, and nonunique-factorization invariants.
Takeaways & Limitations
The package brings diverse numerical- and affine-semigroup procedures into one computational framework while reflecting developments in the area.
Abstract
from arXiv · showhide
The package numericalsgps performs computations with and for numerical semigroups. Recently also affine semigroups are admitted as objects for calculations. This manuscript is a survey of what the package does, and at the same time of the trending topics on numerical semigroups.
1. Introduction
numericalsgps unifies numerical-semigroup computations that were previously scattered across languages and interfaces. Written in GAP, it has evolved into a survey-oriented package covering numerical and affine semigroups.
- Motivation: The package was created because numerical-semigroup procedures lacked a dedicated, unified computational environment.Earlier functions were implemented in distinct programming languages with incompatible interfaces, making communication difficult.
- Motivation: The authors chose GAP as the implementation language, mainly because of the first author’s experience.
- Development: Since its 2005 release, numericalsgps has gained functionality and replaced algorithms with newer, faster versions.
- Manuscript scope: The manuscript describes package contents, gives self-contained definitions and illustrative examples, and points to literature on implemented algorithms.It also functions as a review of computational procedures for numerical and affine semigroups.
- External software: Interactions with other commutative-algebra packages can substantially improve execution time for affine-semigroup functions.
2. Contents
The package supports multiple representations and operations for numerical semigroups, while also documenting definitions, invariants, and construction methods. Its scope includes gaps, generators, interval and modular descriptions, Apéry sets, and periodic functions.
- Numerical semigroups: A numerical semigroup is a cofinite additive submonoid of the nonnegative integers.
- Numerical semigroups: Gaps and fundamental gaps can describe a numerical semigroup, and the package tests and constructs semigroups from corresponding lists.
- Representations: Numerical semigroups can be defined through intervals, modular or proportionally modular inequalities, generating sets, Apéry sets, and periodic subadditive functions.
- Representations: An Apéry set has one element in each residue class modulo its nonzero reference element, enabling efficient membership, Frobenius-number, and genus computations.
- Representations: The package provides functions to define numerical semigroups from generating sets, including equivalent interval and generator descriptions.The examples show an interval-defined semigroup equal to one generated by seven integers.
- Basic operations: The package computes multiplicity, generating systems, minimal generators, small elements, gaps, embedding dimension, Apéry sets, Frobenius number, conductor, and fundamental gaps.
2.3. Basic operations.
Basic operations use stored structural information to compute standard invariants and construct related numerical semigroups. The package also exposes representations through Apéry sets, Kunz coordinates, and factorization homomorphisms.
- Basic operations: When an Apéry set is known, the package computes the Frobenius number using Selmer’s formulas.
- Basic operations: The package lists the first n integers belonging to a numerical semigroup.
- Basic operations: Pseudo-Frobenius numbers are maximal gaps under the semigroup order, and their cardinality is the semigroup’s type.
- Basic operations: Kunz coordinates encode the Apéry set of the multiplicity as a point satisfying a defining system of inequalities.
- Basic operations: Special gaps can be computed and used to construct oversemigroups by adjoining them.
- Basic operations: The factorization homomorphism maps N^e onto a semigroup generated by n_1,...,n_e, providing the basis for its factorization congruence.
2.4. Presentations of a numerical semigroup.
The package computes presentations and factorization structures of numerical semigroups through congruences, graphs, Betti elements, and primitive elements. It also supports related constructions such as semigroup intersections and generator removal.
- Presentations: A presentation generates the factorization congruence kerϕ, while a minimal presentation is a minimal generating system for that congruence.
- Presentations: Minimal presentations are constructed from graphs associated with semigroup elements whose vertices are generators and whose edges encode compatible decompositions.
- Presentations: Betti elements are those whose associated graphs are disconnected, and the package computes both Betti elements and minimal presentations.
- Presentations: Generic numerical semigroups have unique minimal presentations up to permutation of presentation pairs.
- Presentations: The package generalizes associated graphs to simplicial complexes called shaded sets, which have properties connected with the generating function.
- Presentations: Primitive elements are images of minimal nonzero generators of the factorization congruence and are computed because they influence factorization properties.
- Related constructions: Functions also support forming semigroups by adjoining special gaps, removing minimal generators, or intersecting two numerical semigroups.
2.5. Constructing numerical semigroups from others.
This section presents constructions and classifications of numerical semigroups, together with numericalsgps procedures for computing them and related ideals.
- Constructing numerical semigroups: The package computes quotients, constructs inductive numerical semigroups through repeated multiples, and provides procedures for oversemigroups classified by genus or Frobenius number.The multiple operation combines a scaled semigroup with all integers above a threshold.
- Irreducible semigroups: Every numerical semigroup decomposes, not uniquely, as an intersection of irreducible numerical semigroups, and the package can compute such decompositions.It also enumerates irreducible semigroups with a fixed Frobenius number.
- Structural classes: The package tests symmetry, pseudo-symmetry, complete-intersection structure, gluings, freeness, and telescopic structure.Symmetric semigroups coincide with irreducible semigroups of odd Frobenius number; even-Frobenius irreducible semigroups are pseudo-symmetric.
- Structural classes: It tests almost-symmetry and computes all almost symmetric semigroups with a prescribed Frobenius number.For example, the package reports 1827 almost symmetric numerical semigroups with Frobenius number 31.
2.7. Ideals of numerical semigroups.
The package supports numerical-semigroup ideals through computations of their elements, operations, Hilbert functions, reduction numbers, and associated ring properties.
- Ideal operations: It computes small elements, Apéry sets, ambient semigroups, membership, and operations including addition, subtraction, intersection, blow-up, and star-closure.The supported operations also include union, set difference, integer multiplication, and translation.
- Ideal invariants: The Hilbert function of an ideal maps n to nI \ (n + 1)I, while the reduction number is the least n satisfying min(I) + nI = (n + 1)I.The package provides procedures to compute both invariants.
- Ideal invariants: Microinvariants are computed to help determine whether the graded ring associated to K⟦S⟧ is Cohen–Macaulay.This connects ideal computations with a property of the associated graded ring.
- Associated rings: The package tests whether a numerical semigroup is monomial using valuation semigroups of intermediate rings under the stated characteristic-zero assumptions.The criterion concerns whether every such ring is a semigroup ring.
- Basic structure: The embedding dimension is the cardinality of the unique minimal generating system and is at most the multiplicity.Maximal embedding dimension occurs when these two quantities are equal.
2.8. Numerical semigroups with maximal embedding dimension.
This section surveys maximal embedding dimension and related numerical-semigroup classes, emphasizing closure properties, factorizations, and computable invariants.
- Maximal embedding dimension: For fixed multiplicity m, maximal embedding dimension semigroups are closed under intersection and adjoining the Frobenius number.The section uses these properties to define maximal embedding dimension closures and minimal generators relative to the class.
- Arf and saturated semigroups: Arf numerical semigroups generalize the maximal-embedding-dimension condition through x + y − z ∈ S whenever x ≥ y ≥ z, and every Arf semigroup has maximal embedding dimension.Arf semigroups are also closed under finite intersections and adjoining the Frobenius number.
- Arf and saturated semigroups: Saturated semigroups form another Frobenius variety, and numericalsgps provides functions analogous to those for Arf semigroups.Saturation is defined by closure under the stated integer linear combinations satisfying the nonnegativity condition.
- Factorizations and invariants: The package computes factorizations, maximal denumerants, L-shapes, Delta sets, elasticity, catenary degree, tame degree, and Möbius functions.These procedures cover both factorization structure and nonunique-factorization invariants.
- Factorizations and invariants: The ω-primality measures how far an element is from being prime, and the package uses a faster procedure for computing the semigroup invariant.The semigroup’s ω-primality is the maximum among the ω-primalities of its minimal generators.
- Hilbert series: The package also computes Hilbert series and associated polynomials for numerical semigroups.The associated polynomial is defined by (1 − x)HS(x).
2.10. Polynomials, formal series and numerical semigroups.
The package connects numerical semigroups with associated polynomials, formal series, algebraic curves, and algebras, providing procedures for computation and classification.
- Associated polynomials and series: For a numerical semigroup S, (1 − x)HS(x) is a polynomial called the polynomial associated to S, and numericalsgps computes it and the Hilbert series.The Hilbert series is treated as a formal series distinct from the Hilbert function.
- Associated polynomials and series: For complete intersections, the associated polynomial has roots on the unit circle and is a product of cyclotomic polynomials.The package tests the relevant root property and supports auxiliary cyclotomic computations.
- Symmetry: A numerical semigroup is symmetric exactly when its associated polynomial is self-reciprocal, meaning its coefficients form a palindrome.This gives a polynomial characterization of symmetry.
- Curves: Intersection multiplicities of an irreducible plane curve with one place at infinity form a numerical semigroup, whose generators arise from a δ-sequence.The package implements this construction and computes δ-sequences with fixed Frobenius number.
- Algebras: Under suitable conditions, values or degrees of series and polynomials in an algebra form a numerical semigroup, and the package computes it and a basis with minimally generating values or degrees.The construction applies to K⟦F⟧ and K[F].
2.11. Affine semigroups.
The package extends its numerical-semigroup functionality to affine semigroups, supporting representations, structural computations, and nonunique factorization invariants. An example demonstrates computations on an affine semigroup defined by subgroup equations.
- Affine semigroups: Affine semigroups are finitely generated submonoids of N^n, represented in the package by generators, subgroup conditions, or cones.The package distinguishes full semigroups in the positive orthant of a subgroup of Z^n from normal semigroups in the positive orthant of a cone.
- Affine semigroups: The package provides affine-semigroup methods for membership, minimal presentations, gluings, Betti and primitive elements, and nonunique factorization invariants.New procedures based on Hilbert functions and binomial ideals were under development.
- Example: The example computes with G∩N^3, where G is defined by two congruence conditions modulo 2.The subgroup is specified by x+y ≡ 0 mod 2 and x+z ≡ 0 mod 2.
- Example: For the example, the package returns omega primality 3 and the Betti element [2, 2, 2].The displayed GAP session also lists four generators for the affine semigroup.
- Random affine semigroups: Random affine numerical semigroups can be generated for examples and are used extensively to test newly implemented algorithms.These functions are based on GAP methods for creating “random” objects.
2.12. Random.
The package includes random numerical-semigroup generation for constructing examples and testing algorithms, alongside contributed procedures covering semigroup algebras and factorization invariants. These contributions broaden the computational topics addressed by the package.
- 2.13. Contributions: The manuscript identifies functions by Sammartano and O’Neill among the package’s contributions.It also notes coimplementations involving J. I. García-García and A. Sánchez-R.-Navarro.
- 2.13. Contributions: Sammartano’s functions derive properties of the semigroup algebra k[[S]] and its associated graded algebra from properties of S.They include procedures for purity, M-purity, Buchbaum, Gorenstein, complete intersection, Apéry-set shapes, and type sequences.
- 2.13. Contributions: O’Neill’s methods address nonunique factorization invariants, including factorizations, omega-primality, Delta sets, and Delta-set periodicity.The procedures apply both to lists of elements and, for Delta sets, to the whole semigroup.
3. Interaction with other packages
The package interacts with external commutative-algebra software because affine- and numerical-semigroup computations often reduce to linear Diophantine problems or Gröbner-basis calculations. These interactions can substantially improve execution time for affine-semigroup functions.
- 3. Interaction with other packages: Computations with affine and numerical semigroups often involve nonnegative integer solutions of linear Diophantine equations or Gröbner-basis calculations of binomial ideals.
- 3. Interaction with other packages: The package interacts with Singular, Normaliz, and 4ti2 to support these computational tasks.The manuscript describes this interaction as a step forward for the project.