pith. sign in

arxiv: 2605.19569 · v1 · pith:WOZYCGGTnew · submitted 2026-05-19 · 🧮 math.GR

Aperiodic Flows on Finite Semigroups II: Smallish Monoids Suffice for Complexity 1

Stuart Margolis , John Rhodes This is my paper

Pith reviewed 2026-05-20 02:13 UTC · model grok-4.3

classification 🧮 math.GR
keywords finite semigroupsKrohn-Rhodes complexityaperiodic flowssmallish monoidsgroup mapping semigroupsembeddings0-simple ideals
0
0 comments X

The pith

Any finite semigroup embeds into the evaluation semigroup of a smallish monoid while preserving aperiodic flows for group mapping cases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an embedding of an arbitrary finite semigroup S into the evaluation semigroup of a smallish monoid S^Ev. It then applies the theory of flows to prove that a group mapping semigroup admits an aperiodic flow precisely when its image under this embedding does. This equivalence transfers the decision problem for Krohn-Rhodes complexity 1 from all finite semigroups to the restricted class of smallish monoids. A smallish monoid is defined by having a unique 0-minimal ideal that is 0-simple together with only three regular J-classes: the group of units and two inside the ideal. The constructive nature of the embedding ensures the flow property is maintained throughout the reduction.

Core claim

The paper establishes a constructive embedding of any finite semigroup S into the evaluation semigroup S^Ev of a smallish monoid, and shows that for group mapping semigroups the existence of an aperiodic flow in S is equivalent to its existence in S^Ev. This equivalence reduces the computation of Krohn-Rhodes complexity 1 to the class of smallish monoids.

What carries the argument

The evaluation semigroup S^Ev of a smallish monoid, which receives the embedding of S and carries the equivalence of aperiodic flows under the flow theory.

If this is right

  • Deciding whether Krohn-Rhodes complexity equals 1 can be limited to smallish monoids.
  • The flow equivalence transfers directly from the original semigroup to its smallish image.
  • The embedding construction applies uniformly to all finite semigroups.
  • Complexity-1 checks become feasible by restricting attention to monoids with exactly three regular J-classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Algorithms for flow detection might now be specialized to the structure of smallish monoids.
  • The reduction could be tested on explicit smallish monoids to see if complexity-1 cases separate cleanly.
  • Similar embedding techniques might simplify decision problems for other semigroup varieties or higher complexity levels.

Load-bearing premise

The embedding of a group mapping semigroup S into S^Ev preserves the presence or absence of aperiodic flows.

What would settle it

Exhibit a single group mapping semigroup S such that S admits an aperiodic flow but S^Ev does not, or such that S^Ev admits one but S does not.

Figures

Figures reproduced from arXiv: 2605.19569 by John Rhodes, Stuart Margolis.

