COMP0147 but i DFS’d wikipedia too much from the page titled group

$0 \in \N$

General Notes:

Assume the following meanings of symbols unless otherwise specified:
$n$ is an integer (or natural number).
$S$ is a set, $M$ a (algebraic) structure.

When discussing group/ring theory:
$G$ is a group, $R$ a ring, $H$ a subgroup (of $G$), $N$ a normal subgroup (of $G$), $I$ an ideal (of $R$).
$e$ is the identity element.

More Abstract Algebra that is definitely in the course

ok but these are actually important to understand so the rest of the course doesn’t feel like magic. to do that, first read the notes on Algebraic Structures

i gave up on effort in this section so theres more iffy and more prose and less vroomular.

Throughout the section, the two ring operations are referred to as addition $+$ (abelian) and multiplication $\ast$ (monoidal).
Juxtaposition denotes the group operation or multiplication in rings.

Power Notation:
For a group $G$ with $x \in G$, operation $\ast$, and identity $e$:
$x^n \coloneqq \overbrace{x \ast x \ast \cdots \ast x}^\text{n times}$,
$x^{-n} = (x^n)^{-1}$ (the inverse) for $n < 0$, and
$x^0 = e$.

Observe this is literally how it usually works for “multiplication”, except we don’t care what $\ast$ actually does.

Subgroup

A subset of a group that is a group itself (under the same operations).
A subgroup can partition the group (see cosets below).

Coset

A set $\{ g \ast h \mid h \in H \}$ for a $g \in G$ with group operation $\ast$, notated $gH$ or $g \ast H$.

For non-Abelian Groups, that’s specifically a left coset, since $g$ is on the LHS of the $\ast$. I.e., a right coset would be $Hg = \{ h \ast g \mid h \in H \}$.

The "(left) cosets of $H$" is the set of all (left) cosets: $\{ gH \mid g \in G \}$. Same for the right cosets.

Coset in CS-terms: mapping the group operation over a subgroup with a constant.

Alternatively, a coset is an equivalence class (see below).

The sets of left and right cosets are either disjoint or identical.

Observe that all cosets are of the same size, equal to that of the subgroup. As such, a group always divides into a whole number of cosets.

Intuitively, for additive and well-ordered groups (e.g., $\Z$), cosets are left or right “shifts” of a subgroup when the group elements are laid out evenly spaced as line.
for $H = \{ \dots, -6, -3, 0, 3, 6, \dots \}$ of $G = (\Z, +)$, there are two more ($H$ itself is a coset) unique cosets:
$\{ \dots, -5, -2, 1, 4, 7, \dots \} = H + 1$, and
$\{ \dots, -4, -1, 2, 5, 8, \dots \} = H + 2$.
Note that here $H + (a + 3n) = H + a$, and since $+$ is commutative, $n + H = H + n$.

Cosets also exist for Rings, formed from Ideals (!not subrings!) (see below).

Index (of Subgroup)

The number of left cosets of a subgroup $H$ of $G$, denoted $[G:H]$ or $|G:H|$.

Observe that $[G:H] = |G/H| \space$ (if $H$ is normal and forms quotient group $G/H$).

Normal Subgroup

the usual definition is “subgroup that is invariant under conjugation” where conjugation is some forward-backward application of the group operation that is definitely not category theory all over again…
but ugh, a better, equivalent def:

A subgroup whose left and right cosets are the identical; or
A congruence class of the identity element (for some congruence relation).

obviously observable from the first definition, all subgroups of abelian groups are normal

A normal subgroup $N$ of $G$ is notated $N \lhd G$

Quotient Group

A group over cosets (of a normal subgroup).

Normal subgroups are the only subgroups whose cosets form a quotient group.
As such, quotient groups are notated as $G / N$.

How does the group operation work when the elements are (co)sets, you ask?
For cosets $aH$ and $bH$, $aH \ast bH = (a \ast b)H$ (and commutativity carries over from $\ast$ on $G$).

Symmetric Group

A symmetric group (over a set $S$) is a group of all bijections $f : S \mapsto S$ under $\circ$ (function composition).

(I.e., for finite set $S$,) A group over the permutations (of $S$).
$S_n$ denotes the symmetric group for $|S| = n$.

Each $S_n$ is unique (in that the actual contents of $S$ is irrelevant) because the permutations themselves only depend on the cardinality, $n$. (i do not smell category theory here)

