Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Conjugacy in a family of free-by-cyclic groups

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every $m\ge 2$, the free-by-cyclic group $H_m=F_m\rtimes_\varphi\mathbb{Z}$, where $\varphi(a_i)=a_i a_{i-1}$, has linear conjugator length and polynomial-time solvable conjugacy and conjugacy-search problems.

desk verdict A serious, new result on conjugacy in the hydra-like groups H_m, but the proof leans on two unproved piece-decomposition lemmas that need to be supplied before the theorems are fully certified. read the letter →

arxiv 2506.01248 v1 pith:BL7FMOWI submitted 2025-06-02 math.GR

Martin R. Bridson , Timothy R. Riley , Andrew W. Sale This is my paper
classification math.GR MSC 20F6520F10
keywords free-by-cyclicgroupsconjugacyproblemsearchconjugatorlengthfunctionpolynomial-timealgorithmpiecedecompositionspolynomiallygrowingautomorphismstwisted
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

The paper proves that the free-by-cyclic groups $H_m=F_m\rtimes_\varphi\mathbb{Z}$ ($m\ge2$), where $\varphi(a_i)=a_i a_{i-1}$ for $i\ge2$ and $\varphi(a_1)=a_1$, have a linear conjugator length function and polynomial-time solvable conjugation problems. Theorem 1 states $CL(n)\simeq n$: any two conjugate elements represented by words of total length $n$ are conjugate by a word of length at most a fixed multiple of $n$. Theorem 2 states that the conjugacy problem and the conjugacy search problem in $H_m$ are solvable by deterministic algorithms in time polynomial in the total input length, and the algorithm can be modified to output a linear-length conjugator. The route is to translate conjugacy in $H_m$ into three twisted conjugacy problems in the free group $F_m$, then control the geometry of solutions via a piece decomposition of words that is preserved by iterates of $\varphi$. The authors regard $H_m$ as prototypes for the general free-by-cyclic case, for which polynomial-time conjugacy and linear conjugator length are expected but not yet known.

What carries the argument

The load-bearing object is the rank-$i$ piece decomposition of a reduced word in $F_m$: a rank-$i$ piece is a maximal subword of one of the forms $a_i u$, $u a_i^{-1}$, $a_i u a_i^{-1}$, or $u$, where $u$ has rank at most $i-1$. Lemmas 3.1 and 3.2 assert that both $\varphi$ and $\varphi^{-1}$ send every piece to a piece of the same type and produce no cancellation between neighbouring pieces, so the piece decomposition of $\varphi^r(w)$ is just the image of the decomposition of $w$. This piecewise rigidity gives Proposition 4.4's growth bound $|\varphi^r(\pi)|_F\simeq |r|^{i-1}$ for a strict rank-$i$ piece, and Proposition 4.5's distortion bound $|u'|_H\le (2m+1)|h|_H$ for subwords of the normal form. The final ingredient is Lemma 8.4's replacement trick, which substitutes a long product of shifted pieces $M_1$ by the element $s^{pq}$, converting a quadratic estimate into the linear bound needed for Theorem 1.

What would settle it

A concrete computational test would be to run the Section 10 algorithm on all conjugate pairs in $H_3$ with total input length up to $N$ and record the largest ratio of output conjugator length to $N$; if this ratio is unbounded as $N$ grows, the linear bound $CL(n)\simeq n$ is false, and any input on which the algorithm does not halt in polynomial time would refute Theorem 2.

Watch

Extended reading notes

Core claim

The paper's central claim is that in every group $H_m=F_m\rtimes_\varphi\mathbb{Z}$ ($m\ge2$) with $\varphi(a_i)=a_i a_{i-1}$ and $\varphi(a_1)=a_1$, conjugation is both geometrically and algorithmically tame. Theorem 1 asserts $CL(n)\simeq n$: whenever two words of total length $n$ represent conjugate elements, some conjugator of length at most a constant multiple of $n$ exists. Theorem 2 asserts that deterministic polynomial-time algorithms solve both the conjugacy problem and the conjugacy search problem, and the same constructive procedure can be adjusted to output a conjugator of linear length (Remark 10.1). The proof achieves this by decomposing reduced free-group words into rank-$i$ pieces, proving growth and distortion bounds for those pieces under iterates of $\varphi$, reducing conjugacy in $H_m$ to the 0-twisted, $H$-twisted, and $I$-twisted conjugacy problems in $F_m$, and then showing, through Proposition 7.1 and Lemma 8.4, that every solution can be replaced by a 'chunky' one whose length is linear and whose search space is polynomially sized.

Load-bearing premise

The load-bearing premise is the unproved structural assertion, left as an exercise and inherited from the earlier piece-decomposition literature, that applying the automorphism $\varphi$ or its inverse to a word preserves each building-block substring exactly in type and causes no cancellation between neighbouring substrings; if that fails for even one substring type, the growth estimates, prefix analysis, and replacement trick that produce the linear bound and the polynomial-time algorithms all collapse.

Editorial extensions

If this is right

  • For any two conjugate elements of $H_m$ with total input length $n$, a conjugator of length at most a fixed constant times $n$ exists; asymptotically, $CL(n)\simeq n$.
  • The conjugacy problem and the conjugacy search problem for $H_m$ are solvable in deterministic polynomial time, and the algorithm can be modified to output a linear-length conjugator in polynomial time.
  • The solution passes through the 0-twisted, $H$-twisted, and $I$-twisted conjugacy problems in $F_m$, so all three subordinate problems inherit polynomial-time algorithms with linear solution lengths.
  • Because known relative-hyperbolicity results reduce the general free-by-cyclic conjugacy problem to the polynomial-growth case, these prototype groups provide the first polynomial-time and linear-conjugator evidence that the same should hold for all free-by-cyclic groups.
  • The contrast with the abelian analogues $\Gamma_m=\mathbb{Z}^m\rtimes\mathbb{Z}$, where the conjugator length function is polynomial of degree $m$, shows that the linear behaviour is a genuinely free-group phenomenon.

