Group theory

Twelve-tone composition

Posted on by John

Atonal music is difficult to compose because it defies human instincts. It takes discipline to write something so unpleasant to listen to.

One technique that composers use to keep their music from falling into tonal patterns is the twelve-tone row. The composer creates some permutation of the 12 notes in a chromatic scale and then uses these notes strictly in order. The durations of the notes may vary, and the notes may move up or down octaves, but the pitch classes are recycled over and over in order.

There are variations on this technique that allow a small amount of variety, such as allowing the the tone row to be reversed, inverted, or both. The retrograde version of the sequence is the original (prime) sequence of notes in the opposite order. The inverted form of the tone row inverts each of the intervals in the original sequence, going up by k half steps when the original when down by k half steps and vice versa. The retrograde inverted sequence is the inverted sequence in the opposite order.

Here is an example, taken from Arnold Schoenberg’s Suite for Piano, Op. 25.

Some math

Since a tone row is a permutation of 12 notes, there are 12! possible tone rows. However, since the notes of a tone row are played in a cycle, the same sequence of notes starting at a different point shouldn’t count as a distinct tone row. With that way of counting, there are 11! possible tone rows.

The operations of creating the retrograde and inverted forms of a tone row are the generators of an Abelian group. Let P (for prime) be the null operation, leaving a sequence alone. Then the elements of the group are P, R, I, and RI (= IR). The two generators have order 2, i.e. R² = I² = P. Therefore the group is isomorphic to ℤ2 × ℤ2.

Although I enjoy music and math, I do not enjoy most attempts to use math to compose music. I do not like atonal music, though I do like some “math rock.” It seems that math applied to rhythm results in more palatable music than math applied to melody.

Update: More math in the next post. Do the applications of R, I, and RI always produce different sequences of notes? What if you consider two rotations of a tone row to be equivalent?

A concert story

When I was in college I often walked from my dorm over the music building for concerts. I probably heard more concerts in college than I have heard ever since.

One night I went to an organ concert. At the end of the concert the organist took melodies on strips of paper that he had not seen before and improvised a fugue on each. After the concert I ran into a friend in the music building who had not been to the concert. I enthusiastically told him how impressed I was by the improvised fugues, especially the last one that sounded like Schoenberg tone row.

The organist overhead my conversation and walked up to me and said that he was impressed that I recognized the Schoenberg tone row. To be fair, I did not recognize the music per se. The music sounded random, and I came up with the only example of random music I could think of, and said it sounded like a Schoenberg tone row. I certainly did not say “Ah, yes. That was Schoenberg’s tone row from ….” It was a lucky guess.

Combining in-shuffles and out-shuffles

Posted on by John

A few days ago I wrote two posts about perfect shuffles. Once you’ve cut a deck of cards in half, an in-shuffle lets a card from the top half fall first, and an out-shuffle lets a card from the bottom half fall first.

Suppose we have a deck of 52 cards. We said in the earlier posts that the order of an in-shuffle I is 52. That is, after 52 in-shuffles, a deck returns to its initial order. And the order of an out-shuffle O is 8.

We can think of I and O as generators of subgroups of order 52 and 8 respectively in the group S of all permutations of 52 cards. I was curious when I wrote the earlier posts how large the group generated by I and O together would be. Is it possible to reach all 52! permutations of the deck by some combination of applying I and O? If not, how many permutations can be generated?

I’ve since found the answer in [1] in a theorem by Diaconis, Graham, and Kantor. I don’t know who Kantor is, but it’s no surprise that a theorem on card shuffles would come from Persi Diaconis and Ron Graham. The theorem covers the case for decks of size N = 2n, which branches into different results depending on the size of n and the value of n mod 4.

For N = 52, the group generated by I and O has

26! × 226

elements.

On the one hand, that’s a big number, approximately 2.7 × 1034. On the other hand, it’s quite small compared to 52! = 8 × 1067. So while there are a lot of permutations reachable by a combination of in-shuffles and out-shuffles, your chances of selecting such a permutation from the set of all such permutations is vanishingly small.

To put it yet another way, the number of arrangements is on the order of the square root of 52!, a big number, but not big relative to 52!. (Does this pattern

√52! ≈ 26! × 226

generalize? See the next post.)

