Skip to content

Basic Concepts

This chapter briefly introduces the basics of abstract algebra. Currently, the main content of competitive programming does not directly examine abstract algebra knowledge. However, the description of algorithms or problem solutions often involves some fundamental concepts of abstract functions, making it easier for readers with a grasp of basic abstract algebra concepts to understand certain algorithms more quickly. Therefore, this content is not mandatory for any contestant but is provided for reference to those who are interested or may benefit from it. At the same time, this chapter will avoid overly comprehensive or deep introductions to abstract algebra1, focusing instead on foundational concepts and the parts most closely related to other areas of OI. Readers wishing to systematically learn abstract algebra should refer to specialized abstract algebra textbooks.

To better help readers understand the potential gains from reading this section, here are some examples from algorithm competitions that may involve abstract algebra knowledge:

  • Many theorems in number theory and polynomials are special cases of conclusions in abstract algebra;
  • In data structures, structures like Segment Tree can maintain information of monoids, and the recurrence relations of many DP problems can be abstracted into such monoid structures;
  • In combinatorics, the rigorous statement and proof of Pólya's Enumeration Theorem require concepts from group theory.

Based on this, this chapter will focus on essential foundational knowledge and parts directly related to these applications. To begin, this article introduces the basic concepts of groups, rings, and fields.

Groups

A group is defined as follows.

Group

Let \(G\) be a non-empty set with a binary operation \(\cdot:G\times G\rightarrow G\). If they satisfy the following properties, then \((G,\cdot)\) is called a group:

  1. Associative property: For all \(a,b,c\in G\), \(a\cdot(b\cdot c)=(a\cdot b)\cdot c\) holds.
  2. Identity element: There exists \(e\in G\) such that for any \(a\in G\), \(a\cdot e = e\cdot a = a\) holds. Here, \(e\) is called the identity element of \(G\).
  3. Inverse element: For all \(a\in G\), there exists a corresponding \(b\in G\) such that \(a\cdot b=b\cdot a=e\). Here, \(b\) is called the inverse element of \(a\).
On the closure condition in the definition

The binary operation here implicitly includes the so-called closure condition, i.e., for any \(a,b\in G\), \(a\cdot b\in G\). Some articles list this separately.

Basic properties of groups

For a group \((G,\cdot)\), the following properties always hold:

  1. For any finite sequence \(\{g_i\}_{i=1}^k\subseteq G\), the result of the product \(g_1\cdot g_2\cdot\cdots\cdot g_k\) is independent of the way parentheses are added.
  2. The identity element \(e\) is always unique.
  3. For any element \(a\in G\), its inverse \(a^{-1}\) is also unique.
  4. Cancellation law: For \(a,b,c\in G\), if \(a\cdot c=b\cdot c\) or \(c\cdot a=c\cdot b\), then \(a=b\).

Groups are quite common. Informally, all transformations that do not lose structure automatically form groups. Here are examples of several common types of groups.

Examples of groups
  • Symmetric group: All permutations on a set \(M\), i.e., bijections from \(M\) to itself, form a group \(S_M\) under composition of mappings. The identity is the identity transformation, and the inverse is the inverse mapping (a bijection necessarily has an inverse mapping). If the set \(M\) is finite with size \(n\), it is often denoted as \(S_n\), called the symmetric group of degree \(n\).
  • Symmetry group of a geometric figure: For a geometric figure, the set of all transformations that map it onto itself also forms a group under composition of mappings. This describes the spatial symmetry of the figure. Specific examples can be found in Common spatial symmetry groups.
  • Additive group of integers: The set of integers \(\mathbf Z\) under addition \(+\) forms the group \((\mathbf Z,+)\). The identity is \(0\), and the inverse is the opposite number.
  • Multiplicative group of integers modulo \(n\): For a modulus \(n\), all integers coprime to \(n\) form congruence classes that constitute the group \(((\mathbf Z/n\mathbf Z)^\times,\times)\) under multiplication. The identity is \(\bar 1\), and the inverse is the multiplicative inverse modulo \(n\) (the corresponding congruence class), whose existence is guaranteed by Bézout's theorem. For structural analysis, refer to Multiplicative group of integers modulo \(n\).
  • General linear group: The set of all \(n\)-dimensional invertible square matrices over a number field \(F\) forms the group \(GL_n(F)\) under matrix multiplication. The identity is the identity matrix, and the inverse is the inverse matrix.

