Groups of order 2019

Posted on 30 December 2018 by John

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]

$G \rtimes H$

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 (g₁, h₁) and (g₂, h₂) is defined to be

(g₁ + h₁⁻¹g₂, h₁ h₂)

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⁻¹).

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 multiplication    
    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 )

[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.

Number of groups of prime power order

Posted on 19 September 2018 by John

John Baez left a comment on my post on group statistics saying

It’s known that the number of groups of order p^n for prime p is p^{2n^3/27+O(n^(8/3))}. It might be fun to compare this to what Mathematica says.

Here goes. First let’s let p = 2. Mathematica’s FiniteGroupCount function tops out at n = 10. And for the range of values Mathematica does support, 2^{2n^3/27} grossly overestimates the number of groups.

    Table[{FiniteGroupCount[2^n], 2^((2./27) n^3)}, {n, 1, 11}]

    {{1, 1.05269}, {2, 1.50795}, {5, 4.}, {14, 26.7365}, 
    {51, 612.794}, {267, 65536.}, {2328, 4.45033*10^7}, 
    {56092, 2.61121*10^11}, {10494213, 1.80144*10^16}, 
    {49487365422, 1.98847*10^22}, {FiniteGroupCount[2048], 4.7789*10^29}}

OEIS has entries for the sizes of various groups, and the entry for powers of 2 confirms the asymptotic formula above. Maybe it’s not a good approximation until n is very large. (Update: Here’s a reference for the asymptotic expression for all p.)

The OEIS entry for number of groups of order powers of 5 has an interesting result:

For a prime p >= 5, the number of groups of order p^n begins 1, 1, 2, 5, 15,
61 + 2*p + 2*gcd (p – 1, 3) + gcd (p – 1, 4),
3*p^2 + 39*p + 344 + 24*gcd(p – 1, 3) + 11*gcd(p – 1, 4) + 2*gcd(p – 1, 5), …

We can duplicate this with Mathematica.

    Table[FiniteGroupCount[5^n], {n, 0, 6}]

    {1, 1, 2, 5, 15, 77, 684}

and the last two numbers match the calculations given in OEIS.

There’s something interesting going on with Mathematica. It doesn’t seem to know, or agree with, the formula above for groups of order p⁴. For example,

    Table[FiniteGroupCount[7^n], {n, 0, 6}]

    {1, 1, 2, 5, FiniteGroupCount[2401], 83, 860}

I get similar results when I use larger primes: it can’t handle the fourth power.

    Table[FiniteGroupCount[389^n], {n, 0, 6}]

    {1, 1, 2, 5, FiniteGroupCount[22898045041], 845, 469548}

The results for n = 5 and 6 agree with OEIS.

Is OEIS wrong about the number of groups of order p⁴ or should Mathematica simply return 15 but there’s a gap in the software?

Also, does anybody know why the agreement with the asymptotic formula above is so bad? It’s just as bad or worse for other primes that I tried.

Overlap in the classification of finite simple groups

Posted on 9 September 2018 by John

The previous post defined the groups PSL(n, q) where n is a positive integer and q is a prime power. These are finite simple groups for n ≥ 2 except for PSL(2, 2) and PSL(2, 3).

Overlap among PSL(n, q)

There are a couple instances where different values of n and q lead to isomorphic groups: PSL(2, 4) and PSL(2, 5) are isomorphic, and PSL(2, 7) and PSL(3, 2) are isomorphic. These are the only instances [1].

With the exceptions stated above, distinct values of n and q lead to distinct groups. Is it possible for different choices of n and q to lead to groups of the same size, even though the groups are not isomorphic to each other? Yes, PSL(3, 4) and PSL(4, 2) both have order 20160, but the groups are not isomorphic. This is the only example [2].

Overlap between PSL and alternating groups

The first post in this series mentioned that for n ≥ 5, the alternating group A_n, the group of even permutations on a set of n elements, is a simple group. Three of the alternating groups are isomorphic to PSL groups:

PSL(2, 4) = PSL(2, 5) = A₅
PSL(2, 9) = A₆
PSL(4, 2) = A₈

Here “=” really means isomorphic. We mentioned PSL(4, 2) above. It has the same order as PSL(3, 4). This means that A₈ and PSL(3, 4) have the same order but are not isomorphic.

I suspect that with a small number of exceptions, the order of a finite simple group determines the group. I haven’t proven that, but numerical exploration suggests its true. This page lists non-Abelian finite simple groups of order less than 10 billion, and there are only seven orders that correspond to more than 1 group, the largest example being order 25,920.

One last overlap

There is only one other duplication in the lists of groups in the CFSG theorem, and that is PSU(4, 2) = PSp(4, 3). I haven’t written about these groups yet.

Notes

[1] See The Finite Simple Groups by Robert A. Wilson

[2] In fact, aside from the groups mentioned in this post, the orders of all the finite simple groups are unique except for two non-isomorphic families that have orders: PΩ_2n+1(q) and PSp_2n(q) for n ≥ 3 and odd prime powers q. See discussion on Math Overflow.

Orders of finite simple groups

Posted on 2 September 2018 by John

Simple groups are to groups as prime numbers are to numbers.A simple group has no non-trivial normal subgroups, just as a prime number has no non-trivial factors.

Classification

Finite simple groups have been classified into five broad categories:

Cyclic groups of prime order
Alternating groups
Classical groups
Exceptional groups of Lie type
Sporadic groups.

Three of these categories are easy to describe.

The cyclic groups of prime order are simply the integers mod p where p is prime. These are the only Abelian finite simple groups.

The alternating groups are even-order permutations of a set. These groups are simple if the set it permutes has at least 5 elements.

The sporadic groups are a list of 26 groups that don’t fit anywhere else. The other categories are infinite families of groups, but the sporadic groups are just individual groups.

The classical groups and exceptional Lie groups are harder to describe. I’d like to write about them in some detail down the road. For now, I’ll be deliberately vague.

This post is a broad overview, and may be the first of more posts in a series. This post just looks at the sizes (orders) of the groups.

Update: Here’s a follow-on post that looks at the groups denoted A_n(q).

Smallest group in each family

You can find a list of the families of finite simple groups on Wikipedia, along with their orders (the number of elements in each group). We can use this to determine the smallest group in each family, just to get an idea of how these families spread out.

The classical groups and exceptional Lie groups that I glossed over depend on a parameter n and/or a parameter q where q is a prime power. Even for very small values of n and q, the smallest ones for which the groups are simple, some of these groups are BIG.

|------------------+----------------------------------------------|
| Family           |               Order of smallest simple group |
|------------------+----------------------------------------------|
| Cyclic(p)        |                                            2 |
| Alternating(n)   |                                           60 |
| A_n(q)           |                                           60 |
| Sporadic         |                                         7920 |
| B_n(q)           |                                        25920 |
| Suzuki(2^(2n+1)) |                                        29120 |
| 2A_n(q^2)        |                                       126000 |
| C_n(q)           |                                      1251520 |
| G_2(q)           |                                      4245696 |
| 2F_4(q)'         |                                     17971200 |
| D_n(q)           |                                    174182400 |
| 3D_n(q^2)        |                                    197406720 |
| 3D_4(q^3)        |                                    211341312 |
| 2G_2(q)          |                                  10073444472 |
| F_4(q)           |                             3311126603366400 |
| 2E_6(q^2)        |                      76532479683774853939200 |
| E_6(q)           |                     214841575522005575270400 |
| 2F_4(q)          |                     264905352699586176614400 |
| E_7(q)           |     7997476042075799759100487262680802918400 |
| E_8(q)           | 33780475314363480626138819061408559507999169 |
|------------------+----------------------------------------------|

Never mind the cryptic family names for now; I may get into these in future posts. My point here is that for some of these families, even the smallest member is quite large.

Interestingly, the smallest sporadic group has a modest size of 7920. But the largest sporadic group, “The Monster,” has order nearly 10⁵⁴. You could think of each sporadic group of being a lonely family of one, so I’ll list their orders here. (There are groupings within the sporadic groups, but I’m not clear how much these are grouped together for historical reasons (i.e. who discovered them) or mathematical reasons. I expect there’s a blurry line between the historical and mathematical since the groups discovered by an individual were amenable to that person’s techniques.)

|-------+--------------------------------------------------------|
| Group |                         Order of smallest simple group |
|-------+--------------------------------------------------------|
| M_11  |                                                   7920 |
| M_12  |                                                  95040 |
| J_1   |                                                 175560 |
| M_22  |                                                 443520 |
| J_2   |                                                 604800 |
| M_23  |                                               10200960 |
| HS    |                                               44352000 |
| J_3   |                                               50232960 |
| M_24  |                                              244823040 |
| McL   |                                              898128000 |
| He    |                                             4030387200 |
| Ru    |                                           145926144000 |
| Suz   |                                           448345497600 |
| O'N   |                                           460815505920 |
| Co_3  |                                           495766656000 |
| Co_2  |                                         42305421312000 |
| Fi_22 |                                         64561751654400 |
| HN    |                                        273030912000000 |
| Ly    |                                      51765179004000000 |
| Th    |                                      90745943887872000 |
| Fi_23 |                                    4089470473293004800 |
| Co_1  |                                    4157776806543360000 |
| J_4   |                                   86775571046077562880 |
| Fi_24 |                              1255205709190661721292800 |
| B     |                     4154781481226426191177580544000000 |
| M     | 808017424794512875886459904961710757005754368000000000 |
|-------+--------------------------------------------------------|

Groups of order less than a million

In 1972, Marshall Hall published a list of the (non-Abelian) finite simple groups of order less than one million. Hall said that there were 56 such groups known, and now that the classification theorem has been completed we know he wasn’t missing any groups.

There are 78,498 primes less than one million, so there are that many cyclic (Abelian) finite groups of order less than one million. In the range of orders one to a million, Abelian simple groups outnumber non-Abelian simple groups by over 1400 to 1. Of the 56 non-Abelian orders, 46 belong to groups of the form A_n(q). Most of the families in the table above don’t make an appearance since their smallest representatives have order much larger than one million.

There can be multiple non-isomorphic groups with the same order, especially for small orders. This is another detail I may get into in future posts.

Growth of group orders

Now let’s look at plots to see how the size of the groups grow. Because these numbers quickly get very large, all plots are on a log scale.

In case you have difficulty seeing the color differences, the legends are in the same vertical order as the plots.

Some of the captions list two or three groups. That is because the curves corresponding to the separate groups are the same at the resolution of the image.

Here are groups that only depend on a parameter n.

Here are groups that only depend on a parameter q. The q‘s vary over prime powers: 2, 3, 4, 5, 7, 8, 9, 11, etc. Note that the horizontal axis is not q itself but the index of q, i.e. i on the horizontal scale corresponds to the ith prime power.

For the groups that depend on n and q, we vary these separately. First we hold n fixed at 5 and let q vary.

Finally, we now fix q at 5 and let n vary.

Looking up group by size

Imagine writing a program that takes the size n of a finite simple group and tells you what groups it could be. What would such a program look like?

Since the vast majority of finite simple groups below a given size are cyclic, we’d check whether n is prime. If it is, then the group is the integers mod n. What about the non-Abelian groups? These are so thinly spread out that the simplest thing to do would be to make a table of the possible values less than the maximum program input size N. If we set N = 10,000,000,000, then David Madore has already been done here. There are only 491 possible orders for non-Abelian simple groups of order less than 10 billion.

We said above that Abelian groups outnumbered non-Abelian groups by over 1400 to 1 for simple groups of order less than one million. What about for simple groups of order less than 10 billion? The number of primes less than 10 billion is 455,052,511 and so Abelian simple groups outnumber non-Abelian simple groups by a little less than a million to one.

Conclusion

This post began by saying simple groups are analogous to prime numbers. The Abelian finite simple groups are exactly integers modulo prime numbers. The orders of the non-Abelian finite simple groups are spread out much more sparsely than prime numbers.

Also, the way you combine simple groups to make general groups is more complicated than the way you multiply prime numbers to get all integers. There was speculation that group theory would die once finite simple groups were classified, but that has not been the case. Unfortunately (or fortunately if you’re a professional group theorist) the classification theorem doesn’t come close to telling us everything we’d want to know about groups.

A tale of two elliptic curves

Posted on 21 August 2018 by John

A few days ago I blogged about the elliptic curve secp256k1 and its use in Bitcoin. This curve has a sibling, secp256r1. Note the “r” in the penultimate position rather than a “k”. Both are defined in SEC 2: Recommended Elliptic Curve Domain Parameters. Both are elliptic curves over a field z_p where p is a 256-bit prime (though different primes for each curve).

The “k” in sepc256k1 stands for Koblitz and the “r” in sepc256r1 stands for random. A Koblitz elliptic curve has some special properties that make it possible to implement the group operation more efficiently. It is believed that there is a small security trade-off, that more “randomly” selected parameters are more secure. However, some people suspect that the random coefficients may have been selected to provide a back door.

Both elliptic curves are of the form y² = x³ + ax + b. In the Koblitz curve, we have

a = 0
b = 7

and in the random case we have

a = FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC
b = 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B

You can find the rest of the elliptic curve parameters in the SEC 2 report. For some help understanding what the parameters mean and how to decode them, see my earlier post.

The NSA recommends the random curve for government use. It is also known as NIST P-256. Or rather it did recommend P-256 as part of its Suite B of cryptography recommendations. In August 21015 the NSA announced its concern that in the future, quantum computing could render the Suite B methods insecure. As far as we know, quantum computing at scale is years, maybe decades, away. But it takes a long time to develop quality encryption methods, and so the NSA and NIST are urging people to think ahead. (Update: The NSA recommends P-384 until post quantum methods mature.)

Bitcoin chose to use the less popular Koblitz curve for the reasons mentioned above, namely efficiency and concerns over a possible back door in the random curve. Before Bitcoin, secp256k1 was not widely used.

Related post: RSA numbers and factoring

Schnorr groups

Posted on 15 August 2018 by John

Claus Schnorr

Schnorr groups, named after Claus Schnorr, are multiplicative subgroups of a finite field. They are designed for cryptographic application, namely as a setting for hard discrete logarithm problems.

The application of Schnorr groups to Schnorr signatures was patented, but the patent ran out in 2008.

There has been a proposal to include Schnorr signatures in Bitcoin, but it has not been accepted at this point. (The proposal would use Schnorr signatures but over an elliptic curve rather than a Schnorr group.)

Group construction

Pick a large prime p. Then the integers mod p form a finite field. The non-zero elements form an Abelian group of order p −1 under multiplication. Then p − 1 is composite, and so it can be factored into qr where q is prime. We want q to be large as well because it will be the order of our Schnorr group.

Pick any h such that h^r is not congruent to 1 mod p. Then g = h^r is the generator of our Schnorr group. Why does g have order q? A simple calculation shows

$g^q \equiv h^{qr} \equiv h^{p-1} \equiv 1 \pmod p$

where the last step follows from Fermat’s little theorem. This shows that the order of g is either q or a divisor of q, but by construction g is not congruent to 1 (mod p), and q has no other factors since it is prime.

Python code

Here’s a toy example using small numbers. Let p = 23, q = 11 and r = 2. Then we can pick h to be any number that is not a root of 1 (mod 23), i.e. any number except 1 or 22. Say we pick h = 7. Then g = 49 = 3 (mod 23).

Here’s a Python script to verify our claims and print out the elements of our Schnorr group.

    from sympy import isprime
    
    p, q, r, h = 23, 11, 2, 7
    
    assert(isprime(p))
    assert(isprime(q))
    assert(p-1 == q*r)
    
    g = h**r % p
    assert(g != 1)
    assert(g**q % p == 1)
    
    for i in range(q):
        print( g**i % p )

This shows that our group elements are {1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8}.

In theory we could use the same script with much larger numbers, but in that case we wouldn’t want to print out the elements. Also, the code would take forever. We naively computed a^b (mod m) by computing a^b first, then taking the remainder modulo m. It is far more efficient to reduce modulo m along the way. That’s what Python’s three-argument pow function does.

Here’s a revised version that runs quickly with large numbers.

    from sympy import isprime
    
    p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
    q = 341948486974166000522343609283189
    r = 338624364920977752681389262317185522840540224
    h = 3141592653589793238462643383279502884197
    
    assert(isprime(p))
    assert(isprime(q))
    assert(p-1 == q*r)
    
    g = pow(h, r, p)
    assert(g != 1)
    assert(pow(g, q, p) == 1)

Photo of Claus Schnorr by Konrad Jacobs CC BY-SA 2.0 de

Summarizing homotopy groups of spheres

Posted on 20 July 2018 by John

I don’t understand homotopy groups of spheres, and it’s OK if you don’t either. Nobody fully understands them. This post is really more about information compression than homotopy. That is, I’ll be looking at ways to summarize what is known without being overly concerned about what the results mean.

The task: map two integers to a list of integers

For each positive integer k, and non-negative integer n, the kth homotopy group of the sphere Sⁿ is a finitely generated Abelian group, something that can be described by a finite list of numbers. So we’re looking at simply writing a function that takes two integers as input and returns a list of integers. This function is implemented in an online calculator that lets you lookup homotopy groups.

Computing homotopy groups of spheres is far from easy. The first Fields medal given to a topologist was for partial work along these lines. There are still groups that haven’t been computed, and potentially more Fields medals to win. But our task is much more modest: simply to summarize what has been discovered.

This is not going to be too easy, as suggested by the sample of results in the table below.

table of homotopy groups of spheres

This table was taken from the Homotopy Type Theory book, and was in turn based on the Wikipedia article on homotopy groups of spheres.

Output data representation

To give an example of what we’re after, the table says that π₁₃(S²), the 13th homotopy group of the 2-sphere, is Z₁₂ × Z₂. All we need to know is the subscripts on the Z‘s, the orders of the cyclic factors, and so our function would take as input (13, 2) and return (12, 2).

The table tells us that π₈(S⁴) = Z₂². This is another way of writing Z₂ × Z₂, and so our function would take (8, 4) as input and return (2, 2).

When I said above that our function would return a list of integers I glossed over one thing: some of the Z‘s don’t have a subscript. That is some of the factors are the group of integers, not the group of integers mod some finite number. So we need to add an extra symbol to indicate a factor with no subscript. I’ll use ∞ because the integers as the infinite cyclic group. For example, our function would take (7, 4) and return (∞, 12). I will also use 1 to denote the trivial group, the group with 1 element.

Some results are unknown, and so we’ll return an empty list for these.

The order of the numbers in the output doesn’t matter, but we will list the numbers in descending order because that appears to be conventional.

Theorems

Some of the values of our function can be filled in by a general theorem, and some will simply be data.

If we call our function f, then there is a theorem that says f(k, n) = (1) if k < n. This accounts for the zeros in the upper right corner of the chart above.

There’s another theorem that says f(n+m, n) is independent of n if n > m + 1. These are the so-called stable homotopy groups.

The rest of the groups are erratic; we can’t do much better than just listing them as data.

(By the way, the corresponding results for homology rather than homotopy are ridiculously simple by comparison. For k > 0, the kth homology group of Sⁿ is isomorphic to the integers if k = n and is trivial otherwise.)

Weakening the requirements of a group

Posted on 8 July 2018 by John

A group is a set with a binary operation that

closed
associative,
has an identity, and
has inverses.

This post will look at each of these properties and what happens if you modify or remove it.

Magmas

Closed means that applying the binary operation to any two elements of the set yields another elements of the set. (I saw a book one time that had at the top of some chapter a quote something like “The product of two real numbers is a real number; we should be surprised if it were a head of cabbage.”) For example, the positive integers are closed under multiplication but not under division.

A set with a closed binary operation is called a magma.

Semigroups

Associative means that you can parenthesize an expression any way you want and always get the same result. It may be practically important how you parenthesize an expression. For example, matrix multiplication can far fewer operations if you carry out the multiplications in the right order. In programming, left folds and right folds (such as foldl and foldr in Haskell) may have very different efficiency, but they’re supposed to return the same result if you’re folding an associative operation.

A magma with an associative operation is called a semigroup.

Differential equation theory is concerned with analytic semigroups. If you advance the solution of an evolution equation by a positive time increment t and then by an increment s, you end up at the same place as if you’d advanced the solution by t + s.

Notice that the time increment is required to be positive. That’s because the initial conditions for an evolution equation might reside in a different function space than the solutions at any future time. That’s the case, for example, with the heat equation, where initial conditions can be rough but the solution smooths out immediately as you move forward in time.

Monoids

If you add the requirement that a semigroup has an identity, you get a monoid. Partial differential equation theory is more concerned with analytic semigroups than analytic monoids for the reason explored above: you might not have an identity.

Positive integers with multiplication form a monoid but not a group because they have an identity, 1, but positive integers other than 1 do not have a multiplicative inverse that is an integer.

A monoid in which every element has an inverse is a group.

Quasigroups

So far we’ve built up a progression of stronger and stronger requirements leading up to groups, starting with requiring that our operation is associative. What if we don’t have associativity, but we do have other properties?

Non-associative operations are less common. Perhaps the best known operation that is not associative is octonion multiplication.

There are four division algebras over the reals: the reals themselves, complex numbers, quaternions, and octonions. Real and complex numbers are both fields. Quaternions are not a field because multiplication is not commutative. Octonions are even further from being a field because multiplication is not even associative.

But division is possible for octonions, except for 0, and so non-zero octonions form a quasigroup, a magma with division.

Loops

A quasigroup that has an identity element is called a loop. Note that for quasigroups we said “division is possible,” not that elements have inverses. If elements do have inverses, then you can divide by an element by multiplying by its inverse. But you can define division by the ability to solve equations. We say you can divide b by a if ax = b and ya = b have unique solutions.

A loop with associativity is a group.

Alternative loops

Loops are not required to have an associative property, but they may satisfy a weak form of associativity.

An alternative loop satisfies x(xy) = (xx)y and x(yy) = (xy)y. Non-zero octonions form an alternative loop with respect to multiplication.

Moufang loops

A Moufang loop is a loop that satisfies these requirements:

z(x(zy)) = ((zx)z)y
x(z(yz)) = ((xz)y)z
(zx)(yz) = (z(xy))z
(zx)(yz) = z((xy)z)

These conditions imply the alternative loop conditions, so Moufang loops are alternative loops.

Moufang loop are still not required to be associative, but they’re getting closer. And as you might have anticipated, non-zero octonions with respect to multiplication form a Moufang loop.

Semidirect products

Product

Identity

Inverse

Python code

Related posts

Related posts

More algebra posts

More group theory posts

Overlap among PSL(n, q)

Overlap between PSL and alternating groups

One last overlap

Notes

Classification

Smallest group in each family

Groups of order less than a million

Growth of group orders

Looking up group by size

Conclusion

Group construction

Python code

Related posts

The task: map two integers to a list of integers

Output data representation

Theorems

Magmas

Semigroups

Monoids

Quasigroups

Loops

Alternative loops

Moufang loops

Related posts