Namespaces
Variants
Actions

Difference between revisions of "Abstract prime number theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX partially done)
m (gt to >)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--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}}
 
{{TEX|part}}
  
Line 22: Line 30:
 
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$.
 
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 <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
+
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
  
<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>
+
$$\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]]).
  
(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
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
+
[[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
 
 
<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>
 
  
 +
$$\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
 
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>
+
$$\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$.
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" ).
+
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" />.===
+
===Axiom $A ^ { \# }$.===
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
+
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
  
<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>
+
\begin{equation*} P _ { q } ^\#  ( n ) = \frac { 1 } { n } \sum _ { r | n } \mu ( r ) q ^ { n / r }, \end{equation*}
  
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" />.
+
where $\mu$ is the classical [[Möbius function|Möbius function]] on $\mathbf{N}$.
  
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
+
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
  
<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>
+
\begin{equation*} G _ { R } ^ { \# } ( n ) = A _ { R } q ^ { n } + O ( 1 ) \text { as } n \rightarrow \infty, \end{equation*}
  
 
and
 
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>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a13006061.png" /> is a positive constant.
+
where $A _ { R }$ 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#" ).
+
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 <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" />.===
+
===Axioms ${\cal G} _ { 1 }$ and $\mathcal{G} _ { \lambda }$.===
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.,
+
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.,
  
<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>
+
\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 <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.
+
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 <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]]]).
+
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 <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
+
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
  
<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>
+
\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 <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.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060106.png" />.===
+
===Axiom $\Phi$.===
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
+
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
  
<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>
+
\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 <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
+
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
  
<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>
+
\begin{equation*} G ^ { \# } ( n ) \sim C Z _ { G } ( q ^ { - 1 } ) q ^ { n } n ^ { - \alpha } \text { as }\, n \rightarrow \infty , \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060118.png" />.
+
where $Z _ { G } ( y ) = \sum _ { r = 0 } ^ { \infty } G ^ { \# } ( r ) y ^ { r }$.
  
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" />.
+
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 <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
+
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
  
<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>
+
\begin{equation*} {\cal T} ^ { \# } ( n ) \sim C _ { 0 } q _ { 0 } ^ { n } n ^ { - 5 / 2 } \text { as } n \rightarrow \infty , \end{equation*}
  
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
+
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
  
<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>
+
\begin{equation*} \mathcal{F} ^ { \# } ( n ) \sim K _ { 0 } C _ { 0 } q _ { 0 } ^ { n } n ^ { - 5 / 2 } \text { as } \ n \rightarrow \infty, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060134.png" /> is also an explicitly described constant.
+
where $K_{0} > 1$ 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" />.
+
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 <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.
+
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 <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" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130060/a130060145.png" />-polyhedra (or 3-polytopes).
+
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 <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
+
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
  
<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>
+
\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 <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.
+
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 <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.
+
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 <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" />.
+
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====
 
====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>
+
<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>

Latest revision as of 09:45, 11 November 2023


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