• Welcome to the new Internet Infidels Discussion Board, formerly Talk Freethought.

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

My father Mario Petrich worked on semigroups, and I recently got copies of two of his books on them: "Introduction to Semigroups" and "Completely Regular Semigroups".

Regular semigroup: every element a has at least one pseudoinverse x: a*x*a = a

Equivalent to having at least one inverse b: a*b*a = a and b*a*b = b

Each inverse is a pseudoinverse, but does the existence of a pseudoinverse imply the existence of an inverse?

Compose a putative inverse from a pseudoinverse: c = x*a*x

c*a*c = x*a*x*a*x*a*x = x*a*x*a*x = x*a*x = c

a*c*a = a*x*a*x*a = a*x*a = a

So c is an inverse and not just a pseudoinverse.

A completely regular semigroup has the property that every element commutes with every one of its pseudoinverses: a*x = x*a

Also, every element is in a subgroup of that semigroup. Not just a subsemigroup, a subgroup.

In an inverse semigroup, every element has a unique inverse.
 
Last edited:
Regular semigroups have been studied a lot, and Green's relations were devised for studying them.

Let's consider a case of a regular semigroup S where every element has every element as its pseudoinverse.

There is a remarkable construction of the elements of S. Identify each one with a direct product of the products of a with S:

a ~ (a*S, S*a)

A product a*b is thus (a*S*b*S, S*a*S*b). For a*S*b*S, consider S*b*S. One can select any x from both S's, making x*b*x. This is x, and the set of them is S. Thus, the product is (a*S, S*b). Continuing, one can show that a*b*a = a.

That is why this kind of semigroup is called a "rectangular semigroup", because every element of one can be expressed in form (x,y) where x and y are from sets X and Y, and where product a*b = (xa,ya)*(xb,yb) = (xa,yb)

A special case of rectangular semigroups is what happens if one of the sets in it has only one element. This produces "left singular semigroups" and right ones: a*b = a and a*b = b. All left zero and right identity, and all right zero and left identity.

Rectangular semigroups in general are a direct product of a left-singular semigroup and a right-singular one.
 
Back to lattices and semilattices. Using un and it for set union and intersection, and mt and jn for lattice meet and join, and using the earlier examples (sets, numbers, boolean):

A mt B = A it B = min(A,B) = A and B
A jn B = A un B = max(A,B) = A or B

Meet and join are commutative, associative, and idempotent, and they are distributive over each other:

A mt (B jn C) = (A jn C) mt (B jn C)
A jn (B mt C) = (A mt C) jn (B mt C)

The infimum or overall minimum is meet applied to all the lattice-set elements. Likewise, the supremum over overall maximum is join applied to all the lattice-set elements. Both of them will exist for a finite lattice, but for an infinite lattice, one or both of them may be absent.

The infimum, if it exists, is the zero of meet and the identity of join. Likewise, the supremum, if it exists, is the zero of join and the identity of meet.


In many cases, one can flip a lattice's elements to make the meet a join and the join a meet. Examples:
  • Boolean: the negation operator: x -> not x
  • Finite sets: find a set M that contains all the elements of the sets in the lattice. Then do x -> M - x (complement operation: remove elements of x from M)
  • Numbers: negate them: x -> -x
Not surprisingly, repeating the flipping returns the original algebra: it is an involution, like number negation or boolean negation or set complementation.
 
What I described was  Distributive lattice - lattices where meet and join are distributive over each other.

These have the property that if (a mt x) = (b mt x) and (a jn x) = (b jn x) for all x in the lattice, then a = b.

As I suspected, every one of them is isomorphic to a lattices of subsets of some set that is closed over union and intersection.

In general lattices, a property of meet and join is absorption:
a jn (a mt b) = a
a mt (a jn b) = a
for all a, b. Idempotence follows from this property.  Lattice (order)

Related to lattices are posets - partially ordered sets - sets with an order relation <= (or >=)
a <= a -- reflexive
a <= b and b <= a implies a = b -- antisymmetric
a <= b and b <= c implies a <= c -- transitive

