Pith. sign in

REVIEW 5 major objections 8 minor 1 cited by

Answering Five Open Problems Involving Semigroup Conjugacy

T0 review · 5 major / 8 minor · reviewed 2026-08-12 · deepseek-v4-flash

Pith's one-line read The paper proves that six standard semigroup conjugacy relations are partition-covering and answers the remaining open problems with explicit counterexamples and an infinite chain of definable conjugacies.

desk verdict Solid partition-covering results and counterexamples in the first half; Section 8's L-completeness claims are not supported as written. read the letter →

arxiv 2411.16284 v1 pith:O47UQXJI submitted 2024-11-25 math.GR

classification math.GR MSC 20M9920E45
keywords semigroupconjugacypartition-coveringnormalbandsinversesemigroupschainsL-completeproblemsone-relationmonoids
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Semigroup conjugacy is any equivalence relation on a semigroup that agrees with ordinary group conjugacy whenever the semigroup is a group. The paper answers five open problems about such relations, all posed in the literature it responds to. Its central theorem is that each of the six standard relations $\sim_o$, $\sim_c$, $\sim_n$, $\sim_p$, $\sim_p^*$, and $\sim_{tr}$ is partition-covering: for every set $X$ and every partition of $X$, there exists a semigroup on $X$ whose conjugacy classes are exactly the blocks of the partition. The paper also constructs a semigroup embeddable in a group for which $\sim_p$ is not transitive, builds an infinite chain of first-order definable conjugacies, and gives counterexamples for the congruence-quotient and variant-transitivity problems. If these constructions are correct, all five problems are settled as stated.

What carries the argument

The load-bearing objects are the left-zero band construction of Lemma 3.2 and the index-group construction of Theorem 3.3. In the first, each partition block $X_i$ is identified with pairs $\{(i,j) : j \in \alpha_i\}$ for an ordinal $\alpha_i$, and multiplication on $X$ is $(a,b)(c,d) = (\max_P(a,c), b)$ with $\max_P$ comparing the block indices; the result is a normal band in which the relation $\sim_\ell$ (two elements multiply to themselves in both orders) is contained in $\sim_n$, hence in $\sim_p$, $\sim_p^*$, and $\sim_{tr}$, and $\sim_{tr}$-conjugacy forces equality of first coordinates. This sandwich $\sim_\ell \subseteq \sim \subseteq \sim_{tr}$ is what makes all four relations partition-covering. For $\sim_o$ and $\sim_c$, the index set is a commutative group and multiplication $(a,b)(c,d) = (a\cdot c, 0)$ makes the first coordinate behave like group multiplication, so $\sim_o$-conjugacy is equality of first coordinates. The infinite chains are driven by the cycle-chain structure of the full partial bijection semigroup $I_n$: $\sim_{n[k]}$ compares $a^{k+1}a^{-k}$ with $b^{k+1}b^{-k}$, and chains of different lengths separate $\sim_{n[i]}$ from $\sim_{n[j]}$.

What would settle it

Run a brute-force comparison on $I_3$ with $m=1$, checking Algorithm 1's output against the direct existence of an inversive $1$-satisfying pair for every pair of elements; the instance with $a$ a single chain of length 3 and $b$ empty should be rejected, and any mismatch traceable to the arithmetic in line 14 (the update involving $C[i]+a$ rather than $C[i]+t_a$) would refute Lemma 8.1 and Theorem 8.2.

Watch

Extended reading notes

Core claim

The main discovery is Theorem 3.3, which says that $\sim_o$, $\sim_c$, $\sim_n$, $\sim_p$, $\sim_p^*$, and $\sim_{tr}$ are all partition-covering. The proof for the middle four relations uses a normal band built as a semilattice of left-zero subsemigroups: each block of the partition is indexed by an ordinal, elements are pairs $(i,j)$, and multiplication $(a,b)(c,d) = (\max_P(a,c), b)$ makes two elements conjugate exactly when their first coordinates agree. The proof for $\sim_o$ and $\sim_c$ uses a commutative group of indices with multiplication $(a,b)(c,d) = (a\cdot c, 0)$, which again forces conjugacy to coincide with equality of first coordinates. Beyond partition-covering, the paper gives the one-relation monoid $\langle a,b \mid aab = bba\rangle$, which embeds in a group but has nontransitive $\sim_p$, and an infinite chain $\{\sim_{n[k]}\}$ of first-order definable conjugacies on partial bijection semigroups, where $\sim_{n[k]}$ compares $a^{k+1}a^{-k}$ and $b^{k+1}b^{-k}$ under $\sim_n$. It also exhibits an infinite semigroup where $\sim_o$ is a congruence yet the quotient is not cancellative, and an eight-element semigroup where $\sim_p$ fails transitivity while every variant has transitive $\sim_p$.

