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?

Improve this question
$\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$
    – Emil Jeřábek
    Commented May 14, 2014 at 23:29
  • $\begingroup$ Aha - interesting. What about non-abelian groups (or other groups of non-huge diameter)? $\endgroup$
    – H A Helfgott
    Commented 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$
    – Jack Schmidt
    Commented May 15, 2014 at 2:27

1 Answer 1

Reset to default
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$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .