View source for Abstract prime number theory

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 122 formulas, 122 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
{{TEX|part}}

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|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|algebraic number]] field $K$, with $|I| = \mathrm{card}(R/I)$ for any non-zero
[[Ideal|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.
[[#References|[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|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|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|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|ring]] $R = R ( K )$ of all integral functions in an [[Algebraic function|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. [[#References|[a6]]], [[#References|[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|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. [[#References|[a5]]]).

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