User:Richard Pinch/sandbox

Fibonacci word

An infinite sequence of symbols over a binary alphabet defined by a recursion related to that of the Fibonacci numbers.

Let $A$ be the alphabet $\{a,b\}$ and define a sequence of finite words $f_n$, $n \ge 1$ by $f_1 = a$, $f_2 = ab$ and $f_{n+1} = f_n \cdot f_{n-1}$ where $\cdot$ denotes concatenation. The Fibonacci word $\mathcal{F}$ is defined as $$ \mathcal{F} = f_1 \cdot f_2 \cdot \cdots \cdot f_n \cdot \cdots $$ and, since $f_n$ is an initial factor of $f_{n+1}$ we may also obtain $\mathcal{F}$ as the limit of the $f_n$. We have $$ \mathcal{F} = a ab aab abaab aababaab abaabaababaab \ldots \ . $$

The Fibonacci word has complexity $c_{\mathcal{F}}(n) = n+1$ and hence is a Sturmian sequence. It is a morphic word, a fixed point of the endomorphism $a \mapsto ab$, $b \mapsto a$.

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
• Lothaire, M. (1997), Combinatorics on Words (2nd ed.) Encyclopedia of Mathematics and Its Applications 17' Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040
• Lothaire, M. Algebraic Combinatorics on Words Encyclopedia of Mathematics and Its Applications 90, Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 Zbl 1221.68183
• Pytheas Fogg, N. (ed.) Substitutions in dynamics, arithmetics and combinatorics Lecture Notes in Mathematics 1794 Springer (2002) ISBN 978-3-540-44141-0 Zbl 1014.11015

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)$.

Cocktail party graph

hyperoctahedral graph

A family of graphs $H_s$ formed from the complete graph $K_{2s}$ on $2s$ vertices by removing $s$ disjoint edges: equivalently, the complete multipartite graph $K_{2,2,\ldots,2}$.

References

• Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032

Line graph

of a graph $G$

The (unoriented) graph $L(G)$ having a vertex set in one-to-one correspondence with the edge set of $G$, and vertices adjacent in $L(G)$ if the corresponding edges in $G$ have exactly one vertex in common.

The spectra of line graphs have been investigated. Let $G$ have vertices $\{v_1,\ldots,v_n\}$ and edges $e_1,\ldots,e_p$, and let $M$ be the $n \times p$ incidence matrix of $G$, so that $M_{ij} = 1$ if $v_i$ is incident with edge $j$ and otherwise zero. The adjacency matrix $A_L$ of $L(G)$ satisfies $$ M^\top M = A_L + 2 I_p $$ where $I_p$ is an identity matrix. It follows that all eigenvalues of $A_L$ are $\ge -2$.

References

• Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032
• Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan Spectral generalizations of line graphs. On graphs with least eigenvalue $−2$ London Mathematical Society Lecture Note Series 314 Cambridge University Press(2004) ISBN 0-521-83663-8 Zbl 1061.05057

BCH code

A cyclic code over a finite field. Fix length $n$ and ground field $\mathbf{F}_q$ and a design distance parameter $\delta$. Let $\beta$ be a primitive $n$-th root of unity in a suitable extension of $\mathbf{F}_q$. The generator of the cyclic code is the least common multiple $g$ of the minimal polynomials (over $\mathbf{F}_q$) of the elements $\beta^1, \beta^2, \ldots, \beta^{\delta-1}$.

The minimum distance of the BCH code generated by $g$ is at least $\delta$: this is the BCH bound.

As an example, let $q=2$ and $\beta$ be a primitive $7$-th root of unity in $\mathrm{F}_{8}$: we may take $\beta$ to satisfy the polynomial $x^3 + x + 1$. Choose $\delta = 3$. The minimal polynomial for $\beta^2$ is the same as that of $\beta$, so that the cyclic code is generated by the word $1101000$. This is in fact the Hamming [7,4] code.

References

