How many groups have 2019 elements? What are these groups?
2019 is a semiprime, i.e. the product of two primes, 3 and 673. For every semiprime s, there are either one or two distinct groups of order s.
As explained here, if s = pq with p > q, all groups of order s are isomorphic if q is not a factor of p-1. If q does divide p-1 then there are exactly two non-isomorphic groups of order s, one abelian and one non-abelian. In our case, 3 does divide 672, so there are two groups of order 2019. The first is easy: the cyclic group of order 2019. The second is more complex.
You could take the direct product of the cyclic groups of order 3 and 673, but that turns out to be isomorphic to the cyclic group of order 2019. But if you take the semidirect product you get the other group of order 2019, the non-abelian one.
Semidirect products
Starting with two groups G and H, the direct product G × H is the Cartesian product of G and H with multiplication defined componentwise. The semidirect product of G and H, written [1]
also starts with the Cartesian product of G and H but defines multiplication differently.
In our application, G will be the integers mod 673 with addition and H will be a three-element subgroup of the integers mod 673 with multiplication [2]. Let H be the set {1, 255, 417} with respect to multiplication [3]. Note that 1 is its own inverse and 255 and 417 are inverses of each other.
Product
Now the group product of (g1, h1) and (g2, h2) is defined to be
(g1 + h1-1g2, h1 h2)
So, for example, the product of (5, 255) and (334, 417) is (5 + 417*334, 255*417) which reduces to (645, 1) working mod 673.
(We haven’t defined the semidirect product in general, but the procedure above suffices to define the semidirect product for any two groups of prime order, and so it is sufficient to find all groups of semiprime order.)
Note that our group is non-abelian. For example, if we reverse the order of multiplication above we get (263, 1).
Identity
The identity element is just the pair consisting of the identity elements from G and H. In our case, this is (0, 1) because 0 is the additive identity and 1 is the multiplicative identity.
Inverse
The inverse of an element (g, h) is given by
(-gh, h-1).
So, for example, the inverse of (600, 255) is (444, 417).
Python code
The goal of this post is to be concrete rather than general.
So to make everything perfectly explicit, we’ll write a little Python code implementing the product and inverse.
def hinv(h):
if h == 255:
return 417
if h == 417:
return 255
if h == 1:
return 1
def prod(x, y):
g1, h1 = x
g2, h2 = y
g3 = (g1 + hinv(h1)*g2) % 673
h3 = (h1*h2) % 673
return (g3, h3)
def group_inv(x):
g, h = x
return ((-g*h)%673, hinv(h))
x = (5, 255)
y = (334, 417)
print(prod(x, y))
print(prod(y, x))
print(group_inv((600, 255)))
The following code verifies that our group satisfies the axioms of a group.
from itertools import product
identity = (0, 1)
h_list = [1, 255, 417]
def elem(x):
g, h = x
g_ok = (0 <= g <= 672)
h_ok = (h in h_list)
return (g_ok and h_ok)
group = product(range(673), h_list)
assert(len([g for g in group]) == 2019)
# closed under multiplicaton
for x in group:
for y in group:
assert( elem(prod(x, y)) )
# multiplication is associative
for x in group:
for y in group:
for z in group:
xy_z = prod(prod(x, y),z)
x_yz = prod(x, prod(y,z))
assert(xy_z == x_yz)
# identity acts like it's supposed to
for x in group:
assert( prod(x, identity) == x )
assert( prod(identity, x) == x )
# every element has an inverse
for x in group:
ginv = group_inv(x)
assert( elem(ginv) )
assert( prod(x, ginv) == identity )
assert( prod(ginv, x) == identity )
Related posts
[1] The symbol for semidirect product is ⋊. It’s U+22CA in Unicode and \rtimes in LaTeX.
[2] In general, the semidirect product depends on a choice of an action of the group H on the group G. Here the action is multiplication by an element of H. Different actions can result in different groups. Sometimes the particular choice of action is made explicit as a subscript on the ⋊ symbol.
[3] How did I find these numbers? There are 672 non-zero numbers mod 673, so I picked a number, it happened to be 5, and raised it to the powers 672/3 and 2*672/3.
