6
votes
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
3answers
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
1answer
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
2answers
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
2answers
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
2answers
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
0answers
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
0answers
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
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 ...
7
votes
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
2answers
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
3answers
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
3answers
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 ...