Load-bearing premise

The paper's claims about $\sim_{p[m]}$ and the L-completeness results rest on Lemma 8.1, which characterizes $\sim_{p[m]}$ by the existence of an 'inversive $m$-satisfying pair,' and on the logarithmic-space algorithm that checks for such pairs; if either the characterization or the algorithm's bookkeeping has a flaw, those claims lose their support.

Editorial extensions

If this is right

  • For any set and any prescribed partition, one can build a semigroup on that set whose $\sim_o$, $\sim_c$, $\sim_n$, $\sim_p$, $\sim_p^*$, or $\sim_{tr}$ classes realize the partition exactly, so the apparent rigidity of group conjugacy does not carry over to any of these semigroup notions.
  • The one-relation monoid $\langle a,b \mid aab = bba\rangle$ is embeddable in a group but has nontransitive $\sim_p$, so embeddability in a group does not force transitivity of $\sim_p$.
  • The relations $\sim_{n[1]} \subsetneq \sim_{n[2]} \subsetneq \cdots$ form an infinite strictly increasing chain of first-order definable conjugacies, and each agrees with group conjugacy when the semigroup is a group.
  • The decision problems $n[k]$-Conjugacy and $p[m]$-Conjugacy are both L-complete on the full partial bijection semigroup, so the iterated relations do not raise the asymptotic space cost of testing conjugacy.
  • The eight-element semigroup where every variant is $\sim_p$-transitive while $\sim_p$ itself is not shows that local variant behavior cannot force global transitivity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same ordinal-indexed left-zero construction gives a general template: any equivalence relation on an arbitrary set that can be sandwiched between the left-zero relation and $\sim_{tr}$ on normal bands will be partition-covering, so the family of covering conjugacies is likely much larger than the six listed.
  • The one-relation monoid example could be adapted to control the number of $\sim_p$ steps explicitly, potentially producing group-embeddable semigroups where $\sim_{p[m]}\neq\sim_{p[m+1]}$, which would extend the chain result to the embeddable setting.
  • A computational search over small finite semigroups could test whether the infinite example with $\sim_o$ a congruence and noncancellative quotient is necessary, or whether a finite example exists as the paper leaves open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 8 minor

Summary. The paper claims to answer five open problems from Araújo, Kinyon, Konieczny, and Malheiro concerning semigroup conjugacy. It proves that the relations ~o, ~c, ~n, ~p, ~p*, and ~tr are partition-covering (Problem One); constructs a semigroup embeddable in a group for which ~p is not transitive (Problem Two); constructs an infinite chain of first-order definable conjugacies ~n[k] (Problem Three); gives an infinite semigroup for which ~o is a congruence and the quotient is not cancellative (Problem Four); and gives a semigroup for which ~p fails transitivity while each variant has transitive ~p (Problem Five). The paper also introduces families ~n[k] and ~p[m] and claims that the associated conjugacy problems are L-complete, with ~p[m] forming a proper chain on the inverse symmetric monoids I_n.

Significance. The partition-covering construction in Section 3 is elegant and, if correct, resolves a natural open question with a clean uniform method. The counterexamples for Problems Two, Four, and Five address questions that have been open in the semigroup literature, and the claimed L-completeness results would be a novel contribution connecting semigroup conjugacy to descriptive complexity. The paper ships several machine-verifiable finite examples and cites prior peer-reviewed work for the base characterizations; these are strengths. However, several load-bearing assertions are currently unproved or sketched, and the Section 8 results on p[m]-Conjugacy are not supported as written, so the contribution is not yet in a publishable state.