To better understand the definition of a group, it is helpful to look at a few examples that are not groups.

Examples that are not groups
  • All mappings from \(M\) to itself (not necessarily bijections) do not form a group because those that are not bijections lack inverse elements.
  • Integers under multiplication do not form a group because \(2\) has no multiplicative inverse within the integers.
  • Positive integers under addition do not form a group because positive integers lack an additive identity.
  • The set of all nonzero congruence classes modulo \(n\) under multiplication often does not form a group. For example, in \((\mathbf Z/6\mathbf Z)\setminus\{\overline 0\}\), \(\overline 2\times\overline 3=\overline 0\) does not belong to this set, meaning multiplication is not a well-defined binary operation on this set (or it does not satisfy closure).

Sometimes, it is necessary to discuss the properties of less complete structures. Therefore, the following concepts, which are broader than groups, can be defined.

Semigroup

For a non-empty set \(G\) and a binary operation \(\cdot\) on it, if the operation satisfies associativity, then \((G,\cdot)\) is called a semigroup.

Monoid

For a semigroup \((G,\cdot)\), if it also has an identity element, then \((G,\cdot)\) is called a monoid.

Examples of monoids and semigroups

Among the examples above, \((\mathbf N_+,+)\) is a semigroup, while \((\mathbf Z,\times)\) is a monoid.

Finally, many familiar group operations satisfy not only associativity but also commutativity. Such groups have relatively simple structures and are called Abelian groups, also known as commutative groups.

Abelian group

For a group \((G,\cdot)\), if the operation \(\cdot\) also satisfies the commutative property, i.e., for all \(a,b\in G\), \(a\cdot b=b\cdot a\) holds, then \((G,\cdot)\) is called an Abelian group or commutative group.

Examples of Abelian and non-Abelian groups
  • The additive group of integers \((\mathbf Z,+)\) is an Abelian group.
  • For \(n\ge3\), the symmetric group \(S_n\) is not an Abelian group.

These are the basic definitions related to group theory. For more content on group theory, refer to Group Theory or relevant books.

Rings

A ring is defined as follows.

Ring

For a non-empty set \(R\) and two binary operations \(+:R\times R\rightarrow R\) and \(\cdot:R\times R\rightarrow R\) on it, if they satisfy the following properties, then \((R,+,\cdot)\) is called a ring:

  1. \((R,+)\) forms an Abelian group, whose identity is denoted as \(0\), and the inverse of an element \(a\in R\) under \(+\) is denoted as \(-a\).
  2. \((R,\cdot)\) forms a semigroup, i.e., \(\cdot\) satisfies associativity.
  3. Distributive property: For all \(a,b,c\in R\), \(a\cdot(b+c)=a\cdot b+a\cdot c\) and \((a+b)\cdot c=a\cdot c+b\cdot c\) hold.

For convenience, these two binary operations \(+\) and \(\cdot\) are often called the addition and multiplication of the ring, respectively. Correspondingly, the additive identity is called the zero element, and the multiplicative identity (if it exists) is called the identity element. Care should be taken to avoid confusion with the specific addition and multiplication in number sets, as well as the natural numbers zero and one.

On whether the multiplicative identity is required in the definition

In some definitions, a ring must have a multiplicative identity; relatively, those without a multiplicative identity are called pseudo-rings (rng). The context should be used to determine which definition is being used. Wikipedia adopts this definition3.

The additive structure of a ring is quite simple, but the multiplicative structure is primitive. Thus, by analogy with groups, imposing more requirements on multiplication leads to the following related definitions.

