7
votes
2answers
443 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 ...
44
votes
1answer
842 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 ...
8
votes
0answers
247 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 ...
6
votes
1answer
265 views

Status of the Isomorphism problem for automatic groups?

I only ask because I don't know how to look for the answer.
10
votes
0answers
462 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 ...
7
votes
1answer
235 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. ...
49
votes
3answers
4k 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 ...
23
votes
2answers
914 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 ...
6
votes
1answer
236 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 ...
11
votes
2answers
695 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, ...
10
votes
1answer
471 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 ...
13
votes
1answer
421 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 ...
15
votes
3answers
533 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 ...
11
votes
4answers
726 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 ...
38
votes
5answers
4k 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 ...
5
votes
1answer
400 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 ...