Subring

What a Subgroup is to a Group.

A subset of a ring that is a ring itself.

Ideal

What a Normal Subgroup is to a Group (at least in the mechanism of forming Quotient Rings).

(although it is not a subring, but)
An additive subgroup that is also closed under multiplication with the entire ring.

In non-commutative rings, an ideal is left-, right-, or both (two-sided-) depending on which handedness of multiplication is closed.

I.e., a Left Ideal $I$ of $R$ obeys $\forall r \in R, x \in I : r \ast x \in I$. A right ideal would have $x \ast r$ instead of $r \ast x$.

$R/I$ is quotient ring, similar to $G/N$ for groups.

Order

(of a finite structure,) The number of elements its the carrier set, written $|M|$.
(of an element $x$ of a group,) The least (positive) $n$ such that $x^n = e$.

Generated (Sub)structure

A substructure (subgroup, ideal) that is constructed from one (or more) element via repeated application of the structure’s operation(s).

Commonly notated $\braket{a}$ for a substructure generated from one element $a$, called a generator,
or $\braket{S}$ for a subset $S$, called a generating subset.

For a $G$ with group operation $\ast$ and $S \subseteq G, n = |S|$:
$$\braket{S} = \{ s_1^{k_1} \ast s_2^{k_2} \ast \cdots \ast s_n^{k_n} \mid k_1, \dots, k_n \in \Z\} \ .$$

(See beginning of section for power notation.)

A cyclic subgroup is a subgroup generatable from a single element.
A cyclic group is a group generatable from a single element.

I.e, $\braket{g} = \{ \dots, g^{-1}, g^0, g^1, \dots \}$ is a cyclic subgroup for $g \in G$.

Observe that cyclic (sub)groups of finite order are, well, “cyclic” – repeated applications of the group operation to any element will eventually return to itself.
Similarly, finite cyclic (sub)groups are naturally isomorphic to $(\Z, +) / n\Z$, or modular addition.

However, cyclic (sub)groups of infinite order (e.g., $(\Z, +)$) are, obviously, not “cyclic”. Thus, they are often less confusingly called monogenous groups.

$(\Z, +)$ is a monogenous group because it can be generated from $1$, using repeated addition (and inversion to obtain $-1$): $\{ \dots, 1 + -1, 1, 1 + 1, \dots \}$. $(\Z, +)$'s only other generator is $-1$.

How ideals are generated: (similar to cosets for the 1-element case, otherwise a set of “linear combinations”)
$\braket{a} = \{ r \ast a \mid r \in R \}$;
$\braket{\{a, b\}} = \{ r \ast a + s \ast b \mid r, s \in R \}$, etc.
The two-element case links to Bézout’s Identity under a PID.

Principal (Ideal)

An ideal generatable from a single element.
Principal Ideals also have left-/right- ness in non-commutative rings just like Ideals.

E.g., a left principal ideal, generated by an $a \in R$, is $Ra = \{ r \ast a \mid r \in R \}$.

Integral Domain

A Commutative Ring where $\forall x \not = 0, y \not = 0 : x \ast y \not = 0$.
Alternatively, $a \ast b = 0 \implies a = 0 \lor b = 0$, for an unique $0$.

0 is a zero divisor; the above formulas describe the absence of any non-0 zero divisors.

Principal Ideal Domain (PID)

An Integral Domain where all Ideals are principal.

Here, all generated ideals can be generated from a single element (a “GCD”).

Aka. Principal Ring.

Other Things

Lagrange’s Theorem

$|G| = [G:H] \cdot |H|$.
I.e., $|H|$ divides $|G|$.

It follows that $g^{|G|} = e \space$ (for any $g \in G$).
And so, $|g|$ divides $|G|$.

Permutations

A permutation of an $S$ is a bijective function $\sigma : S \mapsto S$.

The identity (i.e., “do-nothing”) permutation can be notated $\text{Id}$.
The inverse of a $\sigma$ is notated $\sigma^{-1}$ where
$\sigma\sigma^{-1} = \sigma^{-1}\sigma = \text{Id}$.

The set of all permutations of an $S$, $S_n$, is a symmetric group under function composition. (Observe that composing permutations is simply sequential application.)
$|S_n| = n!$ where $|S| = n$.

