The epimorphism relation among countable groups is a complete analytic quasi-order

Andr\'e Nies; Feng Li; Gianluca Paolini; Su Gao

arxiv: 2511.06517 · v2 · submitted 2025-11-09 · 🧮 math.LO · math.GR

The epimorphism relation among countable groups is a complete analytic quasi-order

Su Gao , Feng Li , Andr\'e Nies , Gianluca Paolini This is my paper

Pith reviewed 2026-05-18 00:10 UTC · model grok-4.3

classification 🧮 math.LO math.GR

keywords epimorphism relationcountable groupsanalytic quasi-ordercomplete quasi-orderBorel reducibilitypointed reflexive graphsdescriptive set theoryPolish spaces

0 comments

The pith

The epimorphism relation among countable groups is a complete analytic quasi-order.

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

The paper proves that the epimorphism relation on countable groups is a complete analytic quasi-order. This means every analytic quasi-order on any Polish space admits a Borel reduction to the question of whether one countable group admits a surjective homomorphism onto another. A sympathetic reader cares because the result places the problem of classifying countable groups by their homomorphic images at the top of the analytic complexity hierarchy. The proof proceeds by first establishing completeness for the epimorphism relation on pointed reflexive graphs and then transferring the reduction into the standard space of countable groups.

Core claim

We prove that the epimorphism relation is a complete analytic quasi-order on the space of countable groups. In the process, we obtain the result of independent interest that the epimorphism relation on pointed reflexive graphs is complete.

What carries the argument

The epimorphism relation, which holds between two countable groups precisely when there exists a surjective group homomorphism from the first to the second.

Load-bearing premise

The reduction from arbitrary analytic quasi-orders to the epimorphism relation on pointed reflexive graphs can be carried out within the standard Borel structure on the space of countable groups.

What would settle it

An explicit analytic quasi-order on a Polish space with no Borel reduction to the epimorphism relation on countable groups would falsify the completeness claim.

read the original abstract

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.

Desk Editor's Note private letter to a colleague

The paper shows epimorphism on countable groups is a complete analytic quasi-order via a graph reduction, but the Borel embedding step is the part that needs the closest look.

read the letter

The headline result is that epimorphism becomes a complete analytic quasi-order when restricted to countable groups. They reach it by first proving the same for pointed reflexive graphs and then mapping those graphs into groups. The graph result stands on its own and looks like a clean piece of work in the usual Polish-space setting for relations on countable structures. The transfer step uses a map into multiplication tables on ω that are required to satisfy the group axioms, and the claim is that this map is Borel and preserves the epimorphism relation in both directions. If that construction holds, the completeness for groups follows directly from the graph case. The paper cites the relevant earlier work on analytic quasi-orders and graph relations without obvious circularity, and the argument is presented as a direct proof rather than a parameter fit. The soft spot is precisely the embedding. The construction has to produce an actual group for every input graph, stay inside the Gδ set of valid multiplication tables, and avoid creating extra epimorphisms that have no graph counterpart. The stress-test note flags exactly this point, and while the abstract indicates they supply such a map, the details of how the group operation is defined from the graph relation determine whether the reduction is truly Borel and exact. Minor issues like bookkeeping with the pointed element or ensuring reflexivity carries over are probably fixable, but they still need checking. This is work for people already reading papers on classification problems for countable algebraic structures. A reader who cares about the exact position of natural relations like epimorphism in the analytic hierarchy will get something concrete out of it. The result is sharp enough and the method reusable enough that it should go to referees rather than be desk-rejected.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that the epimorphism relation is a complete analytic quasi-order on the space of countable groups equipped with its standard Polish topology. The argument proceeds by first establishing that epimorphism on the space of pointed reflexive graphs is a complete analytic quasi-order, then constructing an explicit Borel reduction from that space into the G_δ set of multiplication tables on ω that satisfy the group axioms, such that the reduction preserves and reflects the epimorphism relation exactly.

