Abstract prime number theory

In various branches of number theory, abstract algebra, combinatorics, and elsewhere in mathematics, it is sometimes possible and convenient to formulate a variety of enumeration or counting questions in a unified way in terms of the concept of an arithmetical semi-group $G$ (cf. Abstract analytic number theory; Semi-group).

Special interest then attaches to the basic counting functions (for $n \in \mathbf{Z}$): $$ G(n) = \# \{ a \in G : |a| = n \} \ , $$ $$ P(n) = \# \{ p \in P : |p| = n \} \; $$ where $P$ denotes the set of "prime" elements in $G$.

If one of the functions $G(n)$,$P(n)$ has a certain type of asymptotic behaviour, it may then be possible to deduce that of the other by a uniform method of derivation. Theorems of the latter kind may then be referred to as abstract prime number theorems within the context considered.

Some concrete examples are given below.

Types of arithmetical semi-groups.

Axiom $A$

The prototype of all arithmetical semi-groups is of course the multiplicative semi-group $\mathbf{N}$ of all positive integers $\{ 1,2,3, \ldots \}$, with its subset $P_{\mathbf{N}}$ of all rational prime numbers $\{ 2,3,5,7,\ldots \}$. Here one may define the norm of an integer $|n|$ to be $|n| = $, so that the number $\mathbf{N}(n) = 1$ for $n \ge 1$.

Although $\mathbf{N}(n)$ would be too trivial to mention if one were not interested in a wider arithmetical theory, the corresponding function $P_{\mathbf{N}}(n)$ remains mysterious to this day (as of 2000). The asymptotic behaviour of $\pi(x) = \sum_{n \le x} P_{\mathbf{N}}(n)$ for large $x$ forms the content of the famous prime number theorem, which states that

$$\pi(x) \sim \frac{x}{\log x} \text{ as } x \to \infty$$ (cf. also de la Vallée-Poussin theorem).

A suitably generalized form of this theorem holds for many other naturally-occurring arithmetical semi-groups. For example, it is true for the multiplicative semi-group $G_K$ of all non-zero ideals in the ring $R=R(K)$ of all algebraic integers in a given algebraic number field $K$, with $|I| = \mathrm{card}(R/I)$ for any non-zero ideal $I$ in $R$. Here, the prime ideals act as prime elements of the semi-group $G_K$, and both the corresponding functions $G_K(n)$, $P_K(n)$ are non-trivial to estimate in general. However, Landau's prime ideal theorem establishes that

$$\pi_K(x) = \sum_{n \le x} P_K(n) \sim \frac{x}{\log x} \text{ as } x \to \infty,$$ while classical theorems of Weber and Landau yield

$$\sum_{n \le x} G_K(n) = A_K x + O(x^{\eta_K}) \text{ as } x \to \infty$$ for explicit positive constants $A_K$ and $\eta_K < 1$.

Similar types of asymptotic behaviour are displayed by many quite different types of concrete arithmetical semi-groups (cf. [a4], Part II, where these are referred to as "semi-groups satisfying axiom A" ).

Axiom $A ^ { \# }$.

For a simple but nevertheless interesting example of an additive arithmetical semi-group, one may consider the multiplicative semi-group $G_q$ of all monic polynomials in one indeterminate $X$ over a finite field $\mathbf{F} _ { q }$ with $q$ elements, with $\partial ( a ) = \operatorname { deg } ( a )$ and set $P _ { q }$ of prime elements represented by the irreducible polynomials (cf. also Irreducible polynomial). Here, $G _ { q } ^ { \# } ( n ) = q ^ { n }$, and it is a well-known theorem that

\begin{equation*} P _ { q } ^\# ( n ) = \frac { 1 } { n } \sum _ { r | n } \mu ( r ) q ^ { n / r }, \end{equation*}

where $\mu$ is the classical Möbius function on $\mathbf{N}$.

Up to isomorphism, $G_q$ is the simplest special case of the semi-group $G _ { R }$ of all non-zero ideals in the ring $R = R ( K )$ of all integral functions in an algebraic function field $K$ in one variable $X$ over $\mathbf{F} _ { q }$. Here, the set $P _ { R }$ of prime ideals in $R$ acts as the set of prime elements, and the degree $\partial ( I )$ is defined by $q ^ { \partial ( I) } = \operatorname { card } ( R / I )$. The case $K = \mathbf{F} _ { q } ( x )$ leads back to $G_q$, and in general it can be proved that

\begin{equation*} G _ { R } ^ { \# } ( n ) = A _ { R } q ^ { n } + O ( 1 ) \text { as } n \rightarrow \infty, \end{equation*}

and

\begin{equation*} P _ { R } ^ { \# } ( n ) = \frac { 1 } { n } q ^ { n } + O \left( \frac { 1 } { n } q ^ { n / 2 } \right) \text { as } n \rightarrow \infty, \end{equation*}

where $A _ { R }$ is a positive constant.

Similar examples arise if one considers the semi-group $G _ { K }$ of all "integral divisors" of $K$, instead of $G _ { R }$. Related types of asymptotic behaviour are also displayed by many quite different kinds of concrete additive arithmetical semi-groups (cf. [a6], [a11], where these are referred to as "semi-groups satisfying axiom A#" ).

Axioms ${\cal G} _ { 1 }$ and $\mathcal{G} _ { \lambda }$.

Yet another natural class of additive arithmetical semi-groups $G$ is provided by those satisfying axiom ${\cal G}_{1}$: "Almost all" elements of $G$ are prime, in the sense that $G^{\#} (n) > 0$ for sufficiently large $n$, and $P^{\#} (n) \sim G ^ { \# } ( n )$ as $n \rightarrow \infty$, i.e.,

\begin{equation*} \operatorname { lim } _ { n \rightarrow \infty } \frac { P ^ { \# } ( n ) } { G ^ { \# } ( n ) } = 1. \end{equation*}

Examples of this slightly unexpected property are provided by various classes $\Gamma$ of finite graphs with the property that a graph $H$ lies in $\Gamma$ if and only if each connected component of $H$ lies in $\Gamma$. Let the disjoint union $\cup _ { d }$ be used as follows to define a "product" operation on the set $G _ { \Gamma }$ of all unlabelled graphs (i.e., isomorphism classes $\overline { H }$ of graphs $H$) in $\Gamma$: $\overline { H _ { 1 } } \cdot \overline { H _ { 2 } } = \overline { H _ { 1 } \cup _ { d } H _ { 2 } }$. Also, let $\partial ( \overline { H } ) = \text{# vertices in} \ H$. Then $G _ { \Gamma }$ becomes an additive arithmetical semi-group.

For some classes $\Gamma$, $G _ { \Gamma }$ satisfies axiom ${\cal G} _ { 1 }$, and this is also true for the quite different multiplicative semi-group $G _ { q , k }$ formed by all associate-classes of non-zero polynomials in $k > 1$ indeterminates $X _ { 1 } , \ldots , X _ { k }$ over a finite field $\mathbf{F} _ { q }$ (cf. [a5]).

Ignoring the corresponding limit zero which occurs under axiom $A ^ { \# }$, and also under axiom $A$ (in a certain sense), R. Warlimont [a10] raised the interesting question as to whether there are any "natural" instances of additive arithmetical semi-groups $G$ satisfying axiom $\mathcal{G} _ { \lambda }$: There exists a $0 < \lambda < 1$ with

\begin{equation*} \operatorname { lim } _ { n \rightarrow \infty } \frac { P ^ { \# } ( n ) } { G ^ { \# } ( n ) } = \lambda. \end{equation*}

In the next section, a variety of "natural" examples of semi-groups satisfying axiom $\mathcal{G} _ { \lambda }$ for various values of $\lambda$ in $( 0,1 )$ will be given.

Axiom $\Phi$.

The concrete examples described below provide a variety of natural illustrations of additive arithmetical semi-groups $G$ with the following property (axiom $\Phi$): There exist real constants $C > 0$, $q > 1$, $\alpha > 1$, depending on $G$, such that

\begin{equation*} P ^ { \# } ( n ) \sim C q ^ { n } n ^ { - \alpha } \;\text { as } n \rightarrow \infty. \end{equation*}

Under these assumptions one has (cf. [a3]) an abstract (inverse) prime number theorem: If $G$ is an additive arithmetical semi-group satisfying axiom $\Phi$, then

\begin{equation*} G ^ { \# } ( n ) \sim C Z _ { G } ( q ^ { - 1 } ) q ^ { n } n ^ { - \alpha } \text { as }\, n \rightarrow \infty , \end{equation*}

where $Z _ { G } ( y ) = \sum _ { r = 0 } ^ { \infty } G ^ { \# } ( r ) y ^ { r }$.

It follows that if $G$ satisfies axiom $\Phi$, then $G$ also satisfies axiom $\mathcal{G} _ { \lambda }$, for $\lambda = \lambda _ { G } = 1 / Z _ { G } ( q ^ { - 1 } )$.

The set $\mathcal{F}$ of all unlabelled (i.e., isomorphism classes of) finite forests forms an additive arithmetical semi-group, whose prime elements are the unlabelled trees. A famous theorem of R. Otter [a7] states that the total number $\mathcal{T} ^ { \# } ( n )$ of unlabelled trees with $n$ vertices satisfies

\begin{equation*} {\cal T} ^ { \# } ( n ) \sim C _ { 0 } q _ { 0 } ^ { n } n ^ { - 5 / 2 } \text { as } n \rightarrow \infty , \end{equation*}

where $C _ { 0 }$ and $q_0$ are explicitly described positive constants ($q_0 > 1$). E.M. Palmer and A.J. Schwenk [a8] estimated the corresponding total number ${\cal F} ^ { \# } ( n )$ of all unlabelled forests with $n$ vertices. They showed that

\begin{equation*} \mathcal{F} ^ { \# } ( n ) \sim K _ { 0 } C _ { 0 } q _ { 0 } ^ { n } n ^ { - 5 / 2 } \text { as } \ n \rightarrow \infty, \end{equation*}

where $K_{0} > 1$ is also an explicitly described constant.

This and various other families of trees provide "natural" examples of Warlimont's axiom $\mathcal{G} _ { \lambda }$ as well as axiom $\Phi$.

As considered by P. Hanlon [a2], an interval graph is defined mathematically as a finite graph $H$ whose vertices are in one-to-one correspondence with a set of real closed intervals in such a way that two vertices are joined by an edge in $H$ if and only if their corresponding intervals intersect non-trivially. If all the intervals have length one, $H$ is called a unit-interval graph; if $H$ is connected, and no two adjacent vertices have exactly the same set of neighbouring vertices, $H$ is called reduced.

Based on the asymptotic estimates of Hanlon [a2] one may then deduce that the semi-group $\cal I$ corresponding to all unit-interval graphs satisfies axiom $\Phi$.

Substantial advances have occurred in recent years (as of 2000) concerning the asymptotic enumeration of the non-isomorphic (combinatorially distinct) convex $3$-polyhedra (or 3-polytopes).

Indeed, let $\mathcal{P} _ { E } ^ { \# } ( n )$ denote the total number of combinatorially distinct convex $3$-polyhedra with $n$ edges (cf. also Polyhedron). L.B. Richmond and N.C. Wormald [a9] showed that

\begin{equation*} {\cal P} _ { \text{E} } ^ { \# } ( n ) \sim \frac { 1 } { 468 \sqrt { \pi } } 4 ^ { n } n ^ { - 7 / 2 } \text { as } n\rightarrow \infty. \end{equation*}

Soon after that, E.A. Bender and Wormald [a1] considered the corresponding numbers $\mathcal{P} _ { V } ^ { \# } ( n )$, $\mathcal{P} _ { \text{F} } ^ { \# } ( n )$ when $n$ now represents the number of vertices, respectively faces, and derived a similar asymptotic estimate.

Let $\mathcal{S} _ { \text{E} }$, $S _ { \text{V} }$, $\mathcal{S} _ { \text{F} }$ denote the additive arithmetical semi-groups which arise from the set $\mathcal{S}$ of all combinatorial equivalence classes of the above special $3$-dimensional simplicial complexes.

Then it follows from the abstract inverse prime number theorem above that $\mathcal{S} _ { \text{E} }$, $S _ { \text{V} }$ and $\mathcal{S} _ { \text{F} }$ are further natural examples of semi-groups satisfying axiom $\Phi$.

References

[a1]	E.A. Bender, N.C. Wormald, "Almost all convex polyhedra are asymmetric" Canad. J. Math. , 27 (1985) pp. 854–871
[a2]	P. Hanlon, "Counting interval graphs" Trans. Amer. Math. Soc. , 272 (1982) pp. 383–426
[a3]	A. Knopfmacher, J. Knopfmacher, "Arithmetical semi-groups related to trees and polyhedra" J. Combin. Th. , 86 (1999) pp. 85–102
[a4]	J. Knopfmacher, "Abstract analytic number theory" , North-Holland (1975) (Reprinted: Dover, 1990)
[a5]	J. Knopfmacher, "Arithmetical properties of finite graphs and polynomials" J. Combin. Th. , 20 (1976) pp. 205–215
[a6]	J. Knopfmacher, "Analytic arithmetic of algebraic function fields" , M. Dekker (1979)
[a7]	R. Otter, "The number of trees" Ann. of Math. , 49 (1948) pp. 583–599
[a8]	E.M. Palmer, A.J. Schwenk, "On the number of trees in a random forest" J. Combin. Th. B , 27 (1979) pp. 109–121
[a9]	L.B. Richmond, N.C. Wormald, "The asymptotic number of convex polyhedra" Trans. Amer. Math. Soc. , 273 (1982) pp. 721–735
[a10]	R. Warlimont, "A relationship between two sequences and arithmetical semi-groups" Math. Nachr. , 164 (1993) pp. 201–217
[a11]	J. Knopfmacher, W.-B. Zhang, "Number theory arising from finite fields, analytic and probabilistic theory" , M. Dekker (2001)