PaperlayerView exact revision on arXiv

Source-linked AI summary

Conjugacy problems in higher-dimensional Thompson groups

Ville Salo

arXiv:2610.11124v1math.GRcs.FLmath.DS

TL;DR

The paper asks whether topological conjugacy can be decided for elements of higher-dimensional Thompson groups. It reduces Turing-machine halting to the conjugacy behavior of constructed elements, proving undecidability for nV when n ≥ 2. When the machine does not halt, their dynamics are distinguished through visits to minimal subsystems of the germ-aperiodic set.

  • Problem

    The paper studies whether topological conjugacy of elements in higher-dimensional Thompson groups is decidable, a question distinct from conjugacy within the group.

    Source: §1 · p. 1

  • Method

    The reduction effectively constructs group elements from a Turing machine, using reversible simulation and modifications that encode different dynamical behavior.

    Source: §1 · p. 1, §4 · pp. 5–6

  • Results

    For n ≥ 2, the relations CPi(nV), 1 ≤ i ≤ 4, are undecidable; the constructed pair is involution-conjugate if the machine halts on empty input and remains nonconjugate after every allowed product if it does not.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    In the nonhalting case, visits to minimal subsystems of the germ-aperiodic set distinguish the constructed elements’ dynamics.

    Source: §5.3 · p. 12

    The argument proves undecidability but does not give a sharper upper bound.

    Source: §7 · p. 16

Abstract

from arXiv · show

We prove that topological conjugacy of elements of the Brin--Thompson group $nV$ is undecidable for every $n\geq2$. From a Turing machine $T$, the reduction produces two elements of $nV$, which are conjugate by an involution in $nV$ if $T$ halts on the empty tape. If $T$ does not halt on the empty tape, the topological dynamics of the two group elements are distinguished by their visits to minimal subsystems of the set of (germ-)aperiodic points. In these groups, and any finitely-generated supergroups inside the homeomorphism group of Cantor space, we also obtain undecidability of the Whitehead problem (the problem of being in the same automorphism orbit), and undecidability of group-theoretic conjugacy.

1 Introduction

The paper extends undecidability results for conjugacy in 2V and reversible one-head machines to topological conjugacy. Its reduction maps a Turing machine to group elements whose conjugacy behavior distinguishes whether the machine halts on empty input.

1 Introduction

  • The conjugacy problem asks whether two group elements are conjugate within the group, while topological conjugacy allows any homeomorphism of the underlying Cantor space.An obstruction to conjugacy within a group need not obstruct topological conjugacy.Source: §1 · p. 1
  • The paper strengthens prior undecidability results for conjugacy in 2V and reversible one-head machines to topological conjugacy, using a construction based on reversible simulation.The construction is almost the one used in, but uses simulated tapes instead of conveyor belts.Source: §1 · p. 1

1.1 Conjugacy relations and the main result

  • A Turing machine can be effectively mapped to f and g that are conjugate by an involution if it halts on empty input, and remain nonconjugate after products with any nonempty compact metrizable space if it does not halt.The construction is stated for one-head machine groups over infinite mixing shifts of finite type.Source: §1.1 · p. 2
  • For each n ≥ 2, CPi(nV), 1 ≤ i ≤ 4, are undecidable; the same four undecidability conclusions hold for RTM(k, s) in the moving-tape model.For CP1(nV) and CP2(nV), the supplied passage also states Σ0_1-completeness.Source: §1.1 · p. 2
  • The undecidability results extend to supergroups when constructed elements can be effectively translated into their inputs; the paper bases its construction directly on.It notes that other techniques might achieve similar results, perhaps with stronger control over the constructed homeomorphisms’ dynamics.Source: §1.1 · p. 2

2 Preliminaries

The preliminaries define the shift spaces and local machine actions used in the reduction, then establish how local density connects automorphism-orbit relations to topological conjugacy. For the groups considered, Rubin’s theorem supplies that connection.

2.1 Local rewrites and one-head machines

  • A subshift is a closed shift-invariant subset of a full shift, and an infinite mixing shift of finite type has membership determined by finitely many forbidden words.Mixing means any two allowed words can be joined by allowed words of every sufficiently large length.Source: §2.1 · p. 2
  • Local-rewrite maps act on bounded tape windows, replacing local words while defining homeomorphisms; length-preserving maps change only boundedly many cells and shift the tape by a bounded amount.The length-preserving subgroup consists of maps whose output-word lengths sum to the input-window length for every allowed input.Source: §2.1 · p. 3
  • One-head machines are length-preserving local maps acting on configurations and states; the moving-head model additionally tracks head position on the tape.For the binary full shift, local rewrites yield 2V, and the same transformations act on the first two coordinates in nV while fixing the others.Source: §2.1 · p. 3

