{"id":"6c5d9762-5e6b-45f9-8e88-f26dd8f58adc","arxiv_id":"2411.16284","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper answers five open problems on semigroup conjugacy with constructive proofs, counterexamples, and L-completeness results.","lead":"Six standard notions of semigroup conjugacy can realize any prescribed partition as their class structure, and five open problems about transitivity, quotients, and definable chains are resolved. The paper supplies explicit counterexamples and an infinite family of L-complete decision problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 8.1 and Algorithm 1, which underpin the new L-completeness class and the ∼p[m] chain, are not established as written; the induction has algebraic gaps and the pseudocode is not executable, so Theorem 8.2 is unsupported.","rationale":"After checking the core constructions, the main five open-problem arguments appear sound: the normal-band product in Lemma 3.2 is associative and the ∼ℓ=∼tr identification there is correct; the group-index construction for ∼o/∼c verifies; Corollary 5.2's non-∼p assertion follows from the length grading of the one-relation monoid; Example 5.3 and Example 6.1 check out from their tables. Theorem 7.1, while terse, is supported by interpreting a^{k+1}a^{-k} as the restriction of a to im(a^k): cycle-chain types remain equal after shortening all chains by a fixed amount, and the strictness example works. The genuine weak spot is Section 8, exactly where the reader placed it: Lemma 8.1 has algebraic gaps and Algorithm 1 has concrete typos and an incorrect data-shifting step. Since Theorem 8.2 and the strictness of the ∼p[m] chain rest entirely on this unverified machinery, the conditional verdict is appropriate. The proposed test is decisive for the small cases and would distinguish a presentation error from a genuine mathematical falsehood.","tokens_in":17036,"tokens_out":33347,"duration_ms":288820,"concrete_test":"Use GAP to enumerate all pairs a,b ∈ I_n for n ≤ 6 and m ≤ 3, compute the relation ∼p[m] by repeatedly composing the ∼p relation (checked by exhaustive factorization in I_n), and independently test the Lemma 8.1 criterion by brute-force search over injective maps on chains with the stated length and idempotency conditions; report the first mismatch, if any. Then reimplement Algorithm 1 with the obvious corrections (Line 14 using ta and preserving the old C[i]; Line 16 shifting before modification) and compare its accept/reject output with the brute-force relation on the same data. Any disagreement refutes Lemma 8.1 or Theorem 8.2; agreement would show the concerns are presentation-level rather than mathematical.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest load-bearing step is in §8. Theorem 8.2 (p[m]-Conjugacy is L-complete) and the Proposition 8.3 chain claim depend on Lemma 8.1 and Algorithm 1. Lemma 8.1's forward induction is not a valid proof: given m-satisfying pairs (φ_a,ψ_a) for (a,c) and (φ_c,ψ_c) for (c,b), the proposed composition (φ_c∘φ_a, ψ_a∘ψ_c) may be undefined because φ_a is only known to map into Θ_c, not into the domain of φ_c (Θ_c^{>2m−1}); the length estimate in the paper reads '2m−1 + 2m−1 = 2m', which is arithmetically wrong (it is 4m−2) and does not yield the required 2m+1 bound for an (m+1)-satisfying pair. The converse mixes n and m (e.g., 'Θ >2n−1 a' and 'Θ 2n−1 b') and the definition of α_i is garbled. Algorithm 1 is not executable: Line 14 adds 'a' instead of 'ta' and mutates C[i] before using it; Line 16 shifts C[i] into C[i+1] after it has been overwritten. Consequently the claimed L-completeness and the strictness of the ∼p[m] chain are not supported by the text as written. The five open problems themselves may still be correctly answered by the earlier sections, but this is the load-bearing fragile premise for the paper's advertised new L-complete class.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17406,"tokens_out":15355,"duration_ms":121549,"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":[{"comment":"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.","section":"§5, Corollary 5.2"},{"comment":"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.","section":"§5, Example 5.3"},{"comment":"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 i2m−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.","section":"§8, Lemma 8.1"},{"comment":"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.","section":"§8, Algorithm 1 and Theorem 8.2"}],"minor_comments":[{"comment":"There is a typo: 'equal s group conjugacy' should read 'equals group conjugacy'.","section":"Abstract"},{"comment":"The notation max P(i,j) is confusing; writing max_P(i,j) or defining it inline would improve readability.","section":"§3, Lemma 3.2"},{"comment":"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.","section":"§3, Theorem 3.3"},{"comment":"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.","section":"§4, Example 4.2"},{"comment":"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.","section":"§6, Example 6.1"},{"comment":"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.","section":"§7, Theorem 7.2"},{"comment":"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.","section":"§8"},{"comment":"The manuscript contains numerous small typos (e.g., 'convenction', 'cancelative' for 'cancellative', 'satsifying') and should be carefully proofread.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper leans heavily on the author's prior work [7] for the base of Lemma 8.1, the logarithmic-space algorithms for inverse semigroup conjugacy, and the L-hardness of group conjugacy. The editor may wish to verify that these citations genuinely contain the claimed results and that the adaptations in this paper are faithful. Also, the claim in Theorem 8.2 that 'testing any notion of semigroup conjugacy is L-hard' is too broad and should be replaced by a precise statement. The finite examples in Section 4 appear to be checkable, but the paper would benefit from including the verification scripts or more detailed computations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jack's note answers five open problems in the semigroup conjugacy program, and the first half is genuinely good. The partition-covering construction in Section 3 is the real contribution: the semilattice-of-left-zero-semigroups trick covers ~n, ~p, ~p*, and ~tr for arbitrary partitions, and the commutative-group construction covers ~o and ~c. That is a clean, self-contained proof of Theorem 3.3. The embeddable monoid counterexample in Section 5 is also convincing—the presentation has acyclic left and right graphs, so Adyan's theorem applies, and the ~p failure is transparent. The non-cancellative quotient example in Section 6 is explicit and checkable.\n\nThe soft spots are concentrated in Section 8, and the stress-test note is right. Lemma 8.1's forward induction does not work as written: composing m-satisfying pairs (φ_a,ψ_a) and (φ_c,ψ_c) gives a map whose domain may not align, and the length bound is arithmetically wrong (2m−1 + 2m−1 = 4m−2, not 2m). The converse is garbled, mixing n and m and defining α_i with a typo. Algorithm 1 is not executable: Line 14 uses `a` instead of `ta` and mutates C[i] before shifting it to C[i+1]. So Theorem 8.2 and Proposition 8.3 are unsupported by the text as written. That matters because the paper advertises a new L-complete class, but it is not load-bearing for the five open problems from [3]—those rely on Sections 3–7, which hold up. The self-citation to [7] is appropriate; Lemma 4.4 there is published and distinct.\n\nBottom line: the core results on partition covering and the counterexamples deserve referee time, but Section 8 needs a rewrite. I'd send it to review with a request to fix or remove the p[m] chain claims and make Algorithm 1 concrete. A serious referee can separate the solid parts from the broken ones.","headline":"Solid partition-covering results and counterexamples in the first half; Section 8's L-completeness claims are not supported as written.","tokens_in":17936,"tokens_out":2551,"would_cite":true,"duration_ms":128190,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20M99","20E45"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["semigroup conjugacy","partition-covering","normal bands","inverse semigroups","conjugacy chains","L-complete problems","one-relation monoids"],"falsifier":"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.","tokens_in":16830,"feed_emoji":"🧩","tokens_out":12793,"duration_ms":96948,"temperature":0.7,"pith_summary":"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.","feed_headline":"Semigroup conjugacies realize any prescribed partition","feed_subtitle":"Six standard relations become partition-covering; a group-embeddable example makes ~p nontransitive.","key_machinery":"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]}$.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The paper under study: it poses the five open problems and defines the four standard conjugacy relations; every main result answers one of its questions.","marker":"[3]"},{"why":"Supplies Lemma 4.4 and the logarithmic-space algorithms for checking cycle-chain conjugacy; the $\\sim_{p[m]}$ characterization and both L-completeness theorems build directly on it.","marker":"[7]"},{"why":"Provides the equivalence between $\\sim_p$ and the existence of an inversive 1-satisfying pair in partial bijection semigroups, which Lemma 8.1 generalizes.","marker":"[9]"},{"why":"Provides the embedding criterion (cycle-free left and right graphs) used in Corollary 5.2 to show the nontransitive example embeds in a group.","marker":"[1]"},{"why":"Defines $\\sim_n$ and gives the characterization used in the construction and strictness of the infinite chain $\\{\\sim_{n[k]}\\}$.","marker":"[8]"},{"why":"Gives the cycle-chain type characterization of $\\sim_n$ in inverse semigroups, used in Theorems 7.1 and 7.2.","marker":"[2]"},{"why":"Supplies the small semigroups and multiplication tables used for the structural counterexamples throughout Sections 4 and 5.","marker":"[5]"},{"why":"Introduces $\\sim_p$ and records its transitivity for free semigroups, the baseline that the embeddable nontransitive example overturns.","marker":"[11]"}],"fun_headline_variants":["Semigroup conjugacies realize any prescribed partition","Five open problems in semigroup conjugacy answered","Six standard conjugacies proven partition-covering","Group-embeddable semigroup with nontransitive ~p"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Semigroup conjugacies realize any prescribed partition","Five open problems in semigroup conjugacy answered","Six standard conjugacies proven partition-covering","Group-embeddable semigroup with nontransitive ~p"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000448,"raw_usage":{"total_tokens":2331,"prompt_tokens":1089,"completion_tokens":1242,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":705,"completion_tokens_details":{"reasoning_tokens":1181}},"tokens_in":705,"tokens_out":1242,"duration_ms":11067,"temperature":1.0,"reasoning_tokens":1181,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:18:36.496712+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Ara´ ujo, M","cited_arxiv_id":null,"evidence_quote":"The paper under study: it poses the five open problems and defines the four standard conjugacy relations; every main result answers one of its questions."},{"cited_title":"Kudryavtseva and V","cited_arxiv_id":null,"evidence_quote":"Provides the equivalence between $\\sim_p$ and the existence of an inversive 1-satisfying pair in partial bijection semigroups, which Lemma 8.1 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the embedding criterion (cycle-free left and right graphs) used in Corollary 5.2 to show the nontransitive example embeds in a group."},{"cited_title":"Konieczny","cited_arxiv_id":null,"evidence_quote":"Defines $\\sim_n$ and gives the characterization used in the construction and strictness of the infinite chain $\\{\\sim_{n[k]}\\}$."},{"cited_title":"Distler and J","cited_arxiv_id":null,"evidence_quote":"Supplies the small semigroups and multiplication tables used for the structural counterexamples throughout Sections 4 and 5."},{"cited_title":"Lallement","cited_arxiv_id":null,"evidence_quote":"Introduces $\\sim_p$ and records its transitivity for free semigroups, the baseline that the embeddable nontransitive example overturns."}],"review_version":1}