Ring with identity

For a ring \((R,+,\cdot)\), if it has an identity, i.e., there exists a multiplicative identity denoted as \(1\), then \((R,+,\cdot)\) is called a ring with identity.

Division ring

For a nonzero ring with identity \((R,+,\cdot)\), if for every nonzero element \(a\in R\), there exists a multiplicative inverse (denoted as \(a^{-1}\)), then \((R,+,\cdot)\) is called a division ring.

Commutative ring

For a ring \((R,+,\cdot)\), if its multiplication satisfies commutativity, then \((R,+,\cdot)\) is called a commutative ring.

An interesting point in the definition of a division ring is that it treats \(0\) as a special element in the multiplicative structure. This is because \(0 = 0\cdot a = a\cdot 0\)2. That is, the additive identity multiplied by any element yields itself. Thus, it naturally cannot have a multiplicative inverse unless it is itself the multiplicative identity. Such a ring is only the zero ring (see the example below).

The insight here is that when understanding the multiplicative structure of a general ring, one should remove the influence of the additive identity and examine \(R\setminus\{0\}\). Based on this idea, the following definitions are given.

Zero divisor

For a ring \((R,+,\cdot)\), if there exists \(b\in R\) with \(b\ne 0\) such that \(a\cdot b=0\) or \(b\cdot a=0\), then the nonzero element \(a\) is called a zero divisor.

Invertible element (unit)

For a ring \((R,+,\cdot)\), if an element \(a\) has a multiplicative inverse, i.e., there exists \(b\in R\) such that \(a\cdot b=b\cdot a=1\), then the element \(a\in R\) is called an invertible element or a unit.

「Unit」 vs. 「Identity element」

Please do not confuse these two concepts. To avoid confusion, the term "invertible element" will be used instead of "unit" in the abstract algebra section.

A zero divisor cannot be an invertible element, and an invertible element cannot be a zero divisor. However, a nonzero element can be neither a zero divisor nor an invertible element.

If a ring has no zero divisors, it means the set of all nonzero elements is closed under multiplication, i.e., \((R\setminus\{0\},\cdot)\) forms a semigroup. Further, if it is required to be a commutative monoid, the definition of an integral domain is obtained.

Integral domain

For a nonzero ring \((R,+,\cdot)\), if it is a commutative ring, has a multiplicative identity, and has no zero divisors, then it is called an integral domain.

Although elements in an integral domain may not necessarily have inverses, the property of having no zero divisors is sufficient to establish the cancellation law in an integral domain.

Cancellation law in integral domains

Let \(R\) be an integral domain with elements \(a,b,c\in R\) and \(a\neq 0\). If \(ab=ac\), then necessarily \(b=c\).

For a general ring with identity, if only its set of all invertible elements is considered, a group structure can also be obtained. This is called the multiplicative group or unit group of the ring.

Multiplicative group (unit group)

For a ring with identity \((R,+,\cdot)\), let \(R^\times\) be the set of all invertible elements in \(R\). Then \((R^\times,\cdot)\) forms a group, called the multiplicative group or unit group of the ring \(R\).

The simplest examples of rings are as follows.