2.2 Rubin’s reconstruction theorem

  • Rubin’s theorem says an isomorphism between locally dense actions on suitable spaces is induced by a homeomorphism, which makes automorphism-conjugate elements topologically conjugate.The paper uses this to establish CP2(G) ⊆ CP3(G).Source: §2.2 · p. 4
  • The action of Gu_X on an infinite mixing shift of finite type is locally dense, and local density also holds for nV and passes to supergroups.Equal-length words with matching memory-radius end contexts can be exchanged inside a fixed interval to move an orbit into any chosen subcylinder.Source: §2.2 · p. 4

3 Overview

The overview presents a simulation chain from a Turing machine to the final homeomorphisms. The resulting pair is modified so its dynamics distinguish halting from nonhalting.

3 Overview

  • Solid arrows represent software simulation on encoded configurations, while dashed arrows represent other kinds of modification.The transition from the counter machine to the one-head machines follows, and the counter machine construction is based on.Source: §3 · pp. 4–5
  • The construction’s stack begins with a Turing machine, passes through a reversible counter machine and one-head machines, and ends with a homeomorphism in Gu_X.The final f and g are minor modifications of that homeomorphism.Source: §3 · p. 4
  • The final maps toggle certain encoded bits differently, making their dynamics distinct when the original Turing machine does not halt.The construction is almost that of, but uses tape segments instead of conveyor belts.Source: §3 · p. 5

4 The one-head machines used in the reduction

The reduction builds a completed one-head machine from a reversible counter-machine simulation, using recursive calls and a global time arrow. Its behavior separates the halting and nonhalting cases, while a one-visit construction provides a further orbit property in the nonhalting case.

4 The one-head machines used in the reduction

  • The reversible counter machine C is constructed so its canonical run from empty counters is finite exactly when T halts, and C has no infinite backward computation.The clock-counter modification supplies the mortal-inverse property.Source: §4 · p. 5
  • M0 simulates C on a tape where the head state records C's state and zero-block lengths encode the two counters; @12 marks a fresh simulation with both counters zero.An unexpected symbol outside an expanding counter zone reverses the internal direction; invalid or halting transitions make the partial computation undefined.Source: §4 · p. 5
  • M inserts a tagged fresh call when a search reaches a sufficiently long zero block, suspending the parent state and restoring it when the child returns.The child runs C forward even if the parent's stored internal direction is backward.Source: §4 · pp. 5–6
  • M treats terra cognita as the expected configuration language and halts on an incorrect delimiter, but an error just beyond a zone does not halt it until the zone is extended.This convention matters when placing a segment boundary beside a delimiter.Source: §4 · p. 6
  • If T halts, H has finite order; if T does not halt, its germ-aperiodic set has exactly two minimal subsystems, one in each global-arrow layer.In the nonhalting case, every infinite tail with fixed arrow a accumulates on K_a.Source: §4 · p. 7
  • When T halts, the canonical computation of C terminates, and two sufficiently spacious recursive-call terminations make H periodic.If all recursive searches instead have bounded space, their uniform bound also makes H periodic.Source: §4 · pp. 5, 7
  • The nonhalting minimal subsystems K_a are orbit closures of germ-aperiodic fresh-call configurations with recurrent state s* and global arrow a.The fresh-call configuration is germ-aperiodic because the simulated canonical computation never halts and its counters grow without bound.Source: §4 · pp. 8–9

4.1 A one-visit computation with constant global arrow

  • The one-visit lemma gives a nonhalting bi-infinite M-orbit that stays in the nonnegative coordinates and visits coordinate 0 exactly once; its corresponding H-orbit accumulates on K0 in both time tails.The construction uses increasingly long zero blocks so child computations return only after increasingly long intervals, while recursive work stays to the right.Source: §4.1 · pp. 9–10

5 Encoding and the two homeomorphisms

The construction encodes a simulated tape in legal blocks and defines two local homeomorphisms that differ by a head-bit flip. If the Turing machine halts, an involution conjugates them; if it does not, they have four minimal subsystems on their germ-aperiodic sets.

5.1 Simulated tape segments

  • Equal-length exchangeable words encode tape cells, letting local rewrites simulate H while remaining in the shift space X.Active configurations use a V-word at the head and W-words elsewhere in a maximal simulated segment; blocks outside it represent #-tails.Source: §5.1 · pp. 10–11
  • The maps f and g both simulate H and flip tape bit c at the left boundary, while only g flips head bit b.On finite simulated segments, the completed dynamics is periodic.Source: §5.1 · p. 11

5.2 The halting case: an explicit involutory conjugacy

  • When T halts, an involution k in the group satisfies kfk = g, and t, f, and g have finite order.The conjugacy uses a locally readable tape bit to define a correction that toggles the head bit; f and g have finite order because the tape-bit parity cancels after two repetitions.Source: §5.2 · pp. 11–12

5.3 The four germ-aperiodic minimal subsystems

  • When T does not halt, the four sets Xa,b are exactly the minimal subsystems of both maps on their germ-aperiodic sets.On each infinite coded tape the maps agree, and the encoded dynamics is minimal; finite simulated segments are locally periodic and excluded from the germ-aperiodic set.Source: §5.3 · p. 12

6 The dynamical obstruction

The paper distinguishes the nonhalting maps using transitions between minimal subsystems of germ-aperiodic points. The distinction persists after adjoining an identity coordinate, supporting the reduction in higher-dimensional settings.

The dynamical obstruction

  • P3 records whether the transition graph of minimal subsystems on the germ-aperiodic set contains a directed injective path with three nodes.An edge represents points arbitrarily close to one minimal subsystem whose forward iterate is arbitrarily close to another.Source: §6 · p. 13
  • If T does not halt, P3(g) holds and P3(f) fails, so f and g are not topologically conjugate; P3(g) is established by transitions X0,0 ⇝ X0,1 and X0,1 ⇝ X1,1.Source: §6 · p. 13
  • The P3 distinction is preserved after taking a product with any nonempty compact metrizable identity coordinate.The product argument preserves germ-aperiodicity and the transition graph within each fixed coordinate fiber.Source: §6 · p. 14

7 Consequences for groups and computability

The reduction extends undecidability from 2V to higher-dimensional Thompson groups and to listed supergroups containing effective copies of the relevant actions. For nV, ordinary and automorphism-conjugacy are Σ⁰₁-complete, while the paper leaves the sharper complexity of topological conjugacy open.

Consequences for groups and computability

  • Every listed group containing an effective copy of the local-rule group on an infinite mixing SFT has undecidable CPi relations, with CP1 recursively inseparable from the complement of CP4.The reduction maps halting inputs into CP1 and nonhalting inputs outside CP4.Source: §7 · p. 15
  • Finitely generated supergroups of 2V inside Cantor-space homeomorphisms also have undecidable CPi relations.The standard copy of 2V has an effective inclusion into such a supergroup.Source: §7 · p. 15
  • The four relations CPi are undecidable in nV, reversible one-head machine groups, and listed supergroups containing the indicated standard actions by effective inclusions.For the stated cases, CP1 is recursively inseparable from the complement of CP4.Source: §7 · p. 15

Computability consequences

  • For finitely presented groups with decidable word problem, ordinary conjugacy and automorphism-conjugacy are recursively enumerable.Candidate conjugators and mutually inverse automorphisms can be enumerated and checked using the word problem.Source: §7 · pp. 15–16
  • For n ≥ 2, ordinary conjugacy and automorphism-conjugacy in nV are Σ⁰₁-complete under computable many-one reductions.Finite prefix-table descriptions give a decidable word problem, and the halting reduction supplies hardness.Source: §7 · p. 16
  • For topological conjugacy in nV, compatible finite clopen-partition codes give a Σ¹₁ upper bound, but the argument proves no sharper bound.Source: §7 · p. 16

Open questions

  • The paper leaves the difficulty of topological conjugacy for the moving-head model uninvestigated.Source: §7 · p. 16

AI acknowledgements

The acknowledgements credit Astra with several mathematical observations and proofs, and Claude with the substance of Remark 6.3.

AI acknowledgements

  • Astra is credited with the second time arrow observation, Remark 7.6, a cross-section-free proof of Lemma 5.1, and a general-properties proof of Lemma 7.4; Claude is credited with Remark 6.3.Source: AI acknowledgements · p. 16
Loading 2610.11124v1…