Semirigidity and the enumeration of nilpotent semigroups of index three

This paper introduces the concept of semirigidity and utilizes orbit counting theory to derive new formulae and improved bounds for enumerating 3-nilpotent semigroups, including their isomorphism and equivalence classes, with computational results provided up to order $n=10$.

The Gist

Imagine you are a master chef trying to count every possible way to arrange ingredients in a giant, chaotic kitchen. In the world of mathematics, these "ingredients" are numbers, and the "arrangements" are called semigroups. A semigroup is just a set of things where you can combine any two of them to get a third thing (like adding numbers), but the rules are a bit looser than in standard arithmetic.

The problem is: there are so many ways to arrange these ingredients that counting them all is impossible for large numbers. It's like trying to count every possible sentence ever written in the English language.

However, mathematicians have discovered a fascinating secret: Almost all of these mathematical structures are actually very boring and simple. They belong to a specific category called "3-nilpotent semigroups."

Think of these as "junk" semigroups. If you keep combining ingredients in them, the result eventually turns into "zero" (nothingness) after just three steps. They are featureless, like a pile of sand where every grain looks the same. Despite being "boring," they make up the vast majority of all possible semigroups.

The Big Challenge: Counting the Piles

The authors of this paper, Igor, D.G., and James, wanted to answer a simple question: "How many of these 'junk' piles exist?"

They looked at this in three different ways, like looking at a pile of sand from different angles:

1. Up to Identity: Counting every single specific arrangement, even if two piles look exactly the same but are labeled differently (like counting two identical red Lego towers as two separate things).
2. Up to Isomorphism: Counting the shapes of the piles. If you can rename the ingredients to make one pile look exactly like another, they count as just one.
3. Up to Equivalence: Counting the piles even if you look at them in a mirror (anti-isomorphic). If a pile is the mirror image of another, they count as the same.

The "Rigid" vs. "Flexible" Piles

To make the counting easier, the authors introduced a concept called Rigidity.

• Rigid Piles: Imagine a sculpture made of clay that is frozen solid. If you try to rotate it or swap parts, it breaks or looks different. These are "rigid." They have no symmetry.
• Flexible Piles: Imagine a spinning top or a snowflake. You can rotate it or flip it, and it looks the same. These are "flexible."

The paper proves that almost all of these 3-nilpotent semigroups are rigid. They are so unique and featureless that they have no symmetry at all. This is a huge help because it means we don't have to worry about the complex math of "flexible" shapes for the vast majority of cases.

The New "Semi-Rigid" Idea

The authors realized that even among the rigid ones, there's a slightly looser category they call "Semi-Rigid."

• Think of a Semi-Rigid pile as a castle where the main tower (the core) is frozen solid, but the little flags on top might wiggle a bit.
• They found that counting these "Semi-Rigid" structures is much easier than counting the perfectly rigid ones, yet it still gives them a very accurate estimate of the total number. It's like estimating the number of people in a stadium by counting the people in the front row and knowing the back rows are almost identical.

The Magic Tool: Orbit Counting