Not only does the theorem of Diaconis et al give the order of the group, it gives the group itself: the group of permutations generated by I and O is isomorphic to the group of symmetries of a 26-dimensional octahedron.

[1] S. Brent Morris. Magic Tricks, Card Shuffling and Dynamic Computer Memories. MAA 1998.

Multiplication tables and Latin squares

Posted on by John

The multiplication table of a finite group forms a Latin square.

You form the multiplication table of a finite group just as you would the multiplication tables from your childhood: list the elements along the top and side of a grid and fill in each square with the products. In the context of group theory the multiplication table is called a Cayley table.

There are two differences between Cayley tables and the multiplication tables of elementary school. First, Cayley tables are complete because you can include all the elements of the group in the table. Elementary school multiplication tables are the upper left corner of an infinite Cayley table for the positive integers.

(The positive integers do not form a group under multiplication because only 1 has a multiplicative inverse. The positive integers form a magma, not a group, but we can still talk of the Cayley table of a magma.)

The other difference is that the elements of a finite group typically do not have a natural order, unlike integers. It’s conventional to start with the group identity, but other than that the order of the elements along the top and sides could be arbitrary. Two people may create different Cayley tables for the same group by listing the elements in a different order.

A Cayley table is necessarily a Latin square. That is, each element appears exactly once in each row and column. Here’s a quick proof. The row corresponding to the element a consists of a multiplied by each of the elements of the group. If two elements were the same, i.e. ab = ac for some b and c, then b = c because you can multiply on the left by the inverse of a. Each row is a permutation of the group elements. The analogous argument holds for columns, multiplying on the right.

Not all Latin squares correspond to the Cayley table of a group. Also, the Cayley table of an algebraic structure without inverses may not form a Latin square. The Cayley table for the positive integers, for example, is not a Latin square.

Here’s an example, the Cayley table for Q8, the group of unit quaternions. The elements are ±1, ±i, ±j, and ±k and the multiplication is the usual multiplication for quaternions:

i² = j² = k² = ijk = −1.

as William Rowan Hamilton famously carved into the stone of Brougham Bridge. I colored the cells of the table to make it easier to scan to verify that table is a Latin square.

Latin square posts

Quaternion posts

Up to isomorphism

Posted on by John

The previous post showed that there are 10 Abelian groups that have 2025 elements. Implicitly that means there are 10 Abelian groups up to isomorphism, i.e. groups that are not in some sense “the same” even if they look different.

Sometimes it is clear what we mean by “the same” and there’s no need to explicitly say “up to isomorphism” and doing so would be pedantic. Other times it helps to be more explicit.

In some context you want to distinguish isomorphic as different objects. This is fine, but it means that you have some notion of “different” that is more strict than “not isomorphic.” For example, the x-axis and the y-axis are different subsets of the plane, but they’re isomorphic as 1-dimensional vector spaces.

Abelian groups

There is a theorem that says ℤmn, the group of integers mod mn, is isomorphic to the direct sum ℤm ⊕ ℤn if and only if m and n are relatively prime. This means, for example, that ℤ15 and ℤ3 ⊕ ℤ5 are isomorphic, but ℤ9 and ℤ3 ⊕ ℤ3 are not.

Because of this theorem it’s possible to come up with a list of Abelian groups of order 2025 that looks different from the list in the previous post but it actually the same, where “same” means isomorphic.

In the previous post we listed direct sums of groups where each group was a cyclic group of some prime power order:

  • ℤ81 ⊕ ℤ25
  • ℤ81 ⊕ ℤ5 ⊕ ℤ5
  • ℤ27 ⊕ ℤ3 ⊕ ℤ25
  • ℤ27 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ9 ⊕ ℤ25
  • ℤ9 ⊕ ℤ9 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5

We could rewrite this list as follows by combining group factors of relatively prime orders:

  • ℤ2025
  • ℤ5 ⊕ ℤ405
  • ℤ3 ⊕ ℤ675
  • ℤ15 ⊕ ℤ135
  • ℤ9 ⊕ ℤ225
  • ℤ45 ⊕ ℤ45
  • ℤ3 ⊕ ℤ3 ⊕ ℤ295
  • ℤ3 ⊕ ℤ15 ⊕ ℤ45
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ75
  • ℤ3 ⊕ ℤ3 ⊕ ℤ15 ⊕ ℤ15

