[Tutorial] A New Perspective on Numbers and Operators: Introducing Group Theory

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	157
6	Qingyu	156
7	djm03178	152
7	adamant	152
9	luogu_official	151
10	awoo	147

We often start our mathematical journey with counting, primes, and basic arithmetic. Then we encounter modular arithmetic, with its intriguing properties and theorems like Euclid's algorithm and the Chinese Remainder Theorem. But what if there's a deeper, more abstract framework that ties all these concepts together? You might have encountered hints that group theory is behind some clever algorithms and data structures (like this comment suggests). But if you've tried to learn about it, you might have found resources that felt either too abstract and disconnected from your existing knowledge (for instance), or too intimidating and complex (like this one).

This blog aims to bridge that gap. We'll start with familiar ground in discrete math and modular arithmetic, and then progressively introduce the core concepts of group theory, showing how they provide a powerful and elegant framework for understanding a wide range of mathematical and computational problems.

1. Basic Discrete Mathematics

I: Definitions and Terms

Equivalence Relation is a binary relationship denoted by $$$\sim $$$ between elements of set $$$X$$$ , if and only if $$$\sim$$$ follows all 3 Reflexive, Symmetric, and Transitive relation, let $$$a,b,c \in X $$$ then following relations must be exist
i. Reflexive: $$$a \sim a$$$
ii. Symmetric: if $$$a \sim b$$$ then there must be $$$ b \sim a$$$
iii. Transitive: if $$$a \sim b$$$ and $$$ b \sim c$$$ then there must $$$a \sim c$$$
Ex: $$$X = \begin{Bmatrix} a,b,c \end{Bmatrix}, ~ R = \left( (a,b),(b,a),(a,c),(b,c),(c,a),(c,b) \right)$$$ , $$$R$$$ contains all possible relations between $$$X$$$ , it follows Symmetric and Transitve but not Reflexive, in this example $$$\sim$$$ is not an Equivalence Relation.
We call $$$d \geq 0$$$ 'divisor' of $$$a \geq 0$$$ if and only if there exist $$$k \in \mathbb{Z}$$$ such that $$$a = kd$$$ , or we say "$$$d$$$ divides $$$a$$$" and write it as $$$d \mid a$$$ .
i. Trivial divisors are $$$1$$$ and $$$a$$$ and non-trivial divisors are called Factors, if there are no non-trivial divisors then $$$a$$$ is called prime number else it will be called a composite number.
ii. Every integer divides $$$0$$$ , and $$$0$$$ , $$$1$$$ and negative are neither prime nor composite.

II: Some Important Conclusions from above 2 points:

Division Theorem: $$$a = qn + r$$$ , given $$$a$$$ and $$$n$$$ there exist a unique $$$q$$$ and $$$r$$$ such that $$$0 \leq r < n$$$

Proof

If $$$d \mid a$$$ , $$$d \mid b$$$ then $$$d \mid (ax+by) \forall x,y \in \mathbb{Z}$$$ . Similarly if $$$d \mid a$$$ , $$$d \mid (ax+by)$$$ $$$ \forall x,y \in \mathbb{Z}$$$ then $$$d \mid b$$$ .
Let $$$a,b$$$ be non-zero integers then set $$$ S = \begin{Bmatrix} ax + by : x,y \in \mathbb{Z} \ \end{Bmatrix} $$$ then smallest positive number in the set will be $$$gcd(a,b)$$$ .

Proof

If $$$gcd(a,p)=1$$$ and $$$gcd(b,p)=1$$$ then $$$gcd(ab,p)=1$$$ , can easily be proved by above statement. Similarly for all primes $$$p$$$ , if $$$p \mid ab$$$, either $$$p \mid a$$$ or $$$p \mid b$$$ or both.
Unique Prime Factorization, Euclidean to find $$$gcd$$$, and Extended Euclidean to find $$$x,y$$$ for $$$gcd(a,b) = ax + by$$$ . Can easily be derived from 2nd , 4th bullet point.

If you wanna look..

Now you can go on a journey to explore fancy Mobius functions, Sieve and Multiplicative functions that deals with all sort of patterns in Prime numbers.

2. Introduction to Modular Arithmetic

Lets define few terms before moving forward, just like we above introduced 'Divisors', 'Prime', and 'Composite'. They may sound scary but bear with it, they will make a lot of things convenient.

I: Definitions and Terms

