Computation of delta sets of numerical monoids. (Q889031): Difference between revisions

A numerical monoid \(S\) is an additive submonoid of the natural numbers with finite complement. Each \(S\) has a unique minimal generating set \(\{a_1,\ldots,a_p\}\) with \(a_1<a_2<\cdots<a_p\) such that \(S\) is the set of linear combinations of elements from this set with nonnegative coefficients. The Delta set of an element \(s\in S\), denoted \(\Delta(s)\), is the set of differences between consecutive elements in the set of factorization lengths of \(s\). The Delta set of \(S\) is defined by \(\Delta(S)=\bigcup_{s\in S}\Delta(s)\). It is known that \(\Delta(S)\) is finite and that every element of \(\Delta(S)\) already occurs in some \(\Delta(s)\) where \(s\) is not `too large'. Theorem 1 in [\textit{S. T. Chapman, R. Hoyer}, and \textit{N. Kaplan}, Aequationes Math. 77, No. 3, 273-279 (2009; Zbl 1204.20078)] says that \(\Delta(S)\) is the union of \(\Delta(s)\) taken over all \(s<2pa_2a_p^2+a_1a_p\). The main result of this paper is to greatly improve this bound (Corollary 19) and to give a fast algorithm for computing \(\Delta(S)\). This algorithm has been implemented and is publicly available. Instead of needing to compute all factorizations of all small elements of \(S\), this paper shows that one need only compute the complete set of factorizations for a particular set of \(a_1\) elements and that Delta sets of the smaller elements can be deduced from these. \textit{A. Geroldinger}'s structure theorem for sets of lengths [Colloq. Math. 78, No. 2, 225-259 (1998; Zbl 0926.11082)], shows that the set of factorization lengths of \(s\in S\) consists of three pieces, where the middle piece is an arithmetic progression, so that all the interesting elements in \(\Delta(s)\) come from the long and short factorizations. The proofs in this article progress along the same lines. The authors divide the set of factorizations into three pieces and show that the factorization lengths in the middle piece form an arithmetic progression (Definition 15 and Theorem 16). They describe how the set of `long factorizations' of \(s\) and of \(s+a_1\) and the set of `short factorizations' for \(s\) and \(s+a_p\) are related for \(s\) sufficiently large (Theorem 18), which leads to the proof of the main result.