Elementary Group Theory for Programmers
In our previous tutorial, we introduced set theory and made the journey from sets to defining a group in set-theoretic terms.
Now it’s time to discuss groups as a mathematical structure.
By way of reminder, a group is a set with
an associative and closed binary operator
an identity element
every element having an inverse
We also discussed abelian groups. An abelian group has the additional requirement that
the binary operator is commutative
If these definitions are not immediately 100% clear, please revisit the previous article on set theory and abstract algebra for coders.
One confusing aspect about using integers under addition as an example of a group is students commonly respond with “but can’t you also multiply integers?”
Admittedly, this is confusing. We’ll get to algebraic structures later that expect two binary operators (rings and fields), but for now think of a group under one fixed and unchanging binary operator and from the group’s perspective, any other possible binary operator does not exist or isn’t a concern.
Here’s where it gets even more confusing. Sometimes binary operators are other binary operators in disguise.
For example, when dealing with groups that only have addition, sometimes writers casually refer to multiplication even though the group does not have that binary operator. What multiplication is in this context is really shorthand for repeating an addition operation a certain number of times.
Examples of groups
The best way to get a feel for a group is to see a lot of them. Let’s do that.
1. The trivial group
Let our group be a set consisting of the number 0 with the binary operator of addition. It is clear that the binary operator is closed and associative
(0 + 0) + 0 = (0 + 0) + 0
and each element has an identity and inverse.
This is not an interesting group, but it is the smallest valid you can create.
Note that a group cannot be empty because by definition it must contain an identity element.
2. Integers and real numbers are not a group under multiplication
Although integers and reals under multiplication has an identity (the number 1) and is closed and associative, they do not all have an inverse.
Integers do not have an inverse, because the “inverse” of 3 is in 1/3, but 1/3 is not an integer. Therefore, integers under multiplication are a monoid.
Real numbers are invertible by taking the inverse, but zero is a real number and it cannot be inverted because you cannot do 1/0. In general, you cannot multiply zero by something and get the identity element of 1.
Positive real numbers excluding zero are a group under multiplication however. Every element has an inverse (it’s fraction), and the identity element is 1.
Because we have an identity element (1) but no inverse, this set and binary operator is a monoid.
3. N × M matrices of real numbers are a group under addition
Let’s work it out:
matrix addition is closed and associative. If you add an N × M matrix of real numbers with another N × M matrix of real numbers, you get an N × M matrix of real numbers.
the identity matrix is an N × M matrix of all zeros
the inverse is a matrix multiplied by -1.
Hey wait, we aren’t allowed to multiply by -1 right?
A group doesn’t require the inverse to be “computable by group laws” only to exist. The group of N × M matrices of real numbers contains inverses for every element, and that’s what matters.
If we define our operator to be the Hadamard product, that is, element-wise multiplication, this cannot be a group for the same reason discussed above.
If we define our operator to be traditional matrix multiplication over square matrices, this may or may not be a group depending on the set definition, as we will see in section example 5.
4. The set of 2D points on an euclidean plane under addition is a group
This is actually a special case of the above example, but let’s look at it through a different angle.
Consider our set to be the set of all real-valued (x, y) points on a typical plot.
Our binary operator is adding points together, for example (1,1) + (2,2) = (3,3).
Our identity element is the origin, because adding with that will result in the same location of the other point.
The inverse is simply the “mirror image” over the origin (the x and y flipped) because when you add them together, they result in the origin.
5. N x N matrices of non-zero determinant under multiplication are a group
Lest you get the impression that it is impossible for a set to be a group when using the multiplication operator, let’s see an example of a multiplicative group.
By way of review, if a matrix has a non-zero determinant, then it is invertible. When a matrix of non-zero determinant is multiplied by another matrix of non-zero determinant, then the product also has a non-zero determinant. Actually, we can be more specific, if A, B, and C are square matrices, and AB = C, then det(a) x det(b) = det(c).
Let’s work through the definitions
multiplication of non-zero determinant matrices is closed because you cannot “leave the group” as the product will always have non-zero determinant. Matrix multiplication is associative.
The identity element is the identity matrix (all zeros, except the main diagonal is one).
The inverse is simply the matrix inverse, and non-zero matrices are invertible.
6. N x N matrices of zero determinant under multiplication are a not group
Remember, a matrix with zero determinant cannot be inverted, so this set cannot have an inverse. In this case, we do not have an identity element because the identity matrix has determinant one. Since we have no identity element, this set and binary operator isn’t even a monoid, it’s a semigroup.
7. The set of all polynomials of a fixed upper-bounded degree is a group under addition.
If we say “all polynomials of degree at most 7 under addition” this is a valid group.
Polynomial addition is closed and associative
The identity is the polynomial 0 (or 0x^0 to be precise)
The inverse is the coefficients multiplied by -1
We cannot say degree “exactly 7” because the identity element has degree 0, and wouldn’t be part of the group.
Polynomials of a fixed upper-bounded degree under multiplication are not a group, because generally the degree gets larger when you multiply polynomials, hence the operator would not be closed.
8. Addition modulo a prime number is a group
Let’s take a prime number 7.
Here, the identity is still 0, because you add by 0 and get the same number back.
In this situation, what would the inverse of 5 be?
It would just be 2, because 7 - 5 = 2, or 5 + 2 mod 7 is zero (the identity).
9. Multiplication modulo a prime number is not a group
The problem is we can’t define an identity and inverse that works for everything.
If we define our identity to be 1, then it isn’t possible to invert zero, because zero cannot be multiplied with anything to obtain 1. If we set our identity to be zero, then it won’t behave like an identity because any number multiplied by zero is not itself, but zero.
By the way, you’ve probably noticed a pattern by now that addition generally forms groups, but multiplication is sometimes problematic due to zero.
This pattern is quite frequent, and that is where algebraic rings enter the picture, but we’ll get to that later.
10. A fixed based raised to integer powers under multiplication is a group
But just because multiplication doesn’t work for some groups, doesn’t mean it never works. Let’s use the binary operator multiplication for this example.
Let’s pick our base to be 2 (arbitrarily). The set and binary operator we are dealing with is
Or the set
…, 1/4, 1/2, 1, 2, 4, 8,…
Why is raising a base to the integers a group under multiplication but integers under multiplication is not a group? That’s because you can’t raise an integer to an integer power and get zero, so we don’t have to worry about inverting zero.
Again, we have the group properties. If you multiply together any of the numbers in the set above, you get another number in the set.
Each element has an inverse, because 2^(-a) is the inverse of 2^a. The identity element is 2^0, because anything multiplied by 1 is itself.
Finite groups
As the name suggests, a finite group has a finite number of elements in it. The set of all integers under addition is not finite, but addition of integers modulo a prime number is a finite group.
Finite groups can be expressed with a Cayley table
A Cayley table is somewhat like a multiplication table except that “multiplication” is the binary operator of the group.
Consider addition on the group {0,1,2,4} modulo 5. The Cayley table would look like this
If this reminds you of the set relation we talked about in our set theory, good!
Here is something interesting about Cayley tables: each row contains no duplicates, and each column contains no duplicates. If it does contain a duplicate, it is not a group because it is either not associative or some of the elements don’t have inverses. We don’t have an immediate use for this fact, but if you are intersted, you can read more about cayley table uniqueness here.
Order of a group
The order of a group is the number of elements in it.
Cyclic groups
A cyclic group is a group that has an element such that every element in the group can be “generated” by applying the binary operator repeatedly to that element, or to it’s inverse.
The generator is usually denoted with g or G.
Going back to our example of groups 2ⁱ, this is a cyclic group because we can start with 1 and repeatedly multiply it by 2 to get all the members greater than 1.
On the flip side, we can start with (1/2) and keep multiplying that by (1/2) to get all the elements less than one.
For integers under multiplication modulo a prime, this group is not cyclic because you cannot generate 0.
However, integers under addition modulo n is a cyclic group because you can generate all the numbers by adding 1 repeatedly.
If a group is cyclic, then it is abelian
This one is a bit more subtle, but consider this:
every element in the group can be generated as (g + g + … + g). Let’s arbitrarily pick that to be R. Let’s partition this set of additions like so
Because of associativity, we can add parenthesis
Let g added to itself m times be P and g added to itself n times be Q. Therefore,
By associativity, we can repartition the original equation as follows (note that the m and n switched places!)
And we get back
Hence, if the group is cyclic, then the group is abelian.
Note that the converse of this statement isn’t true. Real numbers under addition are an abelian group, but they are not cyclic.
The identity element of a group is unique
A group cannot have two identity elements. Don’t overthink this one, it’s derived by simple contradiction. Let’s say ▢ is our binary operator and e is our identity element.
Let’s say we have an alternative identity element e'. This means the following:
If we say e≠e', then it must also be true that
But that is obviously a contradiction, hence we know identity elements are unique.
Going back to how we defined binary operators in set theoretic terms, we know the mapping from the sets (S × S) back to S cannot have the same ordered pair mapping to different elements, so by this definition we know inverses are unique.
Group Homomorphisms
Let A be a group with binary operator □ and B be a group with binary operator △.
Group A is homomorphic to group B if there exists a transformation φ where φ maps elements from A to B, and for all a, a’ in A, φ(a □ a’) = φ(a) △ φ(a’).
Let’s consider our groups all integers and the set 2ⁱ, i ∈ ℤ. The first set is integers under addition, and the second set is powers of 2 under multiplication.
The transformation φ(x) is 2ˣ. It is clear that for all integers
This relationship also happens to be an isomorphism because it works in both directions, but for the purpose of zero knowledge proofs, we are more interested in homomorphisms than isomorphisms.
Consider this map: the set of all integers under addition to the set {0,1,2,3,4} under addition modulo 5.
This is a homomorphism also because our transformation φ(x) is x mod 5 and
(a + b) % 5 == ((a % 5) + (b % 5)) % 5Clearly, this operation cannot be inverted because the target set is finite, but all integers are infinite. The function φ here is surjective; many integers map to a single element in our finite set.
We sometimes call φ a structure preserving transformation.
If our transformation φ is cryptographically hard to invert, then we have homomorphic encryption. That is, we can apply binary operators to encrypted data and “do valid math” but not know what the original values were.
Product of groups
Because groups are (special) sets, and you can take the cartesian product of two sets, you can also take the product of two groups. This is sometimes called the direct product. You might see this written as G × G.
Somewhat mindblowingly, the product of groups is also a group. We won't go into detail about that right now, but when you deal with bilinear parings, you are going to see notation like G × G → G, and now you can understand what that means.
Let's say we take the product of two non-equal groups G and G' and map a subset of it to G''. That would be G × G' → G''. This is just the same set-theoretic definition of a function we have been using all along.
Groups in Scala
The cats library in scala requires the group to implement the following
abstract def combine(x: A, y: A): A
abstract def empty: A
abstract def inverse(a: A): ASince groups are closed, all of the operators take elements of type A and return the same type A. The binary operator is “combine”, the identity element is “empty” and the “inverse” is as the name describes.
In programming contexts, inverses need to be computable, but keep in mind the mathematical definition doesn’t require it.
Why does group theory matter?
Okay cool, we understand groups, but how does this help us?
The reason I went through all the effort explaining this is because I want you to understand the statement below
“Elliptic curve points under addition modulo p are a cyclic finite group and integers under addition are homomorphic to this group.”
You probably don’t know what elliptic curve points are, or what adding them even means, but you do know:
the set of elliptic curve points under addition produce another elliptic curve point
the binary operator is associative
the set of elliptic curve points contain an identity element.
That identity element is unique
each elliptic curve point has an inverse such that combining the two points together produces the identity
because the group is cyclic, every elliptic curve point can be generated by repeatedly applying the binary operator to some generator element
because the group is cylic, it is also abelian
because it is a finite group, the order is finite
because of the homomorphism, we have a strong idea of how the binary operator for elliptic curve points behaves. We can use the elliptic curve point binary operator to “add integers” in a certain sense.
Even though you don’t know what elliptic curve points are, you already know nine things about them!
So whatever this bizarre object is, you know it behaves like, and has the same properties as the groups we discussed above.
Believe it or not, you are already 90% of the way there to comprehending elliptic curves. It’s far easier to make sense of elliptic curves by understanding their similarity to other familiar structures than to try to understand their funky math from the ground up.
This is akin to me telling you that Ethereum uses “patricia merkle trees” to store state. You may not know what a “patricia tree” or a “merkle tree” is, but you do know:
it has a root
you can probably access elements in logarithmic time, or at least that is the intent
something useful is stored in the leaves
there exists some algorithm to traverse the tree and access a leaf you care about
So when I tell you elliptic curve points under addition are a group, you should already know what to look out for when you learn about that subject.
Furthermore, we are also going to encounter rings and fields. Rings and fields are groups with even more restrictions, particularly they must support more than one binary operator. If you understand groups well, you are well on your way to understanding those structures also.
Again, groups don’t need to be mysterious moon math. You’ve worked with groups intuitively as a programmer. Now you have a concrete word to describe this recurring phenomena.
It’s far more efficient to say “group” than it is to say “this is a set with a way to combine elements associatively and the elements all have blah blah blah.”
I know this seems like a huge tangent, but trust me, this allows us to pack a lot of information as we go!
Imagine trying to discuss tree data structures without a word for that. That would be immensely annoying.
We’re getting that annoyance out of the way early.
Learn more with RareSkills
This material is part of our bootcamp to learn zero knowledge proofs.