In this section we study sub-semigroups of the standard discrete space \((\N, +)\) studied in Section 1. Of particular interest are numerical semigroups defined in
Throughout this section we assume that \((S, +)\) is a sub-semigroup of \((\N, +)\) with the properties that
Of course, the meaning of sub-semigroup is closure under the semigroup operation, so if \(x, \, y \in S\) then \(x + y \in S\).
The first condition means that \((S, +)\) is a positive sub-semigroup of \((\N, +)\), and the second condition rules out the trivial case \(S = \{0\}\). Of course, the partial order \(\preceq\) associated with \((S, +)\) is given by \(x \preceq y\) if and only if \(x + z = y\) for some \(z \in S\). So \(x \preceq y\) implies \(x \le y\) for \(x, \, y \in S\) but not conversely. That is, \((S, +)\) is not necessarily algebriacally complete. The partial order graph \((S, \preceq)\) is left finite and hence the associated \(\sigma\)-algebra is \(\ms P(S)\), the collection of all subsets of \(S\). A standard way to construct a subsemigroup is by means of a generating set.
If \(A \subseteq \N\), then the sub-semigroup generated by \(A\) is the interesection of all subsemigroups of \((\N, +)\) that contain \(A\) (and the identity element 0). Equivalently, the base set \(\langle A \rangle\) of the sub-semigroup generated by \(A\) is \[ \langle A \rangle = \{x_1 + x_2 + \cdots x_n: n \in \N, \text { and } x_1, \, x_2, \ldots, x_n \in A\}\] where as usual, an empty sum is interpreted as \(0\). The generating set \(A\) is minimal if no proper subset of \(A\) generates the same semigroup.
If \((S, +)\) is a sub-semigroup of \((\N, +)\) then the set \(I\) of irreducible elements of \((S, +)\) is the unique minimal generating set of \((S, +)\).
The semigroup \((S, +)\) is left finite, so by a result in Section 2.2, if \(x \in S\) then \(x = i_1 + i_2 + \cdots + i_n\) for some \(n \in \N\) and \(i_1, \, i_2, \ldots, i_n \in I\). That is, \(\langle I \rangle = S\). Clearly \(I\) is also miniimal. Suppose that \(J\) is a proper subset of \(I\) and that \(i \in I - J\). But then \(i \notin \langle J \rangle\) since \(i\) is irreducible in \((S, +)\). Conversely, if \(A\) is a generating set for \((S, +)\) then clearly \(I \subseteq A\).
A numerical semigroup is a sub-semigroup of \((\N, +)\) that contains all but finitely many elements of \(\N\).
\((S, +)\) is a numerical semigroup if \(\N - S\) is finite.
In part (c), the maximum is with respect to the ordinary order \(\le\), of course.
So if \(m \in \N\) is the Frobenius number of \((S, +)\) then \(\{m + 1, m + 2, \ldots\} \subseteq S\). Sets that generate numerical semigroups have some special properties.
A semigroup \((S, +)\) generated by a set \(A \subset \N\) is a numerical semigroup if and only if \(\gcd(A) = 1\).
Suppose that \(n = \gcd(A) \in \{2, 3, \ldots\}\). The \(a\) is a multiple of \(n\) for every \(a \in A\) and hence \(x\) is a multiple of \(n\) for every \(x \in S = \langle A \rangle\). So the set of gaps \(\N - S\) is infinite.
Let \(I\) denote the set of irreducible elements of the numerical semiegoupr \((S, +)\) (so that \(I\) is the minimal generaing set). Then
In part (c), the minimum is with respect to the ordinary order \(\le\).
Suppose again that \((S, +)\) is a sub-semigroup of \((\N, +)\) and that \(I\) is the set of irreducible elements. As usual, we let \((S, \upa)\) denote the covering graph corresponding to the partial order graph \((S, \preceq)\). Then for \(x, \, y \in S\), \(x \upa y\) if and only if \(y = x + i\) for some \(i \in I\).
Once again, suppose that \((S, +)\) is a sub-semigroup of \((\N, +)\), as defined in . Since the corresponding partial order graph \((S, \preceq)\) is a lattice, the graph is stochastic. That is, the reliability function \(F\) of a probability measure \(P\) on \(\ms P(S)\) uniquely determines \(P\). As usual, our primary interest is in exponential distributions for \((S, +)\) and constant rate distributions for the corresponding partial order graph \((S, \preceq)\) and for its covering graph \((S, \upa)\).
\(F: S \to (0, 1]\) is the reliability function of an exponential distribution on \((S, +)\) if and only if there exists \(q \in (0, 1)\) such that \(F(x) = q^x\) for \(x \in S\). The rate constant is \(\alpha = 1 / \sum_{x \in S} q^x \).
Suppose that \(q \in (0, 1)\) and that \(F(x) = q^x\) for \(x \in S\). Then trivially \(F\) is multiplicative: \(F(x + y) = F(x) F(y)\) for \(x, \, y \in S\). Also, \[\sum_{x \in S} F(x) \le \sum_{n = 0}^\infty q^n = \frac{1}{1 - q} \lt \infty\] so \(F\) is the reliability function of an exponential distribution on \((S, +)\) by a result in Section 2.3. The rate constant \(\alpha\) is given by \(1 / \alpha = \sum_{x \in S} q^x\). Conversely, suppose that \(F\) is the reliability function for an exponential distribution on \((S, +)\).Let \(i = \min(S_+)\). If \(x \in S\) then \(i x = x i \in S\) so by the memoryless property, \([F(x)]^i = [F(i)]^x\) so \(F(x) = [F(i)]^{x / i}\). That is, \(F\) has the form given in the theorem with \(q = [F(i)]^{1 / i}\).
The following result is essentially a restatment of .
Suppose that \(X\) has a geometric distribution on \(\N\). Then the conditional distribution of \(X\) given \(X \in S\) has an exponential distribution on \((S, +)\). Moreover, every exponential distribution on \((S, +)\) has this form.
Suppose that \(X\) has the geometric distribution on \(\N\) with success parameter \(p \in (0, 1)\). Then of course, \(X\) has an exponential distribution on the standard discrete semigroup \((\N, +)\), with reliability function \(F\) defined by \(F(x) = (1 - p)^x\) for \(x \in \N\). By a standard result in Section 2.4, the conditional distribution of \(X\) given \(X \in S\) is exponential for the sub-semigroup \((S, +)\) and the reliability function of this conditional distribution is simply \(F\) restricted to \(S\). Conversely, an exponential distribution on \((S, +)\) has a reliability function \(F\) of the form \(F(x) = q^x\) for \(x \in S\) where \(q \in (0, 1)\). The corresponding density function \(f\) is \(f(x) = \alpha(q) q^x\) for \(x \in S\) where the rate constant \(\alpha(q)\) is simply the normalizing constant. Equivalently, if \(X\) has the geometric distribution on \(\N\) with success parameter \(1 - q\) then \(\P(X = x \mid X \in S) = \P(X = x) / \P(X \in S) = f(x) \) for \(x \in S\).
Of course, the exponential distribution described in has constant rate for the associated partial order graph \((S, \preceq)\). The distribution also has constant rate for the covering graph \((S, \upa)\).
Suppose that random variable \(X\) in \(S\) has density function \(f\) given by \(f(x) = c q^x\) for \(x \in S\), with parameter \(q \in (0, 1)\), and where \(c = 1 / \sum_{x \in S} q^x\) is the normaliziing constant. Then \(X\) has constant rate \(1 / \sum_{i \in I} q^i\) for the covering graph \((S, \upa)\). Moreover, every constant rate distribution for \((S, \upa)\) has this form.
As before, let \(I\) denote the set of irreducible elements of \((S, +)\), or equivalently, the minimial generatingn set. Suppose that \(X\) has density \(f\) given in the theorem. Then the reliability function \(G\) for \((S, \upa)\) is given by \[G(x) = \sum_{i \in I} f(x + i) = c q^x \sum_{i \in I} q^i = f(x) \sum_{i \in I} q^i, \quad x \in S\] Conversely, suppose that \(f\) is the density function of a distribution on \(S\) with constant rate \(\alpha\) for \((S, \upa)\). Let \(G\) denote the reliability function. Then \[G(x) = \sum_{i \in I} f(x + i) = \alpha \sum_{i \in I} G(x + i), \quad x \in S\] The characterstic equation for this linear recurrence relation is \[\alpha \sum_{i \in I} r^{x + i} - r^x = 0, \quad x \in S\] or equivalently \(\varphi(r) = 0\) where \(\varphi(r) = \alpha \sum_{i \in I} r^i - 1\) for \(r \in (0, 1)\). Note that \(\varphi(0) = -1\), \(\varphi(1) = \alpha \#(I) - 1\), and \(\varphi^\prime(r) = \alpha \sum_{i \in I} i r^{i - 1}\) for \(r \in \(0, 1)\). So if \(\alpha \gt 1 / \#(I)\), then there exists a unique distribution with constant rate \(\alpha\), with reliability function of the form \(G(x) = r^x\) for \(x \in S\). Of course, \(r \in (0, 1)\) depends on \(\alpha\).
Fix \(a \in \N_+\) and let \(S = \{0, a, a + 1, a + 2, \ldots\}\). The numerical semigroup \((S, +)\) has (miniimal) generating set \(A = \{a, a + 1, \ldots 2 a - 1\}\). The genus and Frobenius number are \(a - 1\), and the embedding dimension and multiplier are \(a\). The exponential distribution on \((S, +)\) with parameter \(q \in (0, 1)\) as defined in has probability density function \(f\) given by \[f(x) = \frac{1 - q}{1 - q + q^a} q^x, \quad x \in S\] so the rate constant is \((1 - q) / (1 - q + q^a)\). This distribution also has constant rate for the covering graph \((S, \upa)\), with rate constant. \((1 - q) / (q^a - q^{2 a})\).
Fix an odd integer \(b \ge 3\) and let \(S = \langle \{2, b\} \rangle = \{0, 2, 4, \ldots, b - 3, b - 1, b, b + 1, b + 2, \ldots \}\). The numerical semigroup \((S, +)\) has embedding number 2, multiplier 2, Frobenius number \(b - 2\) and genus \((b - 1) / 2\). The exponential distribution on \((S, +)\) with parameter \(q \in (0, 1)\) as defined in has probability density function \(f\) given by \[f(x) = \frac{1 - q^2}{1 + q^b} q^x, \quad x \in S\] so the rate constant is \((1 - q^2) / (1 + q^b)\). This distribution also has constant rate for the covering graph \((S, \upa)\), with rate constant. \(1 / (q^2 + q^b)\).