|
|
| (106 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| − | =Schroeder–Bernstein theorem= | + | =Eulerian number= |
| − | ''Cantor–Bernstein theorem'' | + | 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 |
| | + | $$ |
| | | | |
| − | For sets $A$ and $B$, if there are [[injection]]s from $A$ to $B$ and from $B$ to $A$ (equivalently, each is equipotent to a subset of the other), then there is a bijection between $A$ and $B$ (they are equipotent).
| + | 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) \ . |
| | + | $$ |
| | | | |
| − | In cardinal arithmetic, if we let $\mathfrak{a} \le \mathfrak{b}$ denote the property that some set of cardinality $\mathfrak{a}$ has an injection to a set of cardinality $\mathfrak{b}$, then $\mathfrak{a} \le \mathfrak{b}$ and $\mathfrak{b} \le \mathfrak{a}$ implies $\mathfrak{a} = \mathfrak{b}$.
| + | 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$. |
| − | | |
| − | The theorem was conjectured by Georg Cantor by 1895 and proved by Felix Bernstein in 1897. Dedekind obtained a further proof in 1897. Schroeder proof of 1898 was found to be flawed by 1902.
| |
| | | | |
| | ====References==== | | ====References==== |
| − | * P. R. Halmos, "Naive Set Theory", Springer (1960) ISBN 0-387-90092-6 | + | * T. Kyle Petersen ''Eulerian Numbers'' Birkhäuser (2015) ISBN 1-4939-3091-5 {{ZBL|06467929}} |
| − | * Michael Potter, "Set Theory and its Philosophy : A Critical Introduction", Oxford University Press (2004) ISBN 0-19-155643-2 | + | * Richard P. Stanley ''Enumerative combinatorics'' '''I''' Wadsworth & Brooks/Cole (1986) ISBN 0-534-06546-5 {{ZBL| 0608.05001}} |
| − | | |
| − | =Hurwitz zeta function=
| |
| − | ''generalised zeta function''
| |
| − | | |
| − | An [[Dirichlet series]] related to the [[Riemann zeta function]] which may be used to exhibit properties of various [[Dirichlet L-function]]s.
| |
| | | | |
| − | The Hurwitz zeta function $\zeta(\alpha,s)$ is defined for real $\alpha$, $0 < \alpha \le 1$ as
| + | =Lattice valuation= |
| | + | A function $\nu$ on a [[lattice]] $L$ with values in a [[ring]] $R$ satisfying |
| | $$ | | $$ |
| − | \zeta(\alpha,s) = \sum_{n=0}^\infty (n+\alpha)^{-s} \ . | + | \nu(x \wedge y) + \nu(x \vee y) = \nu(x) + \nu(y) \ . |
| | $$ | | $$ |
| − | The series is convergent, and defines an analytic function, for $\Re s > 1$. The function possesses an [[analytic continuation]] to the whole $s$-plane except for a simple pole of residue 1 at $s=1$.
| |
| | | | |
| − | ==References==
| |
| − | * Tom M. Apostol, "Introduction to Analytic Number Theory", Undergraduate Texts in Mathematics, Springer (1976) ISBN 0-387-90163-9 {{ZBL|0335.10001}}
| |
| | | | |
| | | | |
| − | =Formal Dirichlet series= | + | ====References==== |
| − | A formal Dirichlet series over a ring $R$ is associated to a function $a$ from the positive integers to $R$ | + | * 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}} |
| − | | |
| − | :<math> L(a,s) = \sum_{n=1}^\infty a(n) n^{-s} \ </math>
| |
| − | | |
| − | with addition and multiplication defined by
| |
| | | | |
| − | :<math> L(a,s) + L(b,s) = \sum_{n=1}^\infty (a+b)(n) n^{-s} \ </math>
| |
| − | :<math> L(a,s) \cdot L(b,s) = \sum_{n=1}^\infty (a*b)(n) n^{-s} \ </math>
| |
| | | | |
| − | where
| |
| | | | |
| − | :<math> (a+b)(n) = a(n)+b(n) \ </math>
| + | =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. |
| | | | |
| − | is the [[pointwise operation|pointwise]] sum and
| + | ... |
| | | | |
| − | :<math> (a*b)(n) = \sum_{k|n} a(k)b(n/k) \ </math>
| + | Series-parallel graphs are characterised by having no subgraph homeomorphic to $K_4$, the [[complete graph]] on $4$ vertices. |
| − | | |
| − | is the [[Dirichlet convolution]] of ''a'' and ''b''.
| |
| − | | |
| − | The formal Dirichlet series form a ring $\Omega$, indeed an $R$-algebra, with the zero function as additive zero element and the function $\delta$ defined by $\delta(1)=1$, $\delta(n)=0$ for $n>1$ (so that $D(\delta,s)=1$) as multiplicative identity. An element of this ring is invertible if $a(1)$ is invertible in $R$. If $R$ is commutative, so is $\Omega$; if $R$ is an integral domain, so is $\Omega$. The non-zero multiplicative functions form a subgroup of the group of units of $\Omega$.
| |
| − | | |
| − | The ring of formal Dirichlet series over $\mathbb{C}$ is isomorphic to a ring of formal power series in countably many variables.
| |
| − | | |
| − | The function $a$ is [[Multiplicative arithmetic function|multiplicative]] if and only if there is a formal [[Euler identity]] beween the Dirichlet series $D(a,s)$ and a formal [[Euler product]] over primes
| |
| − | $$
| |
| − | L(a,s) = \sum_n a_n n^{-s} = \prod_p (1+a_p p^{-s} + a_{p^2} p^{-2s} + \cdots )
| |
| − | $$ | |
| − | and is [[totally multiplicative]] if the Euler product is of the form
| |
| − | $$
| |
| − | L(a,s) = \sum_n a_n n^{-s} = \prod_p (1 - a_p p^{-s})^{-1} \ .
| |
| − | $$
| |
| | | | |
| | ==References== | | ==References== |
| − | * E.D. Cashwell, C.J. Everett,. "The ring of number-theoretic functions", ''Pacific J. Math.'' '''9''' (1959) 975-985 {{ZBL|0092.04602}} {{MR|0108510}} | + | * 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}} |
| − | * Henri Cohen, "Number Theory: Volume II: Analytic and Modern Tools", Graduate Texts in Mathematics '''240''', Springer (2008) ISBN 0-387-49894-X {{ZBL|1119.11002}}
| |
| − | * Gérald Tenenbaum, "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}}
| |
| − | | |
| − | =Isomorphism theorems=
| |
| − | Three theorems relating to [[homomorphism]]s of general [[algebraic system]]s.
| |
| | | | |
| − | ==First Isomorphism Theorem== | + | =Polarity= |
| − | Let $f : A \rightarrow B$ be a [[homomorphism]] of $\Omega$-algebras and $Q$ the [[Kernel of a function|kernel]] of $f$, as an [[equivalence relation]] on $A$. Then $Q$ is a [[Congruence (in algebra)|congruence]] on $A$, and $f$ can be factorised as $f = \epsilon f' \mu$ where $\epsilon : A \rightarrow A/Q$ is the quotient map, $f' : A/Q \rightarrow f(A)$ and $\mu : f(A) \rightarrow B$ is the inclusion map. The theorem asserts that $f'$ is well-defined and an isomorphism.
| |
| | | | |
| − | ==Second Isomorphism Theorem==
| + | 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 $Q$ be a congruence on the $\Omega$-algebra $A$ and let $A_1$ be a subalgebra of $A$. The saturation $A_1^Q$ is a subalgebra of $A$, the restriction $Q_1 = Q \ \cap A_1 \times A_1$ is a congruence on $A_1$ and there is an isomorphism | |
| | $$ | | $$ |
| − | A_1 / Q_1 \cong A_1^Q / Q \ .
| + | F(U) = \{ b \in B : aRb\ \text{for all}\ a \in U \} |
| | $$ | | $$ |
| − | | + | and |
| − | ==Third Isomorphism Theorem==
| |
| − | Let $A$ be an $\Omega$-algebra and $Q \subset R$ congruences on $A$. There is a unique homomorphism $\theta$ from $A/Q \rightarrow A/R$ compatible with the quotient maps from $A$ to $A/R$ and $A/Q$. If $R/Q$ denotes the [[Kernel of a function|kernel]] of $\theta$ on $A/Q$ then there is an isomorphism
| |
| | $$ | | $$ |
| − | (A/Q)/(R/Q) \cong A/R \ . | + | G(V) = \{ a \in A : aRb\ \text{for all}\ b \in V \} \ . |
| | $$ | | $$ |
| | | | |
| − | ==Application to groups==
| + | 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. |
| − | In the case of [[group]]s, a congruence $Q$ on $G$ is determined by the congruence class $N = [1_G]_Q$ of the identity $1_G$, which is a [[normal subgroup]], and the other $Q$-classes are the cosets of $N$. It is conventional to write $G/N$ for $G/Q$. The saturation of a subgroup $H$ is the complex $H^Q = HN$.
| |
| | | | |
| − | ===First Isomorphism Theorem for groups===
| + | 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 |
| − | Let $f : A \rightarrow B$ be a [[homomorphism]] of groups and $N = f^{-1}(1_B)$ the [[Kernel of a morphism in a category|kernel]] of $f$. Then $N$ is a normal subgroup of $A$, and $f$ can be factorised as $f = \epsilon f' \mu$ where $\epsilon : A \rightarrow A/N$ is the quotient map, $f' : A/N \rightarrow f(A)$ and $\mu : f(A) \rightarrow B$ is the inclusion map. The theorem asserts that $f'$ is well-defined and an isomorphism.
| |
| − | | |
| − | ===Second Isomorphism Theorem for groups===
| |
| − | Let $N$ be a normal subgroup $A$ and let $A_1$ be a subgroup of $A$. The complex $NA_1$ is a subgroup of $A$, the intersection $N_1 = N \cap A_1$ is a normal subgroup o $A_1$ and there is an isomorphism
| |
| | $$ | | $$ |
| − | A_1 / N_1 \cong A_1N/N \ .
| + | \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 |
| − | ===Third Isomorphism Theorem for groups===
| |
| − | Let $A$ be a group and $N \subset M$ normal subgroups of $A$. There is a unique homomorphism $\theta$ from $A/N \rightarrow A/M$ compatible with the quotient maps from $A$ to $A/N$ and $A/M$. The set $M/N$ is the kernel of $\theta$ and hence a normal subgroup of $A/N$ and there is an isomorphism
| |
| | $$ | | $$ |
| − | (A/N)/(M/N) \cong A/M \ . | + | \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) \ . |
| | $$ | | $$ |
| | | | |
| − | ==References==
| + | Every complete lattice $L$ arises in this way: indeed, $L = \mathfrak{B}(L,L,{\le})$. |
| − | * Paul M. Cohn, ''Universal algebra'', Kluwer (1981) ISBN 90-277-1213-1
| |
| − | | |
| − | =Dilworth number=
| |
| − | A numerical invariant of a [[graph]] (cf. [[Graph, numerical characteristics of a]]). The Dilworth number of the graph $G$ is the maximum number of vertices in a set $D$ for which the neighbourhoods form a [[Sperner family]]: for any pair of such vertices $x,y \in D$, the neighbourhoods $N(x)$, $N(y)$ each has at least one element not contained in the other. It is the [[Width of a partially ordered set|width]] of the set of neighbourhoods partially ordered by inclusion.
| |
| − | | |
| − | The [[diameter]] of a graph exceeds its Dilworth number by at most 1.
| |
| − | | |
| − | There is a polynomial time algorithm for computing the Dilworth number of a finite graph.
| |
| | | | |
| | ==References== | | ==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}} | + | * 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}} |
| | | | |
| − | =Quaternion algebra= | + | =Frame= |
| − | An associative algebra over a field that generalises the construction of the [[quaternion]]s over the field of real numbers.
| + | A generalisation of the concept of topological space occurring in the theory of logic and computation. |
| | | | |
| − | The quaternion algebra $(a,b)_F$ over a field $F$ is the four-dimensional vector space with basis $\mathbf{1}, \mathbf{i}, \mathbf{j}, \mathbf{k}$ and multiplication defined by
| + | 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: |
| | $$ | | $$ |
| − | \mathbf{i}^2 = a\mathbf{1},\ \ \mathbf{j}^2 = b\mathbf{1},\ \ \mathbf{i}\mathbf{j} = -\mathbf{j}\mathbf{i} = \mathbf{k}\ . | + | x \wedge \bigvee \{ y \in Y \} = \bigvee \{ x \wedge y : y \in Y \} \ . |
| | $$ | | $$ |
| − | It follows that $\mathbf{k}^2 = -ab\mathbf{1}$ and that any two of $\mathbf{i}, \mathbf{j}, \mathbf{k}$ anti-commute.
| |
| − |
| |
| − | The construction is symmetric: $(a,b)_F = (b,a)_F$. The algebra so constructed is a [[central simple algebra]] over $F$.
| |
| − |
| |
| − | The algebra $(1,1)_F$ is isomorphic to the $2 \times 2$ matrix ring $M_2(F)$. Such a quaternion algebra is termed ''split''.
| |
| − |
| |
| − | ==References==
| |
| − | * Tsit-Yuen Lam, ''Introduction to Quadratic Forms over Fields'', Graduate Studies in Mathematics '''67''' , American Mathematical Society (2005) ISBN 0-8218-1095-2 {{ZBL|1068.11023}} {{MR|2104929}}
| |
| | | | |
| − | =Square-free=
| + | The powerset $\mathcal{P}(A)$ of a set $A$ forms a frame. |
| − | ''quadratfrei''
| |
| | | | |
| − | Containing only a trivial square factor.
| + | 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 |
| − | | |
| − | A natural number $n$ is square-free if the only natural number $d$ such that $d^2$ divides $n$ is $d=1$. The prime factorisation of such a number $n$ has all exponents equal to 1. Similarly a polynomial $f$ is square-free if the only factors $g$ such that $g^2$ divides $f$ are constants. For polynomials, this is equivalent to having no repeated roots in any field.
| |
| − | | |
| − | An element $x$ of a [[monoid]] $M$ is square-free if the only $y \in M$ such that $y^2$ divides $x$ are units.
| |
| − | | |
| − | A word $x$ over an alphabet $A$, that is, an element of the free monoid $A^*$, is square-free if $x=uwwv$ implies that $w$ is the empty string.
| |
| − | | |
| − | ==Square-free number==
| |
| − | An integer $n$ is square-free if the only natural number $d$ such that $d^2$ divides $n$ is $d=1$. The prime factorisation of such a number $n$ has all exponents equal to 1. Any integer is uniquely expressible in the form $n = k^2 m$ where $m$ is the ''square-free kernel'' of $n$. If $Q(x)$ counts the square-free natural numbers $\le x$, then
| |
| | $$ | | $$ |
| − | Q(x) = \frac{6}{\pi^2} x + o\left({ x^{1/2} }\right) \ .
| + | \bigwedge \{ S \} = \mathrm{Int}\left({ \bigcap \{ S \} }\right) |
| | $$ | | $$ |
| | + | where $\mathrm{Int}$ denotes the [[interior]]. |
| | | | |
| | ====References==== | | ====References==== |
| − | * E. Landau, "Über den Zusammenhang einiger neuerer Sätze der analytischen Zahlentheorie", Wien. Ber. '''115''' (1906) 589-632. {{ZBL|37.0236.01}}
| + | <table> |
| − | * József Sándor; Dragoslav S. Mitrinović; Borislav Crstici, edd. "Handbook of number theory I". Springer-Verlag (2006). Sect.VI.18. ISBN 1-4020-4215-9. {{ZBL|1151.11300}}
| + | <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> |
| | + | |
| | + | =Alexandrov topology= |
| | + | ''on a [[partially ordered set]] $(X,{\le})$'' |
| | | | |
| − | ==Square-free polynomial==
| + | 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. |
| − | A polynomial $f$ is square-free if the only factors $g$ such that $g^2$ divides $f$ are constants. For polynomials, this is equivalent to having no repeated roots. Over fields of [[characteristic]] zero, a polynomial is square-free if and only if it has coprime to its formal derivative. Over fields of characteristic $p$, this holds for [[separable polynomial]]s, those $f$ such that $f' \not'equiv 0$, that is, those polynomials in $X$ that are not polynomials in $X^p$. | |
| | | | |
| − | Over a finite field $\mathbb{F}_q$, the number of square-free monic polynomials of degree $d$ is $(1-q^{-1})q^d$.
| + | The Alexandrov topology makes $X$ a [[T0 space]] and the [[Specialization of a point|specialisation]] order is just the original order ${\le}$ on $X$. |
| | | | |
| | ====References==== | | ====References==== |
| − | * Gary L. Mullen, Daniel Panario (edd), "Handbook of Finite Fields", CRC Press (2013) ISBN 1439873828 | + | * Johnstone, Peter T. ''Stone spaces'' Cambridge Studies in Advanced Mathematics '''3''' Cambridge University Press(1986) {{ZBL|0586.54001}} |
| − | | |
| − | ==Square-free word==
| |
| − | A word $x$ over an alphabet $A$, that is, an element of the free monoid $A^*$, is square-free if $x=uwwv$ implies that $w$ is the empty string. A square-free word is thus one that [[Avoidable pattern|avoids the pattern]] $XX$.<ref name=LotII112>Lothaire (2011) p.112</ref><ref name=LotII114>Lothaire (2011) p.114</ref>
| |
| | | | |
| − | ===Examples=== | + | =Exponentiation= |
| − | Over a two-letter alphabet $\{a,b\}$ the only square-free words are the empty word and$a$, $b$, $ab$, $ba$m $aba$ and $bab$. However, there exist infinite square-free words in any [[alphabet]] with three or more symbols,<ref name=LotII113/> as proved by [[Axel Thue]].<ref>A. Thue, Über unendliche Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 7 (1906) 1–22.</ref><ref>A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1–67.</ref>
| + | The algebraic and analytic operations generalising the operation of repeated multiplication in number systems. |
| | | | |
| − | One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet $\{0,\pm1\}$ obtained by taking the [[first difference]] of the [[Thue–Morse sequence]].<ref name=PF104>Pytheas Fogg (2002) p.104</ref><ref name=BLRS97>Berstel et al (2009) p.97</ref>
| + | For positive integer $n$, the operation $x \mapsto x^n$ may be defined on any system of numbers by repeated multiplication |
| − | | |
| − | An example found by John Leech<ref>{{cite journal | first=J. | last=Leech | authorlink=John Leech (mathematician) | title=A problem on strings of beads | journal=Math. Gazette | volume=41 | year=1957 | pages=277–278 | zbl=0079.01101 }}</ref> is defined recursively over the alphabet $\{a,b,c\}$. Let <math>w_1</math> be any word starting with the letter $a$. Define the words <math> \{w_i \mid i \in \mathbb{N} \}</math> recursively as follows: the word <math>w_{i+1}</math> is obtained from <math>w_i</math> by replacing each $a$ in <math>w_i</math> with $abcbacbcabcba$, each $b$ with $bcacbacabcacb$, and each $c$ with $cabacbabcabac$. It is possible to check that the sequence converges to the infinite square-free word
| |
| | $$ | | $$ |
| − | abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb \ldots
| + | 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. |
| | | | |
| − | ===Related concepts===
| + | 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 |
| − | A '''cube-free''' word is one with no occurrence of $www$ for a factor $w$. The Thue–Morse sequence is an example of a cube-free word over a binary alphabet.<ref name=LotII113>Lothaire (2011) p.113</ref> This sequence is not square-free but is "almost" so: the [[Critical exponent of a word|critical exponent]] is 2.<ref>{{cite book | title=Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006 | volume=4036 | series=Lecture Notes in Computer Science | editor1-first=Oscar H. | editor1-last=Ibarra | editor2-first=Zhe | editor2-last=Dang | publisher=[[Springer-Verlag]] | year=2006 | isbn=3-540-35428-X | first=Dalia | last=Krieger | chapter=On critical exponents in fixed points of non-erasing morphisms | pages=280-291 | zbl=1227.68074 }}</ref> The Thue–Morse sequence has no '''overlap''' or ''overlapping square'', instances of $0X0X0$ or $1X1X1$:<ref name=LotII113/> it is essentially the only infinite binary word with this property.<ref name=BLRS81>Berstel et al (2009) p.81</ref>
| |
| − | | |
| − | An '''abelian $p$-th power''' is a subsequence of the form <math>w_1 \cdots w_p</math> where each <math>w_i</math> is a permutation of <math>w_1</math>. There is no abelian-square-free infinite word over an alphabet of size three: indeed, every word of length eight over such an alphabet contains an abelian square. There is an infinite abelian-square-free word over an alphabet of size five.<ref>{{cite book | chapter=Avoiding Abelian Powers in Partial Words | title=Developments in Language Theory. Proceedings, 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011 | pages=70-81 | year=2011 | doi=10.1007/978-3-642-22321-1_7 | isbn=978-3-642-22320-4 | series=Lecture Notes in Computer Science | volume=6795 | issn=0302-9743 | publisher=[[Springer-Verlag]] | location=Berlin, Heidelberg | editor1-first=Giancarlo | editor1-last=Mauri | editor2-first=Alberto | editor2-last=Leporati | author1-first=Francine | author2-last=Blanchet-Sadri | author2-first=Sean | author2-last=Simmons }}</ref>
| |
| − | | |
| − | ====References====
| |
| − | <references/>
| |
| − | * {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=http://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
| |
| − | * {{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Combinatorics on words | publisher=[[Cambridge University Press]] | location=Cambridge | year= 1997 | isbn= 0-521-59924-5 }}.
| |
| − | * {{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
| |
| − | * {{cite book | last=Pytheas Fogg | first=N. | others=Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }}
| |
| − | | |
| − | =Root of unity=
| |
| − | {{TEX|done}}
| |
| − | | |
| − | An element $\zeta$ of a ring $R$ with unity $1$ such that $\zeta^m = 1$ for some $m \ge 1$. The least such $m$ is the order of $\zeta$.
| |
| − | | |
| − | A primitive root of unity of order $m$ is an element $\zeta$ such that $\zeta^m = 1$ and $\zeta^r \neq 1$ for any positive integer $r < m$. The element $\zeta$ generates the [[cyclic group]] $\mu_m$ of roots of unity of order $m$.
| |
| − | | |
| − | | |
| − | | |
| − | In the field of [[complex number]]s, there are roots of unity of every order: those of order $m$ take the form | |
| | $$ | | $$ |
| − | \cos \frac{2\pi k}{m} + i \sin \frac{2\pi k}{m}
| + | x^{m+n} = x^m \cdot x^n \ . |
| | $$ | | $$ |
| − | where $0 < k < m$ and $k$ is relatively prime to $m$.
| |
| − |
| |
| − |
| |
| − | ====References====
| |
| − | <table>
| |
| − | <TR><TD valign="top">[1]</TD> <TD valign="top"> S. Lang, "Algebra" , Addison-Wesley (1984)</TD></TR>
| |
| − | </table>
| |
| − |
| |
| − | =Law of quadratic reciprocity=
| |
| − | ==Gauss reciprocity law==
| |
| − | A relation connecting the values of the Legendre symbols (cf. [[Legendre symbol|Legendre symbol]]) $(p/q)$ and $(q/p)$ for different odd prime numbers $p$ and $q$ (cf. [[Quadratic reciprocity law|Quadratic reciprocity law]]). In addition to the principal reciprocity law of Gauss for quadratic residues, which may be expressed as the relation
| |
| − |
| |
| − | $$\left(\frac pq\right)\left(\frac qp\right)=(-1)^{(p-1)/2\cdot(q-1)/2},$$
| |
| − |
| |
| − | there are two more additions to this law, viz.:
| |
| − |
| |
| − | $$\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\quad\text{and}\quad\left(\frac2p\right)=(-1)^{(p^2-1)/8}.$$
| |
| − |
| |
| − | The reciprocity law for quadratic residues was first stated in 1772 by L. Euler. A. Legendre in 1785 formulated the law in modern form and proved a part of it. C.F. Gauss in 1801 was the first to give a complete proof of the law [[#References|[1]]]; he also gave no less than eight different proofs of the reciprocity law, based on various principles, during his lifetime.
| |
| − |
| |
| − | Attempts to establish the reciprocity law for [[Cubic residue|cubic]] and [[biquadratic residue]]s led Gauss to introduce the ring of [[Gaussian integer]]s.
| |
| − |
| |
| − | ====References====
| |
| − | <table>
| |
| − | <TR><TD valign="top">[1]</TD> <TD valign="top"> C.F. Gauss, "Disquisitiones Arithmeticae" , Yale Univ. Press (1966) (Translated from Latin)</TD></TR>
| |
| − | <TR><TD valign="top">[2]</TD> <TD valign="top"> I.M. [I.M. Vinogradov] Winogradow, "Elemente der Zahlentheorie" , R. Oldenbourg (1956) (Translated from Russian)</TD></TR>
| |
| − | <TR><TD valign="top">[3]</TD> <TD valign="top"> H. Hasse, "Vorlesungen über Zahlentheorie" , Springer (1950)</TD></TR>
| |
| − | </table>
| |
| − |
| |
| − |
| |
| − |
| |
| − | ====Comments====
| |
| − | Attempts to generalize the quadratic reciprocity law (as Gauss' reciprocity law is usually called) have been an important driving force for the development of [[algebraic number theory]] and [[class field theory]]. A far-reaching generalization of the quadratic reciprocity law is known as Artin's reciprocity law.
| |
| − |
| |
| − | ==Quadratic reciprocity law==
| |
| − | The relation
| |
| − |
| |
| − | $$\left(\frac pq\right)\left(\frac pq\right)=(-1)^{(p-1)/2\cdot(q-1)/2},$$
| |
| − |
| |
| − | connecting the Legendre symbols (cf. [[Legendre symbol|Legendre symbol]])
| |
| − |
| |
| − | $$\left(\frac pq\right)\quad\text{and}\quad\left(\frac qp\right)$$
| |
| − |
| |
| − | for different odd prime numbers $p$ and $q$. There are two additions to this quadratic reciprocity law, namely:
| |
| − |
| |
| − | $$\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}$$
| |
| − |
| |
| − | and
| |
| − |
| |
| − | $$\left(\frac 2p\right)=(-1)^{(p^2-1)/8}.$$
| |
| − |
| |
| − | C.F. Gauss gave the first complete proof of the quadratic reciprocity law, which for this reason is also called the [[Gauss reciprocity law|Gauss reciprocity law]].
| |
| − |
| |
| − | It immediately follows from this law that for a given square-free number $d$, the primes $p$ for which $d$ is a quadratic residue modulo $p$ ly in certain arithmetic progressions with common difference $2|d|$ or $4|d|$. The number of these progressions is $\phi(2|d|)/2$ or $\phi(4|d|)/2$, where $\phi(n)$ is the [[Euler function|Euler function]]. The quadratic reciprocity law makes it possible to establish factorization laws in quadratic extensions $\mathbf Q(\sqrt d)$ of the field of rational numbers, since the factorization into prime factors in $\mathbf Q(\sqrt d)$ of a prime number that does not divide $d$ depends on whether or not $x^2-d$ is reducible modulo $p$.
| |
| − |
| |
| − | ====References====
| |
| − | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> Z.I. Borevich, I.R. Shafarevich, "Number theory" , Acad. Press (1966) (Translated from Russian) (German translation: Birkhäuser, 1966)</TD></TR></table>
| |
| − |
| |
| − |
| |
| − |
| |
| − | ====Comments====
| |
| − | See also [[Quadratic residue|Quadratic residue]]; [[Dirichlet character|Dirichlet character]].
| |
| − |
| |
| − | ====References====
| |
| − | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. XIII</TD></TR></table>
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | =Euler function=
| |
| − | ==Euler function==
| |
| − |
| |
| − | The arithmetic function $\phi$ whose value at $n$ is equal to the number of positive integers not exceeding $n$ and relatively prime to $n$ (the "totatives" of $n$). The Euler function is a [[multiplicative arithmetic function]], that is $\phi(1)=1$ and $\phi(mn)=\phi(m)\phi(n)$ for $(m,n)=1$. The function $\phi(n)$ satisfies the relations
| |
| − |
| |
| − | $$\sum_{d|n}\phi(d)=n,$$
| |
| | | | |
| − | $$c\frac{n}{\ln\ln n}\leq\phi(n)\leq n,$$
| + | If the operation is also [[commutativity|commutative]] then we have |
| − | | |
| − | $$\sum_{n\leq x}\phi(n)=\frac{3}{\pi^2}x^2+O(x\ln x).$$
| |
| − | | |
| − | It was introduced by L. Euler (1763).
| |
| − | | |
| − | | |
| − | The function $\phi(n)$ can be evaluated by $\phi(n)=n\prod_{p|n}(1-p^{-1})$, where the product is taken over all primes dividing $n$, cf. [[#References|[a1]]].
| |
| − | | |
| − | For a derivation of the asymptotic formula in the article above, as well as of the formula
| |
| − | | |
| − | $$\lim_{n\to\infty}\inf\phi(n)\frac{\ln\ln n}{n}=e^{-\gamma},$$
| |
| − | | |
| − | where $\gamma$ is the [[Euler constant]], see also [[#References|[a1]]], Chapts. 18.4 and 18.5.
| |
| − | | |
| − | The Carmichael conjecture on the Euler totient function states that if $\phi(x) = m$ for some $m$, then $\phi(y) = m$ for some $y \neq x$; i.e. no value of the Euler function is assumed once. This has been verified for $x < 10^{1000000}$, [[#References|[c1]]].
| |
| − | | |
| − | D. H. Lehmer asked whether whether there is any composite number $n$ such that $\phi(n)$ divides $n-1$. This is true of every [[prime number]], and Lehmer conjectured in 1932 that there are no composite numbers with this property: he showed that if any such $n$ exists, it must be odd, square-free, and divisible by at least seven primes [[#References|[c2]]]. For some results on this still (1996) largely open problem, see [[#References|[c3]]] and the references therein.
| |
| − | | |
| − | | |
| − | ====References====
| |
| − | <table>
| |
| − | <TR><TD valign="top">[1]</TD> <TD valign="top"> K. Chandrasekharan, "Introduction to analytic number theory" , Springer (1968) {{MR|0249348}} {{ZBL|0169.37502}}</TD></TR>
| |
| − | <TR><TD valign="top">[a1]</TD> <TD valign="top"> G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 {{MR|0568909}} {{ZBL|0423.10001}}</TD></TR>
| |
| − | <TR><TD valign="top">[c1]</TD> <TD valign="top"> A. Schlafly, S. Wagon, "Carmichael's conjecture on the Euler function is valid below $10^{1000000}$" ''Math. Comp.'' , '''63''' (1994) pp. 415–419</TD></TR>
| |
| − | <TR><TD valign="top">[c2]</TD> <TD valign="top"> D.H. Lehmer, "On Euler's totient function", ''Bulletin of the American Mathematical Society'' '''38''' (1932) 745–751 {{DOI|10.1090/s0002-9904-1932-05521-5}} {{ZBL|0005.34302}}</TD></TR>
| |
| − | <TR><TD valign="top">[c3]</TD> <TD valign="top"> V. Siva Rama Prasad, M. Rangamma, "On composite $n$ for which $\phi(n)|n-1$" ''Nieuw Archief voor Wiskunde (4)'' , '''5''' (1987) pp. 77–83</TD></TR>
| |
| − | <TR><TD valign="top">[c4]</TD> <TD valign="top"> M.V. Subbarao, V. Siva Rama Prasad, "Some analogues of a Lehmer problem on the totient function" ''Rocky Mount. J. Math.'' , '''15''' (1985) pp. 609–620</TD></TR>
| |
| − | <TR><TD valign="top">[c5]</TD> <TD valign="top"> R. Sivamarakrishnan, "The many facets of Euler's totient II: generalizations and analogues" ''Nieuw Archief Wiskunde (4)'' , '''8''' (1990) pp. 169–188</TD></TR>
| |
| − | <TR><TD valign="top">[c6]</TD> <TD valign="top"> R. Sivamarakrishnan, "The many facets of Euler's totient I" ''Nieuw Archief Wiskunde (4)'' , '''4''' (1986) pp. 175–190</TD></TR>
| |
| − | <TR><TD valign="top">[c7]</TD> <TD valign="top"> L.E. Dickson, "History of the theory of numbers I: Divisibility and primality" , Chelsea, reprint (1971) pp. Chapt. V; 113–155</TD></TR>
| |
| − | </table>
| |
| − | | |
| − | ==Totient function==
| |
| − | ''Euler totient function, Euler totient''
| |
| − | | |
| − | Another frequently used named for the [[Euler function]] $\phi(n)$, which counts a [[reduced system of residues]] modulo $n$: the natural numbers $k \in \{1,\ldots,n\}$ that are relatively prime to $n$.
| |
| − | | |
| − | A natural generalization of the Euler totient function is the [[Jordan totient function]] $J_k(n)$, which counts the number of $k$-tuples $(a_1,\ldots,a_k)$, $a_i \in \{1,\ldots,n\}$, such that $\mathrm{hcf}\{n,a_1,\ldots,a_k\} = 1$. Clearly, $J_1 = \phi$. The $J_k$ are [[multiplicative arithmetic function]]s.
| |
| − | | |
| − | One has
| |
| | $$ | | $$ |
| − | J_k(n) = n^k \prod_{p|n} \left({ 1 - p^{-k} }\right)
| + | (x \cdot y)^n = x^n \cdot y^n \ . |
| | $$ | | $$ |
| − | where $p$ runs over the prime numbers dividing $n$, and
| + | |
| | + | We may extend the definition to non-positive integer powers by defining $x^0 = 1$ and |
| | $$ | | $$ |
| − | J_k(n) = \sum_{d | n} \mu(n/d) d^k
| + | x^{-n} = \frac{1}{x^n} |
| | $$ | | $$ |
| − | where $\mu$ is the [[Möbius function]] and $d$ runs over all divisors of $n$. For $k=1$ these formulae reduce to the well-known formulae for the Euler function.
| + | 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$. |
| | | | |
| − | ====References====
| + | 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. |
| − | <table>
| |
| − | <TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Schlafly, S. Wagon, "Carmichael's conjecture on the Euler function is valid below $10^{1000000}$" ''Math. Comp.'' , '''63''' (1994) pp. 415–419</TD></TR>
| |
| − | <TR><TD valign="top">[a2]</TD> <TD valign="top"> D.H. Lehmer, "On Euler's totient function" ''Bull. Amer. Math. Soc.'' , '''38''' (1932) pp. 745–751</TD></TR>
| |
| − | <TR><TD valign="top">[a3]</TD> <TD valign="top"> V. Siva Rama Prasad, M. Rangamma, "On composite $n$ for which $\phi(n)|n-1$" ''Nieuw Archief voor Wiskunde (4)'' , '''5''' (1987) pp. 77–83</TD></TR>
| |
| − | <TR><TD valign="top">[a4]</TD> <TD valign="top"> M.V. Subbarao, V. Siva Rama Prasad, "Some analogues of a Lehmer problem on the totient function" ''Rocky Mount. J. Math.'' , '''15''' (1985) pp. 609–620</TD></TR>
| |
| − | <TR><TD valign="top">[a5]</TD> <TD valign="top"> R. Sivamarakrishnan, "The many facets of Euler's totient II: generalizations and analogues" ''Nieuw Archief Wiskunde (4)'' , '''8''' (1990) pp. 169–188</TD></TR>
| |
| − | <TR><TD valign="top">[a6]</TD> <TD valign="top"> R. Sivamarakrishnan, "The many facets of Euler's totient I" ''Nieuw Archief Wiskunde (4)'' , '''4''' (1986) pp. 175–190</TD></TR>
| |
| − | <TR><TD valign="top">[a7]</TD> <TD valign="top"> L.E. Dickson, "History of the theory of numbers I: Divisibility and primality" , Chelsea, reprint (1971) pp. Chapt. V; 113–155</TD></TR>
| |
| − | </table>
| |
| | | | |
| − | ==Jordan totient function== | + | For positive real numbers there are mutually inverse [[exponential function, real|exponential]] and [[logarithmic function|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-number|$e$]] is the base of natural logarithms. |
| | | | |
| − | An arithmetic function $J_k(n)$ of a [[natural number]] $n$, named after Camille Jordan, counting the $k$-tuples of positive integers all less than or equal to $n$ that form a [[Coprime numbers|coprime]] $(k + 1)$-tuple together with $n$. This is a generalisation of Euler's [[totient function]], which is $J_1$.
| + | ===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)$. |
| | | | |
| − | Jordan's totient function is [[Multiplicative arithmetic function|multiplicative]] and may be evaluated as
| + | ===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 |
| | $$ | | $$ |
| − | J_k(n)=n^k \prod_{p|n}\left(1-\frac{1}{p^k}\right) \ .
| + | x^{n+1} = x \star (x^n) |
| | $$ | | $$ |
| | + | and |
| | + | $$ |
| | + | 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. |
| | | | |
| − | By [[Möbius inversion]] we have $\sum_{d | n } J_k(d) = n^k $. The [[Average order of an arithmetic function|average order]] of $J_k(n)$ is $c n^k$ for some $c$.
| + | =Logarithm= |
| | + | The operation inverse to [[exponentiation]]. |
| | | | |
| − | The analogue of Lehmer's problem for the Jordan totient function (and $k>1$) is easy, [[#References|[c4]]]: For $k>1$, $J_k(n) | n^k-1$ if and only if $n$ is a prime number. Moreover, if $n$ is a prime number, then $J_k(n) = n^k-1$.
| + | 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]]. |
| − | For much more information on the Euler totient function, the Jordan totient function and various other generalizations, see [[#References|[c5]]], [[#References|[c6]]].
| |
| | | | |
| − | ====References====
| + | In a finite Abelian group, the [[discrete logarithm]] is the inverse to exponentiation, with applications in [[cryptography]]. |
| − | * Dickson, L.E. ''History of the Theory of Numbers I'', Chelsea (1971) p. 147, ISBN 0-8284-0086-5
| |
| − | * Ram Murty, M. ''Problems in Analytic Number Theory'', Graduate Texts in Mathematics '''206''' Springer-Verlag (2001) p. 11 ISBN 0387951431 {{ZBL|0971.11001}}
| |
| − | * Sándor, Jozsef; Crstici, Borislav, edd. Handbook of number theory II. Dordrecht: Kluwer Academic (2004). pp.32–36. ISBN 1-4020-2546-7. {{ZBL|1079.11001}}
| |
| | | | |
| − | =Multiplicative sequence=
| + | The [[Zech logarithm]] in a finite field is related to the discrete logarithm. |
| − | 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==
| |
| − | 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
| |
| | | | |
| − | $$\sum_i p_i z^i = \sum p'_i z^i \cdot \sum_i p''_i z^i $$
| |
| | | | |
| − | implies
| + | =''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. |
| | | | |
| − | $$\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 . $$ | + | 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)$. |
| − | The power series
| |
| | | | |
| − | $$\sum K_n(1,0,\ldots,0) z^n $$
| |
| | | | |
| − | 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.
| + | ====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}} |
| | | | |
| − | To recover a multiplicative sequence from a characteristic power series $Q(z)$ we consider the coefficient of ''z''<sup>''j''</sup> in the product
| + | =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]]. |
| | | | |
| − | $$ \prod_{i=1}^m Q(\beta_i z) $$
| + | ====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}} |
| | | | |
| − | 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.
| |
| | | | |
| − | ==Examples==
| |
| − | 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 | + | =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 |
| | $$ | | $$ |
| − | 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)$.
| + | (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 multiplicative sequence with characteristic power series
| + | The algebra $A_1$ has an involution $(x_1,x_2) \mapsto (x_1^*,-x_2)$. |
| − | | |
| − | $$ Q(z) = \frac{2\sqrt z}{\sinh 2\sqrt z} $$
| |
| − | | |
| − | is denoted $A_j(p_1,\ldots,p_j)$.
| |
| − | | |
| − | The multiplicative sequence with characteristic power series
| |
| − | | |
| − | $$Q(z) = \frac{z}{1-\exp(-z)} = 1 + \frac{x}{2} - \sum_{k=1}^\infty (-1)^k \frac{B_k}{(2k)!} z^{2k} $$
| |
| − | is denoted $T_j(p_1,\ldots,p_j)$: the ''[[Todd polynomial]]s''.
| |
| − | | |
| − | ==Genus==
| |
| − | 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.
| |
| − | | |
| − | 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} . $$
| |
| − | | |
| − | ==References==
| |
| − | * 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}}. | |
| − | | |
| − | =Nagao's theorem=
| |
| − | 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]].
| |
| − | | |
| − | ==Nagao's theorem==
| |
| − | | |
| − | 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
| |
| − | | |
| − | $$ 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 \ . $$
| |
| − | | |
| − | Then $B(R)$ is a subgroup of $GL_2(R)$.
| |
| − | | |
| − | 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)$.
| |
| − | | |
| − | ==Serre's extension==
| |
| − | 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. | |
| − | | |
| − | =Brauer–Wall group=
| |
| − | A [[group]] classifying graded [[central simple algebra]]s over a field. It 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}}
| |
| | | | |
| − | ==Properties==
| |
| − | * The Brauer group $\mathrm{B}(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
| + | =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 |
| | $$ | | $$ |
| − | 0 \rightarrow \mathrm{B}(F) \rightarrow \mathrm{BW}(F) \rightarrow Q(F) \rightarrow 0
| + | \partial_i(x_j) = \delta_{ij} \ , |
| | $$ | | $$ |
| − | 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==
| |
| − | * $\mathrm{BW}(\mathbf{R})$ is isomorphic to $\mathbf{Z}/8$. This is an algebraic aspect of [[Bott periodicity]].
| |
| − |
| |
| − | ==References==
| |
| − | * 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}}
| |
| − |
| |
| − | =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 automorphisms. A ''cocycle'' or ''factor system'' is a map $c : G \times G \rightarrow L^*$ satisfying
| |
| | $$ | | $$ |
| − | c(h,k)^g c(hk,g) = c(h,kg) c(k,g) \ .
| + | \partial_i(1) = 0 \ , |
| | $$ | | $$ |
| − |
| |
| − | Cocycles are ''equivalent'' if there exists some system of elements $a : G \rightarrow L^*$ with
| |
| | $$ | | $$ |
| − | c'(g,h) = c(g,h) (a_g^h a_h a_{gh}^{-1}) \ .
| + | \partial_i(uv) = u \partial_i(v) + \partial_i(u) v \ . |
| | $$ | | $$ |
| − | | + | It follows that |
| − | Cocycles of the form
| |
| | $$ | | $$ |
| − | c(g,h) = a_g^h a_h a_{gh}^{-1}
| + | \partial_i(x_i^{-1}) = - x_i^{-1} \ . |
| | $$ | | $$ |
| − | are called ''split''. Cocycles under multiplication modulo split cocycles form a group, the second cohomology group $H^2(G,L^*)$.
| |
| | | | |
| − | ==Crossed product algebras==
| + | The maps extend to [[derivation]]s on $R[F]$. |
| − | 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 \ ,
| |
| − | $$
| |
| − | $$
| |
| − | u_g u_h = u_{gh} c(g,h) \ .
| |
| − | $$
| |
| − | 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 way. The 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}}
| + | ===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^*/\mathrm{N}_{L/K} L^* \equiv \mathrm{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.
| |
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