Class: a collection of mathematical objects, just like sets but without paradoxes that Set theory introduces. (Just think of them as normal sets it will be fine.)
Equivalence class: Given Equivalence relation $$$\sim$$$ on $$$X$$$ and , we define Equivalence of class of $$$a$$$ as set of $$$x \in X$$$ such that $$$ [a] = \begin{Bmatrix} x \in X : x \sim a \ \end{Bmatrix} $$$ , in class of $$$[a]$$$ every 2 element will be considered "Equivalent", $$$\sim $$$ becomes $$$ \equiv $$$ in this case.
Ex: $$$X = \begin{Bmatrix} a,b,c,d,e,f \end{Bmatrix} $$$ ,
$$$ R = \left( (a,a),(b,b),(a,b),(b,a),(c,c),(c,d),(d,c),(d,d),(d,e),(e,d),(e,e),(e,c),(c,e),(f,f) \right)$$$ , then $$$[a] = [b] = \begin{Bmatrix} a,b \ \end{Bmatrix} , ~ [b]=[c]=[d] = \begin{Bmatrix} b,c,d \ \end{Bmatrix} , ~ [f] = \begin{Bmatrix} f \ \end{Bmatrix}$$$ . Its a way of saying from $$$[a]$$$ 's point of view these elements are equivalent.
Finite Groups: Its a set $$$S$$$ with binary operator $$$\oplus$$$ such that following properties holds:
i. Closure: For all $$$a,b \in S$$$ , $$$a \oplus b \in S$$$ .
ii. Identity: There exists element $$$e \in S$$$ , such that $$$a \oplus e = e \oplus a = a$$$ for all $$$a \in S$$$ . Its called the identity element.
iii. Associativity: For all $$$a,b,c \in S$$$ , we have $$$\left( a \oplus b \right) \oplus c = a \oplus \left( b \oplus c \right) $$$ .
iv. Inverses: For all $$$a \in S$$$ there exist such element $$$b \in S$$$ such that $$$a \oplus b = b \oplus a = e$$$ . Its called the inverse of $$$a$$$ .
v. "Finite" in Finite Group means $$$|S|< \infty $$$ .
Abelian Group: If a Finite Group's $$$G$$$ 's operator $$$\oplus$$$ also happens to follow commutative property $$$a \oplus b = b \oplus a$$$ for all $$$a,b \in S$$$ then it will be called Abelian Group.
Finite Subgroup: Given group $$$G = \left( S, \oplus \right)$$$ , if we take $$$S' \subseteq S$$$ such that $$$S'$$$ with operator $$$\oplus$$$ follows all the properties mentioned in 3rd point, then we will call this new group $$$G' = \left( S', \oplus \right)$$$ as Finite Subgroup of $$$G$$$ .

II: Helpful Equivalence Classes and Sets

$$$ [a]_n = \begin{Bmatrix} a+kn: k \in \mathbb{Z} \ \end{Bmatrix} $$$ , we call it "Equivalence class of modulo $$$n$$$ ",
ex: $$$[3]_{10} = \begin{Bmatrix} \cdots, -7,3,13,23,\cdots \ \end{Bmatrix} $$$ , $$$13 \equiv -7 \pmod{10}$$$ , $$$3 \equiv 23 \pmod{10}$$$ they are equivalent from $$$[3]_{10}$$$ 's point of view that's why we have to mention $$$ \pmod{n}$$$ at the end, similarly we can write as $$$[3]_{10} = [-7]_{10}$$$ . We will take smallest positive number $$$a$$$ to present the equivalence class. Note that we used $$$\equiv$$$ Equivalence symbol when comparing numbers in same classes and $$$=$$$ Equals Symbol when comparing Classes.
Given $$$n$$$ there can be only $$$n$$$ equivalence classes since in $$$[a]_n$$$ , $$$0\leq a <n$$$ , and set of all equivalence classes is $$$\mathbb{Z_n} = \begin{Bmatrix} [a]_n : 0 \leq a < n \ \end{Bmatrix}$$$ , $$$\mathbb{Z_n} = \begin{Bmatrix} [0]_n,[1]_n,[2]_n, \cdots , [n-1]_n \ \end{Bmatrix}$$$ , $$$[n]_n = [0]_n ~,~ [n+1]_n = [1]_n $$$ , repetition will happening afterwards.

III: Note about Equivalence Classes

