Subadditive function
Definition
Let \(\mathbb{Q}_0^+\) denote the set of non-negative rational numbers and let \(f : \mathbb{N} \to \mathbb{Q}_0^+\) be a map. It is said that \(f\) is a subadditive function if
\(f(0) = 0\),
\(f(x + y) \le f(x) + f(y)\) for all \(x, y \in \mathbb{N}\).
Given a subadditive function \(f\), the set
\[ M(f) = \{x \in \mathbb{N} ~ | ~ f(x) \le x\}, \]
is a submonoid of \(\mathbb{N}\). Moreover, if \(f\) has period \(m\) for some \(m \in \mathbb{N} \setminus \{0\}\), it can be proven that \(M(f)\) is a numerical semigroup.
Examples
\(\circ\) Let \(f: \mathbb{N} \to \mathbb{Q}_0^+\) such that \(f(0) = 0\) and for all \(n \in \mathbb{N}\), \(f(n) = 2n + 1\). Given \(x, y \in \mathbb{N}\),
\[ f(x + y) = 2(x + y) + 1 = 2x + 2y + 1 < (2x + 1) + (2y + 1) = f(x) + f(y). \]
In conclusion, \(f\) is a subadditive function.
Examples with GAP
The following example is made with the package NumericalSgps in GAP.
\(\diamond\) Let \(f\) be a periodic subadditive function with period \(m\). Given a list of images of the integers from \(1\) to \(m\), the function NumericalSemigroupBySubAdditiveFunction returns the numerical semigroup \(M(f)\) if it is possible (that means, if the list generates a subadditive function). The image of \(m\) has to be \(0\).
gap> S := NumericalSemigroupBySubAdditiveFunction([6, 5, 3, 0]);
<Numerical semigroup>\(S\) is the numerical semigroup of the subadditive function \(f\) such that \(f(0) = 0, f(1) = 6, f(2) = 5, f(3) = 3\) and period \(m = 4\). The function SmallElements returns a list with the left elements and the conductor of the numerical semigroup.
gap> SmallElements(S);
[ 0, 3, 4, 6 ]To sum up, the numerical semigroup generated by \(f\) is \(S = M(f) = \{0, 3, 4, 6, \rightarrow\}\).
References
https://gap-packages.github.io/ numericalsgps.