# Abstract prime number theory

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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$.

How to Cite This Entry:
Abstract prime number theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Abstract_prime_number_theory&oldid=50434
This article was adapted from an original article by John Knopfmacher (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article