Namespaces
Variants
Actions

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

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎Greedoid: move text)
 
(248 intermediate revisions by the same user not shown)
Line 1: Line 1:
=de Bruijn–Newman constant=
+
=Eulerian number=
A constant $\Lambda$ describing the behaviour of functions related to the [[Riemann zeta-function]]The [[Riemann hypotheses|Riemann hypothesis]] is equivalent to the assertion that $\Lambda \le 0$.  By contrast, Newman conjectured that $\Lambda \ge 0$, and it is known that $\Lambda > −1·14541 \cdot 10^{−11}$.
+
A combinatorial counting function for the number of descents in a permutationHere we take a permutation $(a_1,\ldots,a_n)$ of $(1,\ldots,n)$ and count as a ''descent'' any $i$ such that $a_i > a_{i+1}$. We let
 
+
$$
==Definition==
+
\left\langle{ n \atop k }\right\rangle
Let $\Xi$ denote the [[Riemann xi-function]], $\Xi(t) = \xi(\frac12 + it)$ where
+
$$
 +
denote the number of permutations on $n$ elements with $k$ descents.  It satisfies the [[recurrence relation]]
 
$$
 
$$
\xi(s) = \frac12 s(s-1) \pi^{-s/2} \Gamma(s/2) \zeta(s)
+
\left\langle{ n \atop k }\right\rangle = (n-k) \left\langle{ n-1 \atop k-1 }\right\rangle + (k+1) \left\langle{ n-1 \atop k }\right\rangle
 
$$
 
$$
with $\zeta(s)$ the Riemann zeta function.  The Riemann hypothesis is equivalent to the assertion that all the zeroes of $\Xi$ lie on the real line.
 
  
We define a family of modified functions $H_\lambda$ by considering $\Xi$ as the [[Fourier transform]] of a function $\Phi(t)$ and defining $H_\lambda$ as the transform of $\Phi(t) \exp(\lambda t^2)$.  The Riemann hypothesis is that $H_0$ has only real zeroes.  De Bruijn proved that $H_\lambda$ has only real zeroes when $\lambda > \frac14$, and Newman showed that while there there exists a $\lambda$ such that $H_\lambda$ has non-real zeroes, there exists a $\Lambda$ such that  $H_\lambda$ has only real zeroes for all $\lambda \ge \Lambda$.  The infimum of such $\Lambda$ is the de Bruijn–Newman constant.
+
The ''Eulerian polynomial'' is the generating function
 
 
==References==
 
* Finch, Steven R.  ''Mathematical Constants'', Cambridge University Press (2003) ISBN 0-521-81805-2
 
* Saouter, Yannick; Gourdon, Xavier; Demichel, Patrick.  "An improved lower bound for the de Bruijn-Newman constant", ''Math. Comput.'' '''80''', No. 276, 2281-2287 (2011) Zbl 1267.11094
 
 
 
[[:Category:Number theory]]
 
 
 
=Quadratic equation=
 
====Comments====
 
Over a field of characteristic 2, the solution by completing the square is no longer available.  Instead, by a change of variable, the equation may be written either as
 
 
$$
 
$$
X^2 + c = 0
+
S_n(t) = \sum_{k=0}^n \left\langle{ n \atop k }\right\rangle t^k \ .
 
$$
 
$$
or in ''Artin--Schreier form''
+
The recurrence relation may be written as
 
$$
 
$$
X^2 + X + c = 0 \ .
+
S_{n+1}(t) = (1+nt) S_n(t) + t(1-t)S'_n(t) \ .
 
$$
 
$$
  
In the first case, the equation has a double root $c^{1/2}$In the Artin--Schreier case, the map $A:X \mapsto X^2+X$ is two-to-one, since $A(X+1) = A(X)$If $\alpha$ is a root of the equation, so is $\alpha+1$.
+
The Eulerian numbers appear in a related contextWe define an ''excedance'' of a permutation to be the number of $i$ such that $a(i) > i$ (''weak'' if $a_i \ge i$).  Then the number of permutations with $k$ excendances is equal to the number with $k+1$ weak excedances, and is in turn equal to $\left\langle{ n \atop k }\right\rangle$.
See [[Artin-Schreier theorem]]
 
====References====
 
<table>
 
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Lidl,   H. Niederreiter,  "Finite fields" , Addison-Wesley  (1983); second edition Cambridge University Press (1996) Zbl 0866.11069</TD></TR>
 
</table>
 
 
 
=Normal number=
 
====Comments====
 
The example of Champernowne's number as an explicitly normal number in base 10 was generalised by Copeland and Erdős [CE] who showed that if $a_n$ is an increasing sequence of natural numbers with the property that for every $\theta > 1$ then  $a_n < n^\theta$ for sufficiently large $n$, then the number $0 \cdot \alpha_1 \alpha_2 \ldots$ is normal in base $g$ where $\alpha_n$ is the base $g$ expression of $a_n$.  See also [B] pp.86-87.
 
  
 
====References====
 
====References====
[CE] Copeland, A. H.; Erdős, P.  "Note on normal numbers", ''Bulletin of the American Mathematical Society'' '''52''' (1946) 857–860, doi:10.1090/S0002-9904-1946-08657-7, Zbl 0063.00962
+
* T. Kyle Petersen ''Eulerian Numbers'' Birkhäuser (2015) ISBN 1-4939-3091-5 {{ZBL|06467929}}
[B] Bugeaud, Yann. ''Distribution modulo one and Diophantine approximation'', Cambridge Tracts in Mathematics 193, Cambridge: Cambridge University Press (2012) ISBN 978-0-521-11169-0, Zbl 1260.11001
+
* Richard P. Stanley ''Enumerative combinatorics'' '''I''' Wadsworth & Brooks/Cole (1986) ISBN 0-534-06546-5 {{ZBL| 0608.05001}}
  
=Unitary divisor=
+
=Lattice valuation=
A [[natural number]] $d$ is a '''unitary divisor''' of a number $n$ if $d$ is a [[divisor]] of $n$ and $d$ and $n/d$ are [[coprime]], having no common factor other than 1.  Equivalently, $d$ is a unitary divisor of $n$ if and only if every prime factor of $d$ appears to the same power in $d$ as in $n$.
+
A function $\nu$ on a [[lattice]] $L$ with values in a [[ring]] $R$ satisfying
 +
$$
 +
\nu(x \wedge y) + \nu(x \vee y) = \nu(x) + \nu(y) \ .
 +
$$
  
The sum of unitary divisors function is denoted by $\sigma^*(n)$. The sum of the $k$-th powers of the unitary divisors is denoted by $\sigma_k^*(n)$.  These functions  are [[multiplicative arithmetic function]]s of $n$ that are not totally multiplicative. The [[Dirichlet series]] [[generating function]] is
 
  
$$ \sum_{n\ge 1}\sigma_k^*(n) n^{-s} = \frac{\zeta(s)\zeta(s-k)}{\zeta(2s-k)} . $$
 
  
The number of unitary divisors of $n$ is $\sigma_0(n) = 2^{\omega(n)}$, where $\omega(n)$ is the number of distinct [[prime factor]]s of $n$.
+
====References====
 