To make defined Equivalence classes will behave like Finite Groups, so we need to define $$$\oplus$$$ and $$$\otimes$$$ operations for equivalence classes. We can easily define Addition and Multiplication for $$$\mathbb{Z_n}$$$ because addition and multiplication on classes can directly be applied to their integer representation to give unique equivalence classes in return.
i. $$$[a]_n \oplus [b]_n = [a+b]_n$$$ , for any $$$n$$$
ii. $$$[a]_n \otimes [b]_n = [a \cdot b]_n$$$ , given $$$a,b$$$ are co-prime with $$$n$$$

Proof of uniqueness

It might seem like a lot of complicated terms and concepts for just doing modulo maths, but thinking in terms of Equivalence classes and a pair of Set with its own Personal Operator $$$(S, \oplus)$$$ will make a lot of things convenient in the run.

IV: Some Important Conclusions from the above definitions

Our Finite Group $$$ \mathbb{Z_n} $$$ with $$$\oplus$$$ is an Abelian group, can easily be proved by definition. Lets call this group $$$G = (\mathbb{Z_n},\oplus)$$$ an Addivtive group of integers under $$$\bmod n$$$ . Ex: $$$ \mathbb{Z_5} = \begin{Bmatrix} [0]_n, [1]_n, [2]_n, [3]_n, [4]_n \ \end{Bmatrix} $$$ , adding any 2 classes will give other class $$$\in \mathbb{Z_5} $$$ .
Lets define $$$ \mathbb{Z_n}^{*} = \begin{Bmatrix} [a]_n \in \mathbb{Z_n} : gcd(a,n) = 1 \ \end{Bmatrix} $$$ , then $$$\left( \mathbb{Z_n}^{*} , \otimes \right)$$$ . We need $$$gcd(a,n)=1$$$ for inverses to exist. It can easily be proved with above definitons that its also an Abelian group. Its also called Multiplicative group of integers under $$$\bmod n$$$ . Ex: $$$\mathbb{Z_{10}^{*}} = \begin{Bmatrix} [1]_n, [3]_n, [7]_n, [9]_n \ \end{Bmatrix} $$$ , multiplying any 2 classes will give another class $$$\in \mathbb{Z_n}^{*}$$$ .
The size of $$$\mathbb{Z_n}^{*}$$$ is defined as $$$\phi(n)$$$ Euler Phi Function. $$$ \phi(n) = \displaystyle n \prod_{p: ~ p ~ is ~ prime ~ and ~ p \mid n} \left( 1 - \frac{1}{p} \right)$$$ .

Proof

Normally you can easily prove it after proving $$$\phi(ab) = \phi(a) \phi(b)$$$ for $$$gcd(a,b)=1$$$ is a Multiplicative function, but we need CRT for that and we have not reached that stage yet. We will prove it Old school way with Inclusion Exclusion. Let number $$$n$$$ consists of primes $$$(p_1,p_2, \cdots , p_k)$$$ , $$$\phi(n) = n - ~no.of~divisors $$$ ,

$$$ \begin{align*}

\phi(n) &= n - \left( \displaystyle \sum_{j_1}^k \frac{n}{p_{j_1}} - \displaystyle \sum_{j_1<j_2}^k \frac{n}{p_{j_1} p_{j_2}} \cdots + \displaystyle \sum_{j_1<j_2< \cdots j_k}^k \frac{n}{p_{j_1} p_{j_2} \cdots p_{j_k}} \right) \\

\end{align*} $$$

Let $$$S_{g}^{(t)}$$$ = Sum going till $$$t$$$ the term with $$$g$$$ pair of primes, $$$ \displaystyle \sum_{j_1<j_2< \cdots <j_g}^{t} \frac{1}{p_{j_1} p_{j_2} \cdots p_{j_g}}$$$ . It will simplify the summation, assuming the last term is positive. If $$$g<t$$$ then $$$S_{g}^{t} = 0$$$ , because there are no terms that satisfy iteration indice inequality $$$j_1<j_2< \cdots <j_g$$$ .

$$$ \begin{align*}

\frac{\phi(n)}{n} &= 1 - \left( S_{1}^{(k)}- S_{2}^{(k)} + S_{3}^{(k)} - S_{4}^{(k)} + \cdots + S_{k}^{(k)} \right) \\ \frac{\phi(n)}{n} &= 1 - \left( \left( \frac{1}{p_k} + S_{1}^{(k-1)} \right) - \left( \frac{1}{p_k} \cdot S_{1}^{(k-1)} + S_{2}^{(k-1)} \right) + \left( \frac{1}{p_k} \cdot S_{2}^{(k-1)} + S_{3}^{(k-1)} \right) - \cdots + \left( \frac{1}{p_k} \cdot S_{k-1}^{k-1} \right) \right) \\

