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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.
- [§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.
- [§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.
- [§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)
- [Abstract] There is a typo: 'equal s group conjugacy' should read 'equals group conjugacy'.
- [§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, 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, 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.
- [§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.
- [§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.
- [§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.
- [Throughout] The manuscript contains numerous small typos (e.g., 'convenction', 'cancelative' for 'cancellative', 'satsifying') and should be carefully proofread.
Circularity Check
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
assumptions (6)
- standard math Axiom of choice: every set can be well-ordered.
- domain assumption Known inclusion chain ~n ⊊ ~p ⊊ ~p* ⊊ ~tr ⊊ ~o and ~n ⊊ ~c ⊊ ~o (Eq. 2.1 of [3]).
- domain assumption Adyan's theorem: a finitely presented monoid embeds in a group if neither its left nor its right graph has cycles.
- domain assumption Cycle-chain characterization of ~n for inverse semigroups ([8, Thm 2.6], [2, Thm 2.10]).
- domain assumption Characterization of ~p via inversive 1-satisfying pairs ([7, Lemma 4.4]) and L-completeness of group conjugacy ([7, Thm 4.6]).
- standard math For every cardinal k, there exists a commutative group of cardinality k.
invented entities (2)
-
The family of conjugacy relations ~n[k] for k in N
independent evidence
-
The family of relations ~p[m] for m in N
independent evidence
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
Forward citations
Cited by 1 Pith paper
-
Thermodynamic Properties of Diatomic Molecules from the Frost-Musulin Potential
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
-
[3]
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
-
[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
-
[1]
S. I. Adyan. On the embeddability of semigroups in groups . Soviet Math. Dokl. , 1:819-821, 1960
work page 1960
-
[2]
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
-
[4]
J. Ara´ ujo, J. Konieczny, and A. Malheiro. Conjugation i n semigroups. J. Algebra, 403:93–134,
-
[5]
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
work page 2022
-
[6]
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]
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
-
[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
2007
-
[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
2009 doi
-
[11]
Lallement
G. Lallement. Semigroups and combinatorial applications . John Wiley & Sons, New York- Chichestor-Brisbane, 1979. Pure and Applied Mathematics, A Wiley-Interscience Publication
1979
-
[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
2021 doi
-
[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
1984
-
[2014]
doi:10.1016/j.jalgebra.2013.12.025
2013 doi
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.