Examples of rings
  • Zero ring: The set \(\{0\}\) under the usual addition \(+\) and multiplication \(\times\) forms a ring, called the zero ring. It is the only ring with a single element and the only ring where the additive identity equals the multiplicative identity.
  • Ring of integers: The set of integers \(\mathbf Z\) with the usual addition \(+\) and multiplication \(\times\) forms the ring \((\mathbf Z,+,\times)\). In fact, this is an integral domain, but it is not a division ring.
  • Polynomial ring: For a ring \(R\), the polynomial ring \(R[x]\) can be defined over it. If \(R\) is an integral domain, then this polynomial ring is necessarily an integral domain.

  • Quaternions: Analogous to complex numbers, consider the set \(\mathbf H=\{a+b\mathrm{i}+c\mathrm{j}+d\mathrm{k}:a,b,c,d\in\mathbf R\}\) and define addition and multiplication on it, where the multiplication of \(\mathrm{i},\mathrm{j},\mathrm{k}\) satisfies

    \[ \mathrm{i}^2=\mathrm{j}^2=\mathrm{k}^2=-1,\ \mathrm{i}\mathrm{j}=-\mathrm{j}\mathrm{i}=\mathrm{k},\ \mathrm{j}\mathrm{k}=-\mathrm{k}\mathrm{j}=\mathrm{i},\ \mathrm{k}\mathrm{i}=-\mathrm{i}\mathrm{k}=\mathrm{j}. \]

    Then it can be verified that \(\mathbf H\) forms a ring, and it is a non-commutative division ring.

  • The subset \(2\mathbf Z\) of integers, under the usual addition and multiplication, forms a ring. It is a commutative ring, has no zero divisors, but does not have an identity.

  • The set of congruence classes modulo \(n\), \(\mathbf Z/n\mathbf Z\), under addition and multiplication of congruence classes, forms a ring. It is a commutative ring with identity (namely \(\bar 1\)). Such a ring contains zero divisors if and only if \(n\) is composite. Therefore, when \(n\) is prime, the ring \((\mathbf Z/n\mathbf Z, +,\times)\) is an integral domain; moreover, it is also a division ring, so it actually forms a field. Its multiplicative group \(((\mathbf Z/n\mathbf Z)^\times,\times)\) is the multiplicative group of integers modulo \(n\).
  • Matrix ring: The set of all \(n\)-dimensional square matrices over a ring \(R\) forms a ring \(M_n(R)\) under matrix addition and multiplication. Generally, this ring has zero divisors and is not commutative.
  • For the power set \(\mathcal P(A)\) of a set \(A\), if symmetric difference \(\triangle\) and intersection \(\cap\) are defined as addition and multiplication, respectively, then \((\mathcal P(A),\triangle,\cap)\) forms a ring. Generally, this ring has an identity, has zero divisors, and is commutative.

Of course, the discussion of ring structure goes far beyond this. To learn more, refer to Ring Theory or relevant books.

Fields

A field is an algebraic structure with stronger properties than a ring. Specifically, a field is a commutative division ring. Its complete definition can also be written.

Field

For a non-empty set \(F\) and two binary operations \(+:F\times F\rightarrow F\) and \(\cdot:F\times F\rightarrow F\) on it, if they satisfy the following properties, then \((F,+,\cdot)\) is called a field:

  1. \((F,+)\) forms an Abelian group, whose identity is denoted as \(0\), and the inverse of an element \(a\in F\) under \(+\) is denoted as \(-a\).
  2. \((F\setminus\{0\},\cdot)\) forms an Abelian group, whose identity is denoted as \(1\), and the inverse of an element \(a\in F\setminus\{0\}\) under \(\cdot\) is denoted as \(a^{-1}\).

In other words, a field is an algebraic structure closed under the four arithmetic operations: addition, subtraction, multiplication, and division.

Common examples of fields are as follows.