\frac{\phi(n)}{n} &= \left( 1 - \frac{1}{p_k} \right) - \left( 1 - \frac{1}{p_k} \right) S_{1}^{(k-1)} + \left( 1 - \frac{1}{p_k} \right) S_{2}^{(k-1)} - \cdots - \left( 1 - \frac{1}{p_k} \right) S_{k-1}^{(k-1)} \\

\frac{\phi(n)}{n} &= \left( 1 - \frac{1}{p_k} \right) \cdot \left( 1 - S_{1}^{(k-1)} + S_{2}^{(k-1)} - S_{3}^{(k-1)} + \cdots - S_{k-1}^{(k-1)} \right) \\

\end{align*} $$$

Keep on doing it $$$(k-1)$$$ times more (or use the inductive argument with base case being $$$\phi(p) = p-1$$$), at the end you will get all the products.

$$$ \begin{align*}

\phi(n) &= n \displaystyle \prod_{p: p~ is ~ prime, ~p \mid n} \left( 1 - \frac{1}{p} \right)

\end{align*}

$$$

Euler Theorem: $$$a^{\phi(n)} \equiv 1 \bmod n$$$ for any $$$a \in \mathbb{Z_n}^{*}$$$ ,

Proof

Chinese Remainder Theorem. Up to this point, our algebraic operations have been confined to equivalence classes within a single $$$\mathbb{Z_n}$$$ . The CRT expands this, allowing us to perform algebra across different $$$n$$$-s.
Given Integers $$$a$$$ and $$$n = n_1 n_2 \cdots n_k$$$ where the $$$n_i$$$ are pairwise relatively prime, then there exists a correspondence $$$[a]_n \longleftrightarrow ( [a_{1}]_{n_1} , [a_2]_{n_2} , \cdots [a_k]_{n_k} ) $$$ , $$$a_i = a \bmod n_i$$$, where $$$a \in \mathbb{Z_n}$$$ , $$$a_i \in \mathbb{Z_{n_i}}$$$ . It is a one-to-one mapping between $$$\mathbb{Z_n} \longrightarrow \mathbb{Z_{n_1}} \times \mathbb{Z_{n_2}} \cdots \times \mathbb{Z_{n_k}}$$$ .

Exploring Implications

3. Order and Structure: Exploring Subgroups

I: Subgroups

This section delves into the concept of subgroups, demonstrating the far-reaching implications of group theory. The operations discussed are commutative(Abelian Groups), leading to powerful results such as Euler's theorem. However, we can derive other significant conclusions using the concept of subgroups. Some examples of subgroup are

Ex1: Given $$$(\mathbb{Z_9}, \oplus)$$$ which is $$$ \mathbb{Z_9} = \begin{Bmatrix} [0]_n, [1]_n, [2]_n, [3]_n, [4]_n, [5]_n, [6]_n, [7]_n, [8]_n \ \end{Bmatrix} $$$ , then $$$\mathbb{Y_n} = \begin{Bmatrix} [0]_n, [3]_n, [6]_n \ \end{Bmatrix}$$$ is a subgroup.

Ex2: Given $$$(\mathbb{Z_{7}}^{*}, \otimes)$$$ which is $$$ \mathbb{Z_{7}}^{*} = \begin{Bmatrix} [1]_n, [2]_n, [3]_n, [4]_n, [5]_n, [6]_n \ \end{Bmatrix} $$$ , then $$$\mathbb{Y_n} = \begin{Bmatrix} [1]_n, [2]_n, [4]_n \ \end{Bmatrix}$$$ is a subgroup.

Notice that the order of each subgroup, $$$|G'|$$$ , divides the order of the parent group, $$$|G|$$$ . This is, in fact, a formally provable result known as Lagrange's Theorem.

Lagrange Theorem: If $$$H$$$ is subgroup of $$$G$$$, then $$$|H|$$$ is a divisor of $$$|G|$$$ .

Proof

Let $$$H$$$ be the subgroup of $$$G$$$ , and we are assuming operation $$$\oplus$$$ is just associative and do not commute. Lets define $$$g_1 \oplus H = \begin{Bmatrix} g_1 \oplus h \mid \forall ~ h \in H \ \end{Bmatrix}$$$ and $$$ H \oplus g_1 = \begin{Bmatrix} h \oplus g_1 \mid \forall ~ h \in H \ \end{Bmatrix}$$$ for given $$$g_1 \in G$$$ , both are just normal sets.