Strict partial ordering means having an order relation < (or >) -- <= (or >=) without equality
not a < a -- irreflexive
a < b implies not b < a -- asymmetric
a < b and b < c implies a < c -- transitive

Partial ordering from lattices:
a <= b for a mt b = a and for a jn b = b
Some pairs of lattice members may have undefined ordering.

In general, for lattices, the distributive property satisfies the order property:
a mt (b jn c) >= (a mt b) jn (a mt c)
a jn (b mt c) <= (a jn b) mt (a jn c)

 Modular lattice has
a <= b implies a jn (x mt b) = (a jn x) mt b for all x in the lattice.
Every distributive lattice is modular, but some modular lattices are not distributive. Judging from counts over at OEIS, the first non-distributive modular lattice is at order 5, as is the first non-modular lattice.
 
How many lattices?

First four sizes of distributive lattices, expressed as set lattices:
  1. {} -- number, all-subset
  2. {}, {a} -- number, all-subset -- linear
  3. {}, {a}, {a,b} -- number -- linear
  4. Two:
    • {}, {a}, {a,b}, {a,b,c} -- number -- linear
    • {}, {a}, {b}, {a,b} -- all-subset, boolean -- diamond
  5. Three distributive ones:
    • {}, {a}, {a,b}, {a,b,c}, {a,b,c,d} -- linear
    • {}, {a}, {a,b}, {a,c}, {a,b,c} -- diamond-linear
    • {}, {a}, {b}, {a,b}, {a,b,c} -- linear-diamond
All of them are self-dual under flipping, except for the last two, which are flipped versions of each other. Linear lattices in general are always self-dual, as are all-subset ones.
 
More on lattices and semilattices. First some more on semilattices.

Define relation a <= b for a*b = a. It is much like <= for numbers: a <= a ... a <= b and b <= a give a = b ... a <= b and b <= c give a <= c.

What about a*b = c where c is neither a nor b?

Consider an element x where x <= a and x <= b:
a*b*x = c*x

The lhs is a*b*x = a*b*x*x = a*x*b*x = x*x = x. So c*x = x meaning that x <= c.

Thus, c satisfies c <= a and c <= b and there is no c' such that c' also does so, but with c < c' (c <= c' but c != c').

For discrete semilattice set elements, each element will have some closest other elements, closest being those that satisfy a < b with no x such that a < x and x < b (a < x < b).

Thus, one can construct a semilattice's operation table from its element-element relations, what may be called the semilattice graph, and for the smaller ones, one can make some nice diagrams.


This makes possible a strategy for constructing semilattices. Instead of going through all the possible operation tables, one can construct all the semilattice graphs with some number of nodes. As one might expect, this computation is much less time-consuming.
 
To get lattices, one needs monoid semilattices, and one can make monoid ones from non-monoid ones by adjoining or adding on an identity. Once one has a monoid semilattice, one can make the lattice's other semilattice by reversing the directions of the edges.

The paper lawless.pdf notes an additional lattice: the positive integers, with meet = greatest common divisor and join = least common multiple.

For modular lattices, the modular law:
(x mt y) jn (y mt z) = y mt ((x mt y) jn z)
(x jn y) mt (y jn z) = y jn ((x jn y) mt z)


If a lattice contains N5: 1 - 2 - 5, 1 - 3 - 4 - 5, it is not modular, and thus it is not distributive.
If a lattice contains M3: 1 - 2 - 5, 1 - 3 - 5, 1 - 4 - 5, it is not distributive.

Modular lattices:
  • Subspaces of a vector space
  • Ideals of a ring
  • Normal subgroups of a group
Distributive lattices: numbers (min, max), positive integers (gcd, lcm), subsets of some set (intersection, union), boolean algebra (and, or)

Lowest-order distributive lattices: one: 1 _ two: 1 - 2 _ three: 1 - 2 - 3 _ four: 1 - 2 - 3 - 4 _ 1 - 2 - 4, 1 - 3 - 4 _ five: 1 - 2 - 3 - 4 - 5 _ 1 - 2 - 4, 1 - 3 - 4, 4 - 5 _ 1 - 2, 2 - 3 - 5, 2 - 4 - 5