How did they actually do the math? They used a tool from group theory called Orbit Counting (often associated with Burnside's Lemma).

Imagine you have a deck of cards and a friend who shuffles them in specific patterns.

• If you lay out all possible card arrangements, most of them will look different.
• But some arrangements look the same after a shuffle.
• The "Orbit" is the group of all arrangements that can be turned into each other by shuffling.

The authors used this idea to group all the possible semigroups into "orbits." Instead of counting every single one, they counted the orbits. Because almost all semigroups are rigid (they don't shuffle into anything else), the number of orbits is almost exactly the same as the number of rigid semigroups.

The Results: A Mountain of Numbers

The paper provides new formulas to calculate these numbers. They ran these formulas on a computer (using software called GAP) and generated tables of numbers.

• For a small set of 3 items, there are very few arrangements.
• For 10 items, the number explodes into the trillions.

The tables show that their new "Semi-Rigid" estimates are incredibly close to the actual total numbers. It's like having a map that says, "The treasure is in this valley," and being able to say, "And it's definitely within these 100 feet," even though the valley is miles wide.

Why Does This Matter?

You might ask, "Who cares about counting boring piles of sand?"

1. It solves a mystery: For decades, mathematicians suspected that "junk" semigroups were the most common, but they couldn't prove it or count them accurately. This paper provides the best tools we have to do exactly that.
2. It sets a baseline: Since these "junk" semigroups are the most common, knowing how many there are gives us a lower bound for the total number of all semigroups. It's like knowing that 99% of the trees in a forest are pines; if you count the pines, you have a very good idea of the total number of trees.
3. It improves math tools: The methods they developed (using "Semi-Rigidity" and "Orbit Counting") can be applied to other complex counting problems in computer science and cryptography.

In a Nutshell

The authors took a chaotic, impossible-to-count problem (all possible semigroups), realized that 99% of them are boring, featureless "junk," and invented a clever new way to count that junk. By focusing on "Semi-Rigid" structures, they created a formula that gives a near-perfect estimate of the total number, turning a mountain of confusion into a neat, calculable list of numbers.

Technical Summary

Here is a detailed technical summary of the paper "Semirigidity and the Enumeration of Nilpotent Semigroups of Index Three" by Igor Dolinka, D. G. Fitzgerald, and James D. Mitchell.

1. Problem Statement and Context

The paper addresses the enumeration of 3-nilpotent semigroups (semigroups $S$ where $S^3 = 0$ but $S^2 \neq 0$).

• Prevalence: It is widely believed (though not rigorously proven for all $n$) that "almost all" finite semigroups of order $n$ are 3-nilpotent. Consequently, counting these structures provides a crucial lower bound for the total number of finite semigroups.
• The Challenge: While formulas exist for counting 3-nilpotent semigroups on a fixed set (up to identity), counting them up to isomorphism (structural equivalence) or equivalence (isomorphism or anti-isomorphism) is significantly harder.
• Existing Methods: Previous approaches relied on exhaustive testing or complex inclusion-exclusion formulas (e.g., Distler and Mitchell). The paper aims to provide new, computationally tractable formulas and improved bounds for these counts.
• Rigidity: It is known that "almost all" 3-nilpotent semigroups are rigid (having only the identity automorphism). The authors leverage this by introducing a weaker property, semirigidity, to derive tighter bounds.

2. Methodology and Theoretical Framework

2.1 Structural Representation

The authors utilize a standard construction for 3-nilpotent semigroups:

• Any such semigroup $S$ of order $n$ can be represented as $N(X, K, m)$, where:
  • $X$ is the unique minimal generating set ($|X|=r$).
  • $K$ is the set of non-zero products ($|K|=k$).
  • $0$ is the zero element.
  • $n = r + k + 1$.
  • $m: X \times X \to K \cup \{0\}$ is a surjective map (onto $K$ or $K \cup \{0\}$).
• This map $m$ induces a partial partition $P$ of $X \times X$ into $k$ non-empty blocks (plus a zero block). The semigroup is determined by this partition.

2.2 Group Actions and Orbit Counting

To count isomorphism classes, the authors analyze the action of the symmetric group $S_r$ (permutations of the generators $X$) on the set of partial partitions of $X \times X$.

• c-action: The action of $S_r$ on $X \times X$ defined by $(x, y)^\pi = (x^\pi, y^\pi)$.
• p-action: The induced action on the set of partial partitions.
• Isomorphism: Two semigroups are isomorphic if and only if their corresponding partitions lie in the same orbit under the p-action.
• Burnside's Lemma: The number of orbits (isomorphism classes) is the average number of fixed points of the group elements.

2.3 Semirigidity

The authors introduce semirigidity as a generalization of rigidity:

• A semigroup is rigid if its only automorphism is the identity.
• A semigroup is semirigid if every automorphism fixes every element of $S^2$ (the set of products).
• In terms of partitions, a partition $P$ is semirigid if any permutation $\pi$ fixing the partition ($P^\pi = P$) must fix each block of $P$ individually (i.e., $P_i^\pi = P_i$).
• Significance: Since almost all 3-nilpotent semigroups are rigid, and rigid implies semirigid, counting semirigid classes provides an asymptotically accurate lower bound for the total number of isomorphism classes.

2.4 Combinatorial Tools

• Friezes: The authors analyze partitions fixed by a permutation $\pi$ by decomposing the c-cycles of $\pi$ on $X \times X$. They define "friezes" as specific partitions stabilized by $\pi$ constructed from cross-sections of cycle sets.
• Stirling Numbers: The counts are expressed using Stirling numbers of the second kind, denoted $\left\{ \begin{smallmatrix} n \\ k \end{smallmatrix} \right\}$.
• Cycle Types: Calculations are grouped by the conjugacy classes (cycle types $\lambda$) of permutations in $S_r$.

3. Key Contributions and Results

3.1 New Formulas for Enumeration

The paper derives explicit formulas and bounds for several counting problems:

1. Up to Identity: A sum of Stirling numbers expressing the total number of 3-nilpotent operations on a fixed set.
2. Up to Isomorphism:
   • An upper bound for the number of semirigid isomorphism classes (Theorem 6.5).
   • This bound is shown to be a lower bound for the total number of isomorphism classes.
   • The formula involves summing over integer partitions $\lambda \vdash r$, weighted by the number of c-cycles $\beta(\lambda)$ and the size of the conjugacy class.
3. Commutative Classes:
   • Adapted formulas for commutative semigroups (where the partition must be symmetric).
   • Introduces $\gamma(\lambda)$, the count of symmetric cycles, to replace $\beta(\lambda)$ in the main formula (Theorem 7.2).
4. Equivalence Classes (Isomorphism or Anti-isomorphism):
   • Uses the "twist" map $\tau$ (swapping $x$ and $y$) to define anti-isomorphism.
   • Applies a generalized Burnside lemma to count orbits under the group generated by $S_r$ and $\tau$.
   • Derives bounds for self-dual classes (Theorem 8.8) and total equivalence classes (Theorem 8.9).

3.2 Computational Results

The authors implemented these formulas in GAP (Groups, Algorithms, Programming) and provided tables of values up to $n=10$.

• Accuracy: For small $n$ (e.g., $n=4, 5, 6$), the computed bounds match or are extremely close to the exact counts derived from exhaustive databases (Smallsemi).
• Scalability: The method is computationally feasible for $n$ significantly larger than 10, unlike exhaustive testing which becomes impossible.
• Example Data:
  • For $n=10$, the number of 3-nilpotent semigroups up to isomorphism is approximately $2.48 \times 10^{25}$.
  • The number of equivalence classes is approximately $1.24 \times 10^{25}$.

4. Significance and Impact

• Refined Bounds: The introduction of semirigidity allows for a more precise estimation of the number of isomorphism classes than previous methods, which often relied on crude lower bounds or exhaustive enumeration.
• Theoretical Insight: The paper deepens the understanding of the structural properties of 3-nilpotent semigroups, specifically linking the combinatorial properties of partitions (friezes, cycle structures) to algebraic properties (automorphisms, duality).
• Generalization: The methodology is not limited to general 3-nilpotent semigroups; it is successfully adapted to commutative and self-dual cases, demonstrating the robustness of the orbit-counting approach.
• Practical Utility: By providing formulas that depend on cycle types rather than exhaustive listing, the paper offers a pathway to estimate the growth of semigroup counts for large $n$, supporting the conjecture that 3-nilpotent semigroups dominate the landscape of finite semigroups.

Conclusion

Dolinka, Fitzgerald, and Mitchell successfully bridge combinatorial group theory and semigroup enumeration. By leveraging the concept of semirigidity and applying advanced orbit-counting techniques to partial partitions, they provide the most accurate and computationally efficient formulas to date for counting 3-nilpotent semigroups up to isomorphism and equivalence, effectively solving a long-standing enumeration problem for this specific variety.