# Tagged Questions

**23**

votes

**1**answer

708 views

### How strong is this conjecture? $(Z/nZ)^*$ is generated by “small” elements

Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$.
Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My ...

**2**

votes

**1**answer

474 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**8**

votes

**0**answers

187 views

### Computing van Kampen diagrams

If G is a finitely presented group (with generating set X) and w is a word over X such that
w=1 in G, then the latter can be witnessed by a so called van Kampen diagram for w, which is
a planar ...

**11**

votes

**0**answers

300 views

### Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...

**2**

votes

**1**answer

224 views

### Complexity of establishing finite groups (non)-isomorphism ?

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...

**7**

votes

**2**answers

683 views

### How to compute all irreducible representations of a finite group ? (how GAP is doing this?)

Let us "take" a finite group G. Here "take" I mean any type of group-theoretic description you prefer: e.g. as an explicit subset of GL (or other group) or Cayley table, whatever.
Question: How ...

**4**

votes

**0**answers

367 views

### Computational complexity of multiplication in a nilpotent group?

What is the computational complexity of multiplication in a Carnot group ?
Background: A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition
...

**3**

votes

**1**answer

123 views

### Counting connected fundamental domains of actions on Cayley graphs

The following question arises, for me, from mathematical music theory:
Write $({\Bbb Z}^n,E_n)$ for the Cayley graph of ${\Bbb Z}^n$
relative to standard free generators.
Given a subgroup $L$ of ...

**5**

votes

**2**answers

415 views

### Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...

**9**

votes

**2**answers

308 views

### Do there exist groups with word problems in arbitrary P-degrees?

This has been posted on TCS stack exchange for a while here and hasn't gotten any answers, so I'm trying again here.
It has been known for a long time that, given any r.e. Turing degree, there is a ...

**6**

votes

**1**answer

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 ...

**7**

votes

**4**answers

701 views

### Is the classification of finite p-groups a smooth problem?

Fix a prime $p$. Then the question is about the difficulty of classifying finite $p$-groups. Originally I was going to ask if this was a "wild" problem but thanks to Joel David Hamkins' answer to ...

**2**

votes

**0**answers

215 views

### Finding globally minimal row subsets of an integer matrix which generate the full row span

Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.
Given a subset of the rows of $A$ it is ...

**3**

votes

**2**answers

295 views

### What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?

For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. :
$$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy ...