Nearly-linear solution to the word problem for 3-manifold groups Article Swipe

PDF

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2407.18029

We show that the word problem for any 3-manifold group is solvable in time $O(n\log^3 n)$. Our main contribution is the proof that the word problem for admissible graphs of groups, in the sense of Croke and Kleiner, is solvable in $O(n\log n)$; this covers fundamental groups of non-geometric graph manifolds. Similar methods also give that the word problem for free products can be solved "almost as quickly" as the word problem in the factors.

Related Topics

Mechanical Engineering

Concepts

Word (group theory) Manifold (fluid mechanics) Mathematics Pure mathematics Combinatorics Geometry Engineering Mechanical engineering

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2407.18029
PDF: https://arxiv.org/pdf/2407.18029
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4402619119

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4402619119

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2407.18029

Digital Object Identifier
Title: Nearly-linear solution to the word problem for 3-manifold groups

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-07-25

Full publication date if available
Authors: Alessandro Sisto, Stefanie Zbinden

List of authors in order
Landing page: https://arxiv.org/abs/2407.18029

Publisher landing page
PDF URL: https://arxiv.org/pdf/2407.18029

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2407.18029

Direct OA link when available
Concepts: Word (group theory), Manifold (fluid mechanics), Mathematics, Pure mathematics, Combinatorics, Geometry, Engineering, Mechanical engineering

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4402619119
doi	https://doi.org/10.48550/arxiv.2407.18029
ids.doi	https://doi.org/10.48550/arxiv.2407.18029
ids.openalex	https://openalex.org/W4402619119
fwci
type	preprint
title	Nearly-linear solution to the word problem for 3-manifold groups
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10304
topics[0].field.id	https://openalex.org/fields/26
topics[0].field.display_name	Mathematics
topics[0].score	0.9952999949455261
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2608
topics[0].subfield.display_name	Geometry and Topology
topics[0].display_name	Geometric and Algebraic Topology
topics[1].id	https://openalex.org/T10996
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9851999878883362
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1704
topics[1].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[1].display_name	Computational Geometry and Mesh Generation
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C90805587
concepts[0].level	2
concepts[0].score	0.6261281967163086
concepts[0].wikidata	https://www.wikidata.org/wiki/Q10944557
concepts[0].display_name	Word (group theory)
concepts[1].id	https://openalex.org/C529865628
concepts[1].level	2
concepts[1].score	0.532729983329773
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1790740
concepts[1].display_name	Manifold (fluid mechanics)
concepts[2].id	https://openalex.org/C33923547
concepts[2].level	0
concepts[2].score	0.49525824189186096
concepts[2].wikidata	https://www.wikidata.org/wiki/Q395
concepts[2].display_name	Mathematics
concepts[3].id	https://openalex.org/C202444582
concepts[3].level	1
concepts[3].score	0.4137614369392395
concepts[3].wikidata	https://www.wikidata.org/wiki/Q837863
concepts[3].display_name	Pure mathematics
concepts[4].id	https://openalex.org/C114614502
concepts[4].level	1
concepts[4].score	0.3716112971305847
concepts[4].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[4].display_name	Combinatorics
concepts[5].id	https://openalex.org/C2524010
concepts[5].level	1
concepts[5].score	0.1386856734752655
concepts[5].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[5].display_name	Geometry
concepts[6].id	https://openalex.org/C127413603
concepts[6].level	0
concepts[6].score	0.09276461601257324
concepts[6].wikidata	https://www.wikidata.org/wiki/Q11023
concepts[6].display_name	Engineering
concepts[7].id	https://openalex.org/C78519656
concepts[7].level	1
concepts[7].score	0.0586584210395813
concepts[7].wikidata	https://www.wikidata.org/wiki/Q101333
concepts[7].display_name	Mechanical engineering
keywords[0].id	https://openalex.org/keywords/word
keywords[0].score	0.6261281967163086
keywords[0].display_name	Word (group theory)
keywords[1].id	https://openalex.org/keywords/manifold
keywords[1].score	0.532729983329773
keywords[1].display_name	Manifold (fluid mechanics)
keywords[2].id	https://openalex.org/keywords/mathematics
keywords[2].score	0.49525824189186096
keywords[2].display_name	Mathematics
keywords[3].id	https://openalex.org/keywords/pure-mathematics
keywords[3].score	0.4137614369392395
keywords[3].display_name	Pure mathematics
keywords[4].id	https://openalex.org/keywords/combinatorics
keywords[4].score	0.3716112971305847
keywords[4].display_name	Combinatorics
keywords[5].id	https://openalex.org/keywords/geometry
keywords[5].score	0.1386856734752655
keywords[5].display_name	Geometry
keywords[6].id	https://openalex.org/keywords/engineering
keywords[6].score	0.09276461601257324
keywords[6].display_name	Engineering
keywords[7].id	https://openalex.org/keywords/mechanical-engineering
keywords[7].score	0.0586584210395813
keywords[7].display_name	Mechanical engineering
language	en
locations[0].id	pmh:oai:arXiv.org:2407.18029
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2407.18029
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2407.18029
locations[1].id	doi:10.48550/arxiv.2407.18029
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2407.18029
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5009383506
authorships[0].author.orcid	https://orcid.org/0000-0002-4630-3619
authorships[0].author.display_name	Alessandro Sisto
authorships[0].author_position	first
authorships[0].raw_author_name	Sisto, Alessandro
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5015492432
authorships[1].author.orcid	https://orcid.org/0000-0001-5229-3296
authorships[1].author.display_name	Stefanie Zbinden
authorships[1].author_position	last
authorships[1].raw_author_name	Zbinden, Stefanie
authorships[1].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2407.18029
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Nearly-linear solution to the word problem for 3-manifold groups
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10304
primary_topic.field.id	https://openalex.org/fields/26
primary_topic.field.display_name	Mathematics
primary_topic.score	0.9952999949455261
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2608
primary_topic.subfield.display_name	Geometry and Topology
primary_topic.display_name	Geometric and Algebraic Topology
related_works	https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2600246793, https://openalex.org/W4238204885
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2407.18029
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2407.18029
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2407.18029
primary_location.id	pmh:oai:arXiv.org:2407.18029
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2407.18029
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2407.18029
publication_date	2024-07-25
publication_year	2024
referenced_works_count	0
abstract_inverted_index.We	0
abstract_inverted_index.as	66, 68
abstract_inverted_index.be	63
abstract_inverted_index.in	12, 31, 40, 72
abstract_inverted_index.is	10, 19, 38
abstract_inverted_index.of	29, 34, 47
abstract_inverted_index.Our	16
abstract_inverted_index.and	36
abstract_inverted_index.any	7
abstract_inverted_index.can	62
abstract_inverted_index.for	6, 26, 59
abstract_inverted_index.the	3, 20, 23, 32, 56, 69, 73
abstract_inverted_index.also	53
abstract_inverted_index.free	60
abstract_inverted_index.give	54
abstract_inverted_index.main	17
abstract_inverted_index.n)$.	15
abstract_inverted_index.n)$;	42
abstract_inverted_index.show	1
abstract_inverted_index.that	2, 22, 55
abstract_inverted_index.this	43
abstract_inverted_index.time	13
abstract_inverted_index.word	4, 24, 57, 70
abstract_inverted_index.Croke	35
abstract_inverted_index.graph	49
abstract_inverted_index.group	9
abstract_inverted_index.proof	21
abstract_inverted_index.sense	33
abstract_inverted_index.covers	44
abstract_inverted_index.graphs	28
abstract_inverted_index.groups	46
abstract_inverted_index.solved	64
abstract_inverted_index."almost	65
abstract_inverted_index.Similar	51
abstract_inverted_index.groups,	30
abstract_inverted_index.methods	52
abstract_inverted_index.problem	5, 25, 58, 71
abstract_inverted_index.$O(n\log	41
abstract_inverted_index.Kleiner,	37
abstract_inverted_index.factors.	74
abstract_inverted_index.products	61
abstract_inverted_index.quickly"	67
abstract_inverted_index.solvable	11, 39
abstract_inverted_index.$O(n\log^3	14
abstract_inverted_index.3-manifold	8
abstract_inverted_index.admissible	27
abstract_inverted_index.manifolds.	50
abstract_inverted_index.fundamental	45
abstract_inverted_index.contribution	18
abstract_inverted_index.non-geometric	48
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile