What is a “Group”? | Part 2 | Understanding Cryptography Through Mathematical Primitives

Paul Vienhage - Smart Contract Auditor and Engineer
November 2nd, 2018
Proof and Set Theory Understanding Crpytog Image

People like to give poetic visions of what a group is, calling it the study of symmetry or an abstraction of the arithmetic we are familiar with. The truth is that groups are straightforward mathematical objects that have very high levels of complexity when you study them in depth. Many things are modeled by finite or infinite groups, and often it is the symmetry of these objects which allows them to be modeled by groups. This article won’t cover complex group theory, but it should let you understand what people mean when they use group theoretic terms.

Group Axioms

To build a group we take a set G and a function (called a binary operator) * : G × G → B [it takes two elements of G to a single element of B], which is a function that takes two elements of the set and gives you back another element of the set B. If the following statements hold we call the pair (G, *) a group:

1. If a, b ∈ G then a * b ∈ G

2. If a, b, c ∈ G then a * ( b * c) = (a *b) * c

3. There exists an element, called the identity, e ∈ G such that if a ∈ G then a * e = a = e * a

4. If a ∈ G then there is an element b ∈ G such that a * b = e

For example if we consider the integers under addition these are a group because adding two integers gives an integer [ie: a, b ∈ ℤ then a + b ∈ ℤ], addition is associative [ie: a+(b+c) = (a+b)+c], zero is the identity [ie: 0 ∈ ℤ and a+0 = 0+a=a], and to get the inverse of a number we multiply it by negative one [ie: for all a ∈ ℤ then -a ∈ ℤ and a+ -a =0].

A close counterexample is the rationals under multiplication; this has closure, associativity, an identity (1), and almost every element has an inverse. However, there is no rational which when multiplied by 0 gives one, i.e., zero has no inverse. To fix this we just have to take out zero, (ℚ — 0, *) is a group.

Relationships Between Groups

How can we tell if two groups are the same? For example from the article on sets, we know that there is the same number of numbers in the even integers as the integers. Is the group (2ℤ, +) the same group as (ℤ, +)? Obviously, they are not made of the same elements, but they are in essence the same. How do we make this “sameness” precise? Let’s use the strategy we used to check that objects are the same size, define a mapping with precise properties. Consider a mapping from the groups (G, ⋅) and (H, *), f : G → H. If f has that for all g₁ , g₂ ∈ G, f(g₁ ⋅ g₂) = f(g₁) * f(g₂), then f is called a group homomorphism.

However this relationship is fairly weak as the groups in question don’t have to be the same size, in fact, there is a homomorphism between any two groups if you map all elements of G to the identity of H. We can make a much stronger statement if the groups are the same size. We call groups which have a bijective homomorphism, isomorphic groups and as far as groups are concerned, if two groups are isomorphic, they are the same.

Now that we can describe groups which are the same, we should think about groups that are smaller than each other. A subgroup is a group inside a group. Consider a group (G, ⋅) and a subset of the set G, H. H is called a subgroup of G if it is also a group under the same binary operation. This means that it is isomorphic to some other group on fewer elements than G and is a way to symbolize that G contains the information of the group.

Some types of Groups

The order of a group is the number of elements in the set. Finite groups are those with finite order, and infinite groups are those with an infinite order. Given an element of our group we can actually make a subgroup with it by repeating the group operation on it, this is a cyclic subgroup denoted ⟨ g ⟩ = { g, g² , g³ , …}. Sometimes a group is generated by a single element in this way if so it is called a cyclic group. In epileptic curve cryptography, we use cyclic groups. Cyclic groups are very friendly, for example in a cyclic group C if a number divides the group order there is a subgroup of C of that size.

Proof: Let C be a cyclic group of order n generated by g, and let d divide n. Then ⟨g^(n/d)⟩ is a subgroup of C with order d. We can prove this by noting that (g^(n/d))ᵈ = gⁿ = e so the size of ⟨g^(n/d)⟩ is less than or equal to d. But also if the order of ⟨g^(n/d)⟩ is less than d that implies that the order of g is less than n which would imply that g could not generate C a contradiction. Thus ⟨g^(n/d)⟩ is a subgroup of order d.