This listing follows a different convention, namely that the order of each group is a factor of the order of the next.

Related posts

Abelian groups of order 2025

Posted on by John

Every finite Abelian group can be written as the direct sum of cyclic groups of prime power order.

To find the number of Abelian groups of order 2025 we have to find the number of ways to partition the factors of 2025 into prime powers.

Now 2025 = 34 × 52.

We can partition 34 into prime powers 5 ways:

  • 34
  • 33 × 3
  • 32 × 32
  • 32 × 3 × 3
  • 3 × 3 × 3 × 3

And we can partition 52 two ways:

  • 52
  • 5 × 5

A couple of notes here. First, we only consider positive powers. Second, two partitions are considered the same if they consist of the same factors in a different order. For example, 3 × 3 × 32 and 32 × 3 × 3 are considered to be the same partition.

It follows that we can partition 2025 into prime powers 10 ways: we choose one of the five ways to partition 34 and one of the two ways to partition 52. Here are all the Abelian groups of order 2025:

  • ℤ81 ⊕ ℤ25
  • ℤ81 ⊕ ℤ5 ⊕ ℤ5
  • ℤ27 ⊕ ℤ3 ⊕ ℤ25
  • ℤ27 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ9 ⊕ ℤ25
  • ℤ9 ⊕ ℤ9 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5

Given a prime number q, there are as many ways to partition qk as the product of positive prime powers as there are ways to partition k into the sum of positive integers, denoted p(k). What we have shown above is that the number of Abelian groups of order 34 52 equals p(4) p(2).

In general, to find the number of Abelian groups of order n, factor n into prime powers, then multiply the partition numbers of the exponents in the factorization.

Related posts

Normal subgroups are subtle

Posted on by John

The definition of a subgroup is obvious, but the definition of a normal subgroup is subtle.

Widgets and subwidgets

The general pattern of widgets and subwidgets is that a widget is a set with some kind of structure, and a subwidget is a subset that has the same structure. This applies to vector spaces and subspaces, manifolds and submanifolds, lattices and sublattices, etc. Once you know the definition of a group, you can guess the definition of a subgroup.

But the definition of a normal subgroup is not something anyone would guess immediately after learning the definition of a group. The definition is not difficult, but its motivation isn’t obvious.

Standard definition

A subgroup H of a group G is a normal subgroup if for every g ∈ G,

g−1Hg = H.

That is, if h is an element of H, g−1hg is also an element of H. All subgroups of an Abelian group are normal because not only is g−1hg also an element of H, it’s the same element of H, i.e. g−1hg = h.

Alternative definition

There’s an equivalent definition of normal subgroup that I only ran across recently in a paper by Francis Masat [1]. A subgroup H of a group G is normal if for every pair of elements a and b such that ab is in H, ba is also in H. With this definition it’s obvious that every subgroup of an Abelian group is normal because ab = ba for any a and b.

It’s an easy exercise to show that Masat’s definition is equivalent to the usual definition. Masat’s definition seems a little more motivated. It’s requiring some vestige of commutativity. It says that a subgroup H of a non-Abelian group G has some structure in common with subgroups of normal groups if this weak replacement for commutativity holds.

Categories

Category theory has a way of defining subobjects in general that basically formalizes the notion of widgets and subwidgets above. It also has a way of formalizing normal subobjects, but this is more recent and more complicated.

The nLab page on normal subobjects says “The notion was found relatively late.” The page was last edited in 2016 and says it is “to be finished later.” Given how exhaustively thorough nLab is on common and even not-so-common topics, this implies that the idea of normal subobjects is not mainstream.

I found a recent paper that discusses normal subobjects [2] and suffice it to say it’s complicated. This suggests that although analogs of subgroups are common across mathematics, the idea of a normal subgroup is more or less unique to group theory.

Related posts

[1] Francis E. Masat. A Useful Characterization of a Normal Subgroup. Mathematics Magazine, May, 1979, Vol. 52, No. 3, pp. 171–173

[2] Dominique Bourn and Giuseppe Metere. A note on the categorical notions of normal subobject and of equivalence class. Theory and Applications of Categories, Vol 36, No. 3, 2021, pp. 65–101.

