3
$\begingroup$

Let $G$ be a finite group and $S$ be a symmetric generating set for $G$. (EDIT: Assume $S$ does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives of their conjugacy class in $Free(S)$. I am interested in certain properties of cyclically reduced words over $S$ and the values they correspond to in $G$.

1) Can every $g \in G$ be represented by a cyclically reduced word over $S$? Every element of $G$ can certainly be expressed as a reduced word over $S$ (simply because the Cayley graph $Cay(G,S)$ is connected, as $S$ is a symmetric generating set). But is this true for (the more restricted) cyclically reduced words too?

UPDATE: As pointed out in the comments, the answer is yes.

2) The total number of cyclically reduced words of length $k$ over $S$ with $|S|=2m$ is $$(2m-1)^k + m + (m-1)(-1)^k$$ as shown in https://math.stackexchange.com/questions/825830/reduced-words-of-length-l?rq=1 and the references mentioned. But suppose I want to know how many cyclically reduced words evaluate to a specific element $g \in G$, then is there some closed form expression for this?

For instance, if we are interested in the number of reduced words of length $k$ that map to a particular element of $G$, then we can write this out using the non-backtracking operator on the adjacency matrix of $Cay(G,S)$. This is because the sequence of directed edges on a non-backtracking walk on the Cayley graph can be interpreted as a reduced word over $S$. Using known properties of non-backtracking walks as discussed in What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean? this problem of reduced words can be dealt in a fully combinatorial fashion.

However, cyclically reduced words involve more delicate properties of the group and generating set (or labelled edges in the Cayley graph). But I am curious if we can construct some $|G| \times |G|$ matrix $$B_k$$ such that for every $g_1,g_2 \in G$, $$(B_k)_{g_1,g_2} = \#\{\text{cyclically reduced words of length k that evaluate to } g_2g_1^{-1}\}$$ on the lines of the similar analysis of reduced walks using non-backtracking operators.

Also posted on MathSE: https://math.stackexchange.com/questions/2322707/cyclically-reduced-words-and-cayley-graphs

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ For 2, use that the cyclically reduced words form a regular language and the set of words representing a given element of a finite group is a regular language. Build the automaton for the intersection of these languages and use the adjacency matrix for the automaton. $\endgroup$
    – Benjamin Steinberg
    Commented Jun 14, 2017 at 13:37
  • 4
    $\begingroup$ For 1, since the group is finite, there is no need to use any inverses of generators, so the answer is apparently yes. But I am unclear how you are regarding involutory generators. Would you regard the word $aba$ in the group $\langle a,b \mid a^2=b^2=1, aba=bab \rangle$ as being cyclically reduced? $\endgroup$
    – Derek Holt
    Commented Jun 14, 2017 at 13:43
  • 2
    $\begingroup$ @BharatRam, cyclically reduced should just mean that the last letter is not the inverse of the first. $\endgroup$
    – Benjamin Steinberg
    Commented Jun 14, 2017 at 14:04
  • 3
    $\begingroup$ If there are no involutory generators,then, as I explained in my previous comment, the answer to 1) is clearly yes. $\endgroup$
    – Derek Holt
    Commented Jun 14, 2017 at 14:07
  • 2
    $\begingroup$ @BharatRam: Ben Steinberg explained how to find a closed form solution using finite state automata. For a general finite group, you're not going to get a better answer. $\endgroup$
    – Andy Putman
    Commented Jun 14, 2017 at 21:46

0

Reset to default