1 Groups

1.1 Definition and Basic Terms

Given a set with a binary operation $ (G,\cdot) $, if it satisfies:

• Closure: for all $ a,b\in G $, $ a\cdot b\in G $;
• Associativity: for all $ a,b,c\in G $, $ (a\cdot b)\cdot c=a\cdot(b\cdot c) $;
• Identity: there exists $ e\in G $ such that for all $ a\in G $, $ e\cdot a=a\cdot e=a $;
• Inverse: for every $ a\in G $ there exists $ a^{-1}\in G $ with $ a\cdot a^{-1}=a\cdot a=e $,

then $ (G,\cdot) $ is a group.
The order of a group is the number of its elements.

• With only closure + associativity, the structure is a semigroup.
• We often call $ G $ the underlying set, and $ (G,+) $ or $ (G,\cdot) $ the group.

1.2 Abelian Groups

If in addition commutativity holds, i.e., $ a\cdot b=b\cdot a $ for all $ a,b\in G $, then $ (G,\cdot) $ is abelian.

1.3 Cyclic Groups

A cyclic group is generated by one element; all cyclic groups are abelian.

Notation example: $ f^k $ means $ \underbrace{f\cdots f}_{k} $.
Caution. In a cyclic group, elements commute because they are powers of the same generator (hence reduce to addition of exponents), not merely because of associativity.

1.4 Subgroups and Normal Subgroups

A subgroup is a subset of $ G $ that itself forms a group under the same operation.

A normal subgroup $ N\trianglelefteq G $ is defined by

Define the left coset of $ N $ by $ gN $ and the right coset by $ Ng $.
Normality can be understood as “left cosets = right cosets (for all $ g $)”, which ensures the quotient’s operation is well-defined.

• In abelian groups, every subgroup is normal.
• Normal subgroups are well-defined substructures of a group.

1.5 Quotient Groups

The elements of a quotient group are the cosets of a normal subgroup $ N $.
Example for the additive group $ \mathbb Z $:

It is also common to write, using representatives,

• Quotient groups are not subgroups, the role of subgroups and quotient groups couldn't be swapped.
• The representatives are also called equivalence class.

1.6 Simple Groups

A simple group is a nontrivial group with no normal subgroups other than the identity subgroup and itself. They play a role analogous to primes in arithmetic.

1.7 Symmetric and Alternating Groups

Example:

where $ (123) $ means $ 1\mapsto2,\ 2\mapsto3,\ 3\mapsto1 $.
The symmetric group has order $ n! $, and the alternating group has order $ \dfrac{n!}{2} $.

The alternating group consists of even permutations (while the symmetric group contains both odd and even permutations).

Example:

Note that $ (12)(34) $ means apply $ (34) $ first and then $ (12) $.
Alternating groups are different from cyclic groups.

1.8 Matrix Groups

• General Linear Group

  \[GL_n(\mathbb R)=\{\,A\in M_{n\times n}(\mathbb R):\det(A)\neq 0\,\}. \]

  If $ \det(A)=0 $, the linear map is not invertible.

• Special Linear Group

  \[SL_n(\mathbb R)=\{\,A\in GL_n(\mathbb R):\det(A)=1\,\}, \]

  which preserves volume.

• Orthogonal Group

  \[O(n)=\{\,A\in GL_n(\mathbb R):A^\top A=I\,\}. \]

  Orthogonality means columns/rows are orthonormal; geometrically these are rotations and reflections.
  A matrix is often viewed as a collection of column vectors.

1.9 Lie Groups

A Lie group is a group that is also a smooth manifold.

2 \(\sigma\)-Algebra

Let $ X $ be a set. A $ \sigma $-algebra $ \mathcal F\subseteq \mathcal P(X) $ satisfies:

1. Contains the whole space:

   \[X\in\mathcal F. \]

2. Closed under complementation: if $ A\in\mathcal F $, then

   \[X\setminus A\in\mathcal F. \]

3. Closed under countable unions: if $ A_1,A_2,\dots\in\mathcal F $, then

   \[\bigcup_{i=1}^\infty A_i\in\mathcal F. \]

Notes:

• A (set) algebra only requires closure under finite unions (countable may be infinite), hence is weaker than a $ \sigma $-algebra.
• We also use \(\sigma\)-field as a synonym for $ \sigma $-algebra.

Example/Counterexample. Consider

If $ \mathcal F $ contains all sets of the form $ (\cdot,\cdot] $ of this type only, then

and $ (0,1) $ is not in that class, so this is not a $ \sigma $-algebra.

3 Rings and Fields

3.1 Rings

A ring is a set $ R $ with two operations (addition and multiplication) such that:

• $ (R,+) $ is an abelian group;
• multiplication on $ R $ is associative;
• distributive laws hold.

If multiplication is commutative, $ R $ is a commutative ring.
If there is a multiplicative identity, it is often called unity.

3.2 Fields and Examples

If $ (R,\cdot) $ with unity is commutative and $ R\setminus{0} $ forms an abelian group under multiplication (i.e., every nonzero element has a multiplicative inverse), then $ R $ is a field.

Example:

However, $ \mathbb Z_p $ is a field when $ p $ is prime.

(Heuristically, one often categorizes algebraic structures into “group-like” and “ring/field-like”.)

3.3 Polynomial Rings

For a ring $ R $, define the polynomial ring $ R[x] $:

Example:

3.4 Ideals

Ideals play the role in rings analogous to normal subgroups in groups: they are the right substructures for forming quotient rings.

• Quotient rings are made of cosets of an ideal.
• Ideals are well-defined substructures of a ring.

Notation reminder: $ N\trianglelefteq G $ for normal subgroups, while $ I\subseteq R $ for ideals.

3.5 Quotient Rings

For polynomials, write

to mean $ h(x)\mid (f(x)-g(x)) $.

In $ \mathbb Z_2[x] $, let

Then

Since in $ \mathbb Z_2 $ we have $ -x=x $ and $ -1=1 $,

Hence every polynomial can be reduced to a linear representative $ a+bx $. Therefore

In general, the size formula is

3.6 Galois Fields

We denote finite fields by $ GF(p) $ (for prime $ p $), and more generally $ GF(p^n) $.

• $ GF(p^n) $ has $ p^n $ elements (this is called field extension).
• For $ GF(2^n) $ specifically:
  • Addition equals bitwise XOR;
  • Addition equals subtraction (since $ 1=-1 $).

An important equality:

Irreducible polynomials may not be unique, but the extended field must be isomorphism to each other.

4 Crypto

This section especially points to RSA, where groups/rings/fields and modular arithmetic are central.

5 Pólya’s Enumeration Theorem

Especially useful for coloring and other combinatorial counting problems under group actions.