major comments (5)
  1. [§5, Corollary 5.2] The proof that aba and bab are not ~p-related is omitted. The monoid relation aab=bba preserves length, but that alone does not rule out all factorizations uv=aba and vu=bab; one must also consider that the only relation cannot be applied to subwords of aba or bab and check the finite possibilities for (u,v). This is a load-bearing step for Problem Two, and the proof needs to be supplied.
  2. [§5, Example 5.3] The property (2), namely that 6·5 and 7·5 are not ~p-related, is asserted without proof. Since this is exactly the failure of transitivity needed for Problem Five, the assertion should be verified, for example by a short exhaustive check of factorizations in the given eight-element semigroup or by citing a GAP computation with the check described.
  3. [§7, Theorems 7.1 and 7.2] The proof of Theorem 7.1 contains an off-by-one error: for the shift map a defined by xa=x+1 on {1,...,j-1}, a^i satisfies x a^i = x+i, not x+i+1. The conclusion that a ~n[j] b and a ⁄~n[i] b for i<j is correct, but the present computation is not. The proof of Theorem 7.2 is also too terse: the alleged logarithmic-space algorithm for n[k]-Conjugacy is not described, and the L-hardness claim 'testing any notion of semigroup conjugacy is L-hard' is imprecise and needs a concrete reduction.
  4. [§8, Lemma 8.1] The induction proving Lemma 8.1 is not valid as written. In the forward direction, the composition (φ_c∘φ_a, ψ_a∘ψ_c) may be undefined because φ_a maps Θ_a^{>2m−1} into Θ_c, not into the required domain Θ_c^{>2m−1} of φ_c. The length estimate is also arithmetically wrong: 2m−1+2m−1 is 4m−2, not 2m, and it does not yield the required 2m+1 bound for an (m+1)-satisfying pair. In the converse, the construction mixes n and m (e.g., 'Θ >2n−1 a' and 'Θ 2n−1 b') and the definition of α_i is garbled. Since Lemma 8.1 underpins Theorem 8.2 and Proposition 8.3, those results are currently unsupported.
  5. [§8, Algorithm 1 and Theorem 8.2] Algorithm 1 is not executable as written: Line 14 uses the input element a where the integer ta is intended, and Line 16 shifts C[i] into C[i+1] after C[i] has already been updated, which can overwrite data needed in later iterations. The correctness proof does not resolve these problems or explain the intended behavior. Consequently, the claim that p[m]-Conjugacy can be decided in logarithmic space (Theorem 8.2) is not established.
minor comments (8)
  1. [Abstract] There is a typo: 'equal s group conjugacy' should read 'equals group conjugacy'.
  2. [§3, Lemma 3.2] The notation max P(i,j) is confusing; writing max_P(i,j) or defining it inline would improve readability.
  3. [§3, Theorem 3.3] In the third construction for the singleton partition, it would help to state explicitly that the left-zero semigroup makes ~c the universal relation because every element acts as an identity for the others in the required sense.
  4. [§4, Example 4.2] The claim that [3,2,4,4] and [4,2,3,3] are not ~n-related is not justified; a brief kernel/image argument or a note that this was checked in GAP would be useful.
  5. [§6, Example 6.1] The proof that the listed sets are exactly the ~o-classes is sketched; the argument that elements of the form b^i a and b^j a for i≠j are unrelated is not explicitly given and should be included.
  6. [§7, Theorem 7.2] The adaptation of the algorithms from [7] is described only as 'simply ignoring chains of length less than k'; a more precise description of the modified algorithm and its space usage is needed.
  7. [§8] The notation ~p[m] for the relation and p[m]-Conjugacy for the decision problem is potentially confusing; a sentence explicitly distinguishing the two would help.
  8. [Throughout] The manuscript contains numerous small typos (e.g., 'convenction', 'cancelative' for 'cancellative', 'satsifying') and should be carefully proofread.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central constructions are self-contained, and the author's prior work [7] is used only as ordinary published support, not as a self-referential premise.

full rationale