Another important type of group is a symmetric group. Consider a list of objects [a , b, c, d, e, f] a permutation is a changing of the ordering of these elements for example to [b, a, c, d, f, e]. The symmetric group on n elements is the group of all possible permutations of n elements. Its group operation is the composition of permutations, for example, if we have a permutation switching a and b and one switching b and c then their composed permutation takes [a, b, c] to [c, a, b].

Symmetric groups are complicated to work with but contain all finite groups.

Theorem: Every finite group is isomorphic to a subgroup of some symmetric group Sₙ . This theorem is why group theory is called the study of symmetry, in some ways each finite group can be viewed as a group describing a type of symmetry.

To visualize the structure of groups, we can use a diagram called a Cayley graph. A Cayley graph is a directed colored graph which is built in the following way:

  • First we take a set of elements of G which generate G called S.
  • Then for each element of our group we create a vertex and label the vertex by the element.
  • For each element of S we assign a color cₛ.
  • Next for every pair (g,s) with g ∈ G and s ∈ S we create an edge from g to s which is colored cₛ.

This process allows the creation of a diagram which encodes the group structure in a visual way. For example the Cayley graph of a cyclic group of order n is a single direction loop of n vertices and a single color. However the Cayley graph of S₄ is much more complex and encodes some of its structure.

Complex Results in Group Theory

The previous sections have laid out the very general rules of group theory, but these rules don’t give a good idea of how complex and specific our conclusions in group theory can be. In this section, we will present some of the most important results in group so you can see how much structure mathematicians have found in the study of groups.

One of the major undertakings in the history of group theory was the classification of finite simple groups. This massive project took over 10,000 pages of proof and research mathematics to finish. The simple groups are those which are not “divisible” by groups other than themselves. In this way, the simple groups are analogous to prime numbers, and every group can be built out of simple groups. Theorem: Every finite simple group is isomorphic to one of the following:

  • A cyclic group of prime order.
  • An alternating group of degree at least 5 (the alternating group Aₙ is the largest subgroup of the symmetric group Sₙ).
  • A Lie type group (groups which are derived from the properties of infinite groups)
  • One of 26 groups known as the sporadic groups.
  • The Tits Group

This is amazing because despite how general the group axioms are, if a group is finite it can be built from the groups in that list. For an example of how intricate it was to prove that lets take a look at some of the properties of the Monster Group.

The Monster is the largest sporadic group, which makes it the largest group which cannot be classified into an infinite family. The monster group has 808017424794512875886459904961710757005754368000000000= 2⁴⁶ ⋅ 3²⁰ ⋅ 5⁹ ⋅ 7⁶ ⋅ 11² ⋅ 13³ ⋅ 17 ⋅ 19 ⋅ 23 ⋅ 29 ⋅ 31 ⋅ 41 ⋅ 47 ⋅ 59 ⋅ 71 elements. That is about five times the number of atoms in our solar system. This group is so large that mathematicians haven’t even found a good way to write every element of it down. You might be thinking “How is this useful” and to be honest it's not That useful. However, if you ever wanted to model the string theory and interactions of particles called bosons on a space shaped like a donut this group is actually the symmetries of that system. The fact that the largest simple group appears in many surprising places is exactly why group theory is so powerful.

For a simpler example of what groups can do, we can study the result of the “Bad Boy” of mathematics, Évariste Galois. While he was provoking a political revolution, getting arrested for threatening the life of King Louis Philippe and romancing a woman whom he would die fighting in a dual for, he was also revolutionizing mathematics. Before he died at 20, he published a proof to a theorem that mathematics had been trying to solve for 350 years.

To understand the problem he solved we have to take a trip back to high school algebra. The solutions to the equation ax² + bx +c =0 are [-b ± √(b² — 4ac)]/2a. What I didn’t learn in high school is that there are much more complicated formulas to solve ax³ + bx² + cx + d =0 and ax⁴ +bx³ +c x² + dx + e = 0 using no roots higher than ∛ or ∜ respectively. After mathematicians found these formulas they spent 350 years trying to find a way to solve ax⁵ + bx⁴ +cx³ +d x² + ex + f = 0 using roots that are at most fifth roots. Galois proved that there is no way to solve a fifth-degree polynomial with roots of a lesser degree than five. In doing so, he established a field of algebra called Galois Theory. In the next post, we will cover the basic objects in this field and Galois’s revolutionary proof.