Page 1 of 8 123 ... LastLast
Results 1 to 10 of 80

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

  1. Top | #1
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97

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

    I'd started Abstract Algebra long ago, but I want to post on something more specific: how many abstract-algebra entities there are. I will consider only finite entities, those with finite sets of possible operation arguments. One can easily show that the number of each kind of entity must be finite, because the number of possible operation tables without constraints is an upper limit on it.

    For a unary operation and order (set size) n, that upper limit is n^n: 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, ...

    For a binary operation and order n, that upper limit is n^(n^2): 1, 16, 19683, 4294967296, 298023223876953125, ...

    But there is a problem. If one relabels the set members, one will get an equivalent operation, so one has to consider all the possible relabelings.

    I will start with a unary function f to make it easy. The only constraint that I will impose is closure. For a set S, f(S) must be a subset of S. For the empty set, one gets the empty algebra. For a one-element set, one gets the trivial algebra: (f,{a}) has f(a) = a. For two elements, one has 4 possibilities:
    f(a} = a, f(b) = a / f(a} = a, f(b) = b / f(a} = b, f(b) = a / f(a} = b, f(b) = b

    Turning a and b into 1 and 2, I will use this shorthand: 11, 12, 21, 22

    If we impose the constraint that f(S) = S, then the possible tables are 12, 21.

    For finite sets, f(S) = S implies that f is a bijection, meaning that it is invertible. One can define an inverse function g such that f(g(x)) = g(f(x)) = x.

  2. Top | #2
    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 problem, however, one can interchange 1 and 2. When we do that, f(S) in S gives us 3 distinct functions
    {(12), (21), (11 22)}

    while f(S) = S gives us 2 distinct functions
    {(12), (21)}

    Doing this analysis for order 3, I find 7 and 3 distinct functions

    {(123), (231 312), (111 222 333), (132 213 321), (112 131 221 233 313 322), (113 121 122 133 223 323), (211 212 232 311 331 332)}

    {(123), (231 312), (132 213 321)}

    Bijections create permutations, and permutations are well-understood. A permutation is a combination of cyclic permutations, permutations like 1->2, 2->3, 3->1. The possible decompositions:

    1
    11 2
    111 12 3
    1111 112 13 22 4
    11111 1112 113 122 14 23 5

    How many permutations with each set of cycle lengths is n! / product of k^(m(k))*(m(k))! over cycle lengths k with number of cycles with that length m(k)

    n is the total number, equal to sum of k*m(k) for cycle lengths k

    The {m(k) over k} or else {individual k values} form an integer partition of n.

    This has a generating function:
    exp(sum of t(k)/k over cycle lengths k) = 1/n! * ( N({m}) * product of t(k)^(m(k)) over cycle lengths k )

    For the number of partitions of each positive integer n, there is no simple formula, but there is a generating function:

    sum of np(k)*t^k over k = product of 1/(1-t^k) over k

    For more, Partition (number theory), Partition function (number theory)

    The asymptotic formula for np(n) is 1/(4n*sqrt(3)) * exp(pi*sqrt(2n/3))

  3. Top | #3
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    A000041 - OEIS - a(n) is the number of partitions of n (the partition numbers).
    Mathematica built-in: PartitionsP

    Starting from empty: 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525

    Turning to the general case of f(S) in S,
    A001372 - OEIS - Number of mappings (or mapping patterns) from n points to themselves; number of endofunctions.

    Starting from empty: 1, 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, 466199, 1328993, 3799624, 10884049, 31241170, 89814958, 258604642, 745568756, 2152118306, 6218869389, 17988233052, 52078309200, 150899223268, 437571896993, 1269755237948, 3687025544605, 10712682919341, 31143566495273, 90587953109272, 263627037547365


    There exist some formulas for the counts of full case of f(S) in S, but they are rather complicated. The asymptotic behavior is

    c0 * c1^n / sqrt(n)
    where
    c0 = 0.442876769782206479836...
    and
    c1 = 2.9557652856519949747148...
    (Otter's unrooted-tree constant)

    This is much slower than the naive count, with its ignoring of relabelings, but it is still a rapid increase.

  4. Top | #4
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Going further with unary functions over finite sets, let us see what happens when we repeatedly apply it to the elements of S.

    First, if the function repeats itself.
    f(1) = 1
    f(f(1)) = 1
    f(f(f(1))) = 1
    ...
    giving
    1, 1, 1, 1, 1, ...

    Then, if it doesn't.
    f(1) = 2
    Repeating f, we must evaluate f(2)
    If f(2) = 1, then we get
    1, 2, 1, 2, 1, 2, ...
    If f(2) = 2, then we get
    1, 2, 2, 2, 2, 2, ...

    If f(2) = 3, then we must evaluate f(3)
    If f(3) = 1, then we get
    1, 2, 3, 1, 2, 3, ...
    If f(3) = 2, then we get
    1, 2, 3, 2, 3, 2, 3, ...
    If f(3) = 3, then we get
    1, 2, 3, 3, 3, 3, 3, ...

    So we get a limit cycle with other elements approaching it from outward branches. The other elements need not be in the same branch, and they can merge with other elements as they approach the limit cycle. That's what makes the general formula so complicated.

  5. Top | #5
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Some functions are reducible: f(1) = 1, f(2) = 2 -- 12 -- can be divided into two parts, both of them f(a) = a. But f(1) = 2, f(2) = 1 -- 21 -- cannot be divided into two parts, so it is irreducible.

    I've calculated the number of irreducible functions. It also requires a rather complicated formula, but I have implemented it, and I find A002861 - OEIS With the empty set added on,

    1, 1, 2, 4, 9, 20, 51, 125, 329, 862, 2311, 6217, 16949, 46350, 127714, 353272, 981753, 2737539, 7659789, 21492286, 60466130, 170510030, 481867683, 1364424829, 3870373826, 10996890237, 31293083540, 89173833915, 254445242754, 726907585652, 2079012341822, 5952451249381, 17059518771406, 48937697963270

    The fraction of the total slowly declines, and is approximately 1/(c0+c1*log(n)) for c0 ~ -8.5 and c1 ~ 3.8

  6. Top | #6
    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 go from unary to binary functions: binary algebras, groupoids, or magmas.

    A naive count of groupoids of order n is n^(n^2) and that gets very big very fast:

    1, 1, 16, 19683, 4294967296, 298023223876953125

    Taking care of relabelings gives the number of different groupoids: A001329 - OEIS

    1, 1, 10, 3330, 178981952, 2483527537094825, 14325590003318891522275680, 50976900301814584087291487087214170039, 15568208669113794727204250225164346191749883548102 2016

    There is a rather complicated formula for this result, and it is asymptotic to n^(n^2)/n! = (naive number of order-n groupoids) / (number of permutations of n objects)

  7. Top | #7
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    That is a very big field to work in, so let us consider various constraints on groupoids.

    First, being commutative: a*b = b*a for all a, b in the groupoid.

    For commutative ones, the count is A001425 - OEIS

    1, 1, 4, 129, 43968, 254429900, 30468670170912, 91267244789189735259, 8048575431238519331999571800, 24051927835861852500932966021650993560, 2755731922430783367615449408031031255131879354330

    This is also given by a formula, and this has an asymptotic value similar to the general case: n^(n*(n+1)/2) / n! = (naive count) / (permutations of n objects)


    A groupoid has a left identity el if el*a = a for all a, and a right element er if a*er = a. If it has both a left and a right identity, then that two-sided identity is unique: e. There can be more than one left identity if there are no right identities, and likewise for right identities for no left identities.

    For instance, if a*b = a, then every element is a right identity.

    A groupoid has a left zero zl if zl*a = zl for all a, and a right zero zr if a*zr = zr. As with identities, there can be more than one left zero if there are no right zeros, and more than one right zero if there are no left identities. If there are both, then the zero is unique.

    For instance, if a*b = a, then every element is a left zero.

    Groupoids can have both identities and zeros.


    For ones with an identity (or zero), the count is A090601 - OEIS

    1, 2, 45, 43968, 6358196250, 236919104155855296, 3682959509036574988532481464, 35398008251644050232134479709365068115968, 29241529210661172792875915742774732816986602012576 2652311

    Another formula, and asymptotic case n^((n-1)^2+1) / n! = (naive count) / (permutations)

    For commutative ones with an identity (or zero), the count is A038017 - OEIS

    1, 2, 15, 720, 409600, 3920030472, 775775333825891, 3837862827737186253664, 558740081065710564284870598075, 2755731923933734753149997221152548428020, 52099631413533260628548814884449469572205033391248

    Another formula, and asymptotic case n^(n*(n-1)/2+1) / n! = (naive count) / (permutations)

  8. Top | #8
    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 an analogue of division. For all elements a, b, there are unique elements x, y satisfying
    a*x = b, y*a = b

    A groupoid that satisfies this division property is a quasigroup. If it also has an identity, it is a loop.

    The operation table of a quasigroup is a Latin square, a square where every row and column is a permutation of its symbols. For a loop, one row and one column have some canonical order.

    Number of quasigroups: A057991 - OEIS

    1, 1, 1, 5, 35, 1411, 1130531, 12198455835, 2697818331680661, 15224734061438247321497, 2750892211809150446995735533513, 19464657391668924966791023043937578299025

    Number of loops: A057771 - OEIS

    0, 1, 1, 1, 2, 6, 109, 23746, 106228849, 9365022303540, 20890436195945769617, 1478157455158044452849321016

    Number of commutative quasigroups: A057992 - OEIS

    1, 1, 1, 3, 7, 11, 491, 6381

    Number of commutative loops: A089925 - OEIS

    0, 1, 1, 1, 2, 1, 8, 17, 2265, 30583

    Number of Latin squares: A002860 - OEIS

    1, 2, 12, 576, 161280, 812851200, 61479419904000, 108776032459082956800, 5524751496156892842531225600, 9982437658213039871725064756920320000, 776966836171770144107444346734230682311065600000

    Number of reduced (loop-like) Latin squares: A000315 - OEIS

    1, 1, 1, 4, 56, 9408, 16942080, 535281401856, 377597570964258816, 7580721483160132811489280, 5363937773277371298119673540771840

    (full number) = (reduced number) * n! * (n-1)! -- general Latin squares are row and column permutations of reduced ones

    OEIS has no formulas for the counts of any of these entities.

  9. Top | #9
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Quasigroups and loops are not associative in general, so I turn to adding associativity to groupoids:

    (a*b)*c = a*(b*c)

    This gives semigroups. Associativity has the nice property that semigroups can be implemented as matrices, since matrix multiplication is associative. Semigroups are also related to finite state machines, since an input is a function that makes a new internal state from an old one. That is easy to implement in matrix form for a finite set of internal states.

    Number of semigroups: A027851 - OEIS

    1, 1, 5, 24, 188, 1915, 28634, 1627672, 3684030417, 105978177936292

    Number of semigroups where equivalence includes reversing the operator: A001423 - OEIS

    1, 1, 4, 18, 126, 1160, 15973, 836021, 1843120128, 52989400714478, 12418001077381302684

    Number of commutative semigroups: A001426 - OEIS

    1, 1, 3, 12, 58, 325, 2143, 17291, 221805, 11545843, 3518930337

    -

    An inverse semigroup has the property that for all x, there is a unique y that satisfies x = x*y*x. Alternately, x and y are related by x = x*y*x and y = y*x*y

    Number of inverse semigroups: A118099 - OEIS

    1, 3, 8, 24, 76, 284, 1195

    Number of inverse semigroups with reversing the operator: A001428 - OEIS

    1, 2, 5, 16, 52, 208, 911, 4637, 26422, 169163, 1198651, 9324047, 78860687, 719606005, 7035514642

    Number of commutative inverse semigroups: A234843 - OEIS

    1, 2, 5, 16, 51, 201, 877, 4443, 25284, 161698, 1145508, 8910291, 75373563, 687950735, 6727985390

  10. Top | #10
    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 monoid is a semigroup with an identity element.

    Number of monoids: A058129 - OEIS

    0, 1, 2, 7, 35, 228, 2237, 31559, 1668997

    Number of operator-reversal monoids: A058133 - OEIS

    0, 1, 2, 6, 27, 156, 1373, 17730, 858977, 1844075697, 52991253973742

    Number of commutative monoids: A058131 - OEIS

    0, 1, 2, 5, 19, 78, 421, 2637

    An inverse monoid satisfies what an inverse semigroup satisfies.

    Number of inverse monoids: A234844 - OEIS

    1, 2, 4, 11, 27, 89, 310, 1311, 6253, 34325, 212247, 1466180, 11167987, 92889294, 836021796

    Number of commutative inverse monoids: A234845 - OEIS

    1, 2, 4, 11, 27, 87, 300, 1259, 5988, 32812, 202784, 1400541, 10669344, 88761928, 799112310

Posting Permissions

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