Claim1: For all $$$g \in G$$$ , $$$g \oplus G = G$$$

Proof, try it as a Homework

Claim2: If anyone of the below Lemma is true then other 4 are true as well. Without loss of generality lets take 2 elements from $$$g_1,g_2 \in G$$$ ,

$$$g_1 \in g_2 \oplus H$$$ .
$$$g_{1}^{-1} \oplus g_2 \in H$$$ , or $$$g_{2}^{-1} \oplus g_{1} \in H$$$
$$$g_1 \oplus H = g_2 \oplus H$$$ .
$$$ H \oplus g_{1}^{-1} = H \oplus g_{2}^{-1}$$$ .
$$$g_1 \oplus H \subseteq g_2 \oplus H$$$ .

Proof, try them as a homework,

To prove this, we will take one Lemma at a time and derive other four.

Taking $$$g_1 \in g_2 \oplus H$$$ ,

Proof

Taking $$$g_{1}^{-1} \oplus g_2 \in H$$$ ,

Proof

Taking $$$g_1 \oplus H = g_2 \oplus H$$$ ,

Proof

Taking $$$ H \oplus g_{1}^{-1} = H \oplus g_{2}^{-1}$$$ ,

Proof

Taking $$$g_1 \oplus H \subseteq g_2 \oplus H$$$ ,

Proof

Corrolary from Claim2: Given 2 sets $$$g_i \oplus H $$$ and $$$g_j \oplus H$$$ , they are either equal or contain no same element.

Proof, try it as a homework

From Claim 1, we know that $$$|g_i \oplus H| = |H|$$$ for all $$$i$$$ . Claim 2 states that any two sets $$$g_i \oplus H$$$ and $$$g_j \oplus H$$$ are either identical or disjoint. Therefore, the set of all subsets $$$g_i \oplus H$$$ for all $$$i$$$ forms a partition of $$$G$$$. This means that when $$$H$$$ operates on all elements of $$$G$$$ it results in a division of $$$G$$$ into distinct teams (the subsets) such that applying $$$H$$$ to any element within a team keeps it within the same team. These teams are formally known as Partitions and can be described like $$$\displaystyle \bigcup_{g_i \in G} g_i \oplus H = G$$$ . Since each partition is of size $$$H$$$, we can say $$$t |H| = |G| $$$, $$$t$$$ being number of partitions.

Hence $$$|H|$$$ divides $$$|G|$$$ . It looks like a lot of work to prove such an innocent fact.

II: Operators

We've seen groups composed of numbers and equivalence classes. But what if the elements of a group were operators themselves? Just as matrices can be added, subtracted, and multiplied, and can also transform vectors, mathematical operators, in general, possess a similar algebraic structure and similarly in continuous mathematics, differential operators like $$$\frac{d}{dt}$$$ and $$$\frac{\partial }{\partial x}$$$ exhibit algebraic properties analogous to matrices, they can be added, multiplied (composed), and when applied to functions, they transform them, much like matrices transform vectors. This suggests that we can treat operators themselves as elements within a group, extending the concept of a group beyond just numbers or equivalence classes.

To illustrate these concepts in a simplified setting, we'll work with a discrete and finite group of operators, let's construct a finite group, $$$G = (S, \star)$$$ , where $$$S$$$ is a set of operators $$$S = \begin{Bmatrix} \oplus_1 , \oplus_2, \oplus_3 , \cdots , \oplus_{|S|} \ \end{Bmatrix}$$$ and $$$ \star $$$ is a binary operation representing the composition of these operators. Since operators act on objects, let $$$x$$$ be an object and $$$X$$$ be the set of all possible results after applying the operators.

Since $$$G$$$ is a group acting on $$$X$$$ , lets more explicitly state the properties it follows:

Identity Element: There exists an element $$$e$$$ in $$$G$$$ such that $$$e \cdot x = x$$$ for all $$$x \in X$$$ .
Composition Property (similar to Associativity): $$$ \left( \oplus_i \star \oplus_j \right) \cdot x = \oplus_i \cdot \left( \oplus_j \cdot x \right) $$$ , for all $$$\oplus_i , \oplus_j \in G$$$ and for all $$$x \in X$$$ .
Closure Property: $$$\oplus_i \star \oplus_j = \oplus_k$$$ , for all $$$\oplus_i, \oplus_j, \oplus_k \in S$$$ .
Inverse: For all $$$\oplus_i \in G$$$ there exists some $$$\oplus_j$$$ such that $$$\oplus_i \star \oplus_j = e$$$ .