Groups of order 2024

Posted on by John

This time last year I wrote about groups of order 2023 and now I’d like to do the same for 2024.

There are three Abelian groups of order 2024, and they’re not hard to find.

We can factor

2024 = 8 × 11 × 23

and so the Abelian groups of order 2024 are of the form

G ⊕ ℤ11 ⊕ ℤ23

where G is a group of order 8, and there are three possibilities for G:

  • ℤ8,
  • ℤ4 ⊕ ℤ2, and
  • ℤ2 ⊕ ℤ2 ⊕ ℤ2.

How many non-Abelian groups of order 2024 are there? Conway’s estimate would be a total of 52 groups, Abelian and non-Abelian, but that turns out to be a bit high.

There is a formula for the number of groups of order n, but it only applies to square-free numbers. The number 2024 is divisible by 4, so it’s not square-free.

There are 46 groups of order 2024, so 43 of these are non-Abelian. When n is divisible by a square, finding the number of groups of order n is hard, but the results have been tabulated for small n. I’ve seen a table going up to 2048 and no doubt there are tables that go further.

Number of groups of squarefree order

Posted on by John

This post is a sort of footnote to the previous post, Estimating the number of groups of a given order.

The following is taken from an answer to a question on Stack Exchange.

In general there is no formula f(n) for the number of groups of order up to isomorphism. However, if n is squarefree (no prime to the power 2 divides n), then Otto Hölder in 1893 proved the following amazing formula

f(n) = \sum_{m \mid n} \prod_p \frac{p^{c(p)} - 1}{p-1}

where p is a prime divisor of n/m and c(p) is the number of prime divisors q of m that satisfy q = 1 (mod p).

In a sense that can be made precise, about 60% of integers are square free [1]. So Hölder’s formula is often useful, but there are a lot of values it can’t compute.

In this post I develop Python code to implement Hölder’s formula. I’ve tested the code below by comparing it to a table of f(n) for n = 1, 2, 3, …, 100.

from sympy import mobius, divisors, factorint

def squarefree(n):
    return n > 1 and mobius(n) != 0

def prime_divisors(n):
    return list(factorint(n).keys())

def c(p, m):
    return len( [q for q in prime_divisors(m) if q % p == 1] )

def holder(n):
    if not squarefree(n):
        print("Sorry. I can't help you.")
        return None

    s = 0
    for m in divisors(n):
        prod = 1
        for p in prime_divisors(n // m):
            prod *= (p**c(p, m) - 1) // (p - 1)
        s += prod
        
    return s

[1] The number of square-free integers between 1 and x is asymptotically equal to 6x/π² as x → ∞.

Estimating number of groups of a given order

Posted on by John

John Conway et al [1] give the name gnu(n) to the number of groups of order n, where “gnu” stands for group number. This function has been studied since the 19th century, but I don’t know whether there has ever been a standard notation for it. Mathematica calls it FiniteGroupCount. It’s also the first sequence in OEIS.

When n is square-free, there is a formula due to Hölder that computes gnu(n). This formula is given in the next post. But in general computing gnu(n) is hard. However, [1] gives a surprisingly good heuristic for estimating gnu(n).

Let Ω(n) be the number of prime factors of n, counted with multiplicity. So, for example, Ω(75) = 3 because 3 is a factor with multiplicity 1 and 5 is a factor with multiplicity 2.

Let B(n) be the nth Bell number, the number is the number of ways to partition a set of n labeled items.

The heuristic estimate for gnu(n) is

gnu(n) ≈ B( Ω(n) ).

This can be implemented in Python as follows.

    from sympy import bell, primeomega
    def estimate(n): return bell(primeomega(n))

The following plot shows the exact and approximate values of gnu(n) for n = 1, 2, 3, …, 100.

The exact value was plotted first in blue, then the estimate was plotted in orange. The orange line matches the blue so well as to hide it, except at the two spikes where gnu(n) is largest.

Here’s a plot of the errors.

Aside from the two outliers, the error is between −5 and 1.

[1] John H. Conway, Heiko Dietrich and E.A. O’Brien. Counting groups: gnus, moas and other exotica