JipsenLawlessModularLattices20130905.pdf - notes additional kinds of lattices, like "semimodular" ones, and "vertically (in)decomposable" ones. A lattice is vertically decomposable if it can be split into two or more lattices in sequence, and vertically indecomposable otherwise.


Being semimodular is more complicated. First some terminology. If a < b but there is no c satisfying a < c and c < b, then b "covers" a -- there is nothing in between in the a - b sequence. Rather odd term, it must be conceded.

Semimodular: if (a mt b) is covered by a, then a is covered by (a jn b)

A related condition:
Lower semimodular: if a is covered by (a jn b), then (a mt b) is covered by a

For finite-"length" lattices, being modular is equivalent to both conditions holding. Where "length" is the maximum length of all top-to-bottom sequences of elements.
 
Such details aside, it's satisfying that one gets such a simple solution for this abstract-algebra entity - a solution that can be illustrated with diagrams very easily.

Thus putting the problem in the domain of  Graph theory the mathematics of abstract networks, nodes or vertices connected with edge lines. Edges may be directed or undirected.

 Seven Bridges of Königsberg is a classic problem: those bridges connect the two banks of a river and two islands in that river. Is it possible to walk over every bridge exactly once?

The landmasses are nodes and the bridges are edges.

 Four color theorem - how many colors does one need for a map where every region has only different-colored neighboring regions?

The regions are nodes and the region boundaries are node-to-node edges.
 
Back to semilattices and lattices. I'll now prove some of the theorems that I'd stated earlier.

Semilattices first. Consider a*b = c. Now consider some x that satisfies x*a = x and x*b = x (x <= a, x <= b).

Then, x*a*b = x*c with the lhs becoming x*a*b = x*x*a*b = x*a*x*b = x*x = x. Combining with the rhs, x*c = x (x <= c). So c is the "largest" element where c <= a and c <= b are both defined: a*c = c and b*c = c.

Turning to lattices, the absorption property has an interesting consequence. Start with it in one direction:
a jn (a mt b) = a

Choose a and b such that a mt b = b. Then a jn b = a, and vice versa. Thus, the meet and the join orderings are in opposite directions, and one easily shows that absoprtion goes in the other direction:
a mt (a jn b) = a

Considering in absorption the case of a mt b in general, a mt b is the largest c with c <= a and c <= b. This means that a jn c is (whichever is >= the other) or a. Likewise for the dual absorption relation.

http://www.math.hawaii.edu/~jb/math618/os9uh.pdf - contains proofs of (presence of N5) <-> (non-modular) and (presence of M3) <-> (non-distributive)

I checked on the counts at OEIS, and here are the sizes where different kinds of lattices diverge in number:
  • Plain but not semimodular: 5
  • Semimodular but not modular: 7
  • Modular but not distributive: 5
There is one lattice at each departure size that satisfies the departure property.
 
If a graph can be embedded in a plane without any edges crossing each other, then the graph is planar:  Planar graph

A planar lattice has a planar graph of its neighboring elements. where elements are neighbors if they have an order relation with no intermediate elements.

How many planar distributive ones: A343161 - OEIS
The first non-planar distributive one appears at size 8.
There is a surprisingly simple formula for the total number (ntot) in terms of the number of v.i. ones (nvid):

ntot(n) = sum over k = 1 to (n-1) of nvid(k)*ntot(n-k)
nvid(1) = ntot(1) = 1

The vertically-indecomposable planar distributive lattice diagrams have a surprisingly simple appearance. They are composed of the size-4 "diamond" graphs that are connected at their edges, forming sheets.
 
Looking at counts of lattices, I find that the number of lattices in general is roughly exp(0.4*n3/2), with most of them being vertically indecomposable (VI) ones except for the smallest ones. Semimodular ones increase at a bit more than exponential, and are about half-VI except for the small ones. Modular ones increase as (2.1)n and distributive ones as (1.8)n. However, the VI fractions of them decline, with modular ones approaching 0.18 and with distributive ones being roughly 0.2/log(n).