• Goldie, Charles M.; Pinch, Richard G.E. Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) iSBN 0-521-40456-8 Zbl 0746.94001

Hamming distance

A function on words of fixed length over an alphabet describing the number of changes to the symbols of one word required to reduce it to another. Let $A$ be an alphabet of symbols and $C$ a subset of $A^n$, the set of words of length $n$ over $A$. Let $u=(u_1,\ldots,u_n)$ and $v = (v_1,\ldots,v_n)$ be words in $C$. The Hamming distance $d(u,v)$ is defined as the number of places in which $u$ and $v$ differ: that is, $\sharp\{ i : u_i \neq v_i,\,i=1,\dots,n \}$.

The Hamming distance satisfies $$ d(u,v) \ge 0 \ \text{and}\ d(u,v) = 0\ \text{if and only if}\ u=v\ ; $$ $$ d(u,v) = d(v,u)\ ; $$ $$ d(u,v) \le d(u,w) + d(w,v) \ . $$ Hamming distance is thus a metric on $C$.

In the theory of error-correcting codes it is assumed that words from $C$ are transmitted down a noisy channel and that some symbols are changed during the transmission: see for example the symmetric channel. Maximum likelihood decoding of a received word $r$ consists of finding the word in $C$ nearest to $r$ in the Hamming metric. If the minimum Hamming distance between words of $C$ is $\delta$, then this process is capable of detecting up to $\delta-1$ errors in $r$, and correcting up to $\left\lfloor \frac{\delta-1}{2} \right\rfloor$ errors.

References

• Goldie, Charles M.; Pinch, Richard G.E. Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) iSBN 0-521-40456-8 Zbl 0746.94001

Leibniz algebra

An algebra over a field $K$ generalising the properties of a Lie algebra. A Leibniz algebra $L$ is a $K$-algebra with multiplication denoted by $[\cdot,\cdot]$ satisfying $$ [ x, [y,z]] = [[x,y],z] - [[x,z],y] \ . $$ Every Lie algebra is a Leibniz algebra, and a Leibniz algebra is a Lie aglebra if in addition $[x,x] = 0$.

The free Leibniz algebra on a generating set $X$ may be defined as the quotient of the free non-associative algebra over $K$ (cf. Free algebra over a ring) by the ideal generated by all elements of the form $[ x, [y,z]] - [[x,y],z] + [[x,z],y] $. The standard Leibniz algebra on $X$ is obtained from the vector space $V = KX$ and forming the tensor module $$ T(X) = V \oplus V^{{}\otimes 2} \oplus \cdots \oplus V^{{}\otimes n} \oplus \cdots $$ with the multiplication $$ [x,v] = x \otimes v $$ when $v \in V$ and $$ [x, y\otimes v] = [x,y] \otimes v - [x \otimes v, y] \ . $$ The standard algebra is then a presentation of the free algebra on $X$.

References

• Mikhalev, Alexander A.; Shpilrain, Vladimir; Yu, Jie-Tai, Combinatorial methods. Free groups, polynomials, and free algebras, CMS Books in Mathematics 19 Springer (2004) ISBN 0-387-40562-3 Zbl 1039.16024

Tridiagonal matrix

A matrix with non-zero entries only on the main diagonal and the diagonals immediately above and below, for example $$ \begin{pmatrix} a_1 & b_1 & 0 & 0 & \ldots & 0 & 0 \\ c_1 & a_2 & b_2 & 0 & \ldots & 0 & 0 \\ 0 & c_2 & a_3 & b_3 & \ldots & 0 & 0 \\ \vdots & \ddots & \ddots & \ddots & & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & c_{n-1} & a_n \end{pmatrix} \ . $$

The determinant of a tridiagonal matrix may be computed as a continuant.

References

• Thomas Muir. A treatise on the theory of determinants. (Dover Publications, 1960 [1933])

Incidence matrix

A matrix encoding the relation defining an incidence structure, typically in the finite case.