Note that, like function composition, sequential permutations are not generally commutative.

Cycle

A permutation that permutes (a subset of) elements cyclically (while leaving all else fixed).
Length is the number of (distinct) elements in a cycle.

Two cycles are disjoint if they do not permute any common elements.
Disjoint cycles are commutative.

Any permutation $\sigma$ can be decomposed into a set of disjoint cycles, the orbits of its cyclic group $\braket{\sigma}$.

Order

The length of a cycle; or, for any permutation $\sigma$ in general,
the least (positive) $n$ such that $\sigma^n = \text{Id}$.

Observe that the composition of $n$ disjoint cycles with lengths $l_1, l_2, \dots, l_n$ has order $\text{lcm}(l_1, l_2, \dots, l_n)$

Transposition

A 2-cycle (of a permutation), i.e., “swapping” between two elements.

Any permutation can also be decomposed into a composition of transpositions.

Fixed-Point

A 1-cycle.
An element is fixed if it is a fixed-point.

Notation

Two-line

A matrix-ish form, where elements map from the first row to the second.

E.g., for a $\sigma \in S_5$ that transposes 1, 2 and cycles 3, 4, 5:

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 &4 \\ \end{pmatrix}$$

One-line

Two-line but the first line is implicit (omitted) and assumed to be in sorted ascending order.

This of course is only possible if an implicit “natural order” for $S$ exists.

E.g., the example above would be $\sigma = (2, 1, 5, 3, 4)$, or even as $\sigma = 2 1 5 3 4$ (with commas between numbers if ambiguous).

To avoid ambiguity with Cycle notation, the parentheses are often omitted here.

Cycle

Alternative representation as a composition of (usually disjoint) cycles.

One cycle is written as a listing of an orbit between parenthesis.
E.g., $(235)$ for $\Big( \begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 5 & 4 & 2 \end{smallmatrix} \Big)$.

I.e., for a cycle $(a_1 ~ a_2 ~ \dots ~ a_n)$, $\ a_k \mapsto a_{k+1}$. (And the last element wraps to the front.)

Composition of multiple cycles usually just uses juxtaposition.
1-cycles are usually omitted when unambiguous.
E.g., for example from two-line notation with two cycles $\tau= (12)$ and $\upsilon = (543)$, together $\sigma = \tau \upsilon$ is written $\sigma = (12)(543)$.

Canonical

Some (subjective) conventions of (most commonly) disjoint cycle notation.
Usual notations are a combination of writing cycles with the largest/smallest element first, ordering cycles by length, and explicitly writing 1-cycles.

Parity / Sign

Parity

The (parity of the) number of transpositions when a permutation is expressed as a composition thereof.

While translations of a permutation into transpositions are generally not unique, all translations for a given permutation have the same parity.

An alternative metric is inversions / disorders – ordered pairs $(x, y)$ where $\big( x > y \big) \land \big( \sigma(y) < \sigma(x) \big)$.
# transpositions ≤ # inversions, but their parity is always the same.

As a shortcut, a $n$-cycle decomposes into $n-1$ transpositions.

Sign

Another metric for parity; $+$ for even parity; $-$ for odd, commonly denoted as the function $\text{sgn} : S_n \mapsto \{ +1, -1 \}$.

Obviously,
$\text{sgn}(\text{Id}) = +1$;
$\text{sgn}(\sigma \tau) = \text{sgn}(\sigma) \cdot \text{sgn}(\tau)$.

Conversion

A permutation of $S$ can be converted to a set of disjoint cycles by tracing out the orbitals of all elements of $S$.
I.e.,

1. initialize your fast memory storage device to store the set of cycles
2. repeat until no unpicked elements left:
   2.1. pick arbitrary element not already in a cycle
   2.2. trace out its orbital
   2.3. add this to your fast memory storage

An $n$-cycle can be converted to a composition of $n-1$ transpositions by decomposing into adjacent transpositions:
$(a_1 ~ a_2 ~ \dots ~ a_n) = (a_1 ~ a_2)(a_2 ~ a_3) \cdots (a_{n-1} ~ a_n)$, or, equivalently,
$(a_1 ~ a_2 ~ \dots ~ a_n) = (a_1 ~ a_n)(a_1 ~ a_{n-1}) \cdots (a_1 ~ a_2)$.

