2025/05/29 by Massimo Bartoletti, Bartoletti, Massimo, Stefano Bonzio +3
Computer Science · Mathematics · #Commutative Algebra and Its Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Polynomial and algebraic computation #Rings, Modules, and Algebras
paper · pdf · doi:10.48550/arxiv.2505.23205
openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A numerical semigroup is a co-finite submonoid of the monoid of non-negative integers under addition. Many properties of numerical semigroups rely on some fundamental invariants, such as, among others, the set of gaps (and its cardinality), the Apéry set or the Frobenius number. Algorithms for calculating invariants are currently based on computational tools, such as GAP, which lack proofs (either formal or informal) of their correctness. In this paper we introduce a Rocq formalization of numerical semigroups. Given the semigroup generators, we provide certified algorithms for computing some of the fundamental invariants: the set of gaps, of small elements, the Apéry set, the multiplicity, the conductor and the Frobenius number. To the best of our knowledge this is the first formalization of numerical semigroups in any proof assistant.