# Tagged Questions

**6**

votes

**1**answer

219 views

### Fast construction of straight line programs?

Given a group $G$ and a set of generators $A$, we can ask ourselves (and do ask ourselves all the time) to bound the diameter of $G$ with respect to $A$. The diameter, let us recall, is defined to be ...

**3**

votes

**2**answers

126 views

### All Integers from the Smallest Digit Stream with a Window Filter

Let's represent integers with D digits where each digit has B values
(i.e., the base is B and we effectively work only with integers between
1 and B^D). Is it possible to choose a single ...

**3**

votes

**0**answers

152 views

### Finding a basis for the (linear combinations) span of a matrix group, efficiently?

I have an algorithm whose bottleneck is the following task:
Let $\mathbb{F}$ be a finite field.
Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let
$G=\langle ...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

124 views

### Finding particular reduced words for Weyl group elements

I am studying cluster algebra structures on the coordinate rings of partial flag varieties, as defined in the paper Partial flag varieties and preprojective algebras by Geiss, Leclerc and SchrÃ¶er. One ...

**3**

votes

**1**answer

125 views

### Is there an algorithm to compute group presentations of or find generators for the centralizer of a matrix in $GL(n, \mathbb{Z})$?

Let $M \in H \leq GL(n, \mathbb{Z})$. Is there an algorithm that computes either matrix generators or even a group presentation for $C_H(M)$ given generators or a presentation of $H$? Also is ...

**8**

votes

**0**answers

127 views

### Naive Reidemeister-Schreier for $\mathbb Z$ quotients

I have a question about a "standard" variant of the Reidemeister-Schreier algorithm used by topologists when manipulating manifolds they either know or suspect are fibre-bundles over $S^1$.
Say you ...

**4**

votes

**0**answers

160 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**2**

votes

**1**answer

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

**8**

votes

**3**answers

1k views

### Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ?
(Main case - complex numbers, comments on other cases are also welcome. "Given" ...

**9**

votes

**1**answer

287 views

### Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)

Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$.
Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix ...

**6**

votes

**2**answers

438 views

### Algorithm for reducing words in a Coxeter group

Let $W$ be a Coxeter group with set of simple reflections $S$. Suppose that I have chosen a preferred reduced decomposition for every element of $W$. Given an arbitrary word in the alphabet $S$, is ...

**4**

votes

**2**answers

182 views

### Extension of conjugacy problem

Let $F = \langle a,b \rangle$ be a non-abelian free group.
Question: Is there an algorithm that takes as input $x,y,z \in F$ and answers the question whether $x$ is a product of conjugates of $y$ ...

**6**

votes

**2**answers

497 views

### Two groups acting on a set.

Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair ...

**8**

votes

**0**answers

389 views

### Shortest path in Cayley graphs

The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...

**1**

vote

**0**answers

276 views

### Determine the next number in the sequence

This problem originates from a programming interview problem. In that problem, we are asked to convert the array $[a_0, a_1, \cdots, a_{N-1}, b_0, b_1, \cdots, b_{N-1}, c_0, c_1, \cdots, c_{N-1}]$ ...

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

**7**

votes

**1**answer

530 views

### Any nice examples of small cancellation theory appearing in applied mathematics?

Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems?
I ...

**2**

votes

**1**answer

174 views

### Computing a generating set of the kernel of a module

Crossposted from math.stackexchange, since I'm not getting any answer and I think the question is suitable here.
Given a generating set of a $\mathbb{Z_k}$-module $M \subseteq {\mathbb{Z}_k}^n$, is ...

**23**

votes

**2**answers

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

**4**

votes

**1**answer

322 views

### Is there an algorithm for computing Schur multiplier?

Suppose we are given group $G=\langle a_1,\ldots,a_n \mid R_1=1,\ldots R_m=1 \rangle$. Is there an algorithm which computes a finite presentation for the Schur multiplier, i.e. second homology group ...

**5**

votes

**2**answers

460 views

### Lattice reduction in R^3 (R^4) or what is fundamental domain for SL(3,Z) , (SL(4,Z)) ?

Consider a lattice in R^3.
Is the some "canonical" way or ways to choose basis in it ?
I mean in R^2 we can choose a basis |h_1| < |h_2| and |(h_2, h_1)| < 1/2 |h_1|.
Considering lattices with ...

**7**

votes

**2**answers

329 views

### Decidability in Groups

This is not my area of research, but I am curious. Let $G=\left< X|R \right>$ be a finitely presented group, where $X$ and $R$ are finite. There are many questions which are undecidable for all ...

**3**

votes

**0**answers

219 views

### Finding generalised Lyndon words

Let $\Sigma = \lbrace a_1, \ldots, a_n, A_1, \ldots A_n \rbrace$ (where $A_i = a_i^{-1}$) and $\prec$ be a total ordering on $\Sigma$.
Let $\Sigma^*$ be the set of all words (generated by the ...

**6**

votes

**1**answer

484 views

### Testing permutations to see if they generate $S_n$

Alright, so a similar question was recently asked about the theoretical bound for generating certain permutations in polynomial time. I had been thinking about a related problem in algorithms (with ...

**7**

votes

**2**answers

322 views

### Checking whether given binary operation is a group operation

Given a binary function $f: [1..n] \times [1..n] \to [1..n]$ how to check that this operation is a group operation on $[1..n]$?
It's obvious that this can be done in $O(n^3)$ time just by checking ...

**7**

votes

**3**answers

446 views

### Is it decidable whether a given set generates the whole group?

Upon thinking about this question, I have a feeling that there is an interesting general problem like that, but I cannot verbalise it. Here is an approximation.
The question is: given a finitely ...

**8**

votes

**3**answers

292 views

### Searching the symmetric group

You want to design a set of yes/no questions for quickly searching the symmetric group. The questions have to be of the form "Does your permutation move $a_1$ to $b_1$ or $a_2$ to $b_2$ or ... or ...