An incidence system $S = (A,\mathfrak{B},I)$ consists of two sets $A$ and $\mathfrak{B}$ with an incidence relation $I$ between their elements, which is written as $a\,I\,B$ for $a \in A$, $B \in \mathfrak{B}$. In this case one says that the element $a$ is incident with $B$, or that $B$ is incident with $a$. If $A = \{a_1,\ldots,a_n\}$ and $\mathfrak{B} = \{B_1,\ldots,B_m\}$ are finite sets, then the incidence matrix $\Sigma$, where $\Sigma_{ij} = 1$ if $a_i\,I\,B_j$, and $\Sigma_{ij} = 0$ otherwise. The matrix $\Sigma$ determines $S$ up to an isomorphism.

A hypergraph $(V,\mathcal{E})$ consists of a vertex set $V$ and a family of edges $\mathcal{E}$ each of which is a subset of $V$. A vertex $v \in V$ is incident with an edge $E \in \mathcal{E}$ if $v \in E$, so a hypergraph is an incidence system in which the relation is membership. As before, if $V = \{v_1,\ldots,v_n\}$ and $\mathcal{E} = \{E_1,\ldots,E_m\}$ are finite sets, then the incidence matrix $\Sigma$, where $\Sigma_{ij} = 1$ if $v_i \in E_j$, and $\Sigma_{ij} = 0$ otherwise.

An unoriented graph may be regarded as a case of a hypergraph in which all edges are of size 1 (if loops are allowed) or 2. A directed graph $(V,\mathcal{E})$ consists of a vertex set $V$ and a family of edges $\mathcal{E}$ each of which is an ordered pair of $V$; if $(x,y) \in \mathcal{E}$ we say that the edge is directed from $x$ to $y$. Again, if $V = \{v_1,\ldots,v_n\}$ and $\mathcal{E} = \{E_1,\ldots,E_m\}$ are finite sets, then the incidence matrix $\Sigma$ has entries $0,\pm 1$ defined by $$ \Sigma_{ij} = \begin{cases} +1 & \text{if}\, E_j\,\text{is directed from}\,v_i \\ -1 & \text{if}\, E_j\,\text{is directed to}\,v_i \\ 0 & \text{otherwise} \end{cases}\ . $$

In the case of graphs, the product $L = \Sigma\Sigma^\top$ is the graph Laplacian. The off-diagonal entries $L_{ij}$ count (with sign) the number of edges going between $v_i$ and $v_j$ and the diagonal entries $L_{ii}$ count (without sign) the total number of edges going from or to $v_i$. Even for undirected graphs, it may be convenient to assign an arbitrary orientation to each edge and consider the oriented incidence matrix. In this case we have $L = D - A$ where $D$ is a diagonal matrix encoding the degree of each vertex and $A$ is the undirected adjacency matrix.

References

• B. Bollobas, Graph Theory, Graduate Texts in Mathematics 63 Springer (1979) ISBN 3-540-90399-2
• Marshall Hall jr, Combinatorial Theory, Wiley Classics Library 71 (2nd edition) John Wiley & Sons (2011) ISBN 1118031113 Zbl 0907.05002

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

Schroeder–Bernstein theorem

Cantor–Bernstein theorem

For sets $A$ and $B$, if there are injections 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).

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 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

• P. R. Halmos, "Naive Set Theory", Springer (1960) ISBN 0-387-90092-6
• Michael Potter, "Set Theory and its Philosophy : A Critical Introduction", Oxford University Press (2004) ISBN 0-19-155643-2

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-functions.

The Hurwitz zeta function $\zeta(\alpha,s)$ is defined for real $\alpha$, $0 < \alpha \le 1$ as $$ \zeta(\alpha,s) = \sum_{n=0}^\infty (n+\alpha)^{-s} \ . $$ 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

Isomorphism theorems

Three theorems relating to homomorphisms of general algebraic systems.

First Isomorphism Theorem