Conversion	Method
One-line ⟶ Cycles	trace orbits
Cycles ⟶ One-line	apply to $\text{Id}$
Cycle ⟶ Transpositions	decompose adjacents
Transpositions ⟶ Cycles	⟶ one-line ⟶ cycles
One-line ⟶ Transpositions	⟶ cycles ⟶ transpositions
Transpositions ⟶ One-line	apply to $\text{Id}$

(Binary) Relations

An $n$-ary relation determines whether some “relationship” holds for any $n$-tuple of inputs.

Relations are equivalent to predicates, and boolean functions, and a lot of other things.
While relations are more intuitively understood as predicates, their definition is set-theoretic:

An $n$-ary relation $R$ (over domain sets $S_1, S_2, \dots, S_n$) is the set of all so-related $n$-tuples:
$$R \subseteq \{ r \in S_1 \times \cdots \times S_n \mid r \text{ satisfies the relation} \} \ .$$

Binary Relation

A, well, binary (two-argument) relation.

Homogeneous Relation

An $n$-ary relation where $S_1 = S_2 = \cdots = S_n$, i.e., all inputs are of the same domain.

E.g., a binary homogeneous relation over $S$ is
$$R \subseteq \{ (x, y) \mid x, y \in S \}$$

Notation

As per the set-theoretic definition, we naturally have
$(x, y) \in R$
for $(x, y)$ satisfying $R$.

Specialized, shorter notation include:

• infix: $xRy$
• postfix: $Rxy$
• prefix: $xyR$ (rare)
• Functional: $R(x, y)$

Equivalence & Congruence

Equivalence Relation

A binary relation that is reflexive, transitive, and symmetric.

Congruence Relation

An equivalence relation (on an algebraic structure) that is “compatible” with the structure’s operation(s).
I.e., results of operations done on congruent elements must be congruent.

A more concrete illustration for a binary operator $\ast$ and a congruence relation $\sim$:
$\forall a, b, x, y : \big( (x \sim a) \land (y \sim b) \implies (x \ast y) \sim (a \ast b) \big)$ .
This is important for the properties of congruence classes (see below).

Note that “equality”, or the usual meaning of the symbol $=$, is a specific (the most common) example of a equivalence relation.
Similarly, “equality mod m”, the usual meaning of $\equiv$ under modular integer arithmetic, is an example of a congruence relation.

Equivalence & Congruence Classes

Equivalence Class

A coset, or
An exhaustive subset of mutually-equivalent elements.

A “representative” member is usually chosen for an equivalence class.
The equivalence class of a representative $a \in S$ (under a $=$) is notated $[a]$ or $[a]_=$, and
$$[a] \coloneqq \{ x \in S \mid x = a \} \ .$$

The set of all equivalence classes of $S$ (under $=$) is called the quotient set, notated $S/\!=$. Note that this is a specific partition of $S$.

Observe that when the $S$ forms a group, this is another way to define quotient groups (see above).
Even the $/$ notation is analogous (the “denominator” can be either a subgroup or an equivalence relation).

Congruence Class

Everything is the same as equivalence classes, except the set is associated with operations that make it a structure.

Residue Class is a synonym when discussing modular arithmetic.

The partition of a structure by a congruence relation has similar “quotient” names, specific to the exact type of structure: e.g., quotient ring and quotient group.

Congruence classes are exactly cosets, and $[e]_\sim$, the congruence class of a group’s identity element, is a subgroup.

The congruence/residue class of an $a \in \Z$ under modulo $m$ is notated $[a]_m$ or $(a \mod m)$, and
$$[a]_m \coloneqq \{ x \in \Z \mid x = a + km \}$$

where $k \in \Z$.

Modular Arithmetic

Modular arithmetic from an abstract-algebraic view.

NOW you should see that all modular arithmetic are just quotient rings (of $\Z$)!
For a quotient ring $\Z / \!\braket{a}$, where $\braket{a}$ is the ideal generated from $a$, $a$ is precisely the modulo of the equivalent modular arithmetic.

The quotient rings of $\Z$ also satisfy the inverse axiom for multiplication for free, so modular arithmetic are Fields and can do division.

Group Ring-theoretic Foundation

First, note that $\Z$ is obviously a ring under the usual addition and multiplication.
Now trust me bro everything else are just quotient rings.