Figure 1
Figure 1. Figure 1: for a picture of the structure matrix. C0 0 · · · 0 · · · 0 0 C0 · · · 0 · · · 0 . . . . . . . . . . . . . . . 0 0 · · · C0 · · · 0 . . . . . . . . . . . . . . . 0 0 · · · 0 · · · C0 A0 A1 · · · Ai · · · An B0 B1 . . . Bi . . . Bn Bi = B0t i , Ai = t −iA0, i = 0, . . . , n [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: Thus the orbit is a disjoint union of L-classes, {Li | i = 0, . . . n} such that for i ̸= j, it follows from the direct sum decomposition that LiLj = {0}. It follows from Rees Theorem that the idempotents in a regular L-class of any semigroup form a left-zero semigroup. Therefore the idempotent generated submonoid of the orbit monoid consists of the identity and a 0-disjoint union of left-zero semigroups a… view at source ↗
read the original abstract

A smallish monoid M is a monoid that has a unique 0-minimal ideal I(M) that is a 0-simple subsemigroup and such that its regular J -classes are the group of units and the two in I(M). We show constructively how to embed an arbitrary finite semigroup S into the evaluation semigroup of a smallish monoid S^{Ev} . We use the theory of flows to show that a group mapping semigroup S admits an aperiodic flow if and only if S^{Ev} admits one. This reduces the computation of Krohn-Rhodes complexity 1 to the class of smallish monoids.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript claims to constructively embed an arbitrary finite semigroup S into the evaluation semigroup S^{Ev} of a smallish monoid. Using the theory of flows, it shows that for a group mapping semigroup S, S admits an aperiodic flow if and only if S^{Ev} does. This reduces the computation of Krohn-Rhodes complexity 1 to smallish monoids.

Significance. If the embedding and equivalence hold, this provides a valuable reduction in the study of Krohn-Rhodes complexity, limiting the problem to a structurally restricted class of monoids. The constructive embedding is a positive aspect that supports potential computational implementations.

major comments (1)
  1. [Abstract] The reduction to smallish monoids is claimed for arbitrary finite semigroups, yet the iff equivalence for aperiodic flows is only shown for group mapping semigroups. The manuscript should detail the step that allows reduction of general semigroups to group mapping semigroups while preserving the relevant flow properties under the embedding to S^{Ev}.
minor comments (1)
  1. Provide explicit definitions or references for key terms like 'smallish monoid', 'evaluation semigroup', and 'aperiodic flow' early in the paper to aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this point regarding the scope of the reduction. We address the comment below and will revise accordingly to strengthen the exposition.

read point-by-point responses

  1. Referee: [Abstract] The reduction to smallish monoids is claimed for arbitrary finite semigroups, yet the iff equivalence for aperiodic flows is only shown for group mapping semigroups. The manuscript should detail the step that allows reduction of general semigroups to group mapping semigroups while preserving the relevant flow properties under the embedding to S^{Ev}.

    Authors: We agree that the abstract and surrounding discussion would benefit from greater explicitness on this point. The embedding construction itself applies to an arbitrary finite semigroup S. The flow equivalence is established for group mapping semigroups because these are the cases that determine Krohn-Rhodes complexity 1; for a general semigroup the existence of an aperiodic flow reduces to the corresponding property on its group-mapping quotients (via the standard Rhodes expansion and the fact that aperiodic flows are preserved under homomorphic images and certain subsemigroup embeddings). The map S ↦ S^{Ev} commutes with these reductions, so the flow property transfers. We will add a short clarifying paragraph (with appropriate references to the literature on semigroup complexity) immediately after the statement of the main theorem to make this reduction step fully explicit. revision: yes

Circularity Check

0 steps flagged

No circularity: constructive embedding and flow equivalence are independent of target complexity claim.

full rationale

The paper describes a constructive embedding of any finite semigroup S into the evaluation semigroup of a smallish monoid S^Ev, together with an iff statement for the existence of aperiodic flows that is restricted to the group-mapping case. No equations, fitted parameters, or self-definitional reductions appear in the provided abstract or description. The reduction of the complexity-1 decision problem is presented as following from the embedding construction and the theory of flows; these steps are not shown to collapse back to the input claim by construction or via load-bearing self-citation chains. The derivation remains self-contained with respect to the stated assumptions and does not rely on renaming known results or smuggling ansatzes through citations in a circular fashion.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract; the smallish monoid is introduced by definition rather than postulated as a new physical or mathematical object.

pith-pipeline@v0.9.0 · 5637 in / 1182 out tokens · 44915 ms · 2026-05-20T02:13:55.759504+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 1 internal anchor

  1. [1]

    C. J. Ash. Inevitable graphs: a proof of the type II conjecture and some related decision procedures.Internat. J. Algebra Comput., 1(1):127–146, 1991

    work page 1991

  2. [2]

    Austin, K

    B. Austin, K. Henckell, C. Nehaniv, and J. Rhodes. Subsemigroups and complexity via the presentation lemma.J. Pure Appl. Algebra, 101(3):245–289, 1995

    work page 1995

  3. [3]

    Depth decomposition theorem

    S. Eilenberg.Automata, languages, and machines. Vol. B. Academic Press, New York, 1976. With two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by Bret Tilson, Pure and Applied Mathematics, Vol. 59. 19

    work page 1976

  4. [4]

    Henckell, J

    K. Henckell, J. Rhodes, and B. Steinberg. An effective lower bound for the complexity of finite semigroups and automata.Trans. AMS, 364(4):1815–1857, 2012

    work page 2012

  5. [5]

    Krohn, J

    K. Krohn, J. Rhodes, and B. Tilson.Algebraic Theory of Machines, Languages, and Semigroups,. Edited by Michael A. Arbib. With a major contribution by Kenneth Krohn, John L. Rhodes and Bret Tilson. Academic Press, New York, 1968. Chapters 1, 5–9

    work page 1968

  6. [6]

    Margolis and J

    S. Margolis and J. Rhodes. Aperiodic flows on finite semigroups: Foundations and first example. arXiv:2410.06668, 2024

    work page arXiv 2024

  7. [7]

    Margolis and J

    S. Margolis and J. Rhodes. Master List of Examples in Complexity Theory of Finite Semigroup Theory.ArXiv: https://arxiv.org/abs/2501.18300, 2025

    work page arXiv 2025

  8. [8]

    Decidability of Krohn-Rhodes complexity $c = 1$ of finite semigroups and automata

    S. Margolis, J. Rhodes, and A. Schilling. Decidability of Krohn–Rhodes complexity c = 1 of finite semigroups and automata.ArXiv 2110.10373, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  9. [9]

    Margolis, J

    S. Margolis, J. Rhodes, and A. Schilling. Decidability of Krohn–Rhodes complexity for all finite semigroups and automata.ArXiv 2406.18477, 2024

    work page arXiv 2024

  10. [10]

    Margolis, J

    S. Margolis, J. Rhodes, and P. Silva. On the Dowling and Rhodes lattices and wreath products. J. Alg., 578:55–91, 2021

    work page 2021

  11. [11]

    Rhodes and B

    J. Rhodes and B. Steinberg.The q-theory of Finite Semigroups. Springer Monographs in Mathematics. Springer, New York, 2009

    work page 2009

  12. [12]

    Rhodes and B

    J. Rhodes and B. R. Tilson. Improved lower bounds for the complexity of finite semigroups.J. Pure Appl. Algebra, 2:13–71, 1972

    work page 1972

  13. [13]

    B. Tilson. Complexity of two-Jclass semigroups.Advances in Math., 11(2):215–237, 1973

    work page 1973

  14. [14]

    Tilson.Complexity of Semigroups and Morphisms, chapter XII in S

    B. Tilson.Complexity of Semigroups and Morphisms, chapter XII in S. Eilenberg, Automata, Languages and Machines, Vol. B, pages 313–384. Academic Press, 1976

    work page 1976

  15. [15]

    Tilson.Depth Decomposition Theorem, chapter XI in S

    B. Tilson.Depth Decomposition Theorem, chapter XI in S. Eilenberg, Automata, Languages and Machines, Vol. B, Academic Press, New York, 1976, pages 287–312. Academic Press, 1976

    work page 1976

  16. [16]

    B. Tilson. Type II redux. InSemigroups and their applications (Chico, Calif., 1986), pages 201–205. Reidel, Dordrecht, 1987. (Stuart Margolis) Department of Mathematics, Bar Ilan University, Ramat Gan 52900, Israel Email address:margolis@math.biu.ac.il (John Rhodes) Department of Mathematics, University of California, Berkeley, CA 94720, U.S.A. Email addr...

    work page 1986