23
votes
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
2answers
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
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 ...
7
votes
4answers
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
0answers
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
2answers
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 ...