All Questions
Tagged with computability-theory gr.group-theory
36 questions
10
votes
0
answers
425
views
Function related to length of group presentations: is it computable?
(This question comes from a friend who works in sofic group theory.)
Consider the function $f: \mathbb{N} \to \mathbb{N}$, defined, for any $n \in \mathbb{N}$, by putting $f(n)$ to be the largest ...
- 339
4
votes
1
answer
266
views
Are (group theoretic) Markov properties on groups with decidable word problems, decidable?
(Link to SE duplicate: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems)
The Adian-Rabin theorem says that if a property of ...
- 191
4
votes
0
answers
108
views
Decidability of whether two polynomial bijections generate a free group
I am wondering about the decidability of the following question:
Given two polynomial bijections $f, g$ from the real numbers to the real numbers (with say rational coefficient just to simplify what &...
- 1,075
7
votes
1
answer
452
views
Is the isomorphism problem solvable for torsion-free groups?
Given two finite presentations of torsion-free groups, is there an algorithm to determine whether the given groups are isomorphic or not?
I have found results for narrower classes (for example, they ...
- 6,962
2
votes
0
answers
90
views
decidability special case of column generation problem
I have the following problem:
Input: sub-spaces $V_1, \dots, V_d$ of $\mathbb{Z}^{d}$
Question: are there $v_i \in V_i$ such that the matrix $(v_1, \dots, v_d)$ has determinant $\pm 1$ (equivalently, ...
- 55
3
votes
1
answer
121
views
When does a clone on a two-element set have almost abelian symmetry groups?
Say that a clone (in the sense of universal algebra) $\mathfrak{C}$ has almost abelian symmetry groups (= aasg) iff for each function $f(x_1,...,x_n)\in\mathfrak{C}$ there is an abelian subgroup $A\...
- 21.2k
1
vote
0
answers
77
views
When are normal forms computable in amalgamated produts and HNN extensions
I have had little luck searching for references on the following. I would thank a lot any reference.
What are known conditions that ensure computable normal forms on amalgamated products and HNN ...
- 75
7
votes
0
answers
207
views
Is $E(G)$ recursively presented for finitely presented $G$?
Suppose $G$ is a group. Consider the set $G^G$ of all functions $G \to G$, which forms a group under elementwise multiplication. Now, for all $g \in G$ let’s define $c_g \in G^G$ as the constant ...
- 2,618
2
votes
0
answers
71
views
Empty preimage under homomorphism of finitely presented groups with decidable word problems
Let $G, H$ be finitely presented groups with decidable word problems.
Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
user178109
6
votes
1
answer
350
views
Examples of "natural" finitely generated groups with an undecidable conjugacy problem
I am looking for natural groups with undecidable conjugacy problem. By natural, I mean that the word problem should be decidable, and the group should be given by some natural action. I know that $\...
- 6,652
2
votes
1
answer
361
views
Can primitive recursive functions be simulated in the smallest reasonable primitive recursive group?
Second Edition, completely rewritten with unchanged questions.
The said questions are motivated by the bizarre wording of the concluding § in A Class of
Reversible Primitive Recursive Functions by L. ...
- 347
2
votes
1
answer
127
views
A detail about busy beaverly behavior of distortion functions in graph groups
Say a function $\phi : \mathbb{N} \to \mathbb{N}$ is weakly superrecursive if for any total recursive $\phi : \mathbb{N} \to \mathbb{N}$
we have $\phi(n) > \psi(n)$ for infinitely many $n$. Say it ...
- 6,652
7
votes
1
answer
354
views
Does Higman's embedding theorem hold inside group varieties?
Suppose $\mathfrak{U}$ is a variety of groups. Let's define $F_n(\mathfrak{U})$ as relatively free groups in $\mathfrak{U}$.
Suppose $G \in \mathfrak{U}$ is a finitely generated group. We call $G$ ...
- 2,618
4
votes
0
answers
164
views
Subgroup membership problem for Noetherian groups
I am interested in the status of the subgroup membership problem (MP) for finitely presented Noetherian groups. That is, given a finite presentation $\langle X,R\rangle$ for a Noetherian group,
\begin{...
- 343
36
votes
3
answers
2k
views
Is it decidable to check if an element has finite order or not?
Suppose we have a finitely presented group $G$ with decidable word problem. Is it decidable to check whether a given element $x\in G$ has finite order or infinite?
- 1,281
10
votes
1
answer
396
views
Groups whose word problem can be solved in constant time
Given a finitely generated group $G$, define an encoding of $G$ to be a one-to-one function $\Phi:G\to \bigcup_n \{0,1\}^n$ that sends each group element to a unique finite word. For $a,b\in G$, ...
- 799
9
votes
1
answer
753
views
List of finitely presented groups with undecidable word problem
Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem?
By "representative" I mean "avoiding obvious redundancy", i.e. examples ...
- 343
9
votes
1
answer
674
views
Can you decide whether the commutator subgroup of a f.p. group is f.g?
Is the following algorithmic problem known to be decidable/undecidable?
Input: a finite group presentation $P$.
Decide: is the commutator subgroup of the group presented by $P$ finitely generated?
- 343
6
votes
2
answers
490
views
What is the name of this type of groups?
Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as:
$$G=\langle ...
- 2,233
103
votes
4
answers
5k
views
How feasible is it to prove Kazhdan's property (T) by a computer?
Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually can ...
- 10.1k
6
votes
3
answers
872
views
An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.
Edited (this question contains two versions of a similar question)
Is there some finitely presented group $G$ generated by $g_1,...,g_n$ such that
there is an element $g\in G$ expressed as a finite ...
- 14.3k
18
votes
1
answer
921
views
Automorphism group of the Turing degrees
It is conjectured that the automorphism group of the Turing degrees, $Aut(\mathcal{D})$, is trivial. However, to the best of my knowledge, the current state-of-the-art is that $Aut(\mathcal{D})$ is ...
- 21.2k
7
votes
1
answer
393
views
Status of the Isomorphism problem for automatic groups?
I only ask because I don't know how to look for the answer.
- 1,987
17
votes
0
answers
969
views
Groups generated by 3 involutions
Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$\tau_{r_1(m_1),r_2(m_2)}$ be the ...
- 19.6k
8
votes
1
answer
343
views
The equality problem between conjugate group elements
The Novikov--Boone Theorem, which is perhaps the archetypal local unsolvability result in group theory, states existence of a finitely presented group whose word problem is recursively unsolvable. ...
- 22.1k
81
votes
4
answers
12k
views
Can a group be a universal Turing machine?
This question was inspired by this blog post of Jordan Ellenberg.
Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the ...
- 114k
30
votes
3
answers
3k
views
Is it decidable whether or not a collection of integer matrices generates a free group?
Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
- 18.7k
6
votes
1
answer
357
views
computing abelianizations
Suppose I have a finitely presented group $G,$ and a subgroup $H$ of $G$ given by its finite generating set (given as words in the generators of $G.$ I want to know whether $H/[H, H]$ is finite. Is ...
- 96.4k
14
votes
4
answers
1k
views
(un)decidability in matrix groups
Given a collection of matrices $S=\{M_1, \dots, M_k\}$ in (say) $SL(n, Z), \ n>2$ does $S$ generate $SL(n, Z)?$
Similar are questions are undecidable for $n\geq 4$ (eg, given a set $S$ as above, ...
- 96.4k
14
votes
1
answer
764
views
Finite-dimensional version of the word problem for groups
The (uniform) word problem for groups can be stated in several equivalent ways:
Word Problem for Groups (WP)
Instance: A finite presentation of a group G and an element w of G as a product of ...
- 1,959
17
votes
1
answer
875
views
Which finitely presented groups can be distinguished by decidable properties?
This question continues the line of inquiry
of these
three
questions.
Question. Which finitely presented groups can be
distinguished by decidable properties?
To be precise, let us say that φ is ...
- 236k
15
votes
3
answers
687
views
Do decidable properties of finitely presented groups depend only on the profinitization?
This is a just-for-fun question inspired by this one. Let $P$ be a property of finitely presentable groups. Suppose that
The truth of $P(G)$ only depends on the isomorphism class of $G$.
Given a ...
- 156k
19
votes
4
answers
1k
views
Does every decidable question about finitely presented groups amount to a question about abelian groups?
This question is about an issue left unresolved by Chad
Groft's excellent
question and
John Stillwell's excellent
answer of
it. Since I find the possibility of an affirmative answer
so tantalizing, I ...
- 236k
76
votes
6
answers
9k
views
Which graphs are Cayley graphs?
Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...
- 236k
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 258
9
votes
2
answers
1k
views
Recursive presentations
A recursive presentation of a group is a one in which there is a finite number of generators and the set of relations is recursively enumerable. I found the following quote in Lyndon-Schupp, chapter ...
