Find the number of subgroups of a finite group

Question

Definitions

You can skip this part if you already know the definitions of groups, finite groups, and subgroups.

Groups

In abstract algebra, a group is a tuple (G, ∗), where G is a set and ∗ is a function G × G → G such that the following holds:

• Closure: for all x, y in G, x ∗ y is also in G (implied by the fact that ∗ is a function G × G → G).

• Associativity: for all x, y, z in G, (x ∗ y) ∗ z = x ∗ (y ∗ z).

• Identity: there exists an element e in G such that for all x in G, x ∗ e = x = e ∗ x.

• Inverse: for each x in G, there exists an element y in G such that x ∗ y = e = y ∗ x, where e is the identity element mentioned in the previous bullet point.

Finite groups

A finite group is a group (G, ∗) where G is finite, i.e. has finitely many elements.

Subgroups

A subgroup (H, ∗) of a group (G, ∗) is such that H is a subset of G (not necessarily proper subset) and (H, ∗) is also a group (i.e. satisfies the 4 criteria above).

Examples

Consider the dihedral group D₃ (G, ∗) where G = {1, A, B, C, D, E} and ∗ is defined below (a table like this is called a Cayley table):

∗ | 1   A   B   C   D   E
--+----------------------
1 | 1   A   B   C   D   E
A | A   B   1   D   E   C
B | B   1   A   E   C   D
C | C   E   D   1   B   A
D | D   C   E   A   1   B
E | E   D   C   B   A   1

In this group, the identity is 1. Also, A and B are inverses of each other, while 1, C, D, and E are the inverses of themselves respectively (the inverse of 1 is 1, the inverse of C is C, the inverse of D is D, and the inverse of E is E).

Now, we can verify that (H, ∗) where H = {1, A, B} is a subgroup of (G, ∗). For the closure, refer to the table below:

∗ | 1   A   B
--+----------
1 | 1   A   B
A | A   B   1
B | B   1   A

where all possible pairs of elements in H under ∗ give a member in H.

The associativity does not require checking, since elements of H are elements of G.

The identity is 1. This must be the same with the group identity. Also, the identity in a group must be unique. (Can you prove this?)

For the inverse, check that the inverse of A is B, which is a member of H. The inverse of B is A, which is also a member of H. The inverse of 1 is still itself, which does not require checking.

---

Task

Description

Given a finite group (G, ∗), find the number of its subgroups.

Input

For a group (G, ∗), you will receive a 2D array of size n × n, where n is the number of elements in G. Assume that index 0 is the identity element. The 2D array will represent the multiplication table. For example, for the group above, you will receive the following 2D array:

[[0, 1, 2, 3, 4, 5],
[1, 2, 0, 4, 5, 3],
[2, 0, 1, 5, 3, 4],
[3, 5, 4, 0, 2, 1],
[4, 3, 5, 1, 0, 2],
[5, 4, 3, 2, 1, 0]]

For example, you can see that 3 ∗ 1 = 5 because a[3][1] = 5, where a is the 2D array above.

Notes:

• You can used 1-indexed 2D array.
• The row and the column for the identity can be omitted.
• You may use other formats as you see fit, but it must be consistent. (i.e. you may want the last index to be identity instead, etc.)

Output

A positive number representing the number of subgroups in the group.

For example, for the group above, (H, ∗) is a subgroup of (G, ∗) whenever H =

• {1}
• {1, A, B}
• {1, C}
• {1, D}
• {1, E}
• {1, A, B, C, D, E}

Therefore, there are 6 subgroups, and your output for this example should be 6.

---

Hints

You can read the articles that I linked to. Those articles contain theorems about groups and subgroups that might be useful to you.

---

Scoring

This is code-golf. Answer with lowest byte-count wins.

Answer 1

Mathematica, 62 48 bytes

Count[Subsets@First@#,x_/;Union@@#[[x,x]]==x]-1&

Pure function expecting a 1-indexed 2D array. Counts the number of Subsets of the First row of the input array that are closed under the group operation. Since this will include the empty set, we subtract 1. Note that a nonempty subset of a finite group that is closed under the group operation is in fact a subgroup, (and vice versa, by definition).

Strictly speaking I don't check that the subset x is closed under the group operation, I restrict the multiplication table to the subset x and check that it contains precisely the elements of x. Clearly this implies that x is closed with respect to the group operation. Conversely, any subgroup x will contain 1 and thus x will be a subset of the elements appearing in the restricted multiplication table, and since x is closed under the group operation, it must equal x.

Answer 2

Haskell, 79 bytes

Basically a port of ngenisis's Mathematica method. (Except I'm using 0-indexed arrays.)

c takes a list of lists of Ints and returns an integer.

c g=sum[1|l<-foldr(\r->([id,(r!!0:)]<*>))[[]]g,and[g!!x!!y`elem`l|x<-l,y<-l]]-1

Try it online!

It is assumed that the Ints are numbered the same as the rows (outer lists) and columns showing their multiplication. Thus, since 0 is the identity, the first column is the same as the indices of the rows. This allows using the entries of the first column to construct the subsets.

How it works

• c is the main function.
• g is the group array as a list of lists.
• l is a subset of the elements. The list of subsets is constructed as follows:
  • foldr(\r->([id,(r!!0:)]<*>))[[]]g folds a function over the rows of g.
  • r is a row of g, whose first (0th) element is extracted as an element that may be included ((r!!0:)) or not (id).
  • <*> combines the choices for this row with the following ones.
• and[g!!x!!y`elem`l|x<-l,y<-l] tests for each pair of elements in l whether their multiple is in l.
• sum[1|...]-1 counts the subsets that pass the test, except for one, the empty subset.

Answer 3

Jelly, 17 16 bytes

1 byte thanks to ETHproductions (LR → J)

ị³Z⁸ịFḟ
JŒPÇÐḟL’

JŒPÇÐḟL’  main link. one argument (2D array)
J         [1,2,3,...,length of argument]
 ŒP       power set of ^
    Ðḟ    throw away elements that pass the test...
   Ç      in the helper link
      L   length (number of elements that do not pass)
       ’  decrement (the empty set is still closed under
          multiplication, but it is not a subgroup, as
          the identity element does not exist.)

ị³Z⁸ịFḟ   helper link. one argument (1D indexing array)
ị³        elements at required indices of program input (2D array)
  Z       transpose
   ⁸ị     elements at required indices of ^
     F    flatten
      ḟ   remove elements of ^ that are in the argument given
          if the set is closed under multiplication, this will
          result in an empty set, which is considered falsey.

Try it online! (1-indexed)

Answer 4

Python 2, 297 215 bytes

from itertools import*
T=input()
G=T[0]
print sum(all(T[y][x]in g for x,y in product(g,g))*all(any(T[y][x]==G[0]==T[x][y]for y in g)for x in g)*(G[0]in g)for g in chain(*[combinations(G,n)for n in range(len(G)+1)]))

Try it online

This program works for the example group without ==T[x][y], but I'm still pretty sure it's necessary.

Edit: Now assumes that the identity element of G is always the first.

---

Ungolfed:

from itertools import*
T=input()
G=T[0]
def f(x,y):return T[y][x]                                           # function
def C(g):return all(f(x,y)in g for x,y in product(g,g))             # closure
def E(g):return[all(f(x,y)==y for y in g)for x in g]                # identity

a=E(G)
e=any(a)
e=G[a.index(1)]if e else-1                                          # e in G

def I(G):return all(any(f(x,y)==e==f(y,x)for y in G)for x in G)     # inverse

#print e
#print C(G),any(E(G)),I(G)

#for g in chain(*[combinations(G,n)for n in range(len(G)+1)]):      # print all subgroups
#   if C(g)and I(g)and e in g:print g

print sum(C(g)*I(g)*(e in g)for g in chain(*[combinations(G,n)for n in range(len(G)+1)]))

Ungolfed TIO

Negative group elements can be supported at no cost by changing -1 to ''.