Most distributive lattices are planar, something also true of VI ones.
 
Now some more on some kinds of lattices. Lattices of subsets of some set, with meet = intersection and join = union, are distributive, as can easily be shown. The subsets do not have to be all of the subsets of the overall set.

One can also construct lattices of subgroups, where meet = intersection subgroup and join = subgroup generated by union of the input subgroups. The join requires generation because one can easily find counterexamples to the union of subgroups being a group. Like:

For Z2*Z2, the elements are 00, 01, 10, 11. Consider subgroups {00,10}, {00,01}. Their intersection is the identity group, and their union is {00,10,01} which is not a group from lack of closure. Doing closure on this set gives {00, 10, 01, 11} .

A lattice of "quasinormal subgroups" will be modular, where  Quasinormal subgroup is a subgroup that commutes with all the other subgroups. For all a in A and b in B, there is some a' in A and b' in B such that a*b = b'*a'.

Every quasinormal subgroup is a  Normal subgroup a subgroup A where for all a in A and g in the original group, g*a*g-1 is also in A. The converse is not necessary true, however.

One can also form lattices of subalgebras of other kinds of algebras, and some of those are also modular.
 
lpetrich said:
Now some more on some kinds of lattices. Lattices of subsets of some set, with meet = intersection and join = union, are distributive, as can easily be shown. The subsets do not have to be all of the subsets of the overall set.

One can also construct lattices of subgroups, where meet = intersection subgroup and join = subgroup generated by union of the input subgroups. The join requires generation because one can easily find counterexamples to the union of subgroups being a group. Like:

For Z2*Z2, the elements are 00, 01, 10, 11. Consider subgroups {00,10}, {00,01}. Their intersection is the identity group, and their union is {00,10,01} which is not a group from lack of closure. Doing closure on this set gives {00, 10, 01, 11} .

A lattice of "quasinormal subgroups" will be modular, where  Quasinormal subgroup is a subgroup that commutes with all the other subgroups. For all a in A and b in B, there is some a' in A and b' in B such that a*b = b'*a'.

Every quasinormal subgroup is a  Normal subgroup a subgroup A where for all a in A and g in the original group, g*a*g-1 is also in A. The converse is not necessary true, however.

One can also form lattices of subalgebras of other kinds of algebras, and some of those are also modular.
Click to expand...
So, question here: how deeply have you penetrated Langland's Program/philosophy, and the idea of automorphic forms?

I ask this because it's my understanding in Langland's Program that there is an invariant description of such modular lattices, and they arent really different forms but are homologous?
 
A nearest-neighbor diagram of a lattice is sometimes called a  Hasse diagram

For a  Modular lattice the diagram is a  Modular graph

For the graph being made undirected and for every three nodes x, y, z, there is a median node m(x,y,z) that belongs to every shortest path between each pair of those nodes.

A modular graph has no odd-sized cycles and is a  Bipartite graph -- all the nodes are in two sets with the edges connecting a node in one set with a node in the other. This can be interpreted as graph coloring with two colors and no neighbors having the same color. It is easy to prove that a bipartite graph has no odd-sized cycles.

For a modular lattice, the elements can be divided up into tiers that are numbered in sequence, with connections going between even-numbered and odd-numbered tiers.

The modular-lattice condition is, for elements / graph nodes a and b, (a mt b) ngbr a <-> b ngbr (a jn b) where semimodular has the weaker condition -> (implies) and upper semimodular <- (reverse), and where "ngbr" means "is a neighbor of" in the graph, connected by an edge. This is a condition on cycles in the lattice's graph. The smallest cycles are tilted square ones, like for the subset lattice {}, {a}, {b}, {a,b}.


For a  Distributive lattice the diagram is a  Median graph where each three nodes' median node is unique.

In a distributive lattice, one can find the medians in this way:
m(a,b,c) = (a mt b) jn (a mt c) jn (b mt c) = (a jn b) mt (a jn c) mt (b jn c)
where the equality holds for all elements only for distributive lattices.