+
* Rota, Gian-Carlo (with P. Doubilet, C. Greene, D. Kahaner, A: Odlyzko and R. Stanley) ''Finite operator calculus'' Academic Press (1975) ISBN 0-12-596650-4 {{ZBL|0328.05007}}
A '''unitary''' or '''unitarily perfect number''' is equal to the sum of its aliquot unitary divisors:equivalen tly, it is ''n'' such that $\sigma^*(n) = 2n$.  A unitary perfect number must be even.  It is not known whether or not there are infinitely many unitary perfect numbers, or indeed whether there are any further examples beyond the five already known.  A sixth such number would have at least nine odd prime factors.  The five known are
 
 
 
$$ 6 = 2\cdot3,\ 60 = 2^2\cdot3\cdot5,\ 90 = 2\cdot3^3\cdot5,\ 87360 = 2^6\cdot3\cdot5\cdot7\cdot13, $$
 
and
 
$$ 146361946186458562560000  = 2^{18}\cdot3\cdot5^4\cdot7\cdot11\cdot13\cdot19\cdot37\cdot79\cdot109\cdot157\cdot313\ . $$
 
 
 
==References==
 
* Guy, Richard K. ''Unsolved Problems in Number Theory'', Problem Books in Mathematics, 3rd ed. (Springer-Verlag, 2004) p.84, section B3. ISBN 0-387-20860-7 {{ZBL|1058.11001}}
 
* Sándor, Jozsef; Crstici, Borislav (2004). ''Handbook of number theory II''. (Dordrecht: Kluwer Academic, 2004) pp. 179–327. ISBN 1-4020-2546-7. {{ZBL|1079.11001}}
 
* Wall, Charles R.  "The fifth unitary perfect number", ''Can. Math. Bull.'' '''18''' (1975) 115-122.  ISSN 0008-4395.  {{ZBL|0312.10004}}
 
* Wall, Charles R. "New unitary perfect numbers have at least nine odd components". Fibonacci Quarterly '''26''' no.4 (1988) ISSN 0015-0517. {{MR|967649}}. {{ZBL|0657.10003}}
 
 
 
=Descartes number=
 
A number which is close to being a [[perfect number]].  They are named for [[René Descartes]] who observed that the number
 
  
$$D= 198585576189 = 3^2⋅7^2⋅11^2⋅13^2⋅22021 $$
 
  
would be an odd perfect number if only 22021 were a [[prime number]], since the [[sum-of-divisors function]] for $D$ satisfies
 
  
$$\sigma(D) = (3^2+3+1)\cdot(7^2+7+1)\cdot(11^2+11+1)\cdot(13^3+13+1)\cdot(22021+1) \ . $$
+
=Series-parallel graph=
 +
