View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300601.png" /> (cf. [[Abstract analytic number theory|Abstract analytic number theory]]; [[Semi-group|Semi-group]]).

Special interest then attaches to the basic counting functions (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300602.png" />):

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300603.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300604.png" /></td> </tr></table>

(here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300605.png" /> denotes the set of  "prime"  elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300606.png" />).

If one of the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300607.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300608.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a1300609.png" />.===
The prototype of all arithmetical semi-groups is of course the multiplicative semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006010.png" /> of all positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006011.png" />, with its subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006012.png" /> of all rational prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006013.png" />. Here one may define the norm of an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006014.png" /> to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006015.png" />, so that the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006016.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006017.png" />.

Although <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006018.png" /> would be too trivial to mention if one were not interested in a wider arithmetical theory, the corresponding function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006019.png" /> remains mysterious to this day (as of 2000). The asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006020.png" /> for large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006021.png" /> forms the content of the famous prime number theorem, which states that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006022.png" /></td> </tr></table>

(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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006023.png" /> of all non-zero ideals in the ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006024.png" /> of all algebraic integers in a given [[Algebraic number|algebraic number]] field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006025.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006026.png" /> for any non-zero [[Ideal|ideal]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006027.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006028.png" />. Here, the prime ideals act as prime elements of the semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006029.png" />, and both the corresponding functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006031.png" /> are non-trivial to estimate in general. However, Landau's prime ideal theorem establishes that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006032.png" /></td> </tr></table>

while classical theorems of Weber and Landau yield

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006033.png" /></td> </tr></table>

for explicit positive constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006035.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006036.png" />.===
For a simple but nevertheless interesting example of an additive arithmetical semi-group, one may consider the multiplicative semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006037.png" /> of all monic polynomials in one indeterminate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006038.png" /> over a [[Finite field|finite field]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006039.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006040.png" /> elements, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006041.png" /> and set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006042.png" /> of prime elements represented by the irreducible polynomials (cf. also [[Irreducible polynomial|Irreducible polynomial]]). Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006043.png" />, and it is a well-known theorem that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006044.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006045.png" /> is the classical [[Möbius function|Möbius function]] on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006046.png" />.

Up to isomorphism, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006047.png" /> is the simplest special case of the semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006048.png" /> of all non-zero ideals in the [[Ring|ring]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006049.png" /> of all integral functions in an [[Algebraic function|algebraic function]] field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006050.png" /> in one variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006051.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006052.png" />. Here, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006053.png" /> of prime ideals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006054.png" /> acts as the set of prime elements, and the degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006055.png" /> is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006056.png" />. The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006057.png" /> leads back to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006058.png" />, and in general it can be proved that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006059.png" /></td> </tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006060.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006061.png" /> is a positive constant.

Similar examples arise if one considers the semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006062.png" /> of all  "integral divisors"  of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006063.png" />, instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006064.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006065.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006066.png" />.===
Yet another natural class of additive arithmetical semi-groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006067.png" /> is provided by those satisfying axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006069.png" />:  "Almost all"  elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006070.png" /> are prime, in the sense that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006071.png" /> for sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006072.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006073.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006074.png" />, i.e.,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006075.png" /></td> </tr></table>

Examples of this slightly unexpected property are provided by various classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006076.png" /> of finite graphs with the property that a [[Graph|graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006077.png" /> lies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006078.png" /> if and only if each connected component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006079.png" /> lies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006080.png" />. Let the disjoint union <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006081.png" /> be used as follows to define a  "product"  operation on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006082.png" /> of all unlabelled graphs (i.e., isomorphism classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006083.png" /> of graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006084.png" />) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006085.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006086.png" />. Also, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006087.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006088.png" /> becomes an additive arithmetical semi-group.

For some classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006089.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006090.png" /> satisfies axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006091.png" />, and this is also true for the quite different multiplicative semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006092.png" /> formed by all associate-classes of non-zero polynomials in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006093.png" /> indeterminates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006094.png" /> over a finite field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006095.png" /> (cf. [[#References|[a5]]]).

Ignoring the corresponding limit zero which occurs under axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006096.png" />, and also under axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006097.png" /> (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006098.png" /> satisfying axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060100.png" />: There exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060101.png" /> with

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060102.png" /></td> </tr></table>

In the next section, a variety of  "natural"  examples of semi-groups satisfying axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060103.png" /> for various values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060104.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060105.png" /> will be given.

===Axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060106.png" />.===
The concrete examples described below provide a variety of natural illustrations of additive arithmetical semi-groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060107.png" /> with the following property (axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060109.png" />): There exist real constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060110.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060111.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060112.png" />, depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060113.png" />, such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060114.png" /></td> </tr></table>

Under these assumptions one has (cf. [[#References|[a3]]]) an abstract (inverse) prime number theorem: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060115.png" /> is an additive arithmetical semi-group satisfying axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060116.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060117.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060118.png" />.

It follows that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060119.png" /> satisfies axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060120.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060121.png" /> also satisfies axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060122.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060123.png" />.

The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060124.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060125.png" /> of unlabelled trees with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060126.png" /> vertices satisfies

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060127.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060128.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060129.png" /> are explicitly described positive constants (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060130.png" />). E.M. Palmer and A.J. Schwenk [[#References|[a8]]] estimated the corresponding total number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060131.png" /> of all unlabelled forests with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060132.png" /> vertices. They showed that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060133.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060134.png" /> is also an explicitly described constant.

This and various other families of trees provide  "natural"  examples of Warlimont's axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060136.png" /> as well as axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060137.png" />.

As considered by P. Hanlon [[#References|[a2]]], an interval graph is defined mathematically as a finite graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060138.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060139.png" /> if and only if their corresponding intervals intersect non-trivially. If all the intervals have length one, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060140.png" /> is called a unit-interval graph; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060141.png" /> is connected, and no two adjacent vertices have exactly the same set of neighbouring vertices, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060142.png" /> is called reduced.

Based on the asymptotic estimates of Hanlon [[#References|[a2]]] one may then deduce that the semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060143.png" /> corresponding to all unit-interval graphs satisfies axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060144.png" />.

Substantial advances have occurred in recent years (as of 2000) concerning the asymptotic enumeration of the non-isomorphic (combinatorially distinct) convex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060145.png" />-polyhedra (or 3-polytopes).

Indeed, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060146.png" /> denote the total number of combinatorially distinct convex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060147.png" />-polyhedra with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060148.png" /> edges (cf. also [[Polyhedron|Polyhedron]]). L.B. Richmond and N.C. Wormald [[#References|[a9]]] showed that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060149.png" /></td> </tr></table>

Soon after that, E.A. Bender and Wormald [[#References|[a1]]] considered the corresponding numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060150.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060151.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060152.png" /> now represents the number of vertices, respectively faces, and derived a similar asymptotic estimate.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060153.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060154.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060155.png" /> denote the additive arithmetical semi-groups which arise from the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060156.png" /> of all combinatorial equivalence classes of the above special <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060157.png" />-dimensional simplicial complexes.

Then it follows from the abstract inverse prime number theorem above that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060158.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060159.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060160.png" /> are further natural examples of semi-groups satisfying axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060161.png" />.

====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>