Semigroup, monoid
Semigroup: \(<S,+>\): closed under binary operation \$+\$. Monoid: semigroup with identity element e.
Function characteristics
Consider functions on ordered semigroups. Some of these have some notable properties.
Subadditivity
\(f(a + b) \leq f(a) + f(b)\).
Group G
Group (G): monoid with inverses. Commutative group. Cayley tables.
No element can have 2 inverses: \(a_1^{-1}aa_2^{-1} = a_2^{-1} = a_1^{-1}\). \((ab)^{-1} = b^{-1}a^{-1}\). Unique solution for ax=b: \(x=a^{-1}b\).
For examples \(Z_{n}^{+}\) and \(Z_{n}^{*}\), see Number Theory survey.
Order of a group
Number of elements in the group, \(\phi(G)\).
Subgroups
\(H \leq G\). Eg: p prime: \(\set{\pm 1} \leq Z_{p}^{*}\).
Cosets of subgroup
Left coset of subgroup H containing g: gH or g+H; may not be group. Also, right coset of H containing g. Normal subgroup: N for which gN = Ng. Eg: 2Z or 2+Z has 2 cosets: evens and odds.
Cardinality
(Lagrange): If \(H \leq G: |H| | |G|\): Take \(a \in G-H\); then \(aH \inters H = \nullSet\); repeat with \(a’ \in G-H-aH\) etc.. So, if \(H < G\), \(|H| \leq |G|/2\).
So, this is an easy partial-test to see if H is a group.
Quotient/ factor group
\(G/N\): cosets; with Coset product: (aN)(bN) = abNN = abN; eN identity. Eg: Z/nZ isomorphic to \({0, .. n-1}, \oplus_n\).
Product group: G*H.
Multiplicative order ord(a) of element a
\(ord(a) = argmin_{n}: a^{n}=e\). \(ord(A) | \phi(G)\).
Cyclic group G generated by a
Every \(a \in G\) generates some subgroup of G.
G is cyclic if some generator generates G. Then G is non degenerate. Eg: \(Z_{4}\); \(\omega\) in \(\omega^{n}=1\).
Number of generators
If there is a generator g, there are at least \(\phi(Z_{\phi(G)}^{*})\) of them: \(Z_{\phi(G)}^{*}\) excludes all numbers which divide \(\phi(G)\); so for any \(a \in Z_{\phi(G)}^{*}\), can’t write \((g^{a})^{b} = e\) for any \(b < \phi(G)\).
Periodic group
Every element has finite order. All finite groups are periodic.
Group homomorphism
It(a) maps elements of two groups (G,H) : \(a(g.h)=a(g).a(h)\). Image a(G). Kernel of homomorphism: ker(a) = G elements mapped to \(1_{H}\). Isomorphic groups: homomorphism is invertible. ker(a) and a(G) measure closness to homomorphism. ker(a) is a normal subgroup. a(G) isomorphic to G/ker(a).
Special groups
Symmetric group on X
\(S_{X}\) or Sym(X) or \(S_{n}\) is a group of permutations/ bijective functions on X, under composition. Not commutative for \(n>2\). Transposition only switches 2 elements. Every permutation f is a product of transpositions. Even and odd permutations. The product is not unique, but oddness is same: Consider number of pairs \(i<j\), where \(f(j)<f(i)\). Sign of Permutation: Sgn(f) is +1 or -1. Cycle.
Elliptic curve groups
See topology survey.
Bilinear groups
Groups with efficiently computable bilinear maps. \(G_{T}\): target group; \(g_{1}, g_{2}\) generators of \(G_{1}\) and \(G_{2}\). Bilinear map/ pairing operation: \(p: G_1 \times G_2 \to G_{T}\). Not necessarily 1 to 1.
Bilinearity property: \(p(g_{1}^{a}, g_{2}^{b}) = p(g_{1}, g_{2})^{ab}\); can be seen as bilinear map amongst exponents: \(p’(a, b) = ab\). \(p(xz,y) = p(z,y)p(x,y)\).
Can efficiently compute bilinear map \(Z_{p} \times Z_{p} \to Z_{p}\). \why
No efficient way to make multilinear maps known.