Examples of fields
  • Number fields: The set of rational numbers \(\mathbf Q\), the set of real numbers \(\mathbf R\), and the set of complex numbers \(\mathbf C\) all form fields under the usual addition and multiplication.
  • Finite field: The set of integer congruence classes modulo a prime \(p\), \(\mathbf Z/p\mathbf Z\), forms a field under addition and multiplication of congruence classes. Of course, there are other finite fields; their structure is uniquely determined by their size, which must be a prime power.

  • Field of fractions: Let \((R,+,\cdot)\) be an integral domain. Consider the set \(Q\) of elements of the form \(ab^{-1}\). Strictly speaking, define an equivalence relation on the set \(R\times(R\setminus\{0\})\): \((a_1,b_1)\sim(a_2,b_2)\) if and only if \(a_1b_2=a_2b_1\). Then the set \(Q\) is the set of equivalence classes under this relation, \(R\times(R\setminus\{0\})/\sim\), where the equivalence class of \((a,b)\) is denoted as \(ab^{-1}\). If the operations on it are defined as

    \[ \begin{aligned} a_1b_1^{-1}+a_2b_2^{-1} &= (a_1\cdot b_2+a_2\cdot b_1)(b_1\cdot b_2)^{-1},\\ (a_1b_1^{-1})\cdot(a_2b_2^{-1}) &= (a_1\cdot a_2)(b_1\cdot b_2)^{-1} \end{aligned} \]

    then \((Q,+,\cdot)\) forms a field, called the field of fractions of \(R\). For example, the rational number field \((\mathbf Q,+,\times)\) is the field of fractions of the integer ring \((\mathbf Z,+,\times)\).

  • Quadratic field: It is an extension of the rational number field \(\mathbf Q\) by adding \(\sqrt d\), where \(d\neq 0,1\) and is square-free. Related content can be found in Quadratic fields.

Compared to rings, fields have very simple additive and multiplicative structures. Therefore, the structure of a field itself is often simple. This makes the study of fields quite different from that of rings, usually shifting to the study of field extensions and corresponding Galois theory. In algorithm competitions, computations sometimes need to be performed on extensions of the rational number field or finite fields. For content related to field theory, refer to Field Theory or relevant books.

Applications

Finally, the following problem is used as an example to illustrate how abstract algebraic objects assist in analyzing specific problems.

[Template] "Dynamic DP" & Dynamic Tree Divide and Conquer (Enhanced Version)"(https://www.luogu.com.cn/problem/P4751)

Given a tree of size \(n\) with vertex weights, perform \(m\) vertex weight modifications. After each modification, output the sum of weights of the maximum weighted independent set on the tree. The problem is forced online.

Idea Analysis

This problem is a template for dynamic DP. A correct complexity implementation requires the use of Global Balanced Binary Tree, with sample code on the corresponding page. Here, only the modeling process is analyzed in the context of this problem.

To focus on the key points, the handling of tree structure by the global balanced binary tree is temporarily ignored, and the DP problem of the maximum weighted independent set on a chain is considered. Consider each point on the chain \([1,n]\) in order. For point \(i\), it can be selected (\(1\)) or not selected (\(0\)). Let the optimal solutions for the subproblem on \([1,i]\) under these two scenarios be \(f_{i,1}\) and \(f_{i,0}\), respectively. Thus, the DP equations can be written as

\[ \begin{aligned} f_{i,1}&=w_{i}+f_{i-1,0},\\ f_{i,0}&=\max\{f_{i-1,1},f_{i-1,0}\}. \end{aligned} \]

The initial values are \((f_{0,1},f_{0,0})=(0,0)\), and the final answer is \(\max\{f_{n,1},f_{n,0}\}\). To represent the influence of point \(i\) on the final result, it suffices to note that this recurrence relation can be written as

\[ (f_{i,1},f_{i,0})=g(f_{i-1,1},f_{i-1,0};w_i). \]

This is a series of mappings from \(\mathbf R^2\) to \(\mathbf R^2\), mapping \((f_{i-1,1},f_{i-1,0})\) to \((f_{i,1},f_{i,0})\). In group language, these transformations form a monoid under composition. This is exactly what a segment tree can maintain.

However, if the parameterized transformation \(g(\cdot;w_i)\) does not have a special structure, general mappings from \(\mathbf R^2\) to \(\mathbf R^2\) cannot be described by finite-dimensional data. Another observation is needed here: if \(\max\) is defined as addition and \(+\) as multiplication on \(\mathbf R\cup\{-\infty\}\), then \(\mathbf R\cup\{-\infty\}\) forms a structure similar to a ring, where \(-\infty\) is the additive identity and \(0\) is the multiplicative identity. But it is not a ring because not all elements have additive inverses. Such a structure is called a semiring4, and the semiring \((\mathbf R\cup\{-\infty\},\max,+)\) formed here is called the tropical semiring.