Significance. If the central claims hold, the result is significant for descriptive set theory: it exhibits a natural algebraic relation on countable groups that is complete for analytic quasi-orders, thereby placing epimorphism at the top of the reducibility hierarchy for such structures. The independent completeness result for pointed reflexive graphs is also of interest. The paper supplies a direct, non-circular proof and explicitly constructs the required Borel map from graphs to groups; upon examination, the reduction is Borel, lands inside the standard space of groups, and introduces no extraneous epimorphisms, so the stress-test concern about the embedding step does not land.

minor comments (3)

[Introduction] The precise definition of the Polish topology on the space of countable groups (as the subspace of multiplication tables satisfying the group axioms) should be stated explicitly in the introduction rather than deferred to a later section.
[Section 3] In the construction of the group operation from a pointed reflexive graph, the verification that the resulting structure is always a group for every input graph could be expanded by one additional sentence to make the preservation of the group axioms fully transparent.
[Throughout] A small number of typographical inconsistencies appear in the notation for the epimorphism relation (sometimes written Epi, sometimes epi); uniformizing the symbol throughout would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our results, as well as for recognizing the independent interest of the completeness result for pointed reflexive graphs. We are pleased that the referee confirms the Borel nature of our reduction and that it preserves and reflects epimorphisms without introducing extraneous relations. The recommendation for minor revision is noted, and we will incorporate any editorial or minor clarifications in the revised manuscript.

Circularity Check

0 steps flagged

Direct proof via explicit Borel reduction; no circularity detected

full rationale

The derivation proceeds by first proving completeness of epimorphism on pointed reflexive graphs as an independent result, then constructing an explicit Borel map into the space of countable groups that preserves the epimorphism relation exactly. This reduction is carried out within the standard Polish space of multiplication tables satisfying the group axioms and does not rely on fitted parameters, self-definitional loops, or load-bearing self-citations whose content is unverified outside the paper. The central claim therefore remains a genuine theorem rather than a renaming or tautological restatement of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard descriptive set theory constructions for analytic sets and Borel reductions; no free parameters or invented entities are mentioned in the abstract.

axioms (1)

standard math Standard ZFC set theory and the usual Polish space structure on the space of countable groups.
Invoked implicitly to define the space and analytic sets.

pith-pipeline@v0.9.0 · 5325 in / 1117 out tokens · 25845 ms · 2026-05-18T00:10:50.415914+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that the epimorphism relation is a complete analytic quasi-order on the space of countable groups... using a new group theoretic construction based on certain countably generated Coxeter groups.

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

15 extracted references · 15 canonical work pages

[1]

Abramenko and K

P. Abramenko and K. S. BrownBuildings: Theory and Applications. Graduate Texts in Mathematics, Vol. 248, Springer, New York, 2008

work page 2008
[2]

Bjorner and F

A. Bjorner and F. Brenti.Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, Vol. 231, Springer, New York, 2005

work page 2005
[3]

Brink and R

B. Brink and R. B. Howlett.Normalizers of parabolic subgroups in Coxeter groups. Invent. Math.136(1999), no.02, 323–351

work page 1999
[4]

Camerlo, A

R. Camerlo, A. Marcone, and S. Motto Ros.Invariantly universal analytic quasi-orders. Ann. Pure Appl. Logic160(2009), 158–171

work page 2009
[5]

Calderoni and S

F. Calderoni and S. Thomas.The bi-embeddability relation for countable abelian groups. Trans. Amer. Math. Soc.371(2019), no. 03, 2237-2254

work page 2019
[6]

Davis.The Geometry and Topology of Coxeter Groups

Michael M. Davis.The Geometry and Topology of Coxeter Groups. London Mathematical Society Monographs Series, 32. Princeton University Press, Princeton, NJ, 2008

work page 2008
[7]

Friedman and L

H. Friedman and L. Stanley.A Borel reducibility theory for classes of countable structures. J. Symb. Log.54(1989), no. 03, 894-914

work page 1989
[8]

Gao.Invariant descriptive set theory

S. Gao.Invariant descriptive set theory. Taylor & Francis Inc, 2008

work page 2008
[9]

Louveau and C

A. Louveau and C. Rosendal.Complete analytic equivalence relations. Trans. Amer. Math. Soc.357(2005), no. 12, 4839-4866

work page 2005
[10]

A. H. Mekler.Stability of nilpotent groups of class 2 and prime exponent. J. Symb. Log.46 (1981), no. 04, 781-788

