Page 2 of 8 FirstFirst 1234 ... LastLast
Results 11 to 20 of 80

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

  1. Top | #11
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    It's sometimes not very clear from OEIS where a sequence starts, at size parameter 0 (empty set) or size parameter 1 (one-member set).

    That aside, a less restrictive version of the inverse condition is the regularity condition: for every element a, there is at least one element x such that a = a*x*a.

    Another interesting property is the cancellative property. A semigroup is left cancellative if a*b = a*c implies b = c, right cancellative if b*a = c*a implies b = c, and plain cancellative if both left and right cancellative.

    A finite cancellative semigroup is a group.

    A monogenic semigroup has one generator: all the elements are powers of it. A finite one will repeat itself. I write them as (initial elements) (repeating elements in parens). Thus 1(23) is 1^2 = 2, 1*2 = 3, 1*3 = 2, ... If the period is one, then it's called aperiodic.

    Semigroup with two elements

    1. Null semigroup: 11.11 and 22.22
    Commut, zero

    2a. Left-zero semigroup: 11.22
    2b. Right-zero semigroup: 12.12

    3. Boolean semigroup: 11.12 and 12.22
    Commut, identity, inverse

    4. Z2 group: 12.21 and 21.12
    Commut, identity, inverse

    Of these, (3) and (4) are monoids and (4) is a group.

    Semigroup with three elements

    1. Z3 group: 123.231.312
    Commut, identity, inverse

    2. Monogenic: 232.323.232
    Commut

    3. Aperiodic: 233.333.333
    Commut

    4. {-1,0,1} under mult: 321.222.123
    Commut, identity, zero, inverse

    5. 311.123.133
    Commut, identity, inverse

    6. 311.133.133
    Commut

    7. Null: 333.333.333

    8. 333.323.333
    Commut

    9. 323.222.323
    Commut

    10. 313.123.333
    Commut, identity

    11a. 333.222.333
    11b. 323.323.323

    12a. 333.123.333
    12b. 313.323.333

    13. Semilattice: 123.223.333
    Commut, identity, inverse

    14. Semilattice: 133.323.333
    Commut, inverse

    15a. Idempotent: 111.222.113
    13b. Idempotent: 121.121.123
    Regular

    16a. Idempotent: 113.223.333
    16b. Idempotent: 123.123.333
    Regular

    17a. Left zero: 111.222.333
    17b. Right zero: 123.123.123
    Regular

    18a. Idempotent (left flip-flop): 111.222.123
    18b. Idempotent (right flip-flop): 121.122.123
    Regular, identity

    Not very sure about what qualifies as an inverse semigroup - my attempt to find what's inverse and what's regular are in diagreement with OEIS's counts. But my evaluations of the commutative and identity properties agree with OEIS's counts.

  2. Top | #12
    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 now consider groups: monoids with inverses: a*inv(a) = inv(a)*a = (identity)

    Number of finite groups with each order: A000001 - OEIS

    1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51, 1, 2, 1, 14, 1, 2, 2, 14, 1, 6, 1, 4, 2, 2, 1, 52, 2, 5, 1, 5, 1, 15, 2, 13, 2, 2, 1, 13, 1, 2, 4, 267, 1, 4, 1, 5, 1, 4, 1, 50, 1, 2, 3, 4, 1, 6, 1, 52, 15, 2, 1, 15, 1, 2, 1, 12, 1, 10, 1, 4, 2

    Commutative groups are often called Abelian ones.

    Number of finite abelian groups with each order: A000688 - OEIS

    1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 5, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 6, 1, 1, 2, 2, 1, 1, 1, 5, 5, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 7, 1, 2, 2, 4, 1, 1, 1, 3, 1, 1, 1

    Mathematica has built-in functions, FiniteGroupCount and FiniteAbelianGroupCount, which can go much farther than what OEIS lists.

    For finite abelian groups, there is a formula.

    Every abelian group is known: it is a product of cyclic groups of prime-power order. If a cyclic group's order is the product of powers of more than one prime, then it can be broken apart into prime-power cyclic groups. This is because Z(n1*n2) = Z(n1)*Z(n2) if n1 and n2 are relatively prime (coprime). For instance, Z(6) = Z(2)*Z(3) and Z(12) = Z(4)*Z(3). But Z(4) does not reduce to Z(2)*Z(2).

    Thus, for order 4, there are Z(2)*Z(2) and Z(4), and for order 8, Z(2)*Z(2)*Z(2), Z(2)*Z(4), and Z(8).

    The powers of 2 are for 4 = 2^2, 1 1 and 2, and for 8 = 2^3, 1 1 1 and 1 2 and 3.

    Thus, we find all integer partitions of a power, Mathematica's IntegerPartitions with count PartitionsP.

    So for order n factorizing into (product over primes p of p^(m(p))), the order is (product over p of (number of partitions of m(p)))

    -

    There isn't an analogous formula for groups in general.

  3. Top | #13
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    There is a simple way of making groupoids from other groupoids. Composition. Take groupoids (G1,*1) and (G2,*2). Compose a product groupoid, (G12,*12) where the elements of G12 are (a1,a2) with a1 in G1 and a2 in G2. The operation is

    a*b = (a1*b1,a2*b2)

    So from two order-2 groupoids, one can make an order-4 one. One can calculate the number of irreducible groupoids, one that cannot be decomposed in this fashion, from the total number of groupoids.
    m(1) = n(1)
    m(2) = n(2)
    m(3) = n(3)
    m(4) = n(4) - m(2)*(m(2)+1)/2
    m(5) = n(5)
    m(6) = n(6) - m(2)*m(3)
    m(7) = n(7)
    m(8) = n(8) - m(2)*(m(2)+1)*(m(2)+2)/6 - m(2)*m(4)

    One has to be careful with repeated irreducible ones, to avoid duplicates.

    With the number of abelian groups, I indeed find that the number of irreducible ones is 1 for a prime power, 0 otherwise.

  4. Top | #14
    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 will now create some comparison tables.

    Algebra 1 2 3 4 5 6 7 8
    Groupoid 1 10 3330 1.79e8 2.48e15 1,43e25 5.10e37 1.56e53
    Irreducible gpd 1 10 3330 1.79e8 2.48e15 2.43e25 5.10e37 1.56353
    Commutative gpd 1 4 129 43968 2.54e8 3.05e13 9.13e19 8.05e27
    Irreducible cmt gpd 1 4 129 43958 2.54e8 3.05e13 9.13e19 8.05e27
    Gpd w/ identity 1 2 45 43968 6.36e9 2.37e17 3.68e27 3.54e40
    Irreducible gpd id 1 2 45 43965 6.36e9 2.37e17 3.68e27 3.54e60
    Commutative gpd id 1 2 15 720 409600 3.92e9 7.76e14 3.84e21
    Irreducible cmt gpd id 1 2 15 717 409600 3.92e9 7.76e14 3.84e21

    The reducible ones barely make a dent in the totals.

  5. Top | #15
    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 will now add the division property.

    Algebra 1 2 3 4 5 6 7 8
    Quasigroup 1 1 5 35 1411 1.13e6 1.212e10 2.70e15
    Irreducible qsg 1 1 5 34 1411 1.13e6 1.22e10 2.70e15
    Commutative qsg 1 1 3 7 11 491 6381
    Irreducible cmt qsg 1 1 3 6 11 488 6381
    Loop - qsg with identity 1 1 1 2 6 109 23746 1.06e6
    Irreducible loop 1 1 1 1 6 108 23746 1.06e6
    Commutative loop 1 1 1 2 1 8 17 2265
    Irreducible cmt loop 1 1 1 1 1 7 17 2263

    They are becoming more manageable.

  6. Top | #16
    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 will add the associative property.


    Algebra 1 2 3 4 5 6 7 8 9
    Semigroup 1 5 24 188 1915 28634 1.67e6 3.68e9 1.06e14
    Irreducible smg 1 5 24 173 1915 28514 1.67e6 3.68e9 1.06e14
    Commutative smg 1 3 12 58 325 2143 17291 221805 1.15e7
    Irreducible cmt smg 1 3 12 52 325 2107 17291 221639 1.15e7
    Monoid - smg w/ identity 1 2 7 35 228 2237 31559 1.67e6
    Irreducible mnd 1 2 7 32 228 2223 31559 1.67e6
    Commutative monoid 1 2 5 19 78 421 2637
    Irreducible cmt mnd 1 2 5 16 78 411 2637
    Group - mnd w/ inverses 1 1 1 2 1 2 1 5 2
    Irreducible group 1 1 1 1 1 1 1 3 1
    Commutative group 1 1 1 2 1 1 1 3 2
    Irreducible cmt group 1 1 1 1 1 0 1 1 1

    So the number gets very small when one adds a lot of constraints.

  7. Top | #17
    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 On-Line Encyclopedia of Integer Sequences® (OEIS®) was a valuable resource as I collected these numbers of algebraic entities. It is good for guessing what sequence one might have. Enter the sequence values that one already knows and its software will find which sequences match it.

    For instance, 1,1,2,3,5,8,13 gives the Fibonacci sequence as its first hit. Its second hit is the number of transitive rooted trees, a sequence that deviates from the Fibonacci sequence in its 12th member: 88 instead of 89.

    On-Line Encyclopedia of Integer Sequences
    AMS :: The On-line Encyclopedia of Integer Sequences, or, Confessions of a Sequence Addict: An MAA Invited Address by Neil J. A. Sloane
    The On-Line Encyclopedia of Integer Sequences by Neil J.A. Sloane
    Its creator: Neil Sloane

    "Founded in 1964 by N.J.A. Sloane"

    That was long before the Internet, of course, and back then Packet switching, how the Internet works, was being researched.

    Neil Sloane was a graduate student back then, and he started collecting integer sequences to support his work on combinatorics. He first stored them on punched cards, and only later on more accessible digital media. He wrote two books of collections of sequences, "A Handbook of Integer Sequences" in 1973 with 2,372 sequences and "The Encyclopedia of Integer Sequences" in 1995 with 5,488 sequences.

    Publishing sequences in book form was awkward, and NS decided to go online, first with an e-mail service in 1994, then with a website in 1996. The site was first hosted by AT&T, and later on outside hosting. The site is now managed by The OEIS Foundation Inc founded in 2009. It now has more than 300,000 entries.

  8. Top | #18
    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 OEIS hosts several sequences that are not strictly speaking one-dimensional sequences of integers.

    For instance, 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1 gives Pascal's triangle, stored as a sequence of rows: 1 then 1,1 then 1,2,1 then 1,3,3,1 then 1,4,6,4,1 then ...

    It also stores sequences of digits of irrational numbers, both in decimal and in binary, and it stores some continued-fraction expansions. It stores some sequences of fractions as separate sequences of numerators and denominators.


    I tried putting into OEIS my counts of irreducible groupoids and related algebraic entities, but I had no success. Even the count of irreducible abelian groups failed. For the record, that count is 1 for a prime power and 0 otherwise.

  9. Top | #19
    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 mentioned "idempotent" in a previous post. An idempotent element is one whose square equals itself: for x, x*x = x.

    This is also true of any power of x in the system, even if it is not associative.

    The associative property: for every a,b,c: (a*b)*c = a*(b*c)

    A weaker version is the alternating property, a two-variable version of associativity. For every a,b:
    (a*a)*b = a*(a*b)
    (a*b)*a = a*(b*a)
    (b*a)*a = b*(a*a)

    Even weaker is power-associativity. When calculating some power x^n, it does not matter how one groups the x's in it.
    (x*x)*x = x*(x*x)
    ((x*x)*x)*x = (x*(x*x))*x = (x*x)*(x*x) = x*((x*x)*x) = x*(x*(x*x))
    etc.

    Power-associativity < alternativity < associativity


    In ordinary arithmetic, 0 is idempotent in addition, 1 is idempotent in multiplication. A group has only one idempotent element, its identity.

    In Boolean algebra, "and" and "or" have both "true" and "false" idempotent.

    Fuzzy logic violates idempotence, except for the "Zadeh norm": a and b = min(a,b), a or b = max(a,b)

  10. Top | #20
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    A semigroup with every element idempotent is called a band.
    If it is commutative, then it is called a semilattice.

    Number of each kind of algebra with all-idempotent elements. The second list of numbers is for irreducible ones.

    Idempotent groupoids - A038018 - OEIS - general numbers of idempotents: A038021 - OEIS

    1, 1, 3, 138, 700688, 794734575200, 307047114275109035760, 61899500454067972015948863454485, 9279375475116928325576506574232168143663715776
    1, 1, 3, 138, 700682, ...

    Asymptotic to n^(n*(n-1)) / n!

    Idempotent commutative groupoids - A030257 - OEIS - general numbers of idempotents: A038021 - OEIS

    1, 1, 1, 7, 192, 82355, 653502972, 110826042515867, 479732982053513924168, 62082231641825701423422054735, 275573192431752191557427399293883120600, 47363301285150007842253190185182901101879369430257
    1, 1, 1, 7, 191, ...

    Asymptotic to n^((n-1)*(n-2)/2) / n!

    For order 2, these groupoids are idempotent:

    11.12 (equvalent to 12.22), 11.22 12.12

    All of them are semigroups and the first one is a commutative monoid.

    For order 3, these commutative groupoids are idempotent:

    111.121.113 _ 111.122.123 _ 112.121.213 _ 112.122.223 _ 112.123.233 _ 113.122.323 _ 132.321.213

    Two of them are semigroups: 111.121.113 _ 111.122.123 and the second one is a monoid.

    -

    Idempotent semigroups - general numbers of idempotents: A058108 - OEIS

    1, 3, 10, 46, 251, 1682, 13213, 119826, 1228712
    1, 3, 10, 40, 251, 1652, ...

    Idempotent commutative semigroups - A006966 - OEIS - general numbers of idempotents: A058116 - OEIS

    1, 1, 2, 5, 15, 53, 222, 1078, 5994, 37622, 262776, 2018305, 16873364, 152233518, 1471613387, 15150569446, 165269824761, 1901910625578, 23003059864006
    1, 1, 2, 4, 15, 51, 222, 1073, ...

    Idempotent monoids - general numbers of idempotents: A058137 - OEIS

    1, 1, 3, 10, 46, 251, 1682
    1, 1, 3, 9, 46, 248, 1682

    Idempotent commutative monoids - A006966 - OEIS - general numbers of idempotents: A058142 - OEIS

    1, 1, 1, 2, 5, 15, 53, 222, 1078, 5994, 37622, 262776, 2018305, 16873364, 152233518, 1471613387, 15150569446, 165269824761, 1901910625578, 23003059864006
    1, 1, 1, 1, 5, 14, 53, 220, 1077, ...

Posting Permissions

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