Reading between the lines

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

  • Beyond the paper: the same piece-conservation framework should be adaptable to any polynomially growing automorphism of $F_m$, since the authors explicitly shaped the proof to avoid using the special presentations of $H_m$; if the two unproved structural lemmas hold more generally, Theorem 1 would extend to all such mapping tori, and the known relative-hyperbolicity reduction would then give $CL(n
  • Beyond the paper: a practical stress test is to verify Lemmas 3.1 and 3.2 computationally for ranks $2,3,4$, since these lemmas are asserted as exercises and a single piece whose image changes type or cancels with a neighbour would invalidate the chain of estimates from Proposition 4.4 through Lemma 8.4.
  • Beyond the paper: one could implement the Section 10 algorithm and compare its output length and running time against brute-force shortest-conjugator computations in $H_2$ and $H_3$; the linear-output variant in Remark 10.1 makes this a testable quantitative claim rather than just an asymptotic one.
  • Beyond the paper: the free-group linearity versus abelian degree-$m$ polynomial contrast suggests that replacing the tree-like Cayley graph of $F_m$ by other non-positively curved metrics, or varying the growth degree of the automorphism, could interpolate between these behaviours; this is a natural next question the paper does not address.
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

2 major / 4 minor

Summary. The paper studies the free-by-cyclic groups H_m = F_m ⋊_φ Z with φ(a_i)=a_i a_{i-1} for i≥2. It claims that for every m≥2 the conjugator length function of H_m is linear, CL(n)≃n, and that the conjugacy problem and conjugacy search problem are solvable in deterministic polynomial time. The approach reduces conjugacy in H_m to three twisted conjugacy problems in F_m, develops a theory of 'piece decompositions' to control growth under φ and φ^{-1}, solves the twisted problems with explicit algorithms and length bounds, and assembles the solution in Section 10. The main theorems are conditional on the structural Lemmas 3.1 and 3.2, whose proofs are left as exercises.

Significance. If the missing proofs are supplied, the results would be a substantial and concrete step toward polynomial-time conjugacy and conjugacy-search in free-by-cyclic groups, and would provide the first linear conjugator-length bound for a nontrivial family of polynomially growing free-by-cyclic groups. The paper is largely self-contained away from Lemmas 3.1–3.2: Section 4 proves explicit growth and distortion estimates, Proposition 5.1 handles the 0-twisted case cleanly using the classical free-group conjugacy lemma, Section 8 gives an explicit polynomial-time enumeration, and Lemma 8.4 gives a constructive replacement that reduces the quadratic bound to a linear one. The proofs are first-principles, with no fitted constants, and the algorithm in Section 10 is explicit enough to serve as a template for more general polynomially growing automorphisms.

major comments (2)
  1. [Section 3, Lemmas 3.1 and 3.2] The paper leaves the proofs of both structural lemmas as exercises and cites [DR13] for 'very similar observations'. This is not a cosmetic omission: Lemmas 3.1 and 3.2 assert that φ and φ^{-1} send each rank-i piece to a piece of the same type with no cancellation or merging between adjacent image pieces, and this fact is used in Proposition 4.4, Lemma 4.8, Lemma 5.2, Corollary 6.2, Proposition 7.1, and Lemma 8.2. For a piece of the form a_i u, the word φ^{-1}(a_i) ends in a_{i-1}^{-1} (see equation (2)), so if u begins with a_{i-1} there is potential cancellation; the claim that the reduced image is again a piece of the same type requires a rank-by-rank boundary analysis that is not present. If either lemma failed for some piece type, the linear bound in Lemma 8.1 and the polynomial-time enumeration in Lemma 8.2 could collapse. The authors should either provide complete proofs of Lemmas 3.1 and 3.2 or give a precise statement-and-proof reference that covers exactly this automorphism and this piece decomposition.
  2. [Section 9] Theorem 1 asserts CL(n)≃n, which requires both an upper and a lower bound. The proof in Section 9 is introduced as 'We will establish a linear upper bound on the conjugator length of H' and proves only the upper bound; no lower bound for CL is established anywhere in the paper. The lower bound is not automatic from the definitions (abelian groups have CL(n)=0). For H_m it can be proved by a short argument, for example by considering u=a_1^n a_2 a_1^{-n} and v=a_2 in F⊂H_m: any conjugator must have s-exponent 0, since φ^r(a_2)=a_2 a_1^r is not conjugate to a_2 in F for r≠0, and then the free-group conjugator a_1^n is forced. But this argument is not in the manuscript, so Theorem 1 as stated is not fully proved.
minor comments (4)
  1. [Section 1] In the paragraph beginning 'The proofs is this paper are largely combinatorial', 'proofs is' should be 'proofs in'.
  2. [Section 10, Step 3] The time bound 'polynomial in |p|+ℓ(\tilde v)+ℓ(\tilde v)' contains a duplicated \tilde v; it should read |p|+ℓ(\tilde u)+ℓ(\tilde v).
  3. [References] The reference [BFW19] contains the typo 'arViv' for 'arXiv', and [O'C] lacks a year and journal/arXiv identifier; please complete the bibliographic data.
  4. [Section 11] Lemma 11.1 is justified only by 'a straightforward analysis of annular diagrams'; since this section is explicitly an alternative approach and the main proof is completed in Sections 8–10, a full proof is not required, but the statement should clearly indicate that it is a version of Collins' Lemma with the stated simplifying assumptions.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: The proof of Theorems 1 and 2 is a first-principles piece-decomposition argument; the only flagged item is the unproved, self-cited structural Lemmas 3.1-3.2, which is a completeness gap rather than a circular reduction.

full rationale

The central derivation chain is genuine: conjugacy in H_m is reduced to 0-, H-, and I-twisted conjugacy problems in the free group, and the linear conjugator bound and polynomial-time algorithms are proved by constructing explicit conjugators and bounding their lengths via piece decompositions, growth estimates, and exhaustive search over forms whose sizes are polynomially bounded. No constant in Theorem 1 or Theorem 2 is fitted to data, and neither theorem is used as an input to its own proof. Self-citations appear in the paper, but they are not load-bearing in a circular way: [DR13] supplies the piece-decomposition tool; [AS16] supplies a known relative-hyperbolicity reduction; [BR] and [BRSa] are described as related or forthcoming work and are not the source of Theorems 1 or 2. The one item that deserves explicit flagging is Section 3.3: 'We leave the proofs of Lemmas 3.1 and 3.2 as exercises. Very similar observations are made in [DR13].' Lemmas 3.1 and 3.2 are indeed used pervasively (notably in Proposition 4.4, Lemma 5.2, Corollary 6.2, Proposition 7.1, and Lemma 8.1), and [DR13] overlaps with one of the present authors. However, the content of these lemmas is a structural claim about pieces and cancellation under phi^{±1}, not a restatement of the linear conjugator bound or of the polynomial-time solvability that the paper proves. Thus the omission is a completeness and verification gap, and a mild self-citation, but not a circular reduction: the cited result is external published work and does not assume the paper's main theorems.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof introduces no free parameters (the constants A_i, B_i, C_i, D_i, K_i are proven to exist and are not fitted to data), and it posits no new mathematical objects. The only external assumptions are standard background results and the unproved piece-decomposition lemmas.

assumptions (3)
  • standard math ZFC set theory and standard mathematical reasoning
    Implicit throughout the proofs.
  • standard math Lemma 2.1: classical conjugacy theorem in free groups
    Used for the 0-twisted conjugacy problem and the rank-1 case; cited to [LS07].
  • domain assumption Lemmas 3.1 and 3.2: piece decompositions are preserved under phi and phi^{-1} with no cancellation between pieces
    Stated without proof, left as exercises, relying on [DR13]; foundational for Sections 4-9.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Conjugacy in a family of free-by-cyclic groups." pith.science (2026). https://pith.science/paper/BL7FMOWI

@misc{pith2026250601248,
  author       = {Pith},
  title        = {Pith review of: Conjugacy in a family of free-by-cyclic groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BL7FMOWI}},
  note         = {Machine review of arXiv:2506.01248}
}
abstract

We analyse the geometry and complexity of the conjugacy problem in a family of free-by-cyclic groups $H_m=F_m\rtimes\mathbb{Z}$ where the defining free-group automorphism is positive and polynomially growing. We prove that the conjugator length function of $H_m$ is linear, and describe polynomial-time solutions to the conjugacy problem and conjugacy search problem in $H_m$.

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Conjugator length in finitely presented groups

    math.GR 2026-07 accept novelty 6.0 of 10

    The conjugator length function is quadratic for the integral Heisenberg group and Stallings' group, and cyclic-subgroup distortion can be promoted to conjugator length.

  2. Conjugator length of locally compact groups of Euclidean isometries

    math.GR 2025-07 reject novelty 6.0 of 10

    A claim of at most linear conjugator length growth for split locally compact Euclidean isometry groups is false; the full isometry group of the plane already gives unbounded conjugator lengths.

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages · cited by 2 Pith papers

  1. [1]

    Antol \' n and A

    Y. Antol \' n and A. W. Sale. Permute and conjugate: the conjugacy problem in relatively hyperbolic groups. Bull. Lond. Math. Soc. , 48(4):657--675, 2016

    work page 2016

  2. [2]

    Baumslag, M

    G. Baumslag, M. R. Bridson, C. F. Miller, and H. Short. Finitely presented subgroups of automatic groups and their isoperimetric functions. J. London Math. Soc. (2) , 56(2):292--304, 1997

    work page 1997

  3. [3]

    Bestvina, M

    M. Bestvina, M. Feighn, and M. Handel. The T its alternative for Out (F_n) . I . D ynamics of exponentially-growing automorphisms. Ann. of Math. (2) , 151(2):517--623, 2000

    work page 2000

  4. [4]

    Bestvina, M

    M. Bestvina, M. Feighn, and M. Handel. The T its alternative for Out (F_n) . II . A K olchin type theorem. Ann. of Math. (2) , 161(1):1--59, 2005

    work page 2005

  5. [5]

    Farrell-Jones Conjecture for free-by-cyclic groups

    M. Bestvina, K. Fujiwara, and D. Wigglesworth. The F arrell-- J ones conjecture for free-by-cyclic groups. arViv:1906.00069 https://arxiv.org/pdf/1906.00069.pdf , 2019

    work page Pith review arXiv 1906

  6. [6]

    M. R. Bridson and D. Groves. The quadratic isoperimetric inequality for mapping tori of free group automorphisms. Mem. Amer. Math. Soc. , 203(955):xii+152, 2010

    work page 2010

  7. [7]

    Bestvina and M

    M. Bestvina and M. Handel. Train tracks and automorphisms of free groups. Ann. of Math. (2) , 135(1):1--51, 1992

    work page 1992

  8. [8]

    M. R. Bridson and A. Haefliger. Metric Spaces of Non-positive Curvature . Number 319 in Grundlehren der mathematischen Wissenschaften. Springer Verlag, 1999

    work page 1999

Show all 34 references
  1. [9]

    R. G. Burns, A. Karrass, and D. Solitar. A note on groups with separable finitely generated subgroups. Bull. Austral. Math. Soc. , 36(1):153--160, 1987

    1987

  2. [10]

    Bogopolski, A

    O. Bogopolski, A. Martino, O. Maslakova, and E. Ventura. The conjugacy problem is solvable in free-by-cyclic groups. Bull. London Math. Soc. , 38(5):787--794, 2006

    2006

  3. [11]

    M. R. Bridson and T. R. Riley. The lengths of conjugators in the model filiform groups. In preparation

  4. [12]

    M. R. Bridson and T. R. Riley. Extrinsic versus intrinsic diameter for R iemannian filling-discs and van K ampen diagrams. J. Diff. Geom. , 82(1):115--154, 2009

    2009

  5. [13]

    Baker and T

    O. Baker and T. Riley. Cannon- T hurston maps, subgroup distortion, and hyperbolic hydra. Groups Geom. Dyn. , 14(1):255--282, 2020

    2020

  6. [14]

    M. R. Bridson. Polynomial D ehn functions and the length of asynchronously automatic structures. Proc. London Math. Soc. , 85(2):441--465, 2002

    2002

  7. [15]

    M. R. Bridson, T. R. Riley, and A. Sale. Bounded conjugators in mapping tori of triangular free-group automorphisms. In preparation

  8. [16]

    M. R. Bridson, T. R. Riley, and A. Sale. Conjugator length in finitely presented groups. In preparation

  9. [17]

    I. Bumagin. Time complexity of the conjugacy problem in relatively hyperbolic groups. Internat. J. Algebra Comput. , 25(5):689--723, 2015

    2015

  10. [18]

    J. O. Button. Mapping tori with first B etti number at least two. J. Math. Soc. Japan , 59(2):351--370, 2007

    2007

  11. [19]

    C. H. Cashen and N. Macura. Line patterns in free groups. Geom. Topol. , 15(3):1419--1475, 2011

    2011

  12. [20]

    D. J. Collins. On embedding groups and the conjugacy problem. J. London Math. Soc. (2) , 1:674--682, 1969

    1969

  13. [21]

    Dison, E

    W. Dison, E. Einstein, and T. R. Riley. Taming the hydra: the word problem and extreme integer compression. Internat. J. Algebra Comput. , 28(7):1299--1381, 2018

    2018

  14. [22]

    Dison and T

    W. Dison and T. R. Riley. Hydra groups. Comment. Math. Helv. , 88(3):507--540, 2013

    2013

  15. [23]

    Epstein and D

    D. Epstein and D. Holt. The linearity of the conjugacy problem in word-hyperbolic groups. Internat. J. Algebra Comput. , 16(2):287--305, 2006

    2006

  16. [24]

    S. M. Gersten. Quadratic divergence of geodesics in CAT (0) spaces. Geom. Funct. Anal. , 4(1):37--51, 1994

    1994

  17. [25]

    R. Ji, C. Ogle, and B. Ramsey. Relatively hyperbolic groups, rapid decay algebras and a generalization of the B ass conjecture. J. Noncommut. Geom. , 4(1):83--124, 2010. With an appendix by Ogle

    2010

  18. [26]

    G. Levitt. Counting growth types of automorphisms of free groups. Geom. Funct. Anal. , 19(4):1119--1146, 2009

    2009

  19. [27]

    Lohrey and S

    M. Lohrey and S. Schleimer. Efficient computation in groups via compression. In Proc. Computer Science in Russia (CSR 2007) , volume 4649 of Lecture Notes in Computer Science , pages 249--258. Springer, 2007

    2007

  20. [28]

    I. G. Lys \"e nok. Some algorithmic properties of hyperbolic groups. Izv. Akad. Nauk SSSR Ser. Mat. , 53(4):814--832, 912, 1989

    1989

  21. [29]

    N. Macura. Detour functions and quasi-isometries. Q. J. Math. , 53(2):207--239, 2002

    2002

  22. [30]

    N. Macura. C AT (0) spaces with polynomial divergence of geodesics. Geom. Dedicata , 163:361--378, 2013

    2013

  23. [31]

    O'Connor

    Z. O'Connor. Conjugacy search problem for relatively hyperbolic groups. http://arxiv.org/abs/1211.5561 arXiv:1211.5561

    arXiv

  24. [32]

    Pueschel

    K. Pueschel. Hydra group doubles are not residually finite. Groups Complex. Cryptol. , 8(2):163--170, 2016

    2016

  25. [33]

    Samuelson

    P. Samuelson. On CAT (0) structures for free--by--cyclic groups. Topology Appl. , 153(15):2823--2833, 2006

    2006

  26. [34]

    Schleimer

    S. Schleimer. Polynomial-time word problems. Comment. Math. Helv. , 83(4):741--765, 2008

    2008

Pith tools

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