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 would be too trivial to mention if one were not interested in a wider arithmetical theory, the corresponding function remains mysterious to this day (as of 2000). The asymptotic behaviour of for large forms the content of the famous prime number theorem, which states that

(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 of all non-zero ideals in the ring of all algebraic integers in a given algebraic number field , with for any non-zero ideal in . Here, the prime ideals act as prime elements of the semi-group , and both the corresponding functions , are non-trivial to estimate in general. However, Landau's prime ideal theorem establishes that

while classical theorems of Weber and Landau yield

for explicit positive constants and .

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 .

For a simple but nevertheless interesting example of an additive arithmetical semi-group, one may consider the multiplicative semi-group of all monic polynomials in one indeterminate over a finite field with elements, with and set of prime elements represented by the irreducible polynomials (cf. also Irreducible polynomial). Here, , and it is a well-known theorem that

where is the classical Möbius function on .

Up to isomorphism, is the simplest special case of the semi-group of all non-zero ideals in the ring of all integral functions in an algebraic function field in one variable over . Here, the set of prime ideals in acts as the set of prime elements, and the degree is defined by . The case leads back to , and in general it can be proved that

and

where is a positive constant.

Similar examples arise if one considers the semi-group of all "integral divisors" of , instead of . 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 and .

Yet another natural class of additive arithmetical semi-groups is provided by those satisfying axiom : "Almost all" elements of are prime, in the sense that for sufficiently large , and as , i.e.,

Examples of this slightly unexpected property are provided by various classes of finite graphs with the property that a graph lies in if and only if each connected component of lies in . Let the disjoint union be used as follows to define a "product" operation on the set of all unlabelled graphs (i.e., isomorphism classes of graphs ) in : . Also, let . Then becomes an additive arithmetical semi-group.

For some classes , satisfies axiom , and this is also true for the quite different multiplicative semi-group formed by all associate-classes of non-zero polynomials in indeterminates over a finite field (cf. [a5]).

Ignoring the corresponding limit zero which occurs under axiom , and also under axiom (in a certain sense), R. Warlimont [a10] raised the interesting question as to whether there are any "natural" instances of additive arithmetical semi-groups satisfying axiom : There exists a with

In the next section, a variety of "natural" examples of semi-groups satisfying axiom for various values of in will be given.

Axiom .

The concrete examples described below provide a variety of natural illustrations of additive arithmetical semi-groups with the following property (axiom ): There exist real constants , , , depending on , such that

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

where .

It follows that if satisfies axiom , then also satisfies axiom , for .

The set 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 of unlabelled trees with vertices satisfies

where and are explicitly described positive constants (). E.M. Palmer and A.J. Schwenk [a8] estimated the corresponding total number of all unlabelled forests with vertices. They showed that

where is also an explicitly described constant.

This and various other families of trees provide "natural" examples of Warlimont's axiom as well as axiom .

As considered by P. Hanlon [a2], an interval graph is defined mathematically as a finite graph 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 if and only if their corresponding intervals intersect non-trivially. If all the intervals have length one, is called a unit-interval graph; if is connected, and no two adjacent vertices have exactly the same set of neighbouring vertices, is called reduced.

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

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

Indeed, let denote the total number of combinatorially distinct convex -polyhedra with edges (cf. also Polyhedron). L.B. Richmond and N.C. Wormald [a9] showed that

Soon after that, E.A. Bender and Wormald [a1] considered the corresponding numbers , when now represents the number of vertices, respectively faces, and derived a similar asymptotic estimate.

Let , , denote the additive arithmetical semi-groups which arise from the set of all combinatorial equivalence classes of the above special -dimensional simplicial complexes.

Then it follows from the abstract inverse prime number theorem above that , and are further natural examples of semi-groups satisfying axiom .

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)