Also, a mt c = b mt c and a jn c = b jn c imply a = b

Another route to the median involves distances. d(a,b) = shortest distance between a and b, the smallest number of edges between them on a path between them. The interval I(a,b) is all x such that d(a,x) + d(x,b) = d(a,b) -- more or less the nodes in between a and b. One can easily show that I(a,b) contains both a and b. For a median graph, the intersection of I(a,b), I(a,c), and I(b,c) is a single node, the median node for a, b, c.


To see what intervals and medians look like, I worked them out for the number lattice and the all-subsets lattice.

For the number lattice, meet = min, join = max. I(a,b) = x that satisfies number inequality a <= x <= b, m(a,b,c) = number median of a, b, c

For the lattice of all subsets of some set, for an interval I(A1,A2), we consider A1 = S1 un S12 and A2 = S2 un S12 where S1, S2, S12 are disjoint. Then the interval is all sets with some elements from S1, some from S2, and all from S3. That is,

The median of sets A1, A2, A3 is the set with elements in at least two of these sets. Let A1 = S1 un S12 un S13 un S123, A2 = S2 un S12 un S23 un S123, A3 = S3 un S13 un S23 un S123. Then the median is S12 un S13 un S23 un S123.
 
Jarhyn said:
So, question here: how deeply have you penetrated Langland's Program/philosophy, and the idea of automorphic forms?

I ask this because it's my understanding in Langland's Program that there is an invariant description of such modular lattices, and they arent really different forms but are homologous?
Click to expand...
 Langlands program ? I'm not familiar with it.
 
lpetrich said:
Jarhyn said:
So, question here: how deeply have you penetrated Langland's Program/philosophy, and the idea of automorphic forms?

I ask this because it's my understanding in Langland's Program that there is an invariant description of such modular lattices, and they arent really different forms but are homologous?
Click to expand...
 Langlands program ? I'm not familiar with it.
Click to expand...
It is a system of discussing the homology of groups. And yes, that Langland's Program.

Essentially it takes the concepts you are discussing as being "essentially the same lattice with the same structure, but different token assignments and seemingly different organizational representation" and making a singular description of all of those things: an "invariant" form based on a "foundational lemma".

I have been studying it since I badly embarrassed myself in number theory, because a great deal of Langland's Conjectures have been proven, to the point where set theory and number theory and all these different concepts of "groups" and "rings" and "lattices" and "subgroups" are being revealed in many ways to be the same fundamental concepts as "automorphic forms" of whatever field.

At least this is my understanding.

I've been doing my study on it "wikipedia rabbit hole" style where any term that is undefined as I read through the Langland's Program page gets dived through.

Admittedly I've got maybe 6 more MONTHS of reading before I'll really understand it to the point of even being able to read most of this thread beyond the basic ideas of how fields have operations groups applied to them.

Even so, as a programmer, I came to the understanding that this is all math I know, but I just don't know it in these terms (the idea of function and types, of graph structure connections of counting groups, different models of walking across a series, etc).

My own ultimate goal with is to demonstrate that discussion of ethics, "will", "freedom", generally thought to "relative and subjective", are in fact discussions of such automorphic forms too.

I've got maybe 5-10 more years of work before I'm done with that.
 
Now for a proof of semilattice ordering. Consider a*b = c in general.
a * (both sides):
a*a*b = a*c
a*b = a*c
c = a*c
Thus,
a*c = c and b*c = c

As I'd shown earlier, if a*x = x and b*x = x, then c*x = x. Thus, c is the closest possible x to a and b. For a lattice, if a mt b = c, then a mt c = c and by absorption, a jn c = a.

I must say that I find it very entrancing that one gets such a nicely visualizable entity. Without commutativity, one does not get such nice results. The terminology:

Groupoid - associative - semigroup - idempotent - band - commutative - semilattice