The main derivations in the paper do not reduce to their own inputs. Section 3 explicitly constructs semigroups realizing arbitrary prescribed partitions, and verifies by direct multiplication that the six conjugacies coincide with the block relation; the proof is self-contained and does not assume the partition-covering conclusion. Sections 4-6 answer the remaining open problems with explicit examples, external theorems such as Adyan's embeddability criterion, and small-semigroup tables, none of which are fitted parameters or renamed versions of the target claims. Section 7 defines the new relations ~n[k] in terms of the known ~n cycle-chain characterization and proves the chain theorem algebraically using external results [2,8,9,10]; the definition is not a restatement of the conclusion. Section 8 extends the author's earlier characterization [7, Lemma 4.4] to ~p[m] by induction. This is reliance on a prior published result with distinct content, not circularity: the base case is not the theorem being proved, and the present Lemma 8.1 adds a new induction over m. The L-completeness proof also cites [7] for lower bounds and for the ~p* logspace test; these are independent published results, not self-referential assumptions of the present claims. The apparent typographical and correctness issues in Algorithm 1 and in the induction estimates are legitimate correctness concerns, but they do not constitute a circular reduction: no equation is defined in terms of the target relation, and no fitted value is later announced as a prediction. Under the quoted-reduction standard required for a circularity finding, no specific circular step can be exhibited, so the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The central claims rely on standard set-theoretic choice, on the cited chain of inclusions and characterizations, and on Adyan's embeddability theorem. No free parameters are introduced. The families ~n[k] and ~p[m] are explicit definitions with proven properties, not unconstrained postulates.

assumptions (6)
  • standard math Axiom of choice: every set can be well-ordered.
    Lemma 3.2 uses Von Neumann ordinals and well-ordering of each Xi to index elements of the constructed semigroup.
  • domain assumption Known inclusion chain ~n ⊊ ~p ⊊ ~p* ⊊ ~tr ⊊ ~o and ~n ⊊ ~c ⊊ ~o (Eq. 2.1 of [3]).
    Used in Lemma 3.2 and Theorem 3.3 to infer that the constructed left-zero relation lies inside the target conjugacies.
  • domain assumption Adyan's theorem: a finitely presented monoid embeds in a group if neither its left nor its right graph has cycles.
    Used in Theorem 5.1 and Corollary 5.2 to prove that the one-relation monoid S is embeddable in a group.
  • domain assumption Cycle-chain characterization of ~n for inverse semigroups ([8, Thm 2.6], [2, Thm 2.10]).
    Used in Theorems 7.1 and 7.2 to compute classes of ~n[k] and to establish L-membership.
  • domain assumption Characterization of ~p via inversive 1-satisfying pairs ([7, Lemma 4.4]) and L-completeness of group conjugacy ([7, Thm 4.6]).
    Used as the base case and hardness argument for Lemma 8.1 and Theorem 8.2; this is the author's own prior published work.
  • standard math For every cardinal k, there exists a commutative group of cardinality k.
    Used in Theorem 3.3 to construct the index group (I, ·) for the ~o and ~c partition-covering construction.
invented entities (2)
  • The family of conjugacy relations ~n[k] for k in N independent evidence
    purpose: Forms an infinite chain of first-order definable semigroup conjugacies, answering the chain half of Problem 6.21.
    Explicitly defined as a ~n[k] b iff a^(k+1) a^(-k) ~n b^(k+1) b^(-k); Theorem 7.1 proves strict inclusions and Theorem 7.2 proves L-completeness.
  • The family of relations ~p[m] for m in N independent evidence
    purpose: Provides an infinite chain of relations extending ~p that equal group conjugacy on groups, and yields new L-complete problems.
    Defined by iterating the ~p relation; Lemma 8.1 and Proposition 8.3 establish distinctness and L-completeness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Answering Five Open Problems Involving Semigroup Conjugacy." pith.science (2026). https://pith.science/paper/O47UQXJI

@misc{pith2026241116284,
  author       = {Pith},
  title        = {Pith review of: Answering Five Open Problems Involving Semigroup Conjugacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O47UQXJI}},
  note         = {Machine review of arXiv:2411.16284}
}
read the original abstract

A semigroup conjugacy is an equivalence relation that equals group conjugacy when the semigroup is a group. In this note, we answer five open problems related to semigroup conjugacy. (Problem One) We say a conjugacy ~ is partition-covering if for every set X and every partition of the set, there exists a semigroup with universe X such that the partition gives the ~-conjugacy classes of the semigroup. We prove that six well-studied conjugacy relations -- ~o, ~c, ~n, ~p, ~p*, and ~tr -- are all partition-covering. (Problem Two) For two semigroup elements a and b in S, we say a ~p b if there exists u and v in S such that a=uv and b=vu. We give an example of a semigroup that is embeddable in a group for which ~p is not transitive. (Problem Three) We construct an infinite chain of first-order definable semigroup conjugacies. (Problem Four) We construct a semigroup for which ~o is a congruence and S\~o is not cancellative. (Problem Five) We construct a semigroup for which ~p is not transitive while, for each of the semigroup's variants, ~p is transitive.