To understand what's happening, there are two points of view:

How a single $$$\oplus_i$$$ transforms every $$$x \in X$$$ . Note that even when $$$\oplus_i \neq e$$$ , there will be certain $$$x$$$ that it can't change. For example, let's say $$$\oplus_3 = $$$ operation that cyclically shifts an array to the right by $$$3$$$ positions , and $$$x = (0,1,1,0,1,1,0,1,1)$$$ . Then $$$\oplus_3 \cdot x = x$$$ whereas $$$\oplus_2 \cdot x \neq x$$$ because cyclic shift of $$$2$$$ changes $$$x$$$ .
How a single $$$x$$$ is affected by every $$$\oplus \in G$$$ . Similarly, from an element's point of view, certain $$$\oplus$$$ will change it, and certain $$$\oplus_i$$$ won't affect it at all.

As you all might be guessing, the "not-changing" aspect is related to the 'Symmetry' shown by $$$X$$$ towards $$$G$$$ . Let's formally name those 2 point of view:

Fixed Points: Given $$$\oplus \in G$$$ , $$$F_\oplus = \begin{Bmatrix} x \mid \oplus \cdot x = x, x \in X \ \end{Bmatrix} $$$ , it's the set of $$$x$$$ that $$$\oplus$$$ can't change.
Orbit: Given $$$x \in X$$$ , $$$ \mathscr{O}_x = \begin{Bmatrix} \oplus \cdot x \mid \forall \oplus \in G \ \end{Bmatrix}$$$ , It's the set of all elements that $$$x$$$ can be transformed into.
Stabilizer: Given $$$x \in X$$$ , $$$ H_x = \begin{Bmatrix} \oplus \mid \oplus \cdot x = x , \oplus \in G \ \end{Bmatrix} $$$ , it's a subgroup of $$$G$$$ that can't change $$$x$$$ , as this small subset follows all 4 group properties.

We will use insights used in proving the Lagrange Theorem to make connections between Fixed Points, Orbit and Stabilizer.

Connection between Fixed Points and Stabilizer, $$$ \displaystyle \sum_{\oplus \in G} |F_\oplus| = \displaystyle \sum_{x \in X} |H_x| $$$ .

Proof, try it as a homework

Connection between Stabilizer and Orbit, $$$ |\mathscr{O_x}| |H_x| = |G| $$$ , for all $$$x \in X$$$ .

Proof

Connection between Orbites and Fixed points, $$$ \text{Number of Unique Orbits} = \left( 1 / |G| \right) \displaystyle \sum_{\oplus \in G} |F_\oplus|$$$ .

Proof, try it as a homework

Connection between Fixed Points and Orbits is important as it shifts burden of counting unique $$$x$$$ after transformation from iterating every $$$x \in X$$$ to iterating over $$$G$$$ , by just counting for each $$$\oplus \in G$$$ what number of $$$x$$$ it cannot change, summing that will give our result. In practice its very convenient to count from operators point of view.

Existence of Symmetry(in geometry, morphing graphs, cyclic arrays etc) means there exists a Subgroup that deals with it, and whenever we have subgroups we can apply our result, since symmetries are everywhere this result becomes important hence it got a special name its called Burnside Lemma.

Classic Problems:

Counting Grids ,
Counting Necklaces,
Convolution on the Multiplicative Monoid Z/2Z
Evolution of Weasels from SWERC 2021-2022.
Wojtek and Card Tricks

Final Words

Ultimately, abstract algebra is about the interplay between operators and operands. Different restrictions on these interactions give rise to different algebraic structures: Monoids (closure, associativity, identity), Groups (adding inverses), Abelian groups (commutativity), Rings (two operations with distributivity), and Fields (invertible and commutative second operation). These structures are not mere abstract curiosities; they have profound consequences. They underpin results like the Abel-Ruffini theorem (unsolvability of the quintic), Burnside's Lemma, Graph Isomorphism , and even the generalization of the Fourier transform via Pontryagin duality.

Even simpler and more common data structures, like Segment Trees, require operations to be associative. Lazy propagation is used to handle non-commutative operations. To efficiently handle both range queries and range updates, associativity and distributivity (between the main operation and the update operation) are essential.

Since computation fundamentally involves operations on data, abstract algebra, and specifically group theory, will continue to be relevant. We hope this blog has helped shed some light on the importance and elegance of group theory.

I would like to thank Intellegent for proof-reading and pointing out some mistakes that may otherwise have gone unnoticed. $$$\newline$$$

Meme :)