Based on the tropical semiring \((R,\oplus,\otimes)\), matrix multiplication can be defined on it. That is, for an \(m\times n\) matrix \(A=(a_{ij})\) and an \(n\times p\) matrix \(B=(b_{jk})\), their product \(AB\) can be defined as \((c_{ik})\), where each element is

\[ c_{ik} = \bigoplus_{j=1}^n(b_{ij}\otimes c_{jk}) = \max_{1\le j\le n}\;(b_{ij}+c_{jk}). \]

With this notation, the above recurrence relation can be viewed as a linear transformation over the tropical semiring and written in matrix language as

\[ \left(\begin{matrix}f_{i,1}\\f_{i,0}\end{matrix}\right) =\left(\begin{matrix}-\infty&w_i\\0&0\end{matrix}\right)\left(\begin{matrix}f_{i-1,1}\\f_{i-1,0}\end{matrix}\right). \]

Thus, as long as a segment tree is used to maintain the product of matrices over this tropical semiring, the dynamic DP problem on a chain with multiple modifications can be answered.

Now return to the tree version of the problem. For a tree node \(i\), let its set of child nodes be \(S(i)\). Then the DP equation at this node is

\[ \begin{aligned} f_{i,1}&=w_i+\sum_{j\in S(i)}f_{j,0},\\ f_{i,0}&=\sum_{j\in S(i)}\max\{f_{j,1},f_{j,0}\}. \end{aligned} \]

First, transform the problem into a chain version via heavy-light decomposition. Let \(h\) be the heavy child of \(i\). Then the above recurrence can be written as

\[ \begin{aligned} f_{i,1}&=w_i+f_{h,0}+g_{i,1},\\ f_{i,0}&=\max\{f_{j,0},f_{j,1}\}+g_{i,0}, \end{aligned} \]

where

\[ \begin{aligned} g_{i,1}&=\sum_{j\in S(i),\ j\neq h}f_{j,0},\\ g_{i,0}&=\sum_{j\in S(i),\ j\neq h}\max\{f_{j,1},f_{j,0}\} \end{aligned} \]

summarize the contributions of light children. According to the above description, these transformations can all be written in matrix form over the tropical semiring, so the entire problem can also be maintained on a segment tree after heavy-light decomposition. However, directly using heavy-light decomposition plus segment tree results in \(O(\log^2n)\) per modification, so the aforementioned global balanced binary tree is needed to optimize to \(O(\log n)\). Of course, LCT can also be used for maintenance.

The tropical semiring and the matrix operations mentioned here are not uncommon. If \(\max\) is replaced by \(\min\) above, the corresponding tropical semiring is often used in shortest path problems. If an \(n\)-dimensional square matrix \(A\) gives the (shortest) edge weights between two points of a graph with \(n\) vertices, then the element at \((i,j)\) of \(A^k\) is the shortest distance from point \(i\) to point \(j\) using at most \(k\) edges; in particular, \(A^n\) is the distance matrix of the graph. Of course, in actual implementation, the power of this matrix is not computed by brute force; instead, the Floyd algorithm with complexity \(O(n^3)\) is used.

References and Notes

  1. Because OI Wiki is not an encyclopedia. ↩

  2. The derivation of this equation is \(0\cdot a+0 = 0\cdot a = (0+0)\cdot a = 0\cdot a + 0\cdot a\), where the first and second equalities are definitions of the additive identity, the third equality is the distributive property, and the final implication is the cancellation law of addition. Multiplication on the other side is similar. ↩

  3. Ring (mathematics) - Wikipedia ↩

  4. A semiring is an algebraic structure that relaxes the requirement that the addition operation must have inverses in the definition of a ring with identity, i.e., the additive structure is a commutative monoid and the multiplicative structure is a monoid. For more information, see Wikipedia. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用