Figures

Figures reproduced from arXiv: 2411.16284 by the authors.

Figure 1
Figure 1. from [3] depicts a lattice of conjugacies in which order is defi [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Thermodynamic Properties of Diatomic Molecules from the Frost-Musulin Potential

    physics.chem-ph 2026-04 unverdicted novelty 4.0 of 10

    The Frost-Musulin potential with Pekeris approximation produces accurate Gibbs free energy for H2 and LiH but deviates in heat capacity and enthalpy at high temperatures due to neglected dissociation and inelastic effects.

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages · cited by 1 Pith paper

  1. [3]

    Ara´ ujo, M

    J. Ara´ ujo, M. Kinyon, J. Konieczny, and A. Malheiro. Fou r notions of conjugacy for ab- stract semigroups. Proceedings of the Royal Society of Edinburgh: Section A Mat hematics, 147(6):1169–1214, 2017. doi:10.1017/S0308210517000099

  2. [7]

    T. Jack. On the complexity of inverse semigroup conjugac y. Semigroup Forum 106, 618–632 (2023). https://doi.org/10.1007/s00233-023-10349-y

  3. [1]

    S. I. Adyan. On the embeddability of semigroups in groups . Soviet Math. Dokl. , 1:819-821, 1960

  4. [2]

    Ara´ ujo, M

    J. Ara´ ujo, M. Kinyon, and J. Konieczny. Conjugacy in in- verse semigroups. Journal of Algebra , 533:142–173, 2019. URL:https://www.sciencedirect.com/science/article/pii/S0021869319302765 . doi:10.1016/j.jalgebra.2019.05.022

  5. [4]

    Ara´ ujo, J

    J. Ara´ ujo, J. Konieczny, and A. Malheiro. Conjugation i n semigroups. J. Algebra, 403:93–134,

  6. [5]

    Distler and J

    A. Distler and J. Mitchell. Smallsemi, a library of small semigroups, Version 0.6.13. URL: https://gap-packages.github.io/smallsemi/, , Feb 2022. GAP package. ANSWERING FIVE OPEN PROBLEMS INVOL VING SEMIGROUP CONJUGAC Y 15

  7. [6]

    Izhakian, J

    Z. Izhakian, J. Rhodes, and B. Steinberg. Representatio n theory of finite semigroups over semirings. J. Algebra 336:139–157, 2011. doi:10.1016/j.jalgebra.2011.02.048

  8. [8]

    Konieczny

    J. Konieczny. A new definition of conjugacy for semigroup s. Journal of Algebra and Its Appli- cations, 17(02):1850032, 2018. https://doi.org/10.1142/S0219498818500329

Show all 14 references
  1. [9]

    Kudryavtseva and V

    G. Kudryavtseva and V. Mazorchuk. On conjugation in some transformation and Brauer-type semigroups. Publ. Math. Debrecen , 70(1-2):19–43, 2007

  2. [10]

    Kudryavtseva and V

    G. Kudryavtseva and V. Mazorchuk. On three approaches t o conjugacy in semmigroups. Semigroup Forum, 78(1):14-20, 2009. doi:/10.1007/s00233-008-9047-7

  3. [11]

    Lallement

    G. Lallement. Semigroups and combinatorial applications . John Wiley & Sons, New York- Chichestor-Brisbane, 1979. Pure and Applied Mathematics, A Wiley-Interscience Publication

  4. [12]

    The word problem for one-relation monoids: a survey

    Nyberg-Brodda, C.F. The word problem for one-relation monoids: a survey. Semigroup Fo- rum, 103:297–355, 2021. https://doi.org/10.1007/s00233-021-10216-8

  5. [13]

    F. Otto. Conjugacy in monoids with a special Church-Ros ser pre- sentation is decidable. Semigroup Forum , 29:223-240, 1984. URL: https://api.semanticscholar.org/CorpusID:120023501

  6. [2014]

    doi:10.1016/j.jalgebra.2013.12.025

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.