Bands, however, contain rectangular bands: a*b*a = a -- their elements have an isomorphism with (a*S, S*a) for element set S. Doing the operation on two elements: (a*S, S*a) * (b*S, S*b) = (a*S*b*S, S*a*S*b) = (a*S, S*b). That means that for every number of elements n, there is a rectangular band for each factorization into two factors. That makes the number of size-n rb's equal to d(n), the number of divisors of n, counting flipped-table rb's separately. If one counts them together, then the number is ceiling(d(n)/2).

d(n) - [url=https://oeis.org/A000005]A000005 - OEIS[/url] "d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n."
 
A000005 - OEIS "d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n."

I found an article on counting inverse semigroups. In these, every element has an inverse, one that is defined in semigroup fashion.

For every element a, the set of pseudoinverses V(a) is all elements b such that a*b*a = a and b*a*b = b.

If V(a) is nonempty, then a is regular, and if V(a) contains only one element, then a has an inverse, that element. If every element is regular, then the semigroup is regular, and if every element has an inverse, then the semigroup is inverse.

In an inverse semigroup, every idempotent is its own inverse, and the idempotents commute with each other, forming a semilattice.

In general, every idempotent in a semigroup is contained by a subgroup of that semigroup, not just a subsemigroup. The largest one for that element, the one not contained in any other, is the maximal subgroup at that element. Conversely, every subgroup of a semigroup contains exactly one idempotent element: the group's identity element.

[1312.7192] Enumeration of finite inverse semigroups uses known groups and known semilattices to find inverse semigroups.

For finding the semilattices,
Counting Finite Lattices | SpringerLink
and
(PDF) Counting Finite Lattices
 
I found this in arxiv: [2006.01628] Primer on inverse semigroups I

A semigroup element a has an inverse b if a*b*a = a and b*a*b = b. An element may have more than one inverse, making it "regular", and every element being regular makes a semigroup regular. An element may have more than one inverse. But if every element has only one inverse, then the semigroup is inverse, and b = a-1 and a = b-1

Proof that a*b and b*a are idempotent. (a*b)*(a*b) = a*(b*a*b) = a*b or (a*b*a)*b = a*b

Every idempotent has itself as an inverse: e*e*e = e*e = e.

If an inverse semigroup has only one idempotent, then it is a group. Call that idempotent e. Then, a*b = b*a = e, because e is the only idempotent. Multiply on the left and right by a:

a*b*a = a = a*(b*a) = a*e = (a*b)*a = e*a

Thus, e is the identity of this inverse semigroup, and this algebra thus satisfies the group axioms.
 
S is an inverse semigroup <-> S is a regular semigroup and its idempotents E(S) commute with each other, making E(S) a semilattice.

I like the proof of it.

Going backward, if u and v are inverses of a, then for commuting idempotents, u = v. Proof:

u = u*a*u = u*(a*v*a)*u = (u*a)*(v*a)*u = (v*a)*(u*a)*u = v*a*(u*a*u) = v*a*u = (v*a*v)*a*u = v*(a*v)*(a*u) = v*(a*u)*(a*v) =v*(a*u*a)*v = v*a*v = v

Going forward, consider idempotents e and f, and x = (e*f)-1. The element y = f*x*e is an idempotent inverse of e*f. Proof:

y is idempotent: y*y = (f*x*e)*(f*x*e) = f*(x*(e*f)*x)*e = f*x*e

y is an inverse of (e*f): y*(e*f)*y = f*x*(e*e)*(f*f)*x*e = f*(x*(e*f)*x)*e = f*x*e = y and (e*f)*y*(e*f) = e*(f*f)*x*(e*e)*f = (e*f)*x*(e*f) = (e*f)

But in an inverse semigroup, inverses are unique, and x = y. But since y is idempotent, x is idempotent, and x = e*f. Thus, inverse-semigroup idempotents are closed under multiplication.

The reverse order, f*e, is also idempotent, and (e*f)*(f*e)*(e*f) = e*(f*f)*(e*e)*f = (e*f)*(e*f) = e*f meaning that f*e is an inverse of e*f and thus equal to e*f itself. Thus, idempotents commute.
 
You must log in or register to reply here.
Back
Top Bottom