Let $f : A \rightarrow B$ be a homomorphism of $\Omega$-algebras and $Q$ the kernel of $f$, as an equivalence relation on $A$. Then $Q$ is a 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

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 \ . $$

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 $\theta$ on $A/Q$ then there is an isomorphism $$ (A/Q)/(R/Q) \cong A/R \ . $$

Application to groups

In the case of groups, 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

Let $f : A \rightarrow B$ be a homomorphism of groups and $N = f^{-1}(1_B)$ the 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 \ . $$

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 \ . $$

References

• 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 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

• 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

Quaternion algebra

An associative algebra over a field that generalises the construction of the quaternions over the field of real numbers.

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 $$ \mathbf{i}^2 = a\mathbf{1},\ \ \mathbf{j}^2 = b\mathbf{1},\ \ \mathbf{i}\mathbf{j} = -\mathbf{j}\mathbf{i} = \mathbf{k}\ . $$ 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 MR2104929

Square-free

quadratfrei

Containing only a trivial square factor.

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) \ . $$

References

• E. Landau, "Über den Zusammenhang einiger neuerer Sätze der analytischen Zahlentheorie", Wien. Ber. 115 (1906) 589-632. Zbl 37.0236.01
• 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

Square-free polynomial

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 polynomials, 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$.

References

• Gary L. Mullen, Daniel Panario (edd), "Handbook of Finite Fields", CRC Press (2013) ISBN 1439873828

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 avoids the pattern $XX$.

Examples

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, as proved by Axel Thue.

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.

An example found by John Leech is defined recursively over the alphabet $\{a,b,c\}$. Let \(w_1\) be any word starting with the letter $a$. Define the words \( \{w_i \mid i \in \mathbb{N} \}\) recursively as follows: the word \(w_{i+1}\) is obtained from \(w_i\) by replacing each $a$ in \(w_i\) 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 $$

Related concepts

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. This sequence is not square-free but is "almost" so: the critical exponent is 2. The Thue–Morse sequence has no overlap or overlapping square, instances of $0X0X0$ or $1X1X1$: it is essentially the only infinite binary word with this property.

An abelian $p$-th power is a subsequence of the form \(w_1 \cdots w_p\) where each \(w_i\) is a permutation of \(w_1\). 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.

References

• Template:Cite book
• Template:Cite book.
• Template:Cite book
• Template:Cite book

Root of unity

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 numbers, 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} $$ where $0 < k < m$ and $k$ is relatively prime to $m$.

References

[1]	S. Lang, "Algebra" , Addison-Wesley (1984)

Law of quadratic reciprocity

Gauss reciprocity law

A relation connecting the values of the Legendre symbols (cf. Legendre symbol) $(p/q)$ and $(q/p)$ for different odd prime numbers $p$ and $q$ (cf. 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 [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 and biquadratic residues led Gauss to introduce the ring of Gaussian integers.

References

[1]	C.F. Gauss, "Disquisitiones Arithmeticae" , Yale Univ. Press (1966) (Translated from Latin)
[2]	I.M. [I.M. Vinogradov] Winogradow, "Elemente der Zahlentheorie" , R. Oldenbourg (1956) (Translated from Russian)
[3]	H. Hasse, "Vorlesungen über Zahlentheorie" , Springer (1950)

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)

$$\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.

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. 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

[1]	I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)
[2]	Z.I. Borevich, I.R. Shafarevich, "Number theory" , Acad. Press (1966) (Translated from Russian) (German translation: Birkhäuser, 1966)

Comments

See also Quadratic residue; Dirichlet character.

References

