2
$\begingroup$

This might be a rather broad question, and I'll be satisfied with some intuition and pointers to relevant literature. However, I'll certainly fill in more context and details based on any feedback.

Suppose we have a finite group $G$ of size $n$ and a symmetric generating set $S$ of size $d$, consider the reduced words formed using $S$ and their images in $G$. I'd like to find a small enough subset $B \subset G$ (say $|B|=n/d$) such that "many" reduced words of length $k$ not only evaluate to an element of $B$ but stay within $B$ at each step on the way. That is, suppose $s_1 s_2 \dots s_k$ is a reduced word. Then $$s_1s_2 \dots s_j \in B$$ for every $1 \leq j \leq k$.

This can also be visualized as a reduced walk on the corresponding Cayley graph staying within a subset $B$. In that interpretation, we would be interested in the quality of sampling vertices using a random (reduced) walk on the graph. This is closely related to graph expansion and the Ramanujan property.

Anyway, so given a group $G$ and generating set $S$, I am interested in the choice of $B \subset G$ of small size so that there are as many reduced words of length $k$ entirely within $B$ as possible. Two candidate choices I am trying out for $B$ are:

1) A ball around $1$ of appropriately large radius

2) A subgroup constructed using a subset of $S$

Are my candidates reasonable? Essentially this is a kind of isoperimetric problem, and more than finding the worst set $B$ algorithmically, my real aim is to seek out a group (and generating set) such that for all small subsets $B$, the number of reduced words of length $k$ staying within $B$ is asymptotically small as $k$ grows large.

I do realize all this might depend heavily on the precise group and generating set. So for concreteness, I'm working with $PSL(2,q)$ as the group. However, I am not very clear what properties of the group are reflected in this kind of sampling. I did look at Gromov-type theories, but got a bit lost.

As I mentioned in the beginning, I'll gladly refine the question and make it more narrow if recommended so. As of now am just lost since this isn't my area, and I'll be delighted with just some pointers at least.

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you please explain "symmetric generating set " ? $\endgroup$
    – mesel
    Commented May 28, 2017 at 12:14
  • $\begingroup$ Cross-posted to math.stackexchange: math.stackexchange.com/questions/2299840/… $\endgroup$
    – Lee Mosher
    Commented May 28, 2017 at 13:24
  • $\begingroup$ @mesel A symmetric generating set is a generating set that contains $s^{-1}$ whenever it contains an element $s$. It is generally preferred since it is easier to work with and mirrors the free group notion (also, the Cayley diagram can be treated as a graph as opposed to a directed graph). $\endgroup$
    – BharatRam
    Commented May 28, 2017 at 14:11

0

Reset to default

You must log in to answer this question.