We will study the mathematical objects of interest in this chapter from three different points of view. We start with a nonempty countable set \(I\). We generally use subscript notation for functions defined on \(I\).
The base sets are defined as follows:
The sets \(R\), \(S\), and \(T\) are in one-to-one correspondence with each other, and are countable.
That is, \(x \in S\) is unique up to the ordering of the factors. Recall also that a multiset is like an ordinary set, except that an element may be repeated a finite number of times. But like an ordinary set, there is no additional structure beyond membership, so in particular, the elements are not ordered.
So for \(\bs n \in R\), the condition \(\sum_{i \in I} n_i \lt \infty\) is equivalent to the property that \(n_i = 0\) for all but finitely many \(i \in I\). If \(I\) is finite, then \(R = \N^I\), the collection of all functions from \(I\) to \(\N\). If we want to indicate the dependence on \(I\) we will write \(R_I\), \(S_I\) and \(T_I\). Since the sets are countable, we have our usual reference measure spaces in the background. That is, in each case the \(\sigma\)-algebra consists of all subsets of the base set, and counting measure \(\#\) is the reference measure. Next we define the basic operations on the objects.
Suppose that \(\bs m, \, \bs n \in R\), and let \(x, \, y\) be the corresponding elements in \(S\), and \(a, \, b\) the corresponding elements in \(T\). The operations on \(\bs m, \bs n\) below are pointwise.
In the context of (e), \(\min\{\bs m, \bs n\} = \bs 0\) means that no \(i \in I\) satifies \(n_i \gt 0\) and \(m_i \gt 0\). We can now define the semigroups of interest.
\((R, +)\), \((S, \cdot)\), and \((T, +)\) are commutative, positive semigroups and are isomorphic to each other. The corresponding partial order graphs are also isomorphic, and are left finite lattices.
The defining properties of a commuatative, positive semigroup are cleraly satisfied. Suppose that \(\bs m, \bs n \in R\) and that \(x, \, y\) are the corresponding elements of \(S\) and that \(a, \, b\) are the corresponding elements of \(T\). Note that if \(\bs m \le \bs n\) then \(\bs n - \bs m\) corresponds to \(x^{-1} y \in S\) and to the set difference \(b - a \in T\).
Although the semigroups are isomorphic, sometimes the notation and terminology of one is more natural than the others. The semigroup \((S, \cdot)\) is an arithemetic semigroup in the context of abstract analytic number theory (see for example the book by Knopfmacher), although technically, the norm structure described in Section 2 is also a requirement. The division symbol \(|\) is often used for the partial order relation in arithmetic semigroups, but that symbol lacks direction so we will use our generic partial order symbol \(\preceq\). Here are a few of examples:
If \(I\) has a single element, then the semigroups are isomorphic to the standard discrete semigroup \((\N, +)\) studied in Section 4.1.
If \(I = \{2, 3, 5, 7, \ldots\}\), the ordinary set of prime numbers, then \(S = \N_+\) and \(\cdot\) is ordinary multiplcation. The semigroup \((\N_+, \cdot)\) is the standard arithmetic semigroup.
Let \((I^*, \cdot)\) be the free semigroup associated with the countable collection of letters \(I\), as studied in Chapter 5. If we impose the equations \(i j = j i \) for \(i, \, j \in I\), then the new semigroup \((S, \cdot)\) is no longer free, but is the arithmetic semigroup with \(I\) as the set of prime elements.
Suppose that \(J\) is a proper subset of \(I\). Then \((S_J, \cdot)\) is a sub-semigroup of \((S_I, \cdot)\) with \(J\) as the set of prime elements. The corresponding quotient space is \((S_{I - J}, \cdot)\) with \(I - J\) as the set of prime elements. Analogous results hold for the other two semigroups.
Technically, for \(R_J\) to be a subset of \(R_I\), a function \(\bs n = (n_j: j \in J) \in R_J\) needs to be extended to a function on \(I\) by the obvious rule that \(n_i = 0\) for \(i \in I - J\). Note also that \(T_J\) is the collection of multisets with values in \(J\).
Here is a bit more notation:
Suppose that \(\bs n \in R\) and that \(x\) is the corresponding element of \(S\) and that \(a\) is the corresponding element of \(T\).
In part (d), \(\bs n\) is the ordinary indicator function of the set \(a\). Going forward, we will sometimes use the same name for functions defined on \(R\), \(S\) or \(T\), for simplicity and because the various spaces are isomorphic. In particular, in the context of , define \begin{align*} d(a) = d(x) = d(\bs n) &= \sum_{i \in I} n_i \\ \omega(a) = \omega(x) = \omega(\bs n) &= \sum_{i \in I} \bs 1(n_i \gt 0) \end{align*} Of course, each of the partial order graphs has a corresponding covering graph.
The partial order graphs are uniform.
If \(\bs n = (n_i: i \in I) \in R\), then the length of a path from \(\bs 0\) to \(\bs n\) is \(d(\bs n) = \sum_{i \in I} n_i\). In the case of (a), \(\bs 1_i \in R\) is the function given by \(\bs 1_i(j) = 1\) if \(i = j\) and \(\bs 1_i(j) = 0\) for \(j \in I - \{i\}\).
The following definition is most naturally expressed in terms of the arithmetic semigroup \((S, \cdot)\). The corresponding conditions for the other two semigroups are given in the details
A function \(f: S \to \R\) is an arithemetic function for \((S, \cdot)\).
If \(f: R \to \R\) then for the semigroup \((R, +)\),
If \(f: T \to \R\) then for the semigroup \((T, +)\),
The collection of arithmetic functions for \((S, \cdot)\) forms a vector space, as usual, under the pointwise operations of addition and scalar multiplication. Under the convolution operation that we studied in Section 2.3, this vector space becomes an associative algebra, referred to as the Dirichlet algebra. Recall that the convolution of arithmetic functions \(f\) and \(g\) is defined by \[(f * g)(z) = \sum_{x y = z} f(x) g(y), \quad z \in S\] Note also that the sum of two additive (completely additive) functions is also additive (completely additive), and the product of two multiplicative (completely multiplicative) functions is also multiplicative (completely multiplicative). Suppose that \(x = \prod_{i \in I} i^{n_i} \in S\) where \(\bs n = (n_i: i \in I) \in R\). If \(g\) is multiplicative for \((S, \cdot)\) then \(g(x) = \prod_{i \in I} g\left(i^{n_i}\right)\). If \(g\) is completely multiplicatve then \(g(x) = \prod_{i \in I} [g(i)]^{n_i}\).
The walk functions for the partial order graphs are considered next.
For the graphs \((R, \le)\), \((S, \preceq)\) and \((T, \subseteq)\), the left walk function \(\tau_k\) of order \(k \in \N\) is given by \[\tau_k(a) = \tau_k(x) = \tau_k(\bs n ) = \prod_{i \in I} \binom{n_i + k}{k}\] for \(\bs n = (n_i: i \in I) \in R\), and where \(x \in S\) has the sequence \(\bs n\) of prime exponents, and where \(a \in T\) has multiplicty function \(\bs n\). The walk function \(\tau_k\) is multiplicative for \(k \in \N\).
\((R, \le)\) is essentially the power space of \((\N, \le)\) by \(I\). The left walk function of \((\N, \le)\) of order \(k \in \N\) is \[ n \mapsto \binom{n + k}{k}, \quad n \in \N\] Note that for the walk function for \((R, \le)\) in the displayed equation, all but finitely many factors in the prodcut are 1, since \(n_i = 0\) for all but finitely many \(i \in I\). If \(\bs n, \, \bs m \in R\) satisfy \(\min\{\bs m, \bs n\} = \bs 0\) then no \(i \in I\) satisfies \(m_i \gt 0\) and \(n_i \gt 0\), and therefore \[\tau_k(\bs m + \bs n) = \prod_{i \in I} \binom{m_i + n_i + k}{k} = \left[\prod_{i \in I, \, m_i \gt 0} \binom{m_i + k}{k}\right] \left[\prod_{i \in I, \, n_i \gt 0} \binom{n_i + k}{k}\right] = \tau_k(\bs m) \tau_k(\bs n) \]
For the graph \((S, \preceq)\) the multiplicative property means that \(\tau_k(x y) = \tau_k(x) \tau_k(y)\) whenever \(x, \, y \in S\) are relatively prime. Moreover, \(\tau_1(x)\) is the number of divisors of \(x \in S\), an important function in abstract analytic number theory. Similarly, for the graph \((T, \subseteq)\), the multiplicative property means that \(\tau_k(a + b) = \tau_k(a) \tau_k(b)\) whenever \(a, \, b \in T\) are disjoint. Moreover, \(\tau_1(a)\) is the number of subsets of \(a \in S\). The walk functions of the covering graphs are considered next. Recall the following definition from Chapter 5:
The multinomial coefficient \(C\) is defined on \(R\), \(S\), and \(T\) by \[C(a) = C(x) = C(\bs n) = \frac{\left(\sum_{i \in I} n_i\right)!}{\prod_{i \in I} n_i!}\] for \(\bs n = (n_i: i \in I) \in R\), and where \(x \in S\) has the sequence \(\bs n\) of prime exponents, and where \(a \in T\) has multiplicty function \(\bs n\).
Note that \(C(a)\) is the number of distinct permutations of the elements in \(a \in T\) and \(C(x)\) is the number of distinct representations of \(x \in S\) as a product of primes. Finally, \(C(\bs n)\) is the number of ways to partition a set of \(\sum_{i \in I} n_i\) objects into sets indexed by \(I\) with \(n_i\) elements in set \(i\) for each \(i \in I\). For the following result, let \(\upa\) denote the covering relation for \((R, \le)\), \((S, \preceq)\) and \((T, \subseteq)\).
For the graphs \((R, \upa)\), \((S, \upa)\) and \((T, \upa)\), the left walk function \(\gamma_k\) of order \(k \in \N\) is given by \[\gamma_k(a) = \gamma_k(x) = \gamma_k(\bs n) = \sum \{C(\bs m): \bs m \in R, \bs m \le \bs n, d(\bs m) = k\}\] for \(\bs n = (n_i: i \in I) \in R\) and where \(x \in S\) has the sequence \(\bs n\) of prime exponents and where \(a \in T\) has multiplicty function \(\bs n\).
This follows by a simple combinatorial argument. If \(\bs m \le \bs n\) with \(d(\bs m) = k\), then a walk (actually a path) from \(\bs n - \bs m\) to \(\bs n\) of length \(k\) is of the form \[(\bs n - \bs m) + \{i_1\} + \{i_2\} + \cdots + \{i_n\} \] where \(i_1, \, i_2, \ldots, i_k \in I\) are the elements of \(\bs m\). The number of distinct such paths for this \(\bs m\) is the multinomial coefficient \(C(\bs m)\). Moroever, every path of length \(k\) terminating in \(\bs n\) has this from for some such \(\bs m \le \bs n\). with \(d(\bs m) = k\).
Of course, with the multiple definitions of the multinomial coefficient, we could also write \begin{align*} \gamma_k(x) & = \sum \{C(y): y \in S, y \preceq x, d(y) = k\} \\ \gamma_k(a) & = \sum \{C(b): b \in T, b \subseteq a, d(b) = k\} \end{align*} The walk function \(\gamma_k\) is not multiplicative or additive, but there is a simple relationship between the walk functions at \(x y\) and the walk functions at \(x\) and \(y\) when \(x, \, y \in S\) are are relatively prime.
If \(x, \, y \in S\) are relatively prime then for \(n \in \N\), \[\gamma_n(x y) = \sum_{k = 0}^n \binom{n}{k} \gamma_k(x) \gamma_{n - k}(y)\]
An algebraic proof using is possible, but a combinatorial proof is better. Fix \(n \in \N\) and let \(k \in \{0, 1, \ldots, n\}\). A path of length \(k\) in the covering graph that terminates in \(x\) has the form \(u \cdot i_1 \cdot i_2 \cdots i_k\) for some \(u \preceq x\) where \(i_1, \, i_2, \ldots i_k\) are prime factors of \(x\). Similarly, a path of length \(n - k\) in the covering graph that terminates in \(y\) has the form \(v \cdot j_1 \cdot j_2 \cdots j_{n - k}\) for some \( v \preceq y\) where \(j_1, j_2, \ldots, j_{n - k}\) are prime factors of \(y\). A path of length \(n\) in the covering graph that terminates in \(x y\) can be constructed by starting at \(u v\) and then combining the first two paths. There are \(\binom{n}{k}\) choices for where to put the elements in the first path (and then by default the elements in the second path go into the remaining \(n - k\) slots). Since \(x\) and \(y\) are relatively prime, these \(\binom{n}{k}\) paths are distinct. Moreover, every path of legnth \(n\) terminating in \(x y\) has this form.
Equivalently, if \(a, \, b \in T\) are disjoint then \[\gamma_n(a + b) = \sum_{k = 0}^n \binom{n}{k} \gamma_k(a) \gamma_{n - k}(b)\] As noted in , the partial order graphs are uniform. But in the termnology of Section 1.2, they are not completely uniform. If \(\bs n \in R\), the number of paths in the covering graph \((R, \upa)\) from \(\bs 0\) to \(\bs n\) is \(C(\bs n)\), and so does not depend only on \(d(\bs n)\) (the distance from \(\bs 0\) to \(\bs n\) in the covering graph).
The next results relate to the Möbius function \(\mu\) of the semigroup and the corresponding Möbius kernel of the partial order graphs. Recall from Section 2.2 that \(\mu\) is defined inductively on the three semigroups by \begin{align*} & \mu(\bs 0) = 1, \quad \mu(\bs n) = -\sum_{\bs m \lt \bs n} \mu(\bs m), \; \bs n \in R_+ \\ & \mu(e) = 1, \quad \mu(x) = -\sum_{y \prec x} \mu(y), \; x \in S_+ \\ & \mu(\emptyset) = 1, \quad \mu(a) = -\sum_{b \subset a} \mu(b), \; a \in T_+ \end{align*}
The Möbius function \(\mu\) is multiplicative.
We use induction on the well-founded partial order graph \((S, \preceq)\). Suppose that \(x, \, y \in S\) are relatively prime, and that \(\mu(u v) = \mu(u) \mu(v)\) for every \(u, \, v \in S\) that are relativley prime with \(u v \prec x y\). Our goal is to show that \(\mu(x y) = \mu(x) \mu(y)\). Since \(x, \, y\) are relatively prime, \(t \prec x y\) if and only if \(t = u v\) where \(u \preceq x\), \(v \preceq y\) and \(u v \ne x y\). Moreover, the decomposition is unique. Hence \begin{align*} \mu(x y) &= -\sum_{t \prec x y} \mu(t) = -\sum_{u \prec x} \sum_{v \prec y} \mu(u v) - \sum_{v \prec y} \mu(x v) - \sum_{u \prec x} \mu(u y) \\ &= -\sum_{u \prec x} \sum_{v \prec y} \mu(u) \mu(v) - \sum_{v \prec y} \mu(x) \mu(v) - \sum_{u \prec x} \mu(u) \mu(y) \\ &= - \sum_{u \prec x} \mu(u) \sum_{v \prec y} \mu(v) - \mu(x) \sum_{v \prec y} \mu(v) - \mu(y) \sum_{v \prec y} \mu(v) \\ &= - \mu(x) \mu(y) + \mu(x) \mu(y) + \mu(x) \mu(y) = \mu(x) \mu(y) \end{align*}
So as in the details of , \(\mu(x y) = \mu(x) \mu(y)\) if \(x, \, y \in S\) are relatively prime. Equivalently, \(\mu(a + b) = \mu(a) \mu(b)\) if \(a, \, b \in T\) are disjoint.
The Möbius function \(\mu\) for \((S, \cdot)\) is given as follows:
Recall that \(e\) denotes the identity of \((S, \cdot)\), that is, the empty product.
Equivalently, \(\mu(a) = (-1)^k\) if \(a \in T\) is an ordinary subset of \(I\) with \(k \in \N\) (distinct) elements, and \(\mu(a) = 0\) if \(a \in T\) has repeated elements.
The Möbius kernel \(M\) is given as follows:
The dimension of the semigroup is the number of elements in the base set \(I\).
\((R, +)\), \((S, \cdot)\), and \((T, +)\) have dimension \(\#(I)\).
Recall that \(I\) is the set of irreducible elements of \((S, \cdot)\), so from a result in Section 2.2, \(\dim(S, \cdot) \le \#(I)\). Suppose that \(C \subset S\) with \(\#(C) \lt \#(I)\). We need to show that \(C\) cannot be a critical set, that is, there exists a non-trivial homomorphism \(\varphi\) from \((S, \cdot)\) into \((\R, +)\) with \(\varphi(x) = 0\) for every \(x \in C\). Let \(J \subseteq I\) denote the set of distinct prime factors of the elements in \(C\). The condition that \(\varphi(x) = 0\) for \(x \in S\) is equivalent to \[ \sum_{j \in J} n_j \varphi(j) = 0, \quad x = \prod_{j \in J} j^{n_j} \in C \] If \(J \subset I\), then define \(\varphi(j) = 0\) for \(j \in J\) and \(\varphi(i) = 1\) for \(i \in I - J\). If \(J = I\), then the equation above is a set of \(\#(C)\) linear, homogeneous equations in \(\#(I)\) unknowns. Since \(\#(C) \lt \#(I)\), there exists a nontrivial solution \(\varphi(i)\) for \(i \in I\). In either case, we then extend \(\varphi\) to a non-trivial homomorphism from \((S, \cdot)\) to \((\R, +)\) by the rule \[\varphi(x) = \sum_{i \in I} n_i \varphi(i), \quad x = \prod_{i \in I} i^{n_i} \in S\]
We close this section with alternate partial orders on the sets \(R\), \(S\), and \(T\), and when \(I\) is infinite and totally ordered, alternate semigroup operators as well. We will not pursue this line of investigation further in this chapter, but the definitions are worthwhile since they relate to the subset spaces that we will study in Chapter 8. Let \[E = \{\bs n \in R: n_i \in \{0, 1\} \text{ for all } i \in I\} = \{x \in S: x \text{ is square free}\} = \{a \in T: a \text{ is an ordinary set} \} \]
Define the relation \(\le_0\) on \(R\) by \(\bs m \le_0 \bs n\) if and only if \(m_i \gt 0\) implies \(n_i = m_i\) for each \(i \in I\).
Of course, we have the corresponding relations \(\preceq_0\) on \(S\) and \(\subseteq_0\) on \(T\). In the first case \(x \preceq_0 y\) for \(x, \, y \in S\) means that \(y\) has the same prime divisors as \(x\), with the same multiplicities, but perhaps other prime divisors as well. In the second case \(a \subseteq_0 b\) for \(a, \, b \in T\) means that \(a\) is a subset of \(b\) in the sense that \(b\) has the same elements as \(a\), with the same multiplicities, (and perhaps other elements with multiplicities as well). The order \(\le\) on \(R\) that was considered above extends \(\le_0\).
The relation \(\le_0\) is a partial order on \(R\). Moreover, if \(\bs m \le_0 \bs n\) then \(\bs m \le \bs n\) for \(\bs m, \bs n \in R\).
Clearly \(\bs n \le_0 \bs n\) for \(\bs n \in R\) so \(\le_0\) is reflexive. If \(\bs m \le_0 \bs n\) and \(\bs n \le_0 \bs m\) for \(\bs m, \bs n \in R\) then \(\bs m\) and \(\bs n\) have the same positive values and hence also the same zeros so \(\bs m = \bs n\). For the transitive property, suppose that \(\bs l, \bs m, \bs n \in R\) and that \(\bs l \le_0 \bs m\) and \(\bs m \le_0 \bs n\). If \(l_i \gt 0\) then \(m_i = l_i\) and then also \(m_i \gt 0\) so \(n_i = m_i = l_i\). Hence \(\bs l \le_0 \bs n\). Finally, suppose that \(\bs m \le_0 \bs n\) for \(\bs m, \bs n \in R\) and let \(i \in I\). If \(m_i \gt 0\) then \(n_i = m_i\). If \(m_i = 0\) then no conditions are imposed on \(n_i \in \N\). Hence \(m_i \le n_i\) for all \(i \in I\).
Restricted to \(E\) (and in the context of multisets), the partial order \(\subseteq_0\), like the partial order \(\subseteq\), reduces to the ordinary subset partial order: if \(a, \, b \in E\) (so ordinary finite subsets of \(I\)), then \(a \subseteq_0 b\) if and only if every element of \(a\) is also an element of \(b\).
Let \((R, \upa_0)\) denote the covering graph associated with \((R, \le_0)\). Then \(\bs m \upa_0 \bs n\) if and only if there exists \(j \in I\) with \(m_j = 0\) and \(n_j \gt 0\) and \(m_i = n_i\) for \(i \in I - \{j\}\).
Suppose that \(\bs m \in R\) and that \(\bs n \in R\) is defined as in the theorem for fixed \(j \in I\). Clearly \(\bs m \lt_0 \bs n\). Suppose that \(\bs l \in R\) satisfies \(\bs m \le_0 \bs l \le_0 \bs n\). If \(m_i \gt 0\) for \(i \in I - \{j\}\) then \(m_i = l_i = n_i\). If \(m_i = 0\) for \(i \in I - \{j\}\) and \(l_i \gt 0\) then \(n_i = l_i \gt 0\), a contradiction. It follows that \(l_i = m_i\) for all \(i \in I - \{j\}\). So if \(l_j = 0\) then \(\bs m = \bs l\) while if \(l_j \gt 0\) then \(l_j = n_j\) so \(\bs l = \bs n\).
When \(I\) is infinite and totally ordered, there is a simple way to construct a positive semigroup on \(R\) whose associated partial order is \(\le_0\).
Suppose that \(I\) is countably infinite and totally ordered with a minimum element, so that \(I = (i_1, i_2, \ldots)\) and hence, an element \(\bs n \in R\) can be considered as an ordered sequence with values in \(\N\). Define the operation \(\circ\) on \(R\) as follows: For \(\bs m, \, \bs n \in R\), \(\bs m \circ \bs n \in R\) is obtained by putting the values of \(\bs n\), in order, in the zeros of \(\bs m\). Then \((R, \circ)\) is a positive semigroup whose associated partial order is \(\le_0\).
First we show that \((R, \circ)\) is a positive semigroup:
Next we show that the partial order associated with \((R, \circ)\) is the partial order \(\le_0\) in definition . Suppose first that \(\bs m = (m_i: i \in I), \, \bs l = (l_i: i \in I) \in R\) and let \(\bs n = (n_i: i \in I) = \bs m \circ \bs l\) By the very definition of the operation, if \(m_i \gt 0\) then \(n_i = m_i\) and hence \(\bs m \le_0 \bs n\). Conversely, suppose that \(\bs m, \, \bs n \in R\) and \(\bs m \le_0 \bs n\).Let \(\bs l\) be the sequence of values of \(\bs n\) corresponding to the zeros of \(\bs m\), but re-indexed by \(I\). Then again by definition, \(\bs m \circ \bs l = \bs n\).