[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. XIII

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,$$

$$\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. [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 [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}$, [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 [c2]. For some results on this still (1996) largely open problem, see [c3] and the references therein.

References

[1]	K. Chandrasekharan, "Introduction to analytic number theory" , Springer (1968) MR0249348 Zbl 0169.37502
[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 MR0568909 Zbl 0423.10001
[c1]	A. Schlafly, S. Wagon, "Carmichael's conjecture on the Euler function is valid below $10^{1000000}$" Math. Comp. , 63 (1994) pp. 415–419
[c2]	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
[c3]	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
[c4]	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
[c5]	R. Sivamarakrishnan, "The many facets of Euler's totient II: generalizations and analogues" Nieuw Archief Wiskunde (4) , 8 (1990) pp. 169–188
[c6]	R. Sivamarakrishnan, "The many facets of Euler's totient I" Nieuw Archief Wiskunde (4) , 4 (1986) pp. 175–190
[c7]	L.E. Dickson, "History of the theory of numbers I: Divisibility and primality" , Chelsea, reprint (1971) pp. Chapt. V; 113–155

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 functions.

One has $$ J_k(n) = n^k \prod_{p|n} \left({ 1 - p^{-k} }\right) $$ where $p$ runs over the prime numbers dividing $n$, and $$ J_k(n) = \sum_{d | n} \mu(n/d) d^k $$ 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.

References

[a1]	A. Schlafly, S. Wagon, "Carmichael's conjecture on the Euler function is valid below $10^{1000000}$" Math. Comp. , 63 (1994) pp. 415–419
[a2]	D.H. Lehmer, "On Euler's totient function" Bull. Amer. Math. Soc. , 38 (1932) pp. 745–751
[a3]	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
[a4]	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
[a5]	R. Sivamarakrishnan, "The many facets of Euler's totient II: generalizations and analogues" Nieuw Archief Wiskunde (4) , 8 (1990) pp. 169–188
[a6]	R. Sivamarakrishnan, "The many facets of Euler's totient I" Nieuw Archief Wiskunde (4) , 4 (1986) pp. 175–190
[a7]	L.E. Dickson, "History of the theory of numbers I: Divisibility and primality" , Chelsea, reprint (1971) pp. Chapt. V; 113–155

Jordan totient function

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 $(k + 1)$-tuple together with $n$. This is a generalisation of Euler's totient function, which is $J_1$.

Jordan's totient function is multiplicative and may be evaluated as $$ J_k(n)=n^k \prod_{p|n}\left(1-\frac{1}{p^k}\right) \ . $$

By Möbius inversion we have $\sum_{d | n } J_k(d) = n^k $. The average order of $J_k(n)$ is $c n^k$ for some $c$.

The analogue of Lehmer's problem for the Jordan totient function (and $k>1$) is easy, [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$. For much more information on the Euler totient function, the Jordan totient function and various other generalizations, see [c5], [c6].

References

• 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

Also m-sequence, a sequence of polynomials associated with a formal group structure. They have application in the 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

$$\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 . $$ 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.

To recover a multiplicative sequence from a characteristic power series $Q(z)$ we consider the coefficient of z^j in the product

$$ \prod_{i=1}^m Q(\beta_i z) $$

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 functions $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 $$ 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)$.

The multiplicative sequence with characteristic power series

$$ 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 polynomials.

Genus

The genus of a multiplicative sequence is a ring homomorphism, from the cobordism ring of smooth oriented compact manifolds to another ring, usually the ring of rational numbers.

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 matrices over the ring of polynomials over a field. It has been extended by 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 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 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. MR0114866. Zbl 0092.02504.
• Serre, Jean-Pierre. Trees. (Springer, 2003) ISBN 3-540-44237-5.

Brauer–Wall group

A group classifying graded central simple algebras 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 algebras defines the Brauer–Wall group $\mathrm{BW}(F)$.[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 $$ 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.

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[Lam (2005) p.113] which has kernel $I^3$, where $I$ is the fundamental ideal of $W(F)$.[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 MR2104929, 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, MR0167498

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) \ . $$

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}) \ . $$

Cocycles of the form $$ c(g,h) = a_g^h a_h a_{gh}^{-1} $$ 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 \ , $$ $$ 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$.[Saltman (1999) p.44]

Cyclic algebra

Let us further restrict to the case that $L/K$ is 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 $$ 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 $(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

• 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.
• 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.