$n\Z$ denotes the principal ideal (of the $\Z$-ring) generated from $n$. I.e., $n\Z = \braket{n}$.
As such, $\Z / n\Z$ is a quotient ring, namely, residue classes under modulo $n$.

Observe that $I = \braket{n}$ of $n$ in a $\Z$-ring is more concretely $\{ k \times n \mid k \in \Z \}$ – all multiples of $n$, or the residue class $[0]_n$.
Then, the cosets of $I$ are obviously $I + 1$ ($[1]_n$), $I + 2$ ($[2]_n$), etc.
OBVIOUSLY, this is just $\{ [0]_n, [1]_n, \dots, [n-1]_n \}$, or the set of residue classes modulo $n$.

$\Z / n\Z$ is therefore modular arithmetic modulo $n$.

To explicitly notate addition and multiplication as their modular variants, use $\oplus$ and $\otimes$.

Modulo Addition Group

$(\Z / n\Z)^+$ denotes the additive group of integers modulo $n$.

Unlike below, we get this group “for free” because $\Z / n\Z$ is a ring, so its additive substructure is naturally an additive group.

Modulo Multiplication Group

$(\Z / n\Z)^\times$ denotes the multiplicative group of integers modulo $n$.
However, it is not (always) $\Z / \!\braket{n}$ under modular multiplication, as a ring’s multiplicative substructure is only a monoid.

To make “$(\Z / n\Z)^\times$” a group under multiplication, we just have to make sure all elements have inverses. (the other axioms are satisfied as it is a monoid, coming from a ring)
Turns out¹, only elements coprime with $n$ have inverses.
(Note that $[0]_n$ is not coprime with anything, and obviously doesn’t have an inverse.)
So,

$$(\Z / n\Z)^\times = \{ [a]_n \mid \text{gcd}(a, n) = 1 \}$$

and $\big| (\Z / n\Z)^\times \big| = \phi(n)$
The group is Abelian because i said so.

$(\Z / n\Z)^\times$ is cyclic iff $n$ is $1$, $2$, $4$, $p^k$, or $2 p^k$ ($p$ is a prime).
In this case, a generator element $g$ is also called a primitive root modulo $n$.

$(\Z / n\Z)^\times$ is isomorphic to $(\Z / (n-1)\Z)^+$ when $n$ is prime, obviously.

Modular Arithmetic Field

inshallah you see now that $\Z / n\Z$ is a field (under $\oplus$ and $\otimes$) when $n$ is prime.

Other Stuffs

Euler’s Totient Function $\phi$

$\phi(n) = \big| \{ x \in [1,n) \mid \text{gcd}(x, n) = 1 \} \big|$,
the count of whole numbers less than and coprime with $n$.

Alternatively,
$$\phi(n) = \prod p_i^{k_i-1}(p_i-1)$$

for $n = \prod p_i^{k_i}$, its prime factorization.

Still,
$$\phi(n) = n \prod_{p | n} \big( 1 - p^{-1} \big)$$

for primes $p$.

See also, Carmichael function.

Euclidean Algorithm

Iterative algorithm to compute $\text{gcd}$

Tricks

Fast Modular Exponentiation

If the modulo multiplication group is cyclic, then obviously our life would be much easier (as we can directly decompose powers).

$$a^b \mod m$$

$\mathbf{\text{gcd}(a, m) =1}$:
$a^b \equiv a^{b \mod \phi(m)} \mod m$

Useful for $b \gg m$.
Alternatively, eg., when $b < \phi(m)$,
the power can be safely decomposed (to use exponentiation by squaring or other factoring methods).

$\mathbf{\text{gcd}(a, m) = g}$:

ur cooked bro

for $d = a / g$ and $f = m / g$,
$$\begin{align*} a^b \mod m \\ g^b \cdot d^b \mod m \\ g \cdot (g^{b-1} \cdot d^b \mod f) \mod m \end{align*}$$

idk

Linear Algebra

help, i can’t deal with actual numbers.

---

1. the reasoning is actually the same as that of 0: zero-divisors do not have inverses, and for an element $x$, unless $\text{gcd}(x, n) = 1$, there exists a $k \not = 0$ such that $x \times k \equiv 0 \mod n$, making $x$ a zero divisor!

   Now, in division rings, $0$ itself is special-cased as the one unique zero-divisor allowed… but groups do not have this allowance so we can’t even have 0 itself in multiplicative groups.

   ↩︎