A class of [[graph]]s related to ideas from electrical networks.  It is convenient to take "graph" to mean unoriented graph allowing loops and multiple edges.  A two-terminal series-parallel graph $(G,h,t)$ has two distinguished vertices, ''source'' $h$ and ''sink'' $t$ (or "head and "tail").  The class is built recursively from the single edge $P_2 = ((\{h,t\}, \{ht\}), h,t)$ with $h$ as head and $t$ as tail, using the operations of series and parallel combination.  It is assumed that the graphs to be combined have disjoint vertex sets.  The series combination of $(G_1, h_1,t_1)$ and $(G_2, h_2,t_2)$ is the graph obtained by identifying $t_1$ with $h_2$ and taking $h_1$ as head and $t_2$ as tail.  The parallel combination  of $(G_1, h_1,t_1)$ and $(G_2, h_2,t_2)$ is the graph obtained by identifying $h_1$ with $h_2$ and $t_1$ with $t_2$ then taking $h_1=h_2$ as head and $t_1=t_2$ as tail.
  
A Descartes number is defined as an odd number $n = m p$ where $m$ and $p$ are coprime and $2n = \sigma(m)\cdot(p+1)$. The example given is the only one currently known.
+
...
  
If $m$ is an odd [[almost perfect number]], that is, $\sigma(m) = 2m-1$, then $m(2m−1)$ is a Descartes number.
+
Series-parallel graphs are characterised by having no subgraph homeomorphic to $K_4$, the [[complete graph]] on $4$ vertices.
  
 
==References==
 
==References==
* Banks, William D.; Güloğlu, Ahmet M.; Nevans, C. Wesley; Saidak, Filip (2008). "Descartes numbers". In De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (edd). ''Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006''. CRM Proceedings and Lecture Notes '''46''' (Providence, RI: American Mathematical Society) pp. 167–173. ISBN 978-0-8218-4406-9. {{ZBL|1186.11004}}.
+
* Andreas Brandstädt, Van Bang Le; Jeremy P. Spinrad, "Graph classes: a survey". SIAM Monographs on Discrete Mathematics and Applications '''3'''. Society for Industrial and Applied Mathematics (1999) ISBN 978-0-898714-32-6 {{ZBL|0919.05001}}
  
=Multiplicative sequence=
+
=Polarity=
Also '''''m''-sequence''', a sequence of [[polynomial]]s associated with a formal group structure.  They have application in the [[cobordism|cobordism ring]] in [[algebraic topology]].
 
  
==Definition==
+
A correspondence derived from a [[binary relation]] between two sets, introduced by G. Birkhoff: a special case of a [[Galois correspondence]].  Let $R$ be a relation from $A$ to $B$, equivalently a subset of $A \times B$.  Define ''polar'' maps between the [[power set]]s, $F : \mathcal{P}A \rightarrow \mathcal{P}B$ and $G : \mathcal{P}B \rightarrow \mathcal{P}A$ by
Let $K_n$ be polynomials over a ring $A$ in indeterminates $p_1,\ldots$ weighted so that $p_i$ has weight $i$ (with $p_0=1$) and all the terms in $K_n$ have weight $n$ (so that $K_n$ is a polynomial in $p_1,\ldots,p_n$). The sequence $K_n$ is ''multiplicative'' if an identity
+
$$
 +
F(U) = \{ b \in B : aRb\ \text{for all}\ a \in U \}
 +
$$
 +
and
 +
$$
 +
G(V) = \{ a \in A : aRb\ \text{for all}\ b \in V \} \ .
 +
$$
  
$$\sum_i p_i z^i = \sum p'_i z^i \cdot \sum_i p''_i z^i $$
+
Make $\mathcal{P}A$, $\mathcal{P}B$ [[partially ordered set]]s by subset inclusion.  Then $F$ and $G$ are order-reversing maps, and $FG$ and $GF$ are order-preserving (monotone).  Indeed, $F$ and $G$ are quasi-inverse, that is, $FGF = F$ and $GFG = G$; hence $FG$ and $GF$ are [[closure operator]]s.
  
implies
+
The closed pairs $(U,V)$ with $V = F(U)$ and $U = G(V)$ may be ordered by $(U_1,V_1) \le (U_2,V_2) \Leftrightarrow U_1 \subseteq U_2 \Leftrightarrow V_1 \supseteq V_2$.  This ordered set, denoted $\mathfrak{B}(A,B,R)$, is a [[complete lattice]] with
 +
$$
 +
\bigwedge_{i \in I} (U_i,V_i) = \left({ \bigcap_{i\in I} U_i, FG\left({ \bigcup_{i \in I} V_i }\right) }\right)
 +
$$
 +
and
 +
$$
 +
\bigvee_{i \in I} (U_i,V_i) = \left({ GF\left({ \bigcup_{i \in I} U_i }\right), \bigcap_{i\in I} V_i  }\right) \ .
 +
$$
  
$$\sum_i K_i(p_1,\ldots,p_i) z^i = \sum_j K_j(p'_1,\ldots,p'_j) z^j \cdot \sum_k K_k(p''_1,\ldots,p''_k) z^k  . $$
+
Every complete lattice $L$ arises in this way: indeed, $L = \mathfrak{B}(L,L,{\le})$.
The power series
 
  
$$\sum K_n(1,0,\ldots,0) z^n $$
+
==References==
 +
* Birkhoff, Garrett ''Lattice theory'' American Mathematical Society (1940) {{ZBL|0063.00402}}
 +
* Davey, B.A.; Priestley, H.A. ''Introduction to lattices and order'' (2nd ed.) Cambridge University Press (2002) ISBN 978-0-521-78451-1 {{ZBL|1002.06001}}
  
is the ''characteristic power series'' of the $K_n$.  A multiplicative sequence is determined by its characteristic power series $Q(z)$, and every power series with constant term 1 gives rise to a multiplicative sequence.
+
=Frame=
 +
A generalisation of the concept of topological space occurring in the theory of logic and computation.
  
To recover a multiplicative sequence from a characteristic power series $Q(z)$ we consider the coefficient of ''z''<sup>''j''</sup> in the product
+
A ''frame'' is a [[complete lattice]] $(X,{\le})$ (a lattice with all meets and joins) satisfying the frame distributivity law, that binary meets distribute over arbitrary joins:
 +
$$
 +
x \wedge \bigvee \{ y \in Y \} = \bigvee \{ x \wedge y : y \in Y \} \ .
 +
$$
  
$$ \prod_{i=1}^m Q(\beta_i z) $$
+
The powerset $\mathcal{P}(A)$ of a set $A$ forms a frame.
  
for any $m>j$.  This is symmetric in the $\beta_i$ and homogeneous of weight ''j'': so can be expressed as a polynomial $K_j(p_1,\ldots,p_j)$ in the [[elementary symmetric function]]s $p$ of the $\beta$.  Then $K_j$ defines a multiplicative sequence.
+
If $(X,\mathfrak{T})$ is a [[topological space]], with $\mathfrak{T}$ the collection of open sets, then $\mathfrak{T}$ forms a subframe of $\mathcal{P}(X)$: it should be noted that whereas the join is set-theoretic union, the meet operation is given by
 
+
$$
==Examples==
+
\bigwedge \{ S \} = \mathrm{Int}\left({ \bigcap \{ S \} }\right)
As an example, the sequence $K_n = p_n$ is multiplicative and has characteristic power series $1+z$.
 
 
 
Consider the power series
 
 
 
$$ Q(z) = \frac{\sqrt z}{\tanh \sqrt z} = 1 - \sum_{k=1}^\infty (-1)^k \frac{2^{2k}}{(2k)!} B_k z^k
 
 
$$
 
$$
where $B_k$ is the $k$-th [[Bernoulli number]].  The multiplicative sequence with $Q$ as characteristic power series is denoted $L_j(p_1,\ldots,p_j)$.
+
where $\mathrm{Int}$ denotes the [[interior]].   
  
The multiplicative sequence with characteristic power series
+
====References====
 +
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top"> Steven Vickers ''Topology via Logic'' Cambridge Tracts in Theoretical Computer Science '''5''' Cambridge University Press (1989) ISBN 0-521-36062-5 {{ZBL|0668.54001}} </TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top"> Jonathan S. Golan ''Semirings and their Applications'' Springer (2013)  ISBN 9401593337</TD></TR>
 +
</table>
  
$$ Q(z) = \frac{2\sqrt z}{\sinh 2\sqrt z} $$
+
=Alexandrov topology=
 +
''on a [[partially ordered set]] $(X,{\le})$''
  
is denoted $A_j(p_1,\ldots,p_j)$.
+
A topology which is discrete in the broad sense, that arbitrary unions and intersections of open sets are open.  Define an upper set $U \subseteq X$ to be one for which $u \in U$ and $u \le x$ implies $x \in U$.  The Alexandrov topology on $X$ is that for which all upper sets are open.
  
The multiplicative sequence with characteristic power series
+
The Alexandrov topology makes $X$ a [[T0 space]] and the [[Specialization of a point|specialisation]] order is just the original order ${\le}$ on $X$.
  
$$Q(z) = \frac{z}{1-\exp(-z)}  = 1 + \frac{x}{2} - \sum_{k=1}^\infty (-1)^k \frac{B_k}{(2k)!} z^{2k} $$
+
====References====
is denoted $T_j(p_1,\ldots,p_j)$: the ''[[Todd polynomial]]s''.
+
* Johnstone, Peter T. ''Stone spaces'' Cambridge Studies in Advanced Mathematics '''3''' Cambridge University Press(1986) {{ZBL|0586.54001}}
  
==Genus==
+
=Exponentiation=
The '''genus''' of a multiplicative sequence is  a [[ring homomorphism]], from the  [[cobordism|cobordism ring]] of smooth oriented [[compact manifold]]s to another [[ring]], usually the ring of [[rational number]]s.
+
The algebraic and analytic operations generalising the operation of repeated multiplication in number systems.
  
For example, the [[Todd genus]] is associated to the Todd polynomials $T_j$ with characteristic power series $$\frac{z}{1-\exp(-z)}$$ and the [[L-genus]] is associated to the polynomials $L_j$ with charac\teristic polynomial $$\frac{\sqrt z}{\tanh \sqrt z} . $$
+
For positive integer $n$, the operation $x \mapsto x^n$ may be defined on any system of numbers by repeated multiplication
 +
$$
 +
x^n = x \cdot x \cdot \cdots \cdot x\ \ \ (n\,\text{times})  
 +
$$
 +
where $\cdot$ denotes multiplication. The number $n$ is the ''exponent'' in this operation.
  
==References==
+
The repeated operations may be carried out in any order provided that multiplication is [[associativity|associative]], $x \cdot (y \cdot z) = (x \cdot y) \cdot z$. In this case we have
* Hirzebruch, Friedrich. ''Topological methods in algebraic geometry'',  Classics in Mathematics. Translation from the German and appendix one  by R. L. E. Schwarzenberger. Appendix two by A. Borel.  Reprint of the  2nd, corr. print. of the 3rd ed. [1978] (Berlin: Springer-Verlag, 1995). ISBN 3-540-58663-6. {{ZBL|0843.14009}}.
+
$$
 +
x^{m+n} = x^m \cdot x^n \ .
 +
$$
  
=Nagao's theorem=
+
If the operation is also [[commutativity|commutative]] then we have
A result, named after Hirosi Nagao, about the structure of the [[group]] of 2-by-2 [[Invertible matrix|invertible matrices]] over the [[ring of polynomials]] over a [[field]].  It has been extended by [[Jean-Pierre Serre|Serre]] to give a description of the structure of the corresponding matrix group over the [[coordinate ring]] of a [[projective curve]].
+
$$
 +
(x \cdot y)^n = x^n \cdot y^n \ .
 +
$$
  
==Nagao's theorem==
+
We may extend the definition to non-positive integer powers by defining $x^0 = 1$ and  
 
+
$$
For a [[Ring (mathematics)|general ring]] $R$ we let $GL_2(R)$ denote the group of invertible 2-by-2 matrices with entries in $R$, and let $R^*$ denote the [[group of units]] of $R$, and let
+
x^{-n} = \frac{1}{x^n}
 
+
$$
$$ B(R) = \left\lbrace{  \left({\begin{array}{*{20}c} a & b \\ 0 & d \end{array}}\right) : a,d \in R^*, ~ b \in R  }\right\rbrace \ . $$
+
whenever this makes sense.
  
Then $B(R)$ is a subgroup of $GL_2(R)$.
+
We may extend the definition to rational number exponents by taking $x^{1/n}$ to be any number $y$ such that $y^n = x$: this may denote none, one or more than one number.
  
Nagao's theorem states that in the case that $R$ is the ring $K[t]$ of polynomials in one variable over a field $K$, the group $GL_2(R)$ is the [[amalgamated product]] of $GL_2(K)$ and $B(K[t])$ over their intersection $B(K)$.
+
===Positive real numbers===
 +
Exponentiation of positive real numbers by rational exponents may be defined by taking $x^{1/n}$ to be the unique positive real solution of $y^n = x$: this always exists.  We thus have $x^q$ well-defined for $x>0$ and any rational exponent $q$.  Exponentiation preserves order: if $x > y$ then $x^q > y^q$ if $q > 0$ and $x^q < y^q$ if $q < 0$.
  
==Serre's extension==
+
We can now define exponentiation with real exponent $r$ by defining $x^r$ to be the limit of $x^{q_n}$ where $q_n$ is a sequence of rational numbers converging to $r$.  There is always such a sequence, and the limit exists and does not depend on the chosen sequence.
In this setting, $C$ is a [[Singular point of an algebraic variety|smooth]] projective curve over a field $K$.  For a [[closed point]] $P$ of $C$ let $R$ be the corresponding coordinate ring of $C$ with $P$ removed.  There exists a [[graph of groups]] $(G,T)$ where $T$ is a [[tree]] with at most one non-terminal vertex, such that $GL_2(R)$ is isomorphic to the [[fundamental group]] $\pi_1(G,T)$. 
 
 
 
==References==
 
* Mason, A.. "Serre's generalization of Nagao's theorem: an elementary approach". ''Transactions of the American Mathematical Society'' '''353''' (2001) 749–767. {{DOI|10.1090/S0002-9947-00-02707-0}} {{ZBL|0964.20027}}.
 
* Nagao, Hirosi.  "On $GL(2, K[x])$". J. Inst. Polytechn., Osaka City Univ., Ser. A '''10''' (1959) 117–121. {{MR|0114866}}.  {{ZBL|0092.02504}}.
 
* Serre, Jean-Pierre. ''Trees''. (Springer, 2003) ISBN 3-540-44237-5.
 
 
 
=Almost perfect number=
 
''Slightly defective number'' or ''least deficient number''
 
 
 
A [[natural number]] $n$ such that the [[sum]] of all [[divisor]]s of ''n'' (the [[sum-of-divisors function]] $\sigma(n)$) is equal to $2n − 1$.  The only known almost perfect numbers are the powers of 2 with non-negative exponents; however, it has not been shown that all almost perfect numbers are of this form.  It is known that an odd almost perfect number greater than 1 would have at least 6 prime factors.
 
 
 
If $m$ is an odd almost perfect number then $m(2m-1)$ is a [[Descartes number]].
 
 
 
==References==
 
* Kishore, Masao. "Odd integers N with five distinct prime factors for which 2−10−12 < σ(N)/N < 2+10−12". Mathematics of Computation '''32''' (1978) 303–309. ISSN 0025-5718. {{MR|0485658}}. {{ZBL|0376.10005}}
 
* Kishore, Masao. "On odd perfect, quasiperfect, and odd almost perfect numbers". Mathematics of Computation ''36''' (1981) 583–586. ISSN 0025-5718.  {{ZBL|0472.10007}}
 
* Banks, William D.; Güloğlu, Ahmet M.; Nevans, C. Wesley; Saidak, Filip. "Descartes numbers". In De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (edd), ''Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006''. CRM Proceedings and Lecture Notes '''46'''. (Providence, RI: American Mathematical Society, 2008). pp. 167–173. ISBN 978-0-8218-4406-9.  {{ZBL|1186.11004}}
 
* Guy, R. K. . "Almost Perfect, Quasi-Perfect, Pseudoperfect, Harmonic, Weird, Multiperfect and Hyperperfect Numbers". Unsolved Problems in Number Theory (2nd ed.). (New York: Springer-Verlag, 1994). pp. 16, 45–53
 
* Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, edd. (2006). Handbook of number theory I. (Dordrecht: Springer-Verlag, 2006). p.110. ISBN 1-4020-4215-9.  {{ZBL|1151.11300}}
 
* Sándor, Jozsef; Crstici, Borislav, edd. Handbook of number theory II. (Dordrecht: Kluwer Academic, 2004). pp.37–38. ISBN 1-4020-2546-7.  {{ZBL|1079.11001}}
 
 
 
 
 
=Erdős–Wintner theorem=
 
A result in [[probabilistic number theory]] characterising those [[additive function]]s that possess a limiting distribution.
 
 
 
==Limiting distribution==
 
A distribution function $F$ is a non-decreasing function from the real numbers to the unit interval [0,1] which is right-continuous and has limits 0  at $-\infty$ and 1 at $+\infty$.
 
 
 
Let $f$ be a complex-valued function on natural numbers.  We say that $F$ is a limiting distribution for $f$ if $F$ is a distribution function and the sequence $F_N$ defined by
 
  
 +
For positive real numbers there are mutually inverse [[exponential function, real|exponential]] and [[logarithmic function|logarithm]] functions which allow the alternative definition
 
$$
 
$$
F_n(t) = \frac{1}{N} | \{n \le N : |f(n)| \le t \} |
+
x^y = \exp(y \log x) \ .
 
$$
 
$$
 +
Here the exponential function may be regarded as $\exp(x) = e^x$ where [[E-number|$e$]] is the base of natural logarithms.
  
[[Weak convergence of probability measures|converges weakly]] to $F$.
+
===Complex numbers===
 +
Exponentiation of complex numbers with non-integer exponents may be defined using the complex [[exponential function]] and [[logarithmic function|logarithm]].  The exponential function is analytic and defined on the whole complex plane: the logarithmic function requires a choice of [[Branch of an analytic function|branch]], corresponding to a choice of the range of values for the [[argument]], to make it single-valued.  Given such a choice, exponentiation may be defined as $z^w = \exp(w \log z)$.  
  
==Statement of the theorem==
+
===General algebraic systems===
Let $f$ be an additive functionThere is a limiting distribution for $f$ if and only if the following three series converge:
+
For a general (not necessarily associative) binary operation, it is necessary to define the order of operationsThe left and right ''principal powers'' are defined inductively by
 
$$
 
$$
\sum_{|f(p)|>1} \frac{1}{p} \,,\ \sum_{|f(p)|\le1} \frac{f(p)}{p} \,,\ \sum_{|f(p)|\le1} \frac{f(p)^2}{p} \ .
+
x^{n+1} = x \star (x^n)
 
$$
 
$$
 
+
and
When these conditions are satisfied, the distribution is given by
 
 
$$
 
$$
F(t) = \prod_p \left({1 - \frac{1}{p} }\right) \cdot \left({1 + \sum_{k=1}^\infty p^{-k}\exp(i t f(p)^k) }\right) \ .
+
x^{n+1} = (x^n) \star x
 
$$
 
$$
 +
respectively.  A binary operation is [[power associativity|power associative]] if the powers of a single element form an associative subsystem, so that exponentiation is well-defined.
  
==References==
+
=Logarithm=
* Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. pp. 564–566. ISBN 1-4020-4215-9.  {{ZBL|1151.11300}}
+
The operation inverse to [[exponentiation]].
* 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}}
 
  
=Brauer–Wall group=
+
Over the fields of [[Real number|real]] or [[complex number]]s, one speaks of the [[logarithm of a number]]The [[logarithmic function]] is the complex analytic function inverse to the [[exponential function]].
A [[group]] classifying graded [[central simple algebra]]s over a fieldIt was first defined by Wall (1964) as a generalisation of the [[Brauer group]].
 
  
The Brauer group $\mathrm{B}(F)$ of a field $F$ is defined on the isomorphism classes of central simple algebras over ''F''.  The analogous construction for $\mathbf{Z}/2$-[[graded algebra]]s defines the Brauer–Wall group $\mathrm{BW}(F)$.{{cite|Lam (2005) pp.98–99}}
+
In a finite Abelian group, the [[discrete logarithm]] is the inverse to exponentiation, with applications in [[cryptography]].
  
==Properties==
+
The [[Zech logarithm]] in a finite field is related to the discrete logarithm.
* The Brauer group $\mathrm{BW}(F)$ injects into $\mathrm{BW}(F)$ by mapping a CSA $A$ to the graded algebra which is $A$ in grade zero.
 
  
There is an exact sequence
 
$$
 
0 \rightarrow \mathrm{B}(F) \rightarrow \mathrm{BW}(F) \rightarrow Q(F) \rightarrow 0
 
$$
 
where $Q(F)$ is the group of graded quadratic extensions of $F$, defined as $\mathbf{Z}/2 \times F^*/(F^*)^2$ with multiplication $(e,x)(f,y) = (e+f,(-1)^{ef}xy$. The map from W to BW is the '''[[Clifford invariant]]''' defined by mapping an algebra to the pair consisting of its grade and [[Determinant of a quadratic form|determinant]].
 
  
There is a map from the additive group of the [[Witt–Grothendieck ring]] to the Brauer–Wall group obtained by sending a quadratic space to its [[Clifford algebra]].  The map factors through the [[Witt group]]{{cite|Lam (2005) p.113}}  which has kernel $I^3$, where $I$ is the fundamental ideal of $W(F)$.{{cite|Lam (2005) p.115}}
 
  
==Examples==
+
=''I''-semigroup=
* $\mathrm{BW}(\mathbf{R})$ is isomorphic to $\mathbf{Z}/8$.  This is an algebraic aspect of [[Bott periodicity]].
+
A topological semigroup defined on a totally ordered set.  Let $I$ be a [[totally ordered set]] with minimum element $0$ and maximum element $1$, and equipped with the [[order topology]]; then $0$ acts as a zero (absorbing) element for the semigroup operation and $1$ acts as an identity (neutral) elementAlthough not required by the definition, it is the case that an ''I''-semigroup is commutative.
  
==References==
+
Examples.  The real interval $[0,1]$ under multiplication.  The ''nil interval'' $[\frac12,1]$ with operation $x \circ y = \max(xy,\frac12)$. The ''min interval'' $[0,1]$ with operation $x \cdot y = \min(x,y)$.
* Lam, Tsit-Yuen, ''Introduction to Quadratic Forms over Fields'', Graduate Studies in Mathematics '''67''', (American Mathematical Society, 2005) ISBN 0-8218-1095-2 {{MR|2104929}}, {{ZBL|1068.11023}}
 
* Wall, C. T. C., "Graded Brauer groups", ''Journal für die reine und angewandte Mathematik'' '''213''' (1964) 187–199, ISSN 0075-4102, {{ZBL|0125.01904}}, {{MR|0167498}}
 
  
=Barban–Davenport–Halberstam theorem=
 
A statement about the distribution of [[prime number]]s in an [[arithmetic progression]].  It is known that in the long run primes are distributed equally across possible progressions with the same difference.  Theorems of the Barban–Davenport–Halberstam type give estimates for the error term, determining how close to uniform the distributions are.
 
  
Let $a$ be coprime to $k$ and
+
====References====
$$
+
* Hofmann, K.H.; Lawson, J.D. "Linearly ordered semigroups: Historical origins and A. H. Clifford’s influence" ''in'' Hofmann, Karl H. (ed.) et al., ''Semigroup theory and its applications. Proceedings of the 1994 conference commemorating the work of Alfred H. Clifford'' London Math. Soc. Lecture Note Series '''231''' Cambridge University Press (1996) pp.15-39  {{ZBL|0901.06012}}
\vartheta(x;a,k) = \sum_{p<x \,;\, p \equiv a \bmod k} \log p
 
$$
 
be a weighted count of primes in the arithmetic progression $a$ modulo $k$. We have
 
$$
 
\vartheta(x;a,k) = \frac{x}{\phi(k)} + E(x;a,k)
 
$$
 
where the error term $E$ is small compared to $x$We take a square sum of error terms
 
$$
 
G(x,Q) = \sum_{k < Q} \sum_{a \bmod k} E^2(x;a,k) .
 
$$
 
Then we have
 
$$
 
G(x,Q) = O(Q x \log x) + O(x \log^{-A} x)
 
$$
 
for any positive $A$. 
 
  
This form of the theorem is due to Gallagher.  The result of Barban is valid only for $Q < x \log^{-B} x$ for some $B$ depending on $A$, and the result of Davenport–Halberstam has $B = A+5$.
+
=Composition algebra=
 +
An algebra $A$ (not necessarily associative) over a field $K$ with a [[quadratic form]] $q$ taking values in $K$ which is multiplicative, $q(x\cdot y) = q(x) q(y)$.  The composition algebras over the field $\mathbf{R}$ of [[real number]]s are the real numbers, the field of [[complex number]]s $\mathbf{C}$, the [[skew-field]] of [[quaternion]]s, the non-associative algebra of [[octonions]].
  
==See also==
+
====References====
* [[Bombieri–Vinogradov theorem]]
+
* Springer, Tonny A.; Veldkamp, Ferdinand D. ''Octonions, Jordan algebras and exceptional groups''. Springer Monographs in Mathematics. Springer (2000) ISBN 3-540-66337-1 {{ZBL|1087.17001}}
* [[Elliott–Halberstam conjecture]]
 
 
 
==References==
 
* Hooley, C. "On theorems of Barban-Davenport-Halberstam type". In Bennett, M. A.; Berndt, B.C.; Boston, N.; Diamond, H.G.; Hildebrand, A.J.; Philipp, W. (edd) ''Surveys in number theory: Papers from the millennial conference on number theory''. (Natick, MA: A K Peters, 2002) pp. 75–108. ISBN 1-56881-162-4. {{ZBL|1039.11057}}.
 
 
 
=Arithmetic number=
 
An [[integer]] for which the [[arithmetic mean]] of its [[positive number|positive]] [[divisor]]s,  is an integer.  The first numbers in the [[sequence]] are 1, 3, 5, 6, 7, 11, 13, 14, 15, 17, 19, 20 {{OEIS|id=A003601}}.  It is known that the [[natural density]] of such numbers is 1:{{cite|Guy (2004) p.76}} indeed, the proportion of numbers less than ''X'' which are not arithmetic is [[Asymptotic analysis|asymptotically]]{{cite|Bateman et al (1981)}}
 
$$
 
\exp\left( { -c \sqrt{\log\log X} } \right)
 
$$
 
where $c = 2\sqrt{\log 2} + o(1)$.
 
  
A number $N$ is arithmetic if the [[number of divisors]] $d(N)$ divides the [[Sum-of-divisors function|sum of divisors]] $\sigma(N)$. The [[Natural density|density]] of integers $N$ for which $d(N)^2$ divides  $\sigma(N)$ is 1/2.
 
  
==References==
 
* Bateman, Paul T.; Erdős, Paul; Pomerance, Carl; Straus, E.G. (1981). "The arithmetic mean of the divisors of an integer". In Knopp, M.I.. ''Analytic number theory, Proc. Conf., Temple Univ., 1980''. Lecture Notes in Mathematics '''899''' (Springer-Verlag, 1981) pp. 197–220. {{ZBL|0478.10027}}
 
* Guy, Richard K. ''Unsolved problems in number theory'' (3rd ed.). (Springer-Verlag, 2004).  ISBN 978-0-387-20860-2, {{ZBL|1058.11001}}.  Section B2.
 
  
=Factor system=
 
A function on a [[group]] giving the data required to construct an [[algebra]].  A factor system constitutes a realisation of the cocycles in the second [[cohomology group]] in [[group cohomology]].
 
  
Let $G$ be a group and $L$ a field on which $G$ acts as automorphismsA ''cocycle'' or ''factor system'' is a map $c : G \times G \rightarrow L^*$ satisfying
+
=Cayley–Dickson process=
$$
+
A construction of an algebra $A_1$ from an algebra $A$ with involution over a field $K$ which generalises the construction of the [[complex number]]s, [[quaternion]]s and [[octonion]].  Fix a parameter $d \in A$.  As a set $A_1 = A \times A$ with addition defined by $(a_1,a_2) + (b_1,b_2) = (a_1+b_1, a_2+b_2)$ and multiplication by
c(h,k)^g c(hk,g) = c(h,kg) c(k,g) \ .
 
 
$$
 
$$
 +
(a_1,a_2) \cdot (b_1,b_2) = (a_1b_1 - d b_2 a_2^* , a_1^*b_2 + b_1a_2) \ .
 +
$$
 +
The algebra $A_1$ has an involution $(x_1,x_2) \mapsto (x_1^*,-x_2)$. 
 +
  
Cocycles are ''equivalent'' if there exists some system of elements $a : G \rightarrow L^*$ with
+
=Free differential calculus=
 +
Let $F$ be a [[free group]] on a set of generators $X = \{x_i : i \in I \}$ and $R[F]$ the [[group ring]] of $F$ over a commutative unital ring $R$.  The ''Fox derivative'' $\partial_i$ are maps from $F$ to $R[F]$ defined by
 
$$
 
$$
c'(g,h) = c(g,h) (a_g^h a_h a_{gh}^{-1}) \ .
+
\partial_i(x_j) = \delta_{ij} \ ,
 
$$
 
$$
 
Cocycles of the form
 
 
$$
 
$$
c(g,h) = a_g^h a_h a_{gh}^{-1}
+
\partial_i(1) = 0 \ ,
 
$$
 
$$
are called ''split''.  Cocycles under multiplication modulo split cocycles form a group, the second cohomology group $H^2(G,L^*)$.
 
 
==Crossed product algebras==
 
Let us take the case that $G$ is the [[Galois group]] of a [[field extension]] $L/K$.  A factor system $c$ in $H^2(G,L^*)$ gives rise to a ''crossed product algebra'' $A$, which is a $K$-algebra containing $L$ as a subfield, generated by the elements $\lambda \in L$ and $u_g$ with multiplication
 
 
$$
 
$$
\lambda u_g = u_g \lambda^g \ ,
+
\partial_i(uv) = u \partial_i(v) + \partial_i(u) v \ .
 
$$
 
$$
 +
It follows that
 
$$
 
$$
u_g u_h = u_{gh} c(g,h) \ .
+
\partial_i(x_i^{-1}) = - x_i^{-1} \ .
 
$$
 
$$
Equivalent factor systems correspond to a change of basis in $A$ over $K$.  We may write
 
$$ A = (L,G,c) \ .$$
 
  
Every [[central simple algebra]] over$K$ that splits over $L$ arises in this wayThe tensor product of algebras corresponds to multiplication of the corresponding elements in$H^2$. We thus obtain an identification of the [[Brauer group]], where the elements are classes of CSAs over $K$, with $H^2$.{{cite|Saltman (1999) p.44}}
+
The maps extend to [[derivation]]s on $R[F]$.   
 +
 
 +
===References===
 +
* D. L. Johnson, ''Presentations of Groups'', London Mathematical Society Student Texts '''15''' Cambridge University Press (1997) ISBN 0-521-58542-2
  
==Cyclic algebra==
+
=Martin's axiom=
Let us further restrict to the case that $L/K$ is [[Cyclic extension|cyclic]] with Galois group $G$ of order $n$ generated by $t$.  Let $A$ be a crossed product $(L,G,c)$ with factor set $c$.  Let $u=u_t$ be the generator in $A$ corresponding to $t$.  We can define the other generators
+
An axiom of set theory.  Let $(P,{<})$ be a [[partially ordered set]] satisfying the [[countable chain condition]] and $D$ a family of $\mathfrak{k}$ dense subsets of $P$ for $\mathfrak{k}$ a cardinal less than $2^{\aleph_0}$.  Then $\text{MA}_{\mathfrak{k}}$ asserts that there is a $D$-generic filter on $P$.  Martin's axiom $\text{MA}$ is the conjunction of $\text{MA}_{\mathfrak{k}}$ for all $\mathfrak{k} < 2^{\aleph_0}$.
$$
 
u_{t^i} = u^i
 
$$
 
and then we have $u^n = a$ in $K$.  This element $a$ specifies a cocycle $c$ by
 
$$
 
c(t^i,t^j) = \begin{cases} 1 & \text{if } i+j < n, \\ a & \text{if } i+j \ge n. \end{cases}  
 
$$
 
  
It thus makes sense to denote $A$ simply by $(L,t,a)$.  However $a$ is not uniquely specified by $A$ since we can multiply $u$ by any element $\lambda$ of $L^*$ and then $a$ is multiplied by the product of the conjugates of λ.  Hence $A$ corresponds to an element of the norm residue group
+
The case $\text{MA}_{\aleph_0}$ holds in [[ZFC]]MA is a consequence of the [[Continuum hypothesis]] ($\text{CH}$) but $\text{MA} \wedge \text{CH}$ is consistent with ZFC if ZFC is consistent.
$(K^*/N_{L/K}L^*$.  We obtain the isomorphisms
 
$$
 
\mathop{Br}(L/K) \equiv K^*/\mathop{N}_{L/K} L^* \equiv \mathop{H}^2(G,L^*) \ .
 
$$
 
  
==References==
+
====References====
* Lorenz, Falko (2008). Algebra. Volume II: Fields with Structure, Algebras and Advanced Topics. Universitext. Translated from the German by Silvio Levy. With the collaboration of the translator. Springer-Verlag. ISBN 978-0-387-72487-4. Zbl 1130.12001.
+
* Thomas Jech, ''Set Theory'', Perspectives in Mathematical Logic, Third Millennium Edition, revised and expanded. Springer (2007) ISBN 3-540-44761-X
* Saltman, David J. (1999). Lectures on division algebras. Regional Conference Series in Mathematics 94. Providence, RI: American Mathematical Society. ISBN 0-8218-0979-2. Zbl 0934.16013.
 

Latest revision as of 19:18, 29 January 2018

Eulerian number

A combinatorial counting function for the number of descents in a permutation. Here we take a permutation $(a_1,\ldots,a_n)$ of $(1,\ldots,n)$ and count as a descent any $i$ such that $a_i > a_{i+1}$. We let $$ \left\langle{ n \atop k }\right\rangle $$ denote the number of permutations on $n$ elements with $k$ descents. It satisfies the recurrence relation $$ \left\langle{ n \atop k }\right\rangle = (n-k) \left\langle{ n-1 \atop k-1 }\right\rangle + (k+1) \left\langle{ n-1 \atop k }\right\rangle $$

The Eulerian polynomial is the generating function $$ S_n(t) = \sum_{k=0}^n \left\langle{ n \atop k }\right\rangle t^k \ . $$ The recurrence relation may be written as $$ S_{n+1}(t) = (1+nt) S_n(t) + t(1-t)S'_n(t) \ . $$

The Eulerian numbers appear in a related context. We define an excedance of a permutation to be the number of $i$ such that $a(i) > i$ (weak if $a_i \ge i$). Then the number of permutations with $k$ excendances is equal to the number with $k+1$ weak excedances, and is in turn equal to $\left\langle{ n \atop k }\right\rangle$.

References

  • T. Kyle Petersen Eulerian Numbers Birkhäuser (2015) ISBN 1-4939-3091-5 Zbl 06467929
  • Richard P. Stanley Enumerative combinatorics I Wadsworth & Brooks/Cole (1986) ISBN 0-534-06546-5 0608.05001 Zbl 0608.05001

Lattice valuation

A function $\nu$ on a lattice $L$ with values in a ring $R$ satisfying $$ \nu(x \wedge y) + \nu(x \vee y) = \nu(x) + \nu(y) \ . $$


References

  • Rota, Gian-Carlo (with P. Doubilet, C. Greene, D. Kahaner, A: Odlyzko and R. Stanley) Finite operator calculus Academic Press (1975) ISBN 0-12-596650-4 Zbl 0328.05007


Series-parallel graph

A class of graphs related to ideas from electrical networks. It is convenient to take "graph" to mean unoriented graph allowing loops and multiple edges. A two-terminal series-parallel graph $(G,h,t)$ has two distinguished vertices, source $h$ and sink $t$ (or "head and "tail"). The class is built recursively from the single edge $P_2 = ((\{h,t\}, \{ht\}), h,t)$ with $h$ as head and $t$ as tail, using the operations of series and parallel combination. It is assumed that the graphs to be combined have disjoint vertex sets. The series combination of $(G_1, h_1,t_1)$ and $(G_2, h_2,t_2)$ is the graph obtained by identifying $t_1$ with $h_2$ and taking $h_1$ as head and $t_2$ as tail. The parallel combination of $(G_1, h_1,t_1)$ and $(G_2, h_2,t_2)$ is the graph obtained by identifying $h_1$ with $h_2$ and $t_1$ with $t_2$ then taking $h_1=h_2$ as head and $t_1=t_2$ as tail.

...

Series-parallel graphs are characterised by having no subgraph homeomorphic to $K_4$, the complete graph on $4$ vertices.

References

  • Andreas Brandstädt, Van Bang Le; Jeremy P. Spinrad, "Graph classes: a survey". SIAM Monographs on Discrete Mathematics and Applications 3. Society for Industrial and Applied Mathematics (1999) ISBN 978-0-898714-32-6 Zbl 0919.05001

Polarity

A correspondence derived from a binary relation between two sets, introduced by G. Birkhoff: a special case of a Galois correspondence. Let $R$ be a relation from $A$ to $B$, equivalently a subset of $A \times B$. Define polar maps between the power sets, $F : \mathcal{P}A \rightarrow \mathcal{P}B$ and $G : \mathcal{P}B \rightarrow \mathcal{P}A$ by $$ F(U) = \{ b \in B : aRb\ \text{for all}\ a \in U \} $$ and $$ G(V) = \{ a \in A : aRb\ \text{for all}\ b \in V \} \ . $$

Make $\mathcal{P}A$, $\mathcal{P}B$ partially ordered sets by subset inclusion. Then $F$ and $G$ are order-reversing maps, and $FG$ and $GF$ are order-preserving (monotone). Indeed, $F$ and $G$ are quasi-inverse, that is, $FGF = F$ and $GFG = G$; hence $FG$ and $GF$ are closure operators.

The closed pairs $(U,V)$ with $V = F(U)$ and $U = G(V)$ may be ordered by $(U_1,V_1) \le (U_2,V_2) \Leftrightarrow U_1 \subseteq U_2 \Leftrightarrow V_1 \supseteq V_2$. This ordered set, denoted $\mathfrak{B}(A,B,R)$, is a complete lattice with $$ \bigwedge_{i \in I} (U_i,V_i) = \left({ \bigcap_{i\in I} U_i, FG\left({ \bigcup_{i \in I} V_i }\right) }\right) $$ and $$ \bigvee_{i \in I} (U_i,V_i) = \left({ GF\left({ \bigcup_{i \in I} U_i }\right), \bigcap_{i\in I} V_i }\right) \ . $$

Every complete lattice $L$ arises in this way: indeed, $L = \mathfrak{B}(L,L,{\le})$.

References

  • Birkhoff, Garrett Lattice theory American Mathematical Society (1940) Zbl 0063.00402
  • Davey, B.A.; Priestley, H.A. Introduction to lattices and order (2nd ed.) Cambridge University Press (2002) ISBN 978-0-521-78451-1 Zbl 1002.06001

Frame

A generalisation of the concept of topological space occurring in the theory of logic and computation.

A frame is a complete lattice $(X,{\le})$ (a lattice with all meets and joins) satisfying the frame distributivity law, that binary meets distribute over arbitrary joins: $$ x \wedge \bigvee \{ y \in Y \} = \bigvee \{ x \wedge y : y \in Y \} \ . $$

The powerset $\mathcal{P}(A)$ of a set $A$ forms a frame.

If $(X,\mathfrak{T})$ is a topological space, with $\mathfrak{T}$ the collection of open sets, then $\mathfrak{T}$ forms a subframe of $\mathcal{P}(X)$: it should be noted that whereas the join is set-theoretic union, the meet operation is given by $$ \bigwedge \{ S \} = \mathrm{Int}\left({ \bigcap \{ S \} }\right) $$ where $\mathrm{Int}$ denotes the interior.

References

[1] Steven Vickers Topology via Logic Cambridge Tracts in Theoretical Computer Science 5 Cambridge University Press (1989) ISBN 0-521-36062-5 Zbl 0668.54001
[2] Jonathan S. Golan Semirings and their Applications Springer (2013) ISBN 9401593337

Alexandrov topology

on a partially ordered set $(X,{\le})$

A topology which is discrete in the broad sense, that arbitrary unions and intersections of open sets are open. Define an upper set $U \subseteq X$ to be one for which $u \in U$ and $u \le x$ implies $x \in U$. The Alexandrov topology on $X$ is that for which all upper sets are open.

The Alexandrov topology makes $X$ a T0 space and the specialisation order is just the original order ${\le}$ on $X$.

References

  • Johnstone, Peter T. Stone spaces Cambridge Studies in Advanced Mathematics 3 Cambridge University Press(1986) Zbl 0586.54001

Exponentiation

The algebraic and analytic operations generalising the operation of repeated multiplication in number systems.

For positive integer $n$, the operation $x \mapsto x^n$ may be defined on any system of numbers by repeated multiplication $$ x^n = x \cdot x \cdot \cdots \cdot x\ \ \ (n\,\text{times}) $$ where $\cdot$ denotes multiplication. The number $n$ is the exponent in this operation.

The repeated operations may be carried out in any order provided that multiplication is associative, $x \cdot (y \cdot z) = (x \cdot y) \cdot z$. In this case we have $$ x^{m+n} = x^m \cdot x^n \ . $$

If the operation is also commutative then we have $$ (x \cdot y)^n = x^n \cdot y^n \ . $$

We may extend the definition to non-positive integer powers by defining $x^0 = 1$ and $$ x^{-n} = \frac{1}{x^n} $$ whenever this makes sense.

We may extend the definition to rational number exponents by taking $x^{1/n}$ to be any number $y$ such that $y^n = x$: this may denote none, one or more than one number.

Positive real numbers

Exponentiation of positive real numbers by rational exponents may be defined by taking $x^{1/n}$ to be the unique positive real solution of $y^n = x$: this always exists. We thus have $x^q$ well-defined for $x>0$ and any rational exponent $q$. Exponentiation preserves order: if $x > y$ then $x^q > y^q$ if $q > 0$ and $x^q < y^q$ if $q < 0$.

We can now define exponentiation with real exponent $r$ by defining $x^r$ to be the limit of $x^{q_n}$ where $q_n$ is a sequence of rational numbers converging to $r$. There is always such a sequence, and the limit exists and does not depend on the chosen sequence.

For positive real numbers there are mutually inverse exponential and logarithm functions which allow the alternative definition $$ x^y = \exp(y \log x) \ . $$ Here the exponential function may be regarded as $\exp(x) = e^x$ where $e$ is the base of natural logarithms.

Complex numbers

Exponentiation of complex numbers with non-integer exponents may be defined using the complex exponential function and logarithm. The exponential function is analytic and defined on the whole complex plane: the logarithmic function requires a choice of branch, corresponding to a choice of the range of values for the argument, to make it single-valued. Given such a choice, exponentiation may be defined as $z^w = \exp(w \log z)$.

General algebraic systems

For a general (not necessarily associative) binary operation, it is necessary to define the order of operations. The left and right principal powers are defined inductively by $$ x^{n+1} = x \star (x^n) $$ and $$ x^{n+1} = (x^n) \star x $$ respectively. A binary operation is power associative if the powers of a single element form an associative subsystem, so that exponentiation is well-defined.

Logarithm

The operation inverse to exponentiation.

Over the fields of real or complex numbers, one speaks of the logarithm of a number. The logarithmic function is the complex analytic function inverse to the exponential function.

In a finite Abelian group, the discrete logarithm is the inverse to exponentiation, with applications in cryptography.

The Zech logarithm in a finite field is related to the discrete logarithm.


I-semigroup

A topological semigroup defined on a totally ordered set. Let $I$ be a totally ordered set with minimum element $0$ and maximum element $1$, and equipped with the order topology; then $0$ acts as a zero (absorbing) element for the semigroup operation and $1$ acts as an identity (neutral) element. Although not required by the definition, it is the case that an I-semigroup is commutative.

Examples. The real interval $[0,1]$ under multiplication. The nil interval $[\frac12,1]$ with operation $x \circ y = \max(xy,\frac12)$. The min interval $[0,1]$ with operation $x \cdot y = \min(x,y)$.


References

  • Hofmann, K.H.; Lawson, J.D. "Linearly ordered semigroups: Historical origins and A. H. Clifford’s influence" in Hofmann, Karl H. (ed.) et al., Semigroup theory and its applications. Proceedings of the 1994 conference commemorating the work of Alfred H. Clifford London Math. Soc. Lecture Note Series 231 Cambridge University Press (1996) pp.15-39 Zbl 0901.06012

Composition algebra

An algebra $A$ (not necessarily associative) over a field $K$ with a quadratic form $q$ taking values in $K$ which is multiplicative, $q(x\cdot y) = q(x) q(y)$. The composition algebras over the field $\mathbf{R}$ of real numbers are the real numbers, the field of complex numbers $\mathbf{C}$, the skew-field of quaternions, the non-associative algebra of octonions.

References

  • Springer, Tonny A.; Veldkamp, Ferdinand D. Octonions, Jordan algebras and exceptional groups. Springer Monographs in Mathematics. Springer (2000) ISBN 3-540-66337-1 Zbl 1087.17001



Cayley–Dickson process

A construction of an algebra $A_1$ from an algebra $A$ with involution over a field $K$ which generalises the construction of the complex numbers, quaternions and octonion. Fix a parameter $d \in A$. As a set $A_1 = A \times A$ with addition defined by $(a_1,a_2) + (b_1,b_2) = (a_1+b_1, a_2+b_2)$ and multiplication by $$ (a_1,a_2) \cdot (b_1,b_2) = (a_1b_1 - d b_2 a_2^* , a_1^*b_2 + b_1a_2) \ . $$ The algebra $A_1$ has an involution $(x_1,x_2) \mapsto (x_1^*,-x_2)$.


Free differential calculus

Let $F$ be a free group on a set of generators $X = \{x_i : i \in I \}$ and $R[F]$ the group ring of $F$ over a commutative unital ring $R$. The Fox derivative $\partial_i$ are maps from $F$ to $R[F]$ defined by $$ \partial_i(x_j) = \delta_{ij} \ , $$ $$ \partial_i(1) = 0 \ , $$ $$ \partial_i(uv) = u \partial_i(v) + \partial_i(u) v \ . $$ It follows that $$ \partial_i(x_i^{-1}) = - x_i^{-1} \ . $$

The maps extend to derivations on $R[F]$.

References

  • D. L. Johnson, Presentations of Groups, London Mathematical Society Student Texts 15 Cambridge University Press (1997) ISBN 0-521-58542-2

Martin's axiom

An axiom of set theory. Let $(P,{<})$ be a partially ordered set satisfying the countable chain condition and $D$ a family of $\mathfrak{k}$ dense subsets of $P$ for $\mathfrak{k}$ a cardinal less than $2^{\aleph_0}$. Then $\text{MA}_{\mathfrak{k}}$ asserts that there is a $D$-generic filter on $P$. Martin's axiom $\text{MA}$ is the conjunction of $\text{MA}_{\mathfrak{k}}$ for all $\mathfrak{k} < 2^{\aleph_0}$.

The case $\text{MA}_{\aleph_0}$ holds in ZFC. MA is a consequence of the Continuum hypothesis ($\text{CH}$) but $\text{MA} \wedge \text{CH}$ is consistent with ZFC if ZFC is consistent.

References

  • Thomas Jech, Set Theory, Perspectives in Mathematical Logic, Third Millennium Edition, revised and expanded. Springer (2007) ISBN 3-540-44761-X
How to Cite This Entry:
Richard Pinch/sandbox. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox&oldid=34626