Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-6"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎Recurrent word: Lothaire (2002))
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Recurrent word=
+
=Semigroup action=
An infinite word over an alphabet $A$ (finite or infinite) in which every factor occurs infinitely often.  It is sufficient for a one-sided infinite word (element of $A^{\mathbf{N}}$) to be recurrent that every prefix occurs at least once again.
+
''of a semigroup $S$ on a set $X$''
  
A word is uniformly recurrent if for every factor $f$ there is an $N = N(f)$ such that $f$ occurs in every factor of length $N$.   
+
A map from $X \times S \rightarrow X$, written $(x,s)$ or $x^s$ satisfying
 +
$$
 +
(x,st) = ((x,s),t)\ .
 +
$$
 +
For given $s$, the map $\rho_s : x \mapsto (x,s)$ is a [[transformation]] of $X$.  The map $s \mapsto \rho_s$ is a semigroup morphism $\rho : S \rightarrow T_X$ where $T_X$ is the [[transformation semi-group]] on $X$: conversely, every such homomorphism gives rise to an action $(x,s) \mapsto (x)\rho_s$.  If the homomorphism $\rho$ is injective the action is ''faithful'': $S$ may be regarded as a subsemigroup of $T_X$.   
  
The [[Thue–Morse sequence]] is uniformly recurrent.
+
If $S$ is a [[monoid]] with [[identity element]] $1_S$, the action is ''unital'' if in addition
 +
$$
 +
(x,1_S) = x
 +
$$
 +
for all $x \in X$.  In this case the map$s \mapsto \rho_s$ is a monoid morphism.
  
====References====
+
==Polygon (over a monoid)==
* Lothaire, M. "Algebraic Combinatorics on Words", Encyclopedia of Mathematics and its Applications '''90''', Cambridge University Press (2002)  ISBN 0-521-81220-8.  {{ZBL|1001.68093}}
+
''$R$-polygon, operand''
* Sapir, Mark V. "Combinatorial algebra: syntax and semantics" with contributions by Victor S. Guba and Mikhail V. Volkov. Springer Monographs in Mathematics. Springer  (2014) SBN 978-3-319-08030-7 {{ZBL|1319.05001}}
 
  
=Complexity function=
+
A non-empty set with a [[monoid]] of operators. More precisely, a non-empty set $A$ is called a left polygon over a monoid $R$ if for any $\lambda \in R$ and $a \in A$ the product $\lambda a \in A$ is defined, such that
''of a word $w$''
+
$$
 
+
\lambda (\mu a) = (\lambda\mu) a
The complexity function of a [[word]] $w$ (finite, infinite or bi-infinite) over a finite alphabet $A$ is the function $p_w(n)$ that counts the number of distinct factors (substrings of consecutive symbols) of length $n$ in $w$. More generally, the complexity function of a language, a set of finite words over an alphabet, counts the number of distinct words of given length.
+
$$
 +
and
 +
$$
 +
1a = a
 +
$$
 +
for any $\lambda, \mu \in R$, $a \in A$. A right polygon is defined similarly. Specifying an $R$-polygon $A$ is equivalent to specifying a homomorphism $\phi$ from the monoid $R$ into the monoid of mappings of the set $A$ into itself that transforms 1 to the identity mapping. Here $\lambda a = b$ if and only if
 +
$$
 +
\phi(\lambda)a = b \ .
 +
$$
 +
In particular, each non-empty set may be considered as a polygon over the monoid of its mappings into itself. Therefore, polygons are closely related to the representation of semi-groups by transformations: cf. [[Transformation semi-group]].
  
For a string $u$ of length at least $n$ over an alphabet of size $k$ we clearly have
+
If $A$ is a [[universal algebra]] whose signature $\Omega$ contains only unary operations, then $A$ can be converted into a polygon over the free monoid $F$ generated by $\Omega$ by putting
 
$$
 
