Page 3 of 8 FirstFirst 12345 ... LastLast
Results 21 to 30 of 80

Thread: How many groups and semigroups and rings and the like - abstract algebra

  1. Top | #21
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    To try to get a clue as to the asymptotic behavior of all these binary-algebra counts, I decided to compare them to the asymptotic behavior of the general number of groupoids. I looked for something with form

    n^(c*n^2) / n!

    where I tried to find c.

    For quasigroups and loops, it is roughly 1/2.

    For semigroups, it is roughly 1/4.

    For commutative semigroups, it it roughly 3/16.

    For monoids, both in general and commutative, it is roughly 1/8.

    -

    For groups, however, c tends to 0, and their rate of increase is much less. The counts of them jump around quite a lot, and those counts are very sensitive to the exponents of the order's prime factors. So it's hard to make a simple statement.

  2. Top | #22
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    The prime-power-order groups or p-groups have many more elements than those of their "neighbors".

    For powers of 2: (exponent, order, # abelian groups, # groups
    • 0, 1, 1, 1
    • 1, 2, 1, 1
    • 2, 4, 2, 2
    • 3, 8, 3, 5
    • 4, 16, 5, 14
    • 5, 32, 7, 51
    • 6, 64, 11, 267
    • 7, 128, 15, 2328
    • 8, 256, 22, 56092
    • 9, 512, 30, 10494213
    • 10, 1024, 42, 49487365422

    Mathematica doesn't have a count for 2^(11) = 2048.

  3. Top | #23
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    I tried the Higman–Sims asymptotic formula for it, and it is, for order p^n for prime p, p^( (2/27)*n^3 + O(n^(8/3)) )

    That greatly overestimates how many 2-groups there are. I found a power c from 2^(n^c) and from n = 2 to 10 it is
    0, 0.766784, 0.964395, 1.0784, 1.16478, 1.24084, 1.32654, 1.43337, 1.55055

    It becomes approximately linear after 3 and 4, slowing down a bit until 5 and 6 and then speeding up a bit.

    For primes p greater than 2, Mma has counts for orders up to p^7, and for prime powers in the order from 0 to 7, these are the dominant powers of p in the counts:
    0, 0, 0, 0, 0, 1, 2, 5

    That's too few terms to make a convincing identification as a sequence in OEIS.


    Can we go beyond p-groups? There is a simple way of doing so. Some groups are direct product of p-groups for different primes. These groups are "nilpotent" ones, along with the p-groups themselves. Nilpotency means that if one repeats an operation on a binary algebra's set, one will end up at a single element. For semigroups, one uses the operation, but for groups, if one tries, one ends up with the original group again. So for groups, one defines a "commutator":

    [A,B] = group generated by all [a,b] = a*b*inv(a)*inv(b) for a in A and b in B

    One can repeat this operation in various ways.

    The "derived series" is a series of form G(1) = [G,G] with G(k+1) = [G(k),G(k)]. If it ends at the identity group, the group is "solvable". Every abelian group is solvable, and the smallest non-solvable group is the A(5), the group of even permutations of length 5 and order 60. This group and its non-solvability appears in the proof that general quintic equations cannot be solved with nth roots. The connection is in rearranging the roots of the equation, and using the result that nth roots imply that the group of rearrangements must be solvable.

    The "lower central series" is a series of form G(1) = [G,G] and G(k+1) = [G,G(k)]. if it ends at the identity group, then the group is nilpotent.

    The "upper central series" goes in reverse. Starting with the identity group, G(k+1) has all b that satisfy [a,b] in G(k) for all a in G. The member after the identity group is the "center" of the group. If this sequence ends at the original group, then the group is nilpotent.


    Needless to say, there are plenty of non-nilpotent groups, so I have only limited success in estimating how many groups there are.

  4. Top | #24
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Classification and enumeration of finite semigroups - Andreas Distler's PhD thesis - uses nilpotent semigroups to estimate how many there are.

    Nilpotency for semigroups is defined more simply than for groups: use the semigroup operation. One gets a power series:
    S(1) = S*S = S^(2)
    S(k+1) = S*S(k) = S^(k+1)
    If it ends at one element, then the semigroup is nilpotent. The first power of S that gives nilpotency is the degree of nilpotency.

    The null semigroup: for constant a and x, y in S, x*y = a. It has degree 2. Only the trivial semigroup has degree 1.

    The order-2 semigroups have power series:
    1: 12 - 1 - 1 - 1 - 1 ...
    2ab, 3, 4: 12 - 12 - 12 - 12 ...

    I'll write them for short as
    1: 12 - 1
    2ab, 3, 4: 12
    with the last member being the one that repeats endlessly.


    The order-3 semigroups have power series:
    1, 4, 5, 10, 12ab, 13, 14, 15ab, 16ab, 17ab, 18ab: 123
    2, 9, 11ab: 123 - 23
    3: 123 - 23 - 3
    6: 123 - 13
    7: 123 - 3

    Only one of them is nilpotent with degree 3.

    In general, nil-3 groups can be constructed with sets A and B satisfying
    A*A <= B, A*B = B*A = B*B = {z}, the power series' endpoint.

    The A*A operation is completely arbitrary, like the general groupoid operation, and AD used that result to calculate how many nil-3 semigroups there are. This was a nontrivial task, since it was necessary to divide out isomorphisms, like for groupoids. So we have these binary-operation algebras for which we have formulas for numbers of counts:
    • Groupoids: (general, self-converse, commutative) * (general, with identity)
    • Semigroups: nilpotent with degree 3
    • Groups: abelian, nilpotent (using p-groups)

  5. Top | #25
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Taking a power series on a semigroup produces a chain of subsemigroups. The null semigroup makes the trivial semigroup in one step, and those that are groups make themselves.

    1, 4, 5, 10, 12ab, 13, 14, 15ab, 16ab, 17ab, 18ab: Makes itself
    2: Makes 23 - 23.32 - Z2
    3: Makes 23 - 33.33 (2-element null semigroup) - then 3 (trivial semigroup) - a nil-3 semigroup
    6. Makes 13 - 31.13 - Z2
    7. Makes 3 (trivial semigroup) - is the 3-element null semigroup
    8. Makes 23 - 23.33 - boolean
    9. Makes 23 - 22.23 - boolean
    11a. Makes 23 - 22.33 - left zero
    11b. Makes 23 - 23.23 - right zero


    Turning to monoids, I note that every finite one can be expressed as the combination of a group G and a semigroup S. G*G = G and S*S <= S, and g*S = permutation of S and S*g = permutation on S for every g in G.

    The endpoint of a semigroup-like power series is G + (S subset).

    An easy kind of monoid is the "trivial action" one, where g*S = S*g = (unchanged order of S) for all g in G. So one can make a lower limit on the number of monoids by finding the number of trivial-action ones. I've done that, and it's very close to the numbers of monoids themselves.

    So having a nontrivial action makes a strong constraint on the semigroup part. That's g*S = (changed order of S) and likewise for S*g, both for some g in G.

    If the group part has order 1 (the identity group), then the monoid is a trivial-action monad (TAM), since the only group element is the identity. Likewise, for total order n, if the group part has order n-1 or n, the the monoid is a TAM because the semigroup part has only one element or none, giving only one possible action.

  6. Top | #26
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    For groups, there is an additional kind of decomposition that some of them may have. Consider subgroup H of group G.

    That group has "left cosets" x*H for x in G and also "right cosets" H*x for x in G. They are all disjoint and the same size as H. That makes the order of H evenly divide the order of G. This is Lagrange's theorem, and it makes a big constraint on possible subgroups of a group. A constraint that does not exist for semigroups or monoids more generally.

    The two sets of cosets need not be equal, but when they are, they are called plain cosets. They are equal when x.H.inv(x) = H for all x in G, though the elements in H may be rearranged. In that case, H is a "normal subgroup". One can then construct an operation table for cosets C1*C2 = C3 and one finds that it has the group properties. Thus, G and H have a "quotient group".

    If a group has no normal subgroups, it is a "simple group". An obvious one is Z(p), the cyclic group of prime order p. Since a prime number has no divisors other than 1 and itself, Lagrange's theorem shows that this group has no nontrivial subgroups. The trivial ones are itself and the identity group.

    Some decades ago, mathematicians succeeded in finding all the simple groups. Their proof too some 10,000 pages in a large number of articles scattered over mathematics journals. They found several infinite families, including the Z(p) family, and 26 "sporadic groups", outside of those families. Most of them are huge, and the largest one is called the monster group.

  7. Top | #27
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Having considered unary-operator and binary-operator algebras, the next one is a ternary-operator one. But there has been very little done on that.

    OEIS has A091510 - OEIS - Number of nonisomorphic algebras with a ternary operation (3-d groupoids) with n elements.

    The number increases asymptotically as n^(n^3)/n! -- super fast. By comparison, ordinary (2D) groupoids are at n^(n^2)/n! and 1D functions as 0.442 * 2.956^n / sqrt(n)

    For order-2 algebras, a unary operator has 4 possibilities with 3 distinct, a binary operator has 16 possibilities with 10 distinct, and a ternary operator has 256 possibilities with 136 distinct.


    Ternary quasigroups — page one.

    Quasigroups? Defined like binary-operator ones: for a, b, c, one can find x, y, z: a*b*x = c, a*y*b = c, z*a*b = c

    These are related to Latin cubes, a 3D generalization of Latin squares.

    Associativity? A ternary version: (a*b*c)*d*e = a*(b*c*d)*e = a*b*(c*d*e)

    Power-associativity is a weaker version where all the input variables are equal.

    Commutativity? a*b*c = b*a*c = c*b*a = a*c*b = b*c*a = c*a*b

    Identity? Use a pair of values.

  8. Top | #28
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    I'll now turn to pairs of binary algebras, as generalizations of addition and multiplication taken together.

    The usual starting point for this is the ring. It has a set of values and analogs of addition and multiplication with these properties:
    • Addition forms an abelian (commutative) group
    • Multiplication forms a semigroup (associative only)
    • Multiplication is distributive over addition:a*(b+c) = a*b+a*c and (b+c)*a = b*a+c*a.

    About the second property, common variations are to add the commutative property and/or an identity, making multiplication a monoid.

    The additive identity is usually called 0, and when it is present, the multiplicative identity is usually called 1. Some mathematicians reserve "ring" for those rings with 1, sometimes calling a ring without 1 a "rng" (no i, pronounced "rung").

    One can do a + a + a + ... for some nonzero a. The largest number n that produces 0 is the "characteristic" n and if 1 is present, it generates Z(n), the ring of integers modulo n. Otherwise, the ring has characteristic 0 and if 1 is present, it generates Z, the ring of integers.

    Distributivity and the additive identity together yield an interesting result.

    a*(b+0) = a*b + a*0 = a*b -> a*0 = 0
    (b+0)*a = b*a + 0*a = b*a -> 0*a = 0

    So 0 is a zero of multiplication, an absorber or annihilator.

    If nonzero a and b make 0 when multiplied, then a and b are a pair of "zero divisors". If a ring with no zero divisors, if a*b = 0 implies at least one of a and b being zero, then the ring is called a "domain", and if commutative an "integral domain".

    The ring Z(n) is a domain if n is a prime number, but not otherwise. That is because if n = n1*n2, both n1 and n2 being greater than 1, then n1*n2 = 0 mod n, making n1 and n2 zero divisors in Z(n).

    Z(prime) is not only a domain but also an integral domain.

    If all the ring elements but 0 form a group under multiplication, then the ring is a field. All the finite fields are known. Their orders are p^m for prime p, and there is only one field for each order, GF(p^m). It has additive group Z(p)^m and multiplicative group Z(p^m-1). For m = 1, the field is Z(p), while for m > 1, the construction is more complicated.

    The elements are polynomials in some variable x, polynomials with degree at most m-1 and with coefficients in Z(p). Addition proceeds as with polynomial addition in general, and multiplication is polynomial multiplication modulo some "primitive polynomial", a polynomial that cannot be factored in GF(p^m).

    To see how it works, I will construct GF(4). GF(2) is {0, 1} with addition and multiplication modulo 2. GF(4) is thus {0, 1, x, x+1}, and the primitive polynomial is x^2 + x + 1. The possible factors of a degree-2 polynomial are x and x+1, and their products are x^2, x^2+x, and (x+1)^2 = x^2 + 2x + 1 = x^ + 1 (arithmetic is modulo 2 here). The remaining polynomial is x^2 + x + 1. For larger fields, there will be more than one primitive polynomial, and one can choose whatever one wants of them.

    GF(2^m) can easily be done fast with typical computer hardware. Each bit in sequence corresponds to a power of the variable. Addition is xor, and multiplication can be done by shift and add, then subtracting out shifted copies of the primitive polynomial.

  9. Top | #29
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    If a ring has multiplicative inverses, it is called a "division ring": a*inv(a) = inv(a)*a = 1 for all nonzero a.

    Every finite division ring is also a field -- its multiplication is commutative. Also, every finite domain is also a finite integral domain and a finite field.

    Here is the multiplication table for GF(4):

    0 * (anything) = 0
    1 * (anything) = (that anything)
    x * x = x + 1
    x * (x+1) = 1
    (x+1) * (x + 1) = x
    {1, x, x+1} form group Z(3)

    Turning from fields to rings, we find a very interesting result. Every finite ring can be expressed as a direct product of rings with prime-power orders:

    R(n) = product of R(p^m) over p, m in factorization of n (prime p to power m)

    So we only need to do prime-power rings (p-rings?).

    A related result is the Multiplicative group of integers modulo n, what I'll call Zx(n). These groups' elements are all numbers from 1 to (n-1) that are relatively prime to n. They factorize as

    Zx(n) = product of Zx(p^m) over p, m in factorization of n

    For p > 2, the group is Z(p^(m-1)*(p-1))

    For p = 2, the group is, for m = 1, the identity group, and for m > 1, Z(2) * Z(2^(m-2))

    That is also true for the additive group of integers modulo n, Cyclic group, Z(n). From the Chinese remainder theorem,

    Z(n) = product of Z(p^m) over p, m in factorization of n

    As I'd mentioned earlier, this is also true of nilpotent groups - they are direct products of prime-power groups.

  10. Top | #30
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    So we must concern ourselves with prime-power rings.

    For generators a, b, c, ...the elements are na*a + nb*b + nc*c + ... where na, nb, nc, ... are in Z(p^m(a)) where m is the power associated with generator a. If the ring has 1, then it is also a generator.

    For power 1, the additive group is Z(p), and the two kinds of rings are the zero ring and the ring Z(p), equal to GF(p). They are both commutative, and one has an identity and the other one doesn't. I'll list them as {# - id - cmt, - id + cmt, + id - cmt, +id +cmt} where id = identity and cmt = commutative property. Thus,
    {0, 1, 0, 1}

    For power 2, the additive groups are Z(p^2) and Z(p)*Z(p), and there are 11 kinds of rings.

    For Z(p^2), there are three rings: the zero ring, Z(p^2), and a third ring with generator a satisfying a^2 = p*a.
    {0, 2, 0, 1}

    For Z(p)*Z(p), there are three composite rings, Z(p)*Z(p), (zero)*Z(p), and (zero)*(zero)
    {0, 2, 0, 1}

    There are two rings with identity (generators 1, a): a^2 = c0 + c1*a (primitive polynomial for GF(p^2)) and a^2 = 0. There is a commutative ring without identity, a^2 = b, other products zero, and two non-commutative ones without idenitty, a^2 = a, a*b = b, others zero and a^2 = a, b*a = b, others zero.
    {2, 1, 0, 2}

    Both reducible and irreducible for Z(p)*Z(p): {2, 3, 0, 3}
    All for p^2: {2, 5, 0, 4}

    I won't describe the rings for higher prime powers.

    For prime power 3,

    Irreducible:
    Z(p^3): {0, 3, 0, 1}
    Z(p)*Z(p^2): {(6,3+2p), (6,7), 0, (2,3)}
    Z(p)*Z(p*Z(p): {(7,6+p), 3, 1, 3}
    The ()'s contain (value for p = 2, value for p > 2)

    All:
    Z(p^3): {0, 3, 0, 1}
    Z(p)*Z(p^2): {(6,3+2p), (11,12), 0, (3,4)}
    Z(p)*Z(p)*Z(p): {(11,10+p), 10, 1, 6}
    Total: {(17,13+3p), (24,25), 1, (10,11)}
    Grand total: (52, 50+3p)

    General formulas get more complicated for higher powers of primes, so I'll only do 2 and 3, what I've seen numbers for.

    All:
    For 2^3: {17, 24, 1, 10} = 52
    For 3^3: {22, 25, 1, 11} = 59
    For 2^4: {215, 125, 13, 37} = 390
    For 3^4: {>338, >114, 18, 39} = (509)
    For 2^5: {>826576, >3566, 99, 109} = (>830350)

    Some of these calculations are incomplete, but it is evident that the number of rings increases rapidly with increasing prime power.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •