6
$\begingroup$

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 the least $k$ such that every element $g$ of $G$ can be written as a product $x_1 x_2 \dotsc x_k$, $x_i \in A \cup \{e\}$. We care not just about the diameter, but also about navigation: that is, given $A$ and $g$, we would like to actually find a product $g = x_1 x_2 \dotsc x_j$, $x_i \in A \cup \{e\}$, as quickly as possible.

Now, a product is a very special kind of straight-line program. What is known (for different interesting groups $G$) on the following question: given $A$ and $g$, can we construct quickly a (short) straight-line program that, starting from the elements of $A$, outputs $g$ quickly?

$\endgroup$
3
  • 2
    $\begingroup$ Let $G$ be the group of units of $\mathbb Z/p\mathbb Z$, and $A$ the set consisting of a generator of $G$. Then your problem appears to be equivalent to discrete logarithm, which is not known, but widely assumed, to be not efficiently solvable. Am I missing something? $\endgroup$ May 14, 2014 at 23:29
  • $\begingroup$ Aha - interesting. What about non-abelian groups (or other groups of non-huge diameter)? $\endgroup$ May 14, 2014 at 23:51
  • 3
    $\begingroup$ It depends on how $G$ and $A$ are given. If $A$ is a strong generating set for the permutation group $G$, then yes (this is similar to back-substitution solving). If $A$ is a pcgs and $G$ is a pc-group in vector form, then yes (almost trivially). I believe if $G$ is a constructively recognized factor-tree group (such as a matrix group with recognizable composition factors), and $A$ are the standard generators, then yes (modulo DLP and a few other number theory issues). $\endgroup$ May 15, 2014 at 2:27

1 Answer 1

2
$\begingroup$

Larsen, Michael. Navigating the Cayley graph of ${\rm SL}_2(\Bbb F_p)$. Int. Math. Res. Not. 2003, no. 27, 1465–1471.

Math Review by Tullio G. Ceccherini-Silberstein:

Consider the group ${\rm SL}_2(\Bbb F_p)$ with the generating system $$X=\left\{\left(\begin{matrix} 1&1\\ 0&1\end{matrix}\right),\ \left(\begin{matrix} 1&0\\ 1&1\end{matrix}\right)\right\}$$ The diameter of the Cayley graph $X(p)={\rm Cay}({\rm SL}_2(\Bbb F_p), X)$ is $O(\log p)$ [see A. Lubotzky, Discrete groups, expanding graphs and invariant measures, Progr. Math., 125, Birkhäuser, Basel, 1994; MR1308046 (96g:22018)]: there are two proofs of this fact, both non-constructive. The first one is based on bounding the eigenvalues of the combinatorial Laplacian on $L^2(X(p))$ away from zero; the second one uses the circle method to show that every element in ${\rm {\rm SL}}_2(\Bbb F_p)$ lifts to an element of ${\rm SL}_2(\Bbb Z)$ which has a short word representation [A. Lubotzky, R. S. Phillips and P. C. Sarnak, Combinatorica 8 (1988), no. 3, 261–277; MR0963118 (89m:05099)]. Lubotzky asked for an algorithm producing short word representations of general elements of ${\rm SL}_2(\Bbb F_p)$. In this paper such an algorithm is presented, but for word representations of length $O(\log p \log \log p)$ (rather than $O(\log p)$). More precisely one has the following theorem. There exist constants $c_1$ and $c_2$ such that for any $c_3 < 1$, there exists $c_4$ such that for any prime $p$ and any element in ${\rm SL}_2(\Bbb F_p)$, the algorithm will find a word of length $\leq c_1 \log p \log \log p$ in time $\leq c_4 \log^{c_2} p$ with probability $\geq c_3$.

$\endgroup$
2
  • $\begingroup$ Yes, I know this! This is where the word "navigation" comes from. $\endgroup$ May 17, 2014 at 17:04
  • 1
    $\begingroup$ I thought it should be mentioned. $\endgroup$ May 17, 2014 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.