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\) are below 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. For a reference, see for example the book by Knopfmacher. The division symbol \(|\) is often used for the partial order relation in positive 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\}\) is 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 fpr 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 b) = 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(b) = 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)\] 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\]
An arithmetic semigroup \((S, \cdot)\) usually has a norm function, and this function provides a structure that goes beyond the sequence of prime exponents. Of course, the results in this section could be formulated in terms of the other two semigroups, but that is not usually done. Here is the definition:
A norm \(|\cdot|\) for \((S, \cdot)\) is a function from \(S\) to \((0, \infty)\) with the following properties:
By (c), the norm is completely multiplicative.
If \(x = \prod_{i \in I} i^{n_i} \in S\) where \(\bs n = (n_i: i \in I) \in R\) then \[ |x| = \prod_{i \in I} |i|^{n_i} \]
In particular from (b) of and , \(|x| \gt 1\) if \(x \in S_+\). Conversely, it's easy to construct a norm on an arithmetic semigroup: let \(|e| = 1\) and define \(|i| \gt 1\) arbitrarily for \(i \in I\). Then define \(|x|\) by for \(x \in S_+ - I\). The function \(|\cdot|\) satisfies parts (a), (b), and (c) of the definition. If \(I\) is finite, part (d) is satisfied automatically. If \(I\) is infinite, (d) is satisfied for example if \(\prod_{i \in I} |i| = \infty\).
For the standard arithmetic semigroup \((\N_+, \cdot)\) in example , the standard norm is the identity function on \(\N_+\) so that \(|x| = x\) for \(x \in \N_+\). Hence \(N(t) = \lfloor t \rfloor\) for \(t \in (0, \infty)\).
The norm is an essential part of \((\N_+, \cdot)\) so that the actual positive integers, and not just the sequence of the prime exponents, are part of the theory.
The arithmetic semigroup \((S, \cdot)\) with a single prime element \(i\) in example is isomorphic to \((\N, +)\). Any function of the form \(i^n \mapsto c^n\) with \(c \in (1, \infty)\) is a norm for \((S, \cdot)\). For this norm, \(N(t) \le | \ln t / \ln c |\) for \(t \in (0, \infty)\).
For the following definitions, we assume that the arithmetic semigroup \((S, \cdot)\) has a fixed norm.
Suppose that \(f\) is an arithmetic function for \((S, \cdot)\). The corresponding Dirichlet series \(F\) is the formal series defined by by \[F(t) = \sum_{x \in S} \frac{f(x)}{|x|^t}\] If the series converges for some \(t \in (0, \infty)\), then the series converges for \(t\) in an interval of the form \((t_0, \infty)\).
The Dirichlet series corresponding to the constant function \(1\) is the the zeta function: \[\zeta(t) = \sum_{x \in S} \frac{1}{|x|^t}\]
These definitions are most important for the standard arithmetic semigroup in example .
Coonsider the standard arithmetic semigroup \((\N_+, \cdot)\) with the standard norm.
For \((\N_+, \cdot)\) there is a one-to-one correspondence between the arithmetic function \(f\) and the series function \(F\). Given \(f\), we compute \(F\), of course, as the series in the definition. Conversely, given \(F\) defined on the interval of convergence \((t_0, \infty)\), we can recover the arithmetic function \(f\) (see the paper by Alan Gut).
An arithmetic semigroup \((S, \cdot)\) with a single prime element \(i\) can be identified with the standard discrete semigroup \((\N, +)\) as in example . Suppose that the norm is given by \(|n| = c^n\) where \(c \in (1, \infty)\).
We will need one more special function.
The Mangoldt function \(\Lambda\) is the arithmetic function on \((S, \cdot)\) defined as follows: \[\Lambda(x) = \begin{cases} \ln |i| &\text{ if } x = i^n \text{ for some } i \in I \text{ and } n \in \N_+ \\ 0 &\text{ otherwise} \end{cases}\]