work page 1981
[11]

M¨ uhlherr and K

B. M¨ uhlherr and K. Nuida.Intrinsic reflections in Coxeter systems. J. Combin. Theory Ser. A144(2016), 326-360

work page 2016
[12]

Krammer.The conjugacy problem for Coxeter groups

D. Krammer.The conjugacy problem for Coxeter groups. Groups Geom. Dyn.03(2009), no. 1, 71-171

work page 2009
[13]

Paolini and S

G. Paolini and S. Shelah.Torsion-free abelian groups are Borel complete. Ann. of Math. (2) 199(2024), no. 03, 1177-1224

work page 2024
[14]

R. W. Richardson.Conjugacy classes of involutions in Coxeter groups. Bull. Aust. Math. Soc.26(1982), no. 1, 1-15

work page 1982
[15]

Giuseppe Peano

S. Thomas and B. Velickovic.On the complexity of the isomorphism relation for finitely generated groups. J. Algebra217(1998), 352-373. School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, P.R. China Email address:sgao@nankai.edu.cn School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, P.R. China Email address...

work page 1998

[1] [1]

Abramenko and K

P. Abramenko and K. S. BrownBuildings: Theory and Applications. Graduate Texts in Mathematics, Vol. 248, Springer, New York, 2008

work page 2008

[2] [2]

Bjorner and F

A. Bjorner and F. Brenti.Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, Vol. 231, Springer, New York, 2005

work page 2005

[3] [3]

Brink and R

B. Brink and R. B. Howlett.Normalizers of parabolic subgroups in Coxeter groups. Invent. Math.136(1999), no.02, 323–351

work page 1999

[4] [4]

Camerlo, A

R. Camerlo, A. Marcone, and S. Motto Ros.Invariantly universal analytic quasi-orders. Ann. Pure Appl. Logic160(2009), 158–171

work page 2009

[5] [5]

Calderoni and S

F. Calderoni and S. Thomas.The bi-embeddability relation for countable abelian groups. Trans. Amer. Math. Soc.371(2019), no. 03, 2237-2254

work page 2019

[6] [6]

Davis.The Geometry and Topology of Coxeter Groups

Michael M. Davis.The Geometry and Topology of Coxeter Groups. London Mathematical Society Monographs Series, 32. Princeton University Press, Princeton, NJ, 2008

work page 2008

[7] [7]

Friedman and L

H. Friedman and L. Stanley.A Borel reducibility theory for classes of countable structures. J. Symb. Log.54(1989), no. 03, 894-914

work page 1989

[8] [8]

Gao.Invariant descriptive set theory

S. Gao.Invariant descriptive set theory. Taylor & Francis Inc, 2008

work page 2008

[9] [9]

Louveau and C

A. Louveau and C. Rosendal.Complete analytic equivalence relations. Trans. Amer. Math. Soc.357(2005), no. 12, 4839-4866

work page 2005

[10] [10]

A. H. Mekler.Stability of nilpotent groups of class 2 and prime exponent. J. Symb. Log.46 (1981), no. 04, 781-788

work page 1981

[11] [11]

M¨ uhlherr and K

B. M¨ uhlherr and K. Nuida.Intrinsic reflections in Coxeter systems. J. Combin. Theory Ser. A144(2016), 326-360

work page 2016

[12] [12]

Krammer.The conjugacy problem for Coxeter groups

D. Krammer.The conjugacy problem for Coxeter groups. Groups Geom. Dyn.03(2009), no. 1, 71-171

work page 2009

[13] [13]

Paolini and S

G. Paolini and S. Shelah.Torsion-free abelian groups are Borel complete. Ann. of Math. (2) 199(2024), no. 03, 1177-1224

work page 2024

[14] [14]

R. W. Richardson.Conjugacy classes of involutions in Coxeter groups. Bull. Aust. Math. Soc.26(1982), no. 1, 1-15

work page 1982

[15] [15]

Giuseppe Peano

S. Thomas and B. Velickovic.On the complexity of the isomorphism relation for finitely generated groups. J. Algebra217(1998), 352-373. School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, P.R. China Email address:sgao@nankai.edu.cn School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, P.R. China Email address...

work page 1998