Difference between revisions of "Abstract prime number theory"
(Importing text file) |
(TeX partially done) |
||
| Line 1: | Line 1: | ||
| − | + | {{TEX|part}} | |
| − | + | In various branches of number theory, abstract algebra, combinatorics, and elsewhere in mathematics, it is sometimes possible and convenient to formulate a variety of enumeration or counting questions in a unified way in terms of the concept of an arithmetical semi-group $G$ (cf. [[Abstract analytic number theory]]; [[Semi-group]]). | |
| − | + | Special interest then attaches to the basic counting functions (for $n \in \mathbf{Z}$): | |
| + | $$ | ||
| + | G(n) = \# \{ a \in G : |a| = n \} \ , | ||
| + | $$ | ||
| + | $$ | ||
| + | P(n) = \# \{ p \in P : |p| = n \} \; | ||
| + | $$ | ||
| + | where $P$ denotes the set of "prime" elements in $G$. | ||
| − | + | If one of the functions $G(n)$,$P(n)$ has a certain type of asymptotic behaviour, it may then be possible to deduce that of the other by a uniform method of derivation. Theorems of the latter kind may then be referred to as abstract prime number theorems within the context considered. | |
| − | |||
| − | |||
| − | |||
| − | If one of the functions | ||
Some concrete examples are given below. | Some concrete examples are given below. | ||
| Line 16: | Line 19: | ||
| − | ===Axiom | + | ===Axiom $A$=== |
| − | The prototype of all arithmetical semi-groups is of course the multiplicative semi-group | + | 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 <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 | ||
Revision as of 08:03, 10 January 2016
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) |
Abstract prime number theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Abstract_prime_number_theory&oldid=37430