Namespaces
Variants
Actions

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

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: expand bibliodata)
 
(21 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
A complete sup-lattice $Q$ together with an associative product $\otimes$ satisfying the distributive laws
+
=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
 
$$
 
$$
−
a \otimes \left({ \bigvee_i b_i }\right) = \bigvee_i a \otimes b_i
+
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
 
$$
 
$$
−
\left({ \bigvee_i b_i }\right) \otimes a= \bigvee_i b_i \otimes a
+
\phi(\lambda)a = b \ .
 
$$
 
$$
−
for all $a, b_i \in Q$ (cf. also [[Lattice]]; [[Distributivity]]; [[Associativity]]).
+
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]]).
  
−
The name  "quantale"  was introduced by C.J. Mulvey [[#References|[a1]]] to provide a non-commutative extension of the concept of [[locale]]. The intention was to develop the concept of non-commutative topology introduced by R. Giles and H. Kummer [[#References|[a2]]], while providing a constructive, and non-commutative, context for the foundations of quantum mechanics and, more generally, non-commutative logic. The observation that the closed right ideals of a [[C*-algebra|$C^*$-algebra]] form a quantale satisfying the conditions that each element is right-sided ($a \otimes 1_Q \le a$) and idempotent ($a \otimes a = a$)) led certain authors to restrict the term  "quantale"  to mean only quantales of this kind [[#References|[a3]]], but the term is now applied only in its original sense.
+
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.
  
−
The realization by J. Rosický [[#References|[a4]]] that the development of topological concepts such as regularity required additional structure led [[#References|[a5]]] to the consideration of involutive quantales, and of the spectrum $\text{Max} A$ of a $C^*$-algebra $A$ (cf. also [[Spectrum of a C*-algebra|Spectrum of a $C^*$-algebra]]) as the quantale of closed linear subspaces of $A$, together with the operations of join given by closed linear sum, product given by closed linear product of subspaces, and involution by involution within the $C^*$-algebra. The right-sided elements of the spectrum $\text{Max} A$ are the closed right ideals of the $C^*$-algebra $A$ (cf. [[#References|[a2]]], [[#References|[a6]]]). By the existence of approximate units, each element $a \in R(\text{Max} A)$ of the sup-lattice of right-sided elements satisfies the condition that $a \otimes a^* \otimes a = a$. By a ''Gel'fand quantale'' $Q$ is meant an involutive unital quantale in which the right-sided (equivalently, left-sided) elements satisfy this condition.
+
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.
  
−
Generalizing an observation in [[#References|[a4]]], the right-sided elements of any involutive quantale $Q$ may be shown to admit a pseudo-orthocomplement, defined by $a^\perp = \bigvee_{a^* \otimes b = 0_Q} b$. In any Gel'fand quantale $Q$, the right-sided elements are idempotent, and the two-sided elements form a locale.
+
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]]).
  
−
Observing that relations on a set $X$ forming a quantale with respect to arbitrary union and composition is applied implicitly by C.A. Hoare and He Jifeng when considering the weakest pre-specification of a program [[#References|[a7]]], and noting that the quantale $\mathcal{Q}(X)$ in question is exactly that of endomorphisms of the sup-lattice $\mathcal{P}(X)$ of subsets of $X \times X$, led to the consideration [[#References|[a8]]] of the quantale $\mathcal{Q}(S)$ of endomorphisms of any orthocomplemented sup-lattice $S$, in which the involute $\alpha^*$ of a sup-preserving mapping $\alpha$ is defined by $s \alpha^* = \left({ \bigvee_{t \alpha \le s^\perp} t} \right)^\perp$ for each $s \in S$. In the quantale $\mathcal{Q}(X)$ of relations on a set $X$, this describes the [[Transposed relation|reverse]] of a relation in terms of complementation of subsets. Observing that the quantale $\mathcal{Q}(H)$ of endomorphisms of the orthocomplemented sup-lattice of closed linear subspaces of a [[Hilbert space]] $H$ provides a motivating example for this quantization of the calculus of relations, the term ''Hilbert quantale'' was introduced for any quantale isomorphic to the quantale $Q9S)$ of an orthocomplemented sup-lattice $S$.
+
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.
  
−
Noting that the weak spectrum $\text{Max}_{\text{W}}(B)$ of a [[von Neumann algebra]] $B$ is a Gel'fand quantale of which the right-sided elements correspond to the projections of $B$ and on which the right pseudo-orthocomplement corresponds to orthocomplementation of projections, a Gel'fand quantale $Q$ is said to be a ''von Neumann quantale'' if $(a^\perp)^\perp = a$ for any right-sided element $a \in Q$. For any von Neumann quantale $Q$, the locale $I(Q)$ of two-sided elements is a complete [[Boolean algebra]]. Any Hilbert quantale $Q$ is a von Neumann quantale, and a von Neumann quantale $Q$ is a Hilbert quantale exactly if the canonical homomorphism $\mu_Q : Q \rightarrow \mathcal{Q}(R(Q))$, assigning to each $a \in Q$ the sup-preserving mapping $b \in R(Q) \mapsto a^* \otimes b \in R(Q)$ on the orthocomplemented sup-lattice $R(Q)$ of right-sided elements of $Q$, is an isomorphism [[#References|[a8]]]. Any Hilbert quantale $Q$ is a von Neumann factor quantale in the sense that $I(Q)$ is exactly $\mathbf2]$. The weak spectrum $\text{Max}_{\text{W}}(B)$ of a von Neumann algebra $B$ is a factor exactly if $B$ is a factor [[#References|[a9]]] (cf. also [[von Neumann algebra]]).
+
Every polygon can be considered as a [[functor]] from a one-object category into the category of sets.
  
−
A homomorphism $\phi : Q \rightarrow \mathcal{Q}(S)$ from a Gel'fand quantale $Q$ to the Hilbert quantale $\mathcal{Q}(S)$ of an orthocomplemented sup-lattice $S$ is said to be a representation of $Q$ on $S$ [[#References|[a10]]]. A representation is said to be ''irreducible'' provided that $s \in S$ invariant (in the sense that $s \phi_a \le s$ for all $a \in Q$) implies $s = 0_Q$ or $s = 1_Q$. The irreducibility of a representation $\phi : Q \rightarrow \mathcal{Q}(S)$ is equivalent to the homomorphism being ''strong'', in the sense that $\phi(1_Q) = 1_{\mathcal{Q}(S)}$. A homomorphism $Q' \rightarrow Q$ of Gel'fand quantales is strong exactly if $Q' \rightarrow Q \rightarrow \mathcal{Q}(S)$ is irreducible whenever $Q \rightarrow \mathcal{Q}(S)$ is irreducible. A representation $\phi : Q \rightarrow \mathcal{Q}(S)$ of $Q$ on an atomic orthocomplemented sup-lattice $S$ is said to be ''algebraically irreducible'' provided that for any atoms $x,y \in S$ there exists an $a \in Q$ such that $x\phi_a = y$ (cf. also [[atomic lattice]]). Any algebraically irreducible representation is irreducible: the algebraically irreducible representations are those for which every atom is a cyclic generator. An algebraically irreducible representation $\phi : Q \rightarrow \mathcal{Q}(S)$ on an atomic orthocomplemented sup-lattice $S$ is said to be a ''point'' of the Gel'fand quantale $Q$. The points of the spectrum $\text{Max} A$ of a $C^*$-algebra $A$ correspond bijectively to the equivalence classes of irreducible representations of $A$ on a Hilbert space [[#References|[a10]]]. (Presently (2000), this is subject to the conjecture that every point of $\text{Max} A$ is non-trivial in the sense that there exists a pure state that maps properly. For a discussion of the role of pure states in this context, see [[#References|[a10]]].) In particular, the spectrum $\text{Max} A$ is an invariant of the $C^*$-algebra $A$. It may be noted that the Hilbert quantale $\mathcal{Q}(S)$ of an atomic orthocomplemented sup-lattice has, to within equivalence, a unique point; moreover, the reflection of such a Gel'fand quantale into the category of locales is exactly $\mathbf{2}$. In particular, the points of any locale are exactly its points in the sense of the theory of locales.
+
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.
  
−
A von Neumann quantale $Q$ is said to be ''atomic'' provided that the orthocomplemented sup-lattice $R(Q)$ of its right-sided elements is atomic. For any atomic von Neumann quantale $Q$ the complete Boolean algebra of two-sided elements $I(Q)$ is atomic. Moreover, the canonical homomorphism $\mu_Q : Q \rightarrow \mathcal{Q}(R(Q))$ is algebraically irreducible exactly if $Q$ is a von Neumann factor quantale. A Gel'fand quantale $Q$ is said to be ''discrete'' provided that it is an atomic von Neumann quantale that admits a central decomposition of the unit $e_Q \in Q$, in the sense that the atoms of the complete Boolean algebra $I(Q)$ majorize a family of central projections with join $e_Q \in Q$. For any atomic von Neumann algebra $B$, the weak spectrum $\text{Max}_{\text{W}} B$ is a discrete von Neumann quantale. A locale $L$ is a discrete von Neumann quantale exactly if it is a complete atomic Boolean algebra, hence the power set of its set of points. A homomorphism $X \rightarrow Q$ of Gel'fand quantales is said to be:
+
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]]].
  
−
''algebraically strong'' if $X \rightarrow Q \rightarrow \mathcal{Q}(S)$ is algebraically irreducible whenever $Q \rightarrow \mathcal{Q}(S)$ is an algebraically irreducible representation of $Q$ on an atomic orthocomplemented sup-lattice $S$;
+
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]]].
  
−
a ''right embedding'' if it restricts to an embedding $R(X) \rightarrow R(Q)$ of the lattices of right-sided elements;
+
====References====
 +
<table>
 +
<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>
 +
<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>
 +
<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>
 +
<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>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Fountain,  "Perfect semigroups"  ''Proc. Edinburgh Math. Soc.'' , '''20'''  (1976)  pp. 87–93</TD></TR>
 +
<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>
  
−
''discrete'' if it is an algebraically strong right embedding.
+
=Density of a sequence=
  
−
A Gel'fand quantale $X$ is said to be ''spatial'' if it admits a discrete homomorphism $X \rightarrow Q$ into a discrete von Neumann quantale $Q$ [[#References|[a11]]]. For any $C^*$-algebra $A$, the canonical homomorphism
+
==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
 
$$
 
$$
−
\text{Max} A \rightarrow \text{Max}_{\text{W}} B
+
d_\Lambda(A) = \lim_{x \rightarrow \infty} \frac{\sum_{n \le x,\,n \in A} \lambda_n}{\sum_{n \le x} \lambda_n} \ .
 
$$
 
$$
−
of its spectrum $\text{Max} A$ into the weak spectrum of its enveloping atomic von Neumann algebra $B$ is discrete, hence $\text{Max} A$ is spatial. Similarly, a locale $L$ is spatial as a Gel'fand quantale exactly if its canonical homomorphism into the power set of its set of points is discrete. More generally, a Gel'fand quantale $Q$ is spatial exactly if it has enough points, in the sense that if $a,b \in R(Q)$ are distinct, then there is an algebraically irreducible representation $\phi : Q \rightarrow \mathcal{Q}(S)$ on an atomic orthocomplemented sup-lattice $S$ such that $\phi_a, \phi_b \in R(\mathcal{Q}(S))$ are distinct [[#References|[a11]]].
+
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.
 +
 
  
−
In other important directions, Girard quantales have been shown [[#References|[a12]]] to provide a semantics for non-commutative linear logic, and Foulis quantales to generalize the Foulis semi-groups of complete orthomodular lattices [[#References|[a13]]]. The concepts of quantal set and of sheaf have been introduced [[#References|[a14]]] for the case of idempotent right-sided quantales, generalizing those for any locale. These concepts may be localized [[#References|[a15]]] to allow the construction of a fibration from which the quantale may be recovered directly. The representation of quantales by quantales of relations has also been examined [[#References|[a16]]].
 
  
 
====References====
 
====References====
−
<table>
+
* 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}}
−
<TR><TD valign="top">[a1]</TD> <TD valign="top">  C.J. Mulvey,  "&amp;"  ''Rend. Circ. Mat. Palermo'' , '''12'''  (1986) pp. 99–104 {{ZBL|0633.46065}}</TD></TR>
+
 
−
<TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Giles,  H. Kummer,  "A non-commutative generalization of topology"  ''Indiana Univ. Math. J.'' , '''21'''  (1971) pp. 91–102</TD></TR>
+
=Asymptotics of arithmetic functions=
−
<TR><TD valign="top">[a3]</TD> <TD valign="top"> K.I. Rosenthal,   "Quantales and their applications" , ''Pitman Research Notes in Math.'' , '''234''' , Longman  (1990)</TD></TR>
+
<!--
−
<TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Rosický,   "Multiplicative lattices and $C^*$-algebras"  ''Cah. Topol. Géom. Diff. Cat.'' , '''30'''  (1989) pp. 95–110</TD></TR>
+
{{TEX|done}}{{MSC|11A25}}
−
<TR><TD valign="top">[a5]</TD> <TD valign="top">  C.J. Mulvey,   "Quantales" , ''Invited Lecture, Summer Conf. Locales and Topological Groups, Curaçao''  (1989)</TD></TR>
+
-->
−
<TR><TD valign="top">[a6]</TD> <TD valign="top">  C.A. Akemann,  "Left ideal structure of $C^*$-algebras"  ''J. Funct. Anal.'' , '''6'''  (1970) pp. 305–317</TD></TR>
+
 
−
<TR><TD valign="top">[a7]</TD> <TD valign="top">  C.A.R. Hoare,  He Jifeng,  "The weakest prespecification"  ''Inform. Proc. Lett.'' , '''24'''  (1987) pp. 127–132  {{ZBL|0622.68025}}</TD></TR>
+
''asymptotics of number-theoretical functions''
−
<TR><TD valign="top">[a8]</TD> <TD valign="top"> C.J. Mulvey,   J.W. Pelletier,   "A quantisation of the calculus of relations" , ''Category Theory 1991, CMS Conf. Proc.'' , '''13''' , Amer. Math. Soc.  (1992) pp. 345–360 {{ZBL|0793.06008}}</TD></TR>
+
 
−
<TR><TD valign="top">[a9]</TD> <TD valign="top">  J.W. Pelletier,   "Von Neumann algebras and Hilbert quantales"  ''Appl. Cat. Struct.'' , '''5'''  (1997)  pp. 249–264</TD></TR>
+
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.  
−
<TR><TD valign="top">[a10]</TD> <TD valign="top">  C.J. Mulvey,  J.W. Pelletier,  "On the quantisation of points"  ''J. Pure Appl. Algebra'' , '''159''' (2001) pp. 231–295</TD></TR>
+
 
−
<TR><TD valign="top">[a11]</TD> <TD valign="top">  C.J. Mulvey,   J.W. Pelletier,   "On the quantisation of spaces"  ''J. Pure Appl. Math.''  '''175''' (2002) pp.289-325 {{ZBL|1026.06018}}</TD></TR>
+
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
−
<TR><TD valign="top">[a12]</TD> <TD valign="top">  D. Yetter,   "Quantales and (non-commutative) linear logic"  ''J. Symbolic Logic'' , '''55'''  (1990)  pp. 41–64</TD></TR>
+
$$
−
<TR><TD valign="top">[a13]</TD> <TD valign="top">  C.J. Mulvey,  "Foulis quantales" ''to appear''</TD></TR>
+
\lim_{x\to\infty}\frac{f(x)}{\phi(x)}=1 \ .
−
<TR><TD valign="top">[a14]</TD> <TD valign="top">  C.J. Mulvey,  M. Nawaz,  "Quantales: Quantal sets" , ''Non-Classical Logics and Their Application to Fuzzy Subsets: A Handbook of the Mathematical Foundations of Fuzzy Set Theory'' , Kluwer Acad. Publ.  (1995)  pp. 159–217</TD></TR>
+
$$
−
<TR><TD valign="top">[a15]</TD> <TD valign="top">  U. Berni-Canani,  F. Borceux,   R. Succi-Cruciani,  "A theory of quantale sets"  ''J. Pure Appl. Algebra'' , '''62'''  (1989) pp. 123–136</TD></TR>
+
A short notation is: $f(x)\sim\phi(x)$ (cf. [[Asymptotic formula]]).
−
<TR><TD valign="top">[a16]</TD> <TD valign="top">  C. Brown,  D. Gurr,  "A representation theorem for quantales"  ''J. Pure Appl. Algebra'' , '''85'''  (1993)  pp. 27–42</TD></TR>
+
 
−
</table>
+
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:
 +
* The [[Prime number theorem]] in a more precise form: $\pi(x) = (1+o(1)) \mathop{Li}(x)$ where $\mathop{Li}$ is the [[logarithmic integral]] function.
 +
 
 +
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|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 function|continuous]] and [[Monotone function|monotone]].
 +
 
 +
 
 +
The ''average order'' of an arithmetic function is a function which has the same average.
 +
 
 +
Let $f$, $g$ be functions on the [[natural number]]s. 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 average order of $d(n)$, the [[number of divisors]] of $n$, is $\log n$;
 +
* The average order of $\sigma(n)$, the [[sum of divisors]] of $n$, is $ \frac{\pi^2}{6} n$;
 +
* The average order of $\phi(n)$, the [[Euler totient function]] of $n$, is $ \frac{6}{\pi^2} n$;
 +
* The average order of $r(n)$, the number of ways of expressing $n$ as a [[sum of two squares]], is $\pi$;
 +
* The [[Prime number theorem|Prime Number Theorem]] is equivalent to the statement that the [[Mangoldt function|von Mangoldt function]] $\Lambda(n)$ has average order 1.
 +
 
 +
 
 +
 
 +
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 number]]s.  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:
 +
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$;
 +
* The normal order of $\log d(n))$, where $d(n)$ is the [[number of divisors|number of divisors function]] of $n$, is $\log 2 \log\log n$.
 +
 
 +
===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

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=39039
Retrieved from "https://encyclopediaofmath.org/index.php?title=User:Richard_Pinch/sandbox-6&oldid=39303"