$$
1 \le p_u(n) \le k^n \ ,
+
f_1 \cdots f_n a = f_1(\cdots(f_n(a)\cdots)
 
$$
 
$$
the bounds being achieved by the constant word and a [[disjunctive word]] (for example, the [[Champernowne word]]) respectively.  For infinite words $u$, we have $p_u(n)$ bounded if $u$ is ultimately periodic (a finite, possibly empty, sequence followed by a finite cycle).  Conversely, if $p_u(n) \le n$ for some $n$, then $u$ is ultimately periodic.
 
  
An '''aperiodic sequence''' is one which is not ultimately periodic. An aperiodic sequence has strictly increasing complexity function (this is the '''Morse–Hedlund theorem'''), so $p_u(n) \ge n+1$.
+
for any $f_i \in \Omega$, $a \in A$. If $\Omega$ is the set of input signals for an automaton having set of states $A$, then $A$ is similarly transformed into an $F$-polygon (cf. [[Automata, algebraic theory of]]).
  
A set$S$ of finite binary words is ''balanced'' if for each $n$ the subset $S_n$ of words of length $n$ has the property that the [[Hamming weight]] of the words in $S_n$ takes at most two distinct values.  A '''balanced sequence''' is one for which the set of factors is balanced. A balanced sequence has complexity function $p(n) \le n+1$.
+
A mapping $\phi$ of an $R$-polygon $A$ into an $R$-polygon $B$ is called a homomorphism if $\phi(\lambda a) = \lambda \phi(a)$ for any $\lambda \in R$ and $a \in A$. For $A=B$ one arrives at the definition of an endomorphism. All endomorphisms of a polygon $A$ form a monoid, and $A$ can be considered as a polygon over it.
  
A [[Sturmian word]] over a binary alphabet is one with complexity function $p(n) = n+1$ A sequence is Sturmian if and only if it is balanced and aperiodic. An example is the [[Fibonacci word]].  More generally, a Sturmian word over an alphaber of size $k$ is one with complexity $p(n) = n+k-1$. An Arnoux-Rauzy word over a ternary alphabet has complexity $2n+1$:  an example is the [[Tribonacci word]].
+
An [[equivalence relation]] $\theta$ on an $R$-polygon $A$ is called a congruence if $(a,b) \in \theta$ implies $\lambda a,\lambda b) \in \theta$ for any $\lambda \in R$. The set of congruence classes of $\theta$ is naturally transformed into an $R$-polygon, called a quotient polygon of the polygon $A$ and denoted by $A/\theta$. If $A$ is a polygon over $R$, then in $R$ one can define a relation $\mathop{Ann} A$ by putting $(\lambda,\mu) \in \mathop{Ann} A$  if $\lambda a = \mu a$ for all $a \in A$. The relation $\mathop{Ann} A$ is a congruence on the monoid $R$, and $A$ is transformed in a natural fashion into a polygon over the quotient monoid $R/\mathop{Ann} A$. If the polygon $A$ arose from a certain automaton, then this transition is equivalent to identifying identically acting sequences of input signals. In universal algebra one considers the usual constructions of direct and subdirect product, but in addition in polygon theory one may consider a [[wreath product]] construction important in the algebraic theory of automata. The free product (or co-product) of polygons coincides with their disjoint union.
  
Let $L$ be a language over an alphabet and define the function $P_L(n)$ of a positive integer $n$ to be the number of different words of length $n$ in $L$ The complexity function of a word is thus the complexity function of the language consisting of the factors of that word.
+
A polygon may be regarded as a non-additive analogue of a module over a ring, which serves as a rich source of problems in the theory of polygons. In particular, a relationship has been established between polygons and radicals in semi-groups (cf. [[Radical in a class of semi-groups]]), and studies have been made on the relation between the properties of a monoid and those of polygons over them. For example, all left $R$-polygons are projective if and only if $R$ is a one-element group, while the injectivity of all polygons over a commutative monoid $R$ is equivalent to the presence in $R$ of a [[zero element]] and the generation of all its ideals by [[idempotent]]s (see [[Homological classification of rings]]).
  
The complexity function of a language is less constrained than that of a word.  For example, it may be bounded but not eventually constant: the complexity function of the [[regular language]] $a(bb)^*a$ takes values 3 and 4 on odd and even $n \ge 2$ respectively.  There is an analogue of the Morse–Hedlund theorem: if the complexity of $L$ satisfies $p_L(n) \le n$ for some $n$, then $p_L$ is bounded and there is a finite language $F$ such that
+
If $R$ is a monoid with zero 0, one can define an $R$-polygon with zero as a [[pointed set]] $A$ which is an $R$-polygon where the distinguished point $u \in A$ satisfies $0a=u$ for all $a\in A$. The theory of polygons with zero has some special features.
$$
 
L \subseteq \{ x y^k z : x,y,z \in F,\ k \in \mathbb{N} \} \ .
 
$$
 
A '''polynomial''' or '''[[sparse language]]''' is one for which the complexity function $p(n)$ is bounded by a fixed power of $n$.  An ''exponential'' language is one for which there exists $k>1$ such that there are infinitely many $n$ for which $p(n) > k^n$.  Words exist with complexity functions having growth intermediate between polynomial and exponential; however, a [[regular language]] is either polynomial or exponential.
 
  
The ''[[topological entropy]]'' of an infinite sequence $u$ is defined by
+
Every polygon can be considered as a [[functor]] from a one-object category into the category of sets.
$$
 
H_{\mathrm{top}}(u) = \lim_{n \rightarrow \infty} \frac{\log p_u(n)}{n \log k} \ .  
 
$$
 
  
The limit exists as the logarithm of the complexity function is a [[subadditive function]]: indeed, $p(m+n) \le p(m) \cdot p(n)$.  Every real number between 0 and 1 occurs as the topological entropy of some sequence, which may be taken to be a [[uniformly recurrent word]] or even uniquely ergodic.
+
In the West, left polygons over a monoid $M$ are usually called $M$-sets; the term  "operand"  is also in use. The category of all $M$-sets ($M$ fixed) forms a [[topos]]; but for this it is essential not to exclude (as above) the empty $M$-set.
  
For $x$ a real number and $b$ an integer $\ge 2$ then the complexity function of $x$ base $b$ is the complexity function $p_{x,b}(n)$ of the sequence of digits of $x$ written in base $b$.
+
Without assuming commutativity as above, the monoids all of whose non-empty left polygons (or, all of whose pointed left polygons) are injective have a few characterizations, which are reviewed in [[#References|[a3]]]. As noted above, there are no non-trivial monoids all of whose left polygons are projective, but the perfect monoids, defined (like perfect rings, cf. [[Perfect ring]]) by every left polygon having a projective covering, are non-trivial; see [[#References|[a1]]], [[#References|[a2]]].
If $x$ is an [[irrational number]] then $p_{x,b}(n) \ge n+1$; if ''x'' is [[rational number|rational]] then $p_{x,b}(n) \le C$ for some constant $C$ depending on $x$ and $b$.  It is conjectured that for algebraic irrational $x$ the complexity is $b^n$ (which would follow if all such numbers were [[Normal number|normal]]) but all that is known in this case is that $p_{x,b}(n)$ grows faster than any linear function of $n$.
 
  
The '''abelian complexity function''' $p^{\text{ab}}(n)$ similarly counts the number of occurrences of distinct factors of given length $n$, where now we identify factors that differ only by a permutation of the positions.  Clearly $p^{\text{ab}}(n) \le p(n)$.  The abelian complexity of a Sturmian sequence satisfies $p^{\text{ab}}(n) = 2$.
+
The terms ''monoid action'' or ''monoid act'', or ''action'' of a monoid on a set are also common, as is ''act'' for the set acted on; see [[#References|[b1]]].
  
 
====References====
 
====References====
* Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. {{ZBL|1086.11015}}
+
<table>
* Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. {{ZBL|1161.68043}
+
<TR><TD valign="top">[1]</TD> <TD valign="top">  M.A. Arbib (ed.) , ''Algebraic theory of machines, languages and semigroups'' , Acad. Press (1968)</TD></TR>
* Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. {{ZBL|1197.68006}}
+
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.H. Clifford,  G.B. Preston,   "Algebraic theory of semi-groups" , '''2''' , Amer. Math. Soc. (1967)</TD></TR>
* Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. {{ZBL|1260.11001}}.
+
<TR><TD valign="top">[3]</TD> <TD valign="top">  L.A. Skornyakov,   "Generalizations of modules" , ''Modules'' , '''3''' , Novosibirsk  (1973)  pp. 22–27  (In Russian)</TD></TR>
* Cassaigne, Julien; Nicolas, François (2010). "Factor complexity". In Berthé, Valérie; Rigo, Michel. Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. pp. 163–247. ISBN 978-0-521-51597-9. {{ZBL|1216.68204}}
+
<TR><TD valign="top">[4]</TD> <TD valign="top">  L.A. Skornyakov,   A.V. Mikhalev,   "Modules"  ''Itogi Nauk. i Tekhn. Alg. Topol. Geom.'' , '''14'''  (1976) pp. 57–190  (In Russian)</TD></TR>
* Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. {{ZBL|1221.68183}}
+
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Fountain,  "Perfect semigroups"  ''Proc. Edinburgh Math. Soc.'' , '''20'''  (1976) pp. 87–93</TD></TR>
* Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. {{ZBL|1014.11015}}
+
<TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Isbell,   "Perfect monoids"  ''Semigroup Forum'' , '''2'''  (1971)  pp. 95–118</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  R.W. Yoh,   "Congruence relations on left canonic semigroups"  ''Semigroup Forum''  (1977) pp. 175–183</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , Acad. Press  (1974)</TD></TR>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev, ''Monoids, Acts and Categories: With Applications to Wreath Products and Graphs'', Walter de Gruyter (2000) ISBN 3110812908</TD></TR>
 +
</table>
  
 
=Density of a sequence=
 
=Density of a sequence=

Latest revision as of 11:10, 25 September 2016

Semigroup action

of a semigroup $S$ on a set $X$

A map from $X \times S \rightarrow X$, written $(x,s)$ or $x^s$ satisfying $$ (x,st) = ((x,s),t)\ . $$ For given $s$, the map $\rho_s : x \mapsto (x,s)$ is a transformation of $X$. The map $s \mapsto \rho_s$ is a semigroup morphism $\rho : S \rightarrow T_X$ where $T_X$ is the transformation semi-group on $X$: conversely, every such homomorphism gives rise to an action $(x,s) \mapsto (x)\rho_s$. If the homomorphism $\rho$ is injective the action is faithful: $S$ may be regarded as a subsemigroup of $T_X$.

If $S$ is a monoid with identity element $1_S$, the action is unital if in addition $$ (x,1_S) = x $$ for all $x \in X$. In this case the map$s \mapsto \rho_s$ is a monoid morphism.

Polygon (over a monoid)

$R$-polygon, operand

A non-empty set with a monoid of operators. More precisely, a non-empty set $A$ is called a left polygon over a monoid $R$ if for any $\lambda \in R$ and $a \in A$ the product $\lambda a \in A$ is defined, such that $$ \lambda (\mu a) = (\lambda\mu) a $$ and $$ 1a = a $$ for any $\lambda, \mu \in R$, $a \in A$. A right polygon is defined similarly. Specifying an $R$-polygon $A$ is equivalent to specifying a homomorphism $\phi$ from the monoid $R$ into the monoid of mappings of the set $A$ into itself that transforms 1 to the identity mapping. Here $\lambda a = b$ if and only if $$ \phi(\lambda)a = b \ . $$ In particular, each non-empty set may be considered as a polygon over the monoid of its mappings into itself. Therefore, polygons are closely related to the representation of semi-groups by transformations: cf. Transformation semi-group.

If $A$ is a universal algebra whose signature $\Omega$ contains only unary operations, then $A$ can be converted into a polygon over the free monoid $F$ generated by $\Omega$ by putting $$ f_1 \cdots f_n a = f_1(\cdots(f_n(a)\cdots) $$

for any $f_i \in \Omega$, $a \in A$. If $\Omega$ is the set of input signals for an automaton having set of states $A$, then $A$ is similarly transformed into an $F$-polygon (cf. Automata, algebraic theory of).

A mapping $\phi$ of an $R$-polygon $A$ into an $R$-polygon $B$ is called a homomorphism if $\phi(\lambda a) = \lambda \phi(a)$ for any $\lambda \in R$ and $a \in A$. For $A=B$ one arrives at the definition of an endomorphism. All endomorphisms of a polygon $A$ form a monoid, and $A$ can be considered as a polygon over it.

An equivalence relation $\theta$ on an $R$-polygon $A$ is called a congruence if $(a,b) \in \theta$ implies $\lambda a,\lambda b) \in \theta$ for any $\lambda \in R$. The set of congruence classes of $\theta$ is naturally transformed into an $R$-polygon, called a quotient polygon of the polygon $A$ and denoted by $A/\theta$. If $A$ is a polygon over $R$, then in $R$ one can define a relation $\mathop{Ann} A$ by putting $(\lambda,\mu) \in \mathop{Ann} A$ if $\lambda a = \mu a$ for all $a \in A$. The relation $\mathop{Ann} A$ is a congruence on the monoid $R$, and $A$ is transformed in a natural fashion into a polygon over the quotient monoid $R/\mathop{Ann} A$. If the polygon $A$ arose from a certain automaton, then this transition is equivalent to identifying identically acting sequences of input signals. In universal algebra one considers the usual constructions of direct and subdirect product, but in addition in polygon theory one may consider a wreath product construction important in the algebraic theory of automata. The free product (or co-product) of polygons coincides with their disjoint union.

A polygon may be regarded as a non-additive analogue of a module over a ring, which serves as a rich source of problems in the theory of polygons. In particular, a relationship has been established between polygons and radicals in semi-groups (cf. Radical in a class of semi-groups), and studies have been made on the relation between the properties of a monoid and those of polygons over them. For example, all left $R$-polygons are projective if and only if $R$ is a one-element group, while the injectivity of all polygons over a commutative monoid $R$ is equivalent to the presence in $R$ of a zero element and the generation of all its ideals by idempotents (see Homological classification of rings).

If $R$ is a monoid with zero 0, one can define an $R$-polygon with zero as a pointed set $A$ which is an $R$-polygon where the distinguished point $u \in A$ satisfies $0a=u$ for all $a\in A$. The theory of polygons with zero has some special features.

Every polygon can be considered as a functor from a one-object category into the category of sets.

In the West, left polygons over a monoid $M$ are usually called $M$-sets; the term "operand" is also in use. The category of all $M$-sets ($M$ fixed) forms a topos; but for this it is essential not to exclude (as above) the empty $M$-set.

Without assuming commutativity as above, the monoids all of whose non-empty left polygons (or, all of whose pointed left polygons) are injective have a few characterizations, which are reviewed in [a3]. As noted above, there are no non-trivial monoids all of whose left polygons are projective, but the perfect monoids, defined (like perfect rings, cf. Perfect ring) by every left polygon having a projective covering, are non-trivial; see [a1], [a2].

The terms monoid action or monoid act, or action of a monoid on a set are also common, as is act for the set acted on; see [b1].

References

[1] M.A. Arbib (ed.) , Algebraic theory of machines, languages and semigroups , Acad. Press (1968)
[2] A.H. Clifford, G.B. Preston, "Algebraic theory of semi-groups" , 2 , Amer. Math. Soc. (1967)
[3] L.A. Skornyakov, "Generalizations of modules" , Modules , 3 , Novosibirsk (1973) pp. 22–27 (In Russian)
[4] L.A. Skornyakov, A.V. Mikhalev, "Modules" Itogi Nauk. i Tekhn. Alg. Topol. Geom. , 14 (1976) pp. 57–190 (In Russian)
[a1] J. Fountain, "Perfect semigroups" Proc. Edinburgh Math. Soc. , 20 (1976) pp. 87–93
[a2] J. Isbell, "Perfect monoids" Semigroup Forum , 2 (1971) pp. 95–118
[a3] R.W. Yoh, "Congruence relations on left canonic semigroups" Semigroup Forum (1977) pp. 175–183
[a4] S. Eilenberg, "Automata, languages and machines" , Acad. Press (1974)
[b1] Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev, Monoids, Acts and Categories: With Applications to Wreath Products and Graphs, Walter de Gruyter (2000) ISBN 3110812908

Density of a sequence

Other definitions

Let $A$ be a set of natural numbers and $\Lambda = (\lambda_n)$ a sequence of weights. The density of $A$ with respect to $\Lambda$ is the limit, if it exists $$ d_\Lambda(A) = \lim_{x \rightarrow \infty} \frac{\sum_{n \le x,\,n \in A} \lambda_n}{\sum_{n \le x} \lambda_n} \ . $$ The upper and lower densities $\bar d_\Lambda$,${\underline d}_\Lambda$ are the corresponding upper and lower limits, if they exist.

The natural or asymptotic density is the density with respect to the constant weight $\lambda_n = 1$ for all $n$.

The logarithmic density is the density with respect to weights $\lambda_n = \frac{1}{n}$.

A sequence has analytic density if and only if it has logarithmic density and if so then they are equal.


References

  • Tenenbaum, Gérald, "Introduction to analytic and probabilistic number theory." Cambridge Studies in Advanced Mathematics 46 Cambridge University Press (1995) ISBN 0-521-41261-7 Zbl 0831.11001

Asymptotics of arithmetic functions

asymptotics of number-theoretical functions

Approximate representations of arithmetic functions (functions defined for all natural number values of the argument) by means of comparatively simple expressions with arbitrary small error terms.

An initial question is to ask for a function with the same rate of growth as the given function. Given an arithmetic function $f(x)$ we say that $f$ has rate of growth, or is asymptotic to, a given function $\phi$ if $$ \lim_{x\to\infty}\frac{f(x)}{\phi(x)}=1 \ . $$ A short notation is: $f(x)\sim\phi(x)$ (cf. Asymptotic formula).

Examples:

  • The Prime number theorem: $\pi(x)$, the number of primes less than $x$ is asymptotic to $\frac{x}{\log x}$.

More precisely, for an arithmetic function $f(x)$ there exists an asymptotic if one has an asymptotic identity $$ f(x)=\phi(x)+R(x)\,, $$ where $\phi(x)$ is the approximating function or main term, and $R(x)$ is the error term, about which one knows in general only that $$ \lim_{x\to\infty}\frac{R(x)}{\phi(x)}=0 \ . $$ A short notation is: $f(x)=\phi(x)+o(\phi(x))$ or $f(x) = (1+o(1))\phi(x)$.

Examples:

Finding asymptotics of arithmetic functions is one of the most important problems in analytic number theory. This is explained by the fact that most arithmetic functions with interesting arithmetical properties display extreme irregularity in their changes as the argument increases. If one considers instead of an arithmetic function $f(x)$ its average value $(\sum_{n\leq x}f(n))/x$ ($n$ a natural number), then the "irregularity" of $f(x)$ is smoothed out. Hence, a typical problem for an arithmetic function is that of obtaining an asymptotic for its average value function. For example, the average value of the function $\tau(n)$, giving the number of divisors of $n$, is equal to $$ \frac1n\sum_{m\leq n}\tau(m)\sim\ln n. $$ (cf. Divisor_problems#Dirichlet's_divisor_problem). The problem that arises here, of the best possible bound for the error term in the asymptotic identity, is still unsolved (1984) for many functions, in particular for the function $\tau(x)$ (cf. Analytic number theory).

Asymptotics of arithmetic functions play an important a role in additive problems (cf. Additive number theory). For many of them there is no known direct proof of the existence of decompositions of a number into terms of a given form. However, as soon as one has an asymptotic for the number of decompositions of the type one is looking for, one can deduce that the required decomposition exists for all sufficiently large numbers $n$.

The average order and normal order of arithemetic functions refer to some simpler or better-understood function which have comparable asymptotic behaviour. It is conventional to assume that the approximating function $g$ is continuous and monotone.


The average order of an arithmetic function is a function which has the same average.

Let $f$, $g$ be functions on the natural numbers. We say that $f$ has average order $g$ if the asymptotic equality $$ \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) $$ holds as $x$ tends to infinity.


Examples:


The normal order of an arithmetic function is a function which "usually" takes the same or closely approximate values.

Let $f$ be a function on the natural numbers. We say that the normal order of $f$ is $g$ if for every $\epsilon > 0$, the inequalities $$ (1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n) $$ hold for almost all $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity.

Examples:

References

  • G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
  • G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 0-19-921986-5
  • Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics 46. Cambridge University Press. ISBN 0-521-41261-7
How to Cite This Entry:
Richard